Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/722
Hierarchy of surface models and irreducible triangulation
Authors 
Cheng, SiuWing
Dey, Tamal K. Poon, SheungHung 


Issue Date  2002  
Summary  Given a triangulated closed surface, the problem of constructing a hierarchy of surface models of decreasing level of detail has attracted much attention in computer graphics. A hierarchy provides viewdependent refinement and facilitates the computation of parameterization. For a triangulated closed surface of n vertices and genus g, we prove that there is a constant c > 0 such that if n > c⋅g, then a greedy strategy can identify Θ(n) topologypreserving edge contractions that do not interfere with each other. Further, they affect only a constant number of triangles. Repeatedly identifying and contracting such edges produces a topologypreserving hierarchy of O(n + g^{2}) size and O(log n + g) depth. The genus g is very small when compared with n for large models in practice. The identification of edges can be enhanced by selecting edges based on the error of their contractions as measured by some known heuristics. This will keep the geometric approximation small in practice. Although several implementations exist for constructing hierarchies, our work is the first to show that a greedy algorithm can efficiently compute a provably good hierarchy. When no contractible edge exists, the triangulation is irreducible. The best known upper bound on the number of vertices of an irreducible triangulation of an orientable 2manifold is 342g  72 by Nakamoto and Ota. Using our proof techniques we obtain a new bound of 240g.  
Subjects  
Language  English 

Format  Technical report  
Access 
Files in this item:
