Stephan Bischoff
Abstract
We present a fully automatic technique which converts an inconsistent input mesh into an output mesh that is guaranteed to be a clean and consistent mesh representing the closed manifold surface of a solid object. The algorithm removes all typical mesh artifacts such as degenerate triangles, incompatible face orientation, non-manifold vertices and edges, overlapping and penetrating polygons, internal redundant geometry, as well as gaps and holes up to a user-defined maximum size ρ. Moreover, the output mesh always stays within a prescribed tolerance ε to the input mesh. Due to the effective use of a hierarchical octree data structure, the algorithm achieves high voxel resolution (up to 40963 on a 2GB PC) and processing times of just a few minutes for moderately complex objects. We demonstrate our technique on various architectural CAD models to show its robustness and reliability.
- Andujar, C., Brunet, P., and Ayala, D. 2002. Topology-reducing surface simplification using a discrete solid representation. ACM Trans. Graph. 21, 2, 88--105. Google Scholar
- Barequet, G., Duncan, C., and Kumar, S. 1998. Rsvp: A geometric toolkit for controlled repair of solid models. IEEE Trans. Visualiz. Comput. Graph. 4, 2, 162--177. Google Scholar
- Barequet, G. and Kumar, S. 1997. Repairing cad models. In Proceedings of the IEEE Visualization. 363--370. Google Scholar
- Barequet, G. and Sharir, M. 1995. Filling gaps in the boundary of a polyhedron. Comput. Aided Geomet. Des. 12, 2, 207--229. Google Scholar
- Bischoff, S. and Kobbelt, L. 2002. Isosurface reconstruction with topology control. In Proceedings of the Pacific Graphics. 246--255. Google Scholar
- B&oslace;hn, J. and Wozny, M. 1992. Automatic cad-model repair: Shell-closure. In Proceedings of the Symposium on Solid Freeform Fabrication. 86--94.Google Scholar
- Borodin, P., Novotni, M., and Klein, R. 2002. Progressive gap closing for mesh repairing. In Advances in Modelling, Animation and Rendering, J. Vince and R. Earnshaw, Eds. Springer Verlag, 201--213.Google Scholar
- Brunet, P. and Navazo, I. 1990. Solid representation and operation using extended octrees. ACM Trans. Graph. 9, 2, 170--197. Google Scholar
- Davis, J., Marschner, S., Garr, M., and Levoy, M. 2002. Filling holes in complex surfaces using volumetric diffusion. In Proceedings of the International Symposium on 3D Data Processing, Visualization, Transmission. 428--438.Google Scholar
- Dolenc, A. and Mäkelä, I. 1991. Optimized triangulation of parametric surfaces. Techn. rep. TKO-B74, Helsinki University of Technology.Google Scholar
- Frisken, S. F., Perry, R. N., Rockwood, A. P., and Jones, T. R. 2000. Adaptively sampled distance fields: a general representation of shape for computer graphics. In Proceedings of SIGGRAPH. 249--254. Google Scholar
- Garland, M. and Heckbert, P. S. 1997. Surface simplification using quadric error metrics. In Proceedings of SIGGRAPH. 209--216. Google Scholar
- Gibson, S. F. F. 1998. Using distance maps for accurate surface representation in sampled volumes. In Proceedings of IEEE Symposium on Volume Visualization. 23--30. Google Scholar
- Gonzalez, R. and Woods, R. 1992. Digital Image Processing. Addison-Wesley. Google Scholar
- Gottschalk, S., Lin, M. C., and Manocha, D. 1996. Obbtree: A hierarchical structure for rapid interference detection. In Proceedings of SIGGRAPH. 171--180. Google Scholar
- Greß, A. and Klein, R. 2003. Efficient representation and extraction of 2-manifold isosurfaces using kd-trees. In Proceedings of the 11th Pacific Conference on Computer Graphics and Applications (PG'03). 364--376. Google Scholar
- Guéziec, A., Taubin, G., Lazarus, F., and Horn, B. 2001. Cutting and stitching: Converting sets of polygons to manifold surfaces. IEEE Trans. Visualiz. Comput. Graph. 7, 2, 136--151. Google Scholar
- Guskov, I. and Wood, Z. J. 2001. Topological noise removal. In Proceedings of Graphics Interface. 19--26. Google Scholar
- Ju, T. 2004. Robust repair of polygonal models. ACM Trans. Graph. 23, 3, 888--895. Google Scholar
- Ju, T., Losasso, F., Schaefer, S., and Warren, J. 2002. Dual contouring of hermite data. In Proceedings of the SIGGRAPH. 339--346. Google Scholar
- Kobbelt, L., Campagna, S., Vorsatz, J., and Seidel, H.-P. 1998. Interactive multi-resolution modeling on arbitrary meshes. In Proceedings of SIGGRAPH. 105--114. Google Scholar
- Kobbelt, L. P., Botsch, M., Schwanecke, U., and Seidel, H.-P. 2001. Feature sensitive surface extraction from volume data. In Proceedings of SIGGRAPH. 57--66. Google Scholar
- Kong, T. and Rosenfeld, A. 1989. Digital topology: Introduction and survey. Comput. Vision, Graph. Image Process. 48, 357--397. Google Scholar
- Liepa, P. 2003. Filling holes in meshes. In Proceedings of the Symposium on Geometry Processing 03. 200--205. Google Scholar
- Lorensen, W. E. and Cline, H. E. 1987. Marching cubes: A high resolution 3d surface construction algorithm. In Proceedings of SIGGRAPH. 163--169. Google Scholar
- Nooruddin, F. and Turk, G. 2003. Simplification and repair of polygonal models using volumetric techniques. IEEE Trans. Visualiz. Comput. Graph. 9, 2, 191--205. Google Scholar
- Samet, H. and Webber, R. E. 1988. Hierarchical data structures and algorithms for computer graphics. Part i. IEEE Comput. Graph. Appl. 8, 3, 48--68. Google Scholar
- Taubin, G. 1995. A signal processing approach to fair surface design. In Proceedings of SIGGRAPH. 351--358. Google Scholar
- Turk, G. and Levoy, M. 1994. Zippered polygon meshes from range images. In Proceedings of SIGGRAPH 94. 311--318. Google Scholar
- Varadhan, G., Krishnan, S., Kim, Y., Diggavi, S., and Manocha, D. 2003. Efficient max-norm distance computation and reliable voxelization. In Proceedings of the Symposium on Geometry Processing. 116--126. Google Scholar
- Weihe, K. and Willhalm, T. 1998. Why cad data repair requires discrete algorithmic techniques. In Proceedings of the 2nd Workshop on Algorithm Engineering. 1--12.Google Scholar
- Wu, J. and Kobbelt, L. 2003. A stream algorithm for the decimation of massive meshes. In Proceedings of Graphics Interface. 185--192.Google Scholar
Index Terms
- Automatic restoration of polygon models
Recommendations
Compressing polygon mesh geometry with parallelogram prediction
VIS '02: Proceedings of the conference on Visualization '02In this paper we present a generalization of the geometry coder by Touma and Gotsman [34] to polygon meshes. We let the polygon information dictate where to apply the parallelogram rule that they use to predict vertex positions. Since polygons tend to ...
Robust intersection of structured hexahedral meshes and degenerate triangle meshes with volume fraction applications
Two methods for calculating the volume and surface area of the intersection between a triangle mesh and a rectangular hexahedron are presented. The main result is an exact method that calculates the polyhedron of intersection and thereafter the volume ...
Near-optimal connectivity encoding of 2-manifold polygon meshes
Special issue: Processing on large polygonal meshesEncoders for triangle mesh connectivity based on enumeration of vertex valences are among the best reported to date. They are both simple to implement and report the best compressed file sizes for a large corpus of test models. Additionally they have ...
Comments