Team:BCCS-Bristol/Modelling/BSIM/Geometric Modelling/Chemical Fields

From 2010.igem.org

(Difference between revisions)
(Chemical Fields)
 
Line 1: Line 1:
{{:Team:BCCS-Bristol/Header}}
{{:Team:BCCS-Bristol/Header}}
-
==Chemical Fields==
 
-
Octree chemical fields, how the structure is implemented, again, more technical details
+
=Octrees=
-
 
+
-
==Octrees==
+
 +
==Overview==
The octree is a tree type data structure. This a hierarchical data structure comprised of nested
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
nodes. Each node has one parent and either eight or zero children. Nodes with zero children are
-
called leaves. A nodes children subdivide the volume of their parent into eight smaller volumes.
+
called leaves. A node's children subdivide the volume of their parent into eight smaller volumes.
-
Figure 11 shows how an octree partitions space into smaller and smaller volumes and how this can
+
Figure 1 shows how an octree partitions space into smaller and smaller volumes and how this can
be represented by a tree data structure.
be represented by a tree data structure.
 +
 +
 +
[[Image:OctreeSchem.png|thumbnail|right|Fig. 1. Schematic illustration of how an octree subdividies in space (left) and how this is represented as a node and leaf data structure (right). In this example the highest resolution node
 +
is of depth 3.]]
 +
 +
==Methods==
Each node stores the quantity of chemical and the diffusivity constant for its field. Nodes know
Each node stores the quantity of chemical and the diffusivity constant for its field. Nodes know
Line 24: Line 28:
first, then the second deepest etcetera until it reaches the parent node.
first, then the second deepest etcetera until it reaches the parent node.
-
INSERT PSEUDOCODE HERE
+
<pre>
 +
PostOrderTraverse(Node)
 +
{
 +
    IF(Node != leaf){
 +
        FOR(i=0:8){
 +
        PostOrderTraverse(Node.subNodes[i])}
 +
        VISIT(Node)
 +
  }
 +
 +
}
 +
</pre>
 +
 +
==Splitting the Octree==
The octree data structure is used for holding and computing the chemical field because it is able
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
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,
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. ??. This example has
+
the principle is exactly the same for an octree, an example is shown in fig. 2. [[Image:Quadtree.png|thumbnail|right|Fig. 2. An example of quadtree partitioning, as the maximum depth increases, the partition more closely approximates the curve]]
-
a maximum depth of three, the example of an octree partition in fig. 12 has a depth of 5. The
+
 
 +
 
 +
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
maximum resolution increases exponentially with depth, a depth of 7 appears to be adequate for
-
reasonably complex shapes, e.g. the mesh in fig. 8.
+
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
The algorithm for splitting the octree around a mesh is relatively simple. It uses the post order
Line 38: Line 56:
function would be in place of the ‘VISIT’ command:
function would be in place of the ‘VISIT’ command:
-
INSERT PSEUDOCODE HERE
+
<pre>
 +
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
 +
  }
 +
}
 +
</pre>
It is relatively inefficient, each edge of the octree is tested against each edge of the mesh. It
It is relatively inefficient, each edge of the octree is tested against each edge of the mesh. It
Line 45: Line 72:
intersect it, as this algorithm would require only addition and subtraction, whereas the collision
intersect it, as this algorithm would require only addition and subtraction, whereas the collision
detection algorithm operates with vector products.
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.
 +
 +
 +
<center><html><object width="425" height="344"><param name="movie" value="http://www.youtube.com/v/Uoh1mCADghI?fs=1&amp;hl=en_US&amp;rel=0&amp;hd=1"></param><param name="allowFullScreen" value="true"></param><param name="allowscriptaccess" value="always"></param><embed src="http://www.youtube.com/v/Uoh1mCADghI?fs=1&amp;hl=en_US&amp;rel=0&amp;hd=1" type="application/x-shockwave-flash" allowscriptaccess="always" allowfullscreen="true" width="425" height="344"></embed></object></html></center>

Latest revision as of 13:22, 26 October 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.


Fig. 1. Schematic illustration of how an octree subdividies in space (left) and how this is represented as a node and leaf data structure (right). In this example the highest resolution node is of depth 3.

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.
Fig. 2. An example of quadtree partitioning, as the maximum depth increases, the partition more closely approximates the curve


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.