1 | // |
---|
2 | // Lol Engine |
---|
3 | // |
---|
4 | // Copyright: (c) 2010-2013 Sam Hocevar <sam@hocevar.net> |
---|
5 | // (c) 2010-2013 Benjamin "Touky" Huet <huet.benjamin@gmail.com> |
---|
6 | // This program is free software; you can redistribute it and/or |
---|
7 | // modify it under the terms of the Do What The Fuck You Want To |
---|
8 | // Public License, Version 2, as published by Sam Hocevar. See |
---|
9 | // http://www.wtfpl.net/ for more details. |
---|
10 | // |
---|
11 | |
---|
12 | #if defined HAVE_CONFIG_H |
---|
13 | # include "config.h" |
---|
14 | #endif |
---|
15 | |
---|
16 | #if defined _XBOX |
---|
17 | # define _USE_MATH_DEFINES /* for M_PI */ |
---|
18 | # include <xtl.h> |
---|
19 | # undef near /* Fuck Microsoft */ |
---|
20 | # undef far /* Fuck Microsoft again */ |
---|
21 | #elif defined _WIN32 |
---|
22 | # define _USE_MATH_DEFINES /* for M_PI */ |
---|
23 | # define WIN32_LEAN_AND_MEAN |
---|
24 | # include <windows.h> |
---|
25 | # undef near /* Fuck Microsoft */ |
---|
26 | # undef far /* Fuck Microsoft again */ |
---|
27 | #endif |
---|
28 | |
---|
29 | #include <cstdlib> /* free() */ |
---|
30 | #include <cstring> /* strdup() */ |
---|
31 | |
---|
32 | #include <ostream> /* std::ostream */ |
---|
33 | |
---|
34 | #include "core.h" |
---|
35 | |
---|
36 | using namespace std; |
---|
37 | |
---|
38 | namespace lol |
---|
39 | { |
---|
40 | //Projects Point on Plane : Normal must be given normalized. returns point on plane. |
---|
41 | vec3 ProjPointOnPlane(vec3 const &point, vec3 const &planeP, vec3 const &planeN) |
---|
42 | { |
---|
43 | vec3 o2p = point - planeP; |
---|
44 | float d = -dot(o2p, planeN); |
---|
45 | return point + d * planeN; |
---|
46 | } |
---|
47 | |
---|
48 | //gets the dist from a Point to a Plane : Normal must be given normalized. returns distance. |
---|
49 | float PointDistToPlane(vec3 const &point, vec3 const &planeP, vec3 const &planeN) |
---|
50 | { |
---|
51 | vec3 o2p = point - planeP; |
---|
52 | return abs(dot(o2p, planeN)); |
---|
53 | } |
---|
54 | |
---|
55 | // Line/triangle : sets vIsec as the intersection point & return true if ok. |
---|
56 | bool RayIsectTriangle(vec3 const &rayP, vec3 const &rayD, |
---|
57 | vec3 const &triV0, vec3 const &triV1, vec3 const &triV2, |
---|
58 | vec3 &vIsec) |
---|
59 | { |
---|
60 | vec3 v01, v02, h, v0P, q; |
---|
61 | float a, f, triU, triV; |
---|
62 | |
---|
63 | // |
---|
64 | v01 = triV1 - triV0; |
---|
65 | v02 = triV2 - triV0; |
---|
66 | |
---|
67 | h = cross(rayD, v02); |
---|
68 | a = dot(v01, h); |
---|
69 | |
---|
70 | //rayDir is coplanar to the triangle, exit. |
---|
71 | if (a > -CSG_EPSILON && a < CSG_EPSILON) |
---|
72 | return false; |
---|
73 | |
---|
74 | f = 1 / a; |
---|
75 | v0P = rayP - triV0; |
---|
76 | triU = f * (dot(v0P, h)); |
---|
77 | |
---|
78 | //point is supposed to have an U on the segment v01 |
---|
79 | if (triU < -CSG_EPSILON || triU > 1.0) |
---|
80 | return false; |
---|
81 | |
---|
82 | q = cross(v0P, v01); |
---|
83 | triV = f * dot(rayD, q); |
---|
84 | |
---|
85 | //point is not in the triangle |
---|
86 | if (triV < -CSG_EPSILON || triU + triV > 1.0) |
---|
87 | return false; |
---|
88 | |
---|
89 | // at this stage we can compute t to find out where |
---|
90 | // the intersection point is on the line |
---|
91 | float t = f * dot(v02, q); |
---|
92 | |
---|
93 | if (t > CSG_EPSILON) // ray intersection |
---|
94 | { |
---|
95 | vIsec = triV0 + v01 * triU + v02 * triV; |
---|
96 | return true; |
---|
97 | } |
---|
98 | else // this means that there is a line intersection |
---|
99 | // but not a ray intersection |
---|
100 | return false; |
---|
101 | } |
---|
102 | |
---|
103 | // Triangle/Triangle |
---|
104 | bool TriangleIsectTriangle(vec3 const &v00, vec3 const &v01, vec3 const &v02, //triangle 0 |
---|
105 | vec3 const &v10, vec3 const &v11, vec3 const &v12, //triangle 1 |
---|
106 | vec3 &iP00, vec3 &iP10) //triangle intersection, iPx means gives the actual intersection points. |
---|
107 | { |
---|
108 | vec3 isec[2] = { vec3(0, 0, 0), vec3(0, 0, 0) }; |
---|
109 | vec3 triV[6] = { v00, v01, v02, |
---|
110 | v10, v11, v12 }; |
---|
111 | vec3 triD[6] = { v01 - v00, v02 - v01, v00 - v02, |
---|
112 | v11 - v10, v12 - v11, v10 - v12 }; |
---|
113 | int isecIdx = 0; |
---|
114 | vec3 vIsec(0); |
---|
115 | |
---|
116 | //Check the normal before doing any other calculations |
---|
117 | vec3 plane_norm[2] = { cross(normalize(triD[0]), normalize(triD[1])), |
---|
118 | cross(normalize(triD[3]), normalize(triD[4])) }; |
---|
119 | if (abs(dot(plane_norm[0], plane_norm[1])) == 1.0f) |
---|
120 | return false; |
---|
121 | |
---|
122 | #if 0 |
---|
123 | //Precheck to verify if two point of one of the tri-A are on tri-B, and vice versa. |
---|
124 | int zero_dist[2] = { 0, 0 }; |
---|
125 | for (int i = 0; i < 3; i++) |
---|
126 | { |
---|
127 | if (PointDistToPlane(triV[i], triV[3], plane_norm[1]) < CSG_EPSILON) |
---|
128 | zero_dist[0]++; |
---|
129 | if (PointDistToPlane(triV[i + 3], triV[0], plane_norm[0]) < CSG_EPSILON) |
---|
130 | zero_dist[1]++; |
---|
131 | } |
---|
132 | |
---|
133 | if (zero_dist[0] >= 2 || zero_dist[0] >= 2) |
---|
134 | return false; |
---|
135 | #endif |
---|
136 | |
---|
137 | //We first need to find two points intersecting, no matter on which triangle. |
---|
138 | for (int i = 0; i < 2 && isecIdx < 2; i++) |
---|
139 | { |
---|
140 | int found_isec = -1; |
---|
141 | for (int j = 0; j < 3 && isecIdx < 2; j++) |
---|
142 | { |
---|
143 | int pIdx = j + i * 3; |
---|
144 | int tIdx = (1 - i) * 3; |
---|
145 | if (RayIsectTriangle(triV[pIdx], triD[pIdx], |
---|
146 | triV[tIdx + 0], triV[tIdx + 1], triV[tIdx + 2], |
---|
147 | isec[isecIdx])) |
---|
148 | { |
---|
149 | #if 1 //if the point is near one the given entry, consider it as being the same point. |
---|
150 | for (int k = 0; k < 6; k++) |
---|
151 | { |
---|
152 | if (length(isec[isecIdx] - triV[k]) < CSG_EPSILON) |
---|
153 | { |
---|
154 | isec[isecIdx] = triV[k]; |
---|
155 | break; |
---|
156 | } |
---|
157 | } |
---|
158 | #endif |
---|
159 | |
---|
160 | //Automatic pass on the first intersection |
---|
161 | if (isecIdx == 0 || |
---|
162 | //If we have already found an intersection, pass if it's on this triangle. |
---|
163 | /*found_isec == i ||*/ |
---|
164 | //if it's the second intersection, we need it to be different from the first one. |
---|
165 | (isecIdx == 1 && length(isec[0] - isec[1]) > CSG_EPSILON)) |
---|
166 | { |
---|
167 | found_isec = i; |
---|
168 | isecIdx++; |
---|
169 | } |
---|
170 | } |
---|
171 | } |
---|
172 | } |
---|
173 | |
---|
174 | if (isecIdx >= 2) |
---|
175 | { |
---|
176 | iP00 = isec[0]; |
---|
177 | iP10 = isec[1]; |
---|
178 | return true; |
---|
179 | } |
---|
180 | return false; |
---|
181 | } |
---|
182 | |
---|
183 | //Ray/Line : returns one of the RAY_ISECT_* defines. |
---|
184 | int RayIsectRay(vec3 const &rayP00, vec3 const &rayP01, |
---|
185 | vec3 const &rayP10, vec3 const &rayP11, |
---|
186 | vec3 &vIsec) |
---|
187 | { |
---|
188 | vec3 rayD0 = rayP01 - rayP00; |
---|
189 | float rayS0 = length(rayD0); |
---|
190 | vec3 rayD0N = normalize(rayD0); |
---|
191 | |
---|
192 | vec3 rayD1 = rayP11 - rayP10; |
---|
193 | float rayS1 = length(rayD1); |
---|
194 | vec3 rayD1N = normalize(rayD1); |
---|
195 | |
---|
196 | vec3 rayP0P1 = rayP10 - rayP00; |
---|
197 | vec3 c01 = cross(rayD0N, rayD1N); |
---|
198 | float crs01S = length(c01); |
---|
199 | |
---|
200 | if (crs01S > -CSG_EPSILON && crs01S < CSG_EPSILON) |
---|
201 | return 0; |
---|
202 | |
---|
203 | mat3 m0 = mat3(rayP0P1, rayD1N, c01); |
---|
204 | float t0 = determinant(m0) / (crs01S * crs01S); |
---|
205 | vec3 isec0 = rayP00 + rayD0N * t0; |
---|
206 | |
---|
207 | mat3 m1 = mat3(rayP0P1, rayD0N, c01); |
---|
208 | float t1 = determinant(m1) / (crs01S * crs01S); |
---|
209 | vec3 isec1 = rayP10 + rayD1N * t1; |
---|
210 | |
---|
211 | if (sqlength(isec0 - isec1) < CSG_EPSILON) //ray intersection |
---|
212 | { |
---|
213 | vIsec = (isec0 + isec0) * .5f; |
---|
214 | float d0 = (length(rayP01 - vIsec) < CSG_EPSILON || length(rayP00 - vIsec) < CSG_EPSILON)? |
---|
215 | (-1.0f): |
---|
216 | (dot(rayP00 - vIsec, rayP01 - vIsec)); |
---|
217 | float d1 = (length(rayP10 - vIsec) < CSG_EPSILON || length(rayP11 - vIsec) < CSG_EPSILON)? |
---|
218 | (-1.0f): |
---|
219 | (dot(rayP10 - vIsec, rayP11 - vIsec)); |
---|
220 | |
---|
221 | //if the dot is negative, your point is in each ray, so say OK. |
---|
222 | if (d0 < .0f && d1 < .0f) |
---|
223 | return RAY_ISECT_ALL; |
---|
224 | if (d0 < .0f) |
---|
225 | return RAY_ISECT_P0; |
---|
226 | if (d1 < .0f) |
---|
227 | return RAY_ISECT_P1; |
---|
228 | return RAY_ISECT_NONE; |
---|
229 | } |
---|
230 | else // this means that there is a line intersection |
---|
231 | // but not a ray intersection |
---|
232 | return RAY_ISECT_NOTHING; |
---|
233 | } |
---|
234 | |
---|
235 | //Ray/Plane : Normal must be given normalized. returns 1 if succeeded. |
---|
236 | bool RayIsectPlane(vec3 const &rayP0, vec3 const &rayP1, |
---|
237 | vec3 const &planeP, vec3 const &planeN, |
---|
238 | vec3 &vIsec, bool test_line_only) |
---|
239 | { |
---|
240 | vec3 ray_dir = rayP1 - rayP0; |
---|
241 | float d = dot(ray_dir, planeN); |
---|
242 | |
---|
243 | if (d > -CSG_EPSILON && d < CSG_EPSILON) |
---|
244 | return false; |
---|
245 | |
---|
246 | vec3 o2p1 = rayP1 - planeP; |
---|
247 | vec3 o2p0 = rayP0 - planeP; |
---|
248 | |
---|
249 | if (!test_line_only) |
---|
250 | { |
---|
251 | d = dot(o2p1, planeN); |
---|
252 | d *= dot(o2p0, planeN); |
---|
253 | |
---|
254 | //point are on the same side, so ray can intersect. |
---|
255 | if (d > .0f) |
---|
256 | return false; |
---|
257 | } |
---|
258 | |
---|
259 | float t = (dot(ProjPointOnPlane(rayP0, planeP, planeN) - rayP0, planeN)) / dot(ray_dir, planeN); |
---|
260 | |
---|
261 | if (!test_line_only && (t < -CSG_EPSILON || t > 1.0f)) |
---|
262 | return false; |
---|
263 | |
---|
264 | vIsec = rayP0 + t * ray_dir; |
---|
265 | return true; |
---|
266 | } |
---|
267 | |
---|
268 | //used to find the intersecting points between a triangle side and a coplanar line. |
---|
269 | bool RayIsectTriangleSide(vec3 const &v0, vec3 const &v1, vec3 const &v2, |
---|
270 | vec3 const &iP0, vec3 const &iP1, |
---|
271 | vec3 &iV0, int &iIdx0, vec3 &iV1, int &iIdx1) |
---|
272 | { |
---|
273 | vec3 isecV[2] = { vec3(.0f), vec3(.0f) }; |
---|
274 | int isecI[2] = { -1, -1 }; |
---|
275 | |
---|
276 | vec3 triV[3] = { v0, v1, v2 }; |
---|
277 | int isecIdx = 0; |
---|
278 | vec3 vIsec(0); |
---|
279 | |
---|
280 | //Two points given, so we test each triangle side to find the intersect |
---|
281 | isecIdx = 0; |
---|
282 | for (int j = 0; j < 3 && isecIdx < 2; j++) |
---|
283 | { |
---|
284 | int Result = RayIsectRay(triV[j], triV[(j + 1) % 3], iP0, iP1, vIsec); |
---|
285 | if (Result == RAY_ISECT_P0 || Result == RAY_ISECT_ALL) |
---|
286 | { |
---|
287 | isecV[isecIdx] = vIsec; |
---|
288 | isecI[isecIdx] = j; |
---|
289 | isecIdx++; |
---|
290 | } |
---|
291 | } |
---|
292 | |
---|
293 | if (isecIdx < 2) |
---|
294 | return false; |
---|
295 | |
---|
296 | //We send the infos back to the parent. |
---|
297 | //TODO : that can be better than this horrible thing. |
---|
298 | iV0 = isecV[0]; |
---|
299 | iV1 = isecV[1]; |
---|
300 | iIdx0 = isecI[0]; |
---|
301 | iIdx1 = isecI[1]; |
---|
302 | return true; |
---|
303 | } |
---|
304 | |
---|
305 | } /* namespace lol */ |
---|
306 | |
---|