GteIntrIntervals.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/GteFIQuery.h>
11 #include <Mathematics/GteTIQuery.h>
12 #include <array>
13 #include <limits>
14 
15 namespace gte
16 {
17 
18 // The intervals are [u0,u1] and [v0,v1], where u0 <= u1 and v0 <= v1, and
19 // where the endpoints are any finite floating-point numbers. Degenerate
20 // intervals are allowed (u0 = u1 or v0 = v1). The queries do not perform
21 // validation on the input intervals. In the comments, maxReal refers to
22 // std::numeric_limits<Real>::max().
23 
24 template <typename Real>
25 class TIQuery<Real, std::array<Real,2>, std::array<Real,2>>
26 {
27 public:
28  // The query tests overlap, whether a single point or an entire interval.
29  struct Result
30  {
31  bool intersect;
32 
33  // Dynamic queries (intervals moving with constant speeds). If
34  // 'intersect' is true, the contact times are valid and
35  // 0 <= firstTime <= lastTime, firstTime <= maxTime
36  // If 'intersect' is false, there are two cases reported. If the
37  // intervals will intersect at firstTime > maxTime, the contact times
38  // are reported just as when 'intersect' is true. However, if the
39  // intervals will not intersect, then firstTime = maxReal and
40  // lastTime = -maxReal.
41  Real firstTime, lastTime;
42  };
43 
44  // Static query.
45  Result operator()(std::array<Real, 2> const& interval0,
46  std::array<Real, 2> const& interval1);
47 
48  // Dynamic query. Current time is 0, maxTime > 0 is required.
49  Result operator()(Real maxTime, std::array<Real, 2> const& interval0,
50  Real speed0, std::array<Real, 2> const& interval1, Real speed1);
51 };
52 
53 template <typename Real>
54 class FIQuery<Real, std::array<Real, 2>, std::array<Real, 2>>
55 {
56 public:
57  // The query finds overlap, whether a single point or an entire interval.
58  struct Result
59  {
60  bool intersect;
61 
62  // Static queries (no motion of intervals over time). The number of
63  // number of intersections is 0 (no overlap), 1 (intervals are just
64  // touching), or 2 (intervals overlap in an interval). If 'intersect'
65  // is false, numIntersections is 0 and 'overlap' is set to
66  // [maxReal,-maxReal]. If 'intersect' is true, numIntersections is
67  // 1 or 2. When 1, 'overlap' is set to [x,x], which is degenerate and
68  // represents the single intersection point x. When 2, 'overlap' is
69  // the interval of intersection.
70  int numIntersections;
71  std::array<Real, 2> overlap;
72 
73  // Dynamic queries (intervals moving with constant speeds). If
74  // 'intersect' is true, the contact times are valid and
75  // 0 <= firstTime <= lastTime, firstTime <= maxTime
76  // If 'intersect' is false, there are two cases reported. If the
77  // intervals will intersect at firstTime > maxTime, the contact times
78  // are reported just as when 'intersect' is true. However, if the
79  // intervals will not intersect, then firstTime = maxReal and
80  // lastTime = -maxReal.
81  Real firstTime, lastTime;
82  };
83 
84  // Static query.
85  Result operator()(std::array<Real, 2> const& interval0,
86  std::array<Real, 2> const& interval1);
87 
88  // Dynamic query. Current time is 0, maxTime > 0 is required.
89  Result operator()(Real maxTime, std::array<Real, 2> const& interval0,
90  Real speed0, std::array<Real, 2> const& interval1, Real speed1);
91 };
92 
93 // Template aliases for convenience.
94 template <typename Real>
95 using TIIntervalInterval =
96 TIQuery<Real, std::array<Real, 2>, std::array<Real, 2>>;
97 
98 template <typename Real>
99 using FIIntervalInterval =
100 FIQuery<Real, std::array<Real, 2>, std::array<Real, 2>>;
101 
102 
103 template <typename Real>
104 typename TIQuery<Real, std::array<Real, 2>, std::array<Real, 2>>::Result
105 TIQuery<Real, std::array<Real, 2>, std::array<Real, 2>>::operator()(
106  std::array<Real, 2> const& interval0,
107  std::array<Real, 2> const& interval1)
108 {
109  Result result;
110  result.intersect =
111  interval0[0] <= interval1[1] && interval0[1] >= interval1[0];
112  return result;
113 }
114 
115 template <typename Real>
116 typename TIQuery<Real, std::array<Real, 2>, std::array<Real, 2>>::Result
117 TIQuery<Real, std::array<Real, 2>, std::array<Real, 2>>::operator()(
118  Real maxTime, std::array<Real, 2> const& interval0, Real speed0,
119  std::array<Real, 2> const& interval1, Real speed1)
120 {
121  Result result;
122 
123  if (interval0[1] < interval1[0])
124  {
125  // interval0 initially to the left of interval1.
126  Real diffSpeed = speed0 - speed1;
127  if (diffSpeed > (Real)0)
128  {
129  // The intervals must move towards each other. 'intersect' is
130  // true when the intervals will intersect by maxTime.
131  Real diffPos = interval1[0] - interval0[1];
132  Real invDiffSpeed = ((Real)1) / diffSpeed;
133  result.intersect = (diffPos <= maxTime*diffSpeed);
134  result.firstTime = diffPos*invDiffSpeed;
135  result.lastTime = (interval1[1] - interval0[0])*invDiffSpeed;
136  return result;
137  }
138  }
139  else if (interval0[0] > interval1[1])
140  {
141  // interval0 initially to the right of interval1.
142  Real diffSpeed = speed1 - speed0;
143  if (diffSpeed > (Real)0)
144  {
145  // The intervals must move towards each other. 'intersect' is
146  // true when the intervals will intersect by maxTime.
147  Real diffPos = interval0[0] - interval1[1];
148  Real invDiffSpeed = ((Real)1) / diffSpeed;
149  result.intersect = (diffPos <= maxTime*diffSpeed);
150  result.firstTime = diffPos*invDiffSpeed;
151  result.lastTime = (interval0[1] - interval1[0])*invDiffSpeed;
152  return result;
153  }
154  }
155  else
156  {
157  // The intervals are initially intersecting.
158  result.intersect = true;
159  result.firstTime = (Real)0;
160  if (speed1 > speed0)
161  {
162  result.lastTime = (interval0[1] - interval1[0])/(speed1 - speed0);
163  }
164  else if (speed1 < speed0)
165  {
166  result.lastTime = (interval1[1] - interval0[0])/(speed0 - speed1);
167  }
168  else
169  {
170  result.lastTime = std::numeric_limits<Real>::max();
171  }
172  return result;
173  }
174 
175  result.intersect = false;
176  result.firstTime = std::numeric_limits<Real>::max();
177  result.lastTime = -std::numeric_limits<Real>::max();
178  return result;
179 }
180 
181 
182 
183 template <typename Real>
184 typename FIQuery<Real, std::array<Real, 2>, std::array<Real, 2>>::Result
185 FIQuery<Real, std::array<Real, 2>, std::array<Real, 2>>::operator()(
186  std::array<Real, 2> const& interval0,
187  std::array<Real, 2> const& interval1)
188 {
189  Result result;
190  result.firstTime = std::numeric_limits<Real>::max();
191  result.lastTime = -std::numeric_limits<Real>::max();
192 
193  if (interval0[1] < interval1[0] || interval0[0] > interval1[1])
194  {
195  result.numIntersections = 0;
196  result.overlap[0] = std::numeric_limits<Real>::max();
197  result.overlap[1] = -std::numeric_limits<Real>::max();
198  }
199  else if (interval0[1] > interval1[0])
200  {
201  if (interval0[0] < interval1[1])
202  {
203  result.numIntersections = 2;
204  result.overlap[0] =
205  (interval0[0] < interval1[0] ? interval1[0] : interval0[0]);
206  result.overlap[1] =
207  (interval0[1] > interval1[1] ? interval1[1] : interval0[1]);
208  if (result.overlap[0] == result.overlap[1])
209  {
210  result.numIntersections = 1;
211  }
212  }
213  else // interval0[0] == interval1[1]
214  {
215  result.numIntersections = 1;
216  result.overlap[0] = interval0[0];
217  result.overlap[1] = result.overlap[0];
218  }
219  }
220  else // interval0[1] == interval1[0]
221  {
222  result.numIntersections = 1;
223  result.overlap[0] = interval0[1];
224  result.overlap[1] = result.overlap[0];
225  }
226 
227  result.intersect = (result.numIntersections > 0);
228  return result;
229 }
230 
231 template <typename Real>
232 typename FIQuery<Real, std::array<Real, 2>, std::array<Real, 2>>::Result
233 FIQuery<Real, std::array<Real, 2>, std::array<Real, 2>>::operator()(
234  Real maxTime, std::array<Real, 2> const& interval0, Real speed0,
235  std::array<Real, 2> const& interval1, Real speed1)
236 {
237  Result result;
238 
239  if (interval0[1] < interval1[0])
240  {
241  // interval0 initially to the left of interval1.
242  Real diffSpeed = speed0 - speed1;
243  if (diffSpeed > (Real)0)
244  {
245  // The intervals must move towards each other. 'intersect' is
246  // true when the intervals will intersect by maxTime.
247  Real diffPos = interval1[0] - interval0[1];
248  Real invDiffSpeed = ((Real)1) / diffSpeed;
249  result.intersect = (diffPos <= maxTime*diffSpeed);
250  result.numIntersections = 1;
251  result.firstTime = diffPos*invDiffSpeed;
252  result.lastTime = (interval1[1] - interval0[0])*invDiffSpeed;
253  result.overlap[0] = interval0[0] + result.firstTime*speed0;
254  result.overlap[1] = result.overlap[0];
255  return result;
256  }
257  }
258  else if (interval0[0] > interval1[1])
259  {
260  // interval0 initially to the right of interval1.
261  Real diffSpeed = speed1 - speed0;
262  if (diffSpeed > (Real)0)
263  {
264  // The intervals must move towards each other. 'intersect' is
265  // true when the intervals will intersect by maxTime.
266  Real diffPos = interval0[0] - interval1[1];
267  Real invDiffSpeed = ((Real)1) / diffSpeed;
268  result.intersect = (diffPos <= maxTime*diffSpeed);
269  result.numIntersections = 1;
270  result.firstTime = diffPos*invDiffSpeed;
271  result.lastTime = (interval0[1] - interval1[0])*invDiffSpeed;
272  result.overlap[0] = interval1[1] + result.firstTime*speed1;
273  result.overlap[1] = result.overlap[0];
274  return result;
275  }
276  }
277  else
278  {
279  // The intervals are initially intersecting.
280  result.intersect = true;
281  result.firstTime = (Real)0;
282  if (speed1 > speed0)
283  {
284  result.lastTime = (interval0[1] - interval1[0]) / (speed1 - speed0);
285  }
286  else if (speed1 < speed0)
287  {
288  result.lastTime = (interval1[1] - interval0[0]) / (speed0 - speed1);
289  }
290  else
291  {
292  result.lastTime = std::numeric_limits<Real>::max();
293  }
294 
295  if (interval0[1] > interval1[0])
296  {
297  if (interval0[0] < interval1[1])
298  {
299  result.numIntersections = 2;
300  result.overlap[0] = (interval0[0] < interval1[0] ?
301  interval1[0] : interval0[0]);
302  result.overlap[1] = (interval0[1] > interval1[1] ?
303  interval1[1] : interval0[1]);
304  }
305  else // interval0[0] == interval1[1]
306  {
307  result.numIntersections = 1;
308  result.overlap[0] = interval0[0];
309  result.overlap[1] = result.overlap[0];
310  }
311  }
312  else // interval0[1] == interval1[0]
313  {
314  result.numIntersections = 1;
315  result.overlap[0] = interval0[1];
316  result.overlap[1] = result.overlap[0];
317  }
318  return result;
319  }
320 
321  result.intersect = false;
322  result.numIntersections = 0;
323  result.overlap[0] = std::numeric_limits<Real>::max();
324  result.overlap[1] = -std::numeric_limits<Real>::max();
325  result.firstTime = std::numeric_limits<Real>::max();
326  result.lastTime = -std::numeric_limits<Real>::max();
327  return result;
328 }
329 
330 
331 }
array
GLenum array
Definition: glext.h:6669
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