Next: , Previous: Installation, Up: Top


4 The SOLID API

The SOLID API is a set of C functions. All API functions, also referred to as commands, use arguments that have primitive types, such as, integers, floats, and arrays of floats, or handles (type-mangled pointers) to internal objects of SOLID. The types DT_Scalar, DT_Vector and DT_Quaternion are simply typedefs:

     
     typedef float     DT_Scalar; 
     typedef DT_Scalar DT_Vector3[3]; 
     typedef DT_Scalar DT_Quaternion[4]; 
     

The MT C++ classes can be used for representing geometric data such as vectors and quaternions as they are implicitly casted to arrays of floats, however the use of these classes is not required for calling SOLID functions. SOLID API functions can be called using your own or third-party 3D geometry objects if you stick with the following rules:

4.1 Building Shapes

The commands for creating and destroying shapes are

     
     DT_ShapeHandle DT_NewBox(DT_Scalar x, DT_Scalar y, DT_Scalar z);
     DT_ShapeHandle DT_NewCone(DT_Scalar radius, DT_Scalar height);
     DT_ShapeHandle DT_NewCylinder(DT_Scalar radius, DT_Scalar height);
     DT_ShapeHandle DT_NewSphere(DT_Scalar radius);
     DT_ShapeHandle DT_NewPoint(const DT_Vector3 point); 
     DT_ShapeHandle DT_NewLineSegment(const DT_Vector3 source, 
                                      const DT_Vector3 target);
     
     DT_ShapeHandle DT_NewMinkowski(DT_ShapeHandle shape1, 
                                    DT_ShapeHandle shape2);
     DT_ShapeHandle DT_NewHull(DT_ShapeHandle shape1, 
                               DT_ShapeHandle shape2);
     
     void           DT_DeleteShape(DT_ShapeHandle shape);
     

Shapes are referred to by values of DT_ShapeHandle. The command DT_NewBox 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 DT_NewCone and DT_NewCylinder 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 DT_NewSphere creates a sphere centered at the origin of the local coordinate system. The command DT_NewPoint creates a single point. The command DT_NewLineSegment creates a single line segment in a similar way. Any pair of convex shapes (including general polytopes) can be combined to form compound shapes using the commands DT_NewMinkowski and DT_NewHull. The command DT_NewMinkowski `adds' the two shapes by sweeping one shape along the other. For instance, the Minkowski addition of a sphere and a line segment creates a hot dog. The command DT_NewHull creates a shape that represents the exact convex hull of the two shapes. Complex shape types composed of simple polytopes (polytope soups) are created using the DT_NewComplexShape command. Here, a simple polytope is a d-dimensional polytopes, where d is at most 3. A simple d-polytope can be a simplex (point, line segment, triangle, tetrahedron), a convex polygon, or a convex polyhedron. There are no topological constraints on the set of vertices of a polytope. In particular, the vertices of a polytope need not be affinely independent, and need not be extreme vertices of the convex hull. However, convex polytopes with many vertices may deteriorate the performance. Such complex polytopes should be created using the DT_NewPolytope command. Make sure that in that case, SOLID is built using Qhull. For constructing complex shapes the following commands are used:

     DT_VertexBaseHandle DT_NewVertexBase(const void *pointer, 
                                          DT_Size stride);
     void DT_DeleteVertexBase(DT_VertexBaseHandle vertexBase);	
     void DT_ChangeVertexBase(DT_VertexBaseHandle vertexBase, 
                              const void *pointer);
     
     DT_ShapeHandle DT_NewComplexShape(DT_VertexBaseHandle vertexBase);
     void           DT_EndComplexShape();
     
     DT_ShapeHandle DT_NewPolytope(DT_VertexBaseHandle vertexBase);
     void           DT_EndPolytope();
     
     void DT_Begin();
     void DT_End();
     
     void DT_Vertex(const DT_Vector3 vertex);
     void DT_VertexIndex(DT_Index index);
     
     void DT_VertexIndices(DT_Count count, const DT_Index *indices);
     void DT_VertexRange(DT_Index first, DT_Count count); 
     

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 DT_Vertex command. The following example shows how the faces of a pyramid are specified.

     
     DT_Vector3 float verts[] = { 
     		   {  1.0f,  0.0f,  1.0f },
     		   {  1.0f,  0.0f, -1.0f },
     		   { -1.0f,  0.0f, -1.0f }, 
     		   { -1.0f,  0.0f,  1.0f },
     		   {  0.0f, 1.27f,  0.0f }
     };
     
     DT_ShapeHandle pyramid = DT_NewComplexShape(NULL);
     
     DT_Begin();
     DT_Vertex(verts[0]); 
     DT_Vertex(verts[1]); 
     DT_Vertex(verts[2]); 
     DT_Vertex(verts[3]);
     DT_End();
     
     DT_Begin();
     DT_Vertex(verts[0]); 
     DT_Vertex(verts[1]); 
     DT_Vertex(verts[4]); 
     DT_End();
     
     ...
     
     DT_EndComplexShape();
     

Here, an argument of NULL in DT_NewComplexShape denotes that the complex shape does not use an external vertex array. In the second method, the vertices are referred to by indices. For each complex shape, we specify a single array of vertices. Vertex arrays are maintained by the client application and can be accessed directly by SOLID. Vertex arrays are accessed via vertex bases. The command DT_NewVertexBase creates a vertex base for the array given by the argument pointer. The client must maintain vertex data in single-precision floating-point format. The client is free to store vertex data using arbitrary spacing in-between the individual array items. The spacing is specified using the DT_Size stride parameter. For instance, the client maintains an array of vertices of the type:

        
     struct Vertex {
         float xyz[3];
         float uv[2];
         float normal[3];
     };
     
     struct Vertex verts[NUM_VERTICES];
     

When specifying a complex shape you can use this data as follows

     
     DT_VertexBaseHandle base = DT_NewVertexBase(verts[0].xyz, 
                                                 sizeof(struct Vertex));
     

A stride of zero denotes that the vertex coordinate data is packed in a separate array, thus

     
     DT_Vector3 verts[NUM_VERTICES];
     
     DT_VertexBaseHandle base = DT_NewVertexBase(verts[0], 0);
     

Each time the vertices are updated, or a new vertex base is assigned, to a complex shape, for instance, when using a deformable triangle mesh, the client needs to notify SOLID of a changed vertex array by calling DT_ChangeVertexBase. We discuss the use of this command further on. The handle to the vertex base is passed as argument to DT_NewComplexShape. The command DT_VertexIndex is used for specifying vertices. See the following example:

     
     DT_ShapeHandle pyramid = DT_NewComplexShape(base);
     
     DT_Begin();
     DT_VertexIndex(0); 
     DT_VertexIndex(1); 
     DT_VertexIndex(2); 
     DT_VertexIndex(3); 
     DT_End();
     
     DT_Begin();
     DT_VertexIndex(0); 
     DT_VertexIndex(1); 
     DT_VertexIndex(4); 
     DT_End();
     
     ...
     
     DT_EndComplexShape();
     

Alternatively, the indices can be placed into an array and specified using the command DT_VertexIndices, as in the following example:

     
     DT_Index face0[4] = { 0, 1, 2, 3 };
     DT_Index face1[3] = { 0, 1, 4 };
     
     ...
     
     DT_VertexIndices(4, face0);
     DT_VertexIndices(3, face1);
     

Finally, a polytope can be specified from a range of vertices using the command DT_VertexRange. 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.

     
     DT_ShapeHandle pyramid = DT_NewComplexShape(base);
     DT_VertexRange(0, 5);
     DT_EndComplexShape();
     

The same shape can be built using the DT_NewPolytope command:

     
     DT_ShapeHandle pyramid = DT_NewPolytope(base);
     DT_VertexRange(0, 5);
     DT_EndPolytope();
     

Note that within a DT_NewPolytope construction all the vertex array commands can be used to specify vertices. The commands DT_Begin and DT_End are ignored for polytopes. Convex polytopes constructed using the DT_NewPolytope command are preprocessed by SOLID in order to allow for faster testing, and should be used when the number of vertices is large.

4.2 Creating and Moving Objects

An object is an instance of a shape. The commands for creating, moving and deleting objects are

     
     DT_ObjectHandle DT_CreateObject(void *client_object, DT_ShapeHandle shape); 
     void            DT_DestroyObject(DT_ObjectHandle object);
     
     void DT_SetPosition(DT_ObjectHandle object, const DT_Vector3 position);
     void DT_SetOrientation(DT_ObjectHandle object, 
                            const DT_Quaternion orientation);
     void DT_SetScaling(DT_ObjectHandle object, const DT_Vector3 scaling);
     
     void DT_SetMatrixf(DT_ObjectHandle object, const float *m); 
     void DT_SetMatrixd(DT_ObjectHandle object, const double *m); 
     
     void DT_SetMargin(DT_ObjectHandle object, DT_Scalar margin);
     

An object is referred to by a DT_ObjectHandle. The first parameter void *client_object is a pointer to an arbitrary structure in the client application. This pointer is passed as parameter to the callback function in case of a collision, and can be used for collision handling. 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 placement of an object is changed, either by setting the position, orientation, and scaling, or by using an OpenGL 4x4 column-major matrix representing an affine transformation. Placements are specified relative to the world coordinate system. Rotations are specified using quaternions. The object's local coordinate system can be scaled non-uniformly by specifying a scale factor per coordinate axis. Following example shows how a pair of objects are given absolute placements.

     
     DT_ObjectHandle objectHandle = DT_CreateObject(&myObject, shapeHandle);
     
     float position = { 0.0f, 1.0f, 1.0f };
     float orientation = { 0.0f, 0.0f, 0.0f, 0.1f };
     float scaling = { 1.0f, 2.0f, 1.0f };
      
     DT_SetPosition(objectHandle, position);
     DT_SetOrientation(objectHandle, orientation);
     DT_SetScaling(objectHandle, scaling);
     

For scalings along axes that are not coordinate axes, such as shears, you should construct a 4x4 column-major matrix representation of the local coordinate system and use DT_SetMatrix to specify the object placement. The x-axis of the local coordinate system relative to the world coordinate system is the vector (m[0], m[1], m[2]), the y-axis is (m[4], m[5], m[6]), the z-axis is (m[8], m[9], m[10]), and the local origin is (m[12], m[13], m[14]). The elements m[3], m[7], m[11], and m[15] are ignored. These values are assumed to be 0, 0, 0, and 1, respectively. Thus, only affine transformations are allowed. By setting a positive margin using DT_SetMargin you can spherically expand an object. The actual collision object is the set of points whose distance to the transformed shape is at most the margin. For instance, a hot dog or capsule can be created using

     
     DT_Vector3 source = { 0.0f, 0.0f, 0.0f }
     DT_Vector3 target = { 0.0f, -1.5f, 0.0f }
     
     DT_ShapeHandle line = DT_NewLineSegment(source, target);
     
     DT_ObjectHandle object = DT_CreateObject(&myHotDog, line);
     DT_SetMargin(object, 0.3f);
     

This object is useful for navigating along walls and over terrains Positions, orientations, scalings, and margins may all be changed during the life time of an object.

4.2.1 Who's Afraid of Quaternions?

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 the mathematics toolkit (MT). The quaternion class is located in the file MT_Quaternion.h. The class has constructors and methods for setting a quaternion. For example

     
     MT_Quaternion q1(axis, angle);
     MT_Quaternion q2(yaw, pitch, roll);
     
     ...
     
     q1.setRotation(axis, angle);
     q2.setEuler(yaw, pitch, roll);
     
     ...
     
     DT_SetOrientation(objectHandle, q1);
     

Also included is a static method MT_Quaternion::random(), which returns a random orientation.

4.2.2 Proximity Queries

Objects can also be queried directly using the commands

     
     DT_Scalar DT_GetClosestPair(DT_ObjectHandle object1, DT_ObjectHandle object2,
                                 DT_Vector3 point1, DT_Vector3 point2);  
     
     DT_Bool   DT_GetCommonPoint(DT_ObjectHandle object1, DT_ObjectHandle object2,
                                 DT_Vector3 point);
     
     DT_Bool   DT_GetPenDepth(DT_ObjectHandle object1, DT_ObjectHandle object2,
                              DT_Vector3 point1, DT_Vector3 point2);  
     

The command DT_GetClosestPair returns the distance between object1 and object2, and a pair of closest points point1 and point2 given in world coordinates The command DT_GetCommonPoint returns a boolean that denotes whether the objects object1 and object2 intersect, and, in case of an intersection, returns a common point point in world coordinates. The command DT_GetPenDepth also returns a boolean that denotes whether the objects object1 and object2 intersect, and, in case of an intersection, returns a pair of witness points of the penetration depth point1 and point2 in world coordinates. The maximum relative error in the closest points and penetration depth computation can be set using

     
     void DT_SetAccuracy(DT_Scalar max_error);
     

The default for max_error is 1.0e-3. Larger errors result in better performance. Non-positive error tolerances are ignored. The maximum tolerance on relative errors due to rounding is set using

     
     void DT_SetTolerance(DT_Scalar tol_error);
     

This value is the estimated relative rounding error in complex computations and is used for determining whether a floating-point number should be regarded as zero or not. The default value for `tol_error' is the machine epsilon, which is FLT_EPSILON when floats are used, and DBL_EPSILON when double-precision floating-point numbers are used internally. Very large tolerances result in false collisions. Setting tol_error too small results in missed collisions. Non-positive error tolerances are ignored. Furthermore, objects can be queried to return data maintained internally. The world-axes aligned bounding box of an object is returned using

     
     void DT_GetBBox(DT_ObjectHandle object, DT_Vector3 min, DT_Vector3 max);
     

