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

From 2010.igem.org

(Difference between revisions)
(New page: {{:Team:BCCS-Bristol/Header}} ==Chemical Fields== Octree chemical fields, how the structure is implemented, again, more technical details)
(→Chemical Fields)
Line 4: Line 4:
Octree chemical fields, how the structure is implemented, again, more technical details
Octree chemical fields, how the structure is implemented, again, more technical details
 +
 +
==Octrees==
 +
 +
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 nodes 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
 +
be represented by a tree data structure.
 +
 +
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.
 +
 +
INSERT PSEUDOCODE HERE
 +
 +
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. ??. This example has
 +
a maximum depth of three, the example of an octree partition in fig. 12 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 in fig. 8.
 +
 +
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:
 +
 +
INSERT PSEUDOCODE HERE
 +
 +
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.

Revision as of 14:06, 13 October 2010

Chemical Fields

Octree chemical fields, how the structure is implemented, again, more technical details

Octrees

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 nodes 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 be represented by a tree data structure.

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.

INSERT PSEUDOCODE HERE

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. ??. This example has a maximum depth of three, the example of an octree partition in fig. 12 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 in fig. 8.

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:

INSERT PSEUDOCODE HERE

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.

Retrieved from "http://2010.igem.org/Team:BCCS-Bristol/Modelling/BSIM/Geometric_Modelling/Chemical_Fields"