1 // Copyright (c) 2009 INRIA Sophia-Antipolis (France).
2 // All rights reserved.
3 //
4 // This file is part of CGAL (www.cgal.org)
5 //
6 // $URL: https://github.com/CGAL/cgal/blob/v5.3/Intersections_3/include/CGAL/Intersections_3/internal/Triangle_3_Line_3_intersection.h $
7 // $Id: Triangle_3_Line_3_intersection.h 0779373 2020-03-26T13:31:46+01:00 Sébastien Loriot
8 // SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-Commercial
9 //
10 //
11 // Author(s) : Stéphane Tayeb
12 //
13 // Note : This implementation is adapted from Triangle_3_Line_3_do_intersect.h.
14
15 #ifndef CGAL_INTERNAL_INTERSECTIONS_3_TRIANGLE_3_LINE_3_INTERSECTION_H
16 #define CGAL_INTERNAL_INTERSECTIONS_3_TRIANGLE_3_LINE_3_INTERSECTION_H
17
18 #include <CGAL/Intersections_3/Line_3_Plane_3.h>
19
20 namespace CGAL {
21
22 namespace Intersections {
23
24 namespace internal {
25
26 template <class K>
27 typename K::Point_3
t3l3_intersection_coplanar_aux(const typename K::Line_3 & l,const typename K::Point_3 & a,const typename K::Point_3 & b,const K & k)28 t3l3_intersection_coplanar_aux(const typename K::Line_3& l,
29 const typename K::Point_3& a,
30 const typename K::Point_3& b,
31 const K& k)
32 {
33 // Returns the intersection point between line l and segment [a,b]
34 //
35 // preconditions:
36 // + l,a,b are coplanar
37
38 typedef typename K::Point_3 Point_3;
39 typedef typename K::Vector_3 Vector_3;
40 typedef typename K::FT FT;
41
42 typename K::Construct_vector_3 vector =
43 k.construct_vector_3_object();
44
45 typename K::Construct_cross_product_vector_3 cross_product =
46 k.construct_cross_product_vector_3_object();
47
48 typename K::Compute_scalar_product_3 scalar_product =
49 k.compute_scalar_product_3_object();
50
51 typename K::Compute_squared_length_3 sq_length =
52 k.compute_squared_length_3_object();
53
54 const Point_3& p = l.point();
55 const Vector_3& v = l.to_vector();
56 const Vector_3 ab = vector(a,b);
57 const Vector_3 pa = vector(p,a);
58
59 const Vector_3 pa_ab = cross_product(pa,ab);
60 const Vector_3 v_ab = cross_product(v,ab);
61
62 const FT t = scalar_product(pa_ab,v_ab) / sq_length(v_ab);
63
64 return ( p + t*v );
65 }
66
67
68 template <class K>
69 typename K::Segment_3
t3l3_intersection_coplanar_aux(const typename K::Point_3 & a,const typename K::Point_3 & b,const typename K::Point_3 & c,const typename K::Line_3 & l,const bool negative_side,const K & k)70 t3l3_intersection_coplanar_aux(const typename K::Point_3& a,
71 const typename K::Point_3& b,
72 const typename K::Point_3& c,
73 const typename K::Line_3& l,
74 const bool negative_side,
75 const K& k)
76 {
77 // This function is designed to clip pq into the triangle abc.
78 // Point configuration should be as follows
79 //
80 // |
81 // | +b
82 // |
83 // +c | +a
84 // |
85 // | l
86 //
87 // We know that c is isolated on the negative side of pq
88
89 typedef typename K::Point_3 Point_3;
90
91 typename K::Construct_segment_3 segment =
92 k.construct_segment_3_object();
93
94 // Let's get the intersection points
95 const Point_3 l_bc = t3l3_intersection_coplanar_aux(l,b,c,k);
96 const Point_3 l_ca = t3l3_intersection_coplanar_aux(l,c,a,k);
97
98 if ( negative_side )
99 return segment(l_bc, l_ca);
100 else
101 return segment(l_ca, l_bc);
102 }
103
104
105 template <class K>
106 typename Intersection_traits<K, typename K::Triangle_3, typename K::Line_3>::result_type
intersection_coplanar(const typename K::Triangle_3 & t,const typename K::Line_3 & l,const K & k)107 intersection_coplanar(const typename K::Triangle_3 &t,
108 const typename K::Line_3 &l,
109 const K & k )
110 {
111 CGAL_kernel_precondition( ! k.is_degenerate_3_object()(t) ) ;
112 CGAL_kernel_precondition( ! k.is_degenerate_3_object()(l) ) ;
113
114 typedef typename K::Point_3 Point_3;
115
116 typename K::Construct_point_on_3 point_on =
117 k.construct_point_on_3_object();
118
119 typename K::Construct_vertex_3 vertex_on =
120 k.construct_vertex_3_object();
121
122 typename K::Coplanar_orientation_3 coplanar_orientation =
123 k.coplanar_orientation_3_object();
124
125 typename K::Construct_segment_3 segment =
126 k.construct_segment_3_object();
127
128 const Point_3 & p = point_on(l,0);
129 const Point_3 & q = point_on(l,1);
130
131 const Point_3 & A = vertex_on(t,0);
132 const Point_3 & B = vertex_on(t,1);
133 const Point_3 & C = vertex_on(t,2);
134
135 int k0 = 0;
136 int k1 = 1;
137 int k2 = 2;
138
139 // Determine the orientation of the triangle in the common plane
140 if (coplanar_orientation(A,B,C) != POSITIVE)
141 {
142 // The triangle is not counterclockwise oriented
143 // swap two vertices.
144 std::swap(k1,k2);
145 }
146
147 const Point_3& a = vertex_on(t,k0);
148 const Point_3& b = vertex_on(t,k1);
149 const Point_3& c = vertex_on(t,k2);
150
151 // Test whether the line intersects the triangle in the common plane
152 const Orientation pqa = coplanar_orientation(p,q,a);
153 const Orientation pqb = coplanar_orientation(p,q,b);
154 const Orientation pqc = coplanar_orientation(p,q,c);
155
156 switch ( pqa ) {
157 // -----------------------------------
158 // pqa POSITIVE
159 // -----------------------------------
160 case POSITIVE:
161 switch ( pqb ) {
162 case POSITIVE:
163 switch ( pqc ) {
164 case POSITIVE:
165 // the triangle lies in the positive halfspace
166 // defined by the segment's supporting line.
167 return intersection_return<typename K::Intersect_3, typename K::Triangle_3, typename K::Line_3>();
168 case NEGATIVE:
169 // c is isolated on the negative side
170 return intersection_return<typename K::Intersect_3, typename K::Triangle_3, typename K::Line_3>(t3l3_intersection_coplanar_aux(a,b,c,l,true,k));
171 default: // COLLINEAR
172 return intersection_return<typename K::Intersect_3, typename K::Triangle_3, typename K::Line_3>(c);
173 }
174
175 case NEGATIVE:
176 if ( POSITIVE == pqc )
177 // b is isolated on the negative side
178 return intersection_return<typename K::Intersect_3, typename K::Triangle_3, typename K::Line_3>(t3l3_intersection_coplanar_aux(c,a,b,l,true,k));
179 else
180 // a is isolated on the positive side (here mb c could be use as
181 // an endpoint instead of computing an intersection is some cases)
182 return intersection_return<typename K::Intersect_3, typename K::Triangle_3, typename K::Line_3>(t3l3_intersection_coplanar_aux(b,c,a,l,false,k));
183
184 case COLLINEAR:
185 switch ( pqc ) {
186 case POSITIVE:
187 return intersection_return<typename K::Intersect_3, typename K::Triangle_3, typename K::Line_3>((b));
188 case NEGATIVE:
189 // a is isolated on the positive side (here mb b could be use as
190 // an endpoint instead of computing an intersection)
191 return intersection_return<typename K::Intersect_3, typename K::Triangle_3, typename K::Line_3>(t3l3_intersection_coplanar_aux(b,c,a,l,false,k));
192 default: // COLLINEAR
193 // b,c,p,q are aligned, [p,q]&[b,c] have the same direction
194 return intersection_return<typename K::Intersect_3, typename K::Triangle_3, typename K::Line_3>((segment(b,c)));
195 }
196
197 default: // should not happen.
198 CGAL_error();
199 return intersection_return<typename K::Intersect_3, typename K::Triangle_3, typename K::Line_3>();
200 }
201
202 // -----------------------------------
203 // pqa NEGATIVE
204 // -----------------------------------
205 case NEGATIVE:
206 switch ( pqb ) {
207 case POSITIVE:
208 if ( POSITIVE == pqc )
209 // a is isolated on the negative side
210 return intersection_return<typename K::Intersect_3, typename K::Triangle_3, typename K::Line_3>(t3l3_intersection_coplanar_aux(b,c,a,l,true,k));
211 else
212 // b is isolated on the positive side (here mb c could be use as
213 // an endpoint instead of computing an intersection, in some cases)
214 return intersection_return<typename K::Intersect_3, typename K::Triangle_3, typename K::Line_3>(t3l3_intersection_coplanar_aux(c,a,b,l,false,k));
215
216 case NEGATIVE:
217 switch ( pqc ) {
218 case POSITIVE:
219 // c is isolated on the positive side
220 return intersection_return<typename K::Intersect_3, typename K::Triangle_3, typename K::Line_3>(t3l3_intersection_coplanar_aux(a,b,c,l,false,k));
221 case NEGATIVE:
222 // the triangle lies in the negative halfspace
223 // defined by the segment's supporting line.
224 return intersection_return<typename K::Intersect_3, typename K::Triangle_3, typename K::Line_3>();
225 default: // COLLINEAR
226 return intersection_return<typename K::Intersect_3, typename K::Triangle_3, typename K::Line_3>(c);
227 }
228
229 case COLLINEAR:
230 switch ( pqc ) {
231 case POSITIVE:
232 // a is isolated on the negative side (here mb b could be use as
233 // an endpoint instead of computing an intersection)
234 return intersection_return<typename K::Intersect_3, typename K::Triangle_3, typename K::Line_3>(t3l3_intersection_coplanar_aux(b,c,a,l,true,k));
235 case NEGATIVE:
236 return intersection_return<typename K::Intersect_3, typename K::Triangle_3, typename K::Line_3>(b);
237 default: // COLLINEAR
238 // b,c,p,q are aligned, [p,q]&[c,b] have the same direction
239 return intersection_return<typename K::Intersect_3, typename K::Triangle_3, typename K::Line_3>(segment(c,b));
240 }
241
242 default: // should not happen.
243 CGAL_error();
244 return intersection_return<typename K::Intersect_3, typename K::Triangle_3, typename K::Line_3>();
245 }
246
247 // -----------------------------------
248 // pqa COLLINEAR
249 // -----------------------------------
250 case COLLINEAR:
251 switch ( pqb ) {
252 case POSITIVE:
253 switch ( pqc ) {
254 case POSITIVE:
255 return intersection_return<typename K::Intersect_3, typename K::Triangle_3, typename K::Line_3>(a);
256 case NEGATIVE:
257 // b is isolated on the positive side (here mb a could be use as
258 // an endpoint instead of computing an intersection)
259 return intersection_return<typename K::Intersect_3, typename K::Triangle_3, typename K::Line_3>(t3l3_intersection_coplanar_aux(c,a,b,l,false,k));
260 default: // COLLINEAR
261 // a,c,p,q are aligned, [p,q]&[c,a] have the same direction
262 return intersection_return<typename K::Intersect_3, typename K::Triangle_3, typename K::Line_3>(segment(c,a));
263 }
264
265 case NEGATIVE:
266 switch ( pqc ) {
267 case POSITIVE:
268 // b is isolated on the negative side (here mb a could be use as
269 // an endpoint instead of computing an intersection)
270 return intersection_return<typename K::Intersect_3, typename K::Triangle_3, typename K::Line_3>(t3l3_intersection_coplanar_aux(c,a,b,l,true,k));
271 case NEGATIVE:
272 return intersection_return<typename K::Intersect_3, typename K::Triangle_3, typename K::Line_3>(a);
273 default: // COLLINEAR:
274 // a,c,p,q are aligned, [p,q]&[a,c] have the same direction
275 return intersection_return<typename K::Intersect_3, typename K::Triangle_3, typename K::Line_3>(segment(a,c));
276 }
277
278 case COLLINEAR:
279 switch ( pqc ) {
280 case POSITIVE:
281 // a,b,p,q are aligned, [p,q]&[a,b] have the same direction
282 return intersection_return<typename K::Intersect_3, typename K::Triangle_3, typename K::Line_3>(segment(a,b));
283 case NEGATIVE:
284 // a,b,p,q are aligned, [p,q]&[b,a] have the same direction
285 return intersection_return<typename K::Intersect_3, typename K::Triangle_3, typename K::Line_3>(segment(b,a));
286 default: // COLLINEAR
287 // case pqc == COLLINEAR is impossible since the triangle is
288 // assumed to be non flat
289 CGAL_error();
290 return intersection_return<typename K::Intersect_3, typename K::Triangle_3, typename K::Line_3>();
291 }
292
293 default: // should not happen.
294 CGAL_error();
295 return intersection_return<typename K::Intersect_3, typename K::Triangle_3, typename K::Line_3>();
296 }
297
298 default:// should not happen.
299 CGAL_error();
300 return intersection_return<typename K::Intersect_3, typename K::Triangle_3, typename K::Line_3>();
301 }
302 }
303
304
305 template <class K>
306 inline
307 typename CGAL::Intersection_traits<K, typename K::Line_3, typename K::Triangle_3>::result_type
t3l3_intersection_aux(const typename K::Triangle_3 & t,const typename K::Line_3 & l,const K &)308 t3l3_intersection_aux(const typename K::Triangle_3 &t,
309 const typename K::Line_3 &l,
310 const K&)
311 {
312 // typename K::Intersect_3 intersection =
313 // k.intersect_3_object();
314
315 // The intersection between a Line and Plane is either Point or Line
316 typename Intersection_traits<K, typename K::Line_3, typename K::Plane_3>::result_type
317 v = internal::intersection(l,t.supporting_plane(), K());
318
319 // Intersection should be a point (because of orientation test done before)
320 if(v) {
321 if(const typename K::Point_3* p = intersect_get<typename K::Point_3>(v)) {
322 return intersection_return<typename K::Intersect_3, typename K::Triangle_3, typename K::Line_3>(*p);
323 } else {
324 return intersection_return<typename K::Intersect_3, typename K::Triangle_3, typename K::Line_3>();
325 }
326 } else {
327 return intersection_return<typename K::Intersect_3, typename K::Triangle_3, typename K::Line_3>();
328 }
329 }
330
331
332 template <class K>
333 typename CGAL::Intersection_traits<K, typename K::Line_3, typename K::Triangle_3>::result_type
intersection(const typename K::Triangle_3 & t,const typename K::Line_3 & l,const K & k)334 intersection(const typename K::Triangle_3 &t,
335 const typename K::Line_3 &l,
336 const K& k)
337 {
338 CGAL_kernel_precondition( ! k.is_degenerate_3_object()(t) ) ;
339 CGAL_kernel_precondition( ! k.is_degenerate_3_object()(l) ) ;
340
341 typedef typename K::Point_3 Point_3;
342
343 typename K::Construct_point_on_3 point_on =
344 k.construct_point_on_3_object();
345
346 typename K::Construct_vertex_3 vertex_on =
347 k.construct_vertex_3_object();
348
349 typename K::Orientation_3 orientation =
350 k.orientation_3_object();
351
352 const Point_3 & a = vertex_on(t,0);
353 const Point_3 & b = vertex_on(t,1);
354 const Point_3 & c = vertex_on(t,2);
355 const Point_3 & p = point_on(l,0);
356 const Point_3 & q = point_on(l,1);
357
358 if ( ( orientation(a,b,c,p) != COPLANAR )
359 || ( orientation(a,b,c,q) != COPLANAR ) )
360 {
361 const Orientation pqab = orientation(p,q,a,b);
362 const Orientation pqbc = orientation(p,q,b,c);
363 switch ( pqab ) {
364 case POSITIVE:
365 if ( pqbc != NEGATIVE && orientation(p,q,c,a) != NEGATIVE )
366 return t3l3_intersection_aux(t,l,k);
367 else
368 return intersection_return<typename K::Intersect_3, typename K::Line_3, typename K::Triangle_3>();
369
370 case NEGATIVE:
371 if ( pqbc != POSITIVE && orientation(p,q,c,a) != POSITIVE )
372 return t3l3_intersection_aux(t,l,k);
373 else
374 return intersection_return<typename K::Intersect_3, typename K::Line_3, typename K::Triangle_3>();
375
376 case COPLANAR:
377 switch ( pqbc ) {
378 case POSITIVE:
379 if ( orientation(p,q,c,a) != NEGATIVE )
380 return t3l3_intersection_aux(t,l,k);
381 else
382 return intersection_return<typename K::Intersect_3, typename K::Line_3, typename K::Triangle_3>();
383
384 case NEGATIVE:
385 if ( orientation(p,q,c,a) != POSITIVE )
386 return t3l3_intersection_aux(t,l,k);
387 else
388 return intersection_return<typename K::Intersect_3, typename K::Line_3, typename K::Triangle_3>();
389
390 default: // COPLANAR: // pqa or pqb or pqc are collinear
391 return t3l3_intersection_aux(t,l,k);
392
393 }
394
395 default: // should not happen.
396 CGAL_error();
397 return intersection_return<typename K::Intersect_3, typename K::Line_3, typename K::Triangle_3>();
398 }
399 }
400
401 // Coplanar case
402 return intersection_coplanar(t,l,k);
403 }
404
405 template <class K>
406 typename CGAL::Intersection_traits<K, typename K::Line_3, typename K::Triangle_3>::result_type
intersection(const typename K::Line_3 & l,const typename K::Triangle_3 & t,const K & k)407 intersection(const typename K::Line_3 &l,
408 const typename K::Triangle_3 &t,
409 const K& k)
410 {
411 return internal::intersection(t,l,k);
412 }
413
414
415 } // end namespace internal
416 } // namespace Intersections
417 } // end namespace CGAL
418
419 #endif // CGAL_INTERNAL_INTERSECTIONS_3_TRIANGLE_3_LINE_3_INTERSECTION_H
420