HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE TCSC Research Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/722
Title: Hierarchy of surface models and irreducible triangulation
Authors: Cheng, Siu-Wing
Dey, Tamal K.
Poon, Sheung-Hung
Keywords: Level of detail
2-manifold
Abstract simplicial complex
Homology
Edge contraction
Irreducible triangulation
Issue Date: 2002
Series/Report no.: HKUST Theoretical Computer Science Center Research Report ; HKUST-TCSC-2002-06
Abstract: 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 view-dependent 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) topology-preserving 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 topology-preserving hierarchy of O(n + g2) 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 2-manifold is 342g - 72 by Nakamoto and Ota. Using our proof techniques we obtain a new bound of 240g.
URI: http://hdl.handle.net/1783.1/722
Appears in Collections:CSE TCSC Research Reports

Files in This Item:

File Description SizeFormat
200206.pdf160KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.