[AD] Triangulator broken

[ Thread Index | Date Index | More lists.liballeg.org/allegro-developers Archives ]


I ran into this bug in the polygon triangulator. Due to the way it's written,
I think it may be a difficult fix, but maybe Michal would be able to do it more
easily... Here's the situation.



+-------------------------------------------------------+ a
|                                                       |
|                                                       |
|                 +-------+                             |
|                 |        |         +----+             |
|                 |         \        |    |             |
|                 |          |       +----+             |
|                 +----------+         ^ hole 2         |
|                             x                         |i
|                   ^ hole 1                            |
|                                                       |
|                                                       |
|                                                       |
|                                                       |
|                                                       |
+-------------------------------------------------------+ b

  ^ outer polygon

From my understanding of Michal's code, when calculating splits for the holes,
a ray is cast from the rightmost edge of a hole (marked with x) to the nearest
intersection to the right (i). The problem is that that's all it tries. It then deems
that either point a or b is suitable for the split. The problem is that if you look at this
diagram, drawing a line from x to a is going to pass through a hole which is a
no no. b is open but there could easily be another hole there, too. In my own
triangulator (which has flaws of its own), I do the nearest right intersection
test, then cast rays to point a or b. If that ray hits anything before a or b
then I recalculate with the split now on hole 2. Looking at the code, I don't
know how to proceed because hole 2 may not be part of the vertex list at the time
hole 1 is processed (if hole 2 appears later in the data you pass).

Michal, any chance you can take a look or at least advise on this?

Trent



Mail converted by MHonArc 2.6.19+ http://listengine.tuxfamily.org/