1 /***
2  * libccd
3  * ---------------------------------
4  * Copyright (c)2010,2011 Daniel Fiser <danfis@danfis.cz>
5  *
6  *
7  *  This file is part of libccd.
8  *
9  *  Distributed under the OSI-approved BSD License (the "License");
10  *  see accompanying file BDS-LICENSE for details or see
11  *  <http://www.opensource.org/licenses/bsd-license.php>.
12  *
13  *  This software is distributed WITHOUT ANY WARRANTY; without even the
14  *  implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
15  *  See the License for more information.
16  */
17 
18 #ifndef __CCD_H__
19 #define __CCD_H__
20 
21 #include <ccd/precision.h>
22 
23 #include <ccd/vec3.h>
24 
25 #ifdef __cplusplus
26 extern "C" {
27 #endif /* __cplusplus */
28 
29 /**
30  * Type of *support* function that takes pointer to 3D object and direction
31  * and returns (via vec argument) furthest point from object in specified
32  * direction.
33  */
34 typedef void (*ccd_support_fn)(const void *obj, const ccd_vec3_t *dir,
35                                ccd_vec3_t *vec);
36 
37 /**
38  * Returns (via dir argument) first direction vector that will be used in
39  * initialization of algorithm.
40  */
41 typedef void (*ccd_first_dir_fn)(const void *obj1, const void *obj2,
42                                  ccd_vec3_t *dir);
43 
44 
45 /**
46  * Returns (via center argument) geometric center (some point near center)
47  * of given object.
48  */
49 typedef void (*ccd_center_fn)(const void *obj1, ccd_vec3_t *center);
50 
51 /**
52  * Main structure of CCD algorithm.
53  */
54 struct _ccd_t {
55     ccd_first_dir_fn first_dir; /*!< Returns initial direction where first
56                                   !< support point will be searched*/
57     ccd_support_fn support1; /*!< Function that returns support point of
58                                !< first object*/
59     ccd_support_fn support2; /*!< Function that returns support point of
60                                !< second object*/
61 
62     ccd_center_fn center1; /*!< Function that returns geometric center of
63                              !< first object*/
64     ccd_center_fn center2; /*!< Function that returns geometric center of
65                              !< second object*/
66 
67     unsigned long max_iterations; /*!< Maximal number of iterations*/
68     ccd_real_t epa_tolerance;
69     ccd_real_t mpr_tolerance; /*!< Boundary tolerance for MPR algorithm*/
70 };
71 typedef struct _ccd_t ccd_t;
72 
73 /**
74  * Default first direction.
75  */
76 void ccdFirstDirDefault(const void *o1, const void *o2, ccd_vec3_t *dir);
77 
78 #define CCD_INIT(ccd) \
79     do { \
80         (ccd)->first_dir = ccdFirstDirDefault; \
81         (ccd)->support1 = NULL; \
82         (ccd)->support2 = NULL; \
83         (ccd)->center1  = NULL; \
84         (ccd)->center2  = NULL; \
85         \
86         (ccd)->max_iterations = (unsigned long)-1; \
87         (ccd)->epa_tolerance = CCD_REAL(0.0001); \
88         (ccd)->mpr_tolerance = CCD_REAL(0.0001); \
89     } while(0)
90 
91 
92 /**
93  * Returns true if two given objects interest.
94  */
95 int ccdGJKIntersect(const void *obj1, const void *obj2, const ccd_t *ccd);
96 
97 /**
98  * This function computes separation vector of two objects. Separation
99  * vector is minimal translation of obj2 to get obj1 and obj2 speparated
100  * (without intersection).
101  * Returns 0 if obj1 and obj2 intersect and sep is filled with translation
102  * vector. If obj1 and obj2 don't intersect -1 is returned.
103  */
104 int ccdGJKSeparate(const void *obj1, const void *obj2, const ccd_t *ccd,
105                    ccd_vec3_t *sep);
106 
107 /**
108  * Computes penetration of obj2 into obj1.
109  * Depth of penetration, direction and position is returned. It means that
110  * if obj2 is translated by distance depth in direction dir objects will
111  * have touching contact, pos should be position in global coordinates
112  * where force should take a place.
113  *
114  * CCD+EPA algorithm is used.
115  *
116  * Returns 0 if obj1 and obj2 intersect and depth, dir and pos are filled
117  * if given non-NULL pointers.
118  * If obj1 and obj2 don't intersect -1 is returned.
119  */
120 int ccdGJKPenetration(const void *obj1, const void *obj2, const ccd_t *ccd,
121                       ccd_real_t *depth, ccd_vec3_t *dir, ccd_vec3_t *pos);
122 
123 
124 /**
125  * Returns true if two given objects intersect - MPR algorithm is used.
126  */
127 int ccdMPRIntersect(const void *obj1, const void *obj2, const ccd_t *ccd);
128 
129 /**
130  * Computes penetration of obj2 into obj1.
131  * Depth of penetration, direction and position is returned, i.e. if obj2
132  * is translated by computed depth in resulting direction obj1 and obj2
133  * would have touching contact. Position is point in global coordinates
134  * where force should be take a place.
135  *
136  * Minkowski Portal Refinement algorithm is used (MPR, a.k.a. XenoCollide,
137  * see Game Programming Gem 7).
138  *
139  * Returns 0 if obj1 and obj2 intersect, otherwise -1 is returned.
140  */
141 int ccdMPRPenetration(const void *obj1, const void *obj2, const ccd_t *ccd,
142                       ccd_real_t *depth, ccd_vec3_t *dir, ccd_vec3_t *pos);
143 
144 #ifdef __cplusplus
145 } /* extern "C" */
146 #endif /* __cplusplus */
147 
148 #endif /* __CCD_H__ */
149