Here, min and max are the vertices of the box with respectively the least and greatest world coordinates. The local-to-world transformation of an object can be returned using

     
     void DT_GetMatrixf(DT_ObjectHandle object, float *m); 
     void DT_GetMatrixd(DT_ObjectHandle object, double *m); 
     

The arguments of these commands are again arrays of 16 floating-point numbers that represent a 4x4 column-major matrix as discussed above.

4.3 Scenes

For scenes with many objects the number of pairwise intersection queries can become quite large. To overcome this bottleneck, objects are maintained in scenes. The commands for construction and destroying scenes are:

     
     DT_SceneHandle DT_CreateScene(); 
     void           DT_DestroyScene(DT_SceneHandle scene);
     void           DT_AddObject(DT_SceneHandle scene, 
                                 DT_ObjectHandle object);
     void           DT_RemoveObject(DT_SceneHandle scene,
                                    DT_ObjectHandle object);
     

Objects can be shared by multiple scenes. Each scene tracks the changes of placement and deformations of its objects, and updates its cached data accordingly. In this way, global collision queries using DT_Test (see below) can be processed much faster.

4.4 Response Handling

Collision response in SOLID is handled by means of callback functions. The callback functions have the type DT_ResponseCallback defined by

     
     typedef DT_Bool (*DT_ResponseCallback)(void *client_data, 
                                            void *client_object1, 
                                            void *client_object2,
                                            const DT_CollData *coll_data);
     

