geometryrenderingraytracinggeometry-shader

3D point in triangle test, is the cross product required?


The point-in-triangle test from Scratchapixel lists the following pseudocode for determining of a point that lies in the plane of a triangle is also within the bounds of its edges.

Vec3f edge0 = v1 - v0;
Vec3f edge1 = v2 - v1;
Vec3f edge2 = v0 - v2;
Vec3f C0 = P - v0;
Vec3f C1 = P - v1;
Vec3f C2 = P - v2;
if (dotProduct(N, crossProduct(edge0, C0)) > 0 && 
    dotProduct(N, crossProduct(edge1, C1)) > 0 &&
    dotProduct(N, crossProduct(edge2, C2)) > 0) return true; // P is inside the triangle

I understand why this technique works but I don't understand why it's testing if the cross product is in the direction of the normal instead of just checking if the dot product with respect to the edges is positive.

Proposal :

Vec3f edge0 = v1 - v0;
Vec3f edge1 = v2 - v1;
Vec3f edge2 = v0 - v2;
Vec3f C0 = P - v0;
Vec3f C1 = P - v1;
Vec3f C2 = P - v2;
if (dotProduct(edge0, C0) > 0 && 
    dotProduct(edge1, C1) > 0 &&
    dotProduct(edge2, C2) > 0) return true;

This is just checking if the angle between the query point and each edge is not obtuse which I think is sufficient to check that it's in bounds?

I'm guessing there's some edge case I'm missing since the dotProduct method would otherwise have been more widely documented since it's much cheaper.

Thanks!


Solution

  • Think about dotProduct(edge0, C0) > 0. This means that the point P must be above the green line in the figure below.

    enter image description here

    Therefore, combination of all 3 conditions becomes like below. The shape of region consist of the 3 green lines don't match to the triangle.

    enter image description here