I've been playing with path finding algorithms recently and I came up with an OTL that creates a venation structure given root points, seed points and an optional collision surface.
This can be used to create venations on, inside surfaces, and I guess some more cool stuff that at the moment I cannot even think of !
This is a quick demonstration video of the otl (I speeded it up 2x so you don't fall asleep while you watch)
A few days ago I was reading
this article cause I was interested in reproducing Jack Frost effect from Rise of the Guardians.
This line of the article really caught my attention:
Our developer on that would take a model, whatever the frost needed to grow on, and he would run a cellular automata simulation across it
Cellular automata ? what the hell is that ? So I started researching a bit and as it always happens...the by-products of the research are usually even more interesting than the destination.
So I came across this video:
Check out
this blog out when you have time, there is a lot of really interesting stuff, presented in a really nice way.
Researching a bit more I found the details of the algorithm in this amazing paper:
This paper blew my mind. Bye Jack Frost (for now), welcome Hyphae !
So I quickly implemented a prototype in Houdini.
The Algorithm
Given this initial data:
- hormone points (H)
- roots points (R)
The target of the algorithm is to add points to R till the branches reach all the points in H. When one of the R branches reaches one of the H points, that H point will be removed by the group H and not used anymore for the next iteration.
So the way I implemented it in Houdini is the following:
for each point h in H
- find the closest point cp in R and store (on h) its index (integer CLIDX) , location (vector CLPOS) and normalized vector pointing to it from h (vector CLDIR)
- if the cp is too close to h flag it for deletion (int IGNORE=1)
- delete all points in H where IGNORE==1
- in H create groups GR_* based on CLIDX (using partition sop)
for each group gr in GR_*
- find the average CLDIR and normalize it --> AVGCLDIR
- create a new point r=CLPOS-AVGCLDIR
- merge the new r point into R
- goto 1
Test 1
"let's see if it works"
H (hormones) = 100 points scattered by a sphere volume centered at the origin
R (roots) = 1 point at the origin
Test 2
"hell yeah it does ! ...how about more roots ??"
H = same as before
R = 3 points (manually placed randomly in the space not too far from the sphere I used to generate H)
Test 3
"this is amazing. How about a lot more roots ?"
H = same as before
R = points scattered from the surface of a sphere larger than the one I used to generate H
Uhmm...that is not so cool. Why ?
Problem 1:
Well, to start we notice that not all of the points R actually grow. This is because of the step 1.1 in the algorithm ! Only one point between all R is chosen to be the closest one to a specific point in H. So some point of R might not be the closest to ANY H since the beginning.
Solution:
1. we could decrease the number of R but that's cheating , isn't it.
2. we can increase the radius and number of the H distribution so that the outer H points are closer to the roots.
Problem 2:
The veins grow radially towards the center, but as soon as they find a hormone, they stop without splitting any new branch. So we don't get that awesome intricate complexity we like so much and that doesn't let us sleep on night. The reason for this is point 2 in the algorithm. What happens is that we have so many veins now, that they take care of 'killing' the few H very quickly (and more or less at the same time, cause the distribution of the chasers (R) is similar to the distribution of the chased (H), since both are spherical distributions).
Solution:
We need to add more H. The best option is to add more density the more we move towards the center of the spherical distribution of H. A quick way to do that is use Poly to VDB sop, check "fill interior" and scatter from this.
Problem 3:
Lines are too straight ! We like chaos, variation !
Solution:
How about adding in the algorithm some noise ?
Let's modify the step 4.B in the algorithm adding some noise fuction of the position.
Something like this:
4.2 --> r=CLPOS-AVGCLDIR+noise(CLPOS)
Test 4
H = 5000 points scattered from VDB volume with interior filled.
R = same as test 3
I've added a noise function as described in the solution of problem 3 above.
Collision Objects
This algorithm allows creating any sort of volumetric venation , which is really cool.
So I wanted to test it on a real complex model, and see if I could create the effect of venations growing and crawling over the surface of an object.
So I took the model of an arm from internet , I scattered points over the surface of the arm (H points), and I placed one single root point on the tip of the index finger. When I ran the simulation I noticed that, even if the result was mind blowing, there was a big problem : the venation was growing even "inside" the arm not only on the surface. I had to expect this of course, since the each loop iteration of the algorithm is performed on ALL the H points. So it doesn't really matter if the root is initially on the index finger tip : it will be affected even from the H points on the fore arm. So the venation would grow regardless.
You can see it even from another point of view : the algorithm is not aware about the surface of any model ! All we feed into him are point clouds.
So I decided to include in the algorithm the concept of Collision Objects: when a root point enters in a collition object (SDF sample value < 0) then it will be pushed out of the collision object along the normal of the collision object in that point (SDF gradient value).
So all we need is modify once more the step 4.2 of the algorithm:
4.2 --> r=CLPOS - AVGCLDIR + noise(CLPOS) + CVEC
where
CVEC = if ( sample (CLPOS,cobj) < 0 , -sample(CLPOS, cobj)*gradient(CLPOS,cobj) , 0 )
cobj is the collision object
Now CVEC component will make sure that the roots will not grow into the collision object.
What if we want to make sure the roots never leave the surface ?
 |
| For instance in this case, we don't want to see roots growing in the air. We want them to stick on the surface. |
That's easy to fix : we just have to remove the condition to the CVEC component.
In other words, now the roots will be pushed outside of the collision object if they're inside, and towards the collision object if they're outside.
CVEC = -sample(CLPOS, cobj)*gradient(CLPOS,cobj)
This will make sure that the roots stick to the collision object.
In the following example, I duplicated the arm , poly-extruded it out so that the copy is slightly bigger than the arm. Then I selected the hand and a few more polygons on the arm and poly-extruded it again so that the selection is inside the original geometry. Then used it (the copy) as a collision object.
This way I created very quickly a small path on the arm to allow the root to reach the hand which is free to be filled with veins.
This is the collision object (in red) and the arm (in yellow):
This is a quick test
IMPORTANT NOTE:
The Hyphae algorithm is great to create vines / venations structures using STATIC point clouds. What I mean is that, moving one single H or R point in the whole system can radically change the outcoming shape.
So, if you plan to have H, or R or both, animated and expect to have a smooth animation of the resulting venation system, this is not going to happen. The vines will be radically different between two adjacent frames. (this is great if you have to create some electricity effect, or lightnings, or voltaic arcs a la Frankenstein etc..).
The workaround to smoothly animate the resulting venation is to generate it on static point clouds, then deform it using some other deformer (Lattice for instance).
