Navigating through triangle meshes implemented as linear quadtrees

Techniques are presented for navigating between adjacent triangles of great er or equal size in a hierarchical triangle mesh where the triangles are ob tained by a recursive quadtree-like subdivision of the underlying space int o four equilateral triangles. These techniques are useful in a number of ap plications, including finite element analysis, ray tracing, and the modelin g of spherical data. The operations are implemented in a manner analogous t o that used in a quadtree representation of data on the two-dimensional pla ne where the underlying space is tessellated into a square mesh. A new tech nique is described for labeling the triangles, which is useful in implement ing the quadtree triangle mesh as a linear quadtree (i.e., a pointer-less q uadtree); the navigation can then take place in this linear quadtree. When the neighbors are of equal size, the algorithms have a worst-case constant time complexity. The algorithms are very efficient, as they make use of jus t a few bit manipulation operations, and can be implemented in hardware usi ng just a few machine language instructions. The use of these techniques wh en modeling spherical data by projecting it onto the faces of a regular sol id whose faces are equilateral triangles, which are represented as quadtree triangle meshes, is discussed in detail. The methods are applicable to the icosahedron, octahedron, and tetrahedron. The difference lies in the way t ransitions are made between the faces of the polyhedron. However, regardles s of the type of polyhedron, the computational complexity of the methods is the same.