A pattern-based data structure for manipulating meshes with regular regions

ABSTRACT

Automatically generated or laser-scanned surfaces typically exhibit large clusters with a uniform pattern. To take advantage of the regularity within clusters and still be able to edit without decompression, we developed a two-level data structure that uses an enumeration by orbits and an individually adjustable stencil to flexibly describe connectivity. The structure is concise for storing mesh connectivity; efficient for random access, interactive editing, and recursive refinement; and it is flexible by supporting a large assortment of connectity patterns and subdivision schemes.

REFERENCES

• 1: Pierre Alliez, David Cohen-Steiner, Olivier Devillers, Bruno Levy, and Mathieu Desbrun. Anisotropic polygonal remeshing. In SIGGRAPH '03 Conference Proceedings, pages 485--493, 2003.
• 2: Bruce G. Baumgart. A polyhedron representation for computer vision. In Proceedings of the National Computer Conference, pages 589--596, 1975.
• 3: Swen Campagna , Leif Kobbelt , Hans-Peter Seidel, Directed edges—A scalable representation for triangle meshes, Journal of Graphics Tools, v.3 n.4, p.1-11, Dec. 1998
• 4: E. Catmull and J. Clark. Recursively generated B-spline surfaces on arbitrary topological meshes. Computer Aided Design, 10:350--355, 1978.
• 5: D. Doo and M. Sabin. Behaviour of recursive division surfaces near extraordinary points. Computer-Aided Design, 10:356--360, September 1978.
• 6: L. De Floriani, L. Kobbelt, and E. Puppo. A survey on data structures for level-of-detail models. In N. Dodgson, M. Floater, and M. Sabin, editors, Advances in Multiresolution for Geometric Modelling, Series in Mathematics and Visualization, pages 49--74. Springer Verlag, 2004.
• 7: Leo J. Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.221-234, December 1983 [doi>10.1145/800061.808751]
• 8: Hugues Hoppe, Progressive meshes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.99-108, August 1996 [doi>10.1145/237170.237216]
• 9: Martin Isenburg , Jack Snoeyink, Face fixer: compressing polygon meshes with properties, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.263-270, July 2000 [doi>10.1145/344779.344919]
• 10: Kenneth I. Joy, Justin Legakis, and Ron MacCracken. Data structures for multiresolution representation of unstructured meshes. In Gerald Farin, Hans Hagen, and Bernd Hamann, editors, Hierarchical Approximation and Geometric Methods for Scientific Visualization. Springer-Verlag, 2002.
• 11: Lutz Kettner, Using generic programming for designing a data structure for polyhedral surfaces, Computational Geometry: Theory and Applications, v.13 n.1, p.65-90, May 1999 [doi>10.1016/S0925-7721(99)00007-3]
• 12: Leif Kobbelt, √3-subdivision, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.103-112, July 2000 [doi>10.1145/344779.344835]
• 13: A. Levin and D. Levin. Analysis of quasi uniform subdivision. Applied and Computational Harmonic Analysis, 15(1):18--32, 2003.
• 14: Charles T. Loop. Smooth subdivision surfaces based on triangles, 1987. Master's Thesis, Department of Mathematics, University of Utah.
• 15: Jörg Peters, Patching Catmull-Clark meshes, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.255-258, July 2000 [doi>10.1145/344779.344908]
• 16: Kari Pulli , Mark Segal, Fast rendering of subdivision surfaces, Proceedings of the eurographics workshop on Rendering techniques '96, p.61-70, December 1996, Porto, Portugal
• 17: Jarek Rossignac, 3D Compression Made Simple: Edgebreaker with Zip&Wrap on a Corner-Table, Proceedings of the International Conference on Shape Modeling & Applications, p.278, May 07-11, 2001
• 18: Jarek Rossignac, Edgebreaker: Connectivity Compression for Triangle Meshes, IEEE Transactions on Visualization and Computer Graphics, v.5 n.1, p.47-61, January 1999 [doi>10.1109/2945.764870]
• 19: Le-Jeng Shiue , Vineet Goel , Jorg Peters, Mesh mutation in programmable graphics hardware, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 26-27, 2003, San Diego, California
• 20: Jos Stam and Charles Loop. Quad/triangle subdivision. Computer Graphics Forum, 22:79--85, 2002.
• 21: Joe Warren , Joseph D. Warren , Henrik Weimer, Subdivision Methods for Geometric Design: A Constructive Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 22: Kevin Weiler. Edge-based data structures for solid modeling in curved-surface environments. IEEE Computer Graphics and Applications, 5(1):21--40, January 1985.

INDEX TERMS

Keywords:
mesh compression, mesh data structure, mesh refinement, subdivision surfaces