HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_GeometryPredicate.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * COMMENTS:
7  * This code comes from public domain C code for "Fast Robust Predicates
8  * for Computational Geometry" from
9  * http://www.cs.cmu.edu/~quake/robust.html
10  * that provides precise inside/outside tests for lines, planes, circles,
11  * and spheres.
12  *
13  * It is based on the papers
14  * Adaptive Precision Floating-Point Arithmetic and Fast Robust
15  * Geometric Predicates
16  * and
17  * Robust Adaptive Floating-Point Geometric Predicates
18  */
19 
20 #ifndef __UT_GeometryPredicate_h__
21 #define __UT_GeometryPredicate_h__
22 
23 #include "UT_API.h"
24 #include "UT_Vector2.h"
25 #include "UT_Vector3.h"
26 
27 /// Use the following class in places where you can specify the bounding box of
28 /// all the points you will use with these geometry predicates. If the bounding
29 /// box is not known, use the functions at the global scope (note that those will
30 /// be slower since there are additional static filters based on the bounding box
31 /// size used in this class.
32 
33 template<typename REAL, bool USEFILTER = true, bool EXACT = true>
35 {
36 public:
37  // constructors just call exactinit
38  UT_GeometryPredicates(const UT_Vector3T<REAL> &bbox_size);
39  UT_GeometryPredicates(const REAL bbox_size[3]);
40 
41  UT_GeometryPredicates(); // filters uninitialized, must call exactinit with proper bounding box
42 
43  void exactinit(const UT_Vector3T<REAL> &bbox_size);
44  void exactinit(const REAL bbox_size[3]);
45  void exactinit(); // filters are disabled with this initializer
46 
47  // Does point c lie on, to the left of, or to the right of line ab?
48  REAL orient2d(
49  const UT_Vector2T<REAL> &pa,
50  const UT_Vector2T<REAL> &pb,
51  const UT_Vector2T<REAL> &pc) const
52  { return orient2d(pa.data(), pb.data(), pc.data()); }
53  REAL orient2d(
54  const REAL pa[2],
55  const REAL pb[2],
56  const REAL pc[2]) const;
57 
58  // Does point d lie on, to the left of, or to the right of the plane containing
59  // the points a, b, and c?
60  REAL orient3d(
61  const UT_Vector3T<REAL> &pa,
62  const UT_Vector3T<REAL> &pb,
63  const UT_Vector3T<REAL> &pc,
64  const UT_Vector3T<REAL> &pd) const
65  { return orient3d(pa.data(), pb.data(), pc.data(), pd.data()); }
66  REAL orient3d(
67  const REAL pa[3],
68  const REAL pb[3],
69  const REAL pc[3],
70  const REAL pd[3]) const;
71 
72  // Does point d lie on, inside, or outside of the circle containing the points
73  // a, b, and c?
74  REAL incircle(
75  const UT_Vector2T<REAL> &pa,
76  const UT_Vector2T<REAL> &pb,
77  const UT_Vector2T<REAL> &pc,
78  const UT_Vector2T<REAL> &pd) const
79  { return incircle(pa.data(), pb.data(), pc.data(), pd.data()); }
80  REAL incircle(
81  const REAL pa[2],
82  const REAL pb[2],
83  const REAL pc[2],
84  const REAL pd[2]) const;
85 
86  // Does point e lie on, inside, or outside of the sphere containing the points
87  // a, b, c, and d?
88  REAL insphere(
89  const UT_Vector3T<REAL> &pa,
90  const UT_Vector3T<REAL> &pb,
91  const UT_Vector3T<REAL> &pc,
92  const UT_Vector3T<REAL> &pd,
93  const UT_Vector3T<REAL> &pe) const
94  { return insphere(pa.data(), pb.data(), pc.data(), pd.data(), pe.data()); }
95  REAL insphere(
96  const REAL pa[3],
97  const REAL pb[3],
98  const REAL pc[3],
99  const REAL pd[3],
100  const REAL pe[3]) const;
101 
102  // Does point e lie on, to the left of, or to the right of the hyperplane containing
103  // the points a, b, c, and d?
104  REAL orient4d(
105  const UT_Vector3T<REAL> &pa,
106  const UT_Vector3T<REAL> &pb,
107  const UT_Vector3T<REAL> &pc,
108  const UT_Vector3T<REAL> &pd,
109  const UT_Vector3T<REAL> &pe,
110  REAL ah, REAL bh, REAL ch, REAL dh, REAL eh) const
111  { return orient4d(pa.data(), pb.data(), pc.data(), pd.data(), pe.data(), ah,bh,ch,dh,eh); }
112  REAL orient4d(
113  const REAL pa[3],
114  const REAL pb[3],
115  const REAL pc[3],
116  const REAL pd[3],
117  const REAL pe[3],
118  REAL ah, REAL bh, REAL ch, REAL dh, REAL eh) const;
119 
120 protected:
121  /* splitter = 2^ceiling(p / 2) + 1. Used to split floats in half. */
122  REAL splitter;
123  REAL epsilon; /* = 2^(-p). Used to estimate roundoff errors. */
124  /* A set of coefficients used to calculate maximum roundoff errors. */
126  REAL ccwerrboundA, ccwerrboundB, ccwerrboundC;
127  REAL o3derrboundA, o3derrboundB, o3derrboundC;
128  REAL iccerrboundA, iccerrboundB, iccerrboundC;
129  REAL isperrboundA, isperrboundB, isperrboundC;
130 
131  // Additional predicate specific static filters
132  REAL filter1, filter2;
133 };
134 
137 
138 /// Function interface for geometric predicates.
139 /// More efficient predicates are availble through the UT_GeometryPredicates
140 /// class that defines a more thorough static filter
141 namespace UT_GeometryPredicate
142 {
143 
144 // Get the default instantiation of the predicate context (this is convenient
145 // when defining your own predicate dependent functions)
146 template<typename REAL>
148 
149 #define SPECIALIZE_GET_DEFAULT(REAL) \
150 template<> \
151 SYS_FORCE_INLINE \
152 const UT_GeometryPredicates<REAL,false,true>& \
153 getDefault<REAL>() { return ut_global_predicates_##REAL; }
154 
157 
158 // Does point c lie on, to the left of, or to the right of line ab?
159 template<typename REAL>
161 REAL orient2d(
162  const REAL pa[2],
163  const REAL pb[2],
164  const REAL pc[2])
165 { return getDefault<REAL>().orient2d(pa,pb,pc); }
166 template<typename REAL>
168 REAL orient2d(
169  const UT_Vector2T<REAL> &pa,
170  const UT_Vector2T<REAL> &pb,
171  const UT_Vector2T<REAL> &pc)
172 { return getDefault<REAL>().orient2d(pa,pb,pc); }
173 
174 // Does point d lie on, to the left of, or to the right of the plane containing
175 // the points a, b, and c?
176 template<typename REAL>
178 REAL orient3d(
179  const REAL pa[3],
180  const REAL pb[3],
181  const REAL pc[3],
182  const REAL pd[3])
183 { return getDefault<REAL>().orient3d(pa,pb,pc,pd); }
184 template<typename REAL>
186 REAL orient3d(
187  const UT_Vector3T<REAL> &pa,
188  const UT_Vector3T<REAL> &pb,
189  const UT_Vector3T<REAL> &pc,
190  const UT_Vector3T<REAL> &pd)
191 { return getDefault<REAL>().orient3d(pa,pb,pc,pd); }
192 
193 // Does point d lie one, inside, or outside of the circle containing the points
194 // a, b, and c?
195 template<typename REAL>
197 REAL incircle(
198  const REAL pa[2],
199  const REAL pb[2],
200  const REAL pc[2],
201  const REAL pd[2])
202 { return getDefault<REAL>().incircle(pa,pb,pc,pd); }
203 template<typename REAL>
205 REAL incircle(
206  const UT_Vector2T<REAL> &pa,
207  const UT_Vector2T<REAL> &pb,
208  const UT_Vector2T<REAL> &pc,
209  const UT_Vector2T<REAL> &pd)
210 { return getDefault<REAL>().incircle(pa,pb,pc,pd); }
211 
212 // Does point e lie one, inside, or outside of the sphere containing the points
213 // a, b, c, and d?
214 template<typename REAL>
216 REAL insphere(
217  const REAL pa[3],
218  const REAL pb[3],
219  const REAL pc[3],
220  const REAL pd[3],
221  const REAL pe[3])
222 { return getDefault<REAL>().insphere(pa,pb,pc,pd,pe); }
223 template<typename REAL>
225 REAL insphere(
226  const UT_Vector3T<REAL> &pa,
227  const UT_Vector3T<REAL> &pb,
228  const UT_Vector3T<REAL> &pc,
229  const UT_Vector3T<REAL> &pd,
230  const UT_Vector3T<REAL> &pe)
231 { return getDefault<REAL>().insphere(pa,pb,pc,pd,pe); }
232 
233 // Does point e lie on, to the left of, or to the right of the hyperplane containing
234 // the points a, b, c, and d?
235 template<typename REAL>
237 REAL orient4d(
238  const REAL pa[3],
239  const REAL pb[3],
240  const REAL pc[3],
241  const REAL pd[3],
242  const REAL pe[3],
243  REAL ah, REAL bh, REAL ch, REAL dh, REAL eh)
244 { return getDefault<REAL>().orient4d(pa,pb,pc,pd,pe,ah,bh,ch,dh,eh); }
245 template<typename REAL>
247 REAL orient4d(
248  const UT_Vector3T<REAL> &pa,
249  const UT_Vector3T<REAL> &pb,
250  const UT_Vector3T<REAL> &pc,
251  const UT_Vector3T<REAL> &pd,
252  const UT_Vector3T<REAL> &pe,
253  REAL ah, REAL bh, REAL ch, REAL dh, REAL eh)
254 { return getDefault<REAL>().orient4d(pa,pb,pc,pd,pe,ah,bh,ch,dh,eh); }
255 
256 } // end of namespace UT_GeometryPredicate
257 
258 template<typename REAL, bool USEFILTER>
261  const UT_Vector3T<REAL> &v1,
262  const UT_Vector3T<REAL> &v2,
264 {
265  // compute the cross product with exact signs
266  typedef UT_Vector2T<REAL> Vec2;
267  return UT_Vector3T<REAL>(
268  pred.orient2d( Vec2(v1.y(), v1.z()),
269  Vec2(v2.y(), v2.z()),
270  Vec2(0,0) ),
271  pred.orient2d( Vec2(v1.z(), v1.x()),
272  Vec2(v2.z(), v2.x()),
273  Vec2(0,0) ),
274  pred.orient2d( Vec2(v1.x(), v1.y()),
275  Vec2(v2.x(), v2.y()),
276  Vec2(0,0) ));
277 }
278 
279 template<typename REAL>
282  const UT_Vector3T<REAL> &v1,
283  const UT_Vector3T<REAL> &v2)
284 {
285  return UTcrossExact<REAL,false>(v1,v2, UT_GeometryPredicate::getDefault<REAL>());
286 }
287 
288 // Does point c lie on, to the left of, or to the right of line ab?
291  const UT_Vector2 &a,
292  const UT_Vector2 &b,
293  const UT_Vector2 &c)
294 {
295  double pa[2] = {a[0], a[1]};
296  double pb[2] = {b[0], b[1]};
297  double pc[2] = {c[0], c[1]};
298  return UT_GeometryPredicate::orient2d<fpreal64>(pa, pb, pc);
299 }
302  const UT_Vector2D &pa,
303  const UT_Vector2D &pb,
304  const UT_Vector2D &pc)
305 {
306  return UT_GeometryPredicate::orient2d<fpreal64>(pa.data(), pb.data(), pc.data());
307 }
310  const double pa[2],
311  const double pb[2],
312  const double pc[2])
313 {
314  return UT_GeometryPredicate::orient2d<fpreal64>(pa, pb, pc);
315 }
316 // Does point d lie on, to the left of, or to the right of the plane containing
317 // the points a, b, and c?
320  const UT_Vector3 &a,
321  const UT_Vector3 &b,
322  const UT_Vector3 &c,
323  const UT_Vector3 &d)
324 {
325  double pa[3] = {a[0], a[1], a[2]};
326  double pb[3] = {b[0], b[1], b[2]};
327  double pc[3] = {c[0], c[1], c[2]};
328  double pd[3] = {d[0], d[1], d[2]};
329  return UT_GeometryPredicate::orient3d<fpreal64>(pa, pb, pc, pd);
330 }
333  const UT_Vector3D &pa,
334  const UT_Vector3D &pb,
335  const UT_Vector3D &pc,
336  const UT_Vector3D &pd)
337 {
338  return UT_GeometryPredicate::orient3d<fpreal64>(pa.data(), pb.data(), pc.data(), pd.data());
339 }
342  const double pa[3],
343  const double pb[3],
344  const double pc[3],
345  const double pd[3])
346 {
347  return UT_GeometryPredicate::orient3d<fpreal64>(pa, pb, pc, pd);
348 }
349 
350 // Does point d lie one, inside, or outside of the circle containing the points
351 // a, b, and c?
354  const UT_Vector2 &a,
355  const UT_Vector2 &b,
356  const UT_Vector2 &c,
357  const UT_Vector2 &d)
358 {
359  double pa[2] = {a[0], a[1]};
360  double pb[2] = {b[0], b[1]};
361  double pc[2] = {c[0], c[1]};
362  double pd[2] = {d[0], d[1]};
363  return UT_GeometryPredicate::incircle<fpreal64>(pa, pb, pc, pd);
364 }
367  const UT_Vector2D &pa,
368  const UT_Vector2D &pb,
369  const UT_Vector2D &pc,
370  const UT_Vector2D &pd)
371 {
372  return UT_GeometryPredicate::incircle<fpreal64>(pa.data(), pb.data(),
373  pc.data(), pd.data());
374 }
377  const double pa[2],
378  const double pb[2],
379  const double pc[2],
380  const double pd[2])
381 {
382  return UT_GeometryPredicate::incircle<fpreal64>(pa, pb, pc, pd);
383 }
384 
385 // Does point e lie one, inside, or outside of the sphere containing the points
386 // a, b, c, and d?
389  const UT_Vector3 &a,
390  const UT_Vector3 &b,
391  const UT_Vector3 &c,
392  const UT_Vector3 &d,
393  const UT_Vector3 &e)
394 {
395  double pa[3] = {a[0], a[1], a[2]};
396  double pb[3] = {b[0], b[1], b[2]};
397  double pc[3] = {c[0], c[1], c[2]};
398  double pd[3] = {d[0], d[1], d[2]};
399  double pe[3] = {e[0], e[1], e[2]};
400  return UT_GeometryPredicate::insphere<fpreal64>(pa, pb, pc, pd, pe);
401 }
404  const UT_Vector3D &pa,
405  const UT_Vector3D &pb,
406  const UT_Vector3D &pc,
407  const UT_Vector3D &pd,
408  const UT_Vector3D &pe)
409 {
410  return UT_GeometryPredicate::insphere<fpreal64>(pa.data(), pb.data(), pc.data(),
411  pd.data(), pe.data());
412 }
415  const double pa[3],
416  const double pb[3],
417  const double pc[3],
418  const double pd[3],
419  const double pe[3])
420 {
421  return UT_GeometryPredicate::insphere<fpreal64>(pa, pb, pc, pd, pe);
422 }
423 
424 #endif // __UT_GeometryPredicate_h__
SYS_FORCE_INLINE REAL orient3d(const UT_Vector3T< REAL > &pa, const UT_Vector3T< REAL > &pb, const UT_Vector3T< REAL > &pc, const UT_Vector3T< REAL > &pd)
REAL incircle(const UT_Vector2T< REAL > &pa, const UT_Vector2T< REAL > &pb, const UT_Vector2T< REAL > &pc, const UT_Vector2T< REAL > &pd) const
REAL orient3d(const UT_Vector3T< REAL > &pa, const UT_Vector3T< REAL > &pb, const UT_Vector3T< REAL > &pc, const UT_Vector3T< REAL > &pd) const
#define SYS_DEPRECATED_HDK_REPLACE(__V__, __R__)
constexpr SYS_FORCE_INLINE T & z() noexcept
Definition: UT_Vector3.h:667
#define SPECIALIZE_GET_DEFAULT(REAL)
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1222
SYS_FORCE_INLINE double UTgeometryPredicateIncircle(const UT_Vector2 &a, const UT_Vector2 &b, const UT_Vector2 &c, const UT_Vector2 &d)
SYS_FORCE_INLINE REAL insphere(const UT_Vector3T< REAL > &pa, const UT_Vector3T< REAL > &pb, const UT_Vector3T< REAL > &pc, const UT_Vector3T< REAL > &pd, const UT_Vector3T< REAL > &pe)
#define UT_API
Definition: UT_API.h:14
GLfloat GLfloat GLfloat v2
Definition: glcorearb.h:818
SYS_FORCE_INLINE REAL orient4d(const REAL pa[3], const REAL pb[3], const REAL pc[3], const REAL pd[3], const REAL pe[3], REAL ah, REAL bh, REAL ch, REAL dh, REAL eh)
SYS_FORCE_INLINE REAL incircle(const UT_Vector2T< REAL > &pa, const UT_Vector2T< REAL > &pb, const UT_Vector2T< REAL > &pc, const UT_Vector2T< REAL > &pd)
3D Vector class.
2D Vector class.
Definition: UT_Vector2.h:159
float fpreal32
Definition: SYS_Types.h:200
constexpr SYS_FORCE_INLINE const T * data() const noexcept
Definition: UT_Vector3.h:292
double fpreal64
Definition: SYS_Types.h:201
SYS_FORCE_INLINE REAL orient3d(const REAL pa[3], const REAL pb[3], const REAL pc[3], const REAL pd[3])
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
REAL orient2d(const UT_Vector2T< REAL > &pa, const UT_Vector2T< REAL > &pb, const UT_Vector2T< REAL > &pc) const
constexpr SYS_FORCE_INLINE const T * data() const noexcept
Definition: UT_Vector2.h:217
SYS_FORCE_INLINE double UTgeometryPredicateOrient2d(const UT_Vector2 &a, const UT_Vector2 &b, const UT_Vector2 &c)
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1222
UT_API const UT_GeometryPredicates< fpreal64, false, true > ut_global_predicates_fpreal64
REAL orient4d(const UT_Vector3T< REAL > &pa, const UT_Vector3T< REAL > &pb, const UT_Vector3T< REAL > &pc, const UT_Vector3T< REAL > &pd, const UT_Vector3T< REAL > &pe, REAL ah, REAL bh, REAL ch, REAL dh, REAL eh) const
SYS_FORCE_INLINE UT_Vector3T< REAL > UTcrossExact(const UT_Vector3T< REAL > &v1, const UT_Vector3T< REAL > &v2, const UT_GeometryPredicates< REAL, USEFILTER, true > &pred)
SYS_FORCE_INLINE REAL incircle(const REAL pa[2], const REAL pb[2], const REAL pc[2], const REAL pd[2])
SYS_FORCE_INLINE REAL insphere(const REAL pa[3], const REAL pb[3], const REAL pc[3], const REAL pd[3], const REAL pe[3])
Definition: ImathVec.h:31
REAL insphere(const UT_Vector3T< REAL > &pa, const UT_Vector3T< REAL > &pb, const UT_Vector3T< REAL > &pc, const UT_Vector3T< REAL > &pd, const UT_Vector3T< REAL > &pe) const
GLfloat GLfloat v1
Definition: glcorearb.h:817
SYS_FORCE_INLINE REAL orient4d(const UT_Vector3T< REAL > &pa, const UT_Vector3T< REAL > &pb, const UT_Vector3T< REAL > &pc, const UT_Vector3T< REAL > &pd, const UT_Vector3T< REAL > &pe, REAL ah, REAL bh, REAL ch, REAL dh, REAL eh)
UT_API const UT_GeometryPredicates< fpreal32, false, true > ut_global_predicates_fpreal32
SYS_FORCE_INLINE double UTgeometryPredicateOrient3d(const UT_Vector3 &a, const UT_Vector3 &b, const UT_Vector3 &c, const UT_Vector3 &d)
SYS_FORCE_INLINE REAL orient2d(const UT_Vector2T< REAL > &pa, const UT_Vector2T< REAL > &pb, const UT_Vector2T< REAL > &pc)
const UT_GeometryPredicates< REAL, false, true > & getDefault()
constexpr SYS_FORCE_INLINE T & y() noexcept
Definition: UT_Vector3.h:665
SYS_FORCE_INLINE REAL orient2d(const REAL pa[2], const REAL pb[2], const REAL pc[2])
SYS_FORCE_INLINE double UTgeometryPredicateInsphere(const UT_Vector3 &a, const UT_Vector3 &b, const UT_Vector3 &c, const UT_Vector3 &d, const UT_Vector3 &e)
constexpr SYS_FORCE_INLINE T & x() noexcept
Definition: UT_Vector3.h:663