“Flow-Complex-Based Shape Reconstruction From 3D Curve Sketches” by Sadri and Singh

  • ©Bardia Sadri and Karan Singh

Conference:


Type:


Title:

    Flow-Complex-Based Shape Reconstruction From 3D Curve Sketches

Session/Category Title: Interactive Modeling

Presenter(s)/Author(s):


Moderator(s):


Abstract:


    We address the problem of shape reconstruction from a sparse unorganized collection of 3D curves, typically generated by increasingly popular 3D curve sketching applications. Experimentally, we observe that human understanding of shape from connected 3D curves is largely consistent, and informed by both topological connectivity and geometry of the curves. We thus employ the flow complex, a structure that captures aspects of input topology and geometry, in a novel algorithm to produce an intersection-free 3D triangulated shape that interpolates the input 3D curves. Our approach is able to triangulate highly nonplanar and concave curve cycles, providing a robust 3D mesh and parametric embedding for challenging 3D curve input. Our evaluation is fourfold: we show our algorithm to match designer-selected curve cycles for surfacing; we produce user-acceptable shapes for a wide range of curve inputs; we show our approach to be predictable and robust to curve addition and deletion; we compare our results to prior art.

References:


    1. F. Abbasinejad, P. Joshi, and N. Amenta. 2011. Surface patches from unorganized space curves. Comput. Graph. Forum 30, 5, 1379–1387.
    2. M. Alexa, J. Behr, D. Cohen-Or, S. Fleishman, D. Levin, and C. T. Silva. 2001. Point set surfaces. In Proceedings of the Conference on Visualization (VIS’01). 21–28.
    3. N. Amenta, S. Choi, and R. K. Kolluri. 2001. The power crust, unions of balls, and the medial axis transform. Comput. Geom. Theory Appl. 19, 2–3, 127–153.
    4. S.-H. Bae, R. Balakrishnan, and K. Singh. 2008. ILoveSketch: As-natural-as-possible sketching system for creating 3d curve models. In Proceedings of the 21st Annual ACM Symposium on User Interface Software and Technology (UIST’08). ACM Press, New York, 151–160.
    5. M. Bessmeltsev, C. Wang, A. Sheffer, and K. Singh. 2012. Design-driven quadrangulation of closed 3d curves. ACM Trans. Graph. 31, 6.
    6. J.-D. Boissonnat. 1984. Geometric structures for three-dimensional shape representation. ACM Trans. Graph. 3, 4, 266–286.
    7. J.-D. Boissonnat and F. Cazals. 2002. Smooth surface reconstruction via natural neighbour interpolation of distance functions. Comput. Geom. Theory Appl. 22, 1–3, 185–203.
    8. M. Botsch, L. Kobbelt, M. Pauly, P. Alliez, and B. Uno Levy. 2010. Polygon Mesh Processing. AK Peters.
    9. K. Buchin, T. K. Dey, J. Giesen, and M. John. 2008. Recursive geometry of the flow complex and topology of the flow complex filtration. Comput. Geom. Theory Appl. 40, 115–157.
    10. J. C. Carr, R. K. Beatson, J. B. Cherrie, T. J. Mitchell, W. R. Fright, B. C. McCallum, and T. R. Evans. 2001. Reconstruction and representation of 3d objects with radial basis functions. In Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’01). 67–76.
    11. F. Cazals, A. Parameswaran, and S. Pion. 2008. Robust construction of the three-dimensional flow complex. In Proceedings of the 24th Annual Symposium on Computational Geometry. 182–191.
    12. R. Chaine. 2003. A geometric-based convection approach of 3d reconstruction. In Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Geometry Processing (SGP’03). 218–229.
    13. D. Cohen-Steiner, H. Edelsbrunner, and J. Harer. 2007. Stability of persistence diagrams. Discr. Comput. Geom. 37, 1, 103–120.
    14. D. Cohen-Steiner, H. Edelsbrunner, and J. Harer. 2009. Extending persistence using Poincare and Lefschetz duality. Foundat. Comput. Math. 9, 79–103.
    15. T. Dey. 2011. Curve and Surface Reconstruction: Algorithms with Mathematical Analysis. Cambridge Monographs on Applied and Computational Mathematics, Cambridge University Press.
    16. T. K. Dey, J. Giesen, E. A. Ramos, and B. Sadri. 2005. Critical points of the distance to an epsilon-sampling of a surface and flowcomplex-based surface reconstruction. In Proceedings of the 21st Annual ACM Symposium on Computational Geometry (SCG’05). 218–227.
    17. H. Edelsbrunner. 2004. Surface reconstruction by wrapping finite point sets in space. Discr. Comput. Geom. 32, 231–244.
    18. H. Edelsbrunner, D. Letscher, and A. Zomorodian. 2002a. Topological persistence and simplification. Discr. Comput. Geom. 28, 4, 511–533.
    19. H. Edelsbrunner, D. Letscher, and A. Zomorodian. 2002b. Topological persistence and simplification. Discr. Comput. Geom. 28, 4, 511–533.
    20. J. Giesen and M. John. 2002. Surface reconstruction based on a dynamical system. Comput. Graph. Forum 21, 363–371.
    21. Joachim Giesen and Matthias John. 2003. The flow complex: A data structure for geometric modeling. In Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms. 285–294.
    22. T. Grossman, R. Balakrishnan, and K. Singh. 2003. An interface for creating and manipulating curves using a high degree-of-freedom curve input device. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems (CHI’03). ACM Press, New York, 185–192.
    23. H. Hoppe, T. Derose, T. Duchamp, J. A. McDonald, and W. Stuetzle. 1992. Surface reconstruction from unorganized points. In Proceedings of the 19th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’92). 71–78.
    24. R. Mehra, Q. Zhou, J. Long, A. Sheffer, A. Gooch, and N. J. Mitra. 2009. Abstraction of man-made shapes. ACM Trans. Graph. 28, 5, 1–10.
    25. A. Nealen, T. Igarashi, O. Sorkine, and M. Alexa. 2007. Fibermesh: Designing freeform surfaces with 3d curves. ACM Trans. Graph. 26, 3.
    26. L. Olsen, F. Samavati, M. Sousa, and J. Jorge. 2009. Sketchbased modeling: A survey. Comput. Graph. 33, 85–103.
    27. R. Schmidt, A. Khan, K. Singh, and G. Kurtenbach. 2009. Analytic drawing of 3d scaffolds. ACM Trans. Graph. 28, 5.
    28. M. Shpitalni and H. Lipson. 1996. Identification of faces in a 2d line drawing projection of a wireframe object. IEEE Trans. Pattern Anal. Mach. Intell. 18, 1000–1012.
    29. K. Singh. 2006. Industrial motivation for interactive shape modeling: A case study in conceptual automotive design. In Proceedings of the ACM SIGGRAPH Courses (SIGGRAPH’06). ACM Press, New York, 3–9.
    30. T. Varady, A. Rockwood, and P. Salvi. 2011. Transfinite surface interpolation over irregular n-sided domains. Comput.-Aided Des. 43, 11, 1330–1340.

ACM Digital Library Publication:


Overview Page: