2 Copyright (C) 2003, 2010 - Wolfire Games
3 Copyright (C) 2010-2016 - Lugaru contributors (see AUTHORS file)
5 This file is part of Lugaru.
7 Lugaru is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
12 Lugaru is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with Lugaru. If not, see <http://www.gnu.org/licenses/>.
21 #include "Math/XYZ.hpp"
23 bool PointInTriangle(XYZ* p, XYZ normal, XYZ* p1, XYZ* p2, XYZ* p3)
25 static float u0, u1, u2;
26 static float v0, v1, v2;
30 static bool bInter = 0;
31 static float pointv[3];
35 static float normalv[3];
55 normalv[0] = normal.x;
56 normalv[1] = normal.y;
57 normalv[2] = normal.z;
59 #define ABS(X) (((X) < 0.f) ? -(X) : (X))
60 #define MAX(A, B) (((A) < (B)) ? (B) : (A))
61 max = MAX(MAX(ABS(normalv[0]), ABS(normalv[1])), ABS(normalv[2]));
63 if (max == ABS(normalv[0])) {
67 if (max == ABS(normalv[1])) {
71 if (max == ABS(normalv[2])) {
77 u0 = pointv[i] - p1v[i];
78 v0 = pointv[j] - p1v[j];
84 if (u1 > -1.0e-05f && u1 < 1.0e-05f) { // == 0.0f)
86 if (0.0f <= b && b <= 1.0f) {
87 a = (v0 - b * v2) / v1;
88 if ((a >= 0.0f) && ((a + b) <= 1.0f)) {
93 b = (v0 * u1 - u0 * v1) / (v2 * u1 - u2 * v1);
94 if (0.0f <= b && b <= 1.0f) {
95 a = (u0 - b * u2) / u1;
96 if ((a >= 0.0f) && ((a + b) <= 1.0f)) {
105 bool LineFacet(XYZ p1, XYZ p2, XYZ pa, XYZ pb, XYZ pc, XYZ* p)
108 static float denom, mu;
111 //Calculate the parameters for the plane
112 n.x = (pb.y - pa.y) * (pc.z - pa.z) - (pb.z - pa.z) * (pc.y - pa.y);
113 n.y = (pb.z - pa.z) * (pc.x - pa.x) - (pb.x - pa.x) * (pc.z - pa.z);
114 n.z = (pb.x - pa.x) * (pc.y - pa.y) - (pb.y - pa.y) * (pc.x - pa.x);
116 d = -n.x * pa.x - n.y * pa.y - n.z * pa.z;
118 //Calculate the position on the line that intersects the plane
119 denom = n.x * (p2.x - p1.x) + n.y * (p2.y - p1.y) + n.z * (p2.z - p1.z);
120 if (fabs(denom) < 0.0000001) { // Line and plane don't intersect
123 mu = -(d + n.x * p1.x + n.y * p1.y + n.z * p1.z) / denom;
124 p->x = p1.x + mu * (p2.x - p1.x);
125 p->y = p1.y + mu * (p2.y - p1.y);
126 p->z = p1.z + mu * (p2.z - p1.z);
127 if (mu < 0 || mu > 1) { // Intersection not along line segment
131 if (!PointInTriangle(p, n, &pa, &pb, &pc)) {
138 float LineFacetd(XYZ p1, XYZ p2, XYZ pa, XYZ pb, XYZ pc, XYZ* p)
141 static float denom, mu;
144 //Calculate the parameters for the plane
145 n.x = (pb.y - pa.y) * (pc.z - pa.z) - (pb.z - pa.z) * (pc.y - pa.y);
146 n.y = (pb.z - pa.z) * (pc.x - pa.x) - (pb.x - pa.x) * (pc.z - pa.z);
147 n.z = (pb.x - pa.x) * (pc.y - pa.y) - (pb.y - pa.y) * (pc.x - pa.x);
149 d = -n.x * pa.x - n.y * pa.y - n.z * pa.z;
151 //Calculate the position on the line that intersects the plane
152 denom = n.x * (p2.x - p1.x) + n.y * (p2.y - p1.y) + n.z * (p2.z - p1.z);
153 if (fabs(denom) < 0.0000001) { // Line and plane don't intersect
156 mu = -(d + n.x * p1.x + n.y * p1.y + n.z * p1.z) / denom;
157 p->x = p1.x + mu * (p2.x - p1.x);
158 p->y = p1.y + mu * (p2.y - p1.y);
159 p->z = p1.z + mu * (p2.z - p1.z);
160 if (mu < 0 || mu > 1) { // Intersection not along line segment
164 if (!PointInTriangle(p, n, &pa, &pb, &pc)) {
171 float LineFacetd(XYZ p1, XYZ p2, XYZ pa, XYZ pb, XYZ pc, XYZ n, XYZ* p)
174 static float denom, mu;
176 //Calculate the parameters for the plane
177 d = -n.x * pa.x - n.y * pa.y - n.z * pa.z;
179 //Calculate the position on the line that intersects the plane
180 denom = n.x * (p2.x - p1.x) + n.y * (p2.y - p1.y) + n.z * (p2.z - p1.z);
181 if (fabs(denom) < 0.0000001) { // Line and plane don't intersect
184 mu = -(d + n.x * p1.x + n.y * p1.y + n.z * p1.z) / denom;
185 p->x = p1.x + mu * (p2.x - p1.x);
186 p->y = p1.y + mu * (p2.y - p1.y);
187 p->z = p1.z + mu * (p2.z - p1.z);
188 if (mu < 0 || mu > 1) { // Intersection not along line segment
192 if (!PointInTriangle(p, n, &pa, &pb, &pc)) {
198 float LineFacetd(XYZ* p1, XYZ* p2, XYZ* pa, XYZ* pb, XYZ* pc, XYZ* p)
201 static float denom, mu;
204 //Calculate the parameters for the plane
205 n.x = (pb->y - pa->y) * (pc->z - pa->z) - (pb->z - pa->z) * (pc->y - pa->y);
206 n.y = (pb->z - pa->z) * (pc->x - pa->x) - (pb->x - pa->x) * (pc->z - pa->z);
207 n.z = (pb->x - pa->x) * (pc->y - pa->y) - (pb->y - pa->y) * (pc->x - pa->x);
209 d = -n.x * pa->x - n.y * pa->y - n.z * pa->z;
211 //Calculate the position on the line that intersects the plane
212 denom = n.x * (p2->x - p1->x) + n.y * (p2->y - p1->y) + n.z * (p2->z - p1->z);
213 if (fabs(denom) < 0.0000001) { // Line and plane don't intersect
216 mu = -(d + n.x * p1->x + n.y * p1->y + n.z * p1->z) / denom;
217 p->x = p1->x + mu * (p2->x - p1->x);
218 p->y = p1->y + mu * (p2->y - p1->y);
219 p->z = p1->z + mu * (p2->z - p1->z);
220 if (mu < 0 || mu > 1) { // Intersection not along line segment
224 if (!PointInTriangle(p, n, pa, pb, pc)) {
230 float LineFacetd(XYZ* p1, XYZ* p2, XYZ* pa, XYZ* pb, XYZ* pc, XYZ* n, XYZ* p)
233 static float denom, mu;
235 //Calculate the parameters for the plane
236 d = -n->x * pa->x - n->y * pa->y - n->z * pa->z;
238 //Calculate the position on the line that intersects the plane
239 denom = n->x * (p2->x - p1->x) + n->y * (p2->y - p1->y) + n->z * (p2->z - p1->z);
240 if (fabs(denom) < 0.0000001) { // Line and plane don't intersect
243 mu = -(d + n->x * p1->x + n->y * p1->y + n->z * p1->z) / denom;
244 p->x = p1->x + mu * (p2->x - p1->x);
245 p->y = p1->y + mu * (p2->y - p1->y);
246 p->z = p1->z + mu * (p2->z - p1->z);
247 if (mu < 0 || mu > 1) { // Intersection not along line segment
251 if (!PointInTriangle(p, *n, pa, pb, pc)) {