[GRASS-user] [GRASSLIST:1192] New Ideas for geometry simplification

[Ralf Gerlich]

Hi all,

by Markus Neteler's request I'd like to present some ideas I have for
geometry simplification.

A bit on the background: I'm part of a team trying to establish a more
detailed and correct landuse database for use for scenery for the
FlightGear flightsimulator (http://www.flightgear.org/) The landuse data
needs to be free as in beer and in speech (GPL-compatible).

We're currently looking into automatic classification of Landsat7
imagery. While the classification algorithms provided by GRASS do a very
good job on raster classification, we need to convert the raster data
into a set of polygons which may not be too complex for realtime rendering.

Unfortunately, v.clean lacks quite heavily in terms of scalability. As
soon as areas to be simplified get a bit larger (starting at about 30
square-km), the time used for simplifying the dataset gets inacceptably
large. I tried it once and had it run for about 8 hours on such a
dataset on a Pentium M with 1.5GHz and 512MB of RAM. After that the run
had to be canceled as the computer had to be put to another use ;-)

So here's my idea. It is basically built around the Quadric Error Metric
simplification method by Michael Garland. A description of the method
can be found at http://graphics.cs.uiuc.edu/~garland/research/quadrics.html.

Garland applies the typical edge-collapse approach, always collapsing
the edge with the currently lowest predicted error. The error is
calculated using quadrics, which can be efficiently updated after
edge-collapse. The error-sorted list of edges is managed using a heap,
which can be efficiently updated.

Furthermore the approach can apply the quadrics in order to find the
point with lowest error for each edge. The quadrics do in a way describe
the curvature of the surface or polyline to be simplified. Instead of
just removing vertices or triangles, this approach therefore allows to
rearrange the remaining vertices in order to minimise the visual error.

I already did some experiments using pure line data and some results can
be seen at http://custom-scenery.org/Line-data-simpl.275.0.html

The idea for applying this also to polygon data would be to perform a
triangulation on the polygon data set. It would be necessary to record
for each triangle edge whether it originated from a boundary segment and
if it did, from which. Furthermore it would be necessary to record for
each triangle the area of which it was part.

However, instead of using the distance from the adjoining triangles as
error metric for a vertex - as Garland does - the polygon simplification
would use the distances from the adjoining boundary segments. In case of
3D-data one could also use the distance from the adjoining triangles in
addition and add the boundary distance multiplied by some weighting factor.

After happily collapsing edges until a specified maximum error or a
maximum number of vertices, edges or triangles is reached the algorithm
would have to convert the triangle and edge set into a boundary and
centroid set again, which should be no principal problem using the data
about boundaries and areas attached to edges and triangles.

Note that the maximum error specified would not be an exact error as in
the classical v.clean approach but rather a measure for the visual error.

The algorithm would have several advantages performance-wise over
v.clean. First of all, it has an efficiently updatable data structure
for selecting edges to collapse and calculating errors. Furthermore
using the triangulation there is a simple method for determining whether
an edge collapse would turn a polygon over on itself: Watch for triangle
normals flipping. If an edge collapse would flip the normal of any
adjoining triangle, leave the edge as it is and put it back onto the
heap with an appropriate error penalty. Why not remove it from the heap?
Because after some further edge collapses the topology may have changed
so far so that the edge can be collapsed then.

Let me know what you think.

Cheers,
Ralf