Version 2, June 1991
Copyright © 1991 Free Software Foundation, Inc. 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA Everyone is permitted to copy and distribute verbatim copies of this license document, but changing it is not allowed. [This is the first released version of the library GPL. It is numbered 2 because it goes with version 2 of the ordinary GPL.]
The licenses for most software are designed to take away your freedom to share and change it. By contrast, the GNU General Public Licenses are intended to guarantee your freedom to share and change free software--to make sure the software is free for all its users.
This license, the Library General Public License, applies to some specially designated Free Software Foundation software, and to any other libraries whose authors decide to use it. You can use it for your libraries, too.
When we speak of free software, we are referring to freedom, not price. Our General Public Licenses are designed to make sure that you have the freedom to distribute copies of free software (and charge for this service if you wish), that you receive source code or can get it if you want it, that you can change the software or use pieces of it in new free programs; and that you know you can do these things.
To protect your rights, we need to make restrictions that forbid anyone to deny you these rights or to ask you to surrender the rights. These restrictions translate to certain responsibilities for you if you distribute copies of the library, or if you modify it.
For example, if you distribute copies of the library, whether gratis or for a fee, you must give the recipients all the rights that we gave you. You must make sure that they, too, receive or can get the source code. If you link a program with the library, you must provide complete object files to the recipients so that they can relink them with the library, after making changes to the library and recompiling it. And you must show them these terms so they know their rights.
Our method of protecting your rights has two steps: (1) copyright the library, and (2) offer you this license which gives you legal permission to copy, distribute and/or modify the library.
Also, for each distributor's protection, we want to make certain that everyone understands that there is no warranty for this free library. If the library is modified by someone else and passed on, we want its recipients to know that what they have is not the original version, so that any problems introduced by others will not reflect on the original authors' reputations.
Finally, any free program is threatened constantly by software patents. We wish to avoid the danger that companies distributing free software will individually obtain patent licenses, thus in effect transforming the program into proprietary software. To prevent this, we have made it clear that any patent must be licensed for everyone's free use or not licensed at all.
Most GNU software, including some libraries, is covered by the ordinary GNU General Public License, which was designed for utility programs. This license, the GNU Library General Public License, applies to certain designated libraries. This license is quite different from the ordinary one; be sure to read it in full, and don't assume that anything in it is the same as in the ordinary license.
The reason we have a separate public license for some libraries is that they blur the distinction we usually make between modifying or adding to a program and simply using it. Linking a program with a library, without changing the library, is in some sense simply using the library, and is analogous to running a utility program or application program. However, in a textual and legal sense, the linked executable is a combined work, a derivative of the original library, and the ordinary General Public License treats it as such.
Because of this blurred distinction, using the ordinary General Public License for libraries did not effectively promote software sharing, because most developers did not use the libraries. We concluded that weaker conditions might promote sharing better.
However, unrestricted linking of non-free programs would deprive the users of those programs of all benefit from the free status of the libraries themselves. This Library General Public License is intended to permit developers of non-free programs to use free libraries, while preserving your freedom as a user of such programs to change the free libraries that are incorporated in them. (We have not seen how to achieve this as regards changes in header files, but we have achieved it as regards changes in the actual functions of the Library.) The hope is that this will lead to faster development of free libraries.
The precise terms and conditions for copying, distribution and modification follow. Pay close attention to the difference between a "work based on the library" and a "work that uses the library". The former contains code derived from the library, while the latter only works together with the library.
Note that it is possible for a library to be covered by the ordinary General Public License rather than by this special one.
NO WARRANTY
If you develop a new library, and you want it to be of the greatest possible use to the public, we recommend making it free software that everyone can redistribute and change. You can do so by permitting redistribution under these terms (or, alternatively, under the terms of the ordinary General Public License).
To apply these terms, attach the following notices to the library. It is safest to attach them to the start of each source file to most effectively convey the exclusion of warranty; and each file should have at least the "copyright" line and a pointer to where the full notice is found.
one line to give the library's name and an idea of what it does. Copyright (C) year name of author This library is free software; you can redistribute it and/or modify it under the terms of the GNU Library General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public License for more details. You should have received a copy of the GNU Library General Public License along with this library; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Cambridge, MA 02139, USA.
Also add information on how to contact you by electronic and paper mail.
You should also get your employer (if you work as a programmer) or your school, if any, to sign a "copyright disclaimer" for the library, if necessary. Here is a sample; alter the names:
Yoyodyne, Inc., hereby disclaims all copyright interest in the library `Frob' (a library for tweaking knobs) written by James Random Hacker. signature of Ty Coon, 1 April 1990 Ty Coon, President of Vice
That's all there is to it!
SOLID is a library for collision detection of three-dimensional objects undergoing rigid motion and deformation. SOLID is designed to be used in interactive 3D graphics applications, and is especially suited for collision detection of objects and worlds described in VRML. Some of its features are:
The library is written in standard C++ and relies heavily on the STL. Currently, it compiles under GNU g++ version 2.8.1 and up. The library has a standard C API and can be linked to both C and C++ applications. In order to link it to C applications you need the libstdc++ library.
In case you have a recent GNU developers environment installed, simply typing `make' in the root of the distribution directory will build the library, a sample client and documentation.
If you want to use another compiler, you should make the necessary changes to the `Make-config' file in the root directory. See the comments in this file for details.
The auxiliary C++ classes in `include/3D' for performing affine transformation in 3D have all their code inlined, so you do not need to link a library in order to use them.
Q: My compiler cannot figure out the templates used in the SOLID source! What's the matter?
A: Your compiler does not comply with the ISO standard for C++. Install the GNU g++ compiler version 2.8.1 or higher for your platform.
The commands for creating and destroying shapes are
DtShapeRef dtBox(DtScalar x, DtScalar y, DtScalar z); DtShapeRef dtCone(DtScalar radius, DtScalar height); DtShapeRef dtCylinder(DtScalar radius, DtScalar height); DtShapeRef dtSphere(DtScalar radius); DtShapeRef dtNewComplexShape(); void dtDeleteShape(DtShapeRef shape);
Shapes are referred to by values of DtShapeRef.
Currently, the type DtScalar is defined as double.
The command dtBox creates a rectangular parallelepiped centered
at the origin and aligned with the axes of the shape's local coordinate system.
The parameters specify its extent along the respective coordinate axes.
The commands dtCone and dtCylinder create respectively a
cone and a cylinder centered
at the origin and whose central axis is aligned with the Y-axis of the
local coordinate system.
The cone's apex is at y = height / 2.
The command dtSphere creates a sphere centered at the origin of
the local coordinate system.
Other shape types based on point data, such as polygon soups, simplicial
complexes, (compositions of) convex polyhedra, are created by the
dtNewComplexShape command.
For constructing complex shapes the following commands are used:
DtShapeRef dtNewComplexShape(); void dtEndComplexShape(); void dtBegin(DtPolyType type); void dtEnd(); void dtVertex(DtScalar x, DtScalar y, DtScalar z); void dtVertexBase(const void *base); void dtVertexIndex(DtIndex index); void dtVertexIndices(DtPolyType type, DtCount count, const DtIndex *indices); void dtVertexRange(DtPolyType type, DtIndex first, DtCount count);
A complex shape is composed of d-dimensional polytopes, where
d is at most 3.
A d-polytope can be a simplex (point, line segment, triangle,
tetrahedron), a convex polygon, or a convex polyhedron.
The type of d-polytope is specified by a value of
DtPolyType, defined as
typedef enum DtPolyType {
DT_SIMPLEX,
DT_POLYGON,
DT_POLYHEDRON
} DtPolyType;
A d-polytope is specified by enumerating its vertices. This can be done
in two ways. In the first way, the vertices are specified by value,
using the dtVertex command. The following example shows how the
faces of a pyramid are specified.
DtShapeRef pyramid = dtNewComplexShape(); dtBegin(DT_SIMPLEX); dtVertex(1.0, 0.0, 1.0); dtVertex(1.0, 0.0, -1.0); dtVertex(-1.0, 0.0, -1.0); dtVertex(-1.0, 0.0, 1.0); dtEnd(); dtBegin(DT_SIMPLEX); dtVertex(1.0, 0.0, 1.0); dtVertex(1.0, 0.0, -1.0); dtVertex(0.0, 1.27, 0.0); dtEnd(); ... dtEndComplexShape();
In the second method, the vertices are stored in an array, and are
referred to by indices.
For each complex shape, we can specify a single array.
A vertex array is specified by the command dtVertexBase, which
takes the address of the first element in the array, referred to as the base of
the array, as argument.
The command dtVertexIndex is used for
specifying vertices. See the following example:
DtScalar vertices[5 * 3] = {
1.0, 0.0, 1.0,
1.0, 0.0, -1.0,
-1.0, 0.0, -1.0,
-1.0, 0.0, 1.0,
0.0, 1.27, 0.0
};
DtShapeRef pyramid = dtNewComplexShape();
dtVertexBase(vertices);
dtBegin(DT_SIMPLEX);
dtVertexIndex(0);
dtVertexIndex(1);
dtVertexIndex(2);
dtVertexIndex(3);
dtEnd();
dtBegin(DT_SIMPLEX);
dtVertexIndex(0);
dtVertexIndex(1);
dtVertexIndex(4);
dtEnd();
...
dtEndComplexShape();
Alternatively, the indices can be placed into an array and specified
using the command dtVertexIndices, as in the following example:
DtScalar vertices[5 * 3] = {
1.0, 0.0, 1.0,
1.0, 0.0, -1.0,
-1.0, 0.0, -1.0,
-1.0, 0.0, 1.0,
0.0, 1.27, 0.0
};
DtIndex face0[4] = { 0, 1, 2, 3 };
DtIndex face1[3] = { 0, 1, 4 };
...
DtShapeRef pyramid = dtNewComplexShape();
dtVertexBase(vertices);
dtVertexIndices(DT_SIMPLEX, 4, face0);
dtVertexIndices(DT_SIMPLEX, 3, face1);
...
dtEndComplexShape();
Finally, a polytope can be specified from a range of vertices using the
command dtVertexRange.
The range is specified by the first index and the number of vertices.
In the following example a pyramid is constructed as a convex polyhedron,
which is the convex hull of the vertices in the array.
DtScalar vertices[5 * 3] = {
1.0, 0.0, 1.0,
1.0, 0.0, -1.0,
-1.0, 0.0, -1.0,
-1.0, 0.0, 1.0,
0.0, 1.27, 0.0
};
DtShapeRef pyramid = dtNewComplexShape();
dtVertexBase(vertices);
dtVertexRange(DT_POLYHEDRON, 0, 5);
dtEndComplexShape();
Note that the vertices of a simplex need not be affinely independent, and the vertices specifying a convex polyhedron need not be extreme vertices of the convex hull. However, in order to construct a proper convex polygon, the vertices should be approximately coplanar and specified in the order as they appear on the boundary.
An object is an instance of a shape. The commands for creating, moving and deleting objects are
void dtCreateObject(DtObjectRef object, DtShapeRef shape); void dtDeleteObject(DtObjectRef object); void dtSelectObject(DtObjectRef object); void dtLoadIdentity(); void dtLoadMatrixf(const float *m); void dtLoadMatrixd(const double *m); void dtMultMatrixf(const float *m); void dtMultMatrixd(const double *m); void dtTranslate(DtScalar x, DtScalar y, DtScalar z); void dtRotate(DtScalar x, DtScalar y, DtScalar z, DtScalar w); void dtScale(DtScalar x, DtScalar y, DtScalar z);
An object is referred to by a DtObjectRef, which is defined
as void *.
Any pointer type may be used to refer to an object. In general,
a pointer to a structure in the client application associated with the
collision object should be used.
An object's motion is specified by changing the placement of the local coordinate system of the shape. Initially, the local coordinate system of an object coincides with the world coordinate system.
The current object is the last created or selected object. The placement of the current object is changed, either by translations, rotations and nonuniform scalings, or by using an OpenGL 4x4 column-major matrix representing an affine transformation. Placements are specified absolute or relative to the previous placement. Rotations are specified using quaternions. Following example shows how a pair of objects are given absolute placements.
dtCreateObject(&object1, hammer); dtCreateObject(&object2, nail); dtSelectObject(&object1); dtLoadIdentity(); dtTranslate(0, 1, 1); dtRotate(0, 0, 1, 0); dtSelectObject(&object2); dtLoadIdentity(); dtTranslate(0, 1, 0); dtRotate(0, 0, 0, 1);
A quaternion is a four-dimensional vector. The set of quaternions of length one (points on a four-dimensional sphere) map to the set of orientations in three-dimensional space. Since in many applications an orientation defined by either a rotation axis and angle or by a triple of Euler angles is more convenient, the package includes code for quaternion operations. The code is found in a library of C++ classes for 3D affine transformations. The classes are found in the `include/3D' directory. All the code is inlined so you do not need to link a library in order to use the classes.
The quaternion class is found in the file `Quaternion.h'. The class has constructors and methods for setting a quaternion. For example
Quaternion q1(axis, angle); Quaternion q2(yaw, pitch, roll); ... q1.setRotation(axis, angle); q2.setEuler(yaw, pitch, roll); ... dtRotate(q1[X], q1[Y], q1[Z], q1[W]);
Also included is a static method Quaternion::random(), which
returns a random orientation.
Collision response in SOLID is handled by means of callback functions.
The callback functions have the type DtResponse defined by
typedef void (*DtResponse)( void *client_data, DtObjectRef object1, DtObjectRef object2, const DtCollData *coll_data)
Here, client_data is a pointer to an arbitrary structure in the
client application, object1 and object2 are colliding
objects, and coll_data is the response data computed by SOLID.
Currently, there are three types of response: simple,
smart and witnessed response. For simple response the value
of coll_data is NULL.
For smart and witnessed response coll_data points to the
following structure
typedef struct DtCollData {
DtVector point1;
DtVector point2;
DtVector normal;
} DtCollData;
An object of this type represents a pair of points of the respective
objects. The points point1 and point2 are given relative
to the local coordinate system of their respective objects
object1 and object2. The normal field is used for smart
response only.
For witnessed response, the points represent a witness of the collision.
As a result of this the global coordinates of the witness points are
equal.
For smart response, the points represent the closest point pair of the
objects at placements from the previous time frame. The
normal field contains the difference of the global
coordinates of the closest point pair, i.e., normal = Global(point1) - Global(point2).
We will discuss this type of response more thoroughly further on.
Response is defined as default response for all pairs of objects, as object response for all pairs containing a given object, or as pair response for a particular pair of objects. The commands for defining and undefining response are
void dtSetDefaultResponse(DtResponse response, DtResponseType type, void *client_data) void dtClearDefaultResponse() void dtSetObjectResponse(DtObjectRef obj, DtResponse response, DtResponseType type, void *client_data) void dtClearObjectResponse(DtObjectRef obj) void dtResetObjectResponse(DtObjectRef obj) void dtSetPairResponse(DtObjectRef obj1, DtObjectRef obj2, DtResponse response, DtResponseType type, void *client_data) void dtClearPairResponse(DtObjectRef obj1, DtObjectRef obj2) void dtResetPairResponse(DtObjectRef obj1, DtObjectRef obj2)
A response is defined by either a Set or a
Clear command.
The Clear command defines the response to be nil (no response).
Initially, the default response is nil and all pairs of objects have a default response. If for an object pair, one of the objects has an object response defined, then this response overrules the default response. A pair response overrules any object or default response. If for both objects there is an object response defined, then one of the responses is chosen. In this case, one of the responses may be forced to be chosen by defining it as a pair response.
A response is undefined, i.e., reset to a more general setting, by the
Reset commands.
The command dtResetPairResponse resets the response of a pair of
objects to an object response, if one is defined for an object in the pair,
or otherwise to the default response.
The command dtResetObjectResponse resets the responses of the object
pairs, for which no other object response or a pair response is defined, to
the default response.
Note that whenever an object is deleted, the object response and
all pair responses that are set for this object are reset automatically.
The DtResponseType is defined by
typedef enum DtResponseType {
DT_NO_RESPONSE,
DT_SIMPLE_RESPONSE,
DT_SMART_RESPONSE,
DT_WITNESSED_RESPONSE
} DtResponseType
Setting the response type to DT_NO_RESPONSE is equivalent to
clearing the response.
The response callback functions are executed for each colliding pair of objects by calling
int dtTest()
This function returns the number of callback functions that are executed.
For physics-based simulations it is often necessary to have a representation of the collision plane of a pair of colliding objects in order to compute the reaction forces. From a single configuration of two colliding objects it is hard to compute a collision plane, since there is no knowledge of how this configuration came about. Therefore, SOLID uses the configuration of the objects from the previous time frame for approximating the collision plane. If the objects were disjoint in the previous time frame, then the vector defined by the difference of the closest point pair of the objects is a good approximation of the collision plane's normal.
By selecting smart response for a pair of objects, the closest point
pair and the normal from the previous time frame are
computed.
The points point1 and point2 are given in local
coordinates and the normal relative to the
global basis and pointing away from object2.
In order to compute these values, the configuration of
objects must be stored in each time frame. This is done by calling
void dtProceed();
Note that in order to guarantee that a non-zero normal can be found,
the dtProceed command may only be called if all object pairs for
which a smart response is defined, are disjoint!
The common way of guarding this is by iteratively doing collision tests
and changing the placements until the objects are disjoint.
Note that it is possible and often necessary to call dtTest
multiple times before calling dtProceed.
SOLID handles deformations of complex shapes. In this context deformations are specified by changes of vertex positions. Complex shapes that are defined using a vertex array in the client application may be deformed by changing the array elements, or specifying a new array. SOLID is notified of a change of vertices by the command
void dtChangeVertexBase(DtShapeRef shape, const void *base);
When using convex polygons or convex polyhedra as shape components, the client should warrant that the vertex changes do not violate the convexity and topology (planar graph embedding) of a component!
Note that in order to use smart response for deformable shapes, the
change of vertices should be done by specifying a new array.
The vertex array of the previous time frame should be kept intact,
otherwise SOLID can not determine the configuration of objects of the
previous time frame.
This is best handled by applying a `double buffering' technique.
After a call to dtProceed, the new vertex positions are placed in the
free buffer of a pair of vertex buffers, and dtChangeVertexBase
is called using this buffer, after which the other buffer becomes the
free buffer.
In computer animations there is usually a lot of frame coherence (objects move smoothly). In these cases, caching and reusing earlier computations will yield a considerable performance improvement. The caching option of SOLID enables an incremental sort on the set of objects, in order to reduce the number of pairwise intersection tests. Moreover, when the cashing option is on, data from earlier intersection tests is stored and used for faster determination of the intersection status of a pair of objects. Caching is enabled and disabled by
void dtEnableCaching() void dtDisableCaching()
Caching may be enabled or disabled at any time during a simulation. This option is enabled by default.
Look out for my thesis describing the design and performance evaluation of SOLID, to appear in March, 1999.
Please send remarks, questions and bug reports to gino@win.tue.nl, or write to Gino van den Bergen, Department of Mathematics and Computing Science, Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands.
This document was generated on 24 January 1999 using the texi2html translator version 1.51a.