Week 21&22 (May. 18 - May.31) Coding Stage 1

Generation of attraction points

Our first goal is to build a basic working system to enable generation inside the target volume, in which the overlay problem could be properly defined. Thus, we start from building a simple sphere system.

We first try to distribute points uniformly inside a sphere centered at p with radius R. We choose to use random distribution inside a spherical system centered at p, in which r, θ, φ are limited by R.

Problem: the point distribution is not uniform if the points are simply generated based on uniform distributed coordinates in a spherical coordinate system, since the volume is not uniformly increased when r is uniformly increased. More points are needed when r is larger. Referred from Baptiste’s work, r is generated based on the function below:

Based Fuction

After adjusting the distribution on r axis, our code for generating one attraction point in a sphere becomes:

which leads to good results for uniformly-distributed attraction points in a sphere when this function is called desired number of times.

Space colonization algorithm

To generate a tree, we start with adding one segment as the First Branch, which is the start point where the tree will grow. Once the tree starts to grow from the root, there is normally a trunk part of a tree structure. At this part, the structure is normally quite straight. We came up with two ways to implement this part. The original plan is to have a separate function to grow the trunk, so that this part won’t be influenced by the attraction points.

However, we found there is also a situation in the later algorithm process that the branch segment doesn’t reach the influence range of any attraction points, this will lead to a stuck in the algorithm running since the branch growth is driven by the influence of attraction points. One solution is to have a rule asking the branch to continue growing in the same direction when no interference of attraction points until the branch reaches one influence range. We found out that this rule can also help to grow the trunk part without the need of separate functions.

Therefore, to implement the rule, we create a new branch which inherits the same direction vector as its parent, and grow from the extremity for a branch length at each iteration. Starting from the pre-defined root position, an initial direction is set as Vector3(0, 1, 0), the rule will guide the branches to keep growing straight and pointing to the top.

In order to visualize the generation process, the Unity built-in OnDrawGizmos() function is used to represent the objects through gizmos. The purple dots represent the node while the green lines used to connect nodes are branch segments which are later used for mesh generation. As developed in the attraction point generation part, the initial attraction point cloud is in red color.