Jump to content

  • Log In with Google      Sign In   
  • Create Account

We need your help!

We need 7 developers from Canada and 18 more from Australia to help us complete a research survey.

Support our site by taking a quick sponsored survey and win a chance at a $50 Amazon gift card. Click here to get started!

Does the projection of a point onto a plane belong to a triangle in that plane? (3D)

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
3 replies to this topic

#1 Werner291   Members   -  Reputation: 149


Posted 27 November 2012 - 10:47 AM


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.


#2 Álvaro   Crossbones+   -  Reputation: 16536


Posted 27 November 2012 - 11:10 AM

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.

#3 Werner291   Members   -  Reputation: 149


Posted 27 November 2012 - 11:45 AM

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 Posted Image)

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

#4 Zipster   Crossbones+   -  Reputation: 1375


Posted 01 December 2012 - 04:16 AM

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

P = (MTM)-1MT

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 :)

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.