Triangle Mesh Abstraction

The Triangle Mesh abstraction is meant to allow level of detail (LOD) databases for an arbitrary mesh. A LOD database is one in which particular regions of the database (set of triangles in the world) may vary in their resolution. From far away a building may look like a simple cube, but upon certain triggers (high proximity, being well lit, etc..) the model of the house changes to a more refined model. LOD modeling attempts to satisfy one of the primary goals of computer graphics; to present the user with all and only the data required for a given frame.

In general terms a triangle mesh is as set of neighboring triangles which together (assumedly) create a surface. These meshes are extended by a general procedural refinement paradigm controlled by refinement and coarsening functions taken as parameters to the LOD mesh. Each edge in the mesh is queried as to whether it should refine. If so, the edge is replaced by two children and a midpoint. the two incident triangles are informed, and if necessary form edges crossing the triangle (imagine two edges refined on a triangle inducing an edge between the two midpoints of the refined lines). Similarly, two edges will coarsen into one iff they were originally derived from the same parent and the coarsening function returns true. Each frame, the LOD model is checked for compliance with the refinement functions and is updated appropriately.

The triangles in the LOD mesh are organized into a pseudo-quadtree structure. As each triangle eventually resolves into four triangles similar to the parent triangle, we see how a quadtree may be sufficient for holding the triangle data. However, as it happens (read: as the code was written) each node will have either zero, one or four children. If there are two refined incident edges, only one triangle is induced, and refining the thrid edge creates an additional three triangles. With only one refined edge, no child triangles are induced, and a drawing mechanism is used to reflect the refinement.

Quadtrees are very useful in multiresolution queries as each node can act as a safe (defined relative to query) approximation to the union of its children. One example of this is implemented in the current release. Any 3D object can be approximated by a bounding sphere. We let every childless triangle in the model have a bounding sphere. Every node with children can then set its bounding sphere to be the least sphere enclosing the spheres of all of its children (and perhaps its on data as is the case with two refined edges). When a collision test is required, large chunks of data can be instantly removed from the suspect list, as their mutual ancestor will fail the test, and by safety so would they have. In the curernt release, collision with the view volume is used to cull large amounts of data the can not be seen