Table of Contents
The previous chapters introduced several differences between standard SBML and the particular dialect MesoRD understands. In this chapter attention is turned to the last remaining aspect of writing SBML for MesoRD: how to specify the geometry of compartments.
System geometry is essential to the way MesoRD works: simulating diffusion in would be difficult without some space to diffuse in. As was mentioned in the section called “ Compartment ”, each compartment in MesoRD must have its own geometry definition. The geometry of the entire system is the union of all compartment geometries. The volume of the system geometry must be discretised in terms of subvolumes before it is ready for simulation use.
Current versions of SBML have no means to define geometries [Hucka et al 2008]. However, the issue is being worked on, and in a not too distant future there may be standard ways to deal with geometries [9]. In the meantime, this entire chapter describes a MesoRD-specific extension to SBML.
Since subvolumes are inherently three-dimensional, a geometry definition language for MesoRD is not required to handle anything but volumes [10]. Neither users nor developers of MesoRD are expected to be highly skilled mathematicians. Thus, the geometry language should be easy to speak, yet powerful enough to enable construction of non-trivial geometries. A very intuitive way to describe geometry comes from computer aided design and is also used in many three-dimensional modelling packages. It is called constructive solid geometry[11], or CSG for short.
CSG gives a high-level description of geometry. It is intuitive because its syntax resembles the way humans [12] may describe objects in space. Reverting for a moment to two dimensions, the object in Figure 4.1, “ A Simple Two-Dimensional Object ” could, sacrificing any mathematical accuracy, be described as "a circle with four rectangles sticking out its sides" or "two rectangles crossed on top of a circle". Having a computer come up with such a description is surprisingly hard, mainly because humans, unlike computers, can "see" the circle in spite of the fact that its characteristic circumference is interrupted by rectangles. As it turns out, having the same computer generate a geometry from such a description is relatively simple.
Figure 4.1. A Simple Two-Dimensional Object
This object could be described as "a circle with four rectangles sticking out its sides" or "two rectangles crossed on top of a circle".
Theoretically, CSG is a functional procedure that defines a combined, solid, volumetric object from a number of primitive solid volumes by the application of bounded, Boolean set operations [Burger and Gillies 1989] [Foley et al. 1996]. The set of primitive volumes varies with the particular CSG implementation, while the set of operations is quite similar across the board. MesoRD's set of primitives, the parameters needed to define them as well as transformations applicable to them, are inspired by the Virtual Reality Modelling Language, VRML [Hartman and Wernecke 1996]. Note that standard VRML does not actually support CSG -- its geometric primitives cannot be combined using set operations. Also, VRML is not an extended markup language. There are efforts underway to address both these issues.
A CSG procedure can be represented by a tree structure. The root of the tree defines the object of interest, and the leaf nodes are geometric primitives. In between the root and the leaves lie operator nodes. The root object is determined by combining the leaves according to the operator nodes. In a CSG procedure, the operators are either transformations or set operations. A simple, two-dimensional, CSG procedure without transformations is illustrated in Figure 4.2, “ Constructive Solid Geometry Set Operations in Two Dimensions ”.
Figure 4.2. Constructive Solid Geometry Set Operations in Two Dimensions
Set operations and geometric primitives in a simple two-dimensional CSG procedure. This particular specimen is one of the few trees in computer-land that has its root pointing towards the bottom of the page. The blue box is combined with the yellow circle in a union operation, resulting in the upper green object. The red triangle is subtracted from the green object using the difference operator. The last operation, intersection, is illustrated at the bottom part of the figure. For clarity, all transformation operators have been omitted. Note also that this is a binary tree. In general, CSG trees need not be binary: union and intersection nodes can have any number of children.
In general, the Boolean-valued set operations used to combine
the primitives are not commutative. Therefore, the edges of the
tree need to be ordered. It is not difficult to see that exchanging
the operands of a difference operation will yield different results,
just as .
The ordering of operands is relevant from a computational aspect as
well: if a point in space is contained by the first operand of a
union, the algorithm need not spend time checking for containment in
the remaining operands.
Other properties of the tree representation of a CSG procedure are:
The leaf nodes always define a geometric primitive. The inverse is also true: every geometric primitive is represented by a leaf node. By definition, leaf nodes do not have any children. In MesoRD, the
compartmentprimitive, see the section called “ ThecompartmentPrimitive ”, is a strange exception: it is a "leaf" node that could be said to have children.Transformation nodes only have one single child.
Difference nodes have exactly two children, such that the sought object is defined by the volume of the left node minus the volume of the right node. Intersection and union nodes can have any number of children.
A CSG tree does not provide a unique representation. As was exemplified in the figure caption, there are at least two ways to describe the object in Figure 4.2, “ Constructive Solid Geometry Set Operations in Two Dimensions ”. Most objects could be described by several different CSG procedures.
In the world of MesoRD, every
volume element of the full geometry must belong to exactly one
compartment. Because every compartment must define its own
CSG tree, it is possible to specify systems with
overlapping CSG trees, so that some volume
element is "owned" by several compartments. This is not an error
per se, but merely a bad thing to do,
as it will cause confusion when it comes to assigning the volume
element to a compartment. The scenario is easily avoided using the
difference set operation as described in the section called “
The compartment Primitive
”. The
responsibility of avoiding these situations lies entirely on the
side of the user.
MesoRD's geometries are defined by a hierarchical, textual, XML representation of the desired CSG procedure. The XML representation is merely a transcription of the CSG procedure in its tree form. Each element in the XML hierarchy is identified as either a set operation node, a transformation node or a primitive geometry node. The parameters needed to completely define each node, such as the side lengths in case of a box, or the displacements in case of a translation transformation, are supplied as attributes. The XML is kept as an annotation of the compartment, the geometry of which the corresponding CSG procedure defines. The namespace of any such annotations must be http://www.icm.uu.se, otherwise they will be ignored by MesoRD.
Note
The entire purpose of the CSG algorithm is to transform a compartmentalised volume description to a compartmentalised subvolume discretisation. Exactly how this is done will not be discussed here at all. The algorithm is described in the source-level documentation, and also in this report.
[9] Different proposals for geometry support in upcoming versions of SBML are discussed on the SBML Discussion Lists.
[10] In MesoRD only possible to simulate systems with spatial dimension either three or two. Two dimensional surfaces in three dimensional objects are not supported. However, surfaces may be modelled by ensuring the thickness of the geometry is much smaller than its area. Similarly, curves will need to be very thin in directions orthogonal to the tangent. Because any physical object in The Real World™ extends in all three dimensions, MesoRD's idea of a curve or a surface may arguably be more realistic than a true one- or two-dimensional object.
[11] Also called "constructed solid geometry" by some authors [Angel 1997].
[12] At least, it resembles the way those humans who wrote this text would describe objects in space.