Here, client_data is a pointer to an arbitrary structure in the client application, client_object1 and client_object2 are the pointers to structures in the client application specified in DT_CreateObject, and coll_data is the response data computed by SOLID. The Boolean value returned by a callback functions indicates whether further processing of callbacks is needed. If DT_FALSE or DT_CONTINUE is returned, then the remaining colliding object pairs are processed. If DT_TRUE or DT_DONE is returned, then the call to DT_Test is exited without further processing. We discuss the DT_Test further on. Currently, there are three types of response: simple, depth and witnessed response. For simple response the value of coll_data is NULL. For depth and witnessed response coll_data points to the following structure

     
     
     typedef struct DT_CollData {
         DT_Vector3 point1;
         DT_Vector3 point2;
         DT_Vector3 normal;
     } DT_CollData;
     

An object of this type represents a pair of points of the respective objects. The points point1 and point2 are given relative to the world coordinate system. The normal field is used for depth response only. For witnessed response, the points represent a witness of the collision. Both points are contained in the intersection of the colliding objects. Note that the witness points are not necessarily equal. For depth response, the normal represent the penetration depth vector. The penetration depth vector is the shortest vector over which one object needs to be translated in order to bring the two objects into touching contact. The point1 and point2 fields contain the witness points of the penetration depth, thus normal = point2 - point1. Response callbacks are managed in response tables. Response tables are defined independent of the scenes in which they are used. Multiple response tables can be used in one scene, and a response table can be shared among scenes. Responses are defined on (pairs of) response classes. Each response table maintains its set of response classes. A response table is created and destroyed using the commands

     
     DT_RespTableHandle DT_CreateRespTable(); 
     void               DT_DestroyRespTable(DT_RespTableHandle respTable); 
     

A response class for a response table is generated using

     
     DT_ResponseClass DT_GenResponseClass(DT_RespTableHandle respTable);
      

To each object for which a response is defined in the response table a response class needs to be assigned. This is done using

     
     void DT_SetResponseClass(DT_RespTableHandle respTable,
                              DT_ObjectHandle object,
                              DT_ResponseClass responseClass);
     
     

