Drawing polygons, collinearality & clockwise point tests

Drawing polygons, collinearality & clockwise point tests

Post by Thomas Hart » Thu, 24 Sep 1998 04:00:00



Hi,

        I have implemented a polygon renderer that works only if it can be
entirely sure which way round the points of a polygon are in terms of
clockwise or anti-clockwise (it is always one or the other).

        Now, I have implemented this into my code such that the regular reverse
face polygon test is used - that is it does the 'd' part of the plane
equation and compares it to 0. However, this is very occasionally
incorrect.

        What happens is this, the points, when projected are effectively
collinear. However, accuracy being what it is and so on, they actually
end up being projected to be anti-clockwise when the plane test implied
they would project to be clockwise. This really breaks my polygon
routines, like you wouldn't otherwise believe!

        So, I am wondering the way around this. Is there a quick check for
collinearity, or near collinearity? (possibly quicker than one compare
per scanline to check x1 really is < x2 at resolutions from 320x200 up
to 1024x768). Or maybe some sort of check on the projected points for
clockwise / anti-clockwise? Or maybe something more devious I did not
think of?

        collinearness shouldn't actually mess up the polygon rendering by the
way . . . but in polygons that are almost horizontal, this can be a real
problem.

                -Thomas

 
 
 

1. clockwise or counter-clockwise 2d polygons


I believe that it would be much easier to use the simple formula which
computes the AREA of the polygon and then look at the resulting sign.

For a clockwise polygon, the area is:

sum ( ( x(i) - x(i-1) ) * ( ( y(i) + y(i-1) ) ) / 2

Where x(i),y(i) and x(i-1),y(i-1) are adjacent pairs of points going
clockwise around the polygon.

If the sum comes out negative then the polygon was counter-clockwise.

Of course, if you only want the area then don't bother to divide by two.

This is much easier to code, although it is possible that for very long,
thin or otherwise strange polygons, some special case code might be
better.  Similarly, this formula is not guarenteed to work with polygons
that have crossed edges (I don't know what is defined to be clockwise
then, anyway).

I posted the derivation of the area formula sometime last year.

DLL

2. graphics board- QUESTION

3. Clockwise/Counter-clockwise polygon winding

4. HP SCanjet IIc: Control Language??

5. Clockwise polygon point ordering ...

6. AREA LIGHTS

7. 2D Point in Concave Polygon Test

8. OpenGL picking

9. "Fastest Point in Polygon Test"... Answe

10. "Fastest point in polygon test" - Haines

11. Strang problem while using point in a polygon test

12. 2D Point in Concave Polygon Test