“Interactive design space exploration and optimization for CAD models”

  • ©Adriana Schulz, Jie Xu, Bo Zhu, Changxi Zheng, Eitan Grinspun, and Wojciech Matusik



Session Title:

    Work it, Make it Better, Stronger


    Interactive design space exploration and optimization for CAD models




    Computer Aided Design (CAD) is a multi-billion dollar industry used by almost every mechanical engineer in the world to create practically every existing manufactured shape. CAD models are not only widely available but also extremely useful in the growing field of fabrication-oriented design because they are parametric by construction and capture the engineer’s design intent, including manufacturability. Harnessing this data, however, is challenging, because generating the geometry for a given parameter value requires time-consuming computations. Furthermore, the resulting meshes have different combinatorics, making the mesh data inherently discontinuous with respect to parameter adjustments. In our work, we address these challenges and develop tools that allow interactive exploration and optimization of parametric CAD data. To achieve interactive rates, we use precomputation on an adaptively sampled grid and propose a novel scheme for interpolating in this domain where each sample is a mesh with different combinatorics. Specifically, we extract partial correspondences from CAD representations for local mesh morphing and propose a novel interpolation method for adaptive grids that is both continuous/smooth and local (i.e., the influence of each sample is constrained to the local regions where mesh morphing can be computed). We show examples of how our method can be used to interactively visualize and optimize objects with a variety of physical properties.


    1. Aseem Agarwala. 2007. Efficient Gradient-domain Compositing Using Quadtrees. In Siggraph 2007. ACM. Google ScholarDigital Library
    2. Noam Aigerman, Roi Poranne, and Yaron Lipman. 2014. Lifted bijections for low distortion surface mappings. ACM Trans. Graph. 33, 4 (2014), 69. Google ScholarDigital Library
    3. Noam Aigerman, Roi Poranne, and Yaron Lipman. 2015a. Seamless surface mappings. ACM Trans. on Graph. (TOG) 34, 4 (2015), 72.Google ScholarDigital Library
    4. Noam Aigerman, Roi Poranne, and Yaron Lipman. 2015b. Seamless Surface Mappings. ACM Trans. Graph. 34, 4 (July 2015), 72:1–72:13.Google ScholarDigital Library
    5. Marc Alexa, Daniel Cohen-Or, and David Levin. 2000. As-rigid-as-possible shape interpolation. In Siggraph 2000. ACM, 157–164. Google ScholarDigital Library
    6. Pierre Alliez and Craig Gotsman. 2005. Recent advances in compression of 3D meshes. In Advances in multiresolution for geometric modelling. Springer, 3–26. Google ScholarCross Ref
    7. Mehdi Baba-Ali, David Marcheix, and Xavier Skapin. 2009. A method to improve matching process by shape characteristics in parametric systems. Computer-Aided Design and Applications 6, 3 (2009), 341–350. Google ScholarCross Ref
    8. Moritz Bächer, Stelian Coros, and Bernhard Thomaszewski. 2015. LinkEdit: Interactive Linkage Editing Using Symbolic Kinematics. ACM Trans. Graph. 34, 4 (July 2015), 99:1–99:8.Google ScholarDigital Library
    9. Fan Bao, Dong-Ming Yan, Niloy J. Mitra, and Peter Wonka. 2013. Generating and Exploring Good Building Layouts. ACM Trans. Graph. 32, 4 (July 2013), 122:1–122:10.Google ScholarDigital Library
    10. Ilya Baran. 2017. Onshape Inc. Personal Communication. (2017).Google Scholar
    11. David Benson and Joel Davis. 2002. Octree textures. ACM Transactions on Graphics 21, 3 (2002), 785–790. Google ScholarDigital Library
    12. Gaurav Bharaj, David I. W. Levin, James Tompkin, Yun Fei, Hanspeter Pfister, Wojciech Matusik, and Changxi Zheng. 2015. Computational Design of Metallophone Contact Sounds. ACM Trans. Graph. 34, 6 (Oct. 2015), 223:1–223:13.Google ScholarDigital Library
    13. Rafael Bidarra and Willem F Bronsvoort. 2000. Semantic feature modelling. Computer-Aided Design 32, 3 (2000), 201–225. Google ScholarCross Ref
    14. Rafael Bidarra, Paulos J Nyirenda, and Willem F Bronsvoort. 2005. A feature-based solution to the persistent naming problem. Computer-Aided Design and Applications 2, 1–4 (2005), 517–526.Google ScholarCross Ref
    15. 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
    16. Xiang Chen, Changxi Zheng, and Kun Zhou. 2016. Example-Based Subspace Stress Analysis for Interactive Shape Design. IEEE Transactions on Visualization and Computer Graphics (2016).Google Scholar
    17. Tao Du, Adriana Schulz, Bo Zhu, Bernd Bickel, and Wojciech Matusik. 2016. Computational Multicopter Design. ACM Trans. Graph. 35, 6 (Nov. 2016), 227:1–227:10.Google ScholarDigital Library
    18. Gerald E Farin, Josef Hoschek, and Myung-Soo Kim. 2002. Handbook of computer aided geometric design. Elsevier.Google Scholar
    19. Michael S Floater. 2003. Mean value coordinates. Computer aided geometric design 20, 1 (2003), 19–27.Google Scholar
    20. Michael S Floater. 2015. Generalized barycentric coordinates and applications. Acta Numerica 24 (2015), 161–214.Google ScholarCross Ref
    21. David R. Forsey and Richard H. Bartels. 1988. Hierarchical B-spline Refinement. In Siggraph 1988. ACM, 205–212. Google ScholarDigital Library
    22. Michael Foshey, Nicholas Bandiera, and Javier Ramos. 2017. Mechanical Engineers at MIT. Personal Communication. (2017).Google Scholar
    23. Eitan Grinspun, Petr Krysl, and Peter Schröder. 2002. CHARMS: A Simple Framework for Adaptive Simulation. ACM Trans. Graph. 21, 3 (July 2002), 281–290. Google ScholarDigital Library
    24. 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
    25. Leif Kobbelt, Marc Stamminger, and Hans-Peter Seidel. 1997. Using Subdivision on Hierarchical Data to Reconstruct Radiosity Distribution. Computer Graphics Forum (1997).Google Scholar
    26. 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
    27. Vladislav Kraevoy and Alla Sheffer. 2004. Cross-parameterization and Compatible Remeshing of 3D Models. In Siggraph 2004. ACM, 861–869. Google ScholarDigital Library
    28. Timothy R Langlois, Steven S An, Kelvin K Jin, and Doug L James. 2014. Eigenmode compression for modal sound models. ACM Trans. Graph. 33, 4 (2014), 40. Google ScholarDigital Library
    29. Aaron WF Lee, David Dobkin, Wim Sweldens, and Peter Schröder. 1999. Multiresolution mesh morphing. In Siggraph 1999. ACM, 343–350.Google Scholar
    30. Seungyong Lee, George Wolberg, and Sung Yong Shin. 1997. Scattered data interpolation with multilevel B-splines. IEEE transactions on visualization and computer graphics 3, 3 (1997), 228–244. Google ScholarDigital Library
    31. Frank Losasso, Frédéric Gibou, and Ron Fedkiw. 2004. Simulating Water and Smoke with an Octree Data Structure. ACM Trans. Graph. 23, 3 (Aug. 2004), 457–462. Google ScholarDigital Library
    32. Vittorio Megaro, Bernhard Thomaszewski, Maurizio Nitti, Otmar Hilliges, Markus Gross, and Stelian Coros. 2015. Interactive Design of 3D-printable Robotic Creatures. ACM Trans. Graph. 34, 6 (Oct. 2015). Google ScholarDigital Library
    33. Przemyslaw Musialski, Thomas Auzinger, Michael Birsak, Michael Wimmer, and Leif Kobbelt. 2015. Reduced-order Shape Optimization Using Offset Surfaces. ACM Trans. Graph. 34, 4 (July 2015). Google ScholarDigital Library
    34. Przemyslaw Musialski, Christian Hafner, Florian Rist, Michael Birsak, Michael Wimmer, and Leif Kobbelt. 2016. Non-linear Shape Optimization Using Local Subspace Projections. ACM Trans. Graph. 35, 4 (July 2016). Google ScholarDigital Library
    35. Emil Praun, Wim Sweldens, and Peter Schröder. 2001. Consistent mesh parameterizations. In Siggraph 2001. ACM, 179–184. Google ScholarDigital Library
    36. Romain Prévost, Emily Whiting, Sylvain Lefebvre, and Olga Sorkine-Hornung. 2013. Make It Stand: Balancing Shapes for 3D Fabrication. ACM Trans. Graph. 32, 4 (July 2013), 81:1–81:10.Google ScholarDigital Library
    37. John Schreiner, Arul Asirvatham, Emil Praun, and Hugues Hoppe. 2004. Inter-surface mapping. In ACM Trans. Graph., Vol. 23. ACM. Google ScholarDigital Library
    38. Adriana Schulz, Ariel Shamir, Ilya Baran, David I. W. Levin, Pitchaya Sitthi-Amorn, and Wojciech Matusik. 2017. Retrieval on Parametric Shape Collections. ACM Trans. Graph. 36, 1 (Jan. 2017), 11:1–11:14.Google ScholarDigital Library
    39. Adriana Schulz, Ariel Shamir, David I. W. Levin, Pitchaya Sitthi-amorn, and Wojciech Matusik. 2014. Design and Fabrication by Example. ACM Trans. Graph. 33, 4 (July 2014), 62:1–62:11.Google ScholarDigital Library
    40. Thomas W. Sederberg, Jianmin Zheng, Almaz Bakenov, and Ahmad Nasri. 2003. T-splines and T-NURCCs. ACM Trans. Graph. 22, 3 (July 2003). Google ScholarDigital Library
    41. Rajsekhar Setaluri, Mridul Aanjaneya, Sean Bauer, and Eftychios Sifakis. 2014. SPGrid: A Sparse Paged Grid Structure Applied to Adaptive Smoke Simulation. ACM Trans. Graph. 33, 6 (Nov. 2014). Google ScholarDigital Library
    42. Maria Shugrina, Ariel Shamir, and Wojciech Matusik. 2015. Fab Forms: Customizable Objects for Fabrication with Validity and Geometry Caching. ACM Trans. Graph. 34, 4 (July 2015), 100:1–100:12.Google ScholarDigital Library
    43. Mélina Skouras, Stelian Coros, Eitan Grinspun, and Bernhard Thomaszewski. 2015. Interactive Surface Design with Interlocking Elements. ACM Trans. Graph. 34, 6 (Oct. 2015). Google ScholarDigital Library
    44. Ian Stroud. 2006. Boundary representation modelling techniques. Springer Science & Business Media.Google Scholar
    45. N Sukumar and EA Malsch. 2006. Recent advances in the construction of polygonal finite element interpolants. Archives of Computational Methods in Engineering 13, 1 (2006), 129–163. Google ScholarCross Ref
    46. Nobuyuki Umetani, Takeo Igarashi, and Niloy J. Mitra. 2012. Guided Exploration of Physically Valid Shapes for Furniture Design. ACM Trans. Graph. 31, 4 (2012). Google ScholarDigital Library
    47. Nobuyuki Umetani, Danny M. Kaufman, Takeo Igarashi, and Eitan Grinspun. 2011. Sensitive Couture for Interactive Garment Modeling and Editing. ACM Trans. Graph. 30, 4 (July 2011), 90:1–90:12.Google ScholarDigital Library
    48. Nobuyuki Umetani, Yuki Koyama, Ryan Schmidt, and Takeo Igarashi. 2014. Pteromys: Interactive Design and Optimization of Free-formed Free-flight Model Airplanes. ACM Trans. Graph. 33, 4 (July 2014), 65:1–65:10.Google ScholarDigital Library
    49. Oliver Van Kaick, Hao Zhang, Ghassan Hamarneh, and Daniel Cohen-Or. 2011. A survey on shape correspondence. In Computer Graphics Forum, Vol. 30. Wiley Online Library, 1681–1707. Google ScholarCross Ref
    50. Emily Whiting, Hijung Shin, Robert Wang, John Ochsendorf, and Frédo Durand. 2012. Structural Optimization of 3D Masonry Buildings. ACM Trans. Graph. 31, 6 (2012), 159:1–159:11.Google ScholarDigital Library
    51. Kun Xu, Yong Li, Tao Ju, Shi-Min Hu, and Tian-Qiang Liu. 2009. Efficient Affinity-based Edit Propagation Using K-D Tree. In Siggraph Asia 2009. ACM, 118:1–118:6.Google Scholar
    52. 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 ScholarCross Ref
    53. Denis Zorin and Peter Schroder. 2000. Subdivision for Modeling and Animation. In Siggraph 2000 Courses. ACM.Google Scholar

ACM Digital Library Publication: