“InverseCSG: automatic conversion of 3D models to CSG trees” – ACM SIGGRAPH HISTORY ARCHIVES

“InverseCSG: automatic conversion of 3D models to CSG trees”

  • 2018 SA Technical Papers_Du_InverseCSG: automatic conversion of 3D models to CSG trees

Conference:


Type(s):


Title:

    InverseCSG: automatic conversion of 3D models to CSG trees

Session/Category Title:   Learning to compose & decompose

Presenter(s)/Author(s):


Moderator(s):


Abstract:


    While computer-aided design is a major part of many modern manufacturing pipelines, the design files typically generated describe raw geometry. Lost in this representation is the procedure by which these designs were generated. In this paper, we present a method for reverse-engineering the process by which 3D models may have been generated, in the language of constructive solid geometry (CSG). Observing that CSG is a formal grammar, we formulate this inverse CSG problem as a program synthesis problem. Our solution is an algorithm that couples geometric processing with state-of-the-art program synthesis techniques. In this scheme, geometric processing is used to convert the mixed discrete and continuous domain of CSG trees to a pure discrete domain where modern program synthesizers excel. We demonstrate the efficiency and scalability of our algorithm on several different examples, including those with over 100 primitive parts. We show that our algorithm is able to find simple programs which are close to the ground truth, and demonstrate our method’s applicability in mesh re-editing. Finally, we compare our method to prior state-of-the-art. We demonstrate that our algorithm dominates previous methods in terms of resulting CSG compactness and runtime, and can handle far more complex input meshes than any previous method.

