NDEVR
API Documentation
Intersection.hpp
1/*--------------------------------------------------------------------------------------------
2Copyright (c) 2019, NDEVR LLC
3tyler.parke@ndevr.org
4 __ __ ____ _____ __ __ _______
5 | \ | | | __ \ | ___|\ \ / / | __ \
6 | \ | | | | \ \ | |___ \ \ / / | |__) |
7 | . \| | | |__/ / | |___ \ V / | _ /
8 | |\ |_|_____/__|_____|___\_/____| | \ \
9 |__| \__________________________________| \__\
10
11Subject to the terms of the Enterprise+ Agreement, NDEVR hereby grants
12Licensee a limited, non-exclusive, non-transferable, royalty-free license
13(without the right to sublicense) to use the API solely for the purpose of
14Licensee's internal development efforts to develop applications for which
15the API was provided.
16
17The above copyright notice and this permission notice shall be included in all
18copies or substantial portions of the Software.
19
20THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
21INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
22PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE
23FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
24OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
25DEALINGS IN THE SOFTWARE.
26
27Library: Base
28File: Intersection
29Included in API: True
30Author(s): Tyler Parke
31 *-----------------------------------------------------------------------------------------**/
32#pragma once
33#include <NDEVR/Triangle.h>
34#include <NDEVR/Bounds.h>
35#include <NDEVR/LineSegment.h>
36#include <NDEVR/Vector.h>
37#include <NDEVR/Polygon.h>
38#include <NDEVR/Plane.h>
39namespace NDEVR
40{
44 class Intersection
45 {};
46 constexpr fltp08 intersection_epsilon = 0.0001;
63 template<uint01 t_dims, class t_type, class t_vertex>
64 static Bounds<t_dims, t_type, t_vertex> intersection(const Bounds<t_dims, t_type, t_vertex>& bounds_1, const Bounds<t_dims, t_type, t_vertex>& bounds_2)
65 {
66 return Bounds<t_dims, t_type, t_vertex>(getMax(bounds_1[MIN], bounds_2[MIN]), getMin(bounds_1[MAX], bounds_2[MAX]));
67 }
68
69
70
86 template<uint01 t_dims, class t_type, class t_vertex>
87 static LineSegment<t_dims, t_type> intersection(const Bounds<t_dims, t_type, t_vertex>& bounds, const LineSegment<t_dims, t_type, t_vertex>& line)
88 {
89 LineSegment<t_dims, t_type> intersected_line = line;
90 for (uint01 dim = 0; dim < t_dims; ++dim)
91 {
92 if (intersected_line.vertex(A)[dim] < bounds[MIN][dim])
93 {
94 if (intersected_line.vertex(B)[dim] < bounds[MIN][dim])
95 return Constant<LineSegment<t_dims, t_type>>::Invalid;
96 else
97 intersected_line.vertex(A) = line.template pointAt<true>(bounds[MIN][dim], dim);
98 }
99 else if (intersected_line.vertex(B)[dim] < bounds[MIN][dim])
100 {
101 intersected_line.vertex(B) = line.template pointAt<true>(bounds[MIN][dim], dim);
102 }
103 if (intersected_line.vertex(A)[dim] > bounds[MAX][dim])
104 {
105 if (intersected_line.vertex(B)[dim] > bounds[MAX][dim])
106 return Constant<LineSegment<t_dims, t_type>>::Invalid;
107 else
108 intersected_line.vertex(A) = line.template pointAt<true>(bounds[MAX][dim], dim);
109 }
110 else if (intersected_line.vertex(B)[dim] > bounds[MAX][dim])
111 {
112 intersected_line.vertex(B) = line.template pointAt<true>(bounds[MAX][dim], dim);
113 }
114 }
115 return intersected_line;
116 }
117
134 template<uint01 t_dims, class t_type, class t_vertex>
135 static t_vertex intersection(const Triangle<t_dims, t_type, t_vertex>& tri, const LineSegment<t_dims, t_type, t_vertex>& line, t_type epsilon = 0)
136 {
137 const t_vertex tri_edge_ab(tri.edge(A, B).ray());
138 const t_vertex tri_edge_ca(tri.edge(A, C).ray());
139 const t_vertex line_ray(line.ray().template normalized<t_type>());
140 const t_vertex cross_line_tri = cross(line_ray, tri_edge_ca);
141 const t_type determinant = dot(tri_edge_ab, cross_line_tri);
142 if (abs(determinant) < epsilon)
143 return Constant<t_vertex>::Invalid;
144
145 const t_vertex t = line.vertex(A) - tri.vertex(A);
146 const t_type u0 = dot(t, cross_line_tri) / determinant;
147 if (u0 < -epsilon || u0 > cast<t_type>(1) + epsilon)
148 return Constant<t_vertex>::Invalid;
149 const t_vertex q = cross(t, tri_edge_ab);
150 const t_type v = dot(line_ray, q) / determinant;
151 if (v < -epsilon || u0 + v > cast<t_type>(1) + epsilon)
152 return Constant<t_vertex>::Invalid;
153 // At this stage we can compute t to find out where the intersection point is on the line.
154 const t_type final_t = dot(tri_edge_ca, q) / determinant;
155 if (final_t > -epsilon && final_t * final_t < line.lengthSquared())
156 return final_t * line_ray + line.vertex(A);
157 else
158 return Constant<t_vertex>::Invalid;// This means that there is a line intersection but not a segment intersection.
159 }
160 template<uint01 t_dims, class t_type, class t_vertex>
161 constexpr LineSegment<t_dims, t_type> ClosestPoint(const Triangle<t_dims, t_type, t_vertex>& tri, const LineSegment<t_dims, t_type>& segment)
162 {
163 Vertex<t_dims, t_type> inter_point = intersection(tri, segment);
164 if (IsValid(inter_point))
165 return LineSegment<t_dims, t_type>(inter_point, inter_point);
166
167 LineSegment<t_dims, t_type> a = segment.template closestPoints<t_type>(tri.edge(B, A));
168 LineSegment<t_dims, t_type> b = segment.template closestPoints<t_type>(tri.edge(C, B));
169 LineSegment<t_dims, t_type> c = segment.template closestPoints<t_type>(tri.edge(A, C));
170 if (b.magnitudeSquared() > a.magnitudeSquared())
171 a = b;
172 if (c.magnitudeSquared() > a.magnitudeSquared())
173 a = c;
174 return a;
175 }
195 template<uint01 t_dims, class t_type, class t_vertex>
196 static LineSegment<t_dims, t_type, t_vertex> intersection(const Triangle<t_dims, t_type, t_vertex>& tri_a, const Triangle<t_dims, t_type, t_vertex>& tri_b, t_type epsilon = 0)
197 {
198 UNUSED(epsilon);
199 const t_vertex normal_a = tri_a.template normal<true>();
200 const t_vertex normal_b = tri_b.template normal<true>();
201 if (normal_a == normal_b)
202 return Constant<LineSegment<t_dims, t_type, t_vertex>>::Invalid;//We fully intersect the plane, thus cannot produce a linesegment (edge case)
203 const t_type dot_1a = dot(normal_b, tri_a.vertex(A) - tri_b.vertex(A));
204 const t_type dot_1b = dot(normal_b, tri_a.vertex(B) - tri_b.vertex(A));
205 const t_type dot_1c = dot(normal_b, tri_a.vertex(C) - tri_b.vertex(A));
206 if ((dot_1a > 0 && dot_1b > 0 && dot_1c > 0) || (dot_1a < 0 && dot_1b < 0 && dot_1c < 0))
207 return Constant<LineSegment<t_dims, t_type, t_vertex>>::Invalid;
208
209 if (dot_1a == 0 || dot_1b == 0 || dot_1c == 0)
210 {
211 return Constant<LineSegment<t_dims, t_type, t_vertex>>::Invalid;
212 }
213 const t_type dot_2a = dot(normal_a, tri_b.vertex(A) - tri_a.vertex(A));
214 const t_type dot_2b = dot(normal_a, tri_b.vertex(B) - tri_a.vertex(A));
215 const t_type dot_2c = dot(normal_a, tri_b.vertex(C) - tri_a.vertex(A));
216
217 if ((dot_2a > 0 && dot_2b > 0 && dot_2c > 0) || (dot_2a < 0 && dot_2b < 0 && dot_2c < 0))
218 return Constant<LineSegment<t_dims, t_type, t_vertex>>::Invalid;//No intersection
219
220 if (dot_2a == 0 || dot_2b == 0 || dot_2c == 0)
221 return Constant<LineSegment<t_dims, t_type, t_vertex>>::Invalid;//We fully intersect the plane, thus cannot produce a linesegment (edge case)
222
223 const t_vertex seg_a1(tri_a.vertex(A) + (tri_a.vertex(B) - tri_a.vertex(A)) * (dot_1a / (dot_1a - dot_1b)));
224 const t_vertex seg_a2(tri_a.vertex(A) + (tri_a.vertex(C) - tri_a.vertex(A)) * (dot_1a / (dot_1a - dot_1c)));
225
226 const t_vertex seg_b1(tri_b.vertex(A) + (tri_b.vertex(B) - tri_b.vertex(A)) * (dot_2a / (dot_2a - dot_2b)));
227 const t_vertex seg_b2(tri_b.vertex(A) + (tri_b.vertex(C) - tri_b.vertex(A)) * (dot_2a / (dot_2a - dot_2c)));
228
229 const t_vertex cross_normal = cross(normal_a, normal_b).template normalized<t_type>();
230
231 const t_type tp13 = dot(seg_a2 - seg_a1, cross_normal);
232 const t_type Ip1 = getMin(cast<t_type>(0), tp13);
233 const t_type Ip2 = getMax(cast<t_type>(0), tp13);
234
235 const t_type tq12 = dot(seg_b1 - seg_a1, cross_normal);
236 const t_type tq13 = dot(seg_b2 - seg_a1, cross_normal);
237
238 const t_type Iq1 = getMin(tq12, tq13);
239 const t_type Iq2 = getMax(tq12, tq13);
240
241
242 if (abs(Ip1 - Iq1) * 2 < ((Ip2 - Ip1) + (Iq2 - Iq1)))
243 {
244 t_type n_b = getMax(Ip1, Iq1);
245 t_type n_a = getMin(Ip2, Iq2);
246 if (n_a > n_b)
247 {
248 return LineSegment<t_dims, t_type, t_vertex>(seg_a1 + cross_normal * n_a, seg_a1 + cross_normal * n_b);
249 }
250 }
251 return Constant<LineSegment<t_dims, t_type, t_vertex>>::Invalid;
252 }
253
272 template<uint01 t_dims, class t_type, class t_vertex>
273 static LineSegment<t_dims, t_type, t_vertex> intersection(const Triangle<t_dims, t_type, t_vertex>& tri_a, const Plane<t_dims, t_type>& plane, t_type epsilon = 0)
274 {
275 UNUSED(epsilon);
276 const t_type signed_dist_a = plane.distanceTo(tri_a.vertex(A));
277 const t_type signed_dist_b = plane.distanceTo(tri_a.vertex(B));
278 const t_type signed_dist_c = plane.distanceTo(tri_a.vertex(C));
279 LineSegment<t_dims, t_type, t_vertex> seg = Constant<LineSegment<t_dims, t_type, t_vertex>>::Invalid;
280 uint01 seg_location = 0;
281
282 if (signed_dist_a == 0.0)
283 {
284 if (signed_dist_b == 0.0)
285 {
286 if (signed_dist_c != 0.0)
287 {
288 seg[A] = tri_a.vertex(A);
289 seg[B] = tri_a.vertex(B);
290 }//else is on same plane so return Invalid
291 return seg;
292 }
293 else if (signed_dist_c == 0.0)
294 {
295 seg[A] = tri_a.vertex(A);
296 seg[B] = tri_a.vertex(C);
297 return seg;
298 }
299 else
300 {
301 seg[seg_location++] = tri_a.vertex(A);
302 }
303 }
304 if (signed_dist_b == 0.0)
305 {
306 if (signed_dist_c == 0.0)
307 {
308 seg[A] = tri_a.vertex(B);
309 seg[B] = tri_a.vertex(C);
310 return seg;
311 }
312 seg[seg_location++] = tri_a.vertex(B);
313 }
314 if (signed_dist_c == 0.0)
315 {
316 seg[seg_location++] = tri_a.vertex(C);
317 }
318 if (signed_dist_a * signed_dist_b < 0)
319 {
320 t_type t = signed_dist_a / (signed_dist_a - signed_dist_b); // 'time' of intersection point on the segment
321 seg[seg_location++] = tri_a.vertex(A) + t * (tri_a.vertex(B) - tri_a.vertex(A));
322 }
323 if (signed_dist_b * signed_dist_c < 0)
324 {
325 t_type t = signed_dist_b / (signed_dist_b - signed_dist_c); // 'time' of intersection point on the segment
326 seg[seg_location++] = tri_a.vertex(B) + t * (tri_a.vertex(C) - tri_a.vertex(B));
327 }
328 if (signed_dist_c * signed_dist_a < 0)
329 {
330 t_type t = signed_dist_c / (signed_dist_c - signed_dist_a); // 'time' of intersection point on the segment
331 seg[seg_location++] = tri_a.vertex(C) + t * (tri_a.vertex(A) - tri_a.vertex(C));
332 }
333 return seg;
334 }
335 template<uint01 t_dims, class t_type, class t_vertex>
336 static LineSegment<t_dims, t_type, t_vertex> intersection(const Plane<t_dims, t_type>& plane, const Triangle<t_dims, t_type, t_vertex>& tri_a, t_type epsilon = 0)
337 {
338 return intersection(tri_a, plane, epsilon);
339 }
340
341
343
344 template<uint01 t_dims, class t_type>
345 IntersectionTypes classify(const Vector<t_dims, t_type>& v1, const Vector<t_dims, t_type>& v2)
346 {
347 if (v1 == v2)
348 return IntersectionTypes::e_mixed;
349 return IntersectionTypes::e_outside;
350 }
351
352 template<uint01 t_dims, class t_type, class t_vertex>
353 IntersectionTypes classify(const t_vertex& point, const Triangle<t_dims, t_type, t_vertex>& tri)
354 {
355 if (tri.contains(point))
356 return IntersectionTypes::e_mixed;
357 return IntersectionTypes::e_outside;
358 }
359 template<uint01 t_dims, class t_type, class t_vertex>
360 IntersectionTypes classify(const t_vertex& point, const Bounds<t_dims, t_type, t_vertex>& bounds)
361 {
362 if (bounds.contains(point))
363 return IntersectionTypes::e_mixed;
364 return IntersectionTypes::e_outside;
365 }
366 template<uint01 t_dims, class t_type, class t_vertex>
367 IntersectionTypes classify(const t_vertex& point, const RadialObject<t_dims, t_type, t_vertex>& rad)
368 {
369 if (rad.contains(point))
370 return IntersectionTypes::e_mixed;
371 return IntersectionTypes::e_outside;
372 }
373
374 template<class t_type, class t_vertex>
375 IntersectionTypes classify(const t_vertex& point, const Polygon<t_type, t_vertex>& polygon)
376 {
377 if (polygon.contains(point))
378 return IntersectionTypes::e_mixed;
379 return IntersectionTypes::e_outside;
380 }
382
383 template<uint01 t_dims, class t_type, class t_vertex>
384 IntersectionTypes classify(const LineSegment<t_dims, t_type, t_vertex>& line, const t_vertex& vertex)
385 {
386 if(distanceSquared(line, vertex) < intersection_epsilon)
387 return IntersectionTypes::e_inside;
388 return IntersectionTypes::e_outside;
389 }
390 template<uint01 t_dims, class t_type, class t_vertex>
391 IntersectionTypes classify(const t_vertex& vertex, const LineSegment<t_dims, t_type, t_vertex>& line)
392 {
393 if (distanceSquared(line, vertex) < intersection_epsilon)
394 return IntersectionTypes::e_inside;
395 return IntersectionTypes::e_outside;
396 }
397
398 template<uint01 t_dims, class t_type, class t_vertex>
399 IntersectionTypes classify(const LineSegment<t_dims, t_type, t_vertex>& left, const LineSegment<t_dims, t_type, t_vertex>& right)
400 {
401 if (distanceSquared(left, right[A]) < intersection_epsilon)
402 {
403 if (distanceSquared(left, right[B]) < intersection_epsilon)
404 return IntersectionTypes::e_inside;
405 else
406 return IntersectionTypes::e_mixed;
407 }
408 if (distanceSquared(left, right) < intersection_epsilon)
409 return IntersectionTypes::e_mixed;
410 return IntersectionTypes::e_outside;
411 }
412 template<uint01 t_dims, class t_type, class t_vertex>
413 IntersectionTypes classify(const LineSegment<t_dims, t_type, t_vertex>& line, const Triangle<t_dims, t_type, t_vertex>& tri)
414 {
415 t_type epsilon = cast<t_type>(0.0000001);
416 t_vertex edge_ba = tri.vertex(B) - tri.vertex(A);
417 t_vertex edge_ca = tri.vertex(C) - tri.vertex(A);
418 t_vertex dir = line.ray().template normalized<t_type>();
419 t_vertex pvec(cross(dir, edge_ca));
420 t_type det = dot(edge_ba, pvec);
421
422 // ray and triangle are parallel if det is close to 0
423 if (abs(det) < epsilon)
424 return IntersectionTypes::e_outside;
425 t_type invDet = cast<t_type>(1) / det;
426
427 t_vertex tvec = line.vertex(A) - tri.vertex(A);
428 t_type u = dot(tvec, pvec) * invDet;
429 if (u < cast<t_type>(0) || u > cast<t_type>(1))
430 return IntersectionTypes::e_outside;
431
432 t_vertex qvec(cross(tvec, edge_ba));
433 t_type v = dot(dir, qvec) * invDet;
434 if (v < cast<t_type>(0) || u + v > cast<t_type>(1))
435 return IntersectionTypes::e_outside;
436
437 t_type t = dot(edge_ca, qvec) * invDet;
438 if (t * t > line.lengthSquared())
439 return IntersectionTypes::e_outside;
440 return IntersectionTypes::e_mixed;
441 }
442 template<uint01 t_dims, class t_type, class t_vertex>
443 IntersectionTypes classify(const LineSegment<t_dims, t_type, t_vertex>& line, const Bounds<t_dims, t_type, t_vertex>& bounds)
444 {
445 return classify(bounds, line) == IntersectionTypes::e_outside ? IntersectionTypes::e_outside : IntersectionTypes::e_mixed;
446 }
447 template<uint01 t_dims, class t_type, class t_vertex>
448 IntersectionTypes classify(const LineSegment<t_dims, t_type, t_vertex>& line, const Polygon<t_type>& polygon)
449 {
450 return polygon.template contains<t_type>(line.template as<2, t_type>());
451 }
452
454 template<uint01 t_dims, class t_type, class t_vertex>
455 IntersectionTypes classify(const Plane<t_dims, t_type>& plane, const t_vertex& point)
456 {
457 if (plane.contains(point, cast<t_type>(0.0001)))
458 return IntersectionTypes::e_inside;
459 return IntersectionTypes::e_outside;
460 }
461
462 template<uint01 t_dims, class t_type, class t_vertex>
463 IntersectionTypes classify(const t_vertex& point, const Plane<t_dims, t_type>& plane)
464 {
465 if (plane.contains(point, cast<t_type>(0.0001)))
466 return IntersectionTypes::e_mixed;
467 return IntersectionTypes::e_outside;
468 }
469 template<uint01 t_dims, class t_type, class t_vertex>
470 IntersectionTypes classify(const Plane<t_dims, t_type>& plane, const LineSegment<t_dims, t_type, t_vertex>& line)
471 {
472 const PlanePosition position_a = plane.planePosition(line.vertex(A));
473 const PlanePosition position_b = plane.planePosition(line.vertex(B));
474 if (position_a == position_b)
475 {
476 if (position_a == PlanePosition::e_on_plane)
477 return IntersectionTypes::e_inside;
478 else
479 return IntersectionTypes::e_outside;
480 }
481 return IntersectionTypes::e_mixed;
482 }
483 template<uint01 t_dims, class t_type, class t_vertex>
484 IntersectionTypes classify(const LineSegment<t_dims, t_type, t_vertex>& line, const Plane<t_dims, t_type>& plane)
485 {
486 const PlanePosition position_a = plane.planePosition(line.vertex(A));
487 const PlanePosition position_b = plane.planePosition(line.vertex(B));
488 if (position_a == position_b)
489 {
490 if (position_a == PlanePosition::e_on_plane)
491 return IntersectionTypes::e_mixed;
492 else
493 return IntersectionTypes::e_outside;
494 }
495 return IntersectionTypes::e_mixed;
496 }
497
498
500 template<uint01 t_dims, class t_type, class t_vertex>
501 IntersectionTypes classify(const Triangle<t_dims, t_type, t_vertex>& tri, const t_vertex& point)
502 {
503 if (tri.contains(point))
504 return IntersectionTypes::e_inside;
505 return IntersectionTypes::e_outside;
506 }
507 template<uint01 t_dims, class t_type, class t_vertex>
508 IntersectionTypes classify(const Triangle<t_dims, t_type, t_vertex>& tri, const LineSegment<t_dims, t_type, t_vertex>& line)
509 {
510 if (IsInvalid(intersection(tri, line, cast<t_type>(intersection_epsilon))))
511 return IntersectionTypes::e_outside;
512 return IntersectionTypes::e_mixed;
513 }
514
515 template<uint01 t_dims, class t_type, class t_vertex>
516 IntersectionTypes classify(const Triangle<t_dims, t_type, t_vertex>& tri, const Polygon<t_type>& polygon)
517 {
518 return polygon.template contains<t_type>(tri.template as<2, t_type>());
519 }
520 template<uint01 t_dims, class t_type, class t_vertex>
521 IntersectionTypes classify(const Triangle<t_dims, t_type, t_vertex>& triangle, const Plane<t_dims, t_type>& plane)
522 {
523 const PlanePosition position_a = plane.planePosition(triangle.vertex(A));
524 const PlanePosition position_b = plane.planePosition(triangle.vertex(B));
525 const PlanePosition position_c = plane.planePosition(triangle.vertex(C));
526 if (position_a == position_b && position_a == position_c)
527 {
528 if (position_a == PlanePosition::e_on_plane)
529 return IntersectionTypes::e_mixed;
530 else
531 return IntersectionTypes::e_outside;
532 }
533 return IntersectionTypes::e_mixed;
534 }
535 template<uint01 t_dims, class t_type, class t_vertex>
536 IntersectionTypes classify(const Plane<t_dims, t_type>& plane, const Triangle<t_dims, t_type, t_vertex>& triangle)
537 {
538 const PlanePosition position_a = plane.planePosition(triangle.vertex(A));
539 const PlanePosition position_b = plane.planePosition(triangle.vertex(B));
540 const PlanePosition position_c = plane.planePosition(triangle.vertex(C));
541 if (position_a == position_b && position_a == position_c)
542 {
543 if (position_a == PlanePosition::e_on_plane)
544 return IntersectionTypes::e_inside;
545 else
546 return IntersectionTypes::e_outside;
547 }
548 return IntersectionTypes::e_mixed;
549 }
550
552
553 template<uint01 t_dims, class t_type, class t_vertex>
554 IntersectionTypes classify(const Bounds<t_dims, t_type, t_vertex>& bounds, const t_vertex& vertex)
555 {
556 if (bounds.contains(vertex))
557 return IntersectionTypes::e_inside;
558 return IntersectionTypes::e_outside;
559 }
560 template<uint01 t_dims, class t_type, class t_vertex>
561 IntersectionTypes classify(const Bounds<t_dims, t_type, t_vertex>& bounds, const LineSegment<t_dims, t_type, t_vertex>& line)
562 {
563 if (bounds.contains(line))
564 {
565 return IntersectionTypes::e_inside;
566 }
567 const Vertex<t_dims, t_type> ray = line.ray();
568 for (uint01 i = 0; i < t_dims; ++i)
569 {
570 if (bounds.doesIntersect(line.vertex(A)[i] - bounds[MIN][i], line.vertex(B)[i] - bounds[MIN][i], line.vertex(A), ray, i)
571 || bounds.doesIntersect(line.vertex(A)[i] - bounds[MAX][i], line.vertex(B)[i] - bounds[MAX][i], line.vertex(A), ray, i))
572 return IntersectionTypes::e_mixed;
573 }
574 return IntersectionTypes::e_outside;
575 }
576 template<uint01 t_dims, class t_type, class t_vertex>
577 IntersectionTypes classify(const Bounds<t_dims, t_type, t_vertex>& bounds, const Triangle<t_dims, t_type, t_vertex>& tri)
578 {
579 if (bounds.contains(tri))
580 return IntersectionTypes::e_inside;
581 else
582 {
583 const t_vertex min = getMin(tri.vertex(A), tri.vertex(B), tri.vertex(C));
584 const t_vertex max = getMax(tri.vertex(A), tri.vertex(B), tri.vertex(C));
585 for (uint01 i = 0; i < t_dims; i++)
586 {
587 if (min[i] > bounds[MAX][i] || max[i] < bounds[MIN][i])
588 return IntersectionTypes::e_outside;
589 }
590 }
591
592 const t_vertex bounds_center(bounds.center());
593 const Triangle<t_dims, t_type, t_vertex> centered_tri(
594 t_vertex(tri.vertex(A) - bounds_center)
595 , t_vertex(tri.vertex(B) - bounds_center)
596 , t_vertex(tri.vertex(C) - bounds_center));
597 const t_vertex half_span(bounds.span() / cast<t_type>(2));
598 const t_vertex edge[3] = { centered_tri.edge(A, B).ray(), centered_tri.edge(B, C).ray(), centered_tri.edge(C, A).ray() };
599 for (uint01 edge_index = 0; edge_index < 3; ++edge_index)
600 {
601 const t_vertex cur_edge = edge[edge_index];
602 const t_vertex abs_edge = abs(edge[edge_index]);
603 for (uint01 i = 0; i < 3; ++i)
604 {
605 t_type val_a;
606 t_type val_b;
607 t_type radius;
608 switch (i)
609 {
610 case 0:
611 val_a = cur_edge[Z] * centered_tri.vertex(A)[Y] - cur_edge[Y] * centered_tri.vertex(A)[Z];
612 val_b = cur_edge[Z] * centered_tri.vertex(C)[Y] - cur_edge[Y] * centered_tri.vertex(C)[Z];
613 radius = abs_edge[Z] * half_span[Y] + abs_edge[Y] * half_span[Z];
614 break;
615 case 1:
616 val_a = -cur_edge[Z] * centered_tri.vertex(A)[X] + cur_edge[X] * centered_tri.vertex(A)[Z];
617 val_b = -cur_edge[Z] * centered_tri.vertex(C)[X] + cur_edge[X] * centered_tri.vertex(C)[Z];
618 radius = abs_edge[Z] * half_span[X] + abs_edge[X] * half_span[Z];
619 break;
620 case 2:
621 default:
622 val_a = cur_edge[Y] * centered_tri.vertex(B)[X] - cur_edge[X] * centered_tri.vertex(B)[Y];
623 val_b = cur_edge[Y] * centered_tri.vertex(C)[X] - cur_edge[X] * centered_tri.vertex(C)[Y];
624 radius = abs_edge[Y] * half_span[X] + abs_edge[X] * half_span[Y];
625 break;
626 }
627 if (val_a < val_b)
628 {
629 if (val_a > radius || val_b < -radius)
630 return IntersectionTypes::e_outside;
631 }
632 else
633 {
634 if (val_b > radius || val_a < -radius)
635 return IntersectionTypes::e_outside;
636 }
637 }
638 }
639 const t_vertex normal = cross(edge[0], edge[1]);
640 t_vertex vertex_min;
641 t_vertex vertex_max;
642 for (uint01 i = 0; i < 3; i++)
643 {
644 t_type vertex_a_val = centered_tri.vertex(A)[i];
645 if (normal[i] > cast<t_type>(0))
646 {
647 vertex_min[i] = -half_span[i] - vertex_a_val;
648 vertex_max[i] = half_span[i] - vertex_a_val;
649 }
650 else
651 {
652 vertex_min[i] = half_span[i] - vertex_a_val;
653 vertex_max[i] = -half_span[i] - vertex_a_val;
654 }
655 }
656 if (dot(normal, vertex_min) > cast<t_type>(0) || dot(normal, vertex_max) < cast<t_type>(0))
657 return IntersectionTypes::e_outside;
658 return IntersectionTypes::e_mixed;
659 }
660 template<uint01 t_dims, class t_type, class t_vertex>
661 IntersectionTypes classify(const Bounds<t_dims, t_type, t_vertex>& left, const Bounds<t_dims, t_type, t_vertex>& right)
662 {
663 bool is_inside = true;
664 for (uint01 dim = 0; dim < t_dims; ++dim)
665 {
666 if (!(right[MIN][dim] >= left[MIN][dim]))
667 {
668 if (!(right[MAX][dim] >= left[MIN][dim]))
669 return IntersectionTypes::e_outside;
670 is_inside = false;
671 }
672 if (!(right[MAX][dim] <= left[MAX][dim]))
673 {
674 if (!(right[MIN][dim] <= left[MAX][dim]))
675 return IntersectionTypes::e_outside;
676 is_inside = false;
677 }
678 }
679 if (is_inside)
680 return IntersectionTypes::e_inside;
681 return IntersectionTypes::e_mixed;
682 }
683 template<uint01 t_dims, class t_type, class t_vertex>
684 IntersectionTypes classify(const Bounds<t_dims, t_type, t_vertex>& bounds, const RadialObject<t_dims, t_type, t_vertex>& radial)
685 {
686 const t_vertex center = radial.center();
687
688 uint01 inside_dims = 0;
689 t_type sqr_dist = cast<t_type>(0);
690
691 for (uint01 dim = 0; dim < t_dims; ++dim)
692 {
693 if (center[dim] < bounds[MIN][dim])
694 sqr_dist += (bounds[MIN][dim] - center[dim]) * (bounds[MIN][dim] - center[dim]);
695 else if (center[dim] > bounds[MAX][dim])
696 sqr_dist += (center[dim] - bounds[MAX][dim]) * (center[dim] - bounds[MAX][dim]);
697 else if (center[dim] >= bounds[MIN] + radial.radius() && center[dim] <= bounds[MAX][dim] - radial.radius())
698 inside_dims++;
699 }
700 if (inside_dims == t_dims)
701 return IntersectionTypes::e_inside;
702 if (sqr_dist > radial.radius() * radial.radius())
703 return IntersectionTypes::e_outside;
704 return IntersectionTypes::e_mixed;
705 }
706
707
708
709 template<uint01 t_dims, class t_type, class t_vertex>
710 IntersectionTypes classify(const Bounds<t_dims, t_type, t_vertex>& bounds, const Polygon<t_type>& polygon)
711 {
712 return polygon.template contains<t_type>(bounds.template as<2, t_type>());
713 }
714
715
716 template<uint01 t_dims, class t_type, class t_vertex>
717 IntersectionTypes classify(const Bounds<t_dims, t_type, t_vertex>& bounds, const Plane<t_dims, t_type>& plane)
718 {
719 t_vertex c = bounds.center(); // Compute AABB center
720 t_vertex e = bounds[MAX] - c; // Compute positive extents
721
722 // Compute the projection interval radius of b onto L(t) = b.c + t * p.n
723 t_type r = (e * abs(plane.normal)).sum();
724
725 // Compute distance of box center from plane
726 t_type s = dot(plane.normal, c) - plane.d;
727
728 // Intersection occurs when distance s falls within [-r,+r] interval
729 if (abs(s) <= r)
730 return IntersectionTypes::e_mixed;
731 else
732 return IntersectionTypes::e_outside;
733 }
734
735 template<uint01 t_dims, class t_type, class t_vertex>
736 IntersectionTypes classify(const Plane<t_dims, t_type>& plane, const Bounds<t_dims, t_type, t_vertex>& bounds)
737 {
738 return classify(bounds, plane);
739 }
740
742 template<uint01 t_dims, class t_type, class t_vertex>
743 IntersectionTypes classify(const RadialObject<t_dims, t_type, t_vertex>& rad, const t_vertex& vector)
744 {
745 if (rad.contains(vector))
746 return IntersectionTypes::e_inside;
747 return IntersectionTypes::e_outside;
748 }
749
750 template<uint01 t_dims, class t_type, class t_vertex>
751 IntersectionTypes classify(const RadialObject<t_dims, t_type, t_vertex>& radial, const Bounds<t_dims, t_type, t_vertex>& bounds)
752 {
753 t_type max_tot(0);
754 t_type min_tot(0);
755 for (uint01 i = 0; i < t_dims; i++)
756 {
757 const t_type cir_center = radial.center()[i];
758 const t_type dist_max = (bounds[MAX][i] - cir_center) * (bounds[MAX][i] - cir_center);
759 const t_type dist_min = (bounds[MIN][i] - cir_center) * (bounds[MIN][i] - cir_center);
760 if (dist_max > dist_min)
761 {
762 max_tot += dist_max;
763 if (cir_center < bounds[MIN][i])
764 min_tot += dist_min;
765 }
766 else
767 {
768 max_tot += dist_min;
769 if (cir_center > bounds[MAX][i])
770 min_tot += dist_max;
771 }
772 }
773 const t_type rad_squared = radial.radius() * radial.radius();
774 if (max_tot < rad_squared)
775 return IntersectionTypes::e_inside;
776 if (min_tot < rad_squared)
777 return IntersectionTypes::e_mixed;
778 return IntersectionTypes::e_outside;
779 }
780 template<uint01 t_dims, class t_type, class t_vertex>
781 IntersectionTypes classify(const RadialObject<t_dims, t_type, t_vertex>& radial, const Plane<t_dims, t_type>& plane)
782 {
783 t_vertex c = radial.center(); // Compute AABB
784 if (radial.radius() >= plane.distanceTo(c))
785 return IntersectionTypes::e_mixed;
786 else
787 return IntersectionTypes::e_outside;
788 }
789 template<uint01 t_dims, class t_type, class t_vertex>
790 IntersectionTypes classify(const Plane<t_dims, t_type>& plane, const RadialObject<t_dims, t_type, t_vertex>& radial)
791 {
792 return classify(radial, plane);
793 }
794
795 template<class t_type, class t_vertex>
796 IntersectionTypes classify(const Polygon<t_type, t_vertex>& polygon, const t_vertex& vector)
797 {
798 if (polygon.contains(vector))
799 return IntersectionTypes::e_inside;
800 return IntersectionTypes::e_outside;
801 }
802
803
804 template<uint01 t_dims, class t_type, class t_vertex>
805 IntersectionTypes classify(const Polygon<t_type>& polygon, const Bounds<t_dims, t_type, t_vertex>& bounds)
806 {
807 return polygon.template contains<t_type>(bounds.template as<2, t_type>());
808 }
809
810
811 template<uint01 t_dims, class t_type, class t_vertex>
812 IntersectionTypes classify(const Polygon<t_type>& polygon, const Triangle<t_dims, t_type, t_vertex>& tri)
813 {
814 return polygon.template contains<t_type>(tri.template as<2, t_type>());
815 }
816
817
818 template<uint01 t_dims, class t_type, class t_vertex>
819 IntersectionTypes classify(const Polygon<t_type>& polygon, const LineSegment<t_dims, t_type, t_vertex>& line)
820 {
821 return polygon.template contains<t_type>(line.template as<2, t_type>());
822 }
823
824
825
826}
827
Bounds
A specification of upper and lower bounds in N-dimensions.
Definition Bounds.hpp:54
Intersection
Dummy class for including intersection functions.
Definition Intersection.hpp:45
LineSegment
Class: LineSegment.
Definition Line.hpp:52
LineSegment::lengthSquared
constexpr t_type lengthSquared() const
Definition Line.hpp:462
LineSegment::vertex
constexpr const t_vertex & vertex(uint01 index) const
Definition Line.hpp:155
LineSegment::ray
constexpr t_vertex ray() const
Definition Line.hpp:123
Plane
Logic for a given plane or N-dimensions.
Definition Plane.hpp:53
Polygon
An N-sided polygon.
Definition Polygon.hpp:55
RadialObject
A radial object.
Definition RadialObject.hpp:52
Triangle
A three-vertex polygon representing a triangle in N-dimensional space.
Definition Triangle.hpp:142
Triangle::vertex
constexpr t_vertex & vertex(TriangleLocation triangle_node)
Vertices the given triangle node.
Definition Triangle.hpp:172
Triangle::edge
constexpr LineSegment< t_dims, t_type, t_vertex > edge(uint01 triangle_node_a, uint01 triangle_node_b) const
Definition Triangle.hpp:260
Vector
A fixed-size array with N dimensions used as the basis for geometric and mathematical types.
Definition Vector.hpp:62
Vertex
A point in N-dimensional space, used primarily for spatial location information.
Definition Vertex.hpp:44
NDEVR
The primary namespace for the NDEVR SDK.
Definition ArialTileFetcherModule.h:35
getMin
constexpr t_type getMin(const t_type &left, const t_type &right)
Finds the minimum of the given arguments based on the < operator Author: Tyler Parke Date: 2017-11-05...
Definition BaseFunctions.hpp:56
getMax
constexpr t_type getMax(const t_type &left, const t_type &right)
Finds the max of the given arguments using the > operator The only requirement is that t_type have > ...
Definition BaseFunctions.hpp:94
IsValid
static constexpr bool IsValid(const Angle< t_type > &value)
Checks whether the given Angle holds a valid value.
Definition Angle.h:398
PlanePosition
PlanePosition
The location of an object either below, above, or on a given N-dimensional plane.
Definition Plane.hpp:42
dot
t_type dot(const Vector< t_dims, t_type > &v1, const Vector< t_dims, t_type > &v2)
Definition VectorFunctions.hpp:1031
abs
constexpr Angle< t_angle_type > abs(const Angle< t_angle_type > &value)
Changes an input with a negative sign, to a positive sign.
Definition AngleFunctions.h:753
intersection
static Bounds< t_dims, t_type, t_vertex > intersection(const Bounds< t_dims, t_type, t_vertex > &bounds_1, const Bounds< t_dims, t_type, t_vertex > &bounds_2)
Given two bounds, returns the intersection between the two of them.
Definition Intersection.hpp:64
fltp08
double fltp08
Defines an alias representing an 8 byte floating-point number.
Definition BaseValues.hpp:150
cross
constexpr Vector< 1, t_type > cross(const Vector< 1, t_type > &, const Vector< 1, t_type > &)
Definition VectorFunctions.hpp:899
uint01
uint8_t uint01
-Defines an alias representing a 1 byte, unsigned integer -Can represent exact integer values 0 throu...
Definition BaseValues.hpp:81
IsInvalid
static constexpr bool IsInvalid(const Angle< t_type > &value)
Checks whether the given Angle holds an invalid value.
Definition Angle.h:388
IntersectionTypes
IntersectionTypes
Used for classifying shape intersections.
Definition BaseValues.hpp:238
cast
constexpr t_to cast(const Angle< t_from > &value)
Casts an Angle from one backing type to another.
Definition Angle.h:408
Constant
Defines for a given type (such as sint04, fltp08, UUID, etc) a maximum, minimum, and reserved 'invali...
Definition BaseValues.hpp:261