Archived

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

__fold

Simple inside convex polygon question

Recommended Posts

At gamastura there's an article about inside convex polygon testing for points. The first example confuses me a bit. Shouldn't the quad be splitted? If it looks like this, numbers are vertices. Letters are vectors. 1A2 D\B 4B3 then according to me first test create vector and normal for vector 3 to 1 if the point is on top side do the dotproduct test for B ans A else do the dotproduct test for C and D Shouldn't this give 3 multiplications less? http://www.gamasutra.com/features/20000210/lander_01.htm [edited by - __fold on September 2, 2003 5:49:46 AM]

Share this post


Link to post
Share on other sites
> Shouldn''t this give 3 multiplications less?

Sometimes yes, sometimes the opposite ;->

The standard algo presented by Jeff allows an ''early-out'' with each edge-test ( if the point is outside the edge, it must be outside the poly ). The splitting variant does not have this property for the split edge tests.

Once you factor in other complications ( the standard algo results in simpler, smaller code with less branching ) the standard algo will win out on average unless the input polygons have a very large number of vertices.

Share this post


Link to post
Share on other sites
The branching can be eliminated. My algo saves a dot product, a normal calculation and an vector subtraction.
It''s true though that my version must do an extra test before first exit. So it depends on how often the point will actually be inside the quad. If WCET only matters then my version would be nice.

But I know, it''s against the rules to not do calculations as late as possible.

Share this post


Link to post
Share on other sites