A Geometric Interface for Solid Modelling
|
|
Introducing Djinn A Geometric Interface for Solid Modelling |
| First published by the Geometric Modelling Society and Information Geometers Ltd. in May 1995. This is an online reissue and has not been revised. |
|
Solid modelling functionality can be made available for integration with applications by
packaging it under an API. Kernel modellers already
exist, but their API procedures are cast in terms of
their underlying modelling paradigms. The aim of the Djinn project is to
develop an innovative API for solid modelling research
which is cast in terms of geometric operations on point-sets, not
manipulations of model data-structures.
Ground rules for the API have been formulated. Its style relies heavily on hiding model data-structures and providing methods to interrogate them. Procedures to instantiate common geometric entities are to be provided explicitly in the API. The geometric scope of the API is to be non-manifold, stationary, three-dimensional point-sets. A bottom interface will be defined to allow more complex data-types, such as free-form surfaces, to be accessed indirectly. Ways are being explored to support useful but poorly defined modelling operations, such as 'tweaking', in the language of point-sets. |
The Djinn API is being developed by a group of
modelling researchers (the authors of this report) and another group of
applications researchers, together with the cooperation of vendors of
commercial systems, all in the UK. The result is not primarily intended as a
candidate for standardization, with all the delays that that implies, although
we hope I may influence future standardization efforts. Implementations of
Djinn are intended to be tools from which researchers can benefit in the
medium term.
The project started in October 1994, and is scheduled to finish in September 1996. The deliverables will consist mainly of a pair of reports, of which this is the first. The second and final report will be published in hardback book form at the end of the project, and will contain a specification of the Djinn API. In addition, a demonstration C++ binding is planned.
This first report is designed to bring the Djinn project to the attention of the solid modelling community, and outlines the philosophy behind the project, and the likely format of the API that will be developed.
We will be posting details of progress on the World Wide Web and we
warmly welcome contributions and criticisms from the international community
of solid modelling researchers and application researchers. Djinn's URL is:
http://www.bath.ac.uk/~ensab/GMS/Djinn/djinn.html
We are already studying a number of existing solid modelling APIs (see the Acknowledgements and the References) but would welcome details of others.
The authors gratefully acknowledge support for the Djinn project by the Control, Design and Production Group of the UK Engineering and Physical Sciences Research Council.
We are also grateful to EDS Ltd. for supplying complimentary copies of the Parasolid modeller and associated documentation. We acknowledge documentation received without charge from the US Army Ballistics Research Laboratory, from Perspective Design Ltd., and from many academic colleagues.
Background to Djinn
Research in solid modelling has been in progress for, say, twenty-five
years. Early arguments about the need for modellers—given those
excellent drafting systems—already sound authentically medieval. Solid
modelling is now a key technology without which effective CADCAM systems could not be built. There are many commercial
solid modellers available, supported by large teams of programmers.
Dazzled by the scale of these ventures, some people suggest that building existing modelling techniques into larger software edifices is now the only activity of interest. Of course, consequent technologies such as product modelling are important and fashionable areas both for research and for new software products. However, there are still many useful shapes and processes wholly or partially beyond the reach of existing solid modelling techniques. In many cases, making further progress in technologies which rely on solid modelling means making further progress with the fundamentals of solid modelling itself.
Despite twenty-five years of work, problems remain at the heart of solid modelling: for instance, converting boundary models (a.k.a. B-reps) to set-theoretic models (a.k.a. CSG) [28], dealing with degeneracy and inaccuracy [10], and constructing mechanisms for variational modelling [13]. At the same time, the technology is being extended in new directions, including: tolerance modelling [3, 14, 29], multidimensional [22] and cellular [21, 24] modelling, feature modelling and recognition [27], and physically based modelling [9]. And then there is the implementation of solid modelling algorithms—both extant and new—on parallel processors and other innovative hardware(e.g. [8]).
Of course, the need for research is not restricted to solid modelling itself. Enhanced rendering techniques and new CADCAM applications are widely reported. There are also many applications and potential applications of solid modelling in fields such as computer vision and robotics, and these fields have their own communities and literature. In short, there is a great deal of modelling work going on.
The availability of solid
modellers for research
Naturally, research in the application of solid modelling requires a solid modeller. In the early days, it was common for applications work to be done by people attached to a group developing and maintaining a research modeller. The Cambridge CAD Group and the Leeds Geometric Modelling Project were typical examples of large UK groups that grew up in this way. Elsewhere, the TIPS group in Tokyo and the Production Automation Project in Rochester in the US were very well-known examples. Changes in funding policy have perhaps made it more difficult to build large groups to do research in solid modelling; certainly, there are fewer of them now. In any case, there is too much applications research going on for it to be organized in a satellite fashion around modelling research groups. Applications researchers have developed their own communities, as the scope and complexity of their work increases.
In the early days, research groups would make modellers—such asTIPS [ Continuing simplification of access has led to the emergence of modellers
explicitly conceived and labelled as kernel modellers, in which
modelling functionality is packaged beneath an application programming
interface, or API. Commercial kernel modellers
include the boundary modellers ACIS [5] and Parasolid [35], a
descendant of Romulus. Recently, Svlis [2] has
demonstrated that set-theoretic modelling functionality can also be packaged
as a kernel. Although few, kernel modellers have quickly become popular for
applications research. However, they still pose some problems for the
applications researchers and, less directly, for modelling researchers as
well.
Using a kernel modeller, the very approachability of the technology can be a
problem. As well as becoming dependent on a particular vendor, applications
researchers can tether themselves to a particular modelling paradigm and even
to a particular programming language. Object-oriented languages such as
C++ make it very tempting to allow users access to data
classes. Thus users can become further enmeshed by a commitment to one
particular data-structure. This is paradoxical, as a major advantage of
object-orientation is its ability to encapsulate and to hide detail
from the user.
These problems for applications researchers are mirrored by the problems now
faced by modelling researchers who want to get their techniques into use. With
applications researchers locked into a particular vendor, it is increasingly
difficult to get research ideas tested in practice. Even when modelling
researchers offer new functionality that is extremely relevant to a particular
application, it is difficult to find applications researchers prepared to make
the painful transition from a commercially supported modeller to a research
modeller with dubious support which also differs—obtrusively, if
trivially—in every detail of implementation.
Although kernel modellers provide modelling functionality in a form
designed for integration into a larger system, the facilities offered by
existing interfaces are tied closely to the modelling paradigm in use and,
indeed, also to the internal structure of the modeller. It is probably
unreasonable to expect commercial, or for that matter academic, implementors
of solid modelling systems to offer a more general interface than their
modeller supports: certainly not without encouragement. Spontaneously
specifying unused parts of an API involves work, and
merely draws attention to absent or 'unimplemented' features.
However, some independent APIs have been specified. An
early and well-known example is the AIS (Application
Interface Specification) originally developed for CAM-I, and now a draft ANSI
standard [23]. Both boundary and set-theoretic
modelling paradigms are supported. Some operations, such as Boolean
combinations, can be performed on either boundary or set-theoretic models; and
low-level geometric operations (e.g. the creation of 'non-controversial'
geometric items such as points, straight lines and planes) are common to both
types of supporting modeller. But a number of operations address the boundary
data-structure or set-operator tree directly. Thus the interface is
effectively split into two parallel parts (albeit with shared elements), each
servicing one of the alternative types of modeller.
In the same way, the STEP product data exchange
standard (ISO 10303) accommodates both boundary and
set-theoretic models, but again only in parallel; in fact, a look at Part 42
of STEP [20] shows that
support for set-theoretic models is rather perfunctory. Note that, while
STEP is of course a product data standard, it
is relevant because there is a related API being
developed, called SDAI [34].
But, in any case, STEP is probably unsuitable as a
research interface by reason of simple inertia. Eastman has recently provided
a penetrating critique [7] of ways in which
STEP already lags behind current commercial (let alone
research) modelling technology.
Objectives of the Djinn project
The Djinn API is intended to be a tool that will help
modelling researchers. But the Djinn project is itself research. It is not
immediately obvious that a level exists at which practical modelling
operations can be specified independent of a particular modelling paradigm.
The problem of converting boundary models to set-theoretic models has already
been mentioned. Despite heroic efforts to find a solution [28], it would be foolish to define an API predicated on the availability of a general and workable
solution to this historic obstacle. Converting to and from voxel modellers is
even more challenging. Such digital solids are often used as approximations
of shapes, from which many of the original characteristic entities
(e.g. surface types) have been eliminated. In this case, the meaning of
'conversion', let alone its implementation, needs some thought.
While the writers of previous APIs have sidestepped issues
of model conversion by supporting boundary and set-theoretic models in
parallel, perhaps something better can be done which still does not
require solutions to these classic conversion problems. Djinn is an attempt
to achieve this by casting an API in the language
of point-sets and avoiding explicit reference to model data structures:
boundary representations, set-operator trees, voxels, or whatever.
While every modeller would not necessarily have to provide functionality to
perform every procedure in the API, operations that
were geometrically the same would be performed using the same procedures,
irrespective of the underlying implementation. The calling program would
manipulate models as a point-set data-type, and would not become involved in
editing boundary graphs, set-expressions, oct-trees, or any other specific
model data-structure. Other point-set entities, such as points and edges,
would also be represented uniformly at the API level
as point-sets.
As far as the authors are aware, this approach is new.
Style of the Djinn API
A major problem in using an API is the need to
remember a large set of procedure names and argument types. In general, a
minimalist approach is taken in Djinn, achieving richness by a combination of
procedures, not by having a large number of them. Naturally, general
procedures can involve more parameters than are convenient in certain common
cases. Therefore, they need to be augmented by some convenient and intuitive
specialized procedures: for creating well-known 'primitive' objects, for
example.
In addition to the Djinn procedures which support calls to the underlying
modeller, a 'bottom interface' will also be supplied. This defines procedures
that the modeller itself can invoke, and will provide a generalized mechanism
for access to complicated geometric elements, such as free-form curves and
surfaces, geometry embedded in two dimensions, and general half-spaces. These
geometric elements are not supplied explicitly to the modeller; they are
constructed and modified by software external to the Djinn implementation,
which works with references to them.
The meat of the Djinn API is the specification of a set of
procedures. Pre- and post-conditions will be attached to the API calls, as well as facilities for error-handling. The
possibility of using formal methods to define the calls has been considered,
but the resource constraints on the Djinn project do not allow a fully fledged
formal approach.
Although the whole philosophy of Djinn is against modeller-specific features,
it is acknowledged that there is a need for passing auxiliary
information to the underlying modeller: for instance parameters to improve
efficiency, and practical ways of transmitting this information must be
considered.
The problems of accuracy have already been mentioned. The form of
data-structures and, especially, the specification of pre- and
post-conditions, must take account of accuracy requirements, distinguishing
clearly between the requirements to be met by ideal, and by actual, data.
Just three categories of data-type are planned. Their definitions aim to
avoid the exposure of specific modelling data-structures:
It is not obvious exactly where the dividing line should come between
simple and hiddewn data-types. This is a design decision to be taken in the course of
developing Djinn.
The philosophy of Djinn is to make the effect of procedure calls as
predictable as possible.
It is essential that Djinn should provide mechanisms for reporting
the level of success achieved by any procedure call. Thus, error-reporting
mechanisms must be available that allow errors which are non-fatal—and
may even be expected—to be processed efficiently during an active
modelling session, but the error-reporting mechanisms should also provide
adequate information for debugging. The following are some of the major
facilities that are required:
The labels which are given to geometric data cannot be addresses, as
these are obviously very fragile. A part of the API
will be required for 'input and output', but the nature and format of the data
that is written out and read in will obviously vary from modeller to modeller.
Labels and attributes would be expected to persist over an archival read and
write cycle, but not necessarily over every internal operation
(e.g. operations involving inheritance rules, where some labels or
attributes might be destroyed). Of course, archiving of this sort precludes a
file created by one modeller being read by another.
It is not expected that Djinn will itself support journalling (undo, redo
etc.), although the design of Djinn should facilitate its implementation above
the API. The requirement for journalling is in any
case expected to be reduced if procedures have no side-effects.
Because Djinn does not specify the internal data-types or data-structures
that the modeller must create or maintain, it does not provide a mechanism for
two modellers to contribute functionality to an overall implementation, under
one instance of the API. However, the possibility of
an application calling two modellers running in tandem, each separately
implemented under Djinn, is an interesting one.
One of the classic criticisms of vendors' implementations of software
standards (e.g. programming languages or data exchange file formats) is
that vendors omit to implement some (maybe difficult) aspects of a standard,
and cannot resist adding extra procedures. Djinn is not intended to become a
standard; what is research for but inventing new things? So partial
implementations which also provide new functionality are to be expected.
Furthermore, because Djinn is intended to be supported by modellers with very
different technological bases, the quality of implementation must be permitted
to vary. It is expected that some modellers will be able to respond (with
useful results, not error-messages) to some API calls
under one set of circumstances, but not under others.
What is a 'Djinn-compliant' API? At a trivial level,
it is a set of procedures covering the API which return
consistent error messages, even without any geometric functionality at all. At
another level, it is the support of a coherent subset of Djinn
procedures. A modeller which only allows primitives orthogonal to the axes
cannot logically support a general rotation transform. A simple
spatial-enumeration modeller does not hold (useful) face information and so
cannot easily support procedures assigning labels to faces. It might be
possible to enumerate some logically consistent subsets of the API but, equally, this may imply more about the underlying
modellers than is appropriate.
At another level, implementations may be limited by simple matters such as
storage, so that procedures cannot be supported merely because a model is too
large. And at yet a further level, we have to note that accuracy of
the results returned from calls to the API will also
vary from implementation to implementation.
In summary, 'Djinn-compliant' modellers should be expected to provide access
to their underlying representation in terms of point-sets, and to use the
procedures provided by the Djinn API to achieve this.
Scope of the Djinn API
An appropriate scope for the Djinn API is now
suggested, and some of the issues to be resolved are reviewed. This
itemization may, perhaps, have some interest to the modelling community
independent of the specific solutions which are scheduled to come later in the
Djinn project.
Every geometric modeller is limited in the range of shapes that it
can handle (which is one reason for continuing research in geometric
modelling). In designing Djinn, a target domain is essential. Since it is
not suggested that every modeller should support the whole domain, it can and
should be rich, providing plenty of incentive to extend coverage. On the
other hand, excursions into fanciful generality, which is unlikely to be
seriously supported within the life of the interface specification, will
interfere with its usability by the application community.
While acknowledging research interest in multi-dimensional models
(i.e. systems supporting models of arbitrary dimensionality [22], the plan at present is to support entities of three
or fewer dimensions, all embedded in three-dimensional space. That excludes
both higher-dimensional entities and 'drafting' constructions. Even so,
facilities must be provided to export the result of a sectioning operation and
to import two-dimensional geometry for sweeping.
Further, it is not planned that Djinn will provide explicit support for
objects in motion or parameterized objects. Initial discussions with
applications researchers indicate that in many cases, even where moving or
variable solids are important in applications, the geometric computations
required can be adequately performed on static and invariant models
(e.g. using sweeps or by sampling).
Point-set theory as a base for
semantics
The abstraction on which Djinn is predicated is that of point-sets,
with geometric entities of all dimensionalities up to three, defined as open
point-sets embedded in three dimensions:
Models may be constructed by set-operations on these entities. While they
are defined in terms of open point-sets, both regularized and non-regularized
set-operations will no doubt be required [18].
Set-theory has been strongly associated with the 'CSG' modelling community, and boundary modellers have
typically exploited ideas from topology, such as Euler operators. However, it
is not easy to escape from the observation that correct topology follows from
solidity, not the other way around.
Support for cellular and non-manifold objects is essential, in particular
for simplifications and meshing for finite-element analysis, and for
representing hierarchies of features. It is intended that cellular models
will be represented as collections of point-sets [17, 25].
Sometimes, models of point-sets are used as approximations to
other, notionally exact, models: typically to make some computation more
tractable. For instance, a quadric-surfaced model might be approximated by a
faceted model or a voxel model. Approximations of this sort involve a level
of imprecision which is grosser than, and of a different sort to, the
imprecision already inherent, in reality, in 'exact' models, resulting from
the use of floating-point numbers.
In the simplest case, an approximate model may be a strictly internal
data-structure which is used to assist computations on the exact model, such
as a voxel model used as a localizing spatial segmentation. In this case, the
nature of the approximate model does not affect the results of computations
(at least, only in the same way as any other choice of algorithm), and it
should be invisible across the API.
More complex situations arise when approximate models are used to stand in
for exact models. Such substitutions bring interesting problems in the design
of an API. When a procedure is invoked to return an
entity from the model, should this be: a entity taken from the approximate
model, an approximation to the corresponding entity in the exact model, or a
reconstruction of that exact entity? For instance, if a voxel model is
approximating a quadric-surfaced model, and a procedure is called which should
return a face, does the calling program expect to receive the face of a single
voxel, a set of voxels corresponding to an exact face, or a reconstruction of
the face, made by some fitting process?
At the level of the procedure call itself, there is no distinction, since all
these data-types are hidden. However, knowing or controlling the level of
approximation within the hidden data is obviously essential, and the API needs to be able to support whichever options are
required. Significant problems include:
Finally, there needs to be a way to control the creation of
approximate models, unless the underlying modeller is always able to decide
autonomously when this is necessary. It seems unlikely that all the
procedures needed to control model conversions can themselves be described
purely in the language of point-sets.
Most of the geometric objects required will be point-sets. However,
some other simple geometric objects, such as vectors, as well as the usual
numerical data-types, are also required.
It will not necessarily be possible explicitly to create geometric
data of every type using the API. Some types of data
will result from modelling operations. Intersection curves are good examples:
there is unlikely to be any procedure which would allow synthetic intersection
curves to be added to the model from outside, but procedures to interrogate
intersection curves will have to be provided.
Procedures will certainly be provided to create primitives such as planes and
natural quadrics explicitly, together with tori and probably cyclides and
'solid helices' (spring-shapes). Creation and interrogation of other geometry
will be supported indirectly through the bottom interface.
Solids cannot be constructed by set-theoretic operations on surfaces,
and so set-theoretic modellers cannot easily support parametric surfaces: at
least, not as faces of a solid. Boundary models can include parametric
patches, but the topological consistency that is maintained within boundary
models is not equivalent to a guarantee that the models are unambiguous
representations of trivariate point-sets (e.g. after tweaking, but see
also [12]).
One way to involve parametric surfaces in the creation of solids is to require
surfaces to be supplied together with a bottom-interface procedure that serves
the purpose of a point-membership test: some test on the surface which allows
points to be classified as inside or outside a related volume. For instance,
a ray might be cast from the point supplied, in a specified direction, and
intersections with the surface counted. This provides a de facto
solid, and is one way in which parametric surfaces were introduced into
Boolean operations in early boundary modellers. But it is cumbersome; the
point-set defined is not always a very convenient one to combine with others
to get the solid required. Users of today's boundary modellers expect much
more flexibility in 'stitching together' parametric surfaces, even at the
expense of rigour.
Solids as connected
components
A boundary model is a set of surfaces that divides space into two or
more connected components. The connectivity structure of boundary
models means that the number of components is usually known, so the idea of
identifying connected components does not figure explicitly in the literature
of boundary modellers. At the level of the Djinn API,
however, a procedure that identifies and enumerates the connected components
into which a model divides space would provide a more rigorous framework for
creating solids by 'stitching'.
If a boundary modeller is supporting the API,
recognition of connected components can be interpreted as a stitching
operation, although accurate implementation of the API
would require verification that the resulting model really represented the
components. Note that a correct implementation would identify a 'leaky'
boundary as one that did not contain a separate component. Failure of the
procedure in this sense would merely result in the reporting of fewer
components than expected.
Identifying connected components has been a topic of research in
set-theoretic [32] and voxel modelling (in
particular as represented by oct-trees [26]), and
there seems no reason why the recognition of connected components of space
could not be approached in the same way as the identification of connected
components of a solid. By this route, one might find modelling systems based
on set-theory and oct-trees which are able to create models from surfaces by
the same sort of stitching methods previously associated uniquely with
boundary models, but with results certain to be point-sets.
Free-form surface
formulations
While current commercial modellers seem to be heavily focused on B-splines,
and specifically NURBS, very many more types of
parametric and implicit surface are of current interest in the research world.
It is therefore appropriate for Djinn to support free-form surfaces
generically, and not to attempt to provide separate procedures for each type.
A number of specialist packages are available to provide surface creation and
editing procedures (e.g. SISL [36]). Given the wide multiplicity of surface forms,
especially parametric patches, this is obviously beneficial: potentially, the
users of a solid modelling system can 'plug in' surface types common in their
own industries, or proprietary surface formulations.
The mechanism for this is the import of references to external data through
the top interface, and interrogation through the bottom interface: a second
set of procedures defined as part of Djinn, which are called by the solid
modeller supporting the API. Such procedures will
allow properties such as surface normals to be discovered, and interrogations
such as ray-tests performed. The procedures could be serviced by a surface
geometry package, or by such a package embedded in other software, under the
bottom interface.
Since Djinn is deliberately avoiding exposure of the classic modelling
data-structures at the API level, a neutral—but
efficient—way of grouping geometric elements into models is essential.
This would support operations such as extracting all the faces or edges of an
object, or modelling assemblies; it would also address the requirements of
cellular modelling.
In addition to the primary labels by which geometric elements are
identified across the API, it is necessary to handle
externally defined attributes. Features, parametric models and constraints
are important areas in modelling, but these technologies are in a state of
development that makes it difficult to provide generalized functionality to
incorporate them in an API. It is intended to provide
attributes in a way that will facilitate these techniques as processes running
above the API. However, it is fair to note
that the support of generalized variational design in such an indirect way is
definitely challenging.
Appropriate procedures must be provided to instantiate the data-types
outlined in the last section. It is likely to be convenient if bounded
primitives can be created directly, and facilities are provided to create
primitives in the positions where they are required: rather than obliging the
user to bound semi-infinite primitives, and perform subsequent transforms
explicitly.
Geometric modifications, acting on data already instantiated, must be
expressed in terms of point-sets. Booleans are of course formulated as
set-theoretic operations, but others, such as blends [30, 31] and so-called 'local
operations', such as tweaking [11], commonly
associated with boundary models, may need considerable reformulation.
Typically, they do not reliably map one point-set to another, and re-casting
them in the language of point-sets is a problem to be addressed.
There is a great range of transforms that could be allowed in a solid
modelling API. It is well-known that the transforms
which happen to be implementable using a particular mathematical technique,
such as matrix multiplication of homogeneous coordinates, can force the domain
of a modeller to include many unusual geometric objects which may be difficult
to implement and infrequently used. Grouping transforms by invariants
facilitates the selection of a more coherent set:
Solid-body transforms provide a minimal set, but other possibilities will
be considered. For instance, it may be convenient for users to be able to
define their own transform routines, to be supplied as arguments to Djinn
procedures.
A range of sweep operations should be supported, and Minkowski sums (also
called set sums or vector sums) [16] provide
a convenient formalism to describe these in terms of point-sets.
Unfortunately, Minkowski sums do not give a complete set of useful sweeps
(e.g. a profile rotating along a spine curve), and therefore possible
extensions (e.g. performing the Minkowski sums in transformed coordinate
systems) must be considered.
Where complicated two-dimensional profiles are required for sweep
operations, it is envisaged that they will be defined as external data,
imported by reference, and interrogated through the bottom interface.
These are intrinsic properties of a single point-set, such as
integral properties, connectedness and genus.
It is also appropriate to add support for some powerful operations which
are naturally stated in terms of point-sets, such as constructing Voronoi
diagrams [15], even though they do not necessarily map
straightforwardly on to existing modelling technologies.
These are properties of one object relative to another and include
set-membership tests and boundary connectivity relationships, as well
as interference and distance properties. It is obvious that some of these
procedures are more easily computed by set-theoretic modellers, and others by
boundary modellers, but both sorts of query are geometric and are
supportable by both sorts of model.
Labelling new geometry
Because there will be no boundary representation or set-operator tree
accessible through the Djinn interface, it is important to be able to access
pieces of geometry through unique labels. Attaching labels to geometry as it
is instantiated is relatively straightforward. However, as modelling
operations are performed, geometric elements are destroyed and new ones
created, which are unlabelled. API procedures
accessing geometry must have a polite way of telling the calling program when
geometric elements are defunct. It is equally important, but much more
difficult, to provide a class of procedures for allocating labels to new
elements on a purely geometric basis (e.g. a partial ordering in some
specified direction), which does not rely on their location in an
internal data-structure.
Some or all of the text of this may be made available on the World Wide Web
for comment prior to publication. Note again that Djinn's URL is: http://www.bath.ac.uk~ensab/GMS/Djinn/djinn.html
It is also our intention to place the C++ binding of
Djinn into the public domain, and to make it available over the Internet by
anonymous FTP.
APIs such as AIS and
SDAI provide a front-end to existing modelling
paradigms. By contrast, the aim of the Djinn1 project is to determine a set of more abstract
geometric data and operations that different types of modellers can support in
a uniform way; and then to specify a non-commercial application programming
interface (API) for solid modellers which is cast in
terms of those abstractions. It is intended that Djinn may be supported by
boundary modellers, set-theoretic modellers, and indeed any other type of
modeller that unambiguously defines solid objects, for instance 'voxel'
modellers based on oct-trees. As well as being independent of particular
modelling data-structures and algorithms, the API
should also be independent of specific programming languages. Further, there
is no plan for any direct support for graphics, let alone a specific graphics
environment, although operations that provide data in an appropriate form for
generating graphics will be included.
It is convenient to outline the style of the Djinn
API at this point. The software engineering aspects of
Djinn are, in practice, almost as important as its geometric coverage.
Precision and formality in
definition of the API
Point-set dimensionality
Geometric elements
Nilvariate
(0D)
points
Univariate
(1D)
curves
Bivariate
(2D)
surfaces
Trivariate
(3D)
solids
Transforms
Invariants
Solid-body
Distance
Scaling
Distance ratios
Affine
Infinity and ratios
Projective
Straight lines and cross-ratios
Möbius
Circles and sphere
This document gives an overview of the topics that the authors have
been considering as they have started to define the Djinn
API. Our next publication is scheduled to be a book giving the Djinn
definition.
1.
G.P. Bassi, "Building a parametric CSG modeller for industrial
environment: procedural representation and geometrical issues", in
Set-theoretic Solid Modelling: Techniques and Applications (Proceedings
of the CSG 94 Conference, Winchester) (321-335), Information Geometers, April
1994.
2.
A. Bowyer, Svlis: Introduction and User Manual, Information
Geometers 1994.
3.
M. Boyer and N.F. Stewart, "Modelling spaces for toleranced
objects", International Journal of Robotics Research 10,5
(570-582), October 1991.
4.
I.C. Braid, "Notes on a geometric modeller", Cambridge University,
Computer Laboratory CAD Group, Document 101, June 1980.
5.
I.C. Braid, "Improving product models and kernel modellers", in
Organisation of Engineering Knowledge for Product Modelling in
Computer-Integrated Manufacturing, ed. T. Sata (275-299),
Elsevier, 1989.
6.
S.A. Cameron and J.C. Aylett, "Robmod: a geometry engine for
robotics", Proceedings of the IEEE International Conference on Robotics and
Automation, Philadelphia (880-885), April 1988.
7.
C.M. Eastman, "Out of STEP?", Comment article in Computer-Aided
Design 26,5 (338-340), May 1994.
8.
J.L. Ellis, G. Kedem, R.J. Marisa, J.P. Menon and
H.B. Voelcker, "The RayCasting engine and ray representations: a
technical summary", International Journal of Computational Geometry and
Applications 1,4 (247-380), December 1991.
9.
I.A. Essa, S. Sclaroff and A.P. Pentland, "Physically based
modelling for graphics and vision", Chapter 5 of Directions in Geometric
Computing ed. R.R. Martin (161-218), Information Geometers,
1993.
10.
S. Fortune, "Progress in computational geometry", Chapter 3 of
Directions in Geometric Computing, ed. R.R. Martin (81-127),
Information Geometers, 1993.
11.
A.R. Grayer, "Alternative approaches in geometric modelling",
Computer-Aided Design, 1,4 (189-192), May 1980.
12.
C.M. Hoffmann and J.E. Hopcroft, "Geometric ambiguities in boundary
representations", Computer-Aided Design 19,3 (141-148),
1987.
13.
C.M. Hoffmann, "On the semantics of generative geometry representations",
in Advances in Design Automation (ASME DE Vol. 65),
1993.
14.
N.P. Juster, "Modelling and representation of dimensions and tolerances:
a survey", Computer-Aided Design 24,1 (3-17), 1992.
15.
D.A. Lavender, A. Bowyer, J.L. Davenport, A.F. Wallis and
J.R. Woodwark, "Voronoi diagrams of set-theoretic solid models", IEEE
Computer Graphics and Applications 12,5 (69-77), September
1992.
16.
A.E. Middleditch "Application of vector sum operator", Computer-Aided
Design 20,4 (183-188), May 1988.
17.
A.E. Middleditch, "Cellular models of mixed dimension", Brunel
University, Department of Computer Science, Technical Report BRU/CAE/92:3,
April 1992.
18.
A.E. Middleditch, "'The bug' and beyond", in Set-theoretic Solid
Modelling: Techniques and Applications (Proceedings of the CSG 94
Conference, Winchester) (1-16), Information Geometers, April 1994.
19.
N. Okino, H. Kakazu and H. Kubo, "TIPS-1: technical information
processing system for computer-aided design, drawing and manufacturing", in
Computer Languages for Numerical Control (Proceedings of the
PROLAMAT 73 Conference, Budapest), ed. J. Hatvany,
North-Holland (141-150), 1973.
20.
J. Owen, STEP: An Introduction, Information Geometers,
1993.
21.
A. Paoluzzi, F. Bernardini, C. Cattani and V. Ferrucci,
"Dimension-independent modeling with simplicial complexes", ACM
Transactions on Graphics 12,1 (56-102), January 1993.
22.
S.J. Parry-Barwick and A. Bowyer, "Multidimensional set-theoretic
feature recognition", to appear, Computer-Aided Design.
23.
P. Ranyak, "Application Interface Specification (AIS): Volume I:
Functional Specification", CAM-I Report R-94-PM-01 (Version 2.1),
1994.
24.
J.R. Rossignac and M. O'Connor, "SGC: a dimension-independent model
for pointsets with internal structures and incomplete boundaries", in
Geometric Modeling for Product Engineering, eds. M.J. Wozny,
J.U. Turner and K. Preiss (Proceedings of IFIP WG 5.2 Working
Conference, Rensselaerville, September 1988) (145-180), North-Holland, 1990.
25.
J.R. Rossignac and A.A.G. Requicha, "Constructive non-regularized
geometry", Computer-Aided Design 23,1 (21-32), January/February
1991.
26.
H. Samet and M. Tamminen, "Efficient component labelling of images
of arbitrary dimension", University of Maryland Computer Science Department
Report TR-1480, February 1985.
27.
J.J. Shah, "Assessment of features technology", Computer-Aided
Design 23,5 (331-343), June 1991.
28.
V. Shapiro and D.L. Vossler, "Separation for boundary to CSG
conversion", ACM Transactions on Graphics 12,1 (35-55), January
1993.
29.
J.U. Turner and A.B. Gangoiti, "Tolerance analysis approaches in
commercial software", Concurrent Engineering 1,2 (11-23),
1991.
30.
J. Vida, R.R. Martin and T. Varady, "A survey of blending
methods that use parametric surfaces", Computer-Aided Design
26,5 (341-365), May 1994.
31.
J.R. Woodwark, "Blends in geometric modelling", in The Mathematics of
Surfaces II, ed. R.R. Martin (225-297), Oxford University Press,
1987.
32.
J.R. Woodwark "Splitting set-theoretic solid models into connected
components", Geometric Modeling for Product Engineering,
eds. M.J. Wozny, J.U. Turner and K. Preiss (Proceedings of
the IFIP WG 5.2 Working Conference on Geometric Modeling,
Rensselaerville, September 1988) (61-70), North-Holland, 1990.
33.
"An Introduction to PADL", University of Rochester, Production Automation
Project, Report TM 24, December 1974.
34.
"Industrial automation systems and integration - Product data representation
and exchange - Part 22: Implementation methods: Standard data access interface
specification", ISO TC 184/SC4 N280 (committee draft), 1994.
35.
"Overview of Parasolid", Parasolid Business Unit, EDS, March 1995.
36.
"Modelling of complex shaped parts" and "Modelling of sheet metal parts",
Sections 3.3.3 and 3.3.4 in IMPPACT: Integrated Modelling of Products and
Processes using Advanced Computer Technologies (ESPRIT II -
CIM III.1.3.1 Project 2165), eds. O. Björke and
O. Myklebust (118-134), Tapir, 1992.
37.
"Romulus", Proceedings of a Geometric Modelling Seminar, Robinson College
Cambridge, 12-14 December 1983, ed. I.D. Faux, CAM-I Report
P-83-GM-01, CAM-I Inc., Arlington, Texas, 1983.
1.
Djinn: a demon of Arabian mythology, able to assume many forms, and to
become "invisible at pleasure" [Brewer's Dictionary of Phrase and
Fable]. This is an admirable pattern for a transparent interface. The
astute reader will probably have already realized that "Djinn" is also an
acronym—of a sort.
BACK TO TEXT
Back to the
contents list
Back to the Djinn publications
page