|
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 |
Size | Format |
|---|
| 200206.pdf | | 160Kb | Adobe PDF | View/Open |
|
All items in this Repository are protected by copyright, with all rights reserved.
|
