3 replies to this topic

[Werner291]

Hello,

In 3D, say you have a triangle defined by three non-aligned points (A,B,C).

How do I find out if the projection of a fourth point onto the plane that the triangle belongs to is inside the triangle?

Edited by Werner291, 27 November 2012 - 10:48 AM.

[Álvaro]

The obvious solution is: Compute the projection of the point onto the plane, then check if it's inside the triangle (easiest way to do that part is probably to express the point on the plane in a reference that has a vertex as origin and two sides as vector basis).

A less obvious solution: Compute the planes defined by the sides of the triangle and a perpendicular to the plane, check if the point is on the "inside" of each of the planes.

I don't think there are big differences to prefer one over the other, but I would go for the less obvious solution because it feels more robust.

[Werner291]

I took your second solution, it works excellently!

Here's the resulting code:
[source lang="cpp"]Ogre::Vector3 vectorOA = wallStrip[itr-2]; Ogre::Vector3 vectorOB = wallStrip[itr-1]; Ogre::Vector3 vectorOC = wallStrip[itr]; Ogre::Vector3 vectorAB(vectorOB - vectorOA); Ogre::Vector3 vectorBC(vectorOC - vectorOB); Ogre::Vector3 vectorCA(vectorOA - vectorOC); Ogre::Vector3 faceNormal = vectorAB.crossProduct(vectorCA) * (itr%2==0 ? 1.0 : -1.0); // It's a triangle strip if (vectorOA.dotProduct(faceNormal) > 0){ Ogre::Vector3 ABNormal = vectorAB.crossProduct(faceNormal); if (vectorOA.dotProduct(ABNormal) > 0) continue; Ogre::Vector3 BCNormal = vectorBC.crossProduct(faceNormal); if (vectorOB.dotProduct(BCNormal) > 0) continue; Ogre::Vector3 CANormal = vectorCA.crossProduct(faceNormal); if (vectorOA.dotProduct(CANormal) > 0) continue; // The projection falls within the triangle }[/source]

It also checks wether the point is on a specific side of the triangle, it's also inside a loop iterating through a vector of these triangles.
The point that I'm testing is actually the origin in this case, that's why you don't actually see it in the code.

It actually even worked the first time! (That was very unlikely, I'm a champion at typos )

Edited by Werner291, 27 November 2012 - 11:50 AM.

[Zipster]

The projection approach isn't all that bad, all you need is the projection matrix:

P = (M^TM)^-1M^T

Like Alvaro said, use two sides of the triangle as the basis vectors, in this case we'll use (B-A) and (C-A), where 'A', 'B', and 'C' are the triangle points. Plug those vectors into the columns of matrix 'M', which makes it 3x2. Solve for the projection matrix 'P', which can be done by hand since the matrices are small, and then easily translated to code.

Now let's say you're testing point 'D'. All you do is multiply (D-A) by the previously calculated projection matrix 'P', which results in a 2D vector. This is the coordinate of the projected point in the subspace defined by the original basis vectors. Let's call the coordinate values 'x' and 'y'. It follows that that the projected point is in the triangle iff the sum (x+y) is less than or equal to 1, and both 'x' and 'y' are non-negative.

I know the explanation seems pretty intense, but once you've boiled down the math, it ends up being only a few lines of code