Developmental modelling with SDS
Inhaltsverzeichnis
Reference
Porter, B. & Jon McCormack: Developmental modelling with SDS. Computers & Graphics. Vol. 34(4), pp. 294 – 303, 2010.
DOI
http://dx.doi.org/10.1016/j.cag.2010.05.008
Abstract
This paper describes modelling methods based on biological development for use in computer graphics applications, specifically the automated growth and development of complex organic shapes that are difficult to model directly. We examine previous approaches, including grammar-based methods, embedded systems and cellular models. Each system can be classified as endogenous (internally determined) or exogenous (externally determined), with some models exhibiting features of both. We then introduce a new model, the Simplicial Developmental System (SDS), which simulates individual cells embedded in a physical environment, with cell division, movement and growth controlled by morphogenetic chemical simulation. SDS uses a tetrahedral mesh as its base representation for geometric modelling and physical simulation. Cell growth, movement and division are determined by simulating chemical morphogens that are diffused between cells according to a set of user defined rules. We discuss the advantages and disadvantages of this model in terms of the competing goals of user control, developmental complexity and open-ended development (the ability to generate new component structures without explicit specification). Examples highlighting the strengths of the model are illustrated.
Extended Abstract
Bibtex
Used References
1] Shapeways. URL http://www.shapeways.com/
[2] A. Smith, Plants, fractals, and formal languages, in: Proceedings of the 11th annual conference on Computer graphics and interactive techniques (SIGGRAPH), Vol. 18, ACM, 1984, pp. 1–10.
[3] M. Lantin, Computer simulations of developmental processes, Tech. rep., SFU CMPT (1997). URL ftp://fas.sfu.ca/pub/cs/TR/1997/CMPT97-24.pdf
[4] A. Sandberg, Models of development, Tech. rep., KTH, Stockholm (2006). URL http://www.nada.kth.se/ asa/Work/index.html
[5] J. L. Giavitto, C. Godin, O. Michel, P. Prusinkiewicz, Computational models for integrative and developmental biology, Tech. rep. (2002). [6] P. Prusinkiewicz, Modeling and visualization of biological structures, in: Proceeding of Graphics Interface ’93, Toronto, Ontario, 1993, pp. 128– 137.
[7] P. Prusinkiewicz, Modeling plant growth and development, Current Opinion in Plant Biology 7 (1) (2004) 79–83. URL http://algorithmicbotany.org/papers/mpg.copb2004.html
[8] K. O. Stanley, R. Miikkulainen, A taxonomy for artificial embryogeny, Artificial Life 9 (2) (2003) 93–130. doi:http://dx.doi.org/10.1162/106454603322221487.
[9] S. Kumar, P. J. Bentley, Mechanisms of oriented cell division in compu- tational development, in: Proceedings of the first Australian Conference on Artificial Life, Canberra, Australia, 2003.
[10] G. B. Ermentrout, L. Edelstein-Keshet, Cellular automata approaches to biological modeling, Journal of Theoretical Biology 160 (1993) 97–133.
[11] G. W. Brodland, Computational modeling of cell sorting, tissue engulfment, and related phenomena: A review, Applied Mechanics Reviews 57 (1) (2004) 47–76. doi:10.1115/1.1583758. URL http://link.aip.org/link/?AMR/57/47/1
[12] A. Lindenmayer, An axiom system for the development of filamentous organisms, in: Abstracts of the III International Congress on Logic, Methodology and Philosophy of Science, Amsterdam, 1967, pp. 127– 128.
[13] P. Prusinkiewicz, A. Lindenmayer, The algorithmic beauty of plants, no. xii, 228 in The virtual laboratory, Springer-Verlag, New York, 1990.
[14] C. Jirasek, P. Prusinkiewicz, B. Moulia, Integrating biomechanics into developmental plant models expressed using l-systems, in: Plant biome- chanics 2000 . Proceedings of the 3rd Plant Biomechanics Conference, Freiburg-Badenweiler, August 27 to September 2, 2000., Georg Thieme Verlag, Stuttgart, 2000, pp. 615–624.
[15] Z. Lam, S. A. King, Simulating tree growth based on internal and environ- mental factors, in: GRAPHITE ’05: Proceedings of the 3rd international conference on Computer graphics and interactive techniques in Australa- sia and South East Asia, ACM Press, New York, NY, USA, 2005, pp. 99–107.
[16] J. Vaario, From evolutionary computation to computational evolution, In- formatica (Slovenia) 18 (4).
[17] R. Mˇech, P. Prusinkiewicz, Visual models of plants interacting with their environment, in: SIGGRAPH ’96: Proceedings of the 23rd annual conference on Computer graphics and interactive tech- niques, ACM Press, New York, NY, USA, 1996, pp. 397–410. doi:http://doi.acm.org/10.1145/237170.237279.
[18] G. Stiny, Shape: Talking about Seeing and Doing, MIT Press, 2006.
[19] K. Sims, Evolving virtual creatures, in: Computer Graphics, orlando, florida Edition, ACM SIGGRAPH, 1994, pp. 15–22.
[20] J. A. Heisserman, Generative geometric design and boundary solid gram- mars, Ph.D. thesis, Department of Architecture, Carnegie Mellon Univer- sity, Pittsburgh, Pennsylvania (May 1991).
[21] S. Maierhofer, Rule-based mesh growing and generalized subdivision meshes, Ph.D. thesis, Vienna University of Technology (2002).
[22] C. Smith, On vertex-vertex systems and their use in geometric and bio- logical modelling, Ph.D. thesis, The University of Calgary (Apr. 2006).
[23] Y. I. Parish, P. M”uller, Procedural modeling of cities, in: Proceedings of the 28th an- nual conference on Computer graphics and interactive techniques (SIG- GRAPH), ACM, 2001, pp. 301–308.
[24] J. McCormack, Evolutionary l-systems, in: P. F. Hingston, L. C. Barone, Z. Michalewicz (Eds.), Design by Evolution: Advances in Evolutionary Design, Natural Computing Series, Springer, 2008, pp. 168–196.
[25] G. Stiny, Pictorial and formal aspects of shape and shape grammars, no. xv, 399 in ISR, Interdisciplinary systems research;, Birkh ̈auser, Basel; Stuttgart, 1975.
[26] N. Greene, Voxel space automata: modeling with stochastic growth processes in voxel space, in: SIGGRAPH ’89: Proceedings of the 16th Annual Conference on Computer Graphics and Inter- active Techniques, ACM Press, New York, 1989, pp. 175–184. doi:http://doi.acm.org/10.1145/74333.74351.
[27] J. McCormack, Open problems in evolutionary music and art, in: F. Rothlauf, J. Branke, S. Cagnoni, D. W. Corne, R. Drechsler, Y. Jin, P. Machado, E. Marchiori, J. Romero, G. D. Smith, G. Squillero (Eds.), EvoWorkshops, Vol. 3449 of Lecture Notes in Computer Science, Springer, 2005, pp. 428–436.
[28] M. Eden, A Two-Dimensional Growth Process, in: J. Neyman (Ed.), Pro- ceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume IV: Biology and Problems of Health, The Re- gents of the University of California, 1961, pp. 223–239.
[29] S. Ulam, On some mathematical problems connected with patterns of growth of figures, Proceedings of Symposia in Applied Mathematics 14 (1962) 215–224.
[30] Y. Kawaguchi, The art of the growth algorithm, in: C. G. Langton, K. Shi- mohara (Eds.), Artificial Life V: Proceedings of the Fifth International Workshop on the Synthesis and Simulation of Living Systems, MIT Press, Nara, Japan, 1996, pp. 159–166.
[31] T. A. Witten, L. M. Sander, Diffusion-limited aggregation, a kinetic criti- cal phenomenon, Phys. Rev. Letters 47 (1981) 1400–1403.
[32] P. Hogeweg, Evolving mechanisms of morphogenesis: on the interplay between differential adhesion and cell differentiation, Journal of Theoret- ical Biology 203 (2003) 317–333.
[33] T. M. Cickovski, C. Huang, R. Chaturvedi, T. Glimm, H. G. E. Hentschel, M. S. Alber, J. A. Glazier, S. A. Newman, J. A. Izaguirre, A framework for three-dimensional simulation of morphogenesis, IEEE/ACM Transac- tions on Computational Biology and Bioinformatics 2 (3).
[34] J. McCormack, Creative ecosystems, in: A. Cardoso, G. Wiggins (Eds.), Proceedings of the 4th International Joint Workshop on Computational Creativity, 2007, pp. 129–136.
[35] J. McCormack, O. Bown, Life’s what you make: Niche construction and evolutionary art, in: M. Giacobini, A. Brabazon, S. Cagnoni, G. A. D. Caro, A. Ek ́art, A. Esparcia-Alc ́azar, M. Farooq, A. Fink, P. Machado, J. McCormack, M. O’Neill, F. Neri, M. Preuss, F. Rothlauf, E. Tarantino, S. Yang (Eds.), EvoWorkshops, Vol. 5484 of Lecture Notes in Computer Science, Springer, 2009, pp. 528–537.
[36] J. A. Kaandorp, Fractal Modelling: Growth and Form in Biology, Springer-Verlag, 1994.
[37] J. A. Kaandorp, J. E. K ̈ubler, The Algorithmic Beauty of Seaweeds, Sponges and Corals, Springer, 2001.
[38] J. Combaz, F. Neyret, Semi–interactive morphogenesis, in: Proceedings of the IEEE International Conference on Shape Modeling and Applica- tions, 2006.
[39] C. H. Leung, M. Berzins, A computational model for organism growth based on surface mesh generation, J. Comput. Phys. 188 (1) (2003) 75– 99. doi:http://dx.doi.org/10.1016/S0021-9991(03)00153-0.
[40] L. G. Harrison, S. Wehner, D. M. Holloway, Complex morphogenesis of surfaces: theory and experiment on coupling of reaction diffusion pat- terning to growth, Nonlinear Chemical Kinetics: Complex Dynamics and Spatiotemporal Patterns, Faraday Discuss. 120 (2001) 277–294.
[41] K. W. Fleischer, A. H. Barr, Artificial Life III, Vol. XVII, Addison- Wesley, Reading, Massachusetts, 1994, Ch. A Simulation Testbed for the Study of Multicellular Development: The Multiple Mechanisms of Mor- phogenesis, pp. 389–416.
[42] K. W. Fleischer, D. H. Laidlaw, B. L. Currin, A. H. Barr, Cellular texture generation, in: Proceedings of the 22nd annual conference on Computer graphics and interactive techniques (SIGGRAPH), ACM, 1995, pp. 239– 248.
[43] J. Miller, Evolving developmental programs for adaptation, morphogene- sis, and self-repair, Advances in Artificial Life (2003) 256–265.
[44] G. P ̆aun, From cells to computers: Computing with membranes (P sys- tems), BioSystems 59 (3) (2001) 139–158.
[45] J. McCormack, Advances in Artificial Life (8th European Conference, ECAL 2005), Vol. LNAI 3630, Springer-Verlag, Berlin; Heidelberg, 2005, Ch. A Developmental Model for Generative Media, pp. 88–97.
[46] S. A. Wainwright, Axis and circumference: the cylindrical shape of plants and animals, no. viii, 132, Harvard University Press, Cambridge, Mass., 1988.
[47] B. Porter, A developmental system for organic form synthesis, in: K. B. Korb, M. Randall, T. Hendtlass (Eds.), ACAL, Vol. 5865 of Lecture Notes in Computer Science, Springer, 2009, pp. 136–148.
[48] H. Si, Tetgen: A Quality Tetrahedral Mesh Generator and a 3D De- launay Triangulator, retrieved from http://tetgen.berlios.de/ on 29.12.09.
[49] R. Bridson, R. Fedkiw, J. Anderson, Robust treatment of collisions, contact and friction for cloth animation (2005) doi:http://doi.acm.org/10.1145/1198555.1198572.
[50] M. M ̈uller, J. Stam, D. James, N. Th ̈urey, Real time physics: class notes, in: SIGGRAPH ’08: ACM SIGGRAPH 2008 classes, ACM, New York, NY, USA, 2008, pp. 1–90. doi:http://doi.acm.org/10.1145/1401132.1401245.
[51] P. Eggenberger, Genome-physics interaction as a new concept to reduce the number of genetic parameters in artificial evolution, in: R. Sarker, R. Reynolds, H. Abbass, K.-C. Tan, R. McKay, D. Essam, T. Gedeon (Eds.), Proceedings of the IEEE 2003 Congress on Evolutionary Compu- tation, IEEE Press, Piscataway, NJ, 2003, pp. 191–198.
[52] M. J. M. de Boer, F. D. Fracchia, P. Prusinkiewicz, Lindenmayer Systems: Impacts on Theoretical Computer Science, Computer Graphics, and De- velopmental Biology, Springer-Verlag, 1992, Ch. A model for cellular development in morphogenetic fields, pp. 351–370.
[53] M. Teschner, B. Heidelberger, M. M ̈uller, M. Gross, A versatile and ro- bust model for geometrically complex deformable solids, in: Proceedings of Computer Graphics International, Heraklion, 2004, pp. 312–319.
[54] J.Dummer, A simple time-corrected verlet integration method. retrieved from http://www.gamedev.net/reference/articles/article2200.asp on 29.12.09. (June 2005).
[55] M. Teschner, B. Heidelberger, M. Mueller, D. Pomeranets, M. Gross, Op- timized spatial hashing for collision detection of deformable objects, in: Proceedings of Vision, Modeling, and Visualization, Munich, Germany, 2003, pp. 47–54.
[56] B. Heidelberger, M. Teschner, R. Keiser, M. M ̈uller, M. Gross, Consistent penetration depth estimation for deformable collision response, in: Pro- ceedings of Vision, Modeling, Visualization, Stanford, USA, 2004, pp. 339–346.
[57] P. Agarwal, The cell programming language, Artificial Life 2 (1) (1994) 37–77.
[58] F. Stewart, T. Taylor, G. Konidaris, Metamorph: Experimenting with genetic regulatory networks for artificial development, in: Proceedings of the Eighth European Conference on Artificial Life, Springer–Verlag, 2005, pp. 108–117.
[59] F. Streichert, C. Spieth, H. Ulmer, A. Zell, Evolving the ability of limited growth and self-repair for artificial embryos, in: Proceedings of the 7th European Conference on Artificial Life, 2003, pp. 289–298.
[60] F. Dellaert, R. D. Beer, Toward an evolvable model of development for autonomous agent synthesis, in: P. Maes, R. Brooks (Eds.), Artificial Life IV, Proceedings of the Fourth International Workshop on the Synthesis and Simulation of Living Systems, MIT Press, Cambridge, MA, 1994, pp. 246–257.
[61] K. Fleischer, A multiple-mechanism developmental model for defining self-organizing geometric structures, Ph.D. thesis, California Institute of Technology, Pasadena, California (1995).
[62] B. Lintermann, O. Deussen, Interactive modeling of plants, IEEE Com- puter Graphics & Applications 19 (1999) 2–11.
[63] K. O. Stanley, Exploiting regularity without development, in: Proceed- ings of the AAAI Fall Symposium on Developmental Systems, AAAI Press, Menlo Park, CA, 2006.
[64] A. M. Turing, The chemical basis of morphogenesis, Philosophical Trans- actions of the Royal Society 237 (1952) 37–72.
[65] D. Baraff, A. Witkin, Dynamic simulation of non-penetrating flex- ible bodies, SIGGRAPH Comput. Graph. 26 (2) (1992) 303–308. doi:http://doi.acm.org/10.1145/142920.134084.
[66] S. Lin, Y.-S. Lee, R. J. Narayan, Printed Biomaterials, Springer, 2010, Ch. Heterogeneous Deformable Modeling of Bio-Tissues and Haptic Force Rendering for Bio-Object Modeling, pp. 19–37.
[67] L. Kharevych, P. Mullen, H. Owhadi, M. Desbrun, Numerical coarsening of inhomogeneous elastic materials, ACM Trans. Graph. 28 (2009) 51:1– 51:8.
Links
Full Text
http://bp.io/wp/wp-content/uploads/2010/07/CAG2011_preprint.pdf
