This post is going to continue on from the previous one with building systems that we will need, but not actually linking them back into the current code yet. This post is going to focus on how we can organize the faces of our icosahedron into a tree like structure.
You may have heard of a quadtree or an octree before, depending on how much you have investigated procedural generation before. They are both tree data structures that are commonly used in terrain generation. In a quadtree each node has four children, so this is used for our square based grids, while in an octree each node has eight children, making it useful for 3D voxel grids.
Now, our grid uses triangles, so you would expect it to have a different sort of data structure, but if we think about it each triangle (aka node) in our data structure has four children, the same as in the square grid. This means we are going to use a quadtree.
A quadtree is going to be useful because it enables us to do several things, but the most important one for now is allowing us to work out which triangle on the grid is being selected by the mouse. If we tried to do this without a quadtree data structure then it would be extremely expensive, we would have to search every single triangle in the grid to identify the one we needed. Using a quadtree data structure this is a lot easier, we can start at the icosahedral level, and find which of the 20 faces the mouse is currently intersecting, then only check the children of this face, and so on. This means we have to do far, far fewer checks to find the face we are looking for.
An example of how the tree structure would allow us to home in on the triangle we wanted to find.
Most of the new code we need to add comes in the form of these two new methods. One finds the Parent of a specified IcoBits and the other finds the specified Child. I implemented these methods inside the IcosahedronHelper class from last time. The code can be found here.