“Isotopic approximation within a tolerance volume”

  • ©Justin Solomon, Fernando de Goes, Gabriel Peyré, Marco Cuturi, Adrian Butscher, Andy Nguyen, and Tao Du

Conference:


Type:


Title:

    Isotopic approximation within a tolerance volume

Session/Category Title: Meshing Around

Presenter(s)/Author(s):


Moderator(s):


Abstract:


    We introduce in this paper an algorithm that generates from an input tolerance volume a surface triangle mesh guaranteed to be within the tolerance, intersection free and topologically correct. A pliant meshing algorithm is used to capture the topology and discover the anisotropy in the input tolerance volume in order to generate a concise output. We first refine a 3D Delaunay triangulation over the tolerance volume while maintaining a piecewise-linear function on this triangulation, until an isosurface of this function matches the topology sought after. We then embed the isosurface into the 3D triangulation via mutual tessellation, and simplify it while preserving the topology. Our approach extends to surfaces with boundaries and to non-manifold surfaces. We demonstrate the versatility and efficacy of our approach on a variety of data sets and tolerance volumes.

References:


    1. Agarwal, P. K., and Suri, S. 1998. Surface approximation and geometric partitions. Journal of Computing 27, 4, 1016–1035. Google ScholarDigital Library
    2. Aggarwal, A., Booth, H., O’Rourke, J., Suri, S., and Yap, C. K. 1985. Finding minimal convex nested polygons. In Proceedings of ACM Symposium on Computational Geometry, 296–304. Google ScholarDigital Library
    3. Amenta, N., and Bern, M. 1998. Surface reconstruction by voronoi filtering. Discrete and Computational Geometry 22, 481–504.Google ScholarCross Ref
    4. Amenta, N., Choi, S., Dey, T. K., and Leekha, N. 2000. A simple algorithm for homeomorphic surface reconstruction. In Proceedings of ACM Symposium on Computational Geometry, 213–222. Google ScholarDigital Library
    5. Attene, M. 2010. A lightweight approach to repairing digitized polygon meshes. The Visual Computer 26, 1. Google ScholarDigital Library
    6. Bischoff, S., Pavic, D., and Kobbelt, L. 2005. Automatic restoration of polygon models. ACM Transactions on Graphics 24, 1332–1352. Google ScholarDigital Library
    7. Boissonnat, J.-D., and Cazals, F. 2000. Smooth surface reconstruction via natural neighbour interpolation of distance functions. In Proceedings of ACM Symposium on Computational Geometry, 223–232. Google ScholarDigital Library
    8. Boissonnat, J.-D., and Oudot, S. 2005. Provably good sampling and meshing of surfaces. Graphical Models 67, 5, 405–451. Google ScholarDigital Library
    9. Borouchaki, H., and Frey, P. 2005. Simplification of surface mesh using hausdorff envelope. Computer Methods in Applied Mechanics and Engineering 194, 48–49, 4864–4884.Google ScholarCross Ref
    10. Botsch, M., Bommes, D., Vogel, C., and Kobbelt, L. 2004. GPU-based tolerance volumes for mesh processing. In Pacific Conference on Computer Graphics and Applications, IEEE Computer Society, 237–243. Google ScholarDigital Library
    11. Chazal, F., and Cohen-Steiner, D. 2004. A condition for isotopic approximation. In Proceedings of ACM Symposium on Solid Modeling and Applications, 93–99. Google ScholarDigital Library
    12. Chazal, F., Cohen-Steiner, D., and Mérigot, Q. 2011. Geometric Inference for Measures based on Distance Functions. Foundations of Computational Mathematics 11, 6, 733–751. Google ScholarDigital Library
    13. Ciampalini, A., Cignoni, P., Montani, C., and Scopigno, R. 1997. Multiresolution decimation based on global error. The Visual Computer 13, 5, 228–246.Google ScholarCross Ref
    14. Cohen, J., Varshney, A., Manocha, D., Turk, G., Weber, H., Agarwal, P., Brooks, F., and Wright, W. 1996. Simplification envelopes. In Proceedings of ACM Conference on Computer Graphics and Interactive Techniques, 119–128. Google ScholarDigital Library
    15. Cohen, J., Manocha, D., and Olano, M. 2003. Successive mappings: An approach to polygonal mesh simplification with guaranteed error bounds. International Journal of Computational Geometry and Applications 13, 1, 61–96.Google ScholarCross Ref
    16. Dey, T. K., and Goswami, S. 2003. Tight cocone: A watertight surface reconstructor. In Proceedings of ACM Symposium on Solid Modeling and Applications, 127–134. Google ScholarDigital Library
    17. Dey, T. K., and Sun, J. 2005. An adaptive mls surface for reconstruction with guarantees. In Proceedings of EUROGRAPHICS Symposium on Geometry Processing. Google ScholarDigital Library
    18. Dey, T. K., Edelsbrunner, H., Guha, S., and Nekhayev, D. V. 1998. Topology preserving edge contraction. Publ. Inst. Math. (Beograd) (N.S 66, 23–45.Google Scholar
    19. Dey, T. K., Li, K., Ramos, E. A., and Wenger, R. 2009. Isotopic reconstruction of surfaces with boundaries. Computer Graphics Forum 28, 5, 1371–1382. Google ScholarDigital Library
    20. Dey, T. K. 2006. Curve and Surface Reconstruction: Algorithms with Mathematical Analysis (Cambridge Monographs on Applied and Computational Mathematics). Cambridge University Press. Google ScholarDigital Library
    21. Guéziec, A. 1996. Surface simplification inside a tolerance volume. Tech. Rep. 20440. IBM Research Report RC 20440.Google Scholar
    22. Gumhold, S., Borodin, P., and Klein, R. 2003. Intersection free simplification. International Journal of Shape Modeling 9, 2, 155–176.Google ScholarCross Ref
    23. Hornung, A., and Kobbelt, L. 2006. Robust reconstruction of watertight 3d models from non-uniformly sampled point clouds without normal information. In Proceedings of EUROGRAPHICS Symposium on Geometry Processing, 41–50. Google ScholarDigital Library
    24. Ju, T. 2004. Robust repair of polygonal models. ACM Transactions on Graphics 23, 3, 888–895. Google ScholarDigital Library
    25. Kalvin, A. D., and Taylor, R. H. 1996. Superfaces: Polygonal mesh simplification with bounded error. IEEE Computer Graphics and Applications 16, 3. Google ScholarDigital Library
    26. Kazhdan, M., Bolitho, M., and Hoppe, H. 2006. Poisson surface reconstruction. In Proceedings of EUROGRAPHICS Symposium on Geometry Processing, 61–70. Google ScholarDigital Library
    27. Klein, R., Liebich, G., and Strasser, W. 1996. Mesh reduction with error control. In IEEE Visualization, 311–318. Google ScholarDigital Library
    28. Lindstrom, P., and Turk, G. 1999. Evaluation of memoryless simplification. IEEE Transactions on Visualization and Computer Graphics 5, 2, 98–115. Google ScholarDigital Library
    29. Möbius, J., and Kobbelt, L. 2012. Openflipper: An open source geometry processing and rendering framework. In Proceedings of International Conference on Curves and Surfaces, Springer-Verlag, 488–500. Google ScholarDigital Library
    30. Ovreiu, E., Riveros Reyes, J. G., Valette, S., and Prost, R. 2012. Mesh simplification using a two-sided error minimization. In Proceedings of International Conference on Image, Vision and Computing, 26–30.Google Scholar
    31. Shen, C., O’Brien, J. F., and Shewchuk, J. R. 2004. Interpolating and approximating implicit surfaces from polygon soup. ACM Transactions on Graphics 23, 3, 896–904. Google ScholarDigital Library
    32. Zelinka, S., and Garland, M. 2002. Permission grids: Practical, error-bounded simplification. ACM Transactions on Graphics 21, 2, 207–229. Google ScholarDigital Library

ACM Digital Library Publication:


Overview Page: