S E T - T H E O R E T I C   K E R N E L   M O D E L L E R

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

SvLis is also the only modeller that we know of with a Latin motto.
Roughly, it means : "Make it, break it—that'll be perfect."