CODEWITHSUNDEEP
3dgeometry
NotGoodAtMaths
NotGoodAtMaths

Reputation:

Determine if a 3D point is within a triangle

Given a 3D point (x, y & z), and a triangle made of three other 3D points, how can I determine if the point is in triangle?

I've read a lot about doing this in 2D, the most helpful being http://imusthaveit.spaces.live.com/blog/cns!B5212D3C9F7D8093!410.entry, but I'm struggling to move the concept to 3D - could anyone help with either the general concept or code example?

Ultimately what I'm wanting to do is obtain a list of points that can represent the interior of the triangle.

Upvotes: 2

Views: 19014

Answers (8)

Stephen Duffy
Stephen Duffy

Reputation: 505

If you know the normal to the plane, which is the cross product of two of its edges, you can get rid of the axis suggested by the largest sub-co-ordinate of that normal and look at the triangle in the optimal orthographic plane. To do the test of the point inside the edges (or not), I found this very helpful.

http://jsfiddle.net/PerroAZUL/zdaY8/1/

The program is mostly about making things nice and easy but the algorithm you are looking for is contained in this method:

function ptInTriangle(p, p0, p1, p2) {
  var A = 1/2 * (-p1.y * p2.x + p0.y * (-p1.x + p2.x) + p0.x * (p1.y - p2.y) + p1.x * p2.y);
  var sign = A < 0 ? -1 : 1;
  var s = (p0.y * p2.x - p0.x * p2.y + (p2.y - p0.y) * p.x + (p0.x - p2.x) * p.y) * sign;
  var t = (p0.x * p1.y - p0.y * p1.x + (p0.y - p1.y) * p.x + (p1.x - p0.x) * p.y) * sign;
  return s > 0 && t > 0 && (s + t) < 2 * A * sign;

}

Upvotes: 1

Solveering
Solveering

Reputation: 31

Just my observations for improvement on this (old) post. If you (pre-) compute the U&V vectors for the triangle (U being the vector from A to B and V being the vector from A to C in a standard triangle A-B-C, both U and V are not necessarily unit length) then the vector P (from A to the Point) can be used in the following way: compute dot product of P with U and P with V. If both dot products are less (or equal for point on edge) to one but larger (or equal) to zero and their sum is less than (or equal) to one , then the point is inside, otherwise it is outside. This approach is more efficient than to first compare the normals (cross products) and then also their dot products. This approach does not require that the points are in fact already in the order that form a right handed triangle and as such more stable. What it does require is that the point lies in the plane (or close to it) in order to be approximately accurate.

Upvotes: 0

omid
omid

Reputation: 51

private bool PointInTriangle(Vector3[] TriangleVectors, Vector3 P)
    {
        Vector3 A = TriangleVectors[0], B = TriangleVectors[1], C = TriangleVectors[2];
        if (SameSide(P, A, B, C) && SameSide(P, B, A, C) && SameSide(P, C, A, B))
        {
            Vector3 vc1 = Vector3.Cross(Vector3.Subtract(A, B), Vector3.Subtract(A, C));
            if (Math.Abs(Vector3.Dot(Vector3.Subtract(A, P), vc1)) <= .01f)
                return true;
        }

        return false;
    }

    private bool SameSide(Vector3 p1, Vector3 p2, Vector3 A, Vector3 B)
    {
        Vector3 cp1 = Vector3.Cross(Vector3.Subtract(B, A), Vector3.Subtract(p1, A));
        Vector3 cp2 = Vector3.Cross(Vector3.Subtract(B, A), Vector3.Subtract(p2, A));
        if (Vector3.Dot(cp1, cp2) >= 0) return true;
        return false;

    }

Upvotes: 5

DarenW
DarenW

Reputation: 16906

Given point P and triangle A, B, C, compute:

1. the unit normal of triange (A, B, P)  - call it N1
2. the unit normal of triangle (B, C, P) - call it N2

(get the order right!)

Now think about the dot product N1*N2. if P is in the plane of the triangle, and inside the three sides, those normals should be parallel, so this dot product will be 1.0000 (or 0.999...). If P is kept in the plane but moved beyond side BC, those two normals will be opposite: N1*N2==-1. If P isn't in the plane, the dot product will be some intermediate value. Whoops, we still have a loophole - if P goes out past side CA. We need to compute one more:

3.  the unit normal (C,A,P) called N3

Make these two tests (in an ideal world):

N1*N2 == 1.0 ?
N2*N3 == 1.0 ?

(testing N3*N1 is redundant) Of course, the test will have to allow some slop for the imperfections of computer arithmetic. Look for (N1*N2 > 1-epsilon) where epsilon is some small value, depending on accuracy needed and floating point types.

You may need a formula for these unit normals. Given (A,B,C) compute the cross product N =(B-A)x(C-B). Then divide by sqrt(N*N). Definitions of "dot product" and "cross product" are easy to find in textbooks and wikipedia etc. It is possible to increase performance with some algebra to about square roots.

I don't claim this is the fastest algorithm, but should work (until so

Upvotes: 9

danio
danio

Reputation: 8653

Given a 3D point P and three vertices of a triangle T1, T2, T3

Now you can transform all the points to the 2D problem of finding a point in the triangle. Also the distance of P to the plane will tell you how close the point is to being exactly on the triangle.

If I understand your elaboration correctly you are planning to examine all the voxels in your 3D grid to find out if they are in a given triangle? This would be very inefficient - I think a 3D version of Bresenham's line algorithm may work for what you want to do. It would be trivial to find the voxel that T1 is in, then progress through the voxels towards T2, repeating for T3 and back to T1.

Upvotes: 2

pauljwilliams
pauljwilliams

Reputation: 19225

  1. Use the three points of the triangle to calculate the equation of the plane in which they lie
  2. Check if your point satisfies that equation.

Upvotes: 0

Robin Day
Robin Day

Reputation: 102478

Are you really talking about 3 points of a triangle or 4 points of a pyramid?

A single point is extremely unlikely to ever exactly be on the plane of a flat triangle in a 3d space.

EDIT:

As an idea for the triangle version (as it seems you want). You could perform 3x2D checks. Discard the Z cooridinates from your check point and the three triangle points, then see if the point is in the plane using your existing method. Then do the same disregarding just the X coordinate and then again disregarding just the Y coordinate. I'm sure its not the most efficient method, but it will be simple to code.

Upvotes: 6

David Johnstone
David Johnstone

Reputation: 24450

The method described here is very good for the 2D case. I think it is possible to modify this to work in 3D. This doesn't directly answer your question, but if you understand this method you should be able to work out how to modify it for 3D (if that is possible).

Upvotes: 3

Related Questions