Active Surface Definition
Project Goals
The goal of this project is to investigate the Active Surface Definition algorithm provided in SGI's Performer. The goal is do develop a viewer which implements the algorithm and then to develop the necessary logic to build quality ASD databases. SGI Performer is not used in this project, instead it is all developed from documentation on the algorithm.

ASD Algorithm
ASD is a simple algorithm at the surface, at least from a viewer stand point. (This is usually what makes a quality real-time algorithm, simplicity.) At any point, the algorithm can replace a given triangle with up to four children. To avoid popping, the vertices of the four triangles are morphed from points coincident with the edges of the parent triangle to their real locations. The decision on when triangles are replaced with their higher level of detail is driven by LOD switching ranges and an evaluation function.

Nice attributes of the algorithm are that only a vertex position and a morph vector needs to be store for each vertex. (Ignoring attributes.)

Viewer
The first phase of the project involved building a viewer capable of displaying ASD LOD structures. As part of this project, the structure for my ASD surfaces was set up. Mine are slightly different than Performer's. This viewer was then used to display all of the subsequent ASD surfaces.

ASD Generation from Regular Height fields
The second phase of the project was to generate ASD levels of detail from a terrain height field. Though it sounds relatively easy, the generation of ASD content has some challenges.

In this project, I took a top down approach to the LOD generation. Starting from two triangles, the algorithm add up to 3 vertices to each triangle on each LOD level to generate the next level. How does it do this? For each vertex it uses barycentric coordinates to determine the best edge to add it to, and to compute the height at that x,y position in the triangle. (In this case, I am using Z as altitude, not y.) For each edge it picks the vertex which has the largest variance between the real height at that point, and the computed height on the triangle. It adds these vertices for all the edges, computes their morph vectors, and we have the next LOD level. (This is essentially an iterative TIN generation algorithm, using a Local Error Metric.) To the right you will see an animation of the results of this algorithm.

There are a couple short comings to this algorithm, which should be fixed. The first is that there is no "well formed" triangle criteria used when selecting the verts for an edge. Only the largest variance is used for an edge, which can cause some long sliver style triangles. The second is a result of the first. Due to the sliver triangles that can result, the LOD tree can be unbalanced causing more LOD levels than would necessary with a balanced tree. The question is whether adding the vertices with the most error or adding more vertices on each LOD level is more important. Odds are the latter, because the larger error vertices will probably get added in the first couple LOD levels anyways unless there is a large peak near one of the original triangle corners. I might revisit this sometime to fix it.

An animation morphing from the coarsest LOD (2 triangles) through the first four LOD levels. For this animation, the entire level is morphed equally, distance from the eye point is not used.

Summary
ASD is a simple technique for run-time terrain LOD morphing. The problem with ASD is generating the ASD structure. For the regular sampled terrain, it was not that difficult to come up with a solution which should work fairly well. For TINs, it becomes more difficult to efficiently build ASD levels due to the restrictions on how many triangles may replace one and which vertices are static at what levels. Given some more thought, I believe a decent solution for generating ASD levels from a generic TIN can be developed.

glenn@raudins.com