Similar articles

Abstract: Many graphics and computer-aided design applications require that the polygonal meshes used in geometric computing have the properties of not only 2-manifold but also are orientable. In this paper, by collecting previous work scattered in the topology and geometry literature, we rigorously present a theoretical basis for orientable polygonal surface representation from a modern point of view. Based on the presented basis, we propose a new combinatorial data structure that can guarantee the property of orientable 2-manifolds and is primal/dual efficient. Comparisons with other widely used data structures are also presented in terms of time and space efficiency.

[1] Akleman, E., Chen, J., 1999. Guaranteeing the 2-manifold property for meshes with doubly linked face list. International Journal of Shape Modelling, 5(2):159-177.

[2] Akleman, E., Chen, J., Srinivasan, V., 2003. A minimal and complete set of operators for the development of robust manifold mesh modelers. Graphical Models, 65(5):286-304.

[3] Ansaldi, S., Floriani, L.D., Falcidieno, B., 1985. Geometric modelling of solid objects by using a face adjacent graph representation. ACM SIGGRAPH Computer Graphics, 19(3):131-139.

[4] Baumgart, B.G., 1972. Winged-edge Polyhedron Representation. Technical report, STAN-CS-320, Stanford University.

[5] Cooke, G.E., Finney, R.L., 1967. Homology of Cell Complexes. Princeton University Press.

[6] de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O., 1997. Computational Geometry: Algorithms and Applications. Springer.

[7] do Carmo, M.P., 1976. Differential Geometry for Curves and Surfaces. Prentice-Hall.

[8] Edelsbrunner, H., 1987. Algorithms in Combinatorial Geometry, EATCS Monographs on Theoretical Computer Science (Vol. 10). Springer-Verlag.

[9] Fomenko, A.T., Kunii, T.L., 1997. Topological Modelling for Visualization. Springer.

[10] Giblin, P.J., 1981. Graphs, Surfaces and Homology (2nd Ed.). Chapman and Hall.

[11] Gross, J.L., Tucker, T.W., 1987. Topological Graph Theory. Wiley-Interscience.

[12] Guibas, L., Stolfi, J., 1985. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Trans. on Graphics, 4(2):74-123.

[13] Mantyla, M., 1988. An Introduction to Solid Modelling. Computer Science Press.

[14] Preparata, F.P., Shamos, M.I., 1985. Computational Geometry: An Introduction. Springer-Verlag.

[15] Sieradski, A.J., 1992. An Introduction to Topology and Homotopy. PWS-KENT Pub.

[16] Weiler, K., 1985. Edge-based data structures for solid modelling in curved-surface environments. IEEE Computer Graphics and Applications, 5(1):21-40.