/******************************************************************************\ Copyright 1995 The University of North Carolina at Chapel Hill. All Rights Reserved. Permission to use, copy, modify and distribute this software and its documentation for educational, research and non-profit purposes, without fee, and without a written agreement is hereby granted, provided that the above copyright notice and the following three paragraphs appear in all copies. IN NO EVENT SHALL THE UNIVERSITY OF NORTH CAROLINA AT CHAPEL HILL BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUDING LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF NORTH CAROLINA HAVE BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. Permission to use, copy, modify and distribute this software and its documentation for educational, research and non-profit purposes, without fee, and without a written agreement is hereby granted, provided that the above copyright notice and the following three paragraphs appear in all copies. THE UNIVERSITY OF NORTH CAROLINA SPECIFICALLY DISCLAIM ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF NORTH CAROLINA HAS NO OBLIGATION S TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. The authors may be contacted via: US Mail: J. Cohen/M. Lin/D. Manocha/K. Ponamgi Department of Computer Science Sitterson Hall, CB #3175 University of N. Carolina Chapel Hill, NC 27599-3175 Phone: (919)962-1749 EMail: {cohenj,lin,manocha,ponamgi}@cs.unc.edu ***************************************************************************************\ I_COLLIDE USER'S MANUAL - Release 1.0.1 ----------------------- INTRODUCTION The I_COLLIDE collision detection library performs efficient and exact collision detection between convex polyhedral models. It uses a 2-level hierarchical approach to eliminate from consideration pairs of objects that are not close to each other. The lower level of the hierarchy involves exact collision detection between convex polyhedral models. Non-convex models may be decomposed into convex pieces for use with this library, but the library itself does not perform this decomposition. The basic steps involved in using this library are loading a data file containing the polyhedral models, creating instansiations of the models in the data file, choosing which pairs of objects should be tracked to determine closest distances and collisions, setting the positions of the objects, performing the collision test, and getting back reports of the test results. Based on these results and any other parameters of the simulation/interaction, the objects may be moved and the collisions tested again, etc. COMMAND REFERENCE #include int col_open(int max_polytopes, char *filename, double scale, int *num_polytopes); int col_instance_polytope(char *lib_object, int *id); int col_instance_polytope_by_num(int poly_num, int *id); int col_use_cuboid(int id); int col_use_dynamic_bounding_box(int id); int col_enable_nbody(); int col_disable_nbody(); int col_activate_pair(int id1, int id2); int col_activate_full(int id); int col_activate_all(); int col_deactivate_pair(int id1, int id2); int col_deactivate_full(int id); int col_deactivate_all(); int col_set_transform(int id, col_Mat4 matrix); int col_test(); int col_report_collision_pair(int id1, int id2, col_Report *report); int col_report_collision_full(int id, col_Report *report, int report_size); int col_report_collision_all(col_Report *report, int report_size); int col_report_distance_pair(int id1, int id2, col_DistReport *report); int col_report_distance_full(int id, col_DistReport *report, int report_size); int col_report_distance_all(col_DistReport *report, int report_size); int col_calc_cuboid(int poly_id, double *box_center, double *box_radius); INITIALIZATION At initialization time, call col_open() to start up the collision detection library and load the polytope data file. You pass in the name of the polytope data file to load, a scaling factor (1.0 if the objects are already properly scaled in your data file), and a maximum number of polytopes that you will instance. For instance, your data file may contain polytopes that are the convex pieces of a desk and a chair. You might want max_polytopes to be large enough to instance 2 desks and to chairs. Passing -1 for max_polytopes indicates that you intend to instance each object in the data file no more than once. The number of polytopes in the data file is returned in num_polytopes. (see the DATA FILE FORMAT section for details about the data files) By default, the collision library uses an nbody pruning algorithm based on bounding boxes to reduce the number of pairwise collision tests needed during calls to col_test(). If for some reason you want to track distances between all objects regardless of their proximity to one another, you can call col_disable_nbody() to achieve that behavior. INSTANCING OBJECTS After calling col_open(), which loads the data file, you need to instance some polytopes from the file. You can use col_instance_library_polytope() to instance a particular named polytope, or col_instance_library_polytope_by_num() to instance a polytope by number (the number is the order of the polytope in the data file, from 0 to the number of objects in the data file-1). For each polytope you instance, you can choose to use fixed sized bounding cubes or dynamically resized bounding boxes for a bounding box. The fixed-sized boxes may be more efficient for objects that move a lot, while the dynamic boxes fit tighter. The dynamic boxes are the default. ACTIVE PAIRS For an environment with n instanced objects, there are n^2 pairwise combinations of these objects. You may decide that some of these n^2 interactions are interesting, while others are to be ignored. When the objects are first instanciated, all n^2 pairs of objects are "deactivated." They must be "activated" to cause the collision library to track their distances and collisions. Their activation state is maintained until you change it at any later time. To activate a particular pair of objects, pass the ids of the objects to the col_activate_pair() function. Similarly, you can deactivate a pair of objects by calling col_deactivate pair. As a utility, the library also provides routines to activate/deactivate one object with all other objects (called col_activate/deactive_full for lack of a better name) and also routines to activate/deactivate all pairs of objects. If you have decomposed non-convex objects into convex pieces, you should be sure to leave the pairs that are part of the same object deactivated. In a session with few moving objects, you probably want to activate only the pairs containing at least one moving object as a member. MOVING OBJECTS Each object's position and orientation (and possibly scale) is represented by a 4x4 transformation matrix. Any vertex of the object is considered as a column vector, and this column vector is premultiplied by the transformation matrix to determine the vertex's position in world coordinates. If an object moves between the previous time step and the current time step, you call col_set_transform() to update the object's transformation matrix. PERFORMING THE COLLISION TEST When all the objects' transformations have been modified as necessary and all the object pairs are properly activated/deactivated, call col_test() to perform the closest feature tracking and collision testing for the current time step. GETTING REPORTS After calling col_test(), you need to call report functions to get the results of the test. Calling col_report_all() will tell you all the pairs of objects colliding at this time step and also the most recent pair of closest features on these objects (a feature is a vertex, edge, or face). Once the objects are colliding, we no longer know much about which pair of features are the "closest," so we report the pair of features that was closest in the most recent non-colliding frame. You pass an array into the report function and also the number of elements in the array, and the report function fills in as many of the collisions as possible and returns the total number of collisions (if your array isn't big enough, you won't get all the collisions, but you can always call the function again with a larger array). For completeness, you can also inquire about the collision status of a particular pair of polytopes or about the status of a single polytope with respect to all others. There are other report functions for reporting the distances and closest feature pairs of objects. col_report_distance_all() will return all known information about inter-object distances and closest feature pairs. This information is unknown if the an object pair is not activated or if the an object pair has non-overlapping bounding boxes (assuming the nbody bounding box algorithm is enabled as it is by default). Also for completeness, you can inquire about particular pairs, etc. ADVANCED USE Some applications may need to access internal structures of the collision library to perform certain tasks. We try not to make this impossible, but we distinguish between what we consider the internals from the externals by using the col_ prefix for structures and functions meant to be used by applications and the __col_ prefix for internal structures that should be accessed only if you "really think you know what you're doing." The nbody application included with the library shows how to access the geometry of the polytope structures to create display lists for graphics and to calculate the volume of a polytope. COMPILE-TIME OPTIONS The default settings of the compile-time options, located in the options.h, should suffice for most users, but modifying them may be useful on occasion. options.h allows you to set COL_CUBOID_BUFFER_PERCENT and COL_DYNAMIC_BOX_BUFFER_PERCENT to affect the size of the bounding boxes placed around the objects. The percent you choose is a percent of the tightest box radius that is added on to get the final box radius for each object. This allows the tracking of distances and closest features to begin when the objects are farther apart (i.e. before they're about to collide). You must #define _either_ COL_SPARSE_MATRIX _or_ COL_DENSE_MATRIX to determine the representation used for the n^2 pairs of polytopes. Choosing COL_DENSE_MATRIX for applications that are likely to activate all pairs for collision detection may use slightly less space then COL_SPARSE_MATRIX and allow for faster initialization. COL_SPARSE_MATRIX is the default setting because we expect that most applications will not have all the objects moving freely. Setting COL_COLLIDING_DISTANCE to a value greater than the default setting of 0.0 will cause I_COLLIDE to consider objects of distance less than or equal to COL_COLLIDING_DISTANCE to be colliding. These objects will be included in collision reports. Choose COL_GLOBAL_SORT or COL_LOCAL_SORT depending on how many of your objects move every frame. If a large percentage of the objects move every frame, COL_GLOBAL_SORT should be used, and will sort in linear time for successive frames with lots of object coherence. If only a small percentage of the objects move, choosing COL_LOCAL_SORT will enable the sorting of object bounding boxes to take time linear with respect to the number of moving objects. DATA FILE FORMAT The data file contains some number of convex polytopes (convex closed polyhedra). It is assumed that the faces of the polytopes are convex and planar, with the vertices ordered counter-clockwise when viewed from the outside of the object. Each polhedron definition should look like this: polyhedron ... * ... * Here's a sample data file: polyhedron pyramid1 sw0 0 0 0 se0 5 0 0 ne0 5 3 0 nw0 0 3 0 sw1 0 0 1 se1 5 0 1 ne1 5 3 1 nw1 0 3 1 * bottom sw0 nw0 ne0 se0 top sw1 se1 ne1 nw1 south sw0 se0 se1 sw1 north ne1 ne0 nw0 nw1 east se0 ne0 ne1 se1 west sw0 sw1 nw1 nw0 * polyhedron pyramid2 b1 +1 +1 0 b2 -1 +1 0 b3 -1 -1 0 b4 +1 -1 0 a 0 0 +5 * base b4 b3 b2 b1 - b1 b2 a - b2 b3 a - b3 b4 a - b4 b1 a * The word "polyhedron" is a key word used to mark the beginning of a new polyhedron, and the "*" symbol seperates the two main sections of a polyhedron definition. A polyhedron starts with "polyhedron ". This is followed by a list of named vertices and their 3D coordinates. A "*" marks the end of the vertex list and the beginning of the face list. Each face has a name followed by a list of vertices (counter-clockwise order). If you don't want to bother naming your faces, using "-" for the name causes some names to be generated internally. Naturally, you must name the vertices so you can refer to them in your face list. Blank lines are allowed between polyhedron definitions, but not within them. There isn't any comment symbol, so choose your names well. FOR MORE INFORMATION The functions are described individually in the collision.h header file. Also see the nbody demo application for examples of use. (and there's always "ask the authors" if you're really stuck).