On Sun, Oct 16, 2011 at 7:22 AM, Peter Sadrozinski wrote:
> The 'bad' nodes are points that are co linear with a previous segment on
> the same contour. When this happens, the even-odd algorithms used for
> clipping only see one intersection instead of two. So, as a scanline is
> evaluated, if we were currently outside a poly, we would then determine we
> were inside, when it should have gone back to outside.
>
I found that most of the problems with GPC were due to numerical precision
issues -- not in the algorithm itself, but in the data. When you throw a
world's worth of data at an algorithm, you are going to hit every special
case and degeneracy possible.
The results of numerical precision problems in GPC would lead to crashes or
logic errors down stream. As I methodically evaluated each problem and
followed it up stream I would find a lot of strange things. Things that are
harder to explain in email and easier in a picture ... But perhaps you can
imagine four points along some edge of a larger polygon: A, B, C, and D.
Now imagine B == D. That's not a very well behaved polygon because the BCD
triangle is zero area. One of the things that likes to blow up later with
bad data is the delauney triangulator.
> In papillon's terragear repo, we have integrated clipper, which is an
> actively supported clipping routine that has far fewer errors, and is faster
> as well.
>
I'm not writing this email to say that GPC is the fastest or the best, so if
there is something that is indeed better, sure it makes sense to use it.
> I still hit these bad nodes often still, however. I am experimenting with
> nudging these nodes perpendicular away from the segment they touch instead
> of removing them completely. Will update when if I get consistent results.
>
The problem usually is that if you nudge things around to fix one issue,
that act of nudging will probably cause numerical issues to be introduced
elsewhere.
This stuff is really really really tricky.
Here is a random thought: what if the polygon data was painted onto a raster
texture (of some "sufficient" resolution) in correct bottom up order, rather
than being clipped. Then at the end of the process we figure out how to
extract the resulting polygons from the raster image. This would completely
eliminate the polygon clipping (although not for the airport generation I
guess) but would require solving another difficult problem.
Regards,
Curt.
On Oct 16, 2011 7:22 AM, "Maxime Guillaud" <[email protected]> wrote:
>
>> On Sat, 15 Oct 2011 08:53:45 +0000 (UTC)
>> Martin Spott <[email protected]> wrote:
>> > I think the only solution is to make GPC obsolete - either by replacing
>> > GPC by something different but functional equivalent or "simply" (TM ;-)
>> > by avoiding any polygon clipping in 'fgfs-construct' overall.
>>
>> For what it's worth... I am currently trying to generate custom scenery
>> for all of Europe
>> based on Corine + OSM data (similar to what I did for France some time
>> ago:
>> http://wiki.flightgear.org/Custom_France_Scenery), and I am also getting
>> lost in the
>> intricacies of fgfs-construct and crashes in GPC.
>>
>> I managed to make a few changes in the code that improved the situation:
>> - conversely to what is suggested in README.gpc, I did not change the
>> GPC_EPSILON constant
>> (left it defined as DBL_EPSILON)
>> - I completely disabled the removal of so-called "bad nodes" in
>> poly_support.cxx
>>
>> However I did a lot of preprocessing of the data in Postgis before feeding
>> it to
>> fgfs-construct, hopefully removing the need for the hacks mentioned above.
>>
>> So far this configuration has proved very stable for me, and I was able to
>> generate
>> more than a hundred of 1x1 deg tiles without any crash.
>>
>> So far the only problems that remain seem to be located around the 0deg
>> longitude area -
>> there, I am still running into the problem of the NULL pointer in the GPC
>> merge_right().
>>
>> What I noticed so far lends me to think that there is a lot of code in
>> terragear that is
>> supposed to deal with imperfect input data - and should maybe be
>> deactivated.
>> Can anyone shed some light on what the "bad node" detection is supposed to
>> achieve, for
>> instance ? Also, the suggested increase of GPC_EPSILON is bound to
>> introduce
>> inconsistencies in the geometric routines - much better to clean up the
>> input data).
>>
>> Unfortunately, there are many places in terragear where some arbitrary
>> "epsilon" constants
>> are hiding with unexpected effects - just run "grep -r '0\.0000'
>> terragear-cs" and count
>> the matches if you don't believe me.
>>
>> So maybe the problem is not in GPC after all but in what we feed it....
>>
>> Maxime
>>
>>
>>
>> ------------------------------------------------------------------------------
>> All the data continuously generated in your IT infrastructure contains a
>> definitive record of customers, application performance, security
>> threats, fraudulent activity and more. Splunk takes this data and makes
>> sense of it. Business sense. IT sense. Common sense.
>> http://p.sf.net/sfu/splunk-d2d-oct
>> _______________________________________________
>> Flightgear-devel mailing list
>> [email protected]
>> https://lists.sourceforge.net/lists/listinfo/flightgear-devel
>>
>
>
> ------------------------------------------------------------------------------
> All the data continuously generated in your IT infrastructure contains a
> definitive record of customers, application performance, security
> threats, fraudulent activity and more. Splunk takes this data and makes
> sense of it. Business sense. IT sense. Common sense.
> http://p.sf.net/sfu/splunk-d2d-oct
> _______________________________________________
> Flightgear-devel mailing list
> [email protected]
> https://lists.sourceforge.net/lists/listinfo/flightgear-devel
>
>
--
Curtis Olson:
http://www.atiak.com - http://aem.umn.edu/~uav/
http://www.flightgear.org - http://gallinazo.flightgear.org
------------------------------------------------------------------------------
All the data continuously generated in your IT infrastructure contains a
definitive record of customers, application performance, security
threats, fraudulent activity and more. Splunk takes this data and makes
sense of it. Business sense. IT sense. Common sense.
http://p.sf.net/sfu/splunk-d2d-oct
_______________________________________________
Flightgear-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/flightgear-devel
