source: trunk/src/math/geometry.cpp @ 2229

Last change on this file since 2229 was 2229, checked in by sam, 8 years ago

build: fix a few CRLF endings.

File size: 10.2 KB
Line 
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
36using namespace std;
37
38namespace 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
Note: See TracBrowser for help on using the repository browser.