{"id":46,"date":"2010-09-26T10:15:30","date_gmt":"2010-09-26T09:15:30","guid":{"rendered":"http:\/\/www.joesfer.com\/?p=46"},"modified":"2015-05-15T20:19:18","modified_gmt":"2015-05-15T19:19:18","slug":"growing-organic-structures","status":"publish","type":"post","link":"https:\/\/www.joesfer.com\/?p=46","title":{"rendered":"Growing organic structures"},"content":{"rendered":"

\"\"<\/a><\/p>\n

This project arose from a conversation with my friend Gino<\/a>, who is currently working on Medical Visualization, about the difficulty for an artist to create growing structures such as veins -let alone animate them- and how to make them look organic, and therefore irregular and adapted to the surrounding they grow upon.<\/p>\n

The Problem<\/h2>\n

I decided to tackle the problem, and the first approach that came to my mind were L-Systems<\/a>, which have proven useful for modelling vegetation. There are two restrictions, however, which discouraged me from taking this approach:<\/p>\n

    \n
  1. We should be able to bind the growing of the structures to a surface, and therefore the growth needs to be context<\/em> aware<\/em><\/strong>.<\/li>\n
  2. We need to be able to direct the growth<\/strong> by specifying the areas the structure is allowed to occupy.<\/li>\n<\/ol>\n

    Doing some research I ended up taking the approach described in the paper Modeling trees with a space colonization algorithm<\/a>, listed in Algorithmic Botany<\/a>, which perfectly suits the aforementioned requirements.<\/p>\n

    Space Colonization Algorithm<\/h2>\n
    \"\"<\/a>

    Space Colonization Algorithm<\/p><\/div>\n

    The idea for the Space Colonization Algorithm<\/strong> is brilliantly simple: instead of generating the nodes that build our structure by using a set of rules (e.g. a grammar), we begin by producing a set of attractor points<\/strong> by sampling a domain -the surface of an object in our case-. Then we provide one or several start locations<\/strong>, and we iteratively start adding nodes by looking for the set of nearest active <\/em>attractors<\/strong>, and growing towards them. When a new node is added, it kills all the attractor points<\/strong> which fall within a specified range, preventing other branches to fill in the same space, and directing the growth forward.<\/p>\n

    Implementation in Maya<\/h2>\n

    Given the stages of the SCA algorithm, the natural solution felt to devise them as a set of separate DAG nodes which will be linked together. This allows Maya to cache the result of each individual stage and update the graph efficiently<\/strong> when a given parameter is tweaked without requiring the whole solution to be re-evaluated.<\/p>\n

    \"\"<\/a><\/p>\n