Name
Abstract | ||
|---|---|---|
In this paper we propose a novel geometry compression technique for 3D triangle meshes. We focus on a commonly used technique for predicting vertex positions via a flipping operation using the parallelogram rule. We show that the efficiency of the flipping operation is dependent on the order in which triangles are traversed and vertices are predicted accordingly. We formulate the problem of optimally (traversing triangles and) predicting the vertices via flippings as a combinatorial optimization problem of constructing a constrained minimum spanning tree. We give heuristic solutions for this problem and show that we can achieve prediction efficiency within 17.4% on average as compared to the unconstrained minimum spanning tree which is an unachievable lower bound. We also show significant improvements over previous techniques in the literature that strive to find good traversals that also attempt to minimize prediction errors obtained by a sequence of flipping operations, albeit using a different approach. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1109/DCC.2005.68 | DCC |
Keywords | Field | DocType |
computational geometry,computer graphics,data compression,minimisation,trees (mathematics),3D triangle meshes,combinatorial optimization problem,constrained minimum spanning tree,flipping operation,geometry compression,heuristic solutions,parallelogram rule,prediction efficiency,vertex positions | Heuristic,Polygon mesh,Vertex (geometry),Upper and lower bounds,Computer science,Computational geometry,Algorithm,Theoretical computer science,Parallelogram law,Data compression,Minimum spanning tree | Conference |
ISSN | ISBN | Citations |
1068-0314 | 0-7695-2309-9 | 5 |
PageRank | References | Authors |
0.43 | 13 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chen, D. | 1 | 5 | 0.43 |
| Yi-jen Chiang | 2 | 503 | 38.21 |
| Nasir Memon | 3 | 3328 | 299.76 |
| Xiaolin Wu | 4 | 3672 | 286.80 |