BRL-CAD
brep.h
Go to the documentation of this file.
1 /* B R E P . H
2  * BRL-CAD
3  *
4  * Copyright (c) 2007-2014 United States Government as represented by
5  * the U.S. Army Research Laboratory.
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public License
9  * version 2.1 as published by the Free Software Foundation.
10  *
11  * This library is distributed in the hope that it will be useful, but
12  * WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with this file; see the file named COPYING for more
18  * information.
19  */
20 /** @addtogroup libbrep */
21 /** @{ */
22 /** @file brep.h
23  *
24  * Define surface and curve structures for Non-Uniform Rational
25  * B-Spline (NURBS) curves and surfaces. Uses openNURBS library.
26  *
27  */
28 #ifndef BREP_H
29 #define BREP_H
30 
31 #include "common.h"
32 
33 #ifdef __cplusplus
34 extern "C++" {
35 #include <vector>
36 #include <list>
37 #include <iostream>
38 #include <queue>
39 #include <assert.h>
40 
41 #include "dvec.h"
42 #include "opennurbs.h"
43 #include <iostream>
44 #include <fstream>
45 
46 namespace brlcad {
47 class BBNode;
48 }
49 }
51 #endif
52 
53 #include "vmath.h"
54 
55 #ifndef __cplusplus
56 typedef struct _on_brep_placeholder {
57  int dummy; /* MS Visual C hack which can be removed if the struct contains something meaningful */
58 } ON_Brep;
59 #endif
60 
61 
62 /** Maximum number of newton iterations on root finding */
63 #define BREP_MAX_ITERATIONS 100
64 
65 /** Root finding threshold */
66 #define BREP_INTERSECTION_ROOT_EPSILON 1e-6
67 
68 /* if threshold not reached what will we settle for close enough */
69 #define BREP_INTERSECTION_ROOT_SETTLE 1e-2
70 
71 /** Jungle Gym epsilon */
72 
73 /** tighten BREP grazing tolerance to 0.000017453(0.001 degrees) was using RT_DOT_TOL at 0.001 (0.05 degrees) **/
74 #define BREP_GRAZING_DOT_TOL 0.000017453
75 
76 /** Use vector operations? For debugging */
77 #define DO_VECTOR 1
78 
79 #ifndef BREP_EXPORT
80 # if defined(BREP_DLL_EXPORTS) && defined(BREP_DLL_IMPORTS)
81 # error "Only BREP_DLL_EXPORTS or BREP_DLL_IMPORTS can be defined, not both."
82 # elif defined(BREP_DLL_EXPORTS)
83 # define BREP_EXPORT __declspec(dllexport)
84 # elif defined(BREP_DLL_IMPORTS)
85 # define BREP_EXPORT __declspec(dllimport)
86 # else
87 # define BREP_EXPORT
88 # endif
89 #endif
90 
91 #ifndef __cplusplus
93  int dummy;
95 #else
96 typedef brlcad::BBNode BrepBoundingVolume;
97 #endif
98 
99 typedef struct _brep_cdbitem {
100  int dummy; /* MS Visual C hack which can be removed if the struct contains something meaningful */
101 } brep_cdbitem;
102 
103 
104 #ifdef __cplusplus
105 
107 
108 extern "C++" {
109 class plane_ray {
110 public:
111  vect_t n1;
112  fastf_t d1;
113 
114  vect_t n2;
115  fastf_t d2;
116 };
117 
118 /**
119  * These definitions were added to opennurbs_curve.h - they are
120  * extensions of openNURBS, so add them here instead. At some point a
121  * more coherent structure should probably be set up for organization
122  * of openNURBS extensions, since there may be more to come, but at
123  * least try to keep as many as possible out of the external openNURBS
124  * tree - simplifies syncing.
125  */
126 class ON_Ray {
127 public:
128  ON_3dPoint m_origin;
129  ON_3dVector m_dir;
130 
131  ON_Ray(ON_3dPoint &origin, ON_3dVector &dir);
132  ON_Ray(ON_2dPoint &origin, ON_2dVector &dir);
133  ON_Ray(const ON_Ray &r);
134 
135  ON_Ray &operator=(const ON_Ray &r);
136  ON_3dPoint PointAt(double t) const;
137  double DistanceTo(const ON_3dPoint &pt, double *out_t = NULL) const;
138 
139  /**
140  * Intersect two 2d Rays
141  * @param v [in] other ray to intersect with
142  * @param isect [out] point of intersection
143  * @return true if single point of intersection is found
144  */
145  bool IntersectRay(const ON_Ray &v, ON_2dPoint &isect) const;
146 };
147 
148 inline
149 ON_Ray::ON_Ray(ON_3dPoint &origin, ON_3dVector &dir)
150  : m_origin(origin), m_dir(dir)
151 {
152 }
153 
154 inline
155 ON_Ray::ON_Ray(ON_2dPoint &origin, ON_2dVector &dir)
156  : m_origin(origin), m_dir(dir)
157 {
158 }
159 
160 inline
161 ON_Ray::ON_Ray(const ON_Ray &r)
162  : m_origin(r.m_origin), m_dir(r.m_dir)
163 {
164 }
165 
166 inline
167 ON_Ray &
168 ON_Ray::operator=(const ON_Ray &r)
169 {
170  m_origin = r.m_origin;
171  m_dir = r.m_dir;
172  return *this;
173 }
174 
175 inline
176 ON_3dPoint
177 ON_Ray::PointAt(double t) const
178 {
179  return m_origin + m_dir * t;
180 }
181 
182 inline
183 double
184 ON_Ray::DistanceTo(const ON_3dPoint &pt, double *out_t /* = NULL */) const
185 {
186  ON_3dVector w = pt - m_origin;
187  double c1 = w * m_dir;
188  if (c1 <= 0) {
189  return pt.DistanceTo(m_origin);
190  }
191  double c2 = m_dir * m_dir;
192  double b = c1 / c2;
193  ON_3dPoint p = m_dir * b + m_origin;
194  if (out_t != NULL) {
195  *out_t = b;
196  }
197  return p.DistanceTo(pt);
198 }
199 
200 inline
201 bool
202 ON_Ray::IntersectRay(const ON_Ray &v, ON_2dPoint &isect) const
203 {
204  double uxv, q_pxv;
205  /* consider parallel and collinear cases */
206  if (ZERO(uxv = V2CROSS(m_dir, v.m_dir)) ||
207  (ZERO(q_pxv = V2CROSS(v.m_origin - m_origin, v.m_dir))))
208  {
209  return false;
210  }
211  isect = PointAt(q_pxv / uxv);
212  return true;
213 }
214 
215 BREP_EXPORT void brep_get_plane_ray(ON_Ray &r, plane_ray &pr);
216 BREP_EXPORT void brep_r(const ON_Surface *surf, plane_ray &pr, pt2d_t uv, ON_3dPoint &pt, ON_3dVector &su, ON_3dVector &sv, pt2d_t R);
217 BREP_EXPORT void brep_newton_iterate(plane_ray &pr, pt2d_t R, ON_3dVector &su, ON_3dVector &sv, pt2d_t uv, pt2d_t out_uv);
218 BREP_EXPORT void utah_ray_planes(const ON_Ray &r, ON_3dVector &p1, double &p1d, ON_3dVector &p2, double &p2d);
219 
220 BREP_EXPORT bool ON_NearZero(double x, double tolerance = ON_ZERO_TOLERANCE);
221 
222 /** Maximum per-surface BVH depth */
223 #define BREP_MAX_FT_DEPTH 8
224 #define BREP_MAX_LN_DEPTH 20
225 
226 #define SIGN(x) ((x) >= 0 ? 1 : -1)
227 
228 /** Surface flatness parameter, Abert says between 0.8-0.9 */
229 #define BREP_SURFACE_FLATNESS 0.85
230 #define BREP_SURFACE_STRAIGHTNESS 0.75
231 
232 /** Max newton iterations when finding closest point */
233 #define BREP_MAX_FCP_ITERATIONS 50
234 
235 /** Root finding epsilon */
236 #define BREP_FCP_ROOT_EPSILON 1e-5
237 
238 /** trim curve point sampling count for isLinear() check and possibly
239  * growing bounding box
240  */
241 #define BREP_BB_CRV_PNT_CNT 10
242 
243 #define BREP_CURVE_FLATNESS 0.95
244 
245 /** subdivision size factors */
246 #define BREP_SURF_SUB_FACTOR 1
247 #define BREP_TRIM_SUB_FACTOR 1
248 
249 /**
250  * The EDGE_MISS_TOLERANCE setting is critical in a couple of ways -
251  * too small and the allowed uncertainty region near edges will be
252  * smaller than the actual uncertainty needed for accurate solid
253  * raytracing, too large and trimming will not be adequate. May need
254  * to adapt this to the scale of the model, perhaps using bounding box
255  * size to key off of.
256  */
257 /* #define BREP_EDGE_MISS_TOLERANCE 5e-2 */
258 #define BREP_EDGE_MISS_TOLERANCE 5e-3
259 
260 #define BREP_SAME_POINT_TOLERANCE 1e-6
261 
262 /* FIXME: debugging crapola (clean up later) */
263 #define ON_PRINT4(p) "[" << (p)[0] << ", " << (p)[1] << ", " << (p)[2] << ", " << (p)[3] << "]"
264 #define ON_PRINT3(p) "(" << (p)[0] << ", " << (p)[1] << ", " << (p)[2] << ")"
265 #define ON_PRINT2(p) "(" << (p)[0] << ", " << (p)[1] << ")"
266 #define PT(p) ON_PRINT3(p)
267 #define PT2(p) ON_PRINT2(p)
268 #define IVAL(_ival) "[" << (_ival).m_t[0] << ", " << (_ival).m_t[1] << "]"
269 #define TRACE(s)
270 #define TRACE1(s)
271 #define TRACE2(s)
272 /* #define TRACE(s) std::cerr << s << std::endl; */
273 /* #define TRACE1(s) std::cerr << s << std::endl; */
274 /* #define TRACE2(s) std::cerr << s << std::endl; */
275 
276 namespace brlcad {
277 /**
278  * Bounding Rectangle Hierarchy
279  */
280 class BREP_EXPORT BRNode {
281 public:
282  BRNode();
283  BRNode(const ON_BoundingBox &node);
284  BRNode(const ON_Curve *curve,
285  int m_adj_face_index,
286  const ON_BoundingBox &node,
287  const ON_BrepFace *face,
288  const ON_Interval &t,
289  bool innerTrim = false,
290  bool checkTrim = true,
291  bool trimmed = false);
292  ~BRNode();
293 
294  /** List of all children of a given node */
295  std::vector<BRNode *> m_children;
296 
297  /** Bounding Box */
298  ON_BoundingBox m_node;
299 
300  /** Node management functions */
301  void addChild(const ON_BoundingBox &child);
302  void addChild(BRNode *child);
303  void removeChild(BRNode *child);
304 
305  /** Test if this node is a leaf node (i.e. m_children is empty) */
306  bool isLeaf();
307 
308  /** Return a list of all nodes below this node that are leaf nodes */
309  void getLeaves(std::list<BRNode *> &out_leaves);
310 
311  /** Report the depth of this node in the hierarchy */
312  int depth();
313 
314  /**
315  * Get 2 points defining bounding box:
316  *
317  * @verbatim
318  * *----------------max
319  * | |
320  * v | |
321  * | |
322  * min----------------*
323  * u
324  * @endverbatim
325  */
326  void GetBBox(fastf_t *min, fastf_t *max) const;
327 
328  /** Surface Information */
329  const ON_BrepFace *m_face;
330  ON_Interval m_u;
331  ON_Interval m_v;
332 
333  /** Trim Curve Information */
334  const ON_Curve *m_trim;
335  ON_Interval m_t;
336  int m_adj_face_index;
337 
338  /** Trimming Flags */
339  bool m_checkTrim;
340  bool m_trimmed;
341  bool m_XIncreasing;
342  bool m_Horizontal;
343  bool m_Vertical;
344  bool m_innerTrim;
345 
346  ON_3dPoint m_estimate;
347  ON_2dPoint getClosestPointEstimate(const ON_3dPoint &pt);
348  ON_2dPoint getClosestPointEstimate(const ON_3dPoint &pt, ON_Interval &u, ON_Interval &v);
349  fastf_t getLinearEstimateOfV(fastf_t u);
350  fastf_t getCurveEstimateOfV(fastf_t u, fastf_t tol) const;
351  fastf_t getCurveEstimateOfU(fastf_t v, fastf_t tol) const;
352 
353  int isTrimmed(const ON_2dPoint &uv, double &trimdist) const;
354  bool doTrimming() const;
355 
356 private:
357  BRNode *closer(const ON_3dPoint &pt, BRNode *left, BRNode *right);
358  fastf_t m_slope;
359  fastf_t m_vdot;
360  fastf_t m_bb_diag;
361  ON_3dPoint m_start;
362  ON_3dPoint m_end;
363 };
364 
365 inline
366 BRNode::BRNode()
367 {
368  m_start = ON_3dPoint::UnsetPoint;
369  m_end = ON_3dPoint::UnsetPoint;
370 }
371 
372 inline
374 BRNode::BRNode(
375  const ON_Curve *curve,
376  int adj_face_index,
377  const ON_BoundingBox &node,
378  const ON_BrepFace *face,
379  const ON_Interval &t,
380  bool innerTrim /* = false */,
381  bool checkTrim /* = true */,
382  bool trimmed /* = false */)
383  : m_node(node), m_face(face), m_trim(curve), m_t(t),
384  m_adj_face_index(adj_face_index), m_checkTrim(checkTrim),
385  m_trimmed(trimmed), m_innerTrim(innerTrim), m_slope(0.0), m_vdot(0.0)
386 {
387  m_start = curve->PointAt(m_t[0]);
388  m_end = curve->PointAt(m_t[1]);
389  /* check for vertical segments they can be removed from trims
390  * above (can't tell direction and don't need
391  */
392  m_Horizontal = false;
393  m_Vertical = false;
394 
395  /*
396  * should be okay since we split on Horz/Vert tangents
397  */
398  if (m_end[X] < m_start[X]) {
399  m_u[0] = m_end[X];
400  m_u[1] = m_start[X];
401  } else {
402  m_u[0] = m_start[X];
403  m_u[1] = m_end[X];
404  }
405  if (m_end[Y] < m_start[Y]) {
406  m_v[0] = m_end[Y];
407  m_v[1] = m_start[Y];
408  } else {
409  m_v[0] = m_start[Y];
410  m_v[1] = m_end[Y];
411  }
412 
413  if (NEAR_EQUAL(m_end[X], m_start[X], 0.000001)) {
414  m_Vertical = true;
415  if (m_innerTrim) {
416  m_XIncreasing = false;
417  } else {
418  m_XIncreasing = true;
419  }
420  } else if (NEAR_EQUAL(m_end[Y], m_start[Y], 0.000001)) {
421  m_Horizontal = true;
422  if ((m_end[X] - m_start[X]) > 0.0) {
423  m_XIncreasing = true;
424  } else {
425  m_XIncreasing = false;
426  }
427  m_slope = 0.0;
428  } else {
429  if ((m_end[X] - m_start[X]) > 0.0) {
430  m_XIncreasing = true;
431  } else {
432  m_XIncreasing = false;
433  }
434  m_slope = (m_end[Y] - m_start[Y]) / (m_end[X] - m_start[X]);
435  }
436  m_bb_diag = DIST_PT_PT(m_start, m_end);
437 }
438 
439 inline
441 BRNode::BRNode(const ON_BoundingBox &node)
442  : m_node(node)
443 {
444  m_adj_face_index = -99;
445  m_checkTrim = true;
446  m_trimmed = false;
447  m_Horizontal = false;
448  m_Vertical = false;
449  m_XIncreasing = false;
450  m_innerTrim = false;
451  m_bb_diag = 0.0;
452  m_slope = 0.0;
453  m_vdot = 0.0;
454  m_face = NULL;
455  m_trim = NULL;
456  m_start = ON_3dPoint::UnsetPoint;
457  m_end = ON_3dPoint::UnsetPoint;
458  for (int i = 0; i < 3; i++) {
459  double d = m_node.m_max[i] - m_node.m_min[i];
460  if (NEAR_ZERO(d, ON_ZERO_TOLERANCE)) {
461  m_node.m_min[i] -= 0.001;
462  m_node.m_max[i] += 0.001;
463  }
464  }
465  m_start = m_node.m_min;
466  m_end = m_node.m_max;
467 }
468 
469 inline void
470 BRNode::addChild(const ON_BoundingBox &child)
471 {
472  m_children.push_back(new BRNode(child));
473 }
474 
475 inline void
476 BRNode::addChild(BRNode *child)
477 {
478  if (LIKELY(child != NULL)) {
479  m_children.push_back(child);
480  }
481 }
482 
483 inline void
484 BRNode::removeChild(BRNode *child)
485 {
486  std::vector<BRNode *>::iterator i;
487  for (i = m_children.begin(); i < m_children.end(); ++i) {
488  if (*i == child) {
489  delete *i;
490  m_children.erase(i);
491  }
492  }
493 }
494 
495 inline bool
496 BRNode::isLeaf()
497 {
498  if (m_children.size() == 0) {
499  return true;
500  }
501  return false;
502 }
503 
504 inline void
506 BRNode::GetBBox(fastf_t *min, fastf_t *max) const
507 {
508  VSETALL(min, INFINITY);
509  VSETALL(max, -INFINITY);
510  if (m_start != ON_3dPoint::UnsetPoint) {
511  VMINMAX(min, max, m_start);
512  }
513  if (m_end != ON_3dPoint::UnsetPoint) {
514  VMINMAX(min, max, m_end);
515  }
516 }
517 
518 inline bool
519 BRNode::doTrimming() const
520 {
521  return m_checkTrim;
522 }
523 
524 extern bool sortX(BRNode *first, BRNode *second);
525 extern bool sortY(BRNode *first, BRNode *second);
526 
527 /*--------------------------------------------------------------------------------
528  * CurveTree declaration
529  */
530 class BREP_EXPORT CurveTree {
531 public:
532  CurveTree(const ON_BrepFace *face);
533  ~CurveTree();
534 
535  BRNode *getRootNode() const;
536 
537  /**
538  * Calculate, using the surface bounding volume hierarchy, a uv
539  * estimate for the closest point on the surface to the point in
540  * 3-space.
541  */
542  ON_2dPoint getClosestPointEstimate(const ON_3dPoint &pt);
543  ON_2dPoint getClosestPointEstimate(const ON_3dPoint &pt, ON_Interval &u, ON_Interval &v);
544 
545  /**
546  * Return just the leaves of the surface tree
547  */
548  void getLeaves(std::list<BRNode *> &out_leaves);
549  void getLeavesAbove(std::list<BRNode *> &out_leaves, const ON_Interval &u, const ON_Interval &v);
550  void getLeavesAbove(std::list<BRNode *> &out_leaves, const ON_2dPoint &pt, fastf_t tol);
551  void getLeavesRight(std::list<BRNode *> &out_leaves, const ON_Interval &u, const ON_Interval &v);
552  void getLeavesRight(std::list<BRNode *> &out_leaves, const ON_2dPoint &pt, fastf_t tol);
553  int depth();
554 
555 private:
556  bool getHVTangents(const ON_Curve *curve, ON_Interval &t, std::list<fastf_t> &list);
557  bool isLinear(const ON_Curve *curve, double min, double max);
558  BRNode *subdivideCurve(const ON_Curve *curve, int adj_face_index, double min, double max, bool innerTrim, int depth);
559  BRNode *curveBBox(const ON_Curve *curve, int adj_face_index, ON_Interval &t, bool leaf, bool innerTrim, const ON_BoundingBox &bb);
560  BRNode *initialLoopBBox();
561 
562  const ON_BrepFace *m_face;
563  BRNode *m_root;
564  std::list<BRNode *> m_sortedX;
565  std::list<BRNode *> m_sortedY;
566 };
567 
568 /*--------------------------------------------------------------------------------
569  * Bounding Box Hierarchy
570  */
571 class BREP_EXPORT BBNode {
572 public:
573  BBNode();
574  BBNode(const ON_BoundingBox &node);
575  BBNode(CurveTree *ct);
576  BBNode(CurveTree *ct, const ON_BoundingBox &node);
577  BBNode(CurveTree *ct,
578  const ON_BoundingBox &node,
579  const ON_BrepFace *face,
580  const ON_Interval &u,
581  const ON_Interval &v,
582  bool checkTrim = false,
583  bool trimmed = false);
584  ~BBNode();
585 
586  /** List of all children of a given node */
587  std::vector<BBNode *> m_children;
588 
589  /** Curve Tree associated with the parent Surface Tree */
590  CurveTree *m_ctree;
591 
592  /** Bounding Box */
593  ON_BoundingBox m_node;
594 
595  /** Test if this node is a leaf node in the hierarchy */
596  bool isLeaf();
597 
598  /** Return all leaves below this node that are leaf nodes */
599  void getLeaves(std::list<BBNode *> &out_leaves);
600 
601  /** Functions to add and remove child nodes from this node. */
602  void addChild(const ON_BoundingBox &child);
603  void addChild(BBNode *child);
604  void removeChild(BBNode *child);
605 
606  /** Report the depth of this node in the hierarchy */
607  int depth();
608 
609  /** Get 2 points defining a bounding box
610  *
611  * @verbatim
612  * _ max _
613  * _ - + - _
614  * * _ + _ *
615  * | - _ + _ - |
616  * | *+ |
617  * | |+ |
618  * | _ |+ _ |
619  * | _ - | - _ |
620  * * _ | _ *
621  * - _ | _ -
622  * min
623  * @endverbatim
624  */
625  void GetBBox(float *min, float *max);
626  void GetBBox(double *min, double *max);
627 
628  /** Surface Information */
629  const ON_BrepFace *m_face;
630  ON_Interval m_u;
631  ON_Interval m_v;
632 
633  /** Trimming Flags */
634  bool m_checkTrim;
635  bool m_trimmed;
636 
637  /** Point used for closeness testing - usually based on evaluation
638  * of the curve/surface at the center of the parametric domain
639  */
640  ON_3dPoint m_estimate;
641 
642  /* Normal at the m_estimate point */
643  ON_3dVector m_normal;
644 
645  /** Test whether a ray intersects the 3D bounding volume of the
646  * node - if so, and node is not a leaf node, query children. If
647  * leaf node, and intersects, add to list.
648  */
649  bool intersectedBy(ON_Ray &ray, double *tnear = NULL, double *tfar = NULL);
650  bool intersectsHierarchy(ON_Ray &ray, std::list<BBNode *> &results);
651 
652  /** Report if a given uv point is within the uv boundaries defined
653  * by a node.
654  */
655  bool containsUV(const ON_2dPoint &uv);
656 
657  ON_2dPoint getClosestPointEstimate(const ON_3dPoint &pt);
658  ON_2dPoint getClosestPointEstimate(const ON_3dPoint &pt, ON_Interval &u, ON_Interval &v);
659  int getLeavesBoundingPoint(const ON_3dPoint &pt, std::list<BBNode *> &out);
660  int isTrimmed(const ON_2dPoint &uv, BRNode **closest, double &closesttrim, double within_distance_tol) const;
661  bool doTrimming() const;
662 
663  void getTrimsAbove(const ON_2dPoint &uv, std::list<BRNode *> &out_leaves) const;
664  void BuildBBox();
665  bool prepTrims();
666 
667 private:
668  BBNode *closer(const ON_3dPoint &pt, BBNode *left, BBNode *right);
669  std::list<BRNode *> m_trims_above;
670  std::list<BRNode *> m_trims_vertical;
671 };
672 
673 inline
674 BBNode::BBNode()
675  : m_ctree(NULL), m_face(NULL), m_checkTrim(true), m_trimmed(false)
676 {
677 }
678 
679 inline
680 BBNode::BBNode(const ON_BoundingBox &node)
681  : m_ctree(NULL), m_node(node), m_face(NULL), m_checkTrim(true), m_trimmed(false)
682 {
683  for (int i = 0; i < 3; i++) {
684  double d = m_node.m_max[i] - m_node.m_min[i];
685  if (ON_NearZero(d, ON_ZERO_TOLERANCE)) {
686  m_node.m_min[i] -= 0.001;
687  m_node.m_max[i] += 0.001;
688  }
689  }
690 }
691 
692 inline
693 BBNode::BBNode(CurveTree *ct)
694  : m_ctree(ct), m_face(NULL), m_checkTrim(true), m_trimmed(false)
695 {
696 }
697 
698 inline
699 BBNode::BBNode(CurveTree *ct, const ON_BoundingBox &node)
700  : m_ctree(ct), m_node(node), m_face(NULL), m_checkTrim(true), m_trimmed(false)
701 {
702  for (int i = 0; i < 3; i++) {
703  double d = m_node.m_max[i] - m_node.m_min[i];
704  if (ON_NearZero(d, ON_ZERO_TOLERANCE)) {
705  m_node.m_min[i] -= 0.001;
706  m_node.m_max[i] += 0.001;
707  }
708  }
709 }
710 
711 inline
713 BBNode::BBNode(
714  CurveTree *ct,
715  const ON_BoundingBox &node,
716  const ON_BrepFace *face,
717  const ON_Interval &u,
718  const ON_Interval &v,
719  bool checkTrim /* = false */,
720  bool trimmed /* = false */)
721  : m_ctree(ct), m_node(node), m_face(face), m_u(u), m_v(v),
722  m_checkTrim(checkTrim), m_trimmed(trimmed)
723 {
724  for (int i = 0; i < 3; i++) {
725  double d = m_node.m_max[i] - m_node.m_min[i];
726  if (ON_NearZero(d, ON_ZERO_TOLERANCE)) {
727  m_node.m_min[i] -= 0.001;
728  m_node.m_max[i] += 0.001;
729  }
730  }
731 }
732 
733 inline void
734 BBNode::addChild(const ON_BoundingBox &child)
735 {
736  m_children.push_back(new BBNode(child));
737 }
738 
739 inline void
740 BBNode::addChild(BBNode *child)
741 {
742  if (LIKELY(child != NULL)) {
743  m_children.push_back(child);
744  }
745 }
746 
747 inline void
748 BBNode::removeChild(BBNode *child)
749 {
750  std::vector<BBNode *>::iterator i;
751  for (i = m_children.begin(); i < m_children.end(); ++i) {
752  if (*i == child) {
753  delete *i;
754  m_children.erase(i);
755  }
756  }
757 }
758 
759 inline bool
760 BBNode::isLeaf()
761 {
762  if (m_children.size() == 0) {
763  return true;
764  }
765  return false;
766 }
767 
768 inline void
769 BBNode::GetBBox(float *min, float *max)
770 {
771  min[0] = m_node.m_min[0];
772  min[1] = m_node.m_min[1];
773  min[2] = m_node.m_min[2];
774  max[0] = m_node.m_max[0];
775  max[1] = m_node.m_max[1];
776  max[2] = m_node.m_max[2];
777 }
778 
779 inline void
780 BBNode::GetBBox(double *min, double *max)
781 {
782  min[0] = m_node.m_min[0];
783  min[1] = m_node.m_min[1];
784  min[2] = m_node.m_min[2];
785  max[0] = m_node.m_max[0];
786  max[1] = m_node.m_max[1];
787  max[2] = m_node.m_max[2];
788 }
789 
790 inline bool
791 BBNode::intersectedBy(ON_Ray &ray, double *tnear_opt /* = NULL */, double *tfar_opt /* = NULL */)
792 {
793  double tnear = -DBL_MAX;
794  double tfar = DBL_MAX;
795  bool untrimmedresult = true;
796  for (int i = 0; i < 3; i++) {
797  if (UNLIKELY(ON_NearZero(ray.m_dir[i]))) {
798  if (ray.m_origin[i] < m_node.m_min[i] || ray.m_origin[i] > m_node.m_max[i]) {
799  untrimmedresult = false;
800  }
801  } else {
802  double t1 = (m_node.m_min[i] - ray.m_origin[i]) / ray.m_dir[i];
803  double t2 = (m_node.m_max[i] - ray.m_origin[i]) / ray.m_dir[i];
804  if (t1 > t2) {
805  double tmp = t1; /* swap */
806  t1 = t2;
807  t2 = tmp;
808  }
809 
810  V_MAX(tnear, t1);
811  V_MIN(tfar, t2);
812 
813  if (tnear > tfar) { /* box is missed */
814  untrimmedresult = false;
815  }
816  /* go ahead and solve hits behind us
817  if (tfar < 0) untrimmedresult = false;
818  */
819  }
820  }
821  if (LIKELY(tnear_opt != NULL && tfar_opt != NULL)) {
822  *tnear_opt = tnear;
823  *tfar_opt = tfar;
824  }
825  if (isLeaf()) {
826  return !m_trimmed && untrimmedresult;
827  } else {
828  return untrimmedresult;
829  }
830 }
831 
832 inline bool
833 BBNode::doTrimming() const
834 {
835  return m_checkTrim;
836 }
837 
838 /*--------------------------------------------------------------------------------
839  * SurfaceTree declaration
840  */
841 class BREP_EXPORT SurfaceTree {
842 private:
843  bool m_removeTrimmed;
844 
845 public:
846  SurfaceTree();
847  SurfaceTree(const ON_BrepFace *face, bool removeTrimmed = true, int depthLimit = BREP_MAX_FT_DEPTH, double within_distance_tol = BREP_EDGE_MISS_TOLERANCE);
848  ~SurfaceTree();
849 
850  CurveTree *ctree;
851 
852  BBNode *getRootNode() const;
853 
854  /**
855  * Calculate, using the surface bounding volume hierarchy, a uv
856  * estimate for the closest point on the surface to the point in
857  * 3-space.
858  */
859  ON_2dPoint getClosestPointEstimate(const ON_3dPoint &pt);
860  ON_2dPoint getClosestPointEstimate(const ON_3dPoint &pt, ON_Interval &u, ON_Interval &v);
861 
862  /**
863  * Return surface
864  */
865  const ON_Surface *getSurface();
866  int getSurfacePoint(const ON_3dPoint &pt, ON_2dPoint &uv, const ON_3dPoint &from, double tolerance = BREP_SAME_POINT_TOLERANCE) const;
867 
868  /**
869  * Return just the leaves of the surface tree
870  */
871  void getLeaves(std::list<BBNode *> &out_leaves);
872  int depth();
873 
874 private:
875  bool isFlat(ON_Plane frames[]);
876  bool isStraight(ON_Plane frames[]);
877  bool isFlatU(ON_Plane frames[]);
878  bool isFlatV(ON_Plane frames[]);
879  BBNode *subdivideSurface(const ON_Surface *localsurf, const ON_Interval &u, const ON_Interval &v, ON_Plane frames[], int depth, int depthLimit, int prev_knot, double within_distance_tol);
880  BBNode *surfaceBBox(const ON_Surface *localsurf, bool leaf, ON_Plane frames[], const ON_Interval &u, const ON_Interval &v, double within_distance_tol);
881 
882  const ON_BrepFace *m_face;
883  BBNode *m_root;
884  std::queue<ON_Plane *> f_queue;
885 };
886 
887 /**
888  * approach:
889  *
890  * - get an estimate using the surface tree (if non-null, create
891  * one otherwise)
892  *
893  * - find a point (u, v) for which S(u, v) is closest to _point_
894  * _ __
895  * -- minimize the distance function: D(u, v) = sqrt(|S(u, v)-pt|^2)
896  * _ __
897  * -- simplify by minimizing f(u, v) = |S(u, v)-pt|^2
898  *
899  * -- minimum occurs when the gradient is zero, i.e.
900  * \f[ \nabla f(u, v) = |\vec{S}(u, v)-\vec{p}|^2 = 0 \f]
901  */
902 BREP_EXPORT bool get_closest_point(ON_2dPoint &outpt,
903  ON_BrepFace *face,
904  const ON_3dPoint &point,
905  SurfaceTree *tree = NULL,
906  double tolerance = BREP_FCP_ROOT_EPSILON);
907 
908 /**
909  * Pull an arbitrary model-space *curve* onto the given *surface* as a
910  * curve within the surface's domain when, for each point c = C(t) on
911  * the curve and the closest point s = S(u, v) on the surface, we
912  * have: distance(c, s) <= *tolerance*.
913  *
914  * The resulting 2-dimensional curve will be approximated using the
915  * following process:
916  *
917  * 1. Adaptively sample the 3d curve in the domain of the surface
918  * (ensure tolerance constraint). Sampling terminates when the
919  * following flatness criterion is met:
920  *
921  * given two parameters on the curve t1 and t2 (which map to points p1
922  * and p2 on the curve) let m be a parameter randomly chosen near the
923  * middle of the interval [t1, t2] ____ then the curve between t1 and
924  * t2 is flat if distance(C(m), p1p2) < flatness
925  *
926  * 2. Use the sampled points to perform a global interpolation using
927  * universal knot generation to build a B-Spline curve.
928  *
929  * 3. If the curve is a line or an arc (determined with openNURBS
930  * routines), return the appropriate ON_Curve subclass (otherwise,
931  * return an ON_NurbsCurve).
932  */
933 extern ON_Curve *pullback_curve(ON_BrepFace *face,
934  const ON_Curve *curve,
935  SurfaceTree *tree = NULL,
936  double tolerance = BREP_FCP_ROOT_EPSILON,
937  double flatness = 1.0e-3);
938 } /* end namespace brlcad */
939 
940 typedef struct pbc_data {
941  double tolerance;
942  double flatness;
943  const ON_Curve *curve;
944  const ON_Surface *surf;
945  brlcad::SurfaceTree *surftree;
946  std::list<ON_2dPointArray *> segments;
947  const ON_BrepEdge *edge;
948  bool order_reversed;
949 } PBCData;
950 
951 struct BrepTrimPoint
952 {
953  ON_2dPoint p2d; /* 2d surface parameter space point */
954  ON_3dPoint *p3d; /* 3d edge/trim point depending on whether we're using the 3d edge to generate points or the trims */
955  double t; /* corresponding trim curve parameter (ON_UNSET_VALUE if unknown or not pulled back) */
956  double e; /* corresponding edge curve parameter (ON_UNSET_VALUE if using trim not edge) */
957 };
958 
959 extern BREP_EXPORT int IsAtSingularity(const ON_Surface *surf, double u, double v, double tol = 1e-6);
960 extern BREP_EXPORT int IsAtSingularity(const ON_Surface *surf, const ON_2dPoint &pt, double tol = 1e-6);
961 extern BREP_EXPORT int IsAtSeam(const ON_Surface *surf,int dir,double u, double v,double tol = 0.0);
962 extern BREP_EXPORT int IsAtSeam(const ON_Surface *surf,double u, double v,double tol = 0.0);
963 extern BREP_EXPORT int IsAtSeam(const ON_Surface *surf,int dir,const ON_2dPoint &pt,double tol = 0.0);
964 extern BREP_EXPORT int IsAtSeam(const ON_Surface *surf,const ON_2dPoint &pt,double tol = 0.0);
965 extern BREP_EXPORT ON_2dPoint UnwrapUVPoint(const ON_Surface *surf,const ON_2dPoint &pt,double tol = 0.0);
966 extern BREP_EXPORT double DistToNearestClosedSeam(const ON_Surface *surf,const ON_2dPoint &pt);
967 extern BREP_EXPORT void SwapUVSeamPoint(const ON_Surface *surf,ON_2dPoint &p, int hint = 3);
968 extern BREP_EXPORT void ForceToClosestSeam(const ON_Surface *surf,ON_2dPoint &pt,double tol= 0.0);
969 extern BREP_EXPORT bool Find3DCurveSeamCrossing(PBCData &data,double t0,double t1,double offset,double &seam_t,ON_2dPoint &from,ON_2dPoint &to,double tol = 0.0, double same_point_tol=BREP_SAME_POINT_TOLERANCE,double within_distance_tol = BREP_EDGE_MISS_TOLERANCE);
970 extern BREP_EXPORT bool FindTrimSeamCrossing(const ON_BrepTrim &trim,double t0,double t1,double &seam_t,ON_2dPoint &from,ON_2dPoint &to,double tol = 0.0);
971 extern BREP_EXPORT bool surface_GetClosestPoint3dFirstOrder(const ON_Surface *surf,const ON_3dPoint& p,ON_2dPoint& p2d,ON_3dPoint& p3d,double &current_distance,int quadrant = 0,double same_point_tol=BREP_SAME_POINT_TOLERANCE,double within_distance_tol=BREP_EDGE_MISS_TOLERANCE);
972 extern BREP_EXPORT bool trim_GetClosestPoint3dFirstOrder(const ON_BrepTrim& trim,const ON_3dPoint& p,ON_2dPoint& p2d,double& t,double& distance,const ON_Interval* interval,double same_point_tol=BREP_SAME_POINT_TOLERANCE,double within_distance_tol=BREP_EDGE_MISS_TOLERANCE);
973 extern BREP_EXPORT bool ConsecutivePointsCrossClosedSeam(const ON_Surface *surf,const ON_2dPoint &pt,const ON_2dPoint &prev_pt, int &udir, int &vdir,double tol = 1e-6);
974 extern BREP_EXPORT ON_BOOL32 face_GetBoundingBox(const ON_BrepFace &face,ON_BoundingBox& bbox,ON_BOOL32 bGrowBox);
975 extern BREP_EXPORT ON_BOOL32 surface_GetBoundingBox(const ON_Surface *surf,const ON_Interval &u_interval,const ON_Interval &v_interval,ON_BoundingBox& bbox,ON_BOOL32 bGrowBox);
976 extern BREP_EXPORT ON_BOOL32 surface_EvNormal(const ON_Surface *surf,double s,double t,ON_3dPoint& point,ON_3dVector& normal,int side=0,int* hint=0);
977 
978 extern BREP_EXPORT PBCData *pullback_samples(const ON_Surface *surf,const ON_Curve *curve,double tolerance = 1.0e-6,double flatness = 1.0e-3,double same_point_tol=BREP_SAME_POINT_TOLERANCE,double within_distance_tol=BREP_EDGE_MISS_TOLERANCE);
979 
980 extern BREP_EXPORT bool check_pullback_data(std::list<PBCData *> &pbcs);
981 
982 extern BREP_EXPORT ON_Curve *interpolateCurve(ON_2dPointArray &samples);
983 
984 extern BREP_EXPORT int
985 check_pullback_singularity_bridge(const ON_Surface *surf, const ON_2dPoint &p1, const ON_2dPoint &p2);
986 
987 extern BREP_EXPORT ON_NurbsCurve *
988 interpolateLocalCubicCurve(const ON_3dPointArray &Q);
989 
990 /**
991  * Dump the information of an ON_SSX_EVENT.
992  */
993 extern BREP_EXPORT void
994 DumpSSXEvent(ON_SSX_EVENT &x, ON_TextLog &text_log);
995 
996 /* Sub-division support for a curve.
997  * It's similar to generating the bounding box tree, when the Split()
998  * method is called, the curve is split into two parts, whose bounding
999  * boxes become the children of the original curve's bbox.
1000  */
1001 class Subcurve {
1002  friend class Subsurface;
1003 private:
1004  ON_BoundingBox m_node;
1005 public:
1006  ON_Curve *m_curve;
1007  ON_Interval m_t;
1008  Subcurve *m_children[2];
1009  ON_BOOL32 m_islinear;
1010 
1011  Subcurve();
1012  Subcurve(ON_Curve *curve);
1013  Subcurve(const Subcurve &_scurve);
1014  ~Subcurve();
1015  int Split();
1016  void GetBBox(ON_3dPoint &min, ON_3dPoint &max);
1017  void SetBBox(const ON_BoundingBox &bbox);
1018  bool IsPointIn(const ON_3dPoint &pt, double tolerance = 0.0);
1019  bool Intersect(const Subcurve &other, double tolerance = 0.0, ON_BoundingBox *intersection = NULL) const;
1020 };
1021 
1022 /* Sub-division support for a surface.
1023  * It's similar to generating the bounding box tree, when the Split()
1024  * method is called, the surface is split into two parts, whose bounding
1025  * boxes become the children of the original surface's bbox.
1026  */
1027 class Subsurface {
1028 private:
1029  ON_BoundingBox m_node;
1030 public:
1031  ON_Surface *m_surf;
1032  ON_Interval m_u, m_v;
1033  Subsurface *m_children[4];
1034  ON_BOOL32 m_isplanar;
1035 
1036  Subsurface();
1037  Subsurface(ON_Surface *surf);
1038  Subsurface(const Subsurface &_ssurf);
1039  ~Subsurface();
1040 
1041  int Split();
1042  void GetBBox(ON_3dPoint &min, ON_3dPoint &max);
1043  void SetBBox(const ON_BoundingBox &bbox);
1044  bool IsPointIn(const ON_3dPoint &pt, double tolerance = 0.0);
1045  bool Intersect(const Subcurve &curve, double tolerance = 0.0, ON_BoundingBox *intersection = NULL) const;
1046  bool Intersect(const Subsurface &surf, double tolerance = 0.0, ON_BoundingBox *intersection = NULL) const;
1047 };
1048 
1049 /** The ON_PX_EVENT class is used to report point-point, point-curve
1050  * and point-surface intersection events.
1051  */
1052 class BREP_EXPORT ON_PX_EVENT
1053 {
1054 public:
1055  /** Default construction sets everything to zero. */
1056  ON_PX_EVENT();
1057 
1058  /**
1059  * Compares point intersection events and sorts them in the
1060  * canonical order.
1061  *
1062  * @retval -1 this < other
1063  * @retval 0 this == other
1064  * @retval +1 this > other
1065  *
1066  * @remarks ON_PX_EVENT::Compare is used to sort intersection
1067  * events into canonical order.
1068  */
1069  static
1070  int Compare(const ON_PX_EVENT *a, const ON_PX_EVENT *b);
1071 
1072  /**
1073  * Check point intersection event values to make sure they are
1074  * valid.
1075  *
1076  * @param text_log [in] If not null and an error is found, then
1077  * a description of the error is printed to text_log.
1078  * @param intersection_tolerance [in] 0.0 or value used in
1079  * intersection calculation.
1080  * @param pointA [in] NULL or pointA passed to intersection
1081  * calculation.
1082  * @param pointB [in] NULL or pointB passed to intersection
1083  * calculation.
1084  * @param curveB [in] NULL or curveB passed to intersection
1085  * calculation.
1086  * @param curveB_domain [in] NULL or curveB domain used in
1087  * intersection calculation.
1088  * @param surfaceB [in] NULL or surfaceB passed to intersection
1089  * calculation.
1090  * @param surfaceB_domain0 [in] NULL or surfaceB "u" domain used
1091  * in intersection calculation.
1092  * @param surfaceB_domain1 [in] NULL or surfaceB "v" domain used
1093  * in intersection calculation.
1094  *
1095  * @return True if event is valid.
1096  */
1097  bool IsValid(ON_TextLog *text_log,
1098  double intersection_tolerance,
1099  const class ON_3dPoint *pointA,
1100  const class ON_3dPoint *pointB,
1101  const class ON_Curve *curveB,
1102  const class ON_Interval *curveB_domain,
1103  const class ON_Surface *surfaceB,
1104  const class ON_Interval *surfaceB_domain0,
1105  const class ON_Interval *surfaceB_domain1) const;
1106 
1107  void Dump(ON_TextLog &text_log) const;
1108 
1109  enum TYPE {
1110  no_px_event = 0,
1111  ppx_point = 1, /**< point-point intersection */
1112  pcx_point = 2, /**< point-curve intersection */
1113  psx_point = 3 /**< point-surface intersection */
1114  };
1115 
1116  TYPE m_type;
1117 
1118  ON_3dPoint m_A; /**< Point A in 3D space */
1119  ON_3dPoint m_B; /**< Point B in 3D space */
1120 
1121  ON_2dPoint m_b; /**< Point B in 2D space for the curve/surface
1122  * For a curve, m_b[1] == 0
1123  * For a point, m_b[0] == m_b[1] == 0
1124  */
1125 
1126  ON_3dPoint m_Mid; /**< The mid-point of Point A and Point B */
1127  double m_radius; /**< To trace the uncertainty area */
1128 };
1129 
1130 /**
1131  * An overload of ON_Intersect for point-point intersection.
1132  * Intersect pointA with pointB.
1133  *
1134  * @param pointA [in]
1135  * @param pointB [in]
1136  * @param x [out] Intersection events are appended to this array.
1137  * @param tolerance [in] If the input intersection_tolerance <= 0.0,
1138  * then 0.001 is used.
1139  *
1140  * @return True for an intersection. False for no intersection.
1141  */
1142 extern BREP_EXPORT bool
1143 ON_Intersect(const ON_3dPoint &pointA,
1144  const ON_3dPoint &pointB,
1145  ON_ClassArray<ON_PX_EVENT> &x,
1146  double tolerance = 0.0);
1147 
1148 /**
1149  * An overload of ON_Intersect for point-curve intersection.
1150  * Intersect pointA with curveB.
1151  *
1152  * @param pointA [in]
1153  * @param pointB [in]
1154  * @param x [out] Intersection events are appended to this array.
1155  * @param tolerance [in] If the input intersection_tolerance <= 0.0,
1156  * then 0.001 is used.
1157  * @param curveB_domain [in] optional restriction on curveB t domain
1158  * @param treeB [in] optional curve tree for curveB, to avoid re-computation
1159  *
1160  * @return True for an intersection. False for no intersection.
1161  */
1162 extern BREP_EXPORT bool
1163 ON_Intersect(const ON_3dPoint &pointA,
1164  const ON_Curve &curveB,
1165  ON_ClassArray<ON_PX_EVENT> &x,
1166  double tolerance = 0.0,
1167  const ON_Interval *curveB_domain = 0,
1168  Subcurve *treeB = 0);
1169 
1170 /**
1171  * An overload of ON_Intersect for point-surface intersection.
1172  * Intersect pointA with surfaceB.
1173  *
1174  * @param pointA [in]
1175  * @param surfaceB [in]
1176  * @param x [out] Intersection events are appended to this array.
1177  * @param tolerance [in] If the input intersection_tolerance <= 0.0,
1178  * then 0.001 is used.
1179  * @param surfaceB_udomain [in] optional restriction on surfaceB u
1180  * domain
1181  * @param surfaceB_vdomain [in] optional restriction on surfaceB v
1182  * domain
1183  * @param treeB [in] optional surface tree for surfaceB, to avoid
1184  * re-computation
1185  *
1186  * @return True for an intersection. False for no intersection.
1187  */
1188 extern BREP_EXPORT bool
1189 ON_Intersect(const ON_3dPoint &pointA,
1190  const ON_Surface &surfaceB,
1191  ON_ClassArray<ON_PX_EVENT> &x,
1192  double tolerance = 0.0,
1193  const ON_Interval *surfaceB_udomain = 0,
1194  const ON_Interval *surfaceB_vdomain = 0,
1195  Subsurface *treeB = 0);
1196 
1197 /**
1198  * An overload of ON_Intersect for curve-curve intersection.
1199  * Intersect curveA with curveB.
1200  *
1201  * Parameters:
1202  * @param curveA [in]
1203  * @param curveB [in]
1204  * @param x [out] Intersection events are appended to this array.
1205  * @param intersection_tolerance [in] If the distance from a point
1206  * on curveA to curveB is <= intersection tolerance, then the
1207  * point will be part of an intersection event. If the input
1208  * intersection_tolerance <= 0.0, then 0.001 is used.
1209  * @param overlap_tolerance [in] If t1 and t2 are parameters of
1210  * curveA's intersection events and the distance from curveA(t)
1211  * to curveB is <= overlap_tolerance for every t1 <= t <= t2,
1212  * then the event will be returned as an overlap event. If the
1213  * input overlap_tolerance <= 0.0, then
1214  * intersection_tolerance * 2.0 is used.
1215  * @param curveA_domain [in] optional restriction on curveA domain
1216  * @param curveB_domain [in] optional restriction on curveB domain
1217  * @param treeA [in] optional curve tree for curveA, to avoid re
1218  * computation
1219  * @param treeB [in] optional curve tree for curveB, to avoid re
1220  * computation
1221  *
1222  * @return Number of intersection events appended to x.
1223  */
1224 extern BREP_EXPORT int
1225 ON_Intersect(const ON_Curve *curveA,
1226  const ON_Curve *curveB,
1227  ON_SimpleArray<ON_X_EVENT> &x,
1228  double intersection_tolerance = 0.0,
1229  double overlap_tolerance = 0.0,
1230  const ON_Interval *curveA_domain = 0,
1231  const ON_Interval *curveB_domain = 0,
1232  Subcurve *treeA = 0,
1233  Subcurve *treeB = 0);
1234 
1235 /**
1236  * An overload of ON_Intersect for curve-surface intersection.
1237  * Intersect curveA with surfaceB.
1238  *
1239  * @param curveA [in]
1240  * @param surfaceB [in]
1241  * @param x [out] Intersection events are appended to this array.
1242  * @param intersection_tolerance [in] If the distance from a
1243  * point on curveA to the surface is <= intersection tolerance,
1244  * then the point will be part of an intersection event, or
1245  * there is an intersection event the point leads to. If the
1246  * input intersection_tolerance <= 0.0, then 0.001 is used.
1247  * @param overlap_tolerance [in] If the input overlap_tolerance
1248  * <= 0.0, then 2.0*intersection_tolerance is used. Otherwise,
1249  * overlap tolerance must be >= intersection_tolerance. In all
1250  * cases, the intersection calculation is performed with an
1251  * overlap_tolerance that is >= intersection_tolerance. If t1
1252  * and t2 are curve parameters of intersection events and the
1253  * distance from curve(t) to the surface is <=
1254  * overlap_tolerance for every t1 <= t <= t2, then the event
1255  * will be returned as an overlap event.
1256  * @param curveA_domain [in] optional restriction on curveA domain
1257  * @param surfaceB_udomain [in] optional restriction on surfaceB
1258  * u domain
1259  * @param surfaceB_vdomain [in] optional restriction on surfaceB
1260  * v domain
1261  * @param overlap2d [out] return the 2D overlap curves on surfaceB.
1262  * overlap2d[i] is the curve for event x[i].
1263  * @param treeA [in] optional curve tree for curveA, to avoid
1264  * re-computation
1265  * @param treeB [in] optional surface tree for surfaceB, to avoid
1266  * re-computation
1267  *
1268  * @return Number of intersection events appended to x.
1269  */
1270 extern BREP_EXPORT int
1271 ON_Intersect(const ON_Curve *curveA,
1272  const ON_Surface *surfaceB,
1273  ON_SimpleArray<ON_X_EVENT> &x,
1274  double intersection_tolerance = 0.0,
1275  double overlap_tolerance = 0.0,
1276  const ON_Interval *curveA_domain = 0,
1277  const ON_Interval *surfaceB_udomain = 0,
1278  const ON_Interval *surfaceB_vdomain = 0,
1279  ON_CurveArray *overlap2d = 0,
1280  Subcurve *treeA = 0,
1281  Subsurface *treeB = 0);
1282 
1283 /**
1284  * An overload of ON_Intersect for surface-surface intersection.
1285  * Intersect surfaceA with surfaceB.
1286  *
1287  * @param surfaceA [in]
1288  * @param surfaceB [in]
1289  * @param x [out] Intersection events are appended to this array.
1290  * @param intersection_tolerance [in] If the input
1291  * intersection_tolerance <= 0.0, then 0.001 is used.
1292  * @param overlap_tolerance [in] If positive, then overlap_tolerance
1293  * must be >= intersection_tolerance and is used to test for
1294  * overlapping regions. If the input overlap_tolerance <= 0.0,
1295  * then 2*intersection_tolerance is used.
1296  * @param fitting_tolerance [in] If fitting_tolerance is > 0 and
1297  * >= intersection_tolerance, then the intersection curves are
1298  * fit to this tolerance. If input fitting_tolerance <= 0.0 or
1299  * < intersection_tolerance, then intersection_tolerance is used.
1300  * @param surfaceA_udomain [in] optional restriction on surfaceA
1301  * u domain
1302  * @param surfaceA_vdomain [in] optional restriction on surfaceA
1303  * v domain
1304  * @param surfaceB_udomain [in] optional restriction on surfaceB
1305  * u domain
1306  * @param surfaceB_vdomain [in] optional restriction on surfaceB
1307  * v domain
1308  * @param treeA [in] optional surface tree for surfaceA, to avoid
1309  * re-computation
1310  * @param treeB [in] optional surface tree for surfaceB, to avoid
1311  * re-computation
1312  *
1313  * @return Number of intersection events appended to x.
1314  */
1315 extern BREP_EXPORT int
1316 ON_Intersect(const ON_Surface *surfA,
1317  const ON_Surface *surfB,
1318  ON_ClassArray<ON_SSX_EVENT> &x,
1319  double intersection_tolerance = 0.0,
1320  double overlap_tolerance = 0.0,
1321  double fitting_tolerance = 0.0,
1322  const ON_Interval *surfaceA_udomain = 0,
1323  const ON_Interval *surfaceA_vdomain = 0,
1324  const ON_Interval *surfaceB_udomain = 0,
1325  const ON_Interval *surfaceB_vdomain = 0,
1326  Subsurface *treeA = 0,
1327  Subsurface *treeB = 0);
1328 
1329 enum op_type {
1330  BOOLEAN_UNION = 0,
1331  BOOLEAN_INTERSECT = 1,
1332  BOOLEAN_DIFF = 2,
1333  BOOLEAN_XOR = 3
1334 };
1335 
1336 /**
1337  * Evaluate NURBS boolean operations.
1338  *
1339  * @param brepO [out]
1340  * @param brepA [in]
1341  * @param brepB [in]
1342  * @param operation [in]
1343  */
1344 extern BREP_EXPORT int
1345 ON_Boolean(ON_Brep *brepO, const ON_Brep *brepA, const ON_Brep *brepB, op_type operation);
1346 
1347 /**
1348  * Get the curve segment between param a and param b
1349  *
1350  * @param in [in] the curve to split
1351  * @param a, b [in] either of them can be the larger one
1352  *
1353  * @return the result curve segment. NULL for error.
1354  */
1355 extern BREP_EXPORT ON_Curve *
1356 sub_curve(const ON_Curve *in, double a, double b);
1357 
1358 /**
1359  * Get the sub-surface whose u \in [a,b] or v \in [a, b]
1360  *
1361  * @param in [in] the surface to split
1362  * @param dir [in] 0: u-split, 1: v-split
1363  * @param a, b [in] either of them can be the larger one
1364  *
1365  * @return the result sub-surface. NULL for error.
1366  */
1367 extern BREP_EXPORT ON_Surface *
1368 sub_surface(const ON_Surface *in, int dir, double a, double b);
1369 } /* extern C++ */
1370 #endif
1371 
1372 #endif /* BREP_H */
1373 /** @} */
1374 /*
1375  * Local Variables:
1376  * mode: C
1377  * tab-width: 8
1378  * indent-tabs-mode: t
1379  * c-file-style: "stroustrup"
1380  * End:
1381  * ex: shiftwidth=4 tabstop=8
1382  */
bool sortX(BRNode *first, BRNode *second)
bool ON_Intersect(const ON_3dPoint &pointA, const ON_3dPoint &pointB, ON_ClassArray< ON_PX_EVENT > &x, double tol)
Definition: intersect.cpp:647
ON_Curve * interpolateCurve(ON_2dPointArray &samples)
ON_2dPoint UnwrapUVPoint(const ON_Surface *surf, const ON_2dPoint &pt, double tol)
#define LIKELY(expression)
Definition: common.h:261
if lu s
Definition: nmg_mod.c:3860
#define VSETALL(a, s)
Definition: color.c:54
bool isFlat(const ON_2dPoint &p1, const ON_2dPoint &m, const ON_2dPoint &p2, double flatness)
bool Find3DCurveSeamCrossing(PBCData &data, double t0, double t1, double offset, double &seam_t, ON_2dPoint &from, ON_2dPoint &to, double tol, double same_point_tol, double within_distance_tol)
Header file for the BRL-CAD common definitions.
struct _bounding_volume_placeholder BrepBoundingVolume
void brep_r(const ON_Surface *surf, plane_ray &pr, pt2d_t uv, ON_3dPoint &pt, ON_3dVector &su, ON_3dVector &sv, pt2d_t R)
ustring closest
void DumpSSXEvent(ON_SSX_EVENT &x, ON_TextLog &text_log)
Definition: ssx_event.cpp:30
int IsAtSeam(const ON_Surface *surf, int dir, double u, double v, double tol)
void SwapUVSeamPoint(const ON_Surface *surf, ON_2dPoint &p, int hint)
bool check_pullback_data(std::list< PBCData * > &pbcs)
bool get_closest_point(ON_2dPoint &outpt, ON_BrepFace *face, const ON_3dPoint &point, SurfaceTree *tree, double tolerance)
ON_2dPointArray * pullback_samples(PBCData *data, double t, double s, double same_point_tol, double within_distance_tol)
Definition: color.c:49
COMPLEX data[64]
Definition: fftest.c:34
ON_NurbsCurve * interpolateLocalCubicCurve(ON_2dPointArray &Q)
void brep_get_plane_ray(ON_Ray &r, plane_ray &pr)
#define __BEGIN_DECLS
Definition: common.h:73
struct _brep_cdbitem brep_cdbitem
#define NEAR_ZERO(val, epsilon)
Definition: color.c:55
ON_Curve * pullback_curve(const brlcad::SurfaceTree *surfacetree, const ON_Surface *surf, const ON_Curve *curve, double tolerance, double flatness)
bool FindTrimSeamCrossing(const ON_BrepTrim &trim, double t0, double t1, double &seam_t, ON_2dPoint &from, ON_2dPoint &to, double tol)
ON_BOOL32 surface_EvNormal(const ON_Surface *surf, double s, double t, ON_3dPoint &point, ON_3dVector &normal, int side, int *hint)
Coord * point
Definition: chull3d.cpp:52
Definition: human.c:197
ON_BOOL32 surface_GetBoundingBox(const ON_Surface *surf, const ON_Interval &u_interval, const ON_Interval &v_interval, ON_BoundingBox &bbox, ON_BOOL32 bGrowBox)
goto out
Definition: nmg_mod.c:3846
void brep_newton_iterate(plane_ray &pr, pt2d_t R, ON_3dVector &su, ON_3dVector &sv, pt2d_t uv, pt2d_t out_uv)
struct _on_brep_placeholder ON_Brep
ON_Surface * sub_surface(const ON_Surface *in, int dir, double a, double b)
Definition: intersect.cpp:286
bool surface_GetClosestPoint3dFirstOrder(const ON_Surface *surf, const ON_3dPoint &p, ON_2dPoint &p2d, ON_3dPoint &p3d, double &current_distance, int quadrant, double same_point_tol, double within_distance_tol)
int check_pullback_singularity_bridge(const ON_Surface *surf, const ON_2dPoint &p1, const ON_2dPoint &p2)
bool trim_GetClosestPoint3dFirstOrder(const ON_BrepTrim &trim, const ON_3dPoint &p, ON_2dPoint &p2d, double &t, double &distance, const ON_Interval *interval, double same_point_tol, double within_distance_tol)
#define ZERO(val)
Definition: units.c:38
ON_Curve * sub_curve(const ON_Curve *in, double a, double b)
Definition: intersect.cpp:220
#define _BU_ATTR_ALWAYS_INLINE
Definition: defines.h:166
void utah_ray_planes(const ON_Ray &r, ON_3dVector &p1, double &p1d, ON_3dVector &p2, double &p2d)
#define R
Definition: msr.c:55
bool ConsecutivePointsCrossClosedSeam(const ON_Surface *surf, const ON_2dPoint &pt, const ON_2dPoint &prev_pt, int &udir, int &vdir, double tol)
int dummy
Definition: brep.h:100
void ForceToClosestSeam(const ON_Surface *surf, ON_2dPoint &pt, double tol)
ON_BOOL32 face_GetBoundingBox(const ON_BrepFace &face, ON_BoundingBox &bbox, ON_BOOL32 bGrowBox)
boost::shared_ptr< MathFunction > ct
Definition: vm_test.cpp:34
double DistToNearestClosedSeam(const ON_Surface *surf, const ON_2dPoint &pt)
#define __END_DECLS
Definition: common.h:74
#define Q
Definition: msr.c:54
int ON_Boolean(ON_Brep *evaluated_brep, const ON_Brep *brep1, const ON_Brep *brep2, op_type operation)
Definition: boolean.cpp:3891
bool sortY(BRNode *first, BRNode *second)
int IsAtSingularity(const ON_Surface *surf, double u, double v, double tol)
double fastf_t
Definition: defines.h:300
Definition: color.c:50
bool ON_NearZero(double val, double epsilon)
Return truthfully whether a value is within a specified epsilon distance from zero.
#define UNLIKELY(expression)
Definition: common.h:282