There are many ways to implement CSG. The details will vary with the intended application. The MesoRD CSG implementation draws its inspiration from a number of sources, most notably VRML.
Primitives in MesoRD can be boxes,
cones, cylinders, meshes and spheres in 3D models. In 2D models
primitives can be rectangles and circles. Just like objects in
VRML, primitives are defined centred at the
origin of a local, right-handed coordinate
system [Hartman and Wernecke 1996]. In the case
of cones and cylinders, the axis of symmetry is defined to lie
parallel to the local y-axis. The local
coordinate systems are related to the global
coordinate system, the right-handed coordinate system of the full
geometry, by a set of affine transformations.
Note
In the examples below it is assumed that the unit
um is defined as one
micrometre, i.e.
<unitDefinition id="um">
<listOfUnits>
<unit kind="metre" scale="-6"/>
</listOfUnits>
</unitDefinition>
is somewhere in the
listOfUnitDefinitions.
Warning
The format of the unit definitions has changed since earlier versions of MesoRD (version 0.2). Each node now needs to specify a unit by means of the
MesoRD:unitsparameter. This is the unit in which all lengths, radii, angles, etc. of the primitive are to be interpreted.New in MesoRD 0.3 is that each
annotationblock starts with<MesoRD:csg xmlns:MesoRD="http://www.icm.uu.se">and ends with</MesoRD:csg>.
The box node defines is a
block-shaped geometric object centred at the origin of the local
coordinate system. Its sides are aligned with the local coordinate
axes. The parameters in defining a box are the side lengths of the
box along the x-, y- and
z-axis. The example below defines a 5 by 30 by
10 um box. It extends 5
um in the
x-direction, 30
um in the
y-direction and 10
um in the
z-direction.
Example 4.1. Box Geometry
<compartment id="box">
<annotation>
<MesoRD:csg xmlns:MesoRD="http://www.icm.uu.se">
<MesoRD:box MesoRD:x="5"
MesoRD:y="30"
MesoRD:z="10"
MesoRD:units="um"/>
</MesoRD:csg>
</annotation>
</compartment>
The cone node defines a
simple cone oriented along the local y-axis. An
untransformed cone is centred at the origin, extending half its
height along the positive y-axis and half its
height along the negative y-axis. The parameters
in defining a cone are the bottomradius and the
height. The example below defines a cone with
radius 5 um and height 20
um.
Example 4.2. Cone Geometry
<compartment id="cone">
<annotation>
<MesoRD:csg xmlns:MesoRD="http://www.icm.uu.se">
<MesoRD:cone MesoRD:bottomradius="5"
MesoRD:height="20"
MesoRD:units="um"/>
</MesoRD:csg>
</annotation>
</compartment>
The cylinder node builds a
simple, capped cylinder centred at the origin and oriented along the
local y-axis. The cylinder extends half its
height along the positive y-axis and half its
height along the negative y-axis. The parameters
in defining a cylinder are the radius and the
height. The example below defines a cylinder
with radius 5 um and height 20
um.
Example 4.3. Cylinder Geometry
<compartment id="cylinder">
<annotation>
<MesoRD:csg xmlns:MesoRD="http://www.icm.uu.se">
<MesoRD:cylinder MesoRD:height="20"
MesoRD:radius="5"
MesoRD:units="um"/>
</MesoRD:csg>
</annotation>
</compartment>
Cylinders are really special cases of generalised cones, in
the sense that the radius is not dependant on the
y-coordinate. This means that the radius at the
base is always equal to the radius at the top. The fact that the
areas of the base and the top are equal is also what makes periodic
boundary conditions, see the section called “
Periodic Boundary Conditions
”, possible for
cylinders.
The mesh primitive enables
non-trivial geometries to be built without worrying about set
operations or transformations. The mesh is probably the most
powerful primitive available in MesoRD's
CSG implementation, as it allows for the creation
of natural shapes. A mesh is in principle a list of
sided triangles -- sided meaning that the
triangles have a front face and a back face. A triangle is an
ordered list of exactly three vertices. A vertex is one of the
three corners of a triangle. The triangles are not necessarily
centred at the origin.
The sidedness of a triangle is determined by computing the
normal of the triangle, 
, where
,
and
are the
ordered vertices of the triangle. By convention, the normal is
taken to point away from the front face of the
triangle. Equivalently, the normal is assumed to point out of the
solid enclosed by all triangles. Another way to state the above is
this: when looking at the triangle's front face, that is when
inspecting the exterior surface of the solid, the vertices of the
triangle should be listed in counterclockwise order. The volume
behind the list of triangles should be closed. Interesting surprises
await those who define unclosed meshes.
The example below is possibly the simplest instance of a
mesh object: a tetrahedron with a
side length of 8 um. A bigger
example is shown graphically in Figure 4.3, “
The Utah Teapot in MesoRD
CSG
”. By counting the number
of lines required for a typical
mesh object, it becomes apparent
that the added flexibility comes at the price of increased
verbosity. However, it should not be too difficult to write tools
to convert models built in external modelling programs to
MesoRD
mesh objects. In fact,
SBML is designed to be machine-written, not
human-written. Since CSG is a
MesoRD-specific extension to
SBML, there are no external tools for generating
geometries. Yet.
Example 4.4. Mesh Geometry
<compartment id="mesh">
<annotation>
<MesoRD:csg xmlns:MesoRD="http://www.icm.uu.se">
<MesoRD:mesh>
<MesoRD:triangle>
<MesoRD:vertex MesoRD:x="0"
MesoRD:y="4"
MesoRD:z="0"
MesoRD:units="um"/>
<MesoRD:vertex MesoRD:x="-4"
MesoRD:y="0"
MesoRD:z="0"
MesoRD:units="um"/>
<MesoRD:vertex MesoRD:x="4"
MesoRD:y="0"
MesoRD:z="0"
MesoRD:units="um"/>
</MesoRD:triangle>
<MesoRD:triangle>
<MesoRD:vertex MesoRD:x="0"
MesoRD:y="4"
MesoRD:z="0"
MesoRD:units="um"/>
<MesoRD:vertex MesoRD:x="4"
MesoRD:y="0"
MesoRD:z="0"
MesoRD:units="um"/>
<MesoRD:vertex MesoRD:x="0"
MesoRD:y="0"
MesoRD:z="-4"
MesoRD:units="um"/>
</MesoRD:triangle>
<MesoRD:triangle>
<MesoRD:vertex MesoRD:x="0"
MesoRD:y="4"
MesoRD:z="0"
MesoRD:units="um"/>
<MesoRD:vertex MesoRD:x="0"
MesoRD:y="0"
MesoRD:z="-4"
MesoRD:units="um"/>
<MesoRD:vertex MesoRD:x="-4"
MesoRD:y="0"
MesoRD:z="0"
MesoRD:units="um"/>
</MesoRD:triangle>
<MesoRD:triangle>
<MesoRD:vertex MesoRD:x="-4"
MesoRD:y="0"
MesoRD:z="0"
MesoRD:units="um"/>
<MesoRD:vertex MesoRD:x="0"
MesoRD:y="0"
MesoRD:z="-4"
MesoRD:units="um"/>
<MesoRD:vertex MesoRD:x="4"
MesoRD:y="0"
MesoRD:z="0"
MesoRD:units="um"/>
</MesoRD:triangle>
</MesoRD:mesh>
</MesoRD:csg>
</annotation>
</compartment>
Figure 4.3. The Utah Teapot in MesoRD CSG
The Utah teapot as a MesoRD
mesh primitive with 3751
triangles. The 18761 lines long SBML code
for this geometry was generated from an
s3d-file using a small shell
script.
There is no CSG "standard". Meshes are "non-standard" only in the sense that many CSG implementations do not support them.
Warning
The mesh primitive is a
highly experimental feature! In fact, the
are only a few cases in which the
mesh primitive has been tested
and is known to work. Those who try the
mesh primitive will discover that
geometry discretisation takes significantly longer than it does
for the simpler primitives.
The sphere primitive defines
a sphere centred at the origin. The single parameter defining a
sphere is the radius. The example below defines
a sphere with radius 5 um.
Example 4.5. Sphere Geometry
<compartment id="sphere">
<annotation>
<MesoRD:csg xmlns:MesoRD="http://www.icm.uu.se">
<MesoRD:sphere MesoRD:radius="5"
MesoRD:units="um"/>
</MesoRD:csg>
</annotation>
</compartment>
MesoRD supports one more primitive:
the special compartment
pseudo-primitive that allows the geometry of another compartment to
be treated just like any other geometric primitive. The
compartment primitive is not a
true primitive, because it is not a proper
terminal node.
While this sort of "copy operation" allows for new creative
ways in the definition of geometries, the main reason for its
inception is to allow one compartment to surround another
compartment. As was mentioned in the section called “
Tree Representation of CSG
”, it is not a good
idea to define geometries so that a point in space could belong to
several compartments. Using the
compartment primitive together with
the difference set operation, the containing
compartment may be defined as the left operand of a difference
operation. The right operand is set to the geometry of the
contained compartment. This will create a hole
in the containing compartment, just big enough to fit the contained
compartment.
A referenced compartment is identified by its unique
id field. The example below makes
use of the geometry of the original
compartment, defined elsewhere, in the definition of the
copy compartment by means of a
difference operation.
Example 4.6. The compartment Primitive
<compartment id="copy">
<annotation>
<MesoRD:csg xmlns:MesoRD="http://www.icm.uu.se">
<MesoRD:difference>
<MesoRD:box MesoRD:x="5"
MesoRD:y="30"
MesoRD:z="10"
MesoRD:units="um"/>
<MesoRD:compartment MesoRD:id="original"/>
</MesoRD:difference>
</MesoRD:csg>
</annotation>
</compartment>
Note
Previous version of MesoRD
required a compartment to be defined before
any reference through the
compartment primitive. This
requirement is now lifted. However, creating cycles is not
permitted. An easy way to create a cycle is to create a
compartment foo that references
bar that in turn references
foo.
rectangle is like a
box without an extension along the
z-axis.
Example 4.7. The rectangle Primitive
<compartment id="CompartmentOne">
<annotation>
<MesoRD:csg xmlns:MesoRD="http://www.icm.uu.se">
<MesoRD:rectangle MesoRD:x="5"
MesoRD:y="30"
MesoRD:units="um"/>
</MesoRD:csg>
</annotation>
</compartment>
circle is a circle in the x-y
plane[13]. Thus it only requires a radius.
Example 4.8. The circle Primitive
<compartment id="CompartmentOne">
<annotation>
<MesoRD:csg xmlns:MesoRD="http://www.icm.uu.se">
<MesoRD:circle MesoRD:radius="5"
MesoRD:units="um"/>
</MesoRD:csg>
</annotation>
</compartment>
The set of transformed primitives, or objects, are combined using difference, intersection and union set operations. These operations take two or more operand objects and combine them into a new object. Objects resulting from a set operation can act as operand objects in transformations or other set operations.
Note
The unary complement operation, which in combination with the union operation would obsolete the difference operation, is not supported, since MesoRD does not define a "universe".
The difference set operation
computes the difference between exactly two operands. The second
child of a difference node is
subtracted from the first. The
difference operation has no
parameters. The example below defines the geometry that results
when a sphere with radius 2 um and
centred at the origin, is subtracted from a cubic box with sides 8
um, also centred at the origin.
Example 4.9. Difference Operation
<compartment id="difference">
<annotation>
<MesoRD:csg xmlns:MesoRD="http://www.icm.uu.se">
<MesoRD:difference>
<MesoRD:box MesoRD:x="8"
MesoRD:y="8"
MesoRD:z="8"
MesoRD:units="um"/>
<MesoRD:sphere MesoRD:radius="2"
MesoRD:units="um"/>
</MesoRD:difference>
</MesoRD:csg>
</annotation>
</compartment>
The intersection set
operation computes the intersection of an arbitrary number of
operand geometries. The
intersection operation has no
parameters. The example below defines the geometry that results
when a cubic box with sides 8 um
and centred at the origin is intersected with a sphere with radius 5
um, also centred at the origin.
Example 4.10. Intersection Operation
<compartment id="intersection">
<annotation>
<MesoRD:csg xmlns:MesoRD="http://www.icm.uu.se">
<MesoRD:intersection>
<MesoRD:box MesoRD:x="8"
MesoRD:y="8"
MesoRD:z="8"
MesoRD:units="um"/>
<MesoRD:sphere MesoRD:radius="5"
MesoRD:units="um"/>
</MesoRD:intersection>
</MesoRD:csg>
</annotation>
</compartment>
The union set operation
computes the union of an arbitrary number of operand geometries.
The union operation has no
parameters. The example below defines the geometry that results
when a cubic box with sides 9 um
and centred at the origin is united with a sphere with radius 5
um, also centred at the origin.
Example 4.11. Union Operation
<compartment id="union">
<annotation>
<MesoRD:csg xmlns:MesoRD="http://www.icm.uu.se">
<MesoRD:union>
<MesoRD:box MesoRD:x="9"
MesoRD:y="9"
MesoRD:z="9"
MesoRD:units="um"/>
<MesoRD:sphere MesoRD:radius="5"
MesoRD:units="um"/>
</MesoRD:union>
</MesoRD:csg>
</annotation>
</compartment>
Clearly the shape of a compound object depends on the exact
location and orientation of the individual primitives. Therefore,
CSG trees in MesoRD
contain transformation nodes in addition to the set operation nodes.
Transformations allow subtrees to be rotated, scaled, sheared and
translated. These are all affine transformations, preserving the
parallelism of lines, but not lengths or angles. Every primitive
has its own transformation matrix which relates its local coordinate
system to the global coordinate system. For example, a cylinder
parallel to the x-axis is defined by rotating a
cylinder node by 90 degrees around the z-axis.
In case no transformation is specified, the unit transformation is
assumed. Transformations have no direct effect on set operations,
but are propagated to its children.
A transformation node will affect all leaf nodes below it in the tree. The transformation that will take a primitive leaf node from its local coordinate system to the global coordinate system is defined by the composition of all transformations on the path between the root and the respective leaf. The compound transformation is calculated as the matrix product of the corresponding transformation matrices.
Note that transformations affect 2D primitives similarly as 3D primitives. The transformations on 2D primitives may, of course, lack a z direction or a rotation axis.
An example which describes the union of a cone and a box is
illustrated in Figure 4.4, “
A CSG Tree with Transformations
”. The
root of the tree is a scale node, which defines a scale matrix
. The path
from the root to the cone primitive only passes through one
transformation node, namely the root. Thus, the transformation
matrix relating the local coordinate system, in which the cone is
defined, to the global coordinate system of the entire procedure, is
.
Figure 4.4. A CSG Tree with Transformations
The tree describes the union of a cone and a box. The box is translated with respect to the cone. The union of both primitives is scaled.
The box node is separated from the union node by a translation
node which defines a displacement matrix 
. The path
from the box primitive to the root passes through two transformation
nodes. The transformation matrix that relates the local coordinate
system of the box to the global coordinate system is
.
The rotation transformation
in MesoRD is defined by an axis of
rotation and a rotation angle. The rotation axis is given in the
local coordinate system, its length is irrelevant. Thus, the
parameters of a rotation node are
the Cartesian components of the direction of the rotation axis and
the counterclockwise rotation angle. The example below defines the
geometry that results when a cube with side length 5
um is rotated 20 degrees around the
local z-axis. One could just as well have used
radians for the rotation angle, since SBML
defines a radian unit.
Example 4.12. Rotation Transformation
<compartment id="rotation">
<annotation>
<MesoRD:csg xmlns:MesoRD="http://www.icm.uu.se">
<MesoRD:rotation MesoRD:x="0"
MesoRD:y="0"
MesoRD:z="1"
MesoRD:angle="20"
MesoRD:units="degree">
<MesoRD:box MesoRD:x="5"
MesoRD:y="5"
MesoRD:z="5"
MesoRD:units="um"/>
</MesoRD:rotation>
</MesoRD:csg>
</annotation>
</compartment>
The scale transformation in
MesoRD is defined by a scaling vector.
The scaling vector consists of the diagonal elements of the
diagonal, affine scale transformation matrix. The elements of the
scaling vector give the scale factor in each of the three Cartesian
dimensions in the local coordinate system. Thus, the parameters of
a scale node are the components of
the scale vector. The example below defines the geometry that
results when a sphere with radius 5 is scaled by a factor of two
along the local z-axis.
Example 4.13. Scale Transformation
<compartment id="scale">
<annotation>
<MesoRD:csg xmlns:MesoRD="http://www.icm.uu.se">
<MesoRD:scale MesoRD:x="1"
MesoRD:y="1"
MesoRD:z="2">
<MesoRD:sphere MesoRD:radius="5"
MesoRD:units="um"/>
</MesoRD:scale>
</MesoRD:csg>
</annotation>
</compartment>
The shear transformation in
MesoRD is defined by a shear axis and a
shear angle. The shear axis is given in the local coordinate
system, its length is irrelevant. Thus, the parameters of a
shear node are the Cartesian
components of the direction of the shear axis and the
counterclockwise shear angle. The example below defines the
geometry that results when a cube with side length 5 is sheared 2
radians around the local z-axis.
Example 4.14. Shear Transformation
<compartment id="shear">
<annotation>
<MesoRD:csg xmlns:MesoRD="http://www.icm.uu.se">
<MesoRD:rotation MesoRD:x="0"
MesoRD:y="0"
MesoRD:z="1"
MesoRD:angle="2"
MesoRD:units="radian">
<MesoRD:box MesoRD:x="5"
MesoRD:y="5"
MesoRD:z="5"
MesoRD:units="um"/>
</MesoRD:rotation>
</MesoRD:csg>
</annotation>
</compartment>
The translation
transformation in MesoRD is defined by a
displacement vector. The components of the displacement vector give
the displacements in each of the three Cartesian dimensions in the
local coordinate system. Thus, the parameters of a
translation node are the components
of the displacement vector. The example below defines the geometry
that results when a sphere with radius 5 is moved two
um two along the positive local
z-axis.
Example 4.15. Translation Transformation
<compartment id="translation">
<annotation>
<MesoRD:csg xmlns:MesoRD="http://www.icm.uu.se">
<MesoRD:translation MesoRD:x="0"
MesoRD:y="0"
MesoRD:z="2"
MesoRD:units="um"/>
<MesoRD:sphere MesoRD:radius="5"
MesoRD:units="um"/>
</MesoRD:translation>
</MesoRD:csg>
</annotation>
</compartment>