Debian Codegraph @

src/ImathTest/testLineAlgo.cpp

raw
1 //
2 // SPDX-License-Identifier: BSD-3-Clause
3 // Copyright Contributors to the OpenEXR Project.
4 //
5
6 #ifdef NDEBUG
7 # undef NDEBUG
8 #endif
9
10 #include <ImathLineAlgo.h>
11 #include <ImathRandom.h>
12 #include <assert.h>
13 #include <iostream>
14 #include "testLineAlgo.h"
15
16 // Include ImathForward *after* other headers to validate forward declarations
17 #include <ImathForward.h>
18
19 using namespace std;
20 using namespace IMATH_INTERNAL_NAMESPACE;
21
22 namespace
23 {
24
25 void
26 testClosestPoints (const Line3f& line1,
27 const Line3f& line2,
28 bool returnValue,
29 const V3f& point1,
30 const V3f& point2)
31 {
32 V3f p1;
33 V3f p2;
34 bool rv = closestPoints (line1, line2, p1, p2);
35
36 assert (rv == returnValue);
37
38 if (rv)
39 {
40 float e = 10 * std::numeric_limits<float>::epsilon();
41 assert (point1.equalWithAbsError (p1, e));
42 assert (point2.equalWithAbsError (p2, e));
43 }
44 }
45
46 void
47 testClosestPoints()
48 {
49 cout << "closest points on two lines" << endl;
50
51 cout << " non-intersecting, non-parallel lines" << endl;
52
53 testClosestPoints (Line3f (V3f (0, -1, -1), V3f (0, 1, -1)),
54 Line3f (V3f (-1, 0, 1), V3f (1, 0, 1)),
55 true,
56 V3f (0, 0, -1),
57 V3f (0, 0, 1));
58
59 testClosestPoints (Line3f (V3f (2, -1, -1), V3f (2, 1, -1)),
60 Line3f (V3f (-1, 3, 1), V3f (1, 3, 1)),
61 true,
62 V3f (2, 3, -1),
63 V3f (2, 3, 1));
64
65 cout << " intersecting, non-parallel lines" << endl;
66
67 testClosestPoints (Line3f (V3f (2, -1, 0), V3f (2, 1, 0)),
68 Line3f (V3f (-1, 3, 0), V3f (1, 3, 0)),
69 true,
70 V3f (2, 3, 0),
71 V3f (2, 3, 0));
72
73 cout << " parallel lines" << endl;
74
75 testClosestPoints (Line3f (V3f (2, -1, 0), V3f (2, 1, 0)),
76 Line3f (V3f (2, -1, 1), V3f (2, 1, 1)),
77 false,
78 V3f (0, 0, 0),
79 V3f (0, 0, 0));
80
81 testClosestPoints (Line3f (V3f (2, -1, 0), V3f (2, 1, 0)),
82 Line3f (V3f (2, 1, 1), V3f (2, -1, 1)),
83 false,
84 V3f (0, 0, 0),
85 V3f (0, 0, 0));
86
87 cout << " coincident lines" << endl;
88
89 testClosestPoints (Line3f (V3f (2, -1, 0), V3f (2, -1, 1)),
90 Line3f (V3f (2, -1, 0), V3f (2, -1, 1)),
91 false,
92 V3f (0, 0, 0),
93 V3f (0, 0, 0));
94
95 cout << " random lines" << endl;
96
97 Rand48 rand (7);
98
99 for (int i = 0; i < 10000; ++i)
100 {
101 Line3f line1 (solidSphereRand<V3f> (rand) * 100.f, solidSphereRand<V3f> (rand) * 100.f);
102
103 Line3f line2 (solidSphereRand<V3f> (rand) * 100.f, solidSphereRand<V3f> (rand) * 100.f);
104
105 V3f point1;
106 V3f point2;
107 bool rv = closestPoints (line1, line2, point1, point2);
108
109 if (rv)
110 {
111 //
112 // We test if the line that connects point1 and point2
113 // is perpendicular to line1 and line2. The numerical
114 // accuracy of point1 and point2 depends strongly on
115 // the relative directions of line1 and line2; accuracy
116 // degrades rather quickly if line1 and line2 become
117 // close to parallel.
118 //
119
120 float e = 2000 * std::numeric_limits<float>::epsilon();
121 float d = 1 - (line1.dir ^ line2.dir) * (line1.dir ^ line2.dir);
122 V3f n = point1 - point2;
123
124 assert (equalWithAbsError (0.0f, (line1.dir ^ n) * d, e));
125 assert (equalWithAbsError (0.0f, (line2.dir ^ n) * d, e));
126 }
127 }
128 }
129
130 void
131 testIntersect (const Line3f& line,
132 const V3f& v0,
133 const V3f& v1,
134 const V3f& v2,
135 const V3f& point,
136 bool front,
137 bool returnValue)
138 {
139 V3f pt;
140 V3f bary;
141 bool fr;
142
143 bool rv = intersect (line, v0, v1, v2, pt, bary, fr);
144
145 assert (rv == returnValue);
146
147 float e = 10 * std::numeric_limits<float>::epsilon();
148
149 if (rv)
150 {
151 assert (front == fr);
152 assert (pt.equalWithAbsError (point, e));
153 V3f pt2 = v0 * bary.x + v1 * bary.y + v2 * bary.z;
154 assert (pt.equalWithAbsError (pt2, e));
155 }
156 }
157
158 void
159 testIntersect()
160 {
161 cout << "line-triangle intersection" << endl;
162
163 cout << " line-plane intersection inside triangle" << endl;
164
165 testIntersect (Line3f (V3f (0, 0, -1), V3f (0, 0, 7)),
166 V3f (-4, -4, 7),
167 V3f (4, -4, 7),
168 V3f (0, 6, 7),
169 V3f (0, 0, 7),
170 true,
171 true);
172
173 testIntersect (Line3f (V3f (0, 0, -1), V3f (-1, -2, 7)),
174 V3f (-4, -4, 7),
175 V3f (4, -4, 7),
176 V3f (0, 6, 7),
177 V3f (-1, -2, 7),
178 true,
179 true);
180
181 testIntersect (Line3f (V3f (0, 0, -1), V3f (-1, 1, 7)),
182 V3f (-4, -4, 7),
183 V3f (4, -4, 7),
184 V3f (0, 6, 7),
185 V3f (-1, 1, 7),
186 true,
187 true);
188
189 testIntersect (Line3f (V3f (0, 0, -1), V3f (-1, 1, 7)),
190 V3f (4, -4, 7),
191 V3f (-4, -4, 7),
192 V3f (0, 6, 7),
193 V3f (-1, 1, 7),
194 false,
195 true);
196
197 testIntersect (Line3f (V3f (1, 1, 2), V3f (0, 0, 7)),
198 V3f (-4, -4, 7),
199 V3f (4, -4, 7),
200 V3f (0, 6, 7),
201 V3f (0, 0, 7),
202 true,
203 true);
204
205 testIntersect (Line3f (V3f (2, 3, -5), V3f (-1, -2, 7)),
206 V3f (-4, -4, 7),
207 V3f (4, -4, 7),
208 V3f (0, 6, 7),
209 V3f (-1, -2, 7),
210 true,
211 true);
212
213 testIntersect (Line3f (V3f (2, 8, -10), V3f (-1, 1, 7)),
214 V3f (-4, -4, 7),
215 V3f (4, -4, 7),
216 V3f (0, 6, 7),
217 V3f (-1, 1, 7),
218 true,
219 true);
220
221 testIntersect (Line3f (V3f (-10, 2, -1), V3f (-1, 1, 7)),
222 V3f (4, -4, 7),
223 V3f (-4, -4, 7),
224 V3f (0, 6, 7),
225 V3f (-1, 1, 7),
226 false,
227 true);
228
229 cout << " line-plane intersection outside triangle" << endl;
230
231 testIntersect (Line3f (V3f (0, 0, -1), V3f (4, 0, 7)),
232 V3f (-4, -4, 7),
233 V3f (4, -4, 7),
234 V3f (0, 6, 7),
235 V3f (0, 0, 0),
236 false,
237 false);
238
239 testIntersect (Line3f (V3f (0, 0, -1), V3f (-4, 1, 7)),
240 V3f (-4, -4, 7),
241 V3f (4, -4, 7),
242 V3f (0, 6, 7),
243 V3f (0, 0, 0),
244 false,
245 false);
246
247 testIntersect (Line3f (V3f (0, 0, -1), V3f (0, -5, 7)),
248 V3f (-4, -4, 7),
249 V3f (4, -4, 7),
250 V3f (0, 6, 7),
251 V3f (0, 0, 0),
252 false,
253 false);
254
255 testIntersect (Line3f (V3f (0, 0, -1), V3f (0, -7, 7)),
256 V3f (-4, -4, 7),
257 V3f (4, -4, 7),
258 V3f (0, 6, 7),
259 V3f (0, 0, 0),
260 false,
261 false);
262
263 cout << " line parallel to triangle" << endl;
264
265 testIntersect (Line3f (V3f (0, 0, -1), V3f (4, 0, -1)),
266 V3f (-4, -4, 7),
267 V3f (4, -4, 7),
268 V3f (0, 6, 7),
269 V3f (0, 0, 0),
270 false,
271 false);
272
273 testIntersect (Line3f (V3f (0, 4, 7), V3f (4, 0, 7)),
274 V3f (-4, -4, 7),
275 V3f (4, -4, 7),
276 V3f (0, 6, 7),
277 V3f (0, 0, 0),
278 false,
279 false);
280
281 cout << " zero-area triangle" << endl;
282
283 testIntersect (Line3f (V3f (2, 3, -5), V3f (-1, -2, 7)),
284 V3f (0, 6, 7),
285 V3f (4, -4, 7),
286 V3f (0, 6, 7),
287 V3f (0, 0, 0),
288 false,
289 false);
290
291 testIntersect (Line3f (V3f (2, 3, -5), V3f (-1, -2, 7)),
292 V3f (-4, -4, 7),
293 V3f (-4, -4, 7),
294 V3f (0, 6, 7),
295 V3f (0, 0, 0),
296 false,
297 false);
298
299 testIntersect (Line3f (V3f (2, 3, -5), V3f (-1, -2, 7)),
300 V3f (-4, -4, 7),
301 V3f (0, 6, 7),
302 V3f (0, 6, 7),
303 V3f (0, 0, 0),
304 false,
305 false);
306
307 testIntersect (Line3f (V3f (2, 3, -5), V3f (-1, -2, 7)),
308 V3f (-4, -4, 7),
309 V3f (-4, -4, 7),
310 V3f (-4, -4, 7),
311 V3f (0, 0, 0),
312 false,
313 false);
314
315 cout << " random lines and triangles" << endl;
316
317 Rand48 rand (8);
318
319 for (int i = 0; i < 10000; ++i)
320 {
321 //
322 // Generate a random triangle with non-zero area
323 //
324
325 V3f v0, v1, v2;
326 V3f normal;
327
328 do
329 {
330 v0 = solidSphereRand<V3f> (rand);
331 v1 = solidSphereRand<V3f> (rand);
332 v2 = solidSphereRand<V3f> (rand);
333 normal = (v2 - v1) % (v1 - v0);
334 } while (normal.length() < 0.01);
335
336 {
337 //
338 // Generate a line that intersects inside the triangle
339 //
340
341 V3f b;
342
343 do
344 {
345 b.x = float(rand.nextf (0.001, 0.999));
346 b.y = float(rand.nextf (0.001, 0.999));
347 b.z = 1 - b.x - b.y;
348 } while (b.x + b.y > 0.999);
349
350 V3f p1 = v0 * b.x + v1 * b.y + v2 * b.z;
351
352 V3f p0;
353
354 do
355 {
356 p0 = solidSphereRand<V3f> (rand);
357 } while (abs (normal.normalized() ^ (p1 - p0).normalized()) < 0.1);
358
359 //
360 // Test for intersection
361 //
362
363 V3f point;
364 V3f bary;
365 bool front;
366
367 bool rv = intersect (Line3f (p0, p1), v0, v1, v2, point, bary, front);
368
369 assert (rv == true);
370
371 float nd = abs (normal.normalized() ^ (p1 - p0).normalized());
372 float ep = 20 * std::numeric_limits<float>::epsilon() / nd;
373
374 assert (point.equalWithAbsError (p1, ep));
375 }
376
377 {
378 //
379 // Generate a line that intersects the triangle's plane
380 // but outside the triangle
381 //
382
383 V3f b;
384
385 do
386 {
387 b.x = float(rand.nextf (-3, 3));
388 b.y = float(rand.nextf (-3, 3));
389 b.z = 1 - b.x - b.y;
390 } while (b.x > -0.001 && b.y > -0.001 && b.z > -0.001);
391
392 V3f p1 = v0 * b.x + v1 * b.y + v2 * b.z;
393
394 V3f p0;
395
396 do
397 {
398 p0 = solidSphereRand<V3f> (rand) * 10;
399 } while (abs (normal.normalized() ^ (p1 - p0).normalized()) < 0.1);
400
401 //
402 // Test for intersection
403 //
404
405 V3f point;
406 V3f bary;
407 bool front;
408
409 bool rv = intersect (Line3f (p0, p1), v0, v1, v2, point, bary, front);
410
411 assert (rv == false);
412 }
413 }
414 }
415
416 } // namespace
417
418 void
419 testLineAlgo()
420 {
421 cout << "Testing line algorithms" << endl;
422
423 testClosestPoints();
424 testIntersect();
425
426 cout << "ok\n" << endl;
427 }