RE: [AD] Bug in clip3d_f() / polygon3d_f()

["Ben Davis" <ben@xxxxxxxxxx>]

> I wrote this stuff :-) Well, in fact the function checks the order the
> vertices are given in, in order to fill the double-linked list of points
> in clockwise order in every case (so it handles both cases : clockwise
> and anticlockwise). IMHO to fix the bug you mentionned we should just
> change the way the function checks the vertices order. So far, it
> computes the cross product of two vectors made with the first three
> vertices, so if two points among the first three ones are close or
> coincident the check will fail and the poly won't be drawn. I think a
> better way to test the points order would be to check the sign of the
> polygon area : such a test would rely on every vertex coordinates
> instead of using the first three vertices and would therefore be more
> robust.

Nice idea, but I've already solved the problem :-) Rather than ensuring the
edges are stored in clockwise order, the routine is now adapted to handle
both scenarios.

Here are patches for poly3d.c and aintern.h. The functions now handle
coincident vertices properly. I believe the patches can be applied safely to
CVS, but just so everyone knows exactly what I did, here goes:

1. The polygon_z_normal() calls and equivalents, used to ensure that the
list of edges is created in a clockwise fashion, have been removed. The
edges could go in either direction, depending on the input vertices.

2. _fill_3d_edge_structure() and -_f() now take it upon themselves to fail
if an edge is horizontal or gets clipped out of existence. This avoids a
possible floating-point divide-by-zero in one of them (albeit one with no
consequence). It also means these checks do not have to be done by the main
code, so the fceil() calls only occur once - within
_fill_3d_edge_structure(). The functions now return an int. I had to change
the prototypes in aintern.h - but seriously, do those prototypes need to be
there?

3. In do_polygon3d(), left_edge and right_edge don't necessarily correspond
to the left and right edges of the polygon. They could be reversed. As a
result of this ambiguity, I was able to simplify the code to check that
left_edge and right_edge would properly traverse one side of the polygon
each. However...

4. draw_polygon_segment() now swaps the two edges if they are the wrong way
round. It compares the x-coordinates of the tops of the edges. If they are
equal, it compares the values of dx.

5. I have made equivalent changes to the triangle3d() and triangle3d_f()
functions.

I've tested the floating point functions, and they now work perfectly. I
haven't tested the fixed point equivalents.

Finally, comments on what I said before:

> However, I can say for sure that this problem was introduced
> since the last WIP, and exists in the CVS version. I suspect it was
> introduced when the polygon3d functions were given proper sub-pixel
accuracy
> (or did I imagine that? :-)

I can't explain this. If I had the motivation to look at the old file from
the WIP, I probably could explain it, but since it works now, there's
probably no point.

> At the same time, I'd like to point out that the polygons often miss the
> left and top edges of the screen by 1 pixel. This never used to happen.

I think this must just have been 1-pixel-thick polygons not appearing at the
edges, because the gaps are filled with 1-pixel-thick polygons now, using
the new patches. Weird :-)

> I could spend ages puzzling over the inner
> workings of these functions, but I thought it would be better if
> the problem was fixed by someone who already knows what's going on.

Well I guess I spent ages :-) I just couldn't wait!

Ben Davis

PS Apologies to Laurence for consistently spelling his name wrong!

Attachment: aintern.h.diff
Description: Binary data

Attachment: poly3d.c.diff
Description: Binary data