1 // Copyright (C) 2006 Mathias Froehlich - Mathias.Froehlich@web.de
3 // This library is free software; you can redistribute it and/or
4 // modify it under the terms of the GNU Library General Public
5 // License as published by the Free Software Foundation; either
6 // version 2 of the License, or (at your option) any later version.
8 // This library is distributed in the hope that it will be useful,
9 // but WITHOUT ANY WARRANTY; without even the implied warranty of
10 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 // Library General Public License for more details.
13 // You should have received a copy of the GNU General Public License
14 // along with this program; if not, write to the Free Software
15 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19 # include <simgear_config.h>
25 #include "SGGeometry.hxx"
26 #include "sg_random.h"
29 SGVec3<T> rndVec3(void)
31 return SGVec3<T>(sg_random(), sg_random(), sg_random());
36 TriangleLineIntersectionTest(void)
38 unsigned nTests = 100000;
39 unsigned failedCount = 0;
40 for (unsigned i = 0; i < nTests; ++i) {
41 SGVec3<T> v0 = rndVec3<T>();
42 SGVec3<T> v1 = rndVec3<T>();
43 SGVec3<T> v2 = rndVec3<T>();
45 SGTriangle<T> tri(v0, v1, v2);
47 T triangleEps = 100*SGLimits<T>::epsilon();
49 // generate random coeficients
50 T u = 4*sg_random() - 2;
51 T v = 4*sg_random() - 2;
52 T t = 4*sg_random() - 2;
54 SGVec3<T> isectpt = v0 + u*(v1 - v0) + v*(v2 - v0);
56 SGLineSegment<T> lineSegment;
57 SGVec3<T> dir = rndVec3<T>();
60 lineSegment.set(isectpt - t*dir, isectpt + (1 - t)*dir);
62 if (intersects(isectres, tri, lineSegment)) {
63 if (0 <= u && 0 <= v && u+v <= 1 && 0 <= t && t <= 1) {
64 if (!equivalent(isectres, isectpt, triangleEps)) {
65 std::cout << "Failed line segment intersection test #" << i
66 << ": not equivalent!\nu = "
67 << u << ", v = " << v << ", t = " << t
68 << "\n" << tri << "\n" << lineSegment << std::endl;
72 std::cout << "Failed line segment intersection test #" << i
73 << ": false positive!\nu = "
74 << u << ", v = " << v << ", t = " << t
75 << "\n" << tri << "\n" << lineSegment << std::endl;
79 if (0 <= u && 0 <= v && u+v <= 1 && 0 <= t && t <= 1) {
80 std::cout << "Failed line segment intersection test #" << i
81 << ": false negative!\nu = "
82 << u << ", v = " << v << ", t = " << t
83 << "\n" << tri << "\n" << lineSegment << std::endl;
89 ray.set(isectpt - t*dir, dir);
90 if (intersects(isectres, tri, ray)) {
91 if (0 <= u && 0 <= v && u+v <= 1 && 0 <= t) {
92 if (!equivalent(isectres, isectpt, triangleEps)) {
93 std::cout << "Failed ray intersection test #" << i
94 << ": not equivalent!\nu = "
95 << u << ", v = " << v << ", t = " << t
96 << "\n" << tri << "\n" << ray << std::endl;
100 std::cout << "Failed ray intersection test #" << i
101 << ": false positive!\nu = "
102 << u << ", v = " << v << ", t = " << t
103 << "\n" << tri << "\n" << ray << std::endl;
107 if (0 <= u && 0 <= v && u+v <= 1 && 0 <= t) {
108 std::cout << "Failed ray intersection test #" << i
109 << ": false negative !\nu = "
110 << u << ", v = " << v << ", t = " << t
111 << "\n" << tri << "\n" << ray << std::endl;
117 if (nTests < 100*failedCount) {
118 std::cout << "Failed ray intersection tests: " << failedCount
119 << " tests out of " << nTests
120 << " went wrong. Abort!" << std::endl;
124 /// Some crude handmade test
125 SGVec3<T> v0 = SGVec3<T>(0, 0, 0);
126 SGVec3<T> v1 = SGVec3<T>(1, 0, 0);
127 SGVec3<T> v2 = SGVec3<T>(0, 1, 0);
129 SGTriangle<T> tri(v0, v1, v2);
132 ray.set(SGVec3<T>(0, 0, 1), SGVec3<T>(0.1, 0.1, -1));
133 if (!intersects(tri, ray)) {
134 std::cout << "Failed test #1!" << std::endl;
138 ray.set(SGVec3<T>(0, 0, 1), SGVec3<T>(0, 0, -1));
139 if (!intersects(tri, ray)) {
140 std::cout << "Failed test #2!" << std::endl;
144 SGLineSegment<T> lineSegment;
145 lineSegment.set(SGVec3<T>(0, 0, 1), SGVec3<T>(0.1, 0.1, -1));
146 if (!intersects(tri, lineSegment)) {
147 std::cout << "Failed test #3!" << std::endl;
151 lineSegment.set(SGVec3<T>(0, 0, 1), SGVec3<T>(0, 0, -1));
152 if (!intersects(tri, lineSegment)) {
153 std::cout << "Failed test #4!" << std::endl;
157 lineSegment.set(SGVec3<T>(0, 0, 1), SGVec3<T>(0, 1, -1));
158 if (!intersects(tri, lineSegment)) {
159 std::cout << "Failed test #5!" << std::endl;
163 lineSegment.set(SGVec3<T>(0, 0, 1), SGVec3<T>(1, 0, -1));
164 if (!intersects(tri, lineSegment)) {
165 std::cout << "Failed test #6!" << std::endl;
169 lineSegment.set(SGVec3<T>(0, 0, 1), SGVec3<T>(1, 1, -1));
170 if (!intersects(tri, lineSegment)) {
171 std::cout << "Failed test #7!" << std::endl;
175 // is exactly in the plane
176 // FIXME: cannot detect that yet ??
177 // lineSegment.set(SGVec3<T>(0, 0, 0), SGVec3<T>(1, 0, 0));
178 // if (!intersects(tri, lineSegment)) {
179 // std::cout << "Failed test #8!" << std::endl;
183 // is exactly in the plane
184 // FIXME: cannot detect that yet ??
185 // lineSegment.set(SGVec3<T>(-1, 0, 0), SGVec3<T>(1, 0, 0));
186 // if (!intersects(tri, lineSegment)) {
187 // std::cout << "Failed test #9!" << std::endl;
191 // is exactly paralell to the plane
192 // FIXME: cannot detect that yet ??
193 // lineSegment.set(SGVec3<T>(-1, 1, 0), SGVec3<T>(1, 1, 0));
194 // if (intersects(tri, lineSegment)) {
195 // std::cout << "Failed test #10!" << std::endl;
199 // should fail since the line segment poins slightly beyond the triangle
200 lineSegment.set(SGVec3<T>(0, 0, 1), SGVec3<T>(1, 1, -0.9));
201 if (intersects(tri, lineSegment)) {
202 std::cout << "Failed test #11!" << std::endl;
206 lineSegment.set(SGVec3<T>(0, 0, 1), SGVec3<T>(0, -0.1, -1));
207 if (intersects(tri, lineSegment)) {
208 std::cout << "Failed test #12!" << std::endl;
212 lineSegment.set(SGVec3<T>(0, 0, 1), SGVec3<T>(-0.1, -0.1, -1));
213 if (intersects(tri, lineSegment)) {
214 std::cout << "Failed test #13!" << std::endl;
218 lineSegment.set(SGVec3<T>(0, 0, 1), SGVec3<T>(-0.1, 0, -1));
219 if (intersects(tri, lineSegment)) {
220 std::cout << "Failed test #14!" << std::endl;
229 SphereLineIntersectionTest(void)
231 unsigned nTests = 100000;
232 unsigned failedCount = 0;
233 for (unsigned i = 0; i < nTests; ++i) {
234 SGVec3<T> center = rndVec3<T>();
235 T radius = 2*sg_random();
236 SGSphere<T> sphere(center, radius);
238 SGVec3<T> offset = normalize(rndVec3<T>());
241 // This one is the point we use to judge if the test should fail or not
242 SGVec3<T> base = center + t*offset;
244 SGVec3<T> per = perpendicular(offset);
245 SGVec3<T> start = base + 4*sg_random()*per;
246 SGVec3<T> end = base - 4*sg_random()*per;
248 SGLineSegment<T> lineSegment;
249 lineSegment.set(start, end);
250 if (intersects(sphere, lineSegment)) {
252 std::cout << "Failed sphere line intersection test #" << i
253 << ": false positive!\nt = " << t << "\n"
254 << sphere << "\n" << lineSegment << std::endl;
259 std::cout << "Failed sphere line intersection test #" << i
260 << ": false negative!\nt = " << t << "\n"
261 << sphere << "\n" << lineSegment << std::endl;
267 ray.set(start, end - start);
268 if (intersects(sphere, ray)) {
270 std::cout << "Failed sphere line intersection test #" << i
271 << ": false positive!\nt = " << t << "\n"
272 << sphere << "\n" << ray << std::endl;
277 std::cout << "Failed sphere line intersection test #" << i
278 << ": false negative!\nt = " << t << "\n"
279 << sphere << "\n" << ray << std::endl;
285 if (nTests < 100*failedCount) {
286 std::cout << "Failed sphere line intersection tests: " << failedCount
287 << " tests out of " << nTests
288 << " went wrong. Abort!" << std::endl;
293 for (unsigned i = 0; i < nTests; ++i) {
294 SGVec3<T> center = rndVec3<T>();
295 T radius = 2*sg_random();
296 SGSphere<T> sphere(center, radius);
298 SGVec3<T> offset = normalize(rndVec3<T>());
301 // This one is the point we use to judge if the test should fail or not
302 SGVec3<T> base = center + t*offset;
304 SGVec3<T> start = base;
305 SGVec3<T> end = base + 2*sg_random()*offset;
307 SGLineSegment<T> lineSegment;
308 lineSegment.set(start, end);
309 if (intersects(sphere, lineSegment)) {
311 std::cout << "Failed sphere line intersection test #" << i
312 << ": false positive!\nt = " << t << "\n"
313 << sphere << "\n" << lineSegment << std::endl;
318 std::cout << "Failed sphere line intersection test #" << i
319 << ": false negative!\nt = " << t << "\n"
320 << sphere << "\n" << lineSegment << std::endl;
326 ray.set(start, end - start);
327 if (intersects(sphere, ray)) {
329 std::cout << "Failed sphere line intersection test #" << i
330 << ": false positive!\nt = " << t << "\n"
331 << sphere << "\n" << ray << std::endl;
336 std::cout << "Failed sphere line intersection test #" << i
337 << ": false negative!\nt = " << t << "\n"
338 << sphere << "\n" << ray << std::endl;
344 if (nTests < 100*failedCount) {
345 std::cout << "Failed sphere line intersection tests: " << failedCount
346 << " tests out of " << nTests
347 << " went wrong. Abort!" << std::endl;
356 BoxLineIntersectionTest(void)
358 // ok, bad test case coverage, but better than nothing ...
360 unsigned nTests = 100000;
361 unsigned failedCount = 0;
362 for (unsigned i = 0; i < nTests; ++i) {
364 box.expandBy(rndVec3<T>());
365 box.expandBy(rndVec3<T>());
367 SGVec3<T> center = box.getCenter();
369 // This one is the point we use to judge if the test should fail or not
370 SGVec3<T> base = rndVec3<T>();
371 SGVec3<T> dir = base - center;
373 SGLineSegment<T> lineSegment;
374 lineSegment.set(base, base + dir);
375 if (intersects(box, lineSegment)) {
376 if (!intersects(box, base)) {
377 std::cout << "Failed box line intersection test #" << i
378 << ": false positive!\n"
379 << box << "\n" << lineSegment << std::endl;
383 if (intersects(box, base)) {
384 std::cout << "Failed box line intersection test #" << i
385 << ": false negative!\n"
386 << box << "\n" << lineSegment << std::endl;
393 if (intersects(box, ray)) {
394 if (!intersects(box, base)) {
395 std::cout << "Failed box line intersection test #" << i
396 << ": false positive!\n"
397 << box << "\n" << ray << std::endl;
401 if (intersects(box, base)) {
402 std::cout << "Failed box line intersection test #" << i
403 << ": false negative!\n"
404 << box << "\n" << ray << std::endl;
410 if (nTests < 100*failedCount) {
411 std::cout << "Failed box line intersection tests: " << failedCount
412 << " tests out of " << nTests
413 << " went wrong. Abort!" << std::endl;
423 std::cout << "Testing Geometry intersection routines.\n"
424 << "Some of these tests can fail due to roundoff problems...\n"
425 << "Dont worry if only a few of them fail..." << std::endl;
429 if (!TriangleLineIntersectionTest<float>())
431 if (!TriangleLineIntersectionTest<double>())
434 if (!SphereLineIntersectionTest<float>())
436 if (!SphereLineIntersectionTest<double>())
439 if (!BoxLineIntersectionTest<float>())
441 if (!BoxLineIntersectionTest<double>())
444 std::cout << "Successfully passed all tests!" << std::endl;