Week 23&24 ( Jun. 1 - Jun. 14) Coding Stage 2

Generation of attraction points

We deal with the handling logic for the intersection between volumes. The overlapping area will only include attraction points from one sphere (the first one occupies the volume). To do so, we keep a list of added spheres' center and radius. When a new attraction point is added, we will check whether its distance from the center of every sphere in the kept list is smaller or equal to their corresponding radius. If so, that point will be discarded. This handling logic of volume intersection will be inherited when more kinds of volumes are added.

We also created UIs for the attraction point generating system, in which a schematic sphere could be generated with a certain radius at a desired position by users. Then a user-set number of attraction points could be generated by clicking "Add Sphere" buttons.

In the gif below, it could be clearly seen that the attraction points in the big sphere did not be influenced by the later-added small sphere.

Space colonization algorithm

The algorithm is running based on iterative logic. According to the literature study of previous works, there are several parameters shaping how the algorithm performs.

• Branch length: The branch length indicates how long each segment will be. It will intuitively decide the overall appearance of the tree. Shorter branch length will result in curvaceous and intricate trees while longer branch length will make for straight trunks and branches. Meanwhile, even though shorter branch length can lead to larger flexibility of tree’s shape growth and fidelity, it will lead to poorer performance.

• Influence Range: The influence range defines a maximum distance that only branch nodes within this distance around that attractor can be associated and be influenced over. Larger influence range means smoother and more subtle branch curves, but at a performance cost.

• Kill distance: The kill distance is used in the case when an attractor is no longer needed and it may be killed. If one or more branch nodes are within this distance around an attractor, the attractor will be removed. Large kill distance results in smoother branches, whereas lower values will generate curlier shapes.

Once all the fundamental data structures and modules are in place, it’s time to start experimenting with actual algorithms. The implementation starts off simple, with only 250 attraction points. Meanwhile, due to the separate and independent work distribution, the algorithm is firstly implemented based on a fixed sphere volume. The sphere can be considered as one of the simplest volumes since it only consists of a point and a radius. Therefore it is straightforward to compute the random points cloud within this sphere volume. One can think of these points like targets the colonization algorithm will try to reach. This process mainly focuses on getting the core algorithm running smoothly without considering any visual effects.

The logic of the algorithm is simple: In each iteration, every attraction point will be traversed to attach to a trunk node or a tree node that is inside its radius of influence as well as closest to it. In the case that a tree node has a non-empty set of attached attraction points, a new tree node will be generated according to all the attached points. And when there is a tree node inside the kill distance of an attraction point, that point will be removed. This procedure will iteratively generate the tree architecture until no attraction point exists.

Two-dimensional representation of the working process of space colonization algorithm[1].

When a certain branch segment is within the influence range of an attraction point, this point is marked as active and turns the color into yellow.

Reference:

[1]. A. Runions, B. Lane, and P. Prusinkiewicz, “Modeling trees with a space colonization algorithm,” in Proceedings of the Third Eurographics Conference on Natural Phenomena, ser. NPH’07. Aire-la-Ville, Switzerland, Switzerland: Eurographics Association, 2007, pp. 63–70.