For each pair of objects multiple responses can be defined. A response is a callback together with its response type and client data. The DT_ResponseType is defined by

     
     typedef enum DT_ResponseType { 
         DT_NO_RESPONSE,
         DT_SIMPLE_RESPONSE, 
         DT_WITNESSED_RESPONSE   
         DT_DEPTH_RESPONSE,
     } DT_ResponseType;
     

Responses can be defined for all pairs of response classes...

     
     void DT_AddDefaultResponse(DT_RespTableHandle respTable,
                                DT_ResponseCallback response,
                                DT_ResponseType type,
                                void *client_data);
     
     void DT_RemoveDefaultResponse(DT_RespTableHandle respTable,
                                   DT_ResponseCallback response);
     

...per response class...

     
     void DT_AddClassResponse(DT_RespTableHandle respTable,
                              DT_ResponseClass responseClass,
                              DT_ResponseCallback response,
                              DT_ResponseType type,
                              void *client_data);
     
     void DT_RemoveClassResponse(DT_RespTableHandle respTable,
                                 DT_ResponseClass responseClass,
                                 DT_ResponseCallback response);
     

... and per pair of response classes...

     
     void DT_AddPairResponse(DT_RespTableHandle respTable,
                             DT_ResponseClass responseClass1,
                             DT_ResponseClass responseClass2, 
                             DT_ResponseCallback response,
                             DT_ResponseType type, 
                             void *client_data);
     
     void DT_RemovePairResponse(DT_RespTableHandle respTable,
                                DT_ResponseClass responseClass1,
                                DT_ResponseClass responseClass2,
                                DT_ResponseCallback response);
     

If for an object pair, one of the objects has a class object response defined, that needs to be overruled by a pair response, then you should remove the callback defined in the class response for the pair and add the pair response, thus

     
     DT_AddClassResponse(respTable, class1, classResponse, 
                         DT_SIMPLE_RESPONSE, client_data);
     
     DT_RemovePairResponse(respTable, class1, class2, classResponse);
     
     DT_AddPairResponse(respTable, class1, class2, pairResponse, 
                        DT_DEPTH_RESPONSE, client_data);
     

In the same way, a default response can be overruled by a class or pair response. The response callback functions are executed by calling

     
     DT_Count DT_Test(DT_SceneHandle scene, DT_RespTableHandle respTable);
     

This command calls for each colliding pair of objects the corresponding callback function until all pairs are processed or until a callback function returns DT_TRUE or DT_DONE. It returns the number of object pairs for which callback functions have been executed. Note: If the response classes of the objects in a callback differ, then client_object1 has a `lower' response class than client_object2. That is, the response class of client_object1 is generated before the response class of client_object2.

4.5 Deformable Models

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 DT_ChangeVertexBase(DT_VertexBaseHandle vertexBase, 
                              const void *pointer);
     

Note that polytopes constructed from a vertex base using DT_NewPolytope are not affected by a change of vertices.

4.6 Ray Cast

NOTE: This feature is currently implemented for spheres, boxes, triangles, and triangle meshes only. Also, margins are ignored for ray casts. The commands for performing ray casts are

     
     void *DT_RayCast(DT_SceneHandle scene, void *ignore_client,
                      const DT_Vector3 source, 
                      const DT_Vector3 target,
                      DT_Scalar max_param, 
                      DT_Scalar *param, DT_Vector3 normal);
     
     DT_Bool DT_ObjectRayCast(DT_ObjectHandle object,
                              const DT_Vector3 source, 
                              const DT_Vector3 target,
                              DT_Scalar max_param, 
                              DT_Scalar *param, DT_Vector3 normal); 
     

The ray is given by source, target, and max_param. It represents the line segment source + (target - source) * t, where t is a member of the interval [0, max_param]. So, if max_param is 1, then the ray is simply the line segment from source to target, whereas if max_param is equal to FLT_MAX, then the ray is `infinite'. DT_RayCast returns a pointer to the client object of an object in scene that is hit first by the ray, or NULL if no object is hit. DT_ObjectRayCast performs a ray cast on a single object and returns a Boolean indicating a hit. In case of a hit, param points to the t of the hit spot, and normal is a normal to the object's surface in world coordinates. The normal always points towards the source. An object can be made transparent for the ray cast by specifying the object's client object as ignore_client. This is useful if you need to ignore hits of the ray with the source object of the ray. For instance terrain following can be implemented by casting a ray down and setting the moving object at a distance above the spot. In this case, you are probably interested in hits with the terrain only, and do not need reports of hits with the moving object.