“Fit and diverse: set evolution for inspiring 3D shape galleries” by Xu, Zhang, Cohen-Or and Chen

  • ©Kai Xu, Hao (Richard) Zhang, Daniel Cohen-Or, and Baoquan Chen




    Fit and diverse: set evolution for inspiring 3D shape galleries



    We introduce set evolution as a means for creative 3D shape modeling, where an initial population of 3D models is evolved to produce generations of novel shapes. Part of the evolving set is presented to a user as a shape gallery to offer modeling suggestions. User preferences define the fitness for the evolution so that over time, the shape population will mainly consist of individuals with good fitness. However, to inspire the user’s creativity, we must also keep the evolving set diverse. Hence the evolution is “fit and diverse”, drawing motivation from evolution theory. We introduce a novel part crossover operator which works at the finer-level part structures of the shapes, leading to significant variations and thus increased diversity in the evolved shape structures. Diversity is also achieved by explicitly compromising the fitness scores on a portion of the evolving population. We demonstrate the effectiveness of set evolution on man-made shapes. We show that selecting only models with high fitness leads to an elite population with low diversity. By keeping the population fit and diverse, the evolution can generate inspiring, and sometimes unexpected, shapes.


    1. Bentley, P. J. 1999. Evolutionary Design by Computers. Morgan Kaufman Publishers. Google ScholarDigital Library
    2. Bentley, P. J. 2000. Exploring component-based representations – the secret of creativity by evolution? In Proc. of Int. Conf. on Adaptive Computing in Design and Manufacture, 161–172.Google ScholarCross Ref
    3. Chaudhuri, S., and Koltun, V. 2010. Data-driven suggestions for creativity support in 3D modeling. ACM Trans. on Graph (Proc. of SIGGRAPH Asia) 29, 6, 183:1–9. Google ScholarDigital Library
    4. Chaudhuri, S., Kalogerakis, E., Guibas, L., and Koltun, V. 2011. Probabilistic reasoning for assembly-based 3d modeling. ACM Trans. on Graph (Proc. of SIGGRAPH) 30, 35:1–10. Google ScholarDigital Library
    5. Chen, D.-Y., Tian, X.-P., Shen, Y.-T., and Ouhyoung, M. 2003. On visual similarity based 3D model retrieval. Computer Graphics Forum (Special Issue of Eurographics) 22, 3, 223–232.Google ScholarCross Ref
    6. Draves, S. 2006. The electric sheep and their dreams in high fidelity. In Proc. NPAR, 7–9. Google ScholarDigital Library
    7. Fisher, M., Savva, M., and Hanrahan, P. 2011. Characterizing structural relationships in scenes using graph kernels. ACM Trans. on Graph (Proc. of SIGGRAPH) 30, 4, 34:1–11. Google ScholarDigital Library
    8. Frazer, J. 1995. An Evolutionary Architecture. Architectural Association Publications.Google Scholar
    9. Fu, H., Cohen-Or, D., Dror, G., and Sheffer, A. 2008. Upright orientation of man-made objects. ACM Trans. on Graph (Proc. of SIGGRAPH) 27, 42:1–7. Google ScholarDigital Library
    10. Funkhouser, T., Kazhdan, M., Shilane, P., Min, P., Kiefer, W., Tal, A., Rusinkiewicz, S., and Dobkin, D. 2004. Modeling by example. ACM Trans. on Graph (Proc. of SIGGRAPH) 23, 3, 652–663. Google ScholarDigital Library
    11. Jain, A., Thormählen, T., Ritschel, T., and Seidel, H.-P. 2012. Exploring shape variations by 3D-model decomposition and part-based recombination. Computer Graphics Forum (Special Issue of Eurographics) 31, 2, to appear. Google ScholarDigital Library
    12. Jakiela, M. J., and Duda, J. 1997. Generation and classification of structural topologies with genetic algorithm speciation. Journal of Mechanical Design 119, 1, 127–130.Google ScholarCross Ref
    13. Kim, V. G., Li, W., Mitra, N., DiVerdi, S., and Funkhouser, T. 2012. Exploring collections of 3d models using fuzzy correspondences. ACM Trans. on Graph (Proc. of SIGGRAPH) 31, to appear. Google ScholarDigital Library
    14. Kreavoy, V., Julius, D., and Sheffer, A. 2007. Model composition from interchangeable components. In Proc. of Pacific Conference on Computer Graphics and Applications, 129–138. Google ScholarDigital Library
    15. Lee, J., and Funkhouser, T. 2008. Sketch-based search and composition of 3D models. In Proc. of SBIM, 97–104. Google ScholarDigital Library
    16. Lin, J., Cohen-Or, D., Zhang, H., Cheng, L., Sharf, A., Deusson, O., and Chen, B. 2011. Structure-preserving retargeting of irregular 3D architecture. ACM Trans. on Graph 30, 6, 183:1–10. Google ScholarDigital Library
    17. Marks, J., Andalman, B., Beardsley, P. A., Freeman, W. T., Gibson, S., Hodgins, J. K., Kang, T., Mirtich, B., Pfister, H., Ruml, W., Ryall, K., Seims, J., and Shieber, S. M. 1997. Design galleries: a general approach to setting parameters for computer graphics and animation. In Proc. of SIGGRAPH, 389–400. Google ScholarDigital Library
    18. Merrell, P., Schkufza, E., Li, Z., Agrawala, M., and Koltun, V. 2011. Interactive furniture layout using interior design guidelines. ACM Trans. on Graph (Proc. of SIGGRAPH) 30, 4, 87:1–10. Google ScholarDigital Library
    19. Ovsjanikov, M., Li, W., Guibas, L., and Mitra, N. J. 2011. Exploration of continuous variability in collections of 3d shapes. ACM Trans. on Graph (Proc. of SIGGRAPH) 30, 4, 33:1–10. Google ScholarDigital Library
    20. Pilat, M. L., and Jacob, C. 2008. Creature academy: A system for virtual creature evolution. In IEEE Congress on Evolutionary Computation, 3289–3297.Google Scholar
    21. Pollack, J., and Funes, P. 1998. Evolutionary body building: Adaptive physical designs for robots. Artificial Life 4, 337–357. Google ScholarDigital Library
    22. Romero, J., and Machado, P. 2007. The Art of Artificial Evolution. Springer.Google Scholar
    23. Shapira, L., Shamir, A., and Cohen-Or, D. 2009. Image appearance exploration by model-based navigation. Computer Graphics Forum (Special Issue of Eurographics) 28, 2, 629–638.Google ScholarCross Ref
    24. Shin, H., and Igarashi, T. 2007. Magic canvas: interactive design of a 3D scene prototype from freehand sketches. In Proc. of Graphics Interface, 63–70. Google ScholarDigital Library
    25. Sims, K. 1991. Artificial evolution for computer graphics. In Proc. of SIGGRAPH, 319–328. Google ScholarDigital Library
    26. Sims, K. 1994. Evolving virtual creatures. In Proc. of SIGGRAPH, 15–22. Google ScholarDigital Library
    27. Soddu, C., and Colabella, E. 1995. Recreating the city’s identity with a morphogenetic urban design. In Proc. of Int. Conf. on Making Cities Livable, 5–9.Google Scholar
    28. Talton, J. O., Gibson, D., Yang, L., Hanrahan, P., and Koltun, V. 2009. Exploratory modeling with collaborative design spaces. ACM Trans. on Graph (Proc. of SIGGRAPH) 28, 5, 167:1–10. Google ScholarDigital Library
    29. Xu, K., Li, H., Zhang, H., Cohen-Or, D., Xiong, Y., and Cheng, Z. 2010. Style-content separation by anisotropic part scales. ACM Trans. on Graph (Proc. of SIGGRAPH Asia) 29, 5, 184:1–10. Google ScholarDigital Library
    30. Yang, Y.-L., Yang, Y.-J., Pottmann, H., and Mitra, N. J. 2011. Shape space exploration of constrained meshes. ACM Trans. on Graph (Proc. of SIGGRAPH Asia) 30, 124:1–12. Google ScholarDigital Library
    31. Zheng, Y., Fu, H., Cohen-Or, D., Au, O. K.-C., and Tai, C.-L. 2011. Component-wise controllers for structure-preserving shape manipulation. Computer Graphics Forum (Special Issue of Eurographics) 30, 2, 563–572.Google ScholarCross Ref

ACM Digital Library Publication: