Team:BCCS-Bristol/Modelling/BSIM/Geometric Modelling/Octrees
From 2010.igem.org
iGEM 2010
Contents |
Octrees
Overview
The octree is a tree type data structure. This a hierarchical data structure comprised of nested nodes. Each node has one parent and either eight or zero children. Nodes with zero children are called leaves. A node's children subdivide the volume of their parent into eight smaller volumes. Figure 1 shows how an octree partitions space into smaller and smaller volumes and how this can be represented by a tree data structure.
Methods
Each node stores the quantity of chemical and the diffusivity constant for its field. Nodes know what depth they are inside the octree structure and which nodes are their neighbours. This is re-computed each time a node is split it is necessary to know who your neighbors are in order to compute the diffusion of chemicals through the field from one node to those spatially adjacent (i.e. not necessarily nodes of the same parent).
To be able to perform operations across an octree data structure it is necessary to use a traversal algorithm. This is an algorithm that visits each node. There are many different ways of doing this, the method used in BSim is the ‘full post-order’ traverse. This visits each node from deepest depth first, then the second deepest etcetera until it reaches the parent node.
PostOrderTraverse(Node) { IF(Node != leaf){ FOR(i=0:8){ PostOrderTraverse(Node.subNodes[i])} VISIT(Node) } }
Splitting the Octree
The octree data structure is used for holding and computing the chemical field because it is able to approximately represent fields of arbitrary shapes. This is done by splitting an octree from a parent node around a mesh shape. It is easier to explain in terms of the two dimensional quadtree,
the principle is exactly the same for an octree, an example is shown in fig. 2.
This example has a maximum depth of three, the example of an octree partition in fig. 2 has a depth of 5. The
maximum resolution increases exponentially with depth, a depth of 7 appears to be adequate for
reasonably complex shapes, e.g. the mesh of a gel strand.
The algorithm for splitting the octree around a mesh is relatively simple. It uses the post order traverse function above to access each octree node from the bottom to the top. The following function would be in place of the ‘VISIT’ command:
FOR each Edge of Mesh{ FOR each Edge of Node{ IF(Node Edge is crossed by a Mesh Edge) Divide Node into SubNodes ELSE Check next Mesh Edge } }
It is relatively inefficient, each edge of the octree is tested against each edge of the mesh. It could be optimised to try and exclude mesh edges that are extremely unlikely to cross the node edge. It would also be prudent to exclude mesh edges that are too far away from the node to intersect it, as this algorithm would require only addition and subtraction, whereas the collision detection algorithm operates with vector products.
An example of how an octree is split around a mesh in BSim can be seen in the video below. Here you can see how the octree structure looks at each stage of its generation. The maximum resolution increases from 1 at the start, to 8 in the final frame.