Space Colonization Algorithm - CUDA Implementations

An implementation of the Space Colonization Algorithm with GPU-accelerated (CUDA) examples for 2D and 3D branching/venation synthesis. The repository provides multiple variants (2D, 3D, tree visualizations and a rainbow color variant), along with rendered results (PNGs and MP4s) demonstrating typical algorithm behavior.

The Space Colonization Algorithm (SCA) is an agent-based procedural method for simulating branching structures such as trees, leaf venation, and vascular networks. The algorithm distributes attraction points (targets) in space and grows a network of nodes and branches toward these points following simple local rules:

• Attraction points within an influence radius attract nearby branch tips.
• For each tip, an average attraction direction is computed from neighboring points and a new segment is grown in that direction by a fixed step length.
• Attraction points that fall within a kill radius of any branch are removed.
• Growth continues iteratively until attraction points are exhausted or other stop conditions are met.

This repository provides CUDA (.cu) implementations to explore the algorithm in both 2D and 3D, enabling faster generation and experimentation with many attraction points and large branching structures.

What this project contains (What was done)

• 2D and 3D CUDA implementations
  • 2d.cu - CUDA implementation for 2D branching/venation synthesis
  • 3d.cu - CUDA implementation for generic 3D branching
  • tree.cu - A tree-focused variant (parameterized for tree-like growth)
  • 3d_rainbow.cu - A 3D variant with a color-mapped output for visualization
• Results and media
  • results/2d.png, results/3d.png, results/tree.png, results/3d_rainbow.png
  • results/*.mp4 demonstrating animated growth
• A concise references list (this README)

The implementations follow the canonical SCA pattern (influence radius, kill distance, step length, attraction point sampling) and are adapted to run on the GPU to accelerate neighborhood computations and growth steps when many attraction points or branches are present.

Result

Additional outputs (examples):

• ./results/3d.png
• ./results/tree.png
• ./results/3d_rainbow.png
• ./results/*.mp4 (animated growth sequences)

References

• https://algorithmicbotany.org/papers/abop/abop.pdf
• https://algorithmicbotany.org/papers/venation.sig2005.html
• https://algorithmicbotany.org/papers/runionsa.th2008.html
• https://algorithmicbotany.org/papers/kochhar.th2010.html
• https://github.com/mxgmn/WaveFunctionCollapse
• https://algorithmicbotany.org/