HOOPS' LOD Module


Definition
Why Implement LOD?
The Challenges
Technical Details
Switching
Selection
Recalculation Behavior
Acknowledgements


Definition

We define LOD as a reduction of model complexity to improve rendering time.

Examples of ways in which to reduce geometric complexity include:

Wireframe bodies in place of polygons
Bounding volumes in place of the original models
Single polygon with a pre-rendered image of the model as a texture
Removal of text/markers
Ignoring face and edge patterns à i.e., avoid fonting at the DC level
Surface simplification to remove excessive detail in a polygonal mesh

Our first pass at LOD, first released in HOOPS 4.5, supports only the last of these methods, surface simplification, and only as alternate representations for shells.  Methods 1-5 could already be done within the existing HOOPS API.

We implement it as a preprocess step, meaning that all heavy calculation costs at the start, and only switch between precalculated representations at draw time.


Why Implement LOD?

Level-of-Detail (LOD) is essential for large model visualization. General graphics performance enhancements tend to approach an upper bound in the number of triangles per second. After performance tuning has ventured too far into the realm of diminishing returns, the only thing left to do is to somehow reduce the geometric complexity. In most situations, LOD methods can produce several orders of magnitude better performance, depending on the severity of visual artifacts the user is willing to tolerate.

The Challenges

We would like our implementation to balance speed with accuracy.
We would like the computation to be performed at the appropriate time, so that the user does not see a pause at an unacceptable time.
Users who choose not to use LOD should have no performance regresses.
The user interface should allow as much flexibility as possible.
We should conceal as many of the implementation details as possible.
Simplification computations should be user accessible.

Technical Details

The algorithm simplifies the surface taking two vertices joined by an edge, and combining them into one. The new vertex is constrained to lie on the line between the two original vertices, and is positioned so as to minimize a complicated error heuristic. The function that they used as their heuristic is known as a quadric. It measures the change in the normal vectors of the surrounding polygons that the collapse of two vertices would result in. The linear algebra involved is very complicated, but is computationally efficient.

The method allows for some unusual things, such as:


Switching

Perhaps the most difficult original contribution by Tech Soft 3D, switching is the process of determining which model should be visible at a given time.  There are two modes for this. We call the first mode, "clamping", and the second, "dynamic switching".

With clamping, the user specifies a particular level that he would like to see.  It will be used if it is available.  If it is not available, the next coarser resolution is chosen.  If such a resolution also does not exist, we use the next finer resolution.  In other words, "If we don't get what we want, take something that is faster, but always find at least something to draw".  In almost no situations will detail levels be recalculated from within this mode.

With dynamic switching, HOOPS is allowed to make view-dependent decisions about which model to use.  HOOPS will attempt to use whatever resolution best maintains a constant ratio between the area and the number of triangles drawn.  Area can be taken as either physical area (cm2) or number of pixels covered.


Selection

Selection is performed on the original geometry, regardless of what is visible.  For the first release, vertex and edge highlighting (i.e. changing colors locally) may not be supported for LOD representations.  The best option for highlighting portions of a shell would be to move it to a segment that has LOD locked off.

We anticipate that the LOD module will be used only for viewing data, and that interaction with large models will be implemented by the application, in a layer above HOOPS. Once an area of the HOOPS segment tree is selected for interaction (editing, highlighting, etc.) the LOD will be clamped at level 0, the original shell.


Recalculation Behavior

These rules, in order of precedence (i.e. #1 has priority over #2), describe the decision-making process to determine whether or not the detail levels need to be regenerated.  Stop as soon as you find a rule that applies to your situation.

1) if preprocess, recalculate if tlist stops before the maximum number of levels, and skip rule #2.

2) if clamping, do not recalculate.

3) if critical options have changed (dec. % or #), recalculate.

4) if (auto switching and no preprocess) recalculate if you hit a break in the sequence.

5) when recalculating, always blow away all levels in the shell and start from scratch.

Note that this behavior is what we have internally guessed would be the most useful.  We would appreciate any comments and/or feedback on how we can make these rules more convenient and intuitive for developers of real-world applications.


Acknowledgements

We do not pretend that we did this work on our own.  It is based on the algorithm published in ACM Siggraph 1997 by Michael Garland and Paul Heckbert, "Surface Simplification Using Quadric Error metrics".  Our code is furthermore an adaptation in C of their original C++ experimental implementation.
 

SEE ALSO

Compute_Optimized_Shell, Set_Rendering_Options, Open_LOD, Show_LOD_Type, HOOPS Acknowledgements.

Back