GteIntrPlane3Triangle3.h
Go to the documentation of this file.
1 // David Eberly, Geometric Tools, Redmond WA 98052
2 // Copyright (c) 1998-2017
3 // Distributed under the Boost Software License, Version 1.0.
4 // http://www.boost.org/LICENSE_1_0.txt
5 // http://www.geometrictools.com/License/Boost/LICENSE_1_0.txt
6 // File Version: 3.0.0 (2016/06/19)
7 
8 #pragma once
9 
10 #include <Mathematics/GteVector3.h>
11 #include <Mathematics/GteHyperplane.h>
12 #include <Mathematics/GteTriangle.h>
13 #include <Mathematics/GteFIQuery.h>
14 #include <Mathematics/GteTIQuery.h>
15 
16 namespace gte
17 {
18 
19 template <typename Real>
20 class TIQuery<Real, Plane3<Real>, Triangle3<Real>>
21 {
22 public:
23  struct Result
24  {
25  bool intersect;
26 
27  // The number is 0 (no intersection), 1 (plane and triangle intersect
28  // at a single point [vertex]), 2 (plane and triangle intersect in a
29  // segment), or 3 (triangle is in the plane). When the number is 2,
30  // the segment is either interior to the triangle or is an edge of the
31  // triangle, the distinction stored in 'isInterior'.
32  int numIntersections;
33  bool isInterior;
34  };
35 
36  Result operator()(Plane3<Real> const& plane,
37  Triangle3<Real> const& triangle);
38 };
39 
40 template <typename Real>
41 class FIQuery<Real, Plane3<Real>, Triangle3<Real>>
42 {
43 public:
44  struct Result
45  {
46  bool intersect;
47 
48  // The number is 0 (no intersection), 1 (plane and triangle intersect
49  // at a single point [vertex]), 2 (plane and triangle intersect in a
50  // segment), or 3 (triangle is in the plane). When the number is 2,
51  // the segment is either interior to the triangle or is an edge of the
52  // triangle, the distinction stored in 'isInterior'.
53  int numIntersections;
54  bool isInterior;
55  Vector3<Real> point[3];
56  };
57 
58  Result operator()(Plane3<Real> const& plane,
59  Triangle3<Real> const& triangle);
60 };
61 
62 
63 template <typename Real>
64 typename TIQuery<Real, Plane3<Real>, Triangle3<Real>>::Result
65 TIQuery<Real, Plane3<Real>, Triangle3<Real>>::operator()(
66  Plane3<Real> const& plane, Triangle3<Real> const& triangle)
67 {
68  Result result;
69 
70  // Determine on which side of the plane the vertices lie. The table of
71  // possibilities is listed next with n = numNegative, p = numPositive, and
72  // z = numZero.
73  //
74  // n p z intersection
75  // ------------------------------------
76  // 0 3 0 none
77  // 0 2 1 vertex
78  // 0 1 2 edge
79  // 0 0 3 triangle in the plane
80  // 1 2 0 segment (2 edges clipped)
81  // 1 1 1 segment (1 edge clipped)
82  // 1 0 2 edge
83  // 2 1 0 segment (2 edges clipped)
84  // 2 0 1 vertex
85  // 3 0 0 none
86 
87  Real s[3];
88  int numPositive = 0, numNegative = 0, numZero = 0;
89  for (int i = 0; i < 3; ++i)
90  {
91  s[i] = Dot(plane.normal, triangle.v[i]) - plane.constant;
92  if (s[i] >(Real)0)
93  {
94  ++numPositive;
95  }
96  else if (s[i] < (Real)0)
97  {
98  ++numNegative;
99  }
100  else
101  {
102  ++numZero;
103  }
104  }
105 
106  if (numZero == 0 && numPositive > 0 && numNegative > 0)
107  {
108  result.intersect = true;
109  result.numIntersections = 2;
110  result.isInterior = true;
111  return result;
112  }
113 
114  if (numZero == 1)
115  {
116  result.intersect = true;
117  for (int i = 0; i < 3; ++i)
118  {
119  if (s[i] == (Real)0)
120  {
121  if (numPositive == 2 || numNegative == 2)
122  {
123  result.numIntersections = 1;
124  }
125  else
126  {
127  result.numIntersections = 2;
128  result.isInterior = true;
129  }
130  break;
131  }
132  }
133  return result;
134  }
135 
136  if (numZero == 2)
137  {
138  result.intersect = true;
139  result.numIntersections = 2;
140  result.isInterior = false;
141  return result;
142  }
143 
144  if (numZero == 3)
145  {
146  result.intersect = true;
147  result.numIntersections = 3;
148  }
149  else
150  {
151  result.intersect = false;
152  result.numIntersections = 0;
153 
154  }
155  return result;
156 }
157 
158 
159 
160 template <typename Real>
161 typename FIQuery<Real, Plane3<Real>, Triangle3<Real>>::Result
162 FIQuery<Real, Plane3<Real>, Triangle3<Real>>::operator()(
163  Plane3<Real> const& plane, Triangle3<Real> const& triangle)
164 {
165  Result result;
166 
167  // Determine on which side of the plane the vertices lie. The table of
168  // possibilities is listed next with n = numNegative, p = numPositive, and
169  // z = numZero.
170  //
171  // n p z intersection
172  // ------------------------------------
173  // 0 3 0 none
174  // 0 2 1 vertex
175  // 0 1 2 edge
176  // 0 0 3 triangle in the plane
177  // 1 2 0 segment (2 edges clipped)
178  // 1 1 1 segment (1 edge clipped)
179  // 1 0 2 edge
180  // 2 1 0 segment (2 edges clipped)
181  // 2 0 1 vertex
182  // 3 0 0 none
183 
184  Real s[3];
185  int numPositive = 0, numNegative = 0, numZero = 0;
186  for (int i = 0; i < 3; ++i)
187  {
188  s[i] = Dot(plane.normal, triangle.v[i]) - plane.constant;
189  if (s[i] >(Real)0)
190  {
191  ++numPositive;
192  }
193  else if (s[i] < (Real)0)
194  {
195  ++numNegative;
196  }
197  else
198  {
199  ++numZero;
200  }
201  }
202 
203  if (numZero == 0 && numPositive > 0 && numNegative > 0)
204  {
205  result.intersect = true;
206  result.numIntersections = 2;
207  result.isInterior = true;
208  Real sign = (Real)3 - numPositive * (Real)2;
209  for (int i0 = 0; i0 < 3; ++i0)
210  {
211  if (sign * s[i0] >(Real)0)
212  {
213  int i1 = (i0 + 1) % 3, i2 = (i0 + 2) % 3;
214  Real t1 = s[i1] / (s[i1] - s[i0]);
215  Real t2 = s[i2] / (s[i2] - s[i0]);
216  result.point[0] = triangle.v[i1] + t1 *
217  (triangle.v[i0] - triangle.v[i1]);
218  result.point[1] = triangle.v[i2] + t2 *
219  (triangle.v[i0] - triangle.v[i2]);
220  break;
221  }
222  }
223  return result;
224  }
225 
226  if (numZero == 1)
227  {
228  result.intersect = true;
229  for (int i0 = 0; i0 < 3; ++i0)
230  {
231  if (s[i0] == (Real)0)
232  {
233  int i1 = (i0 + 1) % 3, i2 = (i0 + 2) % 3;
234  result.point[0] = triangle.v[i0];
235  if (numPositive == 2 || numNegative == 2)
236  {
237  result.numIntersections = 1;
238  }
239  else
240  {
241  result.numIntersections = 2;
242  result.isInterior = true;
243  Real t = s[i1] / (s[i1] - s[i2]);
244  result.point[1] = triangle.v[i1] + t *
245  (triangle.v[i2] - triangle.v[i1]);
246  }
247  break;
248  }
249  }
250  return result;
251  }
252 
253  if (numZero == 2)
254  {
255  result.intersect = true;
256  result.numIntersections = 2;
257  result.isInterior = false;
258  for (int i0 = 0; i0 < 3; ++i0)
259  {
260  if (s[i0] != (Real)0)
261  {
262  int i1 = (i0 + 1) % 3, i2 = (i0 + 2) % 3;
263  result.point[0] = triangle.v[i1];
264  result.point[1] = triangle.v[i2];
265  break;
266  }
267  }
268  return result;
269  }
270 
271  if (numZero == 3)
272  {
273  result.intersect = true;
274  result.numIntersections = 3;
275  result.point[0] = triangle.v[0];
276  result.point[1] = triangle.v[1];
277  result.point[2] = triangle.v[2];
278  }
279  else
280  {
281  result.intersect = false;
282  result.numIntersections = 0;
283 
284  }
285  return result;
286 }
287 
288 
289 }
t1
GLuint GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat t1
Definition: glext.h:9013
gte::Dot
DualQuaternion< Real > Dot(DualQuaternion< Real > const &d0, DualQuaternion< Real > const &d1)
t
GLdouble GLdouble t
Definition: glext.h:239
s
GLdouble s
Definition: glext.h:231
gte::TIQuery::operator()
Result operator()(Type0 const &primitive0, Type1 const &primitive1)
result
GLuint64EXT * result
Definition: glext.h:10003

geometric_tools_engine
Author(s): Yijiang Huang
autogenerated on Thu Jul 18 2019 04:00:00