Real Time Generation of Progressive Meshes for Changing Environments

The progressive mesh representation is in general introduced for a continuous level of detail, and with it smooth transition between meshes can be achieved. However, the method is impractical for realtime simplification. Despite that, the realtime generation of progressive meshes is often required for applications such as in a robot simulation system or a flight simulation system where models are constantly modified by the actions of object collision, object destruction and reconstruction, etc. A new method is presented in this paper to tackle realtime simplification through progressive meshes. By the algorithm only the current mesh and readily accessible local information of each vertex, such as vertex position, edge length, neighboring vertices, adjacent faces, and face normals, are considered at each simplification step. All edge-collapse costs are calculated and sorted into a binary tree using the heap sort algorithm at the initial stage. At the iterative stages only the neighboring affected costs need be recalculated and rearranged in the binary tree. Other properties, such as vertex color and face texture, are processed in the same way as the geometry. The algorithm greatly improves the time performance under the constraint that the quality of the generated meshes be acceptable. Tests show that the algorithm is viable in a realtime simplification for medium-scale virtual models on PC platforms.