[ 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