Quelltext der Seite Developmental modelling with SDS

== 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

[[intern file]]

=== Sonstige Links ===