“Putting holes in holey geometry: topology change for arbitrary surfaces” by Bernstein and Wojtan

  • ©Gilbert Bernstein and Chris Wojtan

Conference:


Type(s):


Title:

    Putting holes in holey geometry: topology change for arbitrary surfaces

Session/Category Title:   Geometry & Topology

Presenter(s)/Author(s):


Moderator(s):


Abstract:


    This paper presents a method for computing topology changes for triangle meshes in an interactive geometric modeling environment. Most triangle meshes in practice do not exhibit desirable geometric properties, so we develop a solution that is independent of standard assumptions and robust to geometric errors. Specifically, we provide the first method for topology change applicable to arbitrary non-solid, non-manifold, non-closed, self-intersecting surfaces. We prove that this new method for topology change produces the expected conventional results when applied to solid (closed, manifold, non-self-intersecting) surfaces—that is, we prove a backwards-compatibility property relative to prior work. Beyond solid surfaces, we present empirical evidence that our method remains tolerant to a variety of surface aberrations through the incorporation of a novel error correction scheme. Finally, we demonstrate how topology change applied to non-solid objects enables wholly new and useful behaviors.

References:


    1. 3D-Coat, 2013. 3D-Coat.Google Scholar
    2. Attene, M., Campen, M., and Kobbelt, L. 2013. Polygon mesh repairing: An application perspective. ACM Computing Surveys. To appear. Google ScholarDigital Library
    3. Autodesk, 2013. 3ds Max.Google Scholar
    4. Autodesk, 2013. Maya.Google Scholar
    5. Autodesk, 2013. Mudbox.Google Scholar
    6. Boykov, Y., Veksler, O., and Zabih, R. 2001. Fast approximate energy minimization via graph cuts. IEEE Trans. Pattern Anal. Mach. Intell. 23, 11 (Nov.), 1222–1239. Google ScholarDigital Library
    7. Brochu, T., and Bridson, R. 2009. Robust topological operations for dynamic explicit surfaces. SIAM J. Sci. Comput. 31, 4, 2472–2493. Google ScholarDigital Library
    8. Brochu, T., Edwards, E., and Bridson, R. 2012. Efficient geometrically exact continuous collision detection. ACM Trans. Graph. 31, 4 (July), 96:1–96:7. Google ScholarDigital Library
    9. Campen, M., and Kobbelt, L. 2010. Exact and robust (self-)intersections for polygonal meshes. Computer Graphics Forum 29, 2, 397–406.Google ScholarCross Ref
    10. Chaudhuri, S., Kalogerakis, E., Guibas, L., and Koltun, V. 2011. Probabilistic reasoning for assembly-based 3D modeling. ACM Transactions on Graphics (Proc. SIGGRAPH) 30, 4. Google ScholarDigital Library
    11. Edelsbrunner, H., and Mücke, E. 1990. Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms. ACM Transactions on Graphics (TOG 9, 1 (Jan). Google ScholarDigital Library
    12. Grady, L., and Schwartz, E. L. 2006. Isoperimetric graph partitioning for image segmentation. IEEE Trans. on Pat. Anal. and Mach. Int 28, 469–475. Google ScholarDigital Library
    13. Harmon, D., Panozzo, D., Sorkine, O., and Zorin, D. 2011. Interference-aware geometric modeling. ACM Trans. Graph. 30 (Dec.), 137:1–137:10. Google ScholarDigital Library
    14. Hecker, C., Raabe, B., Enslow, R. W., DeWeese, J., Maynard, J., and van Prooijen, K. 2008. Real-time motion retargeting to highly varied user-created morphologies. In ACM SIGGRAPH 2008 papers, ACM, New York, NY, USA, SIGGRAPH ’08, 27:1–27:11. Google ScholarDigital Library
    15. Igarashi, T., Matsuoka, S., and Tanaka, H. 1999. Teddy: a sketching interface for 3d freeform design. In Proceedings of the 26th annual conference on Computer graphics and interactive techniques, ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, SIGGRAPH ’99, 409–416. Google ScholarDigital Library
    16. Ju, T. 2009. Fixing geometric errors on polygonal models: a survey. J. Comput. Sci. Technol. 24, 1 (Jan.), 19–29. Google ScholarDigital Library
    17. McGuire, M. 2004. Observations on silhouette sizes. journal of graphics, gpu, and game tools 9, 1, 1–12.Google Scholar
    18. Mojang, 2013. Minecraft.Google Scholar
    19. Pixologic, 2013. Sculptris.Google Scholar
    20. Pixologic, 2013. ZBrush.Google Scholar
    21. Requicha, A. A. G. 1977. Mathematical models of rigid solid objects. Tech. Rep. TM-28, Production Automation Project, University of Rochester, Rochester, New York 14627, November.Google Scholar
    22. Schmidt, R., and Singh, K. 2010. meshmixer: an interface for rapid mesh composition. In ACM SIGGRAPH 2010 Talks, ACM, New York, NY, USA, SIGGRAPH ’10, 6:1–6:1. Google ScholarDigital Library
    23. Seidel, R. 1994. The nature and meaning of perturbations in geometric computing. In STACS ’94: Proceedings of the 11th Annual Symposium on Theoretical Aspects of Computer Science, Springer-Verlag, London, UK, 3–17. Google ScholarDigital Library
    24. Shewchuk, J. R. 1996. Triangle: Engineering a 2d quality mesh generator and delaunay triangulator. In Selected papers from the Workshop on Applied Computational Geormetry, Towards Geometric Engineering, Springer-Verlag, London, UK, UK, FCRC ’96/WACG ’96, 203–222. Google ScholarDigital Library
    25. Shewchuk, J. R. 1997. Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates. Discrete & Computational Geometry 18, 3 (Oct.), 305–363.Google Scholar
    26. Stãnculescu, L., Chaine, R., and Cani, M.-P. 2011. Smi 2011: Full paper: Freestyle: Sculpting meshes with self-adaptive topology. Comput. Graph. 35, 3 (June), 614–622. Google ScholarDigital Library
    27. Teschner, M., Heidelberger, B., Manocha, D., Govindaraju, N., Zachmann, G., Kimmerle, S., Mezger, J., and Fuhrmann, A. 2005. Collision handling in dynamic simulation environments. In Eurographics 2005: Tutorial Notes.Google Scholar
    28. Wald, I. 2007. On fast construction of sah-based bounding volume hierarchies. In Proceedings of the 2007 IEEE Symposium on Interactive Ray Tracing, IEEE Computer Society, Washington, DC, USA, RT ’07, 33–40. Google ScholarDigital Library
    29. Wojtan, C., Thürey, N., Gross, M., and Turk, G. 2009. Deforming meshes that split and merge. In SIGGRAPH ’09: ACM SIGGRAPH 2009 papers, ACM, New York, NY, USA, 1–10. Google ScholarDigital Library
    30. Wojtan, C., Thürey, N., Gross, M., and Turk, G. 2010. Physics-inspired topology changes for thin fluid features. In SIGGRAPH ’10: ACM SIGGRAPH 2010 papers, ACM, New York, NY, USA, 1–8. Google ScholarDigital Library
    31. Zaharescu, A., Boyer, E., and Horaud, R. 2011. Topology-adaptive mesh deformation for surface evolution, morphing, and multiview reconstruction. IEEE Transactions on Pattern Analysis and Machine Intelligence 33, 823–837. Google ScholarDigital Library

ACM Digital Library Publication:


Overview Page: