1 | #ifndef GIM_TRI_COLLISION_H_INCLUDED |
---|
2 | #define GIM_TRI_COLLISION_H_INCLUDED |
---|
3 | |
---|
4 | /*! \file gim_tri_collision.h |
---|
5 | \author Francisco León Nájera |
---|
6 | */ |
---|
7 | /* |
---|
8 | ----------------------------------------------------------------------------- |
---|
9 | This source file is part of GIMPACT Library. |
---|
10 | |
---|
11 | For the latest info, see http://gimpact.sourceforge.net/ |
---|
12 | |
---|
13 | Copyright (c) 2006 Francisco Leon Najera. C.C. 80087371. |
---|
14 | email: projectileman@yahoo.com |
---|
15 | |
---|
16 | This library is free software; you can redistribute it and/or |
---|
17 | modify it under the terms of EITHER: |
---|
18 | (1) The GNU Lesser General Public License as published by the Free |
---|
19 | Software Foundation; either version 2.1 of the License, or (at |
---|
20 | your option) any later version. The text of the GNU Lesser |
---|
21 | General Public License is included with this library in the |
---|
22 | file GIMPACT-LICENSE-LGPL.TXT. |
---|
23 | (2) The BSD-style license that is included with this library in |
---|
24 | the file GIMPACT-LICENSE-BSD.TXT. |
---|
25 | |
---|
26 | This library is distributed in the hope that it will be useful, |
---|
27 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
---|
28 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the files |
---|
29 | GIMPACT-LICENSE-LGPL.TXT and GIMPACT-LICENSE-BSD.TXT for more details. |
---|
30 | |
---|
31 | ----------------------------------------------------------------------------- |
---|
32 | */ |
---|
33 | |
---|
34 | /*! \addtogroup GEOMETRIC_OPERATIONS |
---|
35 | */ |
---|
36 | //! @{ |
---|
37 | |
---|
38 | |
---|
39 | #define MAX_TRI_CLIPPING 8 |
---|
40 | |
---|
41 | //! Clips a polygon by a plane |
---|
42 | #define PLANE_CLIP_POLYGON(plane,polygon_points,polygon_point_count,clipped,clipped_count,max_clipped) \ |
---|
43 | { \ |
---|
44 | clipped_count = 0; \ |
---|
45 | GUINT _i, _vi, _prevclassif=32000, _classif; \ |
---|
46 | GREAL _d; \ |
---|
47 | for(_i=0;_i<=polygon_point_count;_i++) \ |
---|
48 | { \ |
---|
49 | _vi = _i%polygon_point_count; \ |
---|
50 | _d = DISTANCE_PLANE_POINT(plane,polygon_points[_vi]); \ |
---|
51 | _classif = _d>G_EPSILON ?1:0; \ |
---|
52 | if(_classif == 0) \ |
---|
53 | { \ |
---|
54 | if(_prevclassif==1) \ |
---|
55 | {\ |
---|
56 | if(clipped_count<max_clipped) \ |
---|
57 | {\ |
---|
58 | PLANE_CLIP_SEGMENT(polygon_points[_i-1],polygon_points[_vi],plane,clipped[clipped_count]); \ |
---|
59 | clipped_count++; \ |
---|
60 | } \ |
---|
61 | } \ |
---|
62 | if(clipped_count<max_clipped&&_i<polygon_point_count) \ |
---|
63 | { \ |
---|
64 | VEC_COPY(clipped[clipped_count],polygon_points[_vi]); \ |
---|
65 | clipped_count++; \ |
---|
66 | } \ |
---|
67 | } \ |
---|
68 | else \ |
---|
69 | { \ |
---|
70 | if(_prevclassif==0) \ |
---|
71 | { \ |
---|
72 | if(clipped_count<max_clipped) \ |
---|
73 | { \ |
---|
74 | PLANE_CLIP_SEGMENT(polygon_points[_i-1],polygon_points[_vi],plane,clipped[clipped_count]); \ |
---|
75 | clipped_count++; \ |
---|
76 | } \ |
---|
77 | } \ |
---|
78 | } \ |
---|
79 | _prevclassif = _classif; \ |
---|
80 | } \ |
---|
81 | }\ |
---|
82 | |
---|
83 | |
---|
84 | struct GIM_TRIPLANES_CACHE |
---|
85 | { |
---|
86 | /*! |
---|
87 | Planes are: |
---|
88 | 0 : Face normal plane (0,3) |
---|
89 | 1 : Edge 1 plane (4,7) |
---|
90 | 2 : Edge 2 plane (8,11) |
---|
91 | 3 : Edge 3 plane (12,15) |
---|
92 | */ |
---|
93 | vec4f m_planes[4]; |
---|
94 | }; |
---|
95 | //typedef struct _GIM_TRIPLANES_CACHE GIM_TRIPLANES_CACHE; |
---|
96 | |
---|
97 | |
---|
98 | struct GIM_TRIANGLE_DATA |
---|
99 | { |
---|
100 | vec3f m_vertices[3]; |
---|
101 | GIM_TRIPLANES_CACHE m_planes; |
---|
102 | }; |
---|
103 | //typedef struct _GIM_TRIANGLE_DATA GIM_TRIANGLE_DATA; |
---|
104 | |
---|
105 | //! tri_data is a GIM_TRIANGLE_DATA |
---|
106 | #define GIM_CALC_TRIANGLE_DATA_PLANES(tri_data)\ |
---|
107 | {\ |
---|
108 | TRIANGLE_PLANE((tri_data).m_vertices[0],(tri_data).m_vertices[1],(tri_data).m_vertices[2],(tri_data).m_planes.m_planes[0]);\ |
---|
109 | EDGE_PLANE((tri_data).m_vertices[0],(tri_data).m_vertices[1],((tri_data).m_planes.m_planes[0]),((tri_data).m_planes.m_planes[1]));\ |
---|
110 | EDGE_PLANE((tri_data).m_vertices[1],(tri_data).m_vertices[2],((tri_data).m_planes.m_planes[0]),((tri_data).m_planes.m_planes[2]));\ |
---|
111 | EDGE_PLANE((tri_data).m_vertices[2],(tri_data).m_vertices[0],((tri_data).m_planes.m_planes[0]), ((tri_data).m_planes.m_planes[3]));\ |
---|
112 | }\ |
---|
113 | |
---|
114 | //Structure for collision |
---|
115 | |
---|
116 | struct GIM_TRIANGLE_CONTACT_DATA |
---|
117 | { |
---|
118 | GREAL m_penetration_depth; |
---|
119 | GUINT m_point_count; |
---|
120 | vec3f m_separating_normal; |
---|
121 | vec3f m_points[MAX_TRI_CLIPPING]; |
---|
122 | }; |
---|
123 | //typedef struct _GIM_TRIANGLE_CONTACT_DATA GIM_TRIANGLE_CONTACT_DATA; |
---|
124 | |
---|
125 | struct GIM_TRIANGLE_RAY_CONTACT_DATA |
---|
126 | { |
---|
127 | GREAL u; |
---|
128 | GREAL v; |
---|
129 | GREAL tparam; |
---|
130 | GUINT m_face_id; |
---|
131 | vec3f m_point; |
---|
132 | vec3f m_normal; |
---|
133 | }; |
---|
134 | //typedef struct _GIM_TRIANGLE_RAY_CONTACT_DATA GIM_TRIANGLE_RAY_CONTACT_DATA; |
---|
135 | |
---|
136 | //! Fast Triangle Triangle overlapping test |
---|
137 | int gim_triangle_triangle_overlap( |
---|
138 | GIM_TRIANGLE_DATA *tri1, |
---|
139 | GIM_TRIANGLE_DATA *tri2); |
---|
140 | |
---|
141 | |
---|
142 | //! Fast but inacurate conservative Triangle Triangle overlapping test |
---|
143 | int gim_triangle_triangle_overlap_fast( |
---|
144 | GIM_TRIANGLE_DATA *tri1, |
---|
145 | GIM_TRIANGLE_DATA *tri2); |
---|
146 | |
---|
147 | |
---|
148 | //! Finds the contact points from a collision of two triangles |
---|
149 | /*! |
---|
150 | Returns the contact points, the penetration depth and the separating normal of the collision |
---|
151 | between two triangles. The normal is pointing toward triangle 1 from triangle 2 |
---|
152 | */ |
---|
153 | int gim_triangle_triangle_collision( |
---|
154 | GIM_TRIANGLE_DATA *tri1, |
---|
155 | GIM_TRIANGLE_DATA *tri2, |
---|
156 | GIM_TRIANGLE_CONTACT_DATA * contact_data); |
---|
157 | |
---|
158 | //Ray triangle |
---|
159 | |
---|
160 | |
---|
161 | /*! |
---|
162 | Solve the System for u,v parameters: |
---|
163 | |
---|
164 | u*axe1[i1] + v*axe2[i1] = vecproj[i1] |
---|
165 | u*axe1[i2] + v*axe2[i2] = vecproj[i2] |
---|
166 | |
---|
167 | sustitute: |
---|
168 | v = (vecproj[i2] - u*axe1[i2])/axe2[i2] |
---|
169 | |
---|
170 | then the first equation in terms of 'u': |
---|
171 | |
---|
172 | --> u*axe1[i1] + ((vecproj[i2] - u*axe1[i2])/axe2[i2])*axe2[i1] = vecproj[i1] |
---|
173 | |
---|
174 | --> u*axe1[i1] + vecproj[i2]*axe2[i1]/axe2[i2] - u*axe1[i2]*axe2[i1]/axe2[i2] = vecproj[i1] |
---|
175 | |
---|
176 | --> u*(axe1[i1] - axe1[i2]*axe2[i1]/axe2[i2]) = vecproj[i1] - vecproj[i2]*axe2[i1]/axe2[i2] |
---|
177 | |
---|
178 | --> u*((axe1[i1]*axe2[i2] - axe1[i2]*axe2[i1])/axe2[i2]) = (vecproj[i1]*axe2[i2] - vecproj[i2]*axe2[i1])/axe2[i2] |
---|
179 | |
---|
180 | --> u*(axe1[i1]*axe2[i2] - axe1[i2]*axe2[i1]) = vecproj[i1]*axe2[i2] - vecproj[i2]*axe2[i1] |
---|
181 | |
---|
182 | --> u = (vecproj[i1]*axe2[i2] - vecproj[i2]*axe2[i1]) /(axe1[i1]*axe2[i2] - axe1[i2]*axe2[i1]) |
---|
183 | |
---|
184 | if 0.0<= u+v <=1.0 then they are inside of triangle |
---|
185 | |
---|
186 | */ |
---|
187 | #define TRIANGLE_GET_UVPARAMETERS(point,vec1,vec2,vec3,tri_plane,u,v,outside)\ |
---|
188 | {\ |
---|
189 | vec3f _axe1, _axe2, _vecproj;\ |
---|
190 | VEC_DIFF(_axe1,vec2,vec1);\ |
---|
191 | VEC_DIFF(_axe2,vec3,vec1);\ |
---|
192 | VEC_DIFF(_vecproj,point,vec1);\ |
---|
193 | GUINT _i1,_i2;\ |
---|
194 | PLANE_MINOR_AXES(tri_plane, _i1, _i2);\ |
---|
195 | if(fabsf(_axe2[_i2])<G_EPSILON)\ |
---|
196 | {\ |
---|
197 | u = (_vecproj[_i2]*_axe2[_i1] - _vecproj[_i1]*_axe2[_i2]) /(_axe1[_i2]*_axe2[_i1] - _axe1[_i1]*_axe2[_i2]);\ |
---|
198 | v = (_vecproj[_i1] - u*_axe1[_i1])/_axe2[_i1];\ |
---|
199 | }\ |
---|
200 | else\ |
---|
201 | {\ |
---|
202 | u = (_vecproj[_i1]*_axe2[_i2] - _vecproj[_i2]*_axe2[_i1]) /(_axe1[_i1]*_axe2[_i2] - _axe1[_i2]*_axe2[_i1]);\ |
---|
203 | v = (_vecproj[_i2] - u*_axe1[_i2])/_axe2[_i2];\ |
---|
204 | }\ |
---|
205 | if(u<-G_EPSILON)\ |
---|
206 | {\ |
---|
207 | outside = 1;\ |
---|
208 | }\ |
---|
209 | else if(v<-G_EPSILON)\ |
---|
210 | {\ |
---|
211 | outside = 1;\ |
---|
212 | }\ |
---|
213 | else\ |
---|
214 | {\ |
---|
215 | float sumuv;\ |
---|
216 | sumuv = u+v;\ |
---|
217 | if(sumuv<-G_EPSILON)\ |
---|
218 | {\ |
---|
219 | outside = 1;\ |
---|
220 | }\ |
---|
221 | else if(sumuv-1.0f>G_EPSILON)\ |
---|
222 | {\ |
---|
223 | outside = 1;\ |
---|
224 | }\ |
---|
225 | else\ |
---|
226 | {\ |
---|
227 | outside = 0;\ |
---|
228 | }\ |
---|
229 | }\ |
---|
230 | }\ |
---|
231 | |
---|
232 | //! Finds the collision of a ray and a triangle. |
---|
233 | #define RAY_TRIANGLE_INTERSECTION(vOrigin,vDir,vec1,vec2,vec3,tri_plane,pout,u,v,tparam,tmax,does_intersect)\ |
---|
234 | {\ |
---|
235 | RAY_PLANE_COLLISION(tri_plane,vDir,vOrigin,pout,tparam,does_intersect);\ |
---|
236 | if(does_intersect != 0)\ |
---|
237 | {\ |
---|
238 | if(tparam<-G_EPSILON||tparam>tmax+G_EPSILON)\ |
---|
239 | {\ |
---|
240 | does_intersect = 0;\ |
---|
241 | }\ |
---|
242 | else\ |
---|
243 | {\ |
---|
244 | TRIANGLE_GET_UVPARAMETERS(pout,vec1,vec2,vec3,tri_plane,u,v,does_intersect);\ |
---|
245 | does_intersect = !does_intersect;\ |
---|
246 | }\ |
---|
247 | }\ |
---|
248 | }\ |
---|
249 | |
---|
250 | |
---|
251 | //! @} |
---|
252 | |
---|
253 | #endif // GIM_TRI_COLLISION_H_INCLUDED |
---|