HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros 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
43 
44  void exactinit(const UT_Vector3T<REAL> &bbox_size);
45  void exactinit(const REAL bbox_size[3]);
46  void exactinit(); // filters are disabled with this initializer
47 
48  // Does point c lie on, to the left of, or to the right of line ab?
49  REAL orient2d(
50  const UT_Vector2T<REAL> &pa,
51  const UT_Vector2T<REAL> &pb,
52  const UT_Vector2T<REAL> &pc) const
53  { return orient2d(pa.data(), pb.data(), pc.data()); }
54  REAL orient2d(
55  const REAL pa[2],
56  const REAL pb[2],
57  const REAL pc[2]) const;
58 
59  // Does point d lie on, to the left of, or to the right of the plane containing
60  // the points a, b, and c?
61  REAL orient3d(
62  const UT_Vector3T<REAL> &pa,
63  const UT_Vector3T<REAL> &pb,
64  const UT_Vector3T<REAL> &pc,
65  const UT_Vector3T<REAL> &pd) const
66  { return orient3d(pa.data(), pb.data(), pc.data(), pd.data()); }
67  REAL orient3d(
68  const REAL pa[3],
69  const REAL pb[3],
70  const REAL pc[3],
71  const REAL pd[3]) const;
72 
73  // Does point d lie on, inside, or outside of the circle containing the points
74  // a, b, and c?
75  REAL incircle(
76  const UT_Vector2T<REAL> &pa,
77  const UT_Vector2T<REAL> &pb,
78  const UT_Vector2T<REAL> &pc,
79  const UT_Vector2T<REAL> &pd) const
80  { return incircle(pa.data(), pb.data(), pc.data(), pd.data()); }
81  REAL incircle(
82  const REAL pa[2],
83  const REAL pb[2],
84  const REAL pc[2],
85  const REAL pd[2]) const;
86 
87  // Does point e lie on, inside, or outside of the sphere containing the points
88  // a, b, c, and d?
89  REAL insphere(
90  const UT_Vector3T<REAL> &pa,
91  const UT_Vector3T<REAL> &pb,
92  const UT_Vector3T<REAL> &pc,
93  const UT_Vector3T<REAL> &pd,
94  const UT_Vector3T<REAL> &pe) const
95  { return insphere(pa.data(), pb.data(), pc.data(), pd.data(), pe.data()); }
96  REAL insphere(
97  const REAL pa[3],
98  const REAL pb[3],
99  const REAL pc[3],
100  const REAL pd[3],
101  const REAL pe[3]) const;
102 
103  // Does point e lie on, to the left of, or to the right of the hyperplane containing
104  // the points a, b, c, and d?
105  REAL orient4d(
106  const UT_Vector3T<REAL> &pa,
107  const UT_Vector3T<REAL> &pb,
108  const UT_Vector3T<REAL> &pc,
109  const UT_Vector3T<REAL> &pd,
110  const UT_Vector3T<REAL> &pe,
111  REAL ah, REAL bh, REAL ch, REAL dh, REAL eh) const
112  { return orient4d(pa.data(), pb.data(), pc.data(), pd.data(), pe.data(), ah,bh,ch,dh,eh); }
113  REAL orient4d(
114  const REAL pa[3],
115  const REAL pb[3],
116  const REAL pc[3],
117  const REAL pd[3],
118  const REAL pe[3],
119  REAL ah, REAL bh, REAL ch, REAL dh, REAL eh) const;
120 
121 protected:
122  /* splitter = 2^ceiling(p / 2) + 1. Used to split floats in half. */
123  REAL splitter;
124  REAL epsilon; /* = 2^(-p). Used to estimate roundoff errors. */
125  /* A set of coefficients used to calculate maximum roundoff errors. */
127  REAL ccwerrboundA, ccwerrboundB, ccwerrboundC;
128  REAL o3derrboundA, o3derrboundB, o3derrboundC;
129  REAL iccerrboundA, iccerrboundB, iccerrboundC;
130  REAL isperrboundA, isperrboundB, isperrboundC;
131 
132  // Additional predicate specific static filters
133  REAL filter1, filter2;
134 };
135 
138 
139 /// Function interface for geometric predicates.
140 /// More efficient predicates are availble through the UT_GeometryPredicates
141 /// class that defines a more thorough static filter
142 namespace UT_GeometryPredicate
143 {
144 
145 // Get the default instantiation of the predicate context (this is convenient
146 // when defining your own predicate dependent functions)
147 template<typename REAL>
149 
150 #define SPECIALIZE_GET_DEFAULT(REAL) \
151 template<> \
152 SYS_FORCE_INLINE \
153 const UT_GeometryPredicates<REAL,false,true>& \
154 getDefault<REAL>() { return ut_global_predicates_##REAL; }
155 
158 
159 // Does point c lie on, to the left of, or to the right of line ab?
160 template<typename REAL>
162 REAL orient2d(
163  const REAL pa[2],
164  const REAL pb[2],
165  const REAL pc[2])
166 { return getDefault<REAL>().orient2d(pa,pb,pc); }
167 template<typename REAL>
169 REAL orient2d(
170  const UT_Vector2T<REAL> &pa,
171  const UT_Vector2T<REAL> &pb,
172  const UT_Vector2T<REAL> &pc)
173 { return getDefault<REAL>().orient2d(pa,pb,pc); }
174 
175 // Does point d lie on, to the left of, or to the right of the plane containing
176 // the points a, b, and c?
177 template<typename REAL>
179 REAL orient3d(
180  const REAL pa[3],
181  const REAL pb[3],
182  const REAL pc[3],
183  const REAL pd[3])
184 { return getDefault<REAL>().orient3d(pa,pb,pc,pd); }
185 template<typename REAL>
187 REAL orient3d(
188  const UT_Vector3T<REAL> &pa,
189  const UT_Vector3T<REAL> &pb,
190  const UT_Vector3T<REAL> &pc,
191  const UT_Vector3T<REAL> &pd)
192 { return getDefault<REAL>().orient3d(pa,pb,pc,pd); }
193 
194 // Does point d lie one, inside, or outside of the circle containing the points
195 // a, b, and c?
196 template<typename REAL>
198 REAL incircle(
199  const REAL pa[2],
200  const REAL pb[2],
201  const REAL pc[2],
202  const REAL pd[2])
203 { return getDefault<REAL>().incircle(pa,pb,pc,pd); }
204 template<typename REAL>
206 REAL incircle(
207  const UT_Vector2T<REAL> &pa,
208  const UT_Vector2T<REAL> &pb,
209  const UT_Vector2T<REAL> &pc,
210  const UT_Vector2T<REAL> &pd)
211 { return getDefault<REAL>().incircle(pa,pb,pc,pd); }
212 
213 // Does point e lie one, inside, or outside of the sphere containing the points
214 // a, b, c, and d?
215 template<typename REAL>
217 REAL insphere(
218  const REAL pa[3],
219  const REAL pb[3],
220  const REAL pc[3],
221  const REAL pd[3],
222  const REAL pe[3])
223 { return getDefault<REAL>().insphere(pa,pb,pc,pd,pe); }
224 template<typename REAL>
226 REAL insphere(
227  const UT_Vector3T<REAL> &pa,
228  const UT_Vector3T<REAL> &pb,
229  const UT_Vector3T<REAL> &pc,
230  const UT_Vector3T<REAL> &pd,
231  const UT_Vector3T<REAL> &pe)
232 { return getDefault<REAL>().insphere(pa,pb,pc,pd,pe); }
233 
234 // Does point e lie on, to the left of, or to the right of the hyperplane containing
235 // the points a, b, c, and d?
236 template<typename REAL>
238 REAL orient4d(
239  const REAL pa[3],
240  const REAL pb[3],
241  const REAL pc[3],
242  const REAL pd[3],
243  const REAL pe[3],
244  REAL ah, REAL bh, REAL ch, REAL dh, REAL eh)
245 { return getDefault<REAL>().orient4d(pa,pb,pc,pd,pe,ah,bh,ch,dh,eh); }
246 template<typename REAL>
248 REAL orient4d(
249  const UT_Vector3T<REAL> &pa,
250  const UT_Vector3T<REAL> &pb,
251  const UT_Vector3T<REAL> &pc,
252  const UT_Vector3T<REAL> &pd,
253  const UT_Vector3T<REAL> &pe,
254  REAL ah, REAL bh, REAL ch, REAL dh, REAL eh)
255 { return getDefault<REAL>().orient4d(pa,pb,pc,pd,pe,ah,bh,ch,dh,eh); }
256 
257 } // end of namespace UT_GeometryPredicate
258 
259 template<typename REAL, bool USEFILTER>
262  const UT_Vector3T<REAL> &v1,
263  const UT_Vector3T<REAL> &v2,
265 {
266  // compute the cross product with exact signs
267  typedef UT_Vector2T<REAL> Vec2;
268  return UT_Vector3T<REAL>(
269  pred.orient2d( Vec2(v1.y(), v1.z()),
270  Vec2(v2.y(), v2.z()),
271  Vec2(0,0) ),
272  pred.orient2d( Vec2(v1.z(), v1.x()),
273  Vec2(v2.z(), v2.x()),
274  Vec2(0,0) ),
275  pred.orient2d( Vec2(v1.x(), v1.y()),
276  Vec2(v2.x(), v2.y()),
277  Vec2(0,0) ));
278 }
279 
280 template<typename REAL>
283  const UT_Vector3T<REAL> &v1,
284  const UT_Vector3T<REAL> &v2)
285 {
286  return UTcrossExact<REAL,false>(v1,v2, UT_GeometryPredicate::getDefault<REAL>());
287 }
288 
289 // Does point c lie on, to the left of, or to the right of line ab?
292  const UT_Vector2 &a,
293  const UT_Vector2 &b,
294  const UT_Vector2 &c)
295 {
296  double pa[2] = {a[0], a[1]};
297  double pb[2] = {b[0], b[1]};
298  double pc[2] = {c[0], c[1]};
299  return UT_GeometryPredicate::orient2d<fpreal64>(pa, pb, pc);
300 }
303  const UT_Vector2D &pa,
304  const UT_Vector2D &pb,
305  const UT_Vector2D &pc)
306 {
307  return UT_GeometryPredicate::orient2d<fpreal64>(pa.data(), pb.data(), pc.data());
308 }
311  const double pa[2],
312  const double pb[2],
313  const double pc[2])
314 {
315  return UT_GeometryPredicate::orient2d<fpreal64>(pa, pb, pc);
316 }
317 // Does point d lie on, to the left of, or to the right of the plane containing
318 // the points a, b, and c?
321  const UT_Vector3 &a,
322  const UT_Vector3 &b,
323  const UT_Vector3 &c,
324  const UT_Vector3 &d)
325 {
326  double pa[3] = {a[0], a[1], a[2]};
327  double pb[3] = {b[0], b[1], b[2]};
328  double pc[3] = {c[0], c[1], c[2]};
329  double pd[3] = {d[0], d[1], d[2]};
330  return UT_GeometryPredicate::orient3d<fpreal64>(pa, pb, pc, pd);
331 }
334  const UT_Vector3D &pa,
335  const UT_Vector3D &pb,
336  const UT_Vector3D &pc,
337  const UT_Vector3D &pd)
338 {
339  return UT_GeometryPredicate::orient3d<fpreal64>(pa.data(), pb.data(), pc.data(), pd.data());
340 }
343  const double pa[3],
344  const double pb[3],
345  const double pc[3],
346  const double pd[3])
347 {
348  return UT_GeometryPredicate::orient3d<fpreal64>(pa, pb, pc, pd);
349 }
350 
351 // Does point d lie one, inside, or outside of the circle containing the points
352 // a, b, and c?
355  const UT_Vector2 &a,
356  const UT_Vector2 &b,
357  const UT_Vector2 &c,
358  const UT_Vector2 &d)
359 {
360  double pa[2] = {a[0], a[1]};
361  double pb[2] = {b[0], b[1]};
362  double pc[2] = {c[0], c[1]};
363  double pd[2] = {d[0], d[1]};
364  return UT_GeometryPredicate::incircle<fpreal64>(pa, pb, pc, pd);
365 }
368  const UT_Vector2D &pa,
369  const UT_Vector2D &pb,
370  const UT_Vector2D &pc,
371  const UT_Vector2D &pd)
372 {
373  return UT_GeometryPredicate::incircle<fpreal64>(pa.data(), pb.data(),
374  pc.data(), pd.data());
375 }
378  const double pa[2],
379  const double pb[2],
380  const double pc[2],
381  const double pd[2])
382 {
383  return UT_GeometryPredicate::incircle<fpreal64>(pa, pb, pc, pd);
384 }
385 
386 // Does point e lie one, inside, or outside of the sphere containing the points
387 // a, b, c, and d?
390  const UT_Vector3 &a,
391  const UT_Vector3 &b,
392  const UT_Vector3 &c,
393  const UT_Vector3 &d,
394  const UT_Vector3 &e)
395 {
396  double pa[3] = {a[0], a[1], a[2]};
397  double pb[3] = {b[0], b[1], b[2]};
398  double pc[3] = {c[0], c[1], c[2]};
399  double pd[3] = {d[0], d[1], d[2]};
400  double pe[3] = {e[0], e[1], e[2]};
401  return UT_GeometryPredicate::insphere<fpreal64>(pa, pb, pc, pd, pe);
402 }
405  const UT_Vector3D &pa,
406  const UT_Vector3D &pb,
407  const UT_Vector3D &pc,
408  const UT_Vector3D &pd,
409  const UT_Vector3D &pe)
410 {
411  return UT_GeometryPredicate::insphere<fpreal64>(pa.data(), pb.data(), pc.data(),
412  pd.data(), pe.data());
413 }
416  const double pa[3],
417  const double pb[3],
418  const double pc[3],
419  const double pd[3],
420  const double pe[3])
421 {
422  return UT_GeometryPredicate::insphere<fpreal64>(pa, pb, pc, pd, pe);
423 }
424 
425 #endif // __UT_GeometryPredicate_h__
SYS_FORCE_INLINE constexpr const T * data() const noexcept
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__)
#define SPECIALIZE_GET_DEFAULT(REAL)
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1221
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:12
GLfloat GLfloat GLfloat v2
Definition: glcorearb.h:817
SYS_FORCE_INLINE T & x(void)
Definition: UT_Vector3.h:581
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:137
SYS_FORCE_INLINE T & z(void)
Definition: UT_Vector3.h:585
SYS_FORCE_INLINE REAL orient3d(const REAL pa[3], const REAL pb[3], const REAL pc[3], const REAL pd[3])
double fpreal64
Definition: SYS_Types.h:191
#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
SYS_FORCE_INLINE double UTgeometryPredicateOrient2d(const UT_Vector2 &a, const UT_Vector2 &b, const UT_Vector2 &c)
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
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 T & y(void)
Definition: UT_Vector3.h:583
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])
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:816
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()
#define const
Definition: zconf.h:214
SYS_FORCE_INLINE REAL orient2d(const REAL pa[2], const REAL pb[2], const REAL pc[2])
float fpreal32
Definition: SYS_Types.h:190
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)