文件列表:

QuickCD_v1_00_VC6 (0, 2005-09-15)
QuickCD_v1_00_VC6\QuickCD_v1_00 (0, 2005-09-15)
QuickCD_v1_00_VC6\QuickCD_v1_00\DLL (0, 2003-05-24)
QuickCD_v1_00_VC6\QuickCD_v1_00\DLL\Debug (0, 2003-05-24)
QuickCD_v1_00_VC6\QuickCD_v1_00\DLL\QuickCD DLL.dsp (6028, 2000-08-28)
QuickCD_v1_00_VC6\QuickCD_v1_00\DLL\QuickCD DLL.plg (885, 2000-09-20)
QuickCD_v1_00_VC6\QuickCD_v1_00\DLL\QuickCD_DLL.def (445, 2000-09-20)
QuickCD_v1_00_VC6\QuickCD_v1_00\DLL\Release (0, 2003-05-24)
QuickCD_v1_00_VC6\QuickCD_v1_00\Docs (0, 2003-05-24)
QuickCD_v1_00_VC6\QuickCD_v1_00\lib (0, 2003-05-24)
QuickCD_v1_00_VC6\QuickCD_v1_00\lib\14dop.c (15372, 1998-12-29)
QuickCD_v1_00_VC6\QuickCD_v1_00\lib\18dop.c (16960, 1998-12-29)
QuickCD_v1_00_VC6\QuickCD_v1_00\lib\26dop.c (21279, 1998-12-29)
QuickCD_v1_00_VC6\QuickCD_v1_00\lib\6dop.c (10719, 1998-12-29)
QuickCD_v1_00_VC6\QuickCD_v1_00\lib\basic.h (5456, 1998-12-29)
QuickCD_v1_00_VC6\QuickCD_v1_00\lib\brep.c (41476, 2000-09-21)
QuickCD_v1_00_VC6\QuickCD_v1_00\lib\brep.h (1645, 1998-12-29)
QuickCD_v1_00_VC6\QuickCD_v1_00\lib\brep_header.h (1761, 1998-12-29)
QuickCD_v1_00_VC6\QuickCD_v1_00\lib\build_ftree.c (12750, 1998-12-29)
QuickCD_v1_00_VC6\QuickCD_v1_00\lib\build_tree.c (14482, 1998-12-29)
QuickCD_v1_00_VC6\QuickCD_v1_00\lib\Debug (0, 2003-05-24)
QuickCD_v1_00_VC6\QuickCD_v1_00\lib\defs.h (3192, 1998-12-29)
QuickCD_v1_00_VC6\QuickCD_v1_00\lib\erit.h (7634, 1998-12-29)
QuickCD_v1_00_VC6\QuickCD_v1_00\lib\front.c (10603, 1998-12-29)
QuickCD_v1_00_VC6\QuickCD_v1_00\lib\init.h (3367, 1998-12-29)
QuickCD_v1_00_VC6\QuickCD_v1_00\lib\io.c (5927, 1998-12-29)
QuickCD_v1_00_VC6\QuickCD_v1_00\lib\k-dop.h (9537, 1998-12-29)
QuickCD_v1_00_VC6\QuickCD_v1_00\lib\macros.h (1067, 1998-12-29)
QuickCD_v1_00_VC6\QuickCD_v1_00\lib\Makefile (1098, 1998-12-29)
QuickCD_v1_00_VC6\QuickCD_v1_00\lib\martin.h (6337, 1998-12-29)
QuickCD_v1_00_VC6\QuickCD_v1_00\lib\matrix.h (3714, 1998-12-29)
QuickCD_v1_00_VC6\QuickCD_v1_00\lib\project.h (12279, 1998-12-29)
QuickCD_v1_00_VC6\QuickCD_v1_00\lib\quickcd.c (28955, 2000-09-21)
QuickCD_v1_00_VC6\QuickCD_v1_00\lib\Release (0, 2003-05-24)
QuickCD_v1_00_VC6\QuickCD_v1_00\lib\search_tree.c (11762, 1998-12-29)
QuickCD_v1_00_VC6\QuickCD_v1_00\lib\structs.h (4812, 1998-12-29)
QuickCD_v1_00_VC6\QuickCD_v1_00\lib\tri_tri_2d.c (13127, 1998-12-29)
QuickCD_v1_00_VC6\QuickCD_v1_00\lib\tri_tri_3d.c (15388, 1998-12-29)
QuickCD_v1_00_VC6\QuickCD_v1_00\Makefile (209, 1998-12-29)
QuickCD_v1_00_VC6\QuickCD_v1_00\QuickCD.dsp (6016, 2000-08-02)
... ...