References:


    1. Rajeev Alur, Rastislav Bodik, Garvit Juniwal, Milo MK Martin, Mukund Raghothaman, Sanjit A Seshia, Rishabh Singh, Armando Solar-Lezama, Emina Torlak, and Abhishek Udupa. 2013. Syntax-guided synthesis. In Formal Methods in Computer-Aided Design (FMCAD), 2013. IEEE, 1–8.Google Scholar
    2. Marco Attene, Bianca Falcidieno, and Michela Spagnuolo. 2006. Hierarchical mesh segmentation based on fitting primitives. The Visual Computer 22, 3 (2006), 181–193. Google ScholarDigital Library
    3. Martin Bokeloh, Michael Wand, Hans-Peter Seidel, and Vladlen Koltun. 2012. An Algebraic Model for Parameterized Shape Editing. ACM Trans. Graph. 31, 4 (July 2012), 78:1–78:10. Google ScholarDigital Library
    4. Suzanne Fox Buchele. 1999. Three-dimensional binary space partitioning tree and constructive solid geometry tree construction from algebraic boundary representations. The University of Texas at Austin.Google Scholar
    5. Suzanne F Buchele and Richard H Crawford. 2004. Three-dimensional halfspace constructive solid geometry tree construction from implicit boundary representations. Computer-Aided Design 36, 11 (2004), 1063–1073.Google ScholarCross Ref
    6. Suzanne F Buchele and Angela C Roles. 2001. Binary space partitioning tree and constructive solid geometry representations for objects bounded by curved surfaces.. In CCCG. Citeseer, 49–52.Google Scholar
    7. Siddhartha Chaudhuri, Evangelos Kalogerakis, Leonidas Guibas, and Vladlen Koltun. 2011. Probabilistic Reasoning for Assembly-based 3D Modeling. ACM Trans. Graph. 30, 4, Article 35 (July 2011), 10 pages. Google ScholarDigital Library
    8. Tao Chen, Zhe Zhu, Ariel Shamir, Shi-Min Hu, and Daniel Cohen-Or. 2013. 3-Sweep: Extracting Editable Objects from a Single Photo. ACM Trans. Graph. 32, 6, Article 195 (Nov. 2013), 10 pages. Google ScholarDigital Library
    9. David Cohen-Steiner, Pierre Alliez, and Mathieu Desbrun. 2004. Variational shape approximation. In ACM Transactions on Graphics (TOG), Vol. 23. ACM, 905–914. Google ScholarDigital Library
    10. Benjamin Delaware, Clément Pit-Claudel, Jason Gross, and Adam Chlipala. 2015. Fiat: deductive synthesis of abstract data types in a proof assistant. In Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2015, Mumbai, India, January 15–17, 2015. 689–700. Google ScholarDigital Library
    11. Noah Duncan, Lap-Fai Yu, and Sai-Kit Yeung. 2016. Interchangeable Components for Hands-on Assembly Based Modelling. ACM Trans. Graph. 35, 6, Article 234 (Nov. 2016), 14 pages. Google ScholarDigital Library
    12. Lubin Fan and Peter Wonka. 2016. A Probabilistic Model for Exteriors of Residential Buildings. ACM Trans. Graph. 35, 5, Article 155 (July 2016), 13 pages. Google ScholarDigital Library
    13. Gerald E Farin, Josef Hoschek, and Myung-Soo Kim. 2002. Handbook of computer aided geometric design. Elsevier. Google ScholarDigital Library
    14. Pierre-Alain Fayolle and Alexander Pasko. 2016. An evolutionary approach to the extraction of object construction trees from 3D point clouds. Computer-Aided Design 74 (2016), 1–17. Google ScholarDigital Library
    15. Noa Fish, Melinos Averkiou, Oliver van Kaick, Olga Sorkine-Hornung, Daniel Cohen-Or, and Niloy J. Mitra. 2014. Meta-representation of Shape Families. ACM Trans. Graph. 33, 4, Article 34 (July 2014), 11 pages. Google ScholarDigital Library
    16. Chi-Wing Fu, Peng Song, Xiaoqi Yan, Lee Wei Yang, Pradeep Kumar Jayaraman, and Daniel Cohen-Or. 2015. Computational Interlocking Furniture Assembly. ACM Trans. Graph. 34, 4, Article 91 (July 2015), 11 pages. Google ScholarDigital Library
    17. GrabCAD. 2018. GrabCAD: Design Community, CAD Library, 3D Printing Software. (2018). https://grabcad.com/Google Scholar
    18. Sumit Gulwani. 2011. Automating string processing in spreadsheets using input-output examples. In ACM SIGPLAN Notices, Vol. 46. ACM, 317–330. Google ScholarDigital Library
    19. Sumit Gulwani, William R Harris, and Rishabh Singh. 2012. Spreadsheet data manipulation using examples. Commun. ACM 55, 8 (2012), 97–105. Google ScholarDigital Library
    20. Sumit Gulwani, Oleksandr Polozov, Rishabh Singh, et al. 2017. Program synthesis. Foundations and Trends® in Programming Languages 4, 1–2 (2017), 1–119.Google Scholar
    21. Perttu Hämäläinen, Sebastian Eriksson, Esa Tanskanen, Ville Kyrki, and Jaakko Lehtinen. 2014. Online Motion Synthesis Using Sequential Monte Carlo. ACM Trans. Graph. 33, 4, Article 51 (July 2014), 12 pages. Google ScholarDigital Library
    22. Karim Hamza and Kazuhiro Saitou. 2004. Optimization of constructive solid geometry via a tree-based multi-objective genetic algorithm. In Genetic and Evolutionary Computation Conference. Springer, 981–992.Google ScholarCross Ref
    23. Alec Jacobson, Ilya Baran, Jovan Popovic, and Olga Sorkine. 2011. Bounded biharmonic weights for real-time deformation. ACM Trans. Graph. 30, 4 (2011), 78. Google ScholarDigital Library
    24. Evangelos Kalogerakis, Siddhartha Chaudhuri, Daphne Koller, and Vladlen Koltun. 2012. A Probabilistic Model for Component-based Shape Synthesis. ACM Trans. Graph. 31, 4, Article 55 (July 2012), 11 pages. Google ScholarDigital Library
    25. Pramook Khungurn, Daniel Schroeder, Shuang Zhao, Kavita Bala, and Steve Marschner. 2015. Matching Real Fabrics with Micro-Appearance Models. ACM Trans. Graph. 35, 1, Article 1 (Dec. 2015), 26 pages. Google ScholarDigital Library
    26. Vladimir G. Kim, Wilmot Li, Niloy J. Mitra, Siddhartha Chaudhuri, Stephen DiVerdi, and Thomas Funkhouser. 2013. Learning Part-based Templates from Large Collections of 3D Shapes. ACM Trans. Graph. 32, 4, Article 70 (July 2013), 12 pages. Google ScholarDigital Library
    27. Ali Sinan Koksal, Yewen Pu, Saurabh Srivastava, Rastislav Bodik, Jasmin Fisher, and Nir Piterman. 2013. Synthesis of biological models from mutation experiments. In ACM SIGPLAN Notices, Vol. 48. ACM, 469–482. Google ScholarDigital Library
    28. Yuki Koyama, Shinjiro Sueda, Emma Steinhardt, Takeo Igarashi, Ariel Shamir, and Wojciech Matusik. 2015. AutoConnect: Computational Design of 3D-printable Connectors. ACM Trans. Graph. 34, 6 (Oct. 2015), 231:1–231:11. Google ScholarDigital Library
    29. Manfred Lau, Akira Ohgawara, Jun Mitani, and Takeo Igarashi. 2011. Converting 3D Furniture Models to Fabricatable Parts and Connectors. In ACM SIGGRAPH 2011 Papers (SIGGRAPH ’11). ACM, New York, NY, USA, Article 85, 6 pages. Google ScholarDigital Library
    30. Truc Le and Ye Duan. 2017. A primitive-based 3D segmentation algorithm for mechanical CAD models. Computer Aided Geometric Design 52 (2017), 231–246. Google ScholarDigital Library
    31. Yangyan Li, Xiaokun Wu, Yiorgos Chrysathou, Andrei Sharf, Daniel Cohen-Or, and Niloy J Mitra. 2011. Globfit: Consistently fitting primitives by discovering global relations. In ACM Transactions on Graphics (TOG), Vol. 30. ACM, 52. Google ScholarDigital Library
    32. Roee Litman, Alex Bronstein, Michael Bronstein, and Umberto Castellani. 2014. Supervised Learning of Bag-of-features Shape Descriptors Using Sparse Coding. Comput. Graph. Forum 33, 5 (Aug. 2014), 127–136.Google ScholarDigital Library
    33. Gen Nishida, Ignacio Garcia-Dorado, Daniel G. Aliaga, Bedrich Benes, and Adrien Bousseau. 2016. Interactive Sketching of Urban Procedural Models. ACM Trans. Graph. 35, 4, Article 130 (July 2016), 11 pages. Google ScholarDigital Library
    34. OpenSCAD. 2018. The Programmers Solid 3D CAD Modeller. (2018). Retrieved January 18, 2018 from http://www.openscad.org/Google Scholar
    35. Chi-Han Peng, Yong-Liang Yang, Fan Bao, Daniel Fink, Dong-Ming Yan, Peter Wonka, and Niloy J. Mitra. 2016. Computational Network Design from Functional Specifications. ACM Trans. Graph. 35, 4, Article 131 (July 2016), 12 pages. Google ScholarDigital Library
    36. Markus Püschel, José M. F. Moura, Bryan Singer, Jianxin Xiong, Jeremy R. Johnson, David A. Padua, Manuela M. Veloso, and Robert W. Johnson. 2004. Spiral: A Generator for Platform-Adapted Libraries of Signal Processing Alogorithms. IJHPCA 18, 1 (2004), 21–45. Google ScholarDigital Library
    37. Aristides AG Requicha and Jarek R Rossignac. 1992. Solid modeling and beyond. IEEE computer graphics and applications 12, 5 (1992). Google ScholarDigital Library
    38. Daniel Ritchie, Ben Mildenhall, Noah D. Goodman, and Pat Hanrahan. 2015. Controlling Procedural Modeling Programs with Stochastically-ordered Sequential Monte Carlo. ACM Trans. Graph. 34, 4, Article 105 (July 2015), 11 pages. Google ScholarDigital Library
    39. Eric Schkufza, Rahul Sharma, and Alex Aiken. 2014. Stochastic optimization of floating-point programs with tunable precision. ACM SIGPLAN Notices 49, 6 (2014), 53–64. Google ScholarDigital Library
    40. Ruwen Schnabel, Roland Wahl, and Reinhard Klein. 2007. Efficient RANSAC for point-cloud shape detection. In Computer graphics forum, Vol. 26. Wiley Online Library, 214–226.Google Scholar
    41. Adriana Schulz, Jie Xu, Bo Zhu, Changxi Zheng, Eitan Grispun, and Wojciech Matusik. 2017. Interactive Design Space Exploration and Optimization for CAD Models. ACM Transactions on Graphics 36, 3 (2017). Google ScholarDigital Library
    42. Michael Schwarz and Peter Wonka. 2014. Procedural Design of Exterior Lighting for Buildings with Complex Constraints. ACM Trans. Graph. 33, 5, Article 166 (Sept. 2014), 16 pages. Google ScholarDigital Library
    43. Tianjia Shao, Dongping Li, Yuliang Rong, Changxi Zheng, and Kun Zhou. 2016. Dynamic Furniture Modeling Through Assembly Instructions. ACM Trans. Graph. 35, 6, Article 172 (Nov. 2016), 15 pages. Google ScholarDigital Library
    44. Vadim Shapiro. 2001. A convex deficiency tree algorithm for curved polygons. International Journal of Computational Geometry & Applications 11, 02 (2001), 215–238.Google ScholarCross Ref
    45. Vadim Shapiro and Donald L Vossler. 1991. Construction and optimization of CSG representations. Computer-Aided Design 23, 1 (1991), 4–20. Google ScholarDigital Library
    46. Vadim Shapiro and Donald L Vossler. 1993. Separation for boundary to CSG conversion. ACM Transactions on Graphics (TOG) 12, 1 (1993), 35–55. Google ScholarDigital Library
    47. Gopal Sharma, Rishabh Goyal, Difan Liu, Evangelos Kalogerakis, and Subhransu Maji. 2018. CSGNet: Neural Shape Parser for Constructive Solid Geometry. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR).Google Scholar
    48. Maria Shugrina, Ariel Shamir, and Wojciech Matusik. 2015. Fab Forms: Customizable Objects for Fabrication with Validity and Geometry Caching. ACM Transactions on Graphics 34, 4 (July 2015), 100:1–100:12. Google ScholarDigital Library
    49. Rohit Singh, Venkata Vamsikrishna Meduri, Ahmed K. Elmagarmid, Samuel Madden, Paolo Papotti, Jorge-Arnulfo Quiané-Ruiz, Armando Solar-Lezama, and Nan Tang. 2017. Synthesizing Entity Matching Rules by Examples. PVLDB 11, 2 (2017), 189–202. http://www.vldb.org/pvldb/vol11/p189-singh.pdf Google ScholarDigital Library
    50. Armando Solar-Lezama. 2008. Program Synthesis By Sketching. Ph.D. Dissertation. EECS Dept., UC Berkeley. Google ScholarDigital Library
    51. Armando Solar-Lezama, Liviu Tancau, Rastislav Bodik, Sanjit Seshia, and Vijay Saraswat. 2006. Combinatorial sketching for finite programs. ACM SIGOPS Operating Systems Review 40, 5 (2006), 404–415. Google ScholarDigital Library
    52. Jerry O. Talton, Yu Lou, Steve Lesser, Jared Duke, Radomír Měch, and Vladlen Koltun. 2011. Metropolis Procedural Modeling. ACM Trans. Graph. 30, 2, Article 11 (April 2011), 14 pages. Google ScholarDigital Library
    53. Thingiverse. 2018. Thingiverse: Digital Designs for Physical Objects. (2018). https://www.thingiverse.com/Google Scholar
    54. Shubham Tulsiani, Hao Su, Leonidas J Guibas, Alexei A Efros, and Jitendra Malik. 2017. Learning shape abstractions by assembling volumetric primitives. In Proc. CVPR, Vol. 2.Google ScholarCross Ref
    55. Abhishek Udupa, Arun Raghavan, Jyotirmoy V Deshmukh, Sela Mador-Haim, Milo MK Martin, and Rajeev Alur. 2013. TRANSIT: specifying protocols with concolic snippets. ACM SIGPLAN Notices 48, 6 (2013), 287–296. Google ScholarDigital Library
    56. Julien Valentin, Vibhav Vineet, Ming-Ming Cheng, David Kim, Jamie Shotton, Pushmeet Kohli, Matthias Niessner, Antonio Criminisi, Shahram Izadi, and Philip Torr. 2015. SemanticPaint: Interactive 3D Labeling and Learning at Your Fingertips. ACM Trans. Graph. 34, 5, Article 154 (Nov. 2015), 17 pages. Google ScholarDigital Library
    57. Daniel Weiss. 2009. Geometry-based structural optimization on CAD specification trees. Ph.D. Dissertation. ETH Zurich.Google Scholar
    58. Fuzhang Wu, Dong-Ming Yan, Weiming Dong, Xiaopeng Zhang, and Peter Wonka. 2014. Inverse Procedural Modeling of Facade Layouts. ACM Trans. Graph. 33, 4, Article 121 (July 2014), 10 pages. Google ScholarDigital Library
    59. Q Wu, K Xu, and J Wang. 2018. Constructing 3D CSG Models from 3D Raw Point Clouds. In Computer Graphics Forum, Vol. 37. Wiley Online Library, 221–232.Google Scholar
    60. Jianhua Wu Leif Kobbelt. 2005. Structure recovery via hybrid variational surface approximation. In Computer Graphics Forum, Vol. 24. Wiley Online Library, 277–284.Google Scholar
    61. Zhige Xie, Kai Xu, Ligang Liu, and Yueshan Xiong. 2014. 3D Shape Segmentation and Labeling via Extreme Learning Machine. Comput. Graph. Forum 33, 5 (Aug. 2014), 85–95.Google ScholarDigital Library
    62. Mingliang Xu, Mingyuan Li, Weiwei Xu, Zhigang Deng, Yin Yang, and Kun Zhou. 2016. Interactive mechanism modeling from multi-view images. ACM Trans. Graph 35, 6 (2016), 236. Google ScholarDigital Library
    63. Dong-Ming Yan, Wenping Wang, Yang Liu, and Zhouwang Yang. 2012. Variational mesh segmentation via quadric surface fitting. Computer-Aided Design 44, 11 (2012), 1072–1082. Google ScholarDigital Library
    64. Youyi Zheng, Hongbo Fu, Daniel Cohen-Or, Oscar Kin-Chung Au, and Chiew-Lan Tai. 2011. Component-wise Controllers for Structure-Preserving Shape Manipulation. In Computer Graphics Forum, Vol. 30. Wiley Online Library, 563–572.Google Scholar
    65. Qingnan Zhou and Alec Jacobson. 2016. Thingi10K: A Dataset of 10,000 3D-Printing Models. arXiv preprint arXiv:1605.04797 (2016).Google Scholar
    66. Chenyang Zhu, Renjiao Yi, Wallace Lira, Ibraheem Alhashim, Kai Xu, and Hao Zhang. 2017. Deformation-driven Shape Correspondence via Shape Recognition. ACM Trans. Graph. 36, 4, Article 51 (July 2017), 12 pages. Google ScholarDigital Library

ACM Digital Library Publication:


Overview Page:


Submit a story:

If you would like to submit a story about this presentation, please contact us: historyarchives@siggraph.org