What is a solid modeller?
A geometric modeller is a program that builds and maintains a
representation of geometry, usually in three dimensions : geometric modelling of
one sort or another is the basis of most CAD systems. Solid
modellers are geometric modellers with a datastructure that supports an
inherent notion of solidity : i.e. the modeller will tell you whether a given
point is inside or outside the object it is representing. In practice, most
solid modellers also let you construct 'non-manifold geometry'—i.e. points,
curves and surfaces that are not part of a solid : thus the terms 'geometric
modeller' and 'solid modeller' have become more or less interchangeable, and
most systems have the ability to represent solids where appropriate.
Solids are usually represented as boundary models. These are
datastructures made of the vertices, edges and faces of a solid linked together
in a way that ensures that they correspond to a closed volume.
What is a kernel modeller?
Early modelling systems were written complete with a user interface,
processing and output routines suitable for the job for which the modeller had
been designed. More recently, the kernel modeller has appeared. This is
a piece of software that provides modelling functions in response to function
calls made through an application programming interface (API).
The success of the kernel modelling approach has not only been technical, but
it has also profoundly affected on commercial CAD systems. Many
well-known 3D CAD systems are now constructed based on kernel
modellers obtained from third parties, notably the Acis and Parasolid modelling
kernels, leaving system vendors with more effort to devote to user interface
and integration issues.
What is CSG?
Commercial kernels such as Acis and Parasolid are almost all based on
boundary models. Boundary models are constructed by combining simple shapes
using operators : especially Booleans, that add and subtract solids. If
these operations are stored and replayed then a new copy of the model is
constructed. This list of commands—or history—is usually much more compact than the
completed boundary model. Furthermore, it contains all the information that is
needed for the final geometry, including the representation of solidity.
It has long been known that such a list (actually a tree) of commands, is a
valid model in its own right, and it can be used to answer the same sort of
questions as the final model (e.g. is this point inside or outside the solid?)
without actually constructing a boundary model at all.
There is a significant advantage in this approach. Making a boundary model is
complicated, and inevitably inaccuracies creep in : in particular, the edges of a
boundary model often deviate slightly from the surfaces that they are bounding.
It is extremely difficult to stop these errors affecting subsequent
calculations ; but working directly from the history—which we will now call a
CSG model—we are using the 'raw' geometry, and robustness improves
substantially.
What is recursive division?
The problem with the CSG approach is that the whole model
(i.e. the entire history of its construction) has to be consulted to answer
every query. It's obvious that this must be the case : if we omitted to consult
any operator, that might just be an instruction to delete the whole model! So,
'pure' CSG operations are very slow compared to operations using
the boundary model, in which the scope of what we are trying to do can often be
narrowed down to some 'local' faces, edges and vertices, allowing most of the
model data effectively to be ignored.
An alternative method of restricting the amount of model that we have to
consider is to divide the space in which the model lies
recursively into smaller pieces, thus achieving localization in a
different way. By making sure that these pieces of space are geometrically
simple (usually cuboids aligned with the coordinates axes), we get the
localization without the great geometric complexity of the boundary
model. Many operations on CSG models intelligently localized using recursive
division are much faster than the same operations on boundary models.
The svLis modeller is a CSG kernel modeller that uses recursive
division. Originally a commercial product, compiled code for Linux and Windows
is now available for free FTP from the the svLis pages at Bath
University.
The main advantage of svLis is its robustness : it can manage without the
occasional tinkering that most boundary modellers require to deal with the
problem of mounting geometric errors over many manipulations of the model.
Therefore it is especially useful for applications in areas like robotics,
where many thousands of unsupervised geometric operations may be required to
support a (path, grasp etc.) planner which is testing alternative scenarios.
The main disadvantage of svLis is that, because it uses CSG,
models are not readily interchangeable with other systems. Sculptured surfaces
raise particular problems : the parametric representations that are widely used
in commercial CAD systems are inherently problematic in
CSG. However svLis can represent sculptured forms as implicit
(algebraic) surfaces : blends in particular can easily be modelled.
For full details see the
SvLis Introduction
and User Manual.
Geometric and solid modellers are not limited to representing single objects
in one position. Modern systems commonly include variational modelling
extensions, in which the sizes of various bits of a model are related in the
datastructure : so if, for example, you change the length of something, the rest
of the model readjusts itself in based on dependencies between the model's
dimensions specified by its creator. But these changes only result in one
'instance' of the model. It would be much more interesting if we could create a
model which took up all its possible positions or sizes at once.
This sounds implausible, but it's a concept that can easily be formalized, by
considering the changes in positions or sizes as dimensions of the model
(additional to the basic three spatial dimensions).
But how can we represent such multi-dimensional models? The boundary model is
already very complicated in three dimensions : we have already noted that models
of 3D objects require the support of consistent 2D and 1D entities (edges and
vertices). If we tried to construct a boundary model in n dimensions, we
should need supporting structures in (n-1), (n-2) dimensions
etc., right down to 1D again. Creating all this geometry would be bad enoungh :
enforcing consistency and keeping errors under control would be a nightmare.
Because the CSG model consists only of the original construction
geometry and combining operations, it can be taken into higher dimensions much
more easily : yes, the geometric elements become high-dimensional, but the
datastructure linking them remains the same. Furthermore, recursive division
can also be extended into many dimensions without undue difficulty : the cuboids
used in 3D become multidimensional boxes, which can be conveniently considered
as intervals in the various coordinates. Using this approach, an object with
different shapes and in different positions can be represented as single
model. We call the resulting structure a configuration-space model, because the
multi-dimensional space contains all the possible configurations of the model.
(The configuration-space concept originated in robotics.) By searching this
space, we can potentially find every configuration of the model that meets a
given set of criteria, rather than using the trial-and-error methods necessary
with an ordinary 3D variational model. For concrete examples of svLis in
action, see the svLis
pages at Bath University.
As far as we know, svLis-m is the first CSG multidimensional
modeller with capabilities of this sort. It was developed in conjunction with
our US collaborators Southco, Inc, who
produce a wide range of latches with subtle mechanisms. Southco are interested
in using svLis-m to see how changes in the shapes and dimensions of components
will affect the operation of a mechanism, and, in particular, whether there are
unexpected configurations that a mechanism can assume. (Obviously a regular
modeller is useless for this : if a configuration is unexpected, you can't
program it!)
SvLis-m is not yet available commercially : however, we are interested in finding
additional partners—in industry or research—who would like to collaborate in
realizing its potential. Please contact Adrian Bowyer.
| PERFICTA · PERFRACTA · QUÆRENDO · PERFECTA |