Re: Constructing pfASD

New Message Reply Date view Thread view Subject view Author view

Lee Willis (lwillis++at++inreach.com)
Sat, 28 Mar 1998 12:04:56 -0800

Thom DeCarlo wrote:
>Lee Willis wrote:
>>
>> >From: Jonas Andersson <jonasa++at++cs.umu.se>
>> >To: info-performer++at++sgi.com
>> >Subject: Constructing pfASD
>> >Date: Friday, March 27, 1998 1:52 AM
>>
[snip]
>> >I would like to construct LODs from a high resolution set of
>> >triangles where certain features, e.g. outlines of areas like
>> >lakes, glaciers, etc. should change at a slower rate across
>> >several LODs than the number of triangles inside these areas.
>>
>> >Are there well-known algorithms solving this problem as well?
>>
>> No. :-( Constructing an ASD "bottom-up" (starting from the most
>> detailed and working backwards) is a particularly thorny problem,
>> one I was never able to crack adequately. This is because of the
>> requirements of how an each LOD in an ASD must be connected to each
>> other. It is much simpler to start with a coarse tesselation and
>> subdivide it according to those rules than to start with a fine
>> tesselation and merge those into coarser samples.
>
>It might be simpler, but it makes the technology less than useless for
>accurate terrain modeling.

How so? A top-down-generated irregular ASD mesh comes very close to the
RMS error of
a standard Delaunay triangulation for the same # of polygons.

>It becomes something to be _avoided_! Our
>applications need to ingest sub-meter elevation post spaced data and we
>want to smoothly reduce resolution as the viewer moves away from the
>terrain. This seems to be exactly the opposite of the situation you
>describe.

So far I don't understand what the problem is. The Multigen CAT
implementation
of ASD does just that, picks out the most significant points for each LOD,
working
from coarsest to finest, injecting new points to each LOD to better
approximate the
surface.

>> >Are there any free/cheap libraries or source code supporting such
>> >algorithms?
>>
>> None that I know of.
>>
>
>I thought there was something presented at SIGGRAPH'97 that addresses
>this. (Sorry, I don't have the course notes with me.)

There are libraries and algorithms which will do mesh simplification,
reducing triangular meshes
while maintaining their approximate shape, but an ASD mesh requires some
very strict
rules for connectivity between LODs, which the current mesh decimation
algorithms do not obey.
(The connectivity rules are discussed in my 96 IMAGE Conference paper "A
method for
Continuous Adaptive Terrain".)

You cannot take a mesh, and any simplification of that mesh, and be
guaranteed that there exists
a set of ASD steps that will get you from one to the next.

What you *could* do, is use a mesh simplification/decimation algorithm
(e.g. wavelet simplification)
to create a simplified base mesh, and then reconstruct finer levels of
detail from that base mesh which
would follow the ASD connectivity requirements. The best LOD of this mesh
would approximate your
initial mesh, but would not exactly match it.

>> ------------------------------
>> Lee Willis Virtual Landscape Dermatologist
>>
>> lwillis++at++terrex.com TERREX
>>

=======================================================================
List Archives, FAQ, FTP: http://www.sgi.com/Technology/Performer/
            Submissions: info-performer++at++sgi.com
        Admin. requests: info-performer-request++at++sgi.com

New Message Reply Date view Thread view Subject view Author view

This archive was generated by hypermail 2.0b2 on Mon Aug 10 1998 - 17:57:06 PDT

This message has been cleansed for anti-spam protection. Replace '++at++' in any mail addresses with the '@' symbol.