/*****************************************************************************/ /* */ /* Copyright (C) 19*** J.T. Klosowski */ /* */ /* */ /* C O P Y R I G H T */ /* */ /* This code is handed out for educational purposes only. It must not be */ /* used for or included in any commercial application. This restriction */ /* applies to all parts of this code! Please contact the author for any */ /* commercial licensing agreement. */ /* */ /* */ /* W A R N I N G */ /* */ /* This code comes for free, and neither the author nor his employer accept */ /* any responsibility, to the extent permitted by applicable law, to anyone */ /* for the consequences of using it or for whether it serves any particular */ /* purpose or works at all! By using the code you operate on your own risk! */ /* */ /*****************************************************************************/ /* */ /*****************************************************************************/ /* */ /* Written by: James T. Klosowski */ /* Date: 1995-19*** */ /* Modified: */ /* */ /* E-Mail: jklosow@ams.sunysb.edu */ /* Fax Mail: (+516) 632-8490 */ /* Voice Mail: (+516) 632-8366 */ /* Snail Mail: James T. Klosowski */ /* Department of Applied Mathematics */ /* State University of New York at Stony Brook */ /* Stony Brook, NY 11794-3600, USA */ /* */ /*****************************************************************************/ This README file is for Version 1.00 of QuickCD. Please do not distribute this code. QuickCD can be a obtained by contacting the authors through the QuickCD web page. Please direct any inquires about the collision detection library to the authors. http://cg.ams.sunysb.edu/~quickcd/QuickCD.html QuickCD is a general-purpose collision detection (CD) library, capable of performing fast and exact collision detection on highly complex models. No assumption is made about the structure of the input. QuickCD robustly handles unstructured inputs consisting of a ``soup'' of polygons. No adjacency information is needed; the models are only specified as a collection of triangles. Our method is based upon carefully constructing hierarchies of bounding volumes (BV-trees) to approximate the input models. Our choice of bounding volume is to use ``discrete orientation polytopes'', or k-dops, which are convex polytopes whose facets have normals from a given discrete set of k vectors. Our default bounding volume is an 18-dop, which contains (at most) 18 facets. Six of these facets are the axis-aligned bounding box planes and the remaining 12 are the planes which chop off as much of the 12 edges of the bounding box as possible. Other bounding volumes which QuickCD currently supports are 6-dops (or axis-aligned bounding boxes), 14-dops (6 bounding box planes plus 8 planes which chop off the 8 corners of the box), and 26-dops (6 bounding box planes plus 8 planes to chop off the corners plus 12 planes to chop off the 12 edges of the bounding box). Currently, QuickCD performs CD on one static environment and one moving (or flying) object. We can easily generalize this code to perform CD for a small number of flying objects using a naive all-pairs test. We could also implement the ``sweep and prune'' algorithm utilized within I-COLLIDE, which dynamically maintains three sorted lists of the bounding box dimensions of the moving objects along the x, y, and z axes. Only those pairs of objects whose bounding boxes overlap along all three axes would need to be checked for collision. For more information about our algorithms and data structures, please refer to: Efficient Collision Detection Using Bounding Volume Hierarchies of k-DOPs Klosowski, Held, Mitchell, Sowizral, Zikan IEEE Transactions on Visualization and Computer Graphics January--March 19***, pp 21--36, volume 4, number 1. Efficient Collision for Interactive 3D Graphics and Virtual Environments Klosowski, James T. Ph.D. Dissertation State University of New York at Stony Brook May 19*** Available on-line at: http://www.ams.sunysb.edu/~jklosow/publications/publications.html How to compile the library and example program: ----------------------------------------------- To compile the code, simply type ``make''. This will compile the QuickCD library (libquickcd) and also a sample program (s18) which uses the library. Please note that the sample program need only include ``quickcd.h'' and link to ``libquickcd.a'' in order to use the library. Please see the appropriate ``Makefile'' as an example of how we compile the code. As previously stated, our default bounding volume is an 18-dop. To alternate between these bounding volumes and the default, the Makefile will need to be modified. As the default, we have included the three lines: CFLAGS = $(OPTIMIZER) -DK18DOP -DK=18 NAME = s18 DOP_OBJ = 18dop.o If you would like to use 26-dops instead, comment out the three lines above, and uncomment the following lines: CFLAGS = $(OPTIMIZER) -DK26DOP -DK=26 NAME = s26 DOP_OBJ = 26dop.o Of course, you will need to perform a ``make clean'' to remove the old libquickcd.a and *.o files before doing another ``make''. In each case, the executable program has the name ``sXX'' where the XX is either 6, 14, 18, or 26 --- to indicate which bounding volumes are used for this executable. We have found the 18-dops to work the best on average; thus, we have made this bounding volume our default. After 18-dops, we would choose the 14-dops and then the 26-dops. All of these can perform CD queries much faster than the 6-dops (axis-aligned bounding boxes). Tuning the library for different applications: ---------------------------------------------- The bounding volume hierarchy built upon the environment is constructed so that each leaf of the tree has exactly one triangle in it. The hierarchy approximating the flying object does not build a complete tree, but rather has a threshold T, such that if the number of triangles associated with a node falls below T, then this node is a leaf. We have selected default values of T which work well in practice (as determined by a series of experiments on several datasets), however, the performance of the QuickCD library may be improved for some applications by trying to tune (increase or decrease) this threshold value. This value can be changed in the file: build_ftree.c The parameter name is: flyobj->bvtree_threshold For all of our experiments, we have simply used the default value, therefore, you may not find it necessary (or advantageous) to try to tune this threshold value. QuickCD Library Functions: -------------------------- Below, we highlight the routines within the QuickCD library. All of these routines have names which begin with ``QCD''. The example program ``sample.c'' illustrates how these routines are to be used. If you search through the sample.c file for ``QCD'' you can easily see where the QuickCD routines are being used. Please refer to README.sample to see information concerning the input format for the sample program. Note that this is only for the sample program and that the QuickCD library has two routines (QCD_Add_Env_Tri and QCD_Add_Fly_Tri) for adding triangles to the appropriate models. Thus, if your data is already stored somewhere, or is in a different format than the sample program format, you need only call the two routines to input the data into the QuickCD library. /*****************************************************************************/ void QCD_Print_Status_Message(int status); This routine determines if there was an error during the previous call to one of the QuickCD routines. If there was not an error, then this call will not do anything. However, if there was an error, the current implementation will print out an appropriate error message and then exit the program. This is rather harsh, but at the moment, this is how the routine has been coded. One example of this routine's use is: status = QCD_Collision_Detection(&num_contact_pairs, &contact_pairs, USE_FRONT, ALL_CONTACT); QCD_Print_Status_Message(status); Thus, if there was a problem during the CD check, we would know about it and (gracefully) exit the program. So far, this has not happened, but we would rather be safe than sorry. You should note that most of the QCD routines return an integer value, which indicates the current ``status'' of the library. This should be checked after each call to a QCD routine to avoid problems later. /*****************************************************************************/ int QCD_Initialize_Library(void); This routine MUST be successfully called prior to any of the other QuickCD library routines. This routine allocates memory for the environment and flying object. If there is not any memory available, then this error flag will be returned -- and will be noticed if the QCD_Print_Status_Message routine is called immediately afterwards. Regardless, if the library is not successfully initialized, then none of the other routines will work anyway. They all check prior to doing anything. /*****************************************************************************/ int QCD_Build_Environment_Hierarchy(int split_rule); int QCD_Build_Flying_Object_Hierarchy(int split_rule); These routines will build (respectively) the hierarchy of bounding volumes (BV-trees) on the (static) environment and the flying object. The parameter split_rule is an integer and can be either 0 (for the ``splatter'' method) or 1 (for the ``longside'' method), to indicate which type of splitting rule to use during the construction. Our default method is to use the ``splatter'' method, since this tends to produce very good query times without a great deal of preprocessing. We therefore recommend that you also use ``splatter'' when building the hierarchies. Within quickcd.h, there are some definitions to make things easier: #define QCD_SPLATTER 0 #define QCD_LONGSIDE 1 The possible errors which can occur within these routines are that: the library has not yet been successfully initialized (with QCD_Initialize_Library), no triangles have been added to the model yet, the hierarchy has already been built (you will have to explicitly call the free routine to build another hierarchy), the split rule is not one of the two listed above. In this case, the splatter rule is used by default and no error flag is returned. /*****************************************************************************/ int QCD_Add_Env_Tri(double v1[3], double v2[3], double v3[3], int index); int QCD_Add_Fly_Tri(double v1[3], double v2[3], double v3[3], int index); These routines add triangles to the environment and flying object models respectively. The parameters consist of the three vertices of the triangle, together with a (unique) index for the triangle. Once all of the triangles have been added to the models, you can build the hierarchies using the QCD_Build_***_Hierarchy routines (see above). If the library has not been initialized or it cannot store the new triangle due to a lack of memory, then an error flag will be returned by the routine. /*****************************************************************************/ int QCD_Set_Transformation_Matrix(double R[3][3], double T[3]); This routine sets the (absolute) placement of the moving (or flying) object with respect to its original position and orientation. To move the flying object from one location to the next, this routine must be called prior to QCD_Collision_Detection, to update the transformation matrix. The parameters R and T are the 3x3 rotation matrix and the translation vector. That is, the flying object will be moved by the following transformation p' = R * p + T, where p is a vertex of the flying object in its original position, and p' is the corresponding vertex of the flying object at its current position. If the library has not been initialized, then an error flag will be returned by this routine. /*****************************************************************************/ int QCD_Collision_Detection(int *num_contact_pairs, int ***contact_pairs, int use_front, int all_contacts); This is the core routine in the QuickCD library. The following routines should have been called prior to calling this one: QCD_Initialize_Library call once in beginning QCD_Add_Env_Tri call as many times as needed QCD_Add_FLY_Tri call as many times as needed QCD_Build_Environment_Hierarchy call after adding all triangles to model QCD_Build_Flying_Object_Hierarchy call after adding all triangles to model QCD_Set_Transformation_Matrix call prior to each call to this routine if you want to move the flying object The parameters are: num_contact_pairs will indicate how many triangle-triangle pairs came into contact during the CD check contact_pairs contains the indices of the pairs of triangles which came into contact. contact_pairs[0][i] -- the environment triangle index of the ith pair of colliding triangles contact_pairs[1][i] -- the flying object triangle index of the ith pair of colliding triangles use_front indicates whether to utilize the front to (potentially) speed up the CD queries 0 = do not use the front 1 = use the front all_contacts indicates whether to find all pairs of triangles which are in contact or only the first pair. Be warned that if you are using the front and specify that the first contact only should be found, the code will actually find a few more than just the first one...since the front needs to be completely updated at each step. 0 = find the first contact 1 = find all of the contacts Within quickcd.h, there are some definitions to make things easier: #define QCD_EVERY_CONTACT 1 #define QCD_FIRST_CONTACT 0 #define QCD_USE_FRONT 1 #define QCD_NO_FRONT 0 The sample program, again, will help illustrate how this routine is called. /*****************************************************************************/ int QCD_Read_Environment_Hierarchy(FILE *fptr); int QCD_Store_Environment_Hierarchy(FILE *fptr); Rather than building the environment hierarchy each time, we can build it once, store it in a binary file, and then read it in using these routines. The library must have been initialized prior to calling either of these routines. Of course, the environment hierarchy must have already been built before trying to store it, otherwise an error flag will be returned. Also, if you try to read the environment hierarchy after one has already been created, you will have to free that one first yourself and then read in the new one. /*****************************************************************************/ int QCD_Enable_Front(void); This routine will enable the front to be used during the collision detection queries to (potentially) speed up the queries. The library must have been initialized prior to calling this routine and the flying object hierarchy must have already been built. Calling this routine while the front is already enabled will result in nothing happening, except for the QCD_OKAY flag being sent back to the calling program. By default, the front is enabled when the library is initialized. The purpose for having this and the following routine are to allocate and deallocate the memory needed for the front. /*****************************************************************************/ int QCD_Disable_Front(void); This routine will disable the front from being used during the collision detection queries. This routine actually frees the memory allocated to the front. The front can be enabled again by using QCD_Enable_Front (see above). /*****************************************************************************/ int QCD_Access_CD_Statistics(long *tri_calls, long *bb_calls, long *overlap_calls, long *tumbled_nodes); This routine will access the number of primitive operations that were performed during the previous call to QCD_Collision_Detection. The four statistics which are tabulated are: tri_calls the number of triangle-triangle comparisons bb_calls the number of bounding box comparisons (used as a pretest to the triangle-triangle tests) overlap_calls the number of comparisons between two bounding volumes tumbled_nodes the number of nodes which were updated (i.e. tumbled) in the hierarchy built upon the moving, or flying, object Generally, this routine is used by the authors to gather relevant statistics as we test various parameters and other new ideas. It may not be of much interest to others. To utilize this routine, the code will have to be recompiled with the QCD_COLLECT_STATS flag defined on the CFLAGS line of the Makefile. /*****************************************************************************/ int QCD_Reset_Front(void); This routine will reset the front to the default (the root node of the environment hierarchy). We used this routine when we were timing our CD code in order to re-initialize the front after each flight. If you ... ...

近期下载者：

相关文件：

评论：[我要评论] [举报此文件]

收藏者：