**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.

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 ”.

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

`compartment`

primitive, see the section called “ The`compartment`

Primitive ”, 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.

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.