| Re: [AD] Triangulator broken |
[ Thread Index |
Date Index
| More lists.liballeg.org/allegro-developers Archives
]
I just spotted second mail.
On 13 March 2011 11:37, Michał Cichoń <michcic@xxxxxxxxx> wrote:
> Algorithm is working in a little bit different way. All holes are
> sorted from right to the left according to most right vertex in the
> hole. Therefore First handled hole will be hole 2. Split line will go
> from bottom right vertex to 'b' vertex. After merge, the only hole
> will be the hole 1. Second goes as on the picture:
>
> +-------------------------------------------------------+ a
> | |
> | |
> | +-------+ |
> | | | -+----+ |
> | | \ B / | | |
> | | | / +----+ |
> | +----------+- \ |
> | x \ |i
> | ^ hole 1 ^ hole 2 \ |
> | \ A |
> | \ |
> | \ |
> | \ |
> | \|
> +-------------------------------------------------------+ b
>
> If split is done incorrectly, then probably sorting fail in some way.
> Do you have any specific set of data which produce wrong
> triangulation?
>
>
> On 13 March 2011 09:13, Trent Gamblin <trent@xxxxxxxxxx> wrote:
>> 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
>> ------------------------------------------------------------------------------
>> Colocation vs. Managed Hosting
>> A question and answer guide to determining the best fit
>> for your organization - today and in the future.
>> http://p.sf.net/sfu/internap-sfd2d
>> --
>> https://lists.sourceforge.net/lists/listinfo/alleg-developers
>>
>
>
>
> --
> thedmd, Michał Cichoń
> Artifex Mundi
> michcic@xxxxxxxxx
> http://www.artifexmundi.com
>
--
thedmd, Michał Cichoń
Artifex Mundi
michcic@xxxxxxxxx
http://www.artifexmundi.com