The first fault is inside the gpc code. As I said before, by my best
estimation, gpc is algorithmically correct, but when we throw arbitrary real
world numerical data at it, we can encounter some numerical degeneracies and
that can blow up the gpc routines.
I have no complaints if someone wants to dive into gpc and make it more
numerically stable, but that's beyond what I've ever wanted to tackle
myself.
I'm sure there are a few dumb bugs in the code, but at least for this
particular issue, if you are hoping that the fix is a one or two line patch
that fixes a dumb programming typo, I afraid that's not the case.
You have to dive deep into the underworld of polygon clipping and numerical
representation. You need to get down to the level where flipping one
trailing bit in a floating point number is the difference between the
algorithm being numerically stable, or things going degenerate.
Because of the way things work with computer floating point numbers, after
clipping one region against another, you can end up with artifacts like a
zero area triangle or a boundary that goes out to a point, returns to the
previous point, and then continues on. Things happen that you can't see
with the naked eye until you zoom in with an electron microscope.
The basic process is that terragear/genapts is creating a jigsaw puzzle out
of a collection of almost arbitrary polygon data. The source data could
overlap in any variety of ways (even by just a very very very tiny bit.)
There could be cracks and gaps in the input data. We have to resolve
questions like: what if a road, airport runway, and ocean area all want to
occupy the same physical space (due to different data sets assembled with
different standards of precision.) The end result can't have any slivers
that are too small, and can't have any gaps or cracks. It needs to be
topologically consistent. However, given the nature of the input data and
the nature of ieee floating point numbers, this is not always possible to
do. And as the input data gets more detailed, these problems are magnified.
So my suggestion is to focus on how to maintain a topologically consistent
numerical representation of arbitrary polygon data while performing
arbitrary clipping and union functions to the pieces. That is where the
problems will get cured.
Hunting for a stray null pointer that some programmer inadvertently screwed
up, or digging into gcc optimization routines might all be interesting, and
you may just find some real problems that have been lurking, but you won't
have addressed the core underlying issues that cause most of the problems
with terragear.
One possible solution would be to create a fine grid and map all the input
data to our grid --- but there are some challenges with properly mapping an
arbitrary polygon (out of some gis database) to our underlying grid. That
can't be done perfectly so all kinds of special cases will need to be
discovered the hard way and dealt with.
Maybe we could create really fine mesh, and then "paint" each grid section
based on the highest ranking polygon type that covers that grid. Maybe this
could even be done in the form of a raster image? There are probably ways
this could be done to avoid the polygon clipper problems, but none of these
approaches would be trivial to implement and would bring their own unique
challenges and problems that we'd have to discover the hard way through
trial and error.
And with all of this, I'd love for anyone to advance the discussion by
jumping in with code that fixes the problems or new ways to do things that
are better than the way we were doing things before ... or even evidence
that proves me entirely wrong. I'm stating the way I understand things and
the observations and evidence I have ... and my hope is that it lights a
fire under someone to advance the discussion by proving me wrong or coming
up with something better ... while simultaneously saving people from hunting
for problems in fruitless areas.
Best regards,
Curt.
On Mon, Apr 18, 2011 at 12:20 PM, Christian Schmitt wrote:
> Curtis Olson wrote:
>
> > Right, as said before, you crashed inside the gpc code. Have you tried
> > regenerating this airport using the --nudge option (increasing the value
> > in small increments until you find a value that allows the airport to be
> > successfully built.)
> >
> > Regards,
> >
> > Curt.
>
> Curt, it's not a question of finishing this build, it's a fact that
> something is broken and I'd like to do my best to help get it fixed.
>
> FYI: I found another, different segfault with EGKK:
>
> Starting program: /usr/bin/genapts --input=./EGKK.dat --work=./test
> Input file = ./EGKK.dat
> Terrain sources =
> ./test/SRTM2-Africa-3
> ./test/SRTM2-Australia-3
> ./test/SRTM2-Eurasia-3
> ./test/SRTM2-Islands-3
> ./test/SRTM2-North_America-3
> ./test/SRTM2-South_America-3
> ./test/DEM-USGS-3
> ./test/SRTM-1
> ./test/SRTM-3
> ./test/SRTM-30
> Work directory = ./test
> Nudge = 10
> Longitude = -180:180
> Latitude = -90:90
> Data version = 810
> Next airport = EGKK 196
> End of file reached
> last_apt_id.length() = 4
> Building EGKK
> Runway count = 0
> Taxiway count = 1
> w010n50/w001n51/2941771
>
> Program received signal SIGSEGV, Segmentation fault.
> 0x000000000040fc55 in build_airport (airport_id=..., alt_m=0,
> runways_raw=..., beacons_raw=..., towers_raw=...,
> windsocks_raw=..., root=..., elev_src=...) at build.cxx:621
> 621 taxiways[i].generated = true;
> (gdb) bt
> #0 0x000000000040fc55 in build_airport (airport_id=..., alt_m=0,
> runways_raw=..., beacons_raw=..., towers_raw=...,
> windsocks_raw=..., root=..., elev_src=...) at build.cxx:621
> #1 0x0000000000444e15 in main (argc=3, argv=0x7fffffffda68) at
> main.cxx:442
>
>
>
> Chris
>
>
> ------------------------------------------------------------------------------
> Benefiting from Server Virtualization: Beyond Initial Workload
> Consolidation -- Increasing the use of server virtualization is a top
> priority.Virtualization can reduce costs, simplify management, and improve
> application availability and disaster protection. Learn more about boosting
> the value of server virtualization. http://p.sf.net/sfu/vmware-sfdev2dev
> _______________________________________________
> Flightgear-devel mailing list
> Flightgear-devel@lists.sourceforge.net
> 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
------------------------------------------------------------------------------
Benefiting from Server Virtualization: Beyond Initial Workload
Consolidation -- Increasing the use of server virtualization is a top
priority.Virtualization can reduce costs, simplify management, and improve
application availability and disaster protection. Learn more about boosting
the value of server virtualization. http://p.sf.net/sfu/vmware-sfdev2dev
_______________________________________________
Flightgear-devel mailing list
Flightgear-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/flightgear-devel
