🔒 Locked

Simple inside convex polygon question

Started by __fold Sep 2, 2003 at 4:46 AM 1 replies 1k views

Original Post

Sep 2, 2003 at 4:46 AM

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]

Osc

Sep 2, 2003 at 6:46 AM

> 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.

__fold

Sep 2, 2003 at 7:24 AM

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.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.