Kai Xu
Hao Zhang
Abstract
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.
Supplemental Material
Available for Download
Supplemental material.
- Bentley, P. J. 1999. Evolutionary Design by Computers. Morgan Kaufman Publishers. Google Scholar
Digital Library
- 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
- 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
- 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
- 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
- Draves, S. 2006. The electric sheep and their dreams in high fidelity. In Proc. NPAR, 7--9. Google ScholarDigital Library
- 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
- Frazer, J. 1995. An Evolutionary Architecture. Architectural Association Publications.Google Scholar
- 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
- 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
- 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
- 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
- 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
- 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
- Lee, J., and Funkhouser, T. 2008. Sketch-based search and composition of 3D models. In Proc. of SBIM, 97--104. Google ScholarDigital Library
- 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
- 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
- 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
- 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
- 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
- Pollack, J., and Funes, P. 1998. Evolutionary body building: Adaptive physical designs for robots. Artificial Life 4, 337--357. Google ScholarDigital Library
- Romero, J., and Machado, P. 2007. The Art of Artificial Evolution. Springer.Google Scholar
- 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
- 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
- Sims, K. 1991. Artificial evolution for computer graphics. In Proc. of SIGGRAPH, 319--328. Google ScholarDigital Library
- Sims, K. 1994. Evolving virtual creatures. In Proc. of SIGGRAPH, 15--22. Google ScholarDigital Library
- 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
- 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
- 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
- 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
- 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
Recommendations
On proportions of fit individuals in population of mutation-based evolutionary algorithm with tournament selection
In this article, we consider a fitness-level model of a non-elitist mutation-only evolutionary algorithm EA with tournament selection. The model provides upper and lower bounds for the expected proportion of the individuals with fitness above given ...
Adaptive populations of endogenously diversifying Pushpop organisms are reliably diverse
ICAL 2003: Proceedings of the eighth international conference on Artificial lifeThis paper discusses the evolution of diversifying reproduction. We measured the average difference between mothers and their children, the number of species, and the degree of adaptation in evolving populations of endogenously diversifying digital ...
Diverse partner selection with brood recombination in genetic programming
Graphical abstractDisplay Omitted
Highlights- Optimal parent selection during crossover in genetic programming.
- Exploitation ...
AbstractThe ultimate goal of learning algorithms is to find the best solution from a search space without testing each and every solution available in the search space. During the evolution process new solutions (children) are produced from ...
Comments