Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

DevLiquidKnight

Calculating if a point is within a triangle?

This topic is 5723 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Advertisement
sopose that you have the triangle (v1, v2, v3) and the point p

then if

(v2-v1)x(p-v1), (v3-v2)x(p-v2) and (v1-v3)x(p-v3) have all the same sign the point is in the triangle.

x is the vectorial product

// naher

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
MollerTrumbore97
http://www.acm.org/jgt/papers/MollerTrumbore97/

Share this post


Link to post
Share on other sites
Basically, three half-plane tests that all have to return the same sign. This allows you to generate your normals in either direction, as long as they''re all consistant.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
but how about p is in line v1 and v3??ie p, v1, v3 are collinear

Share this post


Link to post
Share on other sites
Right, so to expand the half-plane test rule, all non-zero numbers have to be the same sign. If two of the numbers are zero though, then it''s automatically inside the triangle, because that means it''s colinear with two of the sides (i.e on the corner).

Share this post


Link to post
Share on other sites
Just a quick tip:

If you''re scanning through lots of triangles to see if the point falls within them, it can be handy to use a quick test to test if it DOESN''T lie in the triangle.
E.g. if x-value of the point is less than the x-values of the all the triangle corners, then you can skip that triangle.
Then you only use the proper point-in-triangle stuff if the quick tests pass.

I''m sure you get the idea. This should speed it up a little.

Share this post


Link to post
Share on other sites
Each "variable" would be the distance from the point to each side respectively. The distance from the point to a side is defined by:

DotProduct(point, sideNormal) - DotProduct(sideNormal, known point on side)

But like tuita said, always perform the trivial tests first so you can possibly eliminate superfluous calculations.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!