BRL-CAD
boolean.cpp
Go to the documentation of this file.
1 /* B O O L E A N . C P P
2  * BRL-CAD
3  *
4  * Copyright (c) 2013-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 /** @file boolean.cpp
21  *
22  * Evaluate NURBS booleans (union, intersection and difference).
23  *
24  */
25 
26 #include "common.h"
27 
28 #include <assert.h>
29 #include <vector>
30 #include <stack>
31 #include <queue>
32 #include <set>
33 #include <map>
34 #include <algorithm>
35 
36 #include "vmath.h"
37 #include "bio.h"
38 #include "bu/log.h"
39 #include "brep.h"
40 #include "raytrace.h"
41 #include "brep_except.h"
42 
43 // Whether to output the debug messages about b-rep booleans.
44 #define DEBUG_BREP_BOOLEAN 0
45 
46 // tol value used in ON_Intersect()s. We use a smaller tolerance than the
47 // default one 0.001.
48 #define INTERSECTION_TOL 1e-4
49 
50 // tol value used in ON_3dVector::IsParallelTo(). We use a smaller tolerance
51 // than the default one ON_PI/180.
52 #define ANGLE_TOL ON_PI/1800.0
53 
55  ON_3dPoint m_pt; // 3D intersection point
56  double m_seg_t; // param on the loop curve
57  int m_loop_seg; // which curve of the loop
58  int m_ssx_curve; // which intersection curve
59  int m_curve_pos; // rank on the chain
60  double m_curve_t; // param on the SSI curve
61  enum {
63  IN,
64  OUT,
66  } m_dir; // dir is going inside/outside
67  int m_split_li; // between clx_points[m_split_li] and
68  // clx_points[m_split_li+1]
69  // after the outerloop is split
70 };
71 
72 
73 // A structure to represent the curve segments generated from surface-surface
74 // intersections, including some information needed by the connectivity graph
75 struct SSICurve {
76  ON_Curve *m_curve;
77 
79  {
80  m_curve = NULL;
81  }
82 
83  SSICurve(ON_Curve *curve)
84  {
85  m_curve = curve;
86  }
87 
89  {
90  SSICurve *out = new SSICurve();
91  if (out != NULL) {
92  *out = *this;
93  out->m_curve = m_curve->Duplicate();
94  }
95  return out;
96  }
97 };
98 
99 HIDDEN void
100 append_to_polycurve(ON_Curve *curve, ON_PolyCurve &polycurve);
101 // We link the SSICurves that share an endpoint, and form this new structure,
102 // which has many similar behaviors as ON_Curve, e.g. PointAt(), Reverse().
103 struct LinkedCurve {
104 private:
105  ON_Curve *m_curve; // an explicit storage of the whole curve
106 public:
107  // The curves contained in this LinkedCurve, including
108  // the information needed by the connectivity graph
109  ON_SimpleArray<SSICurve> m_ssi_curves;
110 
111  // Default constructor
113  {
114  m_curve = NULL;
115  }
116 
117  void Empty()
118  {
119  m_ssi_curves.Empty();
120  delete m_curve;
121  m_curve = NULL;
122  }
123 
125  {
126  Empty();
127  }
128 
130  {
131  Empty();
132  m_curve = _lc.m_curve ? _lc.m_curve->Duplicate() : NULL;
133  m_ssi_curves = _lc.m_ssi_curves;
134  return *this;
135  }
136 
137  ON_3dPoint PointAtStart() const
138  {
139  if (m_ssi_curves.Count()) {
140  return m_ssi_curves[0].m_curve->PointAtStart();
141  } else {
142  return ON_3dPoint::UnsetPoint;
143  }
144  }
145 
146  ON_3dPoint PointAtEnd() const
147  {
148  if (m_ssi_curves.Count()) {
149  return m_ssi_curves.Last()->m_curve->PointAtEnd();
150  } else {
151  return ON_3dPoint::UnsetPoint;
152  }
153  }
154 
155  bool IsClosed() const
156  {
157  if (m_ssi_curves.Count() == 0) {
158  return false;
159  }
160  return PointAtStart().DistanceTo(PointAtEnd()) < ON_ZERO_TOLERANCE;
161  }
162 
163  bool IsValid() const
164  {
165  // Check whether the curve has "gaps".
166  for (int i = 1; i < m_ssi_curves.Count(); i++) {
167  if (m_ssi_curves[i].m_curve->PointAtStart().DistanceTo(m_ssi_curves[i - 1].m_curve->PointAtEnd()) >= ON_ZERO_TOLERANCE) {
168  bu_log("The LinkedCurve is not valid.\n");
169  return false;
170  }
171  }
172  return true;
173  }
174 
175  bool Reverse()
176  {
177  ON_SimpleArray<SSICurve> new_array;
178  for (int i = m_ssi_curves.Count() - 1; i >= 0; i--) {
179  if (!m_ssi_curves[i].m_curve->Reverse()) {
180  return false;
181  }
182  new_array.Append(m_ssi_curves[i]);
183  }
184  m_ssi_curves = new_array;
185  return true;
186  }
187 
188  void Append(const LinkedCurve &lc)
189  {
190  m_ssi_curves.Append(lc.m_ssi_curves.Count(), lc.m_ssi_curves.Array());
191  }
192 
193  void Append(const SSICurve &sc)
194  {
195  m_ssi_curves.Append(sc);
196  }
197 
198  void AppendCurvesToArray(ON_SimpleArray<ON_Curve *> &arr) const
199  {
200  for (int i = 0; i < m_ssi_curves.Count(); i++) {
201  arr.Append(m_ssi_curves[i].m_curve->Duplicate());
202  }
203  }
204 
205  const ON_Curve *Curve()
206  {
207  if (m_curve != NULL) {
208  return m_curve;
209  }
210  if (m_ssi_curves.Count() == 0 || !IsValid()) {
211  return NULL;
212  }
213  ON_PolyCurve *polycurve = new ON_PolyCurve;
214  for (int i = 0; i < m_ssi_curves.Count(); i++) {
215  append_to_polycurve(m_ssi_curves[i].m_curve->Duplicate(), *polycurve);
216  }
217  m_curve = polycurve;
218  return m_curve;
219  }
220 
221  const ON_3dPoint PointAt(double t)
222  {
223  const ON_Curve *c = Curve();
224  if (c == NULL) {
225  return ON_3dPoint::UnsetPoint;
226  }
227  return c->PointAt(t);
228  }
229 
230  const ON_Interval Domain()
231  {
232  const ON_Curve *c = Curve();
233  if (c == NULL) {
234  return ON_Interval::EmptyInterval;
235  }
236  return c->Domain();
237  }
238 
239  ON_Curve *SubCurve(double t1, double t2)
240  {
241  const ON_Curve *c = Curve();
242  if (c == NULL) {
243  return NULL;
244  }
245  try {
246  return sub_curve(c, t1, t2);
247  } catch (InvalidInterval &e) {
248  bu_log("%s", e.what());
249  return NULL;
250  }
251  }
252 };
253 
254 
255 struct TrimmedFace {
256  // curve segments in the face's outer loop
257  ON_SimpleArray<ON_Curve *> m_outerloop;
258  // several inner loops, each has some curves
259  std::vector<ON_SimpleArray<ON_Curve *> > m_innerloop;
260  const ON_BrepFace *m_face;
261  enum {
262  UNKNOWN = -1,
264  BELONG = 1
266  bool m_rev;
267 
268  // Default constructor
270  {
271  m_face = NULL;
273  m_rev = false;
274  }
275 
276  // Destructor
278  {
279  // Delete the curve segments if it's not belong to the result.
280  if (m_belong_to_final != BELONG) {
281  for (int i = 0; i < m_outerloop.Count(); i++) {
282  if (m_outerloop[i]) {
283  delete m_outerloop[i];
284  m_outerloop[i] = NULL;
285  }
286  }
287  for (unsigned int i = 0; i < m_innerloop.size(); i++) {
288  for (int j = 0; j < m_innerloop[i].Count(); j++) {
289  if (m_innerloop[i][j]) {
290  delete m_innerloop[i][j];
291  m_innerloop[i][j] = NULL;
292  }
293  }
294  }
295  }
296  }
297 
299  {
300  TrimmedFace *out = new TrimmedFace();
301  out->m_face = m_face;
302  for (int i = 0; i < m_outerloop.Count(); i++) {
303  if (m_outerloop[i]) {
304  out->m_outerloop.Append(m_outerloop[i]->Duplicate());
305  }
306  }
307  out->m_innerloop = m_innerloop;
308  for (unsigned int i = 0; i < m_innerloop.size(); i++) {
309  for (int j = 0; j < m_innerloop[i].Count(); j++) {
310  if (m_innerloop[i][j]) {
311  out->m_innerloop[i][j] = m_innerloop[i][j]->Duplicate();
312  }
313  }
314  }
315  return out;
316  }
317 };
318 
319 HIDDEN int
321 {
322  // Use for sorting an array. Use strict FP comparison.
323  if (p1->m_loop_seg != p2->m_loop_seg) {
324  return p1->m_loop_seg - p2->m_loop_seg;
325  }
326  return p1->m_seg_t > p2->m_seg_t ? 1 : (p1->m_seg_t < p2->m_seg_t ? -1 : 0);
327 }
328 
329 
330 HIDDEN int
332 {
333  // Use for sorting an array. Use strict FP comparison.
334  return p1->m_curve_t > p2->m_curve_t ? 1 : (p1->m_curve_t < p2->m_curve_t ? -1 : 0);
335 }
336 
337 
338 HIDDEN void
339 append_to_polycurve(ON_Curve *curve, ON_PolyCurve &polycurve)
340 {
341  // use this function rather than ON_PolyCurve::Append() to avoid
342  // getting nested polycurves, which makes ON_Brep::IsValid() to fail.
343 
344  ON_PolyCurve *nested = ON_PolyCurve::Cast(curve);
345  if (nested != NULL) {
346  // The input curve is a polycurve
347  const ON_CurveArray &segments = nested->SegmentCurves();
348  for (int i = 0; i < segments.Count(); i++) {
349  append_to_polycurve(segments[i]->Duplicate(), polycurve);
350  }
351  delete nested;
352  } else {
353  polycurve.Append(curve);
354  }
355 }
356 
357 
358 HIDDEN bool
359 is_loop_valid(const ON_SimpleArray<ON_Curve *> &loop, double tolerance, ON_PolyCurve *polycurve = NULL)
360 {
361  bool delete_curve = false;
362  bool ret = true;
363 
364  if (loop.Count() == 0) {
365  bu_log("The input loop is empty.\n");
366  ret = false;
367  }
368 
369  // First, use a ON_PolyCurve to represent the loop.
370  if (ret) {
371  if (polycurve == NULL) {
372  polycurve = new ON_PolyCurve;
373  if (polycurve) {
374  delete_curve = true;
375  } else {
376  ret = false;
377  }
378  }
379  }
380 
381  // Check the loop is continuous and closed or not.
382  if (ret) {
383  if (loop[0] != NULL) {
384  append_to_polycurve(loop[0]->Duplicate(), *polycurve);
385  }
386  for (int i = 1 ; i < loop.Count(); i++) {
387  if (loop[i] && loop[i - 1] && loop[i]->PointAtStart().DistanceTo(loop[i - 1]->PointAtEnd()) < ON_ZERO_TOLERANCE) {
388  append_to_polycurve(loop[i]->Duplicate(), *polycurve);
389  } else {
390  bu_log("The input loop is not continuous.\n");
391  ret = false;
392  }
393  }
394  }
395  if (ret && (polycurve->PointAtStart().DistanceTo(polycurve->PointAtEnd()) >= ON_ZERO_TOLERANCE ||
396  !polycurve->IsClosed()))
397  {
398  bu_log("The input loop is not closed.\n");
399  ret = false;
400  }
401 
402  if (ret) {
403  // Check whether the loop is degenerated.
404  ON_BoundingBox bbox = polycurve->BoundingBox();
405  ret = !ON_NearZero(bbox.Diagonal().Length(), tolerance)
406  && !polycurve->IsLinear(tolerance);
407  }
408 
409  if (delete_curve) {
410  delete polycurve;
411  }
412 
413  return ret;
414 }
415 
416 enum {
419 };
420 
421 // Returns whether the point is inside/on or outside/on the loop
422 // boundary.
423 //
424 // Throws InvalidGeometry if loop is invalid.
425 //
426 // If you want to know whether this point is on the loop boundary,
427 // call is_point_on_loop().
428 HIDDEN int
429 point_loop_location(const ON_2dPoint &pt, const ON_SimpleArray<ON_Curve *> &loop)
430 {
431  ON_PolyCurve polycurve;
432  if (!is_loop_valid(loop, ON_ZERO_TOLERANCE, &polycurve)) {
433  throw InvalidGeometry("point_loop_location() given invalid loop\n");
434  }
435 
436  ON_BoundingBox bbox = polycurve.BoundingBox();
437  if (!bbox.IsPointIn(pt)) {
438  return OUTSIDE_OR_ON_LOOP;
439  }
440 
441  // The input point is inside the loop's bounding box.
442  // out must be outside the closed region (and the bbox).
443  ON_2dPoint out = pt + ON_2dVector(bbox.Diagonal());
444  ON_LineCurve linecurve(pt, out);
445  ON_3dVector line_dir = linecurve.m_line.Direction();
446 
447  ON_SimpleArray<ON_X_EVENT> tmp_x;
448  for (int i = 0; i < loop.Count(); ++i) {
449  ON_SimpleArray<ON_X_EVENT> li_x;
450  ON_Intersect(&linecurve, loop[i], li_x, INTERSECTION_TOL);
451 
452  for (int j = 0; j < li_x.Count(); ++j) {
453  // ignore tangent and overlap intersections
454  if (li_x[j].m_type != ON_X_EVENT::ccx_overlap &&
455  !loop[i]->TangentAt(li_x[j].m_b[0]).IsParallelTo(line_dir, ANGLE_TOL))
456  {
457  tmp_x.Append(li_x[j]);
458  }
459  }
460  }
461  ON_SimpleArray<ON_X_EVENT> x_event;
462  for (int i = 0; i < tmp_x.Count(); i++) {
463  int j;
464  for (j = 0; j < x_event.Count(); j++) {
465  if (tmp_x[i].m_A[0].DistanceTo(x_event[j].m_A[0]) < INTERSECTION_TOL &&
466  tmp_x[i].m_A[1].DistanceTo(x_event[j].m_A[1]) < INTERSECTION_TOL &&
467  tmp_x[i].m_B[0].DistanceTo(x_event[j].m_B[0]) < INTERSECTION_TOL &&
468  tmp_x[i].m_B[1].DistanceTo(x_event[j].m_B[1]) < INTERSECTION_TOL)
469  {
470  break;
471  }
472  }
473  if (j == x_event.Count()) {
474  x_event.Append(tmp_x[i]);
475  }
476  }
477 
478  return (x_event.Count() % 2) ? INSIDE_OR_ON_LOOP : OUTSIDE_OR_ON_LOOP;
479 }
480 
481 
482 // Returns whether or not point is on the loop boundary.
483 // Throws InvalidGeometry if loop is invalid.
484 HIDDEN bool
485 is_point_on_loop(const ON_2dPoint &pt, const ON_SimpleArray<ON_Curve *> &loop)
486 {
487  ON_PolyCurve polycurve;
488  if (!is_loop_valid(loop, ON_ZERO_TOLERANCE, &polycurve)) {
489  throw InvalidGeometry("is_point_on_loop() given invalid loop\n");
490  }
491 
492  ON_3dPoint pt3d(pt);
493  for (int i = 0; i < loop.Count(); ++i) {
494  ON_ClassArray<ON_PX_EVENT> px_event;
495  if (ON_Intersect(pt3d, *loop[i], px_event, INTERSECTION_TOL)) {
496  return true;
497  }
498  }
499  return false;
500 }
501 
502 HIDDEN bool
503 is_point_inside_loop(const ON_2dPoint &pt, const ON_SimpleArray<ON_Curve *> &loop)
504 {
505  return (point_loop_location(pt, loop) == INSIDE_OR_ON_LOOP) && !is_point_on_loop(pt, loop);
506 }
507 
508 HIDDEN bool
509 is_point_outside_loop(const ON_2dPoint &pt, const ON_SimpleArray<ON_Curve *> &loop)
510 {
511  return (point_loop_location(pt, loop) == OUTSIDE_OR_ON_LOOP) && !is_point_on_loop(pt, loop);
512 }
513 
514 HIDDEN ON_Interval
515 union_intervals(const ON_SimpleArray<ON_Interval> &intervals)
516 {
517  ON_Interval union_interval;
518  for (int i = 0; i < intervals.Count(); ++i) {
519  union_interval.Union(intervals[i]);
520  }
521  if (!union_interval.IsValid()) {
522  throw IntervalGenerationError("union_intervals() created invalid interval\n");
523  }
524  return union_interval;
525 }
526 
527 HIDDEN ON_Interval
528 intersect_intervals(const ON_Interval &interval1, const ON_Interval &interval2)
529 {
530  ON_Interval intersection_interval;
531  if (!intersection_interval.Intersection(interval1, interval2)) {
532  throw IntervalGenerationError("intersect_intervals() failed to intersect intervals\n");
533  }
534  return intersection_interval;
535 }
536 
537 HIDDEN void
538 replace_curve_with_subcurve(ON_Curve *&curve, const ON_Interval &interval)
539 {
540  try {
541  ON_Curve *subcurve = sub_curve(curve, interval.Min(), interval.Max());
542  delete curve;
543  curve = subcurve;
544  } catch (InvalidInterval &) {
545  throw GeometryGenerationError("replace_curve_with_subcurve(): NULL "
546  "subcurve\n");
547  }
548 }
549 
550 HIDDEN ON_SimpleArray<ON_Interval>
552  ON_Curve *curve2D,
553  const ON_ClassArray<ON_SimpleArray<ON_Curve *> > &face_loops,
554  double isect_tol)
555 {
556  // get curve-loop intersections
557  ON_SimpleArray<double> isect_curve_t;
558  ON_SimpleArray<ON_X_EVENT> ccx_events;
559 
560  for (int i = 0; i < face_loops.Count(); ++i) {
561  for (int j = 0; j < face_loops[i].Count(); ++j) {
562  ON_Intersect(curve2D, face_loops[i][j], ccx_events, isect_tol);
563  }
564  }
565 
566  // get a sorted list of just the parameters on the first curve
567  // where it intersects the outerloop
568  for (int i = 0; i < ccx_events.Count(); i++) {
569  isect_curve_t.Append(ccx_events[i].m_a[0]);
570 
571  if (ccx_events[i].m_type == ON_X_EVENT::ccx_overlap) {
572  isect_curve_t.Append(ccx_events[i].m_a[1]);
573  }
574  }
575  isect_curve_t.QuickSort(ON_CompareIncreasing);
576 
577 
578  // insert start and end parameters so every part of the curve is tested
579  isect_curve_t.Insert(0, curve2D->Domain().Min());
580  isect_curve_t.Append(curve2D->Domain().Max());
581 
582  // if the midpoint of an interval is inside/on the face, keep the
583  // entire interval
584  ON_SimpleArray<ON_Interval> included_intervals;
585  for (int i = 0; i < isect_curve_t.Count() - 1; i++) {
586  ON_Interval interval(isect_curve_t[i], isect_curve_t[i + 1]);
587  if (ON_NearZero(interval.Length(), isect_tol)) {
588  continue;
589  }
590  ON_2dPoint pt = curve2D->PointAt(interval.Mid());
591 
592  bool point_included = false;
593  try {
594  // inside/on outerloop
595  if (!is_point_outside_loop(pt, face_loops[0])) {
596 
597  // outside/on innerloops
598  point_included = true;
599  for (int j = 1; j < face_loops.Count(); ++j) {
600  if (is_point_inside_loop(pt, face_loops[j])) {
601  point_included = false;
602  break;
603  }
604  }
605  }
606  } catch (InvalidGeometry &e) {
607  bu_log("%s", e.what());
608  }
609  if (point_included) {
610  included_intervals.Append(interval);
611  }
612  }
613 
614  // merge continuous intervals
615  ON_SimpleArray<ON_Interval> final_intervals;
616  for (int j, i = 0; i < included_intervals.Count(); i = j) {
617  ON_Interval merged_interval = included_intervals[i];
618 
619  for (j = i + 1; j < included_intervals.Count(); ++j) {
620  ON_Interval &next = included_intervals[j];
621 
622  if (ON_NearZero(next.Min() - merged_interval.Max(), isect_tol)) {
623  ON_Interval new_interval = merged_interval;
624 
625  if (new_interval.Union(next)) {
626  merged_interval = new_interval;
627  } else {
628  break;
629  }
630  } else {
631  break;
632  }
633  }
634  final_intervals.Append(merged_interval);
635  }
636 
637  return final_intervals;
638 }
639 
640 HIDDEN int
641 compare_interval(const ON_Interval *a, const ON_Interval *b)
642 {
643  return a->Compare(*b);
644 }
645 
647  ON_3dPoint min;
648  ON_3dPoint mid;
649  ON_3dPoint max;
650 };
651 
653 public:
654  double min;
655  double mid;
656  double max;
657 
658  void
660  {
661  if (min > mid) {
662  std::swap(min, mid);
663  }
664  if (mid > max) {
665  std::swap(mid, max);
666 
667  if (min > mid) {
668  std::swap(min, mid);
669  }
670  }
671  }
672 };
673 
674 // given parameters in a curve interval, create new interval
675 // parameters that reflect the the non-degenerate (different
676 // dimensioned) curve interval used to generate the curve parameters
679  IntervalParams interval_t,
680  const ON_Curve *curve)
681 {
682  if (!curve->IsClosed()) {
683  return interval_t;
684  }
685 
686  if (interval_t.min > interval_t.max) {
687  std::swap(interval_t.min, interval_t.max);
688  }
689  double min_t = interval_t.min;
690  double max_t = interval_t.max;
691 
692  ON_Interval cdom = curve->Domain();
693  if (!(min_t < max_t || min_t > max_t)) {
694  // if endpoints are both at closed curve joint, put them at
695  // either end of the curve domain
696  if (ON_NearZero(cdom.Min() - min_t, ON_ZERO_TOLERANCE)) {
697  interval_t.max = cdom.Max();
698  } else if (ON_NearZero(cdom.Max() - min_t, ON_ZERO_TOLERANCE)) {
699  interval_t.min = cdom.Min();
700  }
701  } else {
702  // if interval doesn't include midpt, assume the point nearest
703  // the seam needs to be on the opposite side of the domain
704  ON_Interval curr(min_t, max_t);
705  if (!curr.Includes(interval_t.mid)) {
706  if (fabs(cdom.Min() - min_t) > fabs(cdom.Max() - max_t)) {
707  interval_t.max = cdom.Min();
708  } else {
709  interval_t.min = cdom.Max();
710  }
711  }
712  }
713  interval_t.MakeIncreasing();
714 
715  return interval_t;
716 }
717 
719 
720 
721 // given interval points in surface uv space, create new interval
722 // points that reflect the non-degenerate curve parameter interval
723 // used to generate the input points
726  IntervalPoints interval_pts,
727  const ON_Surface *surf)
728 {
729  ON_3dPoint &min_uv = interval_pts.min;
730  ON_3dPoint &max_uv = interval_pts.max;
731 
732  ON_Interval udom = surf->Domain(0);
733  ON_Interval vdom = surf->Domain(1);
734 
735  int seam_min = IsAtSeam(surf, min_uv, ON_ZERO_TOLERANCE);
736  int seam_max = IsAtSeam(surf, max_uv, ON_ZERO_TOLERANCE);
737 
738  if ((seam_min && seam_max) && (min_uv == max_uv)) {
739  // if uv endpoints are identical and on a seam
740  // they need to be on opposite sides of the domain
741  if (ON_NearZero(udom.Min() - min_uv[0], ON_ZERO_TOLERANCE) ||
742  ON_NearZero(udom.Max() - min_uv[0], ON_ZERO_TOLERANCE))
743  {
744  // point on west/east edge becomes one point on west
745  // edge, one point on east edge
746  min_uv[0] = udom.Min();
747  max_uv[0] = udom.Max();
748  } else if (ON_NearZero(vdom.Min() - min_uv[1], ON_ZERO_TOLERANCE) ||
749  ON_NearZero(vdom.Max() - min_uv[1], ON_ZERO_TOLERANCE))
750  {
751  // point on south/north edge becomes one point on
752  // south edge, one point on north edge
753  min_uv[1] = vdom.Min();
754  max_uv[1] = vdom.Max();
755  }
756  } else if (!seam_min != !seam_max) { // XOR
757  // if just one point is on a seam, make sure it's on the
758  // correct side of the domain
759 
760  // get interval midpoint in uv space
761  ON_ClassArray<ON_PX_EVENT> events;
762  ON_3dPoint midpt = surf->PointAt(interval_pts.mid.x,
763  interval_pts.mid.y);
764  ON_Intersect(midpt, *surf, events, INTERSECTION_TOL);
765 
766  if (events.Count() == 1) {
767  // Check that the non-seam parameter of the
768  // midpoint is between the non-seam parameters of
769  // the interval uv on the seam and the other
770  // interval uv. If the midpoint non-seam parameter
771  // is outside the interval we'll move the seam_uv
772  // to the other side of the domain.
773  //
774  // For example, if the surface has a seam at the
775  // west/east edge and we have seam_uv (0.0, .1)
776  // and other_uv (.5, .6) we'll check that the
777  // interval midpoint uv has a u in [0.0, .5].
778  //
779  // A midpoint of (.25, .25) would be okay. A
780  // midpoint of (.75, .25) would necessitate us
781  // moving the seam_uv from the west edge to the
782  // east edge, e.g (1.0, .1).
783  int seam = seam_min ? seam_min : seam_max;
784  ON_3dPoint &seam_uv = seam_min ? min_uv : max_uv;
785  ON_3dPoint other_uv = seam_min ? max_uv : min_uv;
786 
787  double *seam_t = &seam_uv[1];
788  double seam_opp_t = vdom.Max() - seam_uv[1];
789  double other_t = other_uv[1];
790  double midpt_t = events[0].m_b[1];
791  if (seam != SEAM_ALONG_U) {
792  seam_t = &seam_uv[0];
793  seam_opp_t = udom.Max() - seam_uv[0];
794  other_t = other_uv[0];
795  midpt_t = events[0].m_b[0];
796  }
797 
798  ON_Interval curr(*seam_t, other_t);
799  if (!curr.Includes(midpt_t)) {
800  // need to flip the seam point to the other
801  // side of the domain
802  *seam_t = seam_opp_t;
803  }
804  }
805  }
806  return interval_pts;
807 }
808 
811  const ON_Interval &interval_2d,
812  const ON_Curve *curve2d,
813  const ON_Surface *surf)
814 {
815  // initialize endpoints from evaluated surface uv points
816  IntervalPoints pts;
817  pts.min = curve2d->PointAt(interval_2d.Min());
818  pts.mid = curve2d->PointAt(interval_2d.Mid());
819  pts.max = curve2d->PointAt(interval_2d.Max());
820 
821  return uv_interval_from_points(pts, surf);
822 }
823 
824 HIDDEN std::pair<IntervalPoints, IntervalPoints>
826  const ON_Interval &interval_2d,
827  const ON_Curve *curve2d,
828  const ON_Surface *surf,
829  double split_t)
830 {
831  std::pair<IntervalPoints, IntervalPoints> out;
832 
833  ON_Interval left(interval_2d.Min(), split_t);
834  ON_Interval right(split_t, interval_2d.Max());
835 
836  out.first = interval_2d_to_uv(left, curve2d, surf);
837  out.second = interval_2d_to_uv(right, curve2d, surf);
838 
839  return out;
840 }
841 
844  const IntervalPoints &interval_uv,
845  const ON_Surface *surf)
846 {
847  // evaluate surface at uv points to get 3d interval points
848  IntervalPoints pts_3d;
849  pts_3d.min = surf->PointAt(interval_uv.min.x, interval_uv.min.y);
850  pts_3d.mid = surf->PointAt(interval_uv.mid.x, interval_uv.mid.y);
851  pts_3d.max = surf->PointAt(interval_uv.max.x, interval_uv.max.y);
852 
853  return pts_3d;
854 }
855 
858  const IntervalPoints &pts_3d,
859  const ON_Curve *curve3d)
860 {
861  ON_ClassArray<ON_PX_EVENT> events;
862  ON_Intersect(pts_3d.min, *curve3d, events, INTERSECTION_TOL);
863  ON_Intersect(pts_3d.mid, *curve3d, events, INTERSECTION_TOL);
864  ON_Intersect(pts_3d.max, *curve3d, events, INTERSECTION_TOL);
865 
866  if (events.Count() != 3) {
867  throw AlgorithmError("points_3d_to_params_3d: conversion failed\n");
868  }
869 
870  IntervalParams params_3d;
871  params_3d.min = events[0].m_b[0];
872  params_3d.mid = events[1].m_b[0];
873  params_3d.max = events[2].m_b[0];
874 
875  return params_3d;
876 }
877 
878 HIDDEN std::vector<ON_Interval>
880  const ON_Interval &interval,
881  const ON_Curve *curve2d,
882  const ON_Curve *curve3d,
883  const ON_Surface *surf)
884 {
885  std::vector<ON_Interval> intervals_3d;
886 
887  ON_Interval c2_dom = curve2d->Domain();
888  ON_Interval c3_dom = curve3d->Domain();
889 
890  c2_dom.MakeIncreasing();
891  if (ON_NearZero(interval.Min() - c2_dom.Min(), ON_ZERO_TOLERANCE) &&
892  ON_NearZero(interval.Max() - c2_dom.Max(), ON_ZERO_TOLERANCE))
893  {
894  // entire 2d domain equates to entire 3d domain
895  c3_dom.MakeIncreasing();
896  if (c3_dom.IsValid()) {
897  intervals_3d.push_back(c3_dom);
898  }
899  } else {
900  // get 2d curve interval points as uv points
901  IntervalPoints interval_uv =
902  interval_2d_to_uv(interval, curve2d, surf);
903 
904  // evaluate surface at uv points to get 3d interval points
905  IntervalPoints pts_3d = points_uv_to_3d(interval_uv, surf);
906 
907  // convert 3d points into 3d curve parameters
908  try {
909  std::vector<IntervalParams> int_params;
910 
911  IntervalParams curve_t = points_3d_to_params_3d(pts_3d, curve3d);
912 
913  if (curve3d->IsClosed()) {
914  // get 3d seam point as surf point
915  ON_3dPoint seam_pt = curve3d->PointAt(c3_dom.Min());
916 
917  ON_ClassArray<ON_PX_EVENT> events;
918  ON_Intersect(seam_pt, *surf, events, INTERSECTION_TOL);
919 
920  if (events.Count() == 1) {
921  ON_3dPoint surf_pt = events[0].m_b;
922  std::vector<double> split_t;
923 
924  // get surf point as 2d curve t
925  events.Empty();
926  ON_Intersect(surf_pt, *curve2d, events, INTERSECTION_TOL);
927  if (events.Count() == 1) {
928  split_t.push_back(events[0].m_b[0]);
929  }
930 
931  int surf_seam = IsAtSeam(surf, surf_pt, ON_ZERO_TOLERANCE);
932  if (surf_seam != SEAM_NONE) {
933  // move surf_pt to other side of seam
934  if (surf_seam == SEAM_ALONG_U || surf_seam == SEAM_ALONG_UV) {
935  ON_Interval vdom = surf->Domain(1);
936  if (ON_NearZero(surf_pt.y - vdom.Min(),
937  ON_ZERO_TOLERANCE)) {
938  surf_pt.y = vdom.Max();
939  } else {
940  surf_pt.y = vdom.Min();
941  }
942  }
943  if (surf_seam == SEAM_ALONG_V || surf_seam == SEAM_ALONG_UV) {
944  ON_Interval udom = surf->Domain(0);
945  if (ON_NearZero(surf_pt.x - udom.Min(),
946  ON_ZERO_TOLERANCE)) {
947  surf_pt.x = udom.Max();
948  } else {
949  surf_pt.x = udom.Min();
950  }
951  }
952  // get alternative surf point as 2d curve t
953  events.Empty();
954  ON_Intersect(surf_pt, *curve2d, events, INTERSECTION_TOL);
955  if (events.Count() == 1) {
956  split_t.push_back(events[0].m_b[0]);
957  }
958  }
959 
960  // see if 3d curve seam point is in the 2d curve interval
961  for (size_t i = 0; i < split_t.size(); ++i) {
962  double min2split = fabs(curve_t.min - split_t[i]);
963  double max2split = fabs(curve_t.max - split_t[i]);
964 
965  if (min2split > ON_ZERO_TOLERANCE ||
966  max2split > ON_ZERO_TOLERANCE)
967  {
968  // split 2d interval at seam point
969  std::pair<IntervalPoints, IntervalPoints> halves =
970  interval_2d_to_2uv(interval, curve2d, surf,
971  split_t[i]);
972 
973  // convert new intervals to 3d curve intervals
974  IntervalPoints left_3d, right_3d;
975  IntervalParams left_t, right_t;
976 
977  left_3d = points_uv_to_3d(halves.first, surf);
978  left_t = points_3d_to_params_3d(left_3d, curve3d);
979  int_params.push_back(left_t);
980 
981  right_3d = points_uv_to_3d(halves.second, surf);
982  right_t = points_3d_to_params_3d(right_3d, curve3d);
983  int_params.push_back(right_t);
984  }
985  }
986  }
987  }
988  if (int_params.size() == 0) {
989  int_params.push_back(curve_t);
990  }
991 
992  // get final 3d intervals
993  for (size_t i = 0; i < int_params.size(); ++i) {
994  curve_t = curve_interval_from_params(int_params[i], curve3d);
995  ON_Interval interval_3d(curve_t.min, curve_t.max);
996  if (interval_3d.IsValid()) {
997  intervals_3d.push_back(interval_3d);
998  }
999  }
1000  } catch (AlgorithmError &e) {
1001  bu_log("%s", e.what());
1002  }
1003  }
1004  return intervals_3d;
1005 }
1006 
1007 
1008 // Convert parameter interval of a 3d curve into the equivalent parameter
1009 // interval on a matching 2d face curve.
1010 HIDDEN ON_Interval
1012  const ON_Interval &interval,
1013  const ON_Curve *curve2d,
1014  const ON_Curve *curve3d,
1015  const ON_BrepFace *face)
1016 {
1017  ON_Interval interval_2d;
1018 
1019  ON_Interval whole_domain = curve3d->Domain();
1020  whole_domain.MakeIncreasing();
1021 
1022  if (ON_NearZero(interval.Min() - whole_domain.Min(), ON_ZERO_TOLERANCE) &&
1023  ON_NearZero(interval.Max() - whole_domain.Max(), ON_ZERO_TOLERANCE))
1024  {
1025  interval_2d = curve2d->Domain();
1026  interval_2d.MakeIncreasing();
1027  } else {
1028  const ON_Surface *surf = face->SurfaceOf();
1029 
1030  IntervalPoints pts;
1031  pts.min = curve3d->PointAt(interval.Min());
1032  pts.mid = curve3d->PointAt(interval.Mid());
1033  pts.max = curve3d->PointAt(interval.Max());
1034 
1035  ON_ClassArray<ON_PX_EVENT> events;
1036  ON_Intersect(pts.min, *surf, events, INTERSECTION_TOL);
1037  ON_Intersect(pts.mid, *surf, events, INTERSECTION_TOL);
1038  ON_Intersect(pts.max, *surf, events, INTERSECTION_TOL);
1039 
1040  if (events.Count() == 3) {
1041  IntervalPoints interval_uv;
1042  interval_uv.min = events[0].m_b;
1043  interval_uv.mid = events[1].m_b;
1044  interval_uv.max = events[2].m_b;
1045 
1046  interval_uv = uv_interval_from_points(interval_uv, surf);
1047 
1048  // intersect surface uv parameters with 2d curve to convert
1049  // surface uv parameters to 2d curve parameters
1050  events.Empty();
1051  ON_Intersect(interval_uv.min, *curve2d, events, INTERSECTION_TOL);
1052  ON_Intersect(interval_uv.mid, *curve2d, events, INTERSECTION_TOL);
1053  ON_Intersect(interval_uv.max, *curve2d, events, INTERSECTION_TOL);
1054 
1055  if (events.Count() == 3) {
1057  curve_t.min = events[0].m_b[0];
1058  curve_t.mid = events[1].m_b[0];
1059  curve_t.max = events[2].m_b[0];
1060 
1061  curve_t = curve_interval_from_params(curve_t, curve2d);
1062  interval_2d.Set(curve_t.min, curve_t.max);
1063  }
1064  }
1065  }
1066  return interval_2d;
1067 }
1068 
1069 HIDDEN void
1071  ON_SimpleArray<ON_Curve *> &subcurves_on1,
1072  ON_SimpleArray<ON_Curve *> &subcurves_on2,
1073  const ON_Brep *brep1,
1074  const ON_Brep *brep2,
1075  int face_i1,
1076  int face_i2,
1077  ON_SSX_EVENT *event)
1078 {
1079  // The ON_SSX_EVENT from SSI is the intersection of two whole surfaces.
1080  // We need to get the part that lies inside both trimmed patches.
1081  // (brep1's face[face_i1] and brep2's face[face_i2])
1082  ON_SimpleArray<ON_SSX_EVENT *> out;
1083 
1084  if (event == NULL) {
1085  return;
1086  }
1087 
1088  if (event->m_curve3d == NULL || event->m_curveA == NULL || event->m_curveB == NULL) {
1089  return;
1090  }
1091 
1092  // get the face loops
1093  if (face_i1 < 0 || face_i1 >= brep1->m_F.Count()) {
1094  bu_log("get_subcurves_inside_faces(): invalid face_i1 (%d).\n", face_i1);
1095  return;
1096  }
1097  if (face_i2 < 0 || face_i2 >= brep2->m_F.Count()) {
1098  bu_log("get_subcurves_inside_faces(): invalid face_i2 (%d).\n", face_i2);
1099  return;
1100  }
1101 
1102  const ON_SimpleArray<int> &face1_li = brep1->m_F[face_i1].m_li;
1103  ON_ClassArray<ON_SimpleArray<ON_Curve *> > face1_loops;
1104  for (int i = 0; i < face1_li.Count(); ++i) {
1105  const ON_BrepLoop &brep_loop = brep1->m_L[face1_li[i]];
1106 
1107  ON_SimpleArray<ON_Curve *> loop_curves;
1108  for (int j = 0; j < brep_loop.m_ti.Count(); ++j) {
1109  ON_Curve *trim2d =
1110  brep1->m_C2[brep1->m_T[brep_loop.m_ti[j]].m_c2i];
1111  loop_curves.Append(trim2d);
1112  }
1113  face1_loops.Append(loop_curves);
1114  }
1115 
1116  const ON_SimpleArray<int> &face2_li = brep2->m_F[face_i2].m_li;
1117  ON_ClassArray<ON_SimpleArray<ON_Curve *> > face2_loops;
1118  for (int i = 0; i < face2_li.Count(); ++i) {
1119  const ON_BrepLoop &brep_loop = brep2->m_L[face2_li[i]];
1120  ON_SimpleArray<ON_Curve *> loop_curves;
1121 
1122  for (int j = 0; j < brep_loop.m_ti.Count(); ++j) {
1123  ON_Curve *trim2d =
1124  brep2->m_C2[brep2->m_T[brep_loop.m_ti[j]].m_c2i];
1125  loop_curves.Append(trim2d);
1126  }
1127  face2_loops.Append(loop_curves);
1128  }
1129 
1130  // find the intervals of the curves that are inside/on each face
1131  ON_SimpleArray<ON_Interval> intervals1, intervals2;
1132 
1133  intervals1 = get_curve_intervals_inside_or_on_face(event->m_curveA,
1134  face1_loops, INTERSECTION_TOL);
1135 
1136  intervals2 = get_curve_intervals_inside_or_on_face(event->m_curveB,
1137  face2_loops, INTERSECTION_TOL);
1138 
1139  // get subcurves for each face
1140  for (int i = 0; i < intervals1.Count(); ++i) {
1141  // convert interval on face 1 to equivalent interval on face 2
1142  std::vector<ON_Interval> intervals_3d;
1143  intervals_3d = interval_2d_to_3d(intervals1[i], event->m_curveA,
1144  event->m_curve3d, &brep1->m_F[face_i1]);
1145 
1146  for (size_t j = 0; j < intervals_3d.size(); ++j) {
1147  ON_Interval interval_on2 = interval_3d_to_2d(intervals_3d[j],
1148  event->m_curveB, event->m_curve3d, &brep2->m_F[face_i2]);
1149  if (interval_on2.IsValid()) {
1150  // create subcurve from interval
1151  try {
1152  ON_Curve *subcurve_on2 = sub_curve(event->m_curveB,
1153  interval_on2.Min(), interval_on2.Max());
1154 
1155  subcurves_on2.Append(subcurve_on2);
1156  } catch (InvalidInterval &e) {
1157  bu_log("%s", e.what());
1158  }
1159  }
1160  }
1161 
1162  }
1163  for (int i = 0; i < intervals2.Count(); ++i) {
1164  // convert interval on face 1 to equivalent interval on face 2
1165  std::vector<ON_Interval> intervals_3d;
1166  intervals_3d = interval_2d_to_3d(intervals2[i], event->m_curveB,
1167  event->m_curve3d, &brep2->m_F[face_i2]);
1168 
1169  for (size_t j = 0; j < intervals_3d.size(); ++j) {
1170  ON_Interval interval_on1 = interval_3d_to_2d(intervals_3d[j],
1171  event->m_curveA, event->m_curve3d, &brep1->m_F[face_i1]);
1172  if (interval_on1.IsValid()) {
1173  // create subcurve from interval
1174  try {
1175  ON_Curve *subcurve_on1 = sub_curve(event->m_curveA,
1176  interval_on1.Min(), interval_on1.Max());
1177 
1178  subcurves_on1.Append(subcurve_on1);
1179  } catch (InvalidInterval &e) {
1180  bu_log("%s", e.what());
1181  }
1182  }
1183  }
1184 
1185  }
1186 }
1187 
1188 HIDDEN double
1189 bbox_diagonal_length(ON_Curve *curve)
1190 {
1191  double len = 0.0;
1192  if (curve) {
1193  ON_BoundingBox bbox;
1194  if (curve->GetTightBoundingBox(bbox)) {
1195  len = bbox.Diagonal().Length();
1196  } else {
1197  len = curve->PointAtStart().DistanceTo(curve->PointAtEnd());
1198  }
1199  }
1200  return len;
1201 }
1202 
1203 HIDDEN void
1204 split_curve(ON_Curve *&left, ON_Curve *&right, const ON_Curve *in, double t)
1205 {
1206  try {
1207  left = sub_curve(in, in->Domain().m_t[0], t);
1208  } catch (InvalidInterval &) {
1209  left = NULL;
1210  }
1211  try {
1212  right = sub_curve(in, t, in->Domain().m_t[1]);
1213  } catch (InvalidInterval &) {
1214  right = NULL;
1215  }
1216 }
1217 
1218 HIDDEN double
1220  LinkedCurve *&first,
1221  LinkedCurve *&second,
1222  LinkedCurve &in1,
1223  LinkedCurve &in2)
1224 {
1225  double dist_s1s2 = in1.PointAtStart().DistanceTo(in2.PointAtStart());
1226  double dist_s1e2 = in1.PointAtStart().DistanceTo(in2.PointAtEnd());
1227  double dist_e1s2 = in1.PointAtEnd().DistanceTo(in2.PointAtStart());
1228  double dist_e1e2 = in1.PointAtEnd().DistanceTo(in2.PointAtEnd());
1229 
1230  double min_dist = std::min(dist_s1s2, dist_s1e2);
1231  min_dist = std::min(min_dist, dist_e1s2);
1232  min_dist = std::min(min_dist, dist_e1e2);
1233 
1234  first = second = NULL;
1235  if (dist_s1e2 <= min_dist) {
1236  first = &in2;
1237  second = &in1;
1238  } else if (dist_e1s2 <= min_dist) {
1239  first = &in1;
1240  second = &in2;
1241  } else if (dist_s1s2 <= min_dist) {
1242  if (in1.Reverse()) {
1243  first = &in1;
1244  second = &in2;
1245  }
1246  } else if (dist_e1e2 <= min_dist) {
1247  if (in2.Reverse()) {
1248  first = &in1;
1249  second = &in2;
1250  }
1251  }
1252  return min_dist;
1253 }
1254 
1258  ON_SimpleArray<ON_X_EVENT> events;
1259 };
1260 
1261 HIDDEN ON_ClassArray<LinkedCurve>
1262 get_joinable_ssi_curves(const ON_SimpleArray<SSICurve> &in)
1263 {
1264  ON_SimpleArray<SSICurve> curves;
1265  for (int i = 0; i < in.Count(); ++i) {
1266  curves.Append(in[i]);
1267  }
1268 
1269  for (int i = 0; i < curves.Count(); ++i) {
1270  if (curves[i].m_curve == NULL || curves[i].m_curve->IsClosed()) {
1271  continue;
1272  }
1273  for (int j = i + 1; j < curves.Count(); j++) {
1274  if (curves[j].m_curve == NULL || curves[j].m_curve->IsClosed()) {
1275  continue;
1276  }
1277  ON_Curve *icurve = curves[i].m_curve;
1278  ON_Curve *jcurve = curves[j].m_curve;
1279 
1280  ON_SimpleArray<ON_X_EVENT> events;
1281  ON_Intersect(icurve, jcurve, events, INTERSECTION_TOL);
1282 
1283  if (events.Count() != 1) {
1284  if (events.Count() > 1) {
1285  bu_log("unexpected intersection between curves\n");
1286  }
1287  continue;
1288  }
1289 
1290  ON_X_EVENT event = events[0];
1291  if (event.m_type == ON_X_EVENT::ccx_overlap) {
1292  // curves from adjacent surfaces may overlap and have
1293  // common endpoints, but we don't want the linked
1294  // curve to double back on itself creating a
1295  // degenerate section
1296  ON_Interval dom[2], range[2];
1297  dom[0] = icurve->Domain();
1298  dom[1] = jcurve->Domain();
1299  range[0].Set(event.m_a[0], event.m_a[1]);
1300  range[1].Set(event.m_b[0], event.m_b[1]);
1301 
1302  // overlap endpoints that are near the endpoints
1303  // should be snapped to the endpoints
1304  for (int k = 0; k < 2; ++k) {
1305  dom[k].MakeIncreasing();
1306  range[k].MakeIncreasing();
1307 
1308  for (int l = 0; l < 2; ++l) {
1309  if (ON_NearZero(dom[k].m_t[l] - range[k].m_t[l],
1310  ON_ZERO_TOLERANCE)) {
1311  range[k].m_t[l] = dom[k].m_t[l];
1312  }
1313  }
1314  }
1315 
1316  if (dom[0].Includes(range[0], true) ||
1317  dom[1].Includes(range[1], true))
1318  {
1319  // overlap is in the middle of one or both curves
1320  continue;
1321  }
1322 
1323  // if one curve is completely contained by the other,
1324  // keep just the larger curve (or the first curve if
1325  // they're the same)
1326  if (dom[1] == range[1]) {
1327  curves[j].m_curve = NULL;
1328  continue;
1329  }
1330  if (dom[0] == range[0]) {
1331  curves[i].m_curve = NULL;
1332  continue;
1333  }
1334 
1335  // remove the overlapping portion from the end of one
1336  // curve so the curves meet at just a single point
1337  try {
1338  double start = dom[0].m_t[0];
1339  double end = range[0].m_t[0];
1340  if (ON_NearZero(start - end, ON_ZERO_TOLERANCE)) {
1341  start = range[0].m_t[1];
1342  end = dom[0].m_t[1];
1343  }
1344  ON_Curve *isub = sub_curve(icurve, start, end);
1345 
1346  delete curves[i].m_curve;
1347  curves[i] = isub;
1348  } catch (InvalidInterval &e) {
1349  bu_log("%s", e.what());
1350  }
1351  } else {
1352  // For a single intersection, assume that one or both
1353  // curve endpoints is just a little past where it
1354  // should be. Split the curves at the intersection,
1355  // and discard the portion with the smaller bbox
1356  // diagonal.
1357  ON_Curve *ileft, *iright, *jleft, *jright;
1358  ileft = iright = jleft = jright = NULL;
1359  split_curve(ileft, iright, icurve, event.m_a[0]);
1360  split_curve(jleft, jright, jcurve, event.m_b[0]);
1361 
1362  if (bbox_diagonal_length(ileft) <
1363  bbox_diagonal_length(iright))
1364  {
1365  std::swap(ileft, iright);
1366  }
1367  ON_Curve *isub = ileft;
1368  delete iright;
1369 
1370  if (bbox_diagonal_length(jleft) <
1371  bbox_diagonal_length(jright))
1372  {
1373  std::swap(jleft, jright);
1374  }
1375  ON_Curve *jsub = jleft;
1376  delete jright;
1377 
1378  if (isub && jsub) {
1379  // replace the original ssi curves with the
1380  // trimmed versions
1381  curves[i].m_curve = isub;
1382  curves[j].m_curve = jsub;
1383  isub = jsub = NULL;
1384  }
1385  delete isub;
1386  delete jsub;
1387  }
1388  }
1389  }
1390 
1391  ON_ClassArray<LinkedCurve> out;
1392  for (int i = 0; i < curves.Count(); ++i) {
1393  if (curves[i].m_curve != NULL) {
1394  LinkedCurve linked;
1395  linked.Append(curves[i]);
1396  out.Append(linked);
1397  }
1398  }
1399  return out;
1400 }
1401 
1402 HIDDEN ON_ClassArray<LinkedCurve>
1403 link_curves(const ON_SimpleArray<SSICurve> &in)
1404 {
1405  // There might be two reasons why we need to link these curves.
1406  // 1) They are from intersections with two different surfaces.
1407  // 2) They are not continuous in the other surface's UV domain.
1408 
1409  ON_ClassArray<LinkedCurve> tmp = get_joinable_ssi_curves(in);
1410 
1411  // As usual, we use a greedy approach.
1412  for (int i = 0; i < tmp.Count(); i++) {
1413  for (int j = 0; j < tmp.Count(); j++) {
1414  if (tmp[i].m_ssi_curves.Count() == 0 || tmp[i].IsClosed()) {
1415  break;
1416  }
1417 
1418  if (tmp[j].m_ssi_curves.Count() == 0 || tmp[j].IsClosed() || j == i) {
1419  continue;
1420  }
1421  LinkedCurve *c1 = NULL, *c2 = NULL;
1422  double dist = configure_for_linking(c1, c2, tmp[i], tmp[j]);
1423 
1424  if (dist > INTERSECTION_TOL) {
1425  continue;
1426  }
1427 
1428  if (c1 != NULL && c2 != NULL) {
1429  LinkedCurve new_curve;
1430  new_curve.Append(*c1);
1431  if (dist > ON_ZERO_TOLERANCE) {
1432  new_curve.Append(SSICurve(new ON_LineCurve(c1->PointAtEnd(), c2->PointAtStart())));
1433  }
1434  new_curve.Append(*c2);
1435  tmp[i] = new_curve;
1436  tmp[j].m_ssi_curves.Empty();
1437  }
1438 
1439  // Check whether tmp[i] is closed within a tolerance
1440  if (tmp[i].PointAtStart().DistanceTo(tmp[i].PointAtEnd()) < INTERSECTION_TOL && !tmp[i].IsClosed()) {
1441  // make IsClosed() true
1442  tmp[i].Append(SSICurve(new ON_LineCurve(tmp[i].PointAtEnd(), tmp[i].PointAtStart())));
1443  }
1444  }
1445  }
1446 
1447  // Append the remaining curves to out.
1448  ON_ClassArray<LinkedCurve> out;
1449  for (int i = 0; i < tmp.Count(); i++) {
1450  if (tmp[i].m_ssi_curves.Count() != 0) {
1451  out.Append(tmp[i]);
1452  }
1453  }
1454 
1455  if (DEBUG_BREP_BOOLEAN) {
1456  bu_log("link_curves(): %d curves remaining.\n", out.Count());
1457  }
1458 
1459  return out;
1460 }
1461 
1462 
1463 class CurvePoint {
1464 public:
1467  double curve_t;
1468  ON_2dPoint pt;
1469 
1470  enum Location {
1474  } location;
1475 
1476  static CurvePoint::Location
1477  PointLoopLocation(ON_2dPoint pt, const ON_SimpleArray<ON_Curve *> &loop);
1478 
1480  int loop,
1481  int li,
1482  double pt_t,
1483  ON_Curve *curve,
1484  const ON_SimpleArray<ON_Curve *> &other_loop)
1485  : source_loop(loop), loop_index(li), curve_t(pt_t)
1486  {
1487  pt = curve->PointAt(curve_t);
1488  location = PointLoopLocation(pt, other_loop);
1489  }
1490 
1492  int loop,
1493  int li,
1494  double t,
1495  ON_2dPoint p,
1497  : source_loop(loop), loop_index(li), curve_t(t), pt(p), location(l)
1498  {
1499  }
1500 
1501  bool
1503  {
1504  // for points not on the same loop, compare the actual points
1505  if (source_loop != other.source_loop) {
1506  if (ON_NearZero(pt.DistanceTo(other.pt), INTERSECTION_TOL)) {
1507  return false;
1508  }
1509  return pt < other.pt;
1510  }
1511 
1512  // for points on the same loop, compare loop position
1513  if (loop_index == other.loop_index) {
1514  if (ON_NearZero(curve_t - other.curve_t, INTERSECTION_TOL)) {
1515  return false;
1516  }
1517  return curve_t < other.curve_t;
1518  }
1519  return loop_index < other.loop_index;
1520  }
1521 
1522  bool
1524  {
1525  return ON_NearZero(pt.DistanceTo(other.pt), INTERSECTION_TOL);
1526  }
1527 
1528  bool
1530  {
1531  return !ON_NearZero(pt.DistanceTo(other.pt), INTERSECTION_TOL);
1532  }
1533 };
1534 
1536 public:
1537  bool
1538  operator()(const CurvePoint &a, const CurvePoint &b) const
1539  {
1540  if (ON_NearZero(a.pt.DistanceTo(b.pt), INTERSECTION_TOL)) {
1541  return false;
1542  }
1543  return a.pt < b.pt;
1544  }
1545 };
1546 
1549  ON_2dPoint pt,
1550  const ON_SimpleArray<ON_Curve *> &loop)
1551 {
1552  if (is_point_on_loop(pt, loop)) {
1553  return CurvePoint::BOUNDARY;
1554  }
1555  if (point_loop_location(pt, loop) == OUTSIDE_OR_ON_LOOP) {
1556  return CurvePoint::OUTSIDE;
1557  }
1558  return CurvePoint::INSIDE;
1559 }
1560 
1562 public:
1563  ON_SimpleArray<ON_Curve *> orig_loop;
1565  enum Location {
1569  } location;
1570 
1572  ON_SimpleArray<ON_Curve *> &loop,
1573  CurvePoint f,
1574  CurvePoint t,
1576  : orig_loop(loop), from(f), to(t), location(l)
1577  {
1578  }
1579 
1580  void
1581  Reverse(void)
1582  {
1583  std::swap(from, to);
1584  }
1585 
1586  ON_Curve *
1587  Curve(void) const
1588  {
1589  ON_Curve *from_curve = orig_loop[from.loop_index];
1590  ON_Curve *to_curve = orig_loop[to.loop_index];
1591  ON_Interval from_dom = from_curve->Domain();
1592  ON_Interval to_dom = to_curve->Domain();
1593 
1594  // if endpoints are on the same curve, just get the part between them
1595  if (from.loop_index == to.loop_index) {
1596  ON_Curve *seg_curve =
1597  sub_curve(from_curve, from.curve_t, to.curve_t);
1598  return seg_curve;
1599  }
1600  // if endpoints are on different curves, we may need a subcurve of
1601  // just the 'from' curve, just the 'to' curve, or both
1602  if (ON_NearZero(from.curve_t - from_dom.m_t[1], INTERSECTION_TOL)) {
1603  // starting at end of 'from' same as starting at start of 'to'
1604  ON_Curve *seg_curve = sub_curve(to_curve, to_dom.m_t[0],
1605  to.curve_t);
1606  return seg_curve;
1607  }
1608  if (ON_NearZero(to.curve_t - to_dom.m_t[0], INTERSECTION_TOL)) {
1609  // ending at start of 'to' same as ending at end of 'from'
1610  ON_Curve *seg_curve = sub_curve(from_curve, from.curve_t,
1611  from_dom.m_t[1]);
1612  return seg_curve;
1613  }
1614  ON_PolyCurve *pcurve = new ON_PolyCurve();
1615  append_to_polycurve(sub_curve(from_curve, from.curve_t,
1616  from_dom.m_t[1]), *pcurve);
1617  append_to_polycurve(sub_curve(to_curve, to_dom.m_t[0], to.curve_t),
1618  *pcurve);
1619  return pcurve;
1620  }
1621 
1622  bool
1624  {
1625  ON_Curve *seg_curve = NULL;
1626  try {
1627  seg_curve = Curve();
1628  } catch (InvalidInterval &) {
1629  return true;
1630  }
1631 
1632  double length = 0.0;
1633  if (seg_curve->IsLinear(INTERSECTION_TOL)) {
1634  length = seg_curve->PointAtStart().DistanceTo(
1635  seg_curve->PointAtEnd());
1636  } else {
1637  double min[3] = {0.0, 0.0, 0.0};
1638  double max[3] = {0.0, 0.0, 0.0};
1639 
1640  seg_curve->GetBBox(min, max, true);
1641  length = DIST_PT_PT(min, max);
1642  }
1643  delete seg_curve;
1644  return length < INTERSECTION_TOL;
1645  }
1646 
1647  bool
1649  {
1650  return from < other.from;
1651  }
1652 };
1653 
1655 public:
1656  std::vector<ON_SimpleArray<ON_Curve *> > outerloops;
1657  std::vector<ON_SimpleArray<ON_Curve *> > innerloops;
1658 
1660  for (size_t i = 0; i < outerloops.size(); ++i) {
1661  for (int j = 0; j < outerloops[i].Count(); ++j) {
1662  delete outerloops[i][j];
1663  }
1664  }
1665  }
1667  for (size_t i = 0; i < innerloops.size(); ++i) {
1668  for (int j = 0; j < innerloops[i].Count(); ++j) {
1669  delete innerloops[i][j];
1670  }
1671  }
1672  }
1673 };
1674 
1675 #define LOOP_DIRECTION_CCW 1
1676 #define LOOP_DIRECTION_CW -1
1677 #define LOOP_DIRECTION_NONE 0
1678 
1679 HIDDEN bool
1680 close_small_gap(ON_SimpleArray<ON_Curve *> &loop, int curr, int next)
1681 {
1682  ON_3dPoint end_curr = loop[curr]->PointAtEnd();
1683  ON_3dPoint start_next = loop[next]->PointAtStart();
1684 
1685  double gap = end_curr.DistanceTo(start_next);
1686  if (gap <= INTERSECTION_TOL && gap >= ON_ZERO_TOLERANCE) {
1687  ON_Curve *closing_seg = new ON_LineCurve(end_curr, start_next);
1688  loop.Insert(next, closing_seg);
1689  return true;
1690  }
1691  return false;
1692 }
1693 
1694 HIDDEN void
1695 close_small_gaps(ON_SimpleArray<ON_Curve *> &loop)
1696 {
1697  if (loop.Count() == 0) {
1698  return;
1699  }
1700  for (int i = 0; i < loop.Count() - 1; ++i) {
1701  if (close_small_gap(loop, i, i + 1)) {
1702  ++i;
1703  }
1704  }
1705  close_small_gap(loop, loop.Count() - 1, 0);
1706 }
1707 
1708 ON_Curve *
1709 get_loop_curve(const ON_SimpleArray<ON_Curve *> &loop)
1710 {
1711  ON_PolyCurve *pcurve = new ON_PolyCurve();
1712  for (int i = 0; i < loop.Count(); ++i) {
1713  append_to_polycurve(loop[i]->Duplicate(), *pcurve);
1714  }
1715  return pcurve;
1716 }
1717 
1718 std::list<ON_SimpleArray<ON_Curve *> >::iterator
1719 find_innerloop(std::list<ON_SimpleArray<ON_Curve *> > &loops)
1720 {
1721  std::list<ON_SimpleArray<ON_Curve *> >::iterator k;
1722  for (k = loops.begin(); k != loops.end(); ++k) {
1723  ON_Curve *loop_curve = get_loop_curve(*k);
1724 
1725  if (ON_ClosedCurveOrientation(*loop_curve, NULL) == LOOP_DIRECTION_CW) {
1726  delete loop_curve;
1727  return k;
1728  }
1729  delete loop_curve;
1730  }
1731  return loops.end();
1732 }
1733 
1734 bool
1735 set_loop_direction(ON_SimpleArray<ON_Curve *> &loop, int dir)
1736 {
1737  ON_Curve *curve = get_loop_curve(loop);
1738  int curr_dir = ON_ClosedCurveOrientation(*curve, NULL);
1739  delete curve;
1740 
1741  if (curr_dir == LOOP_DIRECTION_NONE) {
1742  // can't set the correct direction
1743  return false;
1744  }
1745  if (curr_dir != dir) {
1746  // need reverse
1747  for (int i = 0; i < loop.Count(); ++i) {
1748  if (!loop[i]->Reverse()) {
1749  return false;
1750  }
1751  }
1752  loop.Reverse();
1753  }
1754  // curve already has the correct direction
1755  return true;
1756 }
1757 
1758 void
1759 add_point_to_set(std::multiset<CurvePoint> &set, CurvePoint pt)
1760 {
1761  if (set.count(pt) < 2) {
1762  set.insert(pt);
1763  }
1764 }
1765 
1766 std::multiset<CurveSegment>
1768  std::multiset<CurvePoint> &curve1_points,
1769  ON_SimpleArray<ON_Curve *> &loop1,
1770  ON_SimpleArray<ON_Curve *> &loop2)
1771 {
1772  std::multiset<CurveSegment> out;
1773 
1774  std::multiset<CurvePoint>::iterator first = curve1_points.begin();
1775  std::multiset<CurvePoint>::iterator curr = first;
1776  std::multiset<CurvePoint>::iterator next = ++curve1_points.begin();
1777 
1778  for (; next != curve1_points.end(); ++curr, ++next) {
1779  CurvePoint from = *curr;
1780  CurvePoint to = *next;
1781  CurveSegment new_seg(loop1, from, to, CurveSegment::BOUNDARY);
1782 
1783  if (new_seg.IsDegenerate()) {
1784  continue;
1785  }
1786 
1787  if (from.location == CurvePoint::BOUNDARY &&
1789  {
1790  ON_Curve *seg_curve = loop1[from.loop_index];
1791 
1792  double end_t = to.curve_t;
1793  if (from.loop_index != to.loop_index) {
1794  end_t = seg_curve->Domain().m_t[1];
1795  }
1796  ON_2dPoint seg_midpt = seg_curve->PointAt(
1797  ON_Interval(from.curve_t, end_t).Mid());
1798 
1799  CurvePoint::Location midpt_location =
1800  CurvePoint::PointLoopLocation(seg_midpt, loop2);
1801 
1802  if (midpt_location == CurvePoint::INSIDE) {
1803  new_seg.location = CurveSegment::INSIDE;
1804  } else if (midpt_location == CurvePoint::OUTSIDE) {
1805  new_seg.location = CurveSegment::OUTSIDE;
1806  }
1807  } else if (from.location == CurvePoint::INSIDE ||
1809  {
1810  new_seg.location = CurveSegment::INSIDE;
1811  } else if (from.location == CurvePoint::OUTSIDE ||
1813  {
1814  new_seg.location = CurveSegment::OUTSIDE;
1815  }
1816  out.insert(new_seg);
1817  }
1818  return out;
1819 }
1820 
1821 void
1823  std::multiset<CurveSegment> &out,
1824  const CurveSegment &seg)
1825 {
1826  std::multiset<CurveSegment>::iterator i;
1827  for (i = out.begin(); i != out.end(); ++i) {
1828  if ((i->from == seg.to) && (i->to == seg.from)) {
1829  // if this segment is a reversed version of an existing
1830  // segment, it cancels the existing segment out
1831  ON_Curve *prev_curve = i->Curve();
1832  ON_Curve *seg_curve = seg.Curve();
1833  ON_SimpleArray<ON_X_EVENT> events;
1834  ON_Intersect(prev_curve, seg_curve, events, INTERSECTION_TOL);
1835  if (events.Count() == 1 && events[0].m_type == ON_X_EVENT::ccx_overlap) {
1836  out.erase(i);
1837  return;
1838  }
1839  }
1840  }
1841  out.insert(seg);
1842 }
1843 
1844 void
1846  std::multiset<CurveSegment> &out,
1847  std::multiset<CurveSegment> &in,
1848  CurveSegment::Location location,
1849  bool reversed_segs_cancel)
1850 {
1851  std::multiset<CurveSegment>::iterator i;
1852  if (reversed_segs_cancel) {
1853  for (i = in.begin(); i != in.end(); ++i) {
1854  if (i->location == location) {
1855  set_append_segment(out, *i);
1856  }
1857  }
1858  } else {
1859  for (i = in.begin(); i != in.end(); ++i) {
1860  if (i->location == location) {
1861  out.insert(*i);
1862  }
1863  }
1864  }
1865 }
1866 
1867 std::multiset<CurveSegment>
1869  std::multiset<CurveSegment> &set,
1870  const CurveSegment &seg)
1871 {
1872  std::multiset<CurveSegment> out;
1873 
1874  std::multiset<CurveSegment>::iterator i;
1875  for (i = set.begin(); i != set.end(); ++i) {
1876  if (((i->from == seg.from) && (i->to == seg.to)) ||
1877  ((i->from == seg.to) && (i->to == seg.from)))
1878  {
1879  out.insert(*i);
1880  }
1881  }
1882  return out;
1883 }
1884 
1885 HIDDEN std::multiset<CurveSegment>
1887  std::multiset<CurveSegment> &curve1_segments,
1888  std::multiset<CurveSegment> &curve2_segments,
1889  op_type op)
1890 {
1891  std::multiset<CurveSegment> out;
1892 
1893  std::multiset<CurveSegment> c1_boundary_segs;
1894  set_append_segments_at_location(c1_boundary_segs, curve1_segments,
1895  CurveSegment::BOUNDARY, false);
1896 
1897  std::multiset<CurveSegment> c2_boundary_segs;
1898  set_append_segments_at_location(c2_boundary_segs, curve2_segments,
1899  CurveSegment::BOUNDARY, false);
1900 
1901  if (op == BOOLEAN_INTERSECT) {
1902  set_append_segments_at_location(out, curve1_segments,
1903  CurveSegment::INSIDE, true);
1904 
1905  set_append_segments_at_location(out, curve2_segments,
1906  CurveSegment::INSIDE, true);
1907 
1908  std::multiset<CurveSegment>::iterator i;
1909  for (i = c1_boundary_segs.begin(); i != c1_boundary_segs.end(); ++i) {
1910  std::multiset<CurveSegment> curve1_matches =
1911  find_similar_segments(c1_boundary_segs, *i);
1912 
1913  std::multiset<CurveSegment> curve2_matches =
1914  find_similar_segments(c2_boundary_segs, *i);
1915 
1916  if (curve1_matches.size() > 1 || curve2_matches.size() > 1) {
1917  continue;
1918  }
1919  if (curve1_matches.begin()->from == curve2_matches.begin()->from) {
1920  out.insert(*i);
1921  }
1922  }
1923  } else if (op == BOOLEAN_DIFF) {
1924  set_append_segments_at_location(out, curve1_segments,
1925  CurveSegment::OUTSIDE, true);
1926 
1927  set_append_segments_at_location(out, curve2_segments,
1928  CurveSegment::INSIDE, true);
1929 
1930  std::multiset<CurveSegment>::iterator i;
1931  for (i = c1_boundary_segs.begin(); i != c1_boundary_segs.end(); ++i) {
1932  std::multiset<CurveSegment> curve1_matches =
1933  find_similar_segments(c1_boundary_segs, *i);
1934 
1935  std::multiset<CurveSegment> curve2_matches =
1936  find_similar_segments(c2_boundary_segs, *i);
1937 
1938  if (curve1_matches.size() > 1) {
1939  continue;
1940  }
1941  if (curve1_matches.begin()->from == curve2_matches.begin()->from ||
1942  curve2_matches.size() > 1)
1943  {
1944  out.insert(*i);
1945  }
1946  }
1947  } else if (op == BOOLEAN_UNION) {
1948  set_append_segments_at_location(out, curve1_segments,
1949  CurveSegment::OUTSIDE, true);
1950 
1951  set_append_segments_at_location(out, curve2_segments,
1952  CurveSegment::OUTSIDE, true);
1953 
1954  std::multiset<CurveSegment>::iterator i;
1955  for (i = c1_boundary_segs.begin(); i != c1_boundary_segs.end(); ++i) {
1956  std::multiset<CurveSegment> curve1_matches =
1957  find_similar_segments(c1_boundary_segs, *i);
1958 
1959  std::multiset<CurveSegment> curve2_matches =
1960  find_similar_segments(c2_boundary_segs, *i);
1961 
1962  if (curve1_matches.size() > 1 && curve2_matches.size() > 1) {
1963  continue;
1964  }
1965 
1966  std::multiset<CurveSegment>::iterator a, b;
1967  for (a = curve1_matches.begin(); a != curve1_matches.end(); ++a) {
1968 
1969  b = curve2_matches.begin();
1970  for (; b != curve2_matches.end(); ++b) {
1971  if (a->from == b->from) {
1972  out.insert(*i);
1973  }
1974  }
1975  }
1976  }
1977  }
1978 
1979  return out;
1980 }
1981 
1982 std::list<ON_SimpleArray<ON_Curve *> >
1984  std::multiset<CurveSegment> &segments)
1985 {
1986  std::list<ON_SimpleArray<ON_Curve *> > out;
1987 
1988  while (!segments.empty()) {
1989  std::vector<std::multiset<CurveSegment>::iterator> loop_segs;
1990  std::multiset<CurvePoint, CurvePointAbsoluteCompare> visited_points;
1991 
1992  std::multiset<CurveSegment>::iterator curr_seg, prev_seg;
1993  curr_seg = segments.begin();
1994 
1995  loop_segs.push_back(curr_seg);
1996  visited_points.insert(curr_seg->from);
1997  visited_points.insert(curr_seg->to);
1998 
1999  bool closed_curve = (curr_seg->from == curr_seg->to);
2000  while (!closed_curve) {
2001  // look for a segment that connects to the previous
2002  prev_seg = curr_seg;
2003  for (curr_seg = segments.begin(); curr_seg != segments.end(); ++curr_seg) {
2004  if (curr_seg->from == prev_seg->to) {
2005  break;
2006  }
2007  }
2008 
2009  if (curr_seg == segments.end()) {
2010  // no segment connects to the prev one
2011  break;
2012  } else {
2013  // Extend our loop with the joining segment.
2014  // If we've visited its endpoint before, then the loop
2015  // is now closed.
2016  loop_segs.push_back(curr_seg);
2017  visited_points.insert(curr_seg->to);
2018  closed_curve = (visited_points.count(curr_seg->to) > 1);
2019  }
2020  }
2021 
2022  if (closed_curve) {
2023  // find the segment the closing segment connected to (it
2024  // may not be the first segment)
2025  size_t i;
2026  for (i = 0; i < loop_segs.size(); ++i) {
2027  if (loop_segs[i]->from == loop_segs.back()->to) {
2028  break;
2029  }
2030  }
2031  // Form a curve from the closed chain of segments.
2032  // Remove the used segments from the available set.
2033  ON_SimpleArray<ON_Curve *> loop;
2034  for (; i < loop_segs.size(); ++i) {
2035  try {
2036  loop.Append(loop_segs[i]->Curve());
2037  } catch (InvalidInterval &e) {
2038  bu_log("%s", e.what());
2039  }
2040  segments.erase(loop_segs[i]);
2041  }
2042  out.push_back(loop);
2043  } else {
2044  // couldn't join to the last segment, discard it
2045  segments.erase(loop_segs.back());
2046  bu_log("construct_loops_from_segments: found unconnected segment\n");
2047  }
2048  loop_segs.clear();
2049  visited_points.clear();
2050  }
2051  return out;
2052 }
2053 
2054 std::multiset<CurvePoint>
2056  int source_loop,
2057  ON_SimpleArray<ON_Curve *> loop1,
2058  ON_SimpleArray<ON_Curve *> loop2)
2059 {
2060  std::multiset<CurvePoint> out;
2061 
2062  ON_Curve *loop1_seg = loop1[0];
2063  out.insert(CurvePoint(source_loop, 0, loop1_seg->Domain().m_t[0], loop1_seg,
2064  loop2));
2065 
2066  for (int i = 0; i < loop1.Count(); ++i) {
2067  loop1_seg = loop1[i];
2068  out.insert(CurvePoint(source_loop, i, loop1_seg->Domain().m_t[1],
2069  loop1_seg, loop2));
2070  }
2071 
2072  return out;
2073 }
2074 
2075 // separate outerloops and innerloops
2077 make_result_from_loops(const std::list<ON_SimpleArray<ON_Curve *> > &loops)
2078 {
2080 
2081  std::list<ON_SimpleArray<ON_Curve *> >::const_iterator li;
2082  for (li = loops.begin(); li != loops.end(); ++li) {
2083  ON_Curve *loop_curve = get_loop_curve(*li);
2084 
2085  int dir = ON_ClosedCurveOrientation(*loop_curve, NULL);
2086 
2087  if (dir == LOOP_DIRECTION_CCW) {
2088  out.outerloops.push_back(*li);
2089  } else if (dir == LOOP_DIRECTION_CW) {
2090  out.innerloops.push_back(*li);
2091  }
2092  delete loop_curve;
2093  }
2094 
2095  return out;
2096 }
2097 
2098 
2099 // Get the result of a boolean combination of two loops. Based on the
2100 // algorithm from this paper:
2101 //
2102 // Margalit, Avraham and Gary D. Knott. 1989. "An Algorithm for
2103 // Computing the Union, Intersection or Difference of two Polygons."
2104 // Computers & Graphics 13:167-183.
2105 //
2106 // gvu.gatech.edu/people/official/jarek/graphics/papers/04PolygonBooleansMargalit.pdf
2109  const ON_SimpleArray<ON_Curve *> &l1,
2110  const ON_SimpleArray<ON_Curve *> &l2,
2111  op_type op)
2112 {
2114 
2115  if (op != BOOLEAN_INTERSECT &&
2116  op != BOOLEAN_DIFF &&
2117  op != BOOLEAN_UNION)
2118  {
2119  bu_log("loop_boolean: unsupported operation\n");
2120  return out;
2121  }
2122 
2123  // copy input loops
2124  ON_SimpleArray<ON_Curve *> loop1, loop2;
2125  for (int i = 0; i < l1.Count(); ++i) {
2126  loop1.Append(l1[i]->Duplicate());
2127  }
2128  for (int i = 0; i < l2.Count(); ++i) {
2129  loop2.Append(l2[i]->Duplicate());
2130  }
2131 
2132  // set curve directions based on operation
2133  int loop1_dir, loop2_dir;
2134 
2135  loop1_dir = loop2_dir = LOOP_DIRECTION_CCW;
2136  if (op == BOOLEAN_DIFF) {
2137  loop2_dir = LOOP_DIRECTION_CW;
2138  }
2139 
2140  if (!set_loop_direction(loop1, loop1_dir) ||
2141  !set_loop_direction(loop2, loop2_dir))
2142  {
2143  bu_log("loop_boolean: couldn't standardize curve directions\n");
2144 
2145  for (int i = 0; i < l1.Count(); ++i) {
2146  delete loop1[i];
2147  }
2148  for (int i = 0; i < l2.Count(); ++i) {
2149  delete loop2[i];
2150  }
2151  return out;
2152  }
2153 
2154  // get curve endpoints and intersection points for each loop
2155  std::multiset<CurvePoint> loop1_points, loop2_points;
2156 
2157  loop1_points = get_loop_points(1, loop1, loop2);
2158  loop2_points = get_loop_points(2, loop2, loop1);
2159 
2160  for (int i = 0; i < loop1.Count(); ++i) {
2161  for (int j = 0; j < loop2.Count(); ++j) {
2162  ON_SimpleArray<ON_X_EVENT> x_events;
2163  ON_Intersect(loop1[i], loop2[j], x_events, INTERSECTION_TOL);
2164 
2165  for (int k = 0; k < x_events.Count(); ++k) {
2166  add_point_to_set(loop1_points, CurvePoint(1, i,
2167  x_events[k].m_a[0], x_events[k].m_A[0],
2169 
2170  add_point_to_set(loop2_points, CurvePoint(2, j,
2171  x_events[k].m_b[0], x_events[k].m_B[0],
2173 
2174  if (x_events[k].m_type == ON_X_EVENT::ccx_overlap) {
2175  add_point_to_set(loop1_points, CurvePoint(1, i,
2176  x_events[k].m_a[1], x_events[k].m_A[1],
2178 
2179  add_point_to_set(loop2_points, CurvePoint(2, j,
2180  x_events[k].m_b[1], x_events[k].m_B[1],
2182  }
2183  }
2184  }
2185  }
2186 
2187  // classify segments and determine which belong in the result
2188  std::multiset<CurveSegment> loop1_segments, loop2_segments;
2189  loop1_segments = make_segments(loop1_points, loop1, loop2);
2190  loop2_segments = make_segments(loop2_points, loop2, loop1);
2191 
2192  std::multiset<CurveSegment> out_segments =
2193  get_op_segments(loop1_segments, loop2_segments, op);
2194 
2195  // build result
2196  std::list<ON_SimpleArray<ON_Curve *> > new_loops;
2197 
2198  new_loops = construct_loops_from_segments(out_segments);
2199  for (int i = 0; i < l1.Count(); ++i) {
2200  delete loop1[i];
2201  }
2202  for (int i = 0; i < l2.Count(); ++i) {
2203  delete loop2[i];
2204  }
2205 
2206  std::list<ON_SimpleArray<ON_Curve *> >::iterator li;
2207  for (li = new_loops.begin(); li != new_loops.end(); ++li) {
2208  close_small_gaps(*li);
2209  }
2210 
2211  out = make_result_from_loops(new_loops);
2212 
2213  return out;
2214 }
2215 
2216 std::list<ON_SimpleArray<ON_Curve *> >
2218  const ON_SimpleArray<ON_Curve *> &outerloop_curve,
2219  const std::vector<ON_SimpleArray<ON_Curve *> > &innerloop_curves)
2220 {
2221  std::list<ON_SimpleArray<ON_Curve *> > out;
2222 
2223  for (size_t i = 0; i < innerloop_curves.size(); ++i) {
2224  std::list<ON_SimpleArray<ON_Curve *> > new_innerloops;
2225  LoopBooleanResult new_loops;
2226  new_loops = loop_boolean(outerloop_curve, innerloop_curves[i],
2227  BOOLEAN_INTERSECT);
2228 
2229  // grab outerloops
2230  for (size_t j = 0; j < new_loops.outerloops.size(); ++j) {
2232  out.push_back(new_loops.outerloops[j]);
2233  }
2234  new_loops.ClearInnerloops();
2235  }
2236  return out;
2237 }
2238 
2239 TrimmedFace *
2241  const TrimmedFace *orig_face,
2242  const ON_SimpleArray<ON_Curve *> &outerloop,
2243  const std::vector<ON_SimpleArray<ON_Curve *> > &innerloops)
2244 {
2245  TrimmedFace *face = new TrimmedFace();
2246 
2247  face->m_face = orig_face->m_face;
2248  face->m_outerloop.Append(outerloop.Count(), outerloop.Array());
2249 
2250  // TODO: the innerloops found here can't be inside any other
2251  // outerloop, and should be removed from the innerloop set in the
2252  // interest of efficiency
2253  std::list<ON_SimpleArray<ON_Curve *> > new_innerloops;
2254  new_innerloops = innerloops_inside_outerloop(outerloop, innerloops);
2255 
2256  std::list<ON_SimpleArray<ON_Curve *> >::iterator i;
2257  for (i = new_innerloops.begin(); i != new_innerloops.end(); ++i) {
2258  face->m_innerloop.push_back(*i);
2259  }
2260  return face;
2261 }
2262 
2265  const TrimmedFace *orig_face,
2266  const LoopBooleanResult &new_loops)
2267 {
2268  // Intersections always produce a single outerloop.
2269  //
2270  // Subtractions may produce multiple outerloops, or a single
2271  // outerloop that optionally includes a single innerloop.
2272  //
2273  // So, the possible results are:
2274  // 1) Single outerloop.
2275  // 2) Multiple outerloops.
2276  // 3) Single outerloop with single innerloop.
2277 
2278  // First we'll combine the old and new innerloops.
2279  std::vector<ON_SimpleArray<ON_Curve *> > merged_innerloops;
2280  if (new_loops.innerloops.size() == 1) {
2281  // If the result has an innerloop, it may overlap any of the
2282  // original innerloops. We'll union all overlapping loops with
2283  // the new innerloop.
2284  ON_SimpleArray<ON_Curve *> candidate_innerloop(new_loops.innerloops[0]);
2285 
2286  for (size_t i = 0; i < orig_face->m_innerloop.size(); ++i) {
2287  LoopBooleanResult merged = loop_boolean(candidate_innerloop,
2288  orig_face->m_innerloop[i], BOOLEAN_UNION);
2289 
2290  if (merged.outerloops.size() == 1) {
2291  candidate_innerloop = merged.outerloops[0];
2292  } else {
2293  merged_innerloops.push_back(orig_face->m_innerloop[i]);
2294  merged.ClearOuterloops();
2295  }
2296  }
2297  merged_innerloops.push_back(candidate_innerloop);
2298  } else if (orig_face->m_innerloop.size() > 0) {
2299  for (size_t i = 0; i < orig_face->m_innerloop.size(); ++i) {
2300  merged_innerloops.push_back(orig_face->m_innerloop[i]);
2301  }
2302  }
2303 
2304  // Next we'll attempt to subtract all merged innerloops from each
2305  // new outerloop to get the final set of loops. For each
2306  // subtraction, there are four possibilities:
2307  // 1) The innerloop is outside the outerloop, and the result is
2308  // the original outerloop.
2309  // 2) The innerloop completely encloses the outerloop, and the
2310  // result is empty.
2311  // 3) The innerloop is completely contained by the outerloop, and
2312  // the result is the input outerloop and innerloop.
2313  // 4) The innerloop overlaps the outerloop, and the result is one
2314  // or more outerloops.
2316  for (size_t i = 0; i < new_loops.outerloops.size(); ++i) {
2317 
2318  std::list<ON_SimpleArray<ON_Curve *> >::iterator part, next_part;
2319  std::list<ON_SimpleArray<ON_Curve *> > outerloop_parts;
2320 
2321  // start with the original outerloop
2322  outerloop_parts.push_back(new_loops.outerloops[i]);
2323 
2324  // attempt to subtract all innerloops from it, and from
2325  // whatever subparts of it are created along the way
2326  for (size_t j = 0; j < merged_innerloops.size(); ++j) {
2327 
2328  part = outerloop_parts.begin();
2329  for (; part != outerloop_parts.end(); part = next_part) {
2330  LoopBooleanResult diffed = loop_boolean(*part,
2331  merged_innerloops[j], BOOLEAN_DIFF);
2332 
2333  next_part = part;
2334  ++next_part;
2335 
2336  if (diffed.innerloops.size() == 1) {
2337  // The outerloop part contains the innerloop, so
2338  // the innerloop belongs in the final set.
2339  //
2340  // Note that any innerloop added here will remains
2341  // completely inside an outerloop part even if the
2342  // part list changes. In order for a subsequent
2343  // subtraction to put any part of it outside an
2344  // outerloop, that later innerloop would have to
2345  // overlap this one, in which case, the innerloops
2346  // would have been unioned together in the
2347  // previous merging step.
2348  out.innerloops.push_back(diffed.innerloops[0]);
2349  } else {
2350  // outerloop part has been erased, modified, or
2351  // split, so we need to remove it
2352  for (int k = 0; k < part->Count(); ++k) {
2353  delete (*part)[k];
2354  }
2355  outerloop_parts.erase(part);
2356 
2357  // add any new parts for subsequent subtractions
2358  for (size_t k = 0; k < diffed.outerloops.size(); ++k) {
2359  outerloop_parts.push_front(diffed.outerloops[k]);
2360  }
2361  }
2362  }
2363  }
2364 
2365  // whatever parts of the outerloop that remain after
2366  // subtracting all innerloops belong in the final set
2367  part = outerloop_parts.begin();
2368  for (; part != outerloop_parts.end(); ++part) {
2369  out.outerloops.push_back(*part);
2370  }
2371  }
2372  return out;
2373  // Only thing left to do is make a face from each outerloop. If
2374  // one of the innerloops is inside the outerloop, make it part of
2375  // the face and remove it for consideration for other faces.
2376 }
2377 
2378 
2379 HIDDEN void
2381  ON_SimpleArray<TrimmedFace *> &out,
2382  const TrimmedFace *orig_face,
2383  const LoopBooleanResult &new_loops)
2384 {
2385  LoopBooleanResult combined_loops = combine_loops(orig_face, new_loops);
2386 
2387  // make a face from each outerloop, using appropriate innerloops
2388  for (size_t i = 0; i < combined_loops.outerloops.size(); ++i) {
2389  out.Append(make_face_from_loops(orig_face,
2390  combined_loops.outerloops[i],
2391  combined_loops.innerloops));
2392  }
2393 }
2394 
2395 /* Turn an open curve into a closed curve by using segments from the
2396  * face outerloop to connect its endpoints.
2397  *
2398  * Returns false on failure, true otherwise.
2399  */
2400 std::vector<ON_SimpleArray<ON_Curve *> >
2402  const TrimmedFace *orig_face,
2403  LinkedCurve &linked_curve)
2404 {
2405  std::vector<ON_SimpleArray<ON_Curve *> > out;
2406 
2407  if (linked_curve.IsClosed()) {
2408  ON_SimpleArray<ON_Curve *> loop;
2409  for (int i = 0; i < orig_face->m_outerloop.Count(); ++i) {
2410  loop.Append(orig_face->m_outerloop[i]->Duplicate());
2411  }
2412  out.push_back(loop);
2413  return out;
2414  }
2415 
2416  /* We followed the algorithms described in:
2417  * S. Krishnan, A. Narkhede, and D. Manocha. BOOLE: A System to Compute
2418  * Boolean Combinations of Sculptured Solids. Technical Report TR95-008,
2419  * Department of Computer Science, University of North Carolina, 1995.
2420  * Appendix B: Partitioning a Simple Polygon using Non-Intersecting
2421  * Chains.
2422  */
2423 
2424  // Get the intersection points between the SSI curves and the outerloop.
2425  ON_SimpleArray<IntersectPoint> clx_points;
2426  bool intersects_outerloop = false;
2427  for (int i = 0; i < orig_face->m_outerloop.Count(); i++) {
2428  ON_SimpleArray<ON_X_EVENT> x_events;
2429  ON_Intersect(orig_face->m_outerloop[i], linked_curve.Curve(),
2430  x_events, INTERSECTION_TOL);
2431 
2432  for (int j = 0; j < x_events.Count(); j++) {
2433  IntersectPoint tmp_pt;
2434  tmp_pt.m_pt = x_events[j].m_A[0];
2435  tmp_pt.m_seg_t = x_events[j].m_a[0];
2436  tmp_pt.m_curve_t = x_events[j].m_b[0];
2437  tmp_pt.m_loop_seg = i;
2438  clx_points.Append(tmp_pt);
2439 
2440  if (x_events[j].m_type == ON_X_EVENT::ccx_overlap) {
2441  tmp_pt.m_pt = x_events[j].m_A[1];
2442  tmp_pt.m_seg_t = x_events[j].m_a[1];
2443  tmp_pt.m_curve_t = x_events[j].m_b[1];
2444  clx_points.Append(tmp_pt);
2445  }
2446  if (x_events.Count()) {
2447  intersects_outerloop = true;
2448  }
2449  }
2450  }
2451 
2452  // can't close curves that don't partition the face
2453  if (!intersects_outerloop || clx_points.Count() < 2) {
2454  ON_SimpleArray<ON_Curve *> loop;
2455  for (int i = 0; i < orig_face->m_outerloop.Count(); ++i) {
2456  loop.Append(orig_face->m_outerloop[i]->Duplicate());
2457  }
2458  out.push_back(loop);
2459  return out;
2460  }
2461 
2462  // rank these intersection points
2463  clx_points.QuickSort(curve_t_compare);
2464  for (int i = 0; i < clx_points.Count(); i++) {
2465  clx_points[i].m_curve_pos = i;
2466  }
2467 
2468  // classify intersection points
2469  ON_SimpleArray<IntersectPoint> new_pts;
2470  double curve_min_t = linked_curve.Domain().Min();
2471  double curve_max_t = linked_curve.Domain().Max();
2472 
2473  for (int i = 0; i < clx_points.Count(); i++) {
2474  bool is_first_ipt = (i == 0);
2475  bool is_last_ipt = (i == (clx_points.Count() - 1));
2476 
2477  IntersectPoint *ipt = &clx_points[i];
2478  double curve_t = ipt->m_curve_t;
2479 
2480  ON_3dPoint prev = linked_curve.PointAtStart();
2481  if (!is_first_ipt) {
2482  double prev_curve_t = clx_points[i - 1].m_curve_t;
2483  prev = linked_curve.PointAt((curve_t + prev_curve_t) * .5);
2484  }
2485  ON_3dPoint next = linked_curve.PointAtEnd();
2486  if (!is_last_ipt) {
2487  double next_curve_t = clx_points[i + 1].m_curve_t;
2488  next = linked_curve.PointAt((curve_t + next_curve_t) * .5);
2489  }
2490  // If the point is on the boundary, we treat it with the same
2491  // way as it's outside.
2492  // For example, the prev side is inside, and the next's on
2493  // boundary, that point should be IntersectPoint::OUT, the
2494  // same as the next's outside the loop.
2495  // Other cases are similar.
2496  bool prev_in, next_in;
2497  try {
2498  prev_in = is_point_inside_loop(prev, orig_face->m_outerloop);
2499  next_in = is_point_inside_loop(next, orig_face->m_outerloop);
2500  } catch (InvalidGeometry &e) {
2501  bu_log("%s", e.what());
2502  // not a loop
2504  continue;
2505  }
2506  if (is_first_ipt && ON_NearZero(curve_t - curve_min_t)) {
2507  ipt->m_dir = next_in ? IntersectPoint::IN : IntersectPoint::OUT;
2508  continue;
2509  }
2510  if (is_last_ipt && ON_NearZero(curve_t - curve_max_t)) {
2511  ipt->m_dir = prev_in ? IntersectPoint::OUT : IntersectPoint::IN;
2512  continue;
2513  }
2514  if (prev_in && next_in) {
2515  // tangent point, both sides in, duplicate that point
2516  new_pts.Append(*ipt);
2517  new_pts.Last()->m_dir = IntersectPoint::TANGENT;
2518  new_pts.Last()->m_curve_pos = ipt->m_curve_pos;
2520  } else if (!prev_in && !next_in) {
2521  // tangent point, both sides out, useless
2523  } else if (prev_in && !next_in) {
2524  // transversal point, going outside
2525  ipt->m_dir = IntersectPoint::OUT;
2526  } else {
2527  // transversal point, going inside
2528  ipt->m_dir = IntersectPoint::IN;
2529  }
2530  }
2531 
2532  clx_points.Append(new_pts.Count(), new_pts.Array());
2533  clx_points.QuickSort(loop_t_compare);
2534 
2535  // Split the outer loop.
2536  ON_SimpleArray<ON_Curve *> outerloop_segs;
2537  int clx_i = 0;
2538  for (int loop_seg = 0; loop_seg < orig_face->m_outerloop.Count(); loop_seg++) {
2539  ON_Curve *remainder = orig_face->m_outerloop[loop_seg]->Duplicate();
2540  if (remainder == NULL) {
2541  bu_log("ON_Curve::Duplicate() failed.\n");
2542  continue;
2543  }
2544  for (; clx_i < clx_points.Count() && clx_points[clx_i].m_loop_seg == loop_seg; clx_i++) {
2545  IntersectPoint &ipt = clx_points[clx_i];
2546  ON_Curve *portion_before_ipt = NULL;
2547  if (remainder) {
2548  double start_t = remainder->Domain().Min();
2549  double end_t = remainder->Domain().Max();
2550  if (ON_NearZero(ipt.m_seg_t - end_t)) {
2551  // Can't call Split() if ipt is at start (that
2552  // case is handled by the initialization) or ipt
2553  // is at end (handled here).
2554  portion_before_ipt = remainder;
2555  remainder = NULL;
2556  } else if (!ON_NearZero(ipt.m_seg_t - start_t)) {
2557  if (!remainder->Split(ipt.m_seg_t, portion_before_ipt, remainder)) {
2558  bu_log("Split failed.\n");
2559  bu_log("Domain: [%f, %f]\n", end_t, start_t);
2560  bu_log("m_seg_t: %f\n", ipt.m_seg_t);
2561  }
2562  }
2563  }
2564  if (portion_before_ipt) {
2565  outerloop_segs.Append(portion_before_ipt);
2566  }
2567  ipt.m_split_li = outerloop_segs.Count() - 1;
2568  }
2569  if (remainder) {
2570  outerloop_segs.Append(remainder);
2571  }
2572  }
2573 
2574  // Append the first element at the last to handle some special cases.
2575  if (clx_points.Count()) {
2576  clx_points.Append(clx_points[0]);
2577  clx_points.Last()->m_loop_seg += orig_face->m_outerloop.Count();
2578  for (int i = 0; i <= clx_points[0].m_split_li; i++) {
2579  ON_Curve *dup = outerloop_segs[i]->Duplicate();
2580  if (dup == NULL) {
2581  bu_log("ON_Curve::Duplicate() failed.\n");
2582  }
2583  outerloop_segs.Append(dup);
2584  }
2585  clx_points.Last()->m_split_li = outerloop_segs.Count() - 1;
2586  }
2587 
2588  if (DEBUG_BREP_BOOLEAN) {
2589  for (int i = 0; i < clx_points.Count(); i++) {
2590  IntersectPoint &ipt = clx_points[i];
2591  bu_log("clx_points[%d](count = %d): ", i, clx_points.Count());
2592  bu_log("m_curve_pos = %d, m_dir = %d\n", ipt.m_curve_pos, ipt.m_dir);
2593  }
2594  }
2595 
2596  std::stack<int> s;
2597  for (int i = 0; i < clx_points.Count(); i++) {
2598  if (clx_points[i].m_dir == IntersectPoint::UNSET) {
2599  continue;
2600  }
2601  if (s.empty()) {
2602  s.push(i);
2603  continue;
2604  }
2605  const IntersectPoint &p = clx_points[s.top()];
2606  const IntersectPoint &q = clx_points[i];
2607 
2608  if (loop_t_compare(&p, &q) > 0 || q.m_split_li < p.m_split_li) {
2609  bu_log("stack error or sort failure.\n");
2610  bu_log("s.top() = %d, i = %d\n", s.top(), i);
2611  bu_log("p->m_split_li = %d, q->m_split_li = %d\n", p.m_split_li, q.m_split_li);
2612  bu_log("p->m_loop_seg = %d, q->m_loop_seg = %d\n", p.m_loop_seg, q.m_loop_seg);
2613  bu_log("p->m_seg_t = %g, q->m_seg_t = %g\n", p.m_seg_t, q.m_seg_t);
2614  continue;
2615  }
2616  if (q.m_curve_pos - p.m_curve_pos == 1 &&
2617  q.m_dir != IntersectPoint::IN &&
2619  {
2620  s.pop();
2621  } else if (p.m_curve_pos - q.m_curve_pos == 1 &&
2622  p.m_dir != IntersectPoint::IN &&
2624  {
2625  s.pop();
2626  } else {
2627  s.push(i);
2628  continue;
2629  }
2630 
2631  // need to form a new loop
2632  ON_SimpleArray<ON_Curve *> newloop;
2633  int curve_count = q.m_split_li - p.m_split_li;
2634  for (int j = p.m_split_li + 1; j <= q.m_split_li; j++) {
2635  // No need to duplicate the curve, because the pointer
2636  // in the array 'outerloop_segs' will be moved out later.
2637  newloop.Append(outerloop_segs[j]);
2638  }
2639 
2640  // The curves on the outer loop is from p to q, so the curves on the
2641  // SSI curve should be from q to p (to form a loop)
2642  double t1 = p.m_curve_t, t2 = q.m_curve_t;
2643  bool need_reverse = true;
2644  if (t1 > t2) {
2645  std::swap(t1, t2);
2646  need_reverse = false;
2647  }
2648  ON_Curve *seg_on_SSI = linked_curve.SubCurve(t1, t2);
2649  if (seg_on_SSI == NULL) {
2650  bu_log("sub_curve() failed.\n");
2651  continue;
2652  }
2653  if (need_reverse) {
2654  if (!seg_on_SSI->Reverse()) {
2655  bu_log("Reverse failed.\n");
2656  continue;
2657  }
2658  }
2659  newloop.Append(seg_on_SSI);
2660  close_small_gaps(newloop);
2661 
2662  ON_Curve *rev_seg_on_SSI = seg_on_SSI->Duplicate();
2663  if (!rev_seg_on_SSI || !rev_seg_on_SSI->Reverse()) {
2664  bu_log("Reverse failed.\n");
2665  continue;
2666  } else {
2667  // Update the outerloop
2668  outerloop_segs[p.m_split_li + 1] = rev_seg_on_SSI;
2669  int k = p.m_split_li + 2;
2670  for (int j = q.m_split_li + 1; j < outerloop_segs.Count(); j++) {
2671  outerloop_segs[k++] = outerloop_segs[j];
2672  }
2673  while (k < outerloop_segs.Count()) {
2674  outerloop_segs[outerloop_segs.Count() - 1] = NULL;
2675  outerloop_segs.Remove();
2676  }
2677  // Update m_split_li
2678  for (int j = i + 1; j < clx_points.Count(); j++) {
2679  clx_points[j].m_split_li -= curve_count - 1;
2680  }
2681  }
2682 
2683  // append the new loop if it's valid
2684  if (is_loop_valid(newloop, ON_ZERO_TOLERANCE)) {
2685  ON_SimpleArray<ON_Curve *> loop;
2686  loop.Append(newloop.Count(), newloop.Array());
2687  out.push_back(loop);
2688  } else {
2689  for (int j = 0; j < newloop.Count(); j++) {
2690  delete newloop[j];
2691  }
2692  }
2693  }
2694 
2695  // Remove the duplicated segments before the first intersection point.
2696  if (clx_points.Count()) {
2697  for (int i = 0; i <= clx_points[0].m_split_li; i++) {
2698  delete outerloop_segs[0];
2699  outerloop_segs[0] = NULL;
2700  outerloop_segs.Remove(0);
2701  }
2702  }
2703 
2704  if (out.size() > 0) {
2705  // The remaining part after splitting some parts out.
2706  close_small_gaps(outerloop_segs);
2707  if (is_loop_valid(outerloop_segs, ON_ZERO_TOLERANCE)) {
2708  ON_SimpleArray<ON_Curve *> loop;
2709  loop.Append(outerloop_segs.Count(), outerloop_segs.Array());
2710  out.push_back(loop);
2711  } else {
2712  for (int i = 0; i < outerloop_segs.Count(); i++)
2713  if (outerloop_segs[i]) {
2714  delete outerloop_segs[i];
2715  }
2716  }
2717  }
2718  return out;
2719 }
2720 
2721 void
2722 free_loops(std::vector<ON_SimpleArray<ON_Curve *> > &loops)
2723 {
2724  for (size_t i = 0; i < loops.size(); ++i) {
2725  for (int j = 0; j < loops[i].Count(); ++j) {
2726  delete loops[i][j];
2727  loops[i][j] = NULL;
2728  }
2729  }
2730 }
2731 
2732 bool
2733 loop_is_degenerate(const ON_SimpleArray<ON_Curve *> &loop)
2734 {
2735  if (loop.Count() < 1) {
2736  return true;
2737  }
2738  // want sufficient distance between non-adjacent curve points
2739  ON_Curve *loop_curve = get_loop_curve(loop);
2740  ON_Interval dom = loop_curve->Domain();
2741 
2742  ON_3dPoint pt1 = loop_curve->PointAt(dom.ParameterAt(.25));
2743  ON_3dPoint pt2 = loop_curve->PointAt(dom.ParameterAt(.75));
2744  delete loop_curve;
2745 
2746  return pt1.DistanceTo(pt2) < INTERSECTION_TOL;
2747 }
2748 
2749 // It might be worth investigating the following approach to building a set of faces from the splitting
2750 // in order to achieve robustness in the final result:
2751 //
2752 // A) trim the raw SSI curves with the trimming loops from both faces and get "final" curve segments in
2753 // 3D and both 2D parametric spaces. Consolidate curves where different faces created the same curve.
2754 // B) assemble the new 2D segments and whatever pieces are needed from the existing trimming curves to
2755 // form new 2D loops (which must be non-self-intersecting), whose roles in A and B respectively
2756 // would be determined by the boolean op and each face's role within it.
2757 // C) build "representative polygons" for all the 2D loops in each face, new and old - representative in
2758 // this case meaning that the intersection behavior of the general loops is accurately duplicated
2759 // by the polygons, which should be assurable by identifying and using all 2D curve intersections and possibly
2760 // horizontal and vertical tangents - and use clipper to perform the boolean ops. Using the resulting polygons,
2761 // deduce and assemble the final trimming loops (and face or faces) created from A and B respectively.
2762 
2763 // Note that the 2D information alone cannot be enough to decide *which* faces created from these splits
2764 // end up in the final brep. A case to think about here is the case of two spheres intersecting -
2765 // depending on A, the exact trimming
2766 // loop in B may need to either define the small area as a new face, or everything BUT the small area
2767 // as a new face - different A spheres may either almost fully contain B or just intersect it. That case
2768 // would seem to suggest that we do need some sort of inside/outside test, since B doesn't have enough
2769 // information to determine which face is to be saved without consulting A. Likewise, A may either save
2770 // just the piece inside the loop or everything outside it, depending on B. This is the same situation we
2771 // were in with the original face sets.
2772 //
2773 // A possible improvement here might be to calculate the best fit plane of the intersection curve and rotate
2774 // both the faces in question and A so that that plane is centered at the origin with the normal in z+.
2775 // In that orientation, axis aligned bounding box tests can be made that will be as informative
2776 // as possible, and may allow many inside/outside decisions to be made without an explicit raytrace. Coplanar
2777 // faces will have to be handled differently, but for convex cases there should be enough information to decide.
2778 // Concave cases may require a raytrace, but there is one other possible approach - if, instead of using the
2779 // whole brep and face bounding boxes we start with the bounding box of the intersection curve and construct
2780 // the sub-box that 'slices' through the parent bbox to the furthest wall in the opposite direction from the
2781 // surface normal, then see which of the two possible
2782 // faces' bounding boxes removes the most volume from that box when subtracted, we may be able to decide
2783 // (say, for a subtraction) which face is cutting deeper. It's not clear to me yet if such an approach would
2784 // work or would scale to complex cases, but it may be worth thinking about.
2785 HIDDEN ON_SimpleArray<TrimmedFace *>
2787  const TrimmedFace *orig_face,
2788  ON_ClassArray<LinkedCurve> &ssx_curves)
2789 {
2790  ON_SimpleArray<TrimmedFace *> out;
2791  out.Append(orig_face->Duplicate());
2792 
2793  if (ssx_curves.Count() == 0) {
2794  // no curves, no splitting
2795  return out;
2796  }
2797 
2798  ON_Curve *face_outerloop = get_loop_curve(orig_face->m_outerloop);
2799  if (!face_outerloop->IsClosed()) {
2800  // need closed outerloop
2801  delete face_outerloop;
2802  return out;
2803  }
2804  delete face_outerloop;
2805 
2806  for (int i = 0; i < ssx_curves.Count(); ++i) {
2807  std::vector<ON_SimpleArray<ON_Curve *> > ssx_loops;
2808 
2809  // get current ssx curve as closed loops
2810  if (ssx_curves[i].IsClosed()) {
2811  ON_SimpleArray<ON_Curve *> loop;
2812  loop.Append(ssx_curves[i].Curve()->Duplicate());
2813  ssx_loops.push_back(loop);
2814  } else {
2815  ssx_loops = split_face_into_loops(orig_face, ssx_curves[i]);
2816  }
2817 
2818  // combine each intersection loop with the original face (or
2819  // the previous iteration of split faces) to create new split
2820  // faces
2821  ON_SimpleArray<TrimmedFace *> next_out;
2822  for (size_t j = 0; j < ssx_loops.size(); ++j) {
2823  if (loop_is_degenerate(ssx_loops[j])) {
2824  continue;
2825  }
2826 
2827  for (int k = 0; k < out.Count(); ++k) {
2828  LoopBooleanResult intersect_loops, diff_loops;
2829 
2830  // get the portion of the face outerloop inside the
2831  // ssx loop
2832  intersect_loops = loop_boolean(out[k]->m_outerloop,
2833  ssx_loops[j], BOOLEAN_INTERSECT);
2834 
2835  if (ssx_curves[i].IsClosed()) {
2836  if (intersect_loops.outerloops.size() == 0) {
2837  // no intersection, just keep the face as-is
2838  next_out.Append(out[k]->Duplicate());
2839  continue;
2840  }
2841 
2842  // for a naturally closed ssx curve, we also need
2843  // the portion outside the loop
2844  diff_loops = loop_boolean(out[k]->m_outerloop, ssx_loops[j],
2845  BOOLEAN_DIFF);
2846 
2847  append_faces_from_loops(next_out, out[k], diff_loops);
2848  diff_loops.ClearInnerloops();
2849  }
2850  append_faces_from_loops(next_out, out[k], intersect_loops);
2851  intersect_loops.ClearInnerloops();
2852  }
2853  }
2854  free_loops(ssx_loops);
2855 
2856  if (next_out.Count() > 0) {
2857  // replace previous faces with the new ones
2858  for (int j = 0; j < out.Count(); ++j) {
2859  delete out[j];
2860  }
2861  out.Empty();
2862 
2863  out.Append(next_out.Count(), next_out.Array());
2864  }
2865  }
2866 
2867  for (int i = 0; i < out.Count(); ++i) {
2868  close_small_gaps(out[i]->m_outerloop);
2869  for (size_t j = 0; j < out[i]->m_innerloop.size(); ++j) {
2870  close_small_gaps(out[i]->m_innerloop[j]);
2871  }
2872  }
2873 
2874  if (DEBUG_BREP_BOOLEAN) {
2875  bu_log("Split to %d faces.\n", out.Count());
2876  for (int i = 0; i < out.Count(); i++) {
2877  bu_log("Trimmed Face %d:\n", i);
2878  bu_log("outerloop:\n");
2879  ON_wString wstr;
2880  ON_TextLog textlog(wstr);
2881  textlog.PushIndent();
2882  for (int j = 0; j < out[i]->m_outerloop.Count(); j++) {
2883  textlog.Print("Curve %d\n", j);
2884  out[i]->m_outerloop[j]->Dump(textlog);
2885  }
2886  if (ON_String(wstr).Array()) {
2887  bu_log("%s", ON_String(wstr).Array());
2888  }
2889 
2890  for (unsigned int j = 0; j < out[i]->m_innerloop.size(); j++) {
2891  bu_log("innerloop %d:\n", j);
2892  ON_wString wstr2;
2893  ON_TextLog textlog2(wstr2);
2894  textlog2.PushIndent();
2895  for (int k = 0; k < out[i]->m_innerloop[j].Count(); k++) {
2896  textlog2.Print("Curve %d\n", k);
2897  out[i]->m_innerloop[j][k]->Dump(textlog2);
2898  }
2899  if (ON_String(wstr2).Array()) {
2900  bu_log("%s", ON_String(wstr2).Array());
2901  }
2902  }
2903  }
2904  }
2905  return out;
2906 }
2907 
2908 
2909 HIDDEN bool
2910 is_same_surface(const ON_Surface *surf1, const ON_Surface *surf2)
2911 {
2912  // Approach: Get their NURBS forms, and compare their CVs.
2913  // If their CVs are all the same (location and weight), they are
2914  // regarded as the same surface.
2915 
2916  if (surf1 == NULL || surf2 == NULL) {
2917  return false;
2918  }
2919  /*
2920  // Deal with two planes, if that's what we have - in that case
2921  // the determination can be more general than the CV comparison
2922  ON_Plane surf1_plane, surf2_plane;
2923  if (surf1->IsPlanar(&surf1_plane) && surf2->IsPlanar(&surf2_plane)) {
2924  ON_3dVector surf1_normal = surf1_plane.Normal();
2925  ON_3dVector surf2_normal = surf2_plane.Normal();
2926  if (surf1_normal.IsParallelTo(surf2_normal) == 1) {
2927  if (surf1_plane.DistanceTo(surf2_plane.Origin()) < ON_ZERO_TOLERANCE) {
2928  return true;
2929  } else {
2930  return false;
2931  }
2932  } else {
2933  return false;
2934  }
2935  }
2936  */
2937 
2938  ON_NurbsSurface nurbs_surf1, nurbs_surf2;
2939  if (!surf1->GetNurbForm(nurbs_surf1) || !surf2->GetNurbForm(nurbs_surf2)) {
2940  return false;
2941  }
2942 
2943  if (nurbs_surf1.Degree(0) != nurbs_surf2.Degree(0)
2944  || nurbs_surf1.Degree(1) != nurbs_surf2.Degree(1)) {
2945  return false;
2946  }
2947 
2948  if (nurbs_surf1.CVCount(0) != nurbs_surf2.CVCount(0)
2949  || nurbs_surf1.CVCount(1) != nurbs_surf2.CVCount(1)) {
2950  return false;
2951  }
2952 
2953  for (int i = 0; i < nurbs_surf1.CVCount(0); i++) {
2954  for (int j = 0; j < nurbs_surf2.CVCount(1); j++) {
2955  ON_4dPoint cvA, cvB;
2956  nurbs_surf1.GetCV(i, j, cvA);
2957  nurbs_surf2.GetCV(i, j, cvB);
2958  if (cvA != cvB) {
2959  return false;
2960  }
2961  }
2962  }
2963 
2964  if (nurbs_surf1.KnotCount(0) != nurbs_surf2.KnotCount(0)
2965  || nurbs_surf1.KnotCount(1) != nurbs_surf2.KnotCount(1)) {
2966  return false;
2967  }
2968 
2969  for (int i = 0; i < nurbs_surf1.KnotCount(0); i++) {
2970  if (!ON_NearZero(nurbs_surf1.m_knot[0][i] - nurbs_surf2.m_knot[0][i])) {
2971  return false;
2972  }
2973  }
2974 
2975  for (int i = 0; i < nurbs_surf1.KnotCount(1); i++) {
2976  if (!ON_NearZero(nurbs_surf1.m_knot[1][i] - nurbs_surf2.m_knot[1][i])) {
2977  return false;
2978  }
2979  }
2980 
2981  return true;
2982 }
2983 
2984 
2985 HIDDEN void
2986 add_elements(ON_Brep *brep, ON_BrepFace &face, const ON_SimpleArray<ON_Curve *> &loop, ON_BrepLoop::TYPE loop_type)
2987 {
2988  if (!loop.Count()) {
2989  return;
2990  }
2991 
2992  ON_BrepLoop &breploop = brep->NewLoop(loop_type, face);
2993  const ON_Surface *srf = face.SurfaceOf();
2994 
2995  // Determine whether a segment should be a seam trim, according to the
2996  // requirements in ON_Brep::IsValid() (See opennurbs_brep.cpp)
2997  for (int k = 0; k < loop.Count(); k++) {
2998  ON_BOOL32 bClosed[2];
2999  bClosed[0] = srf->IsClosed(0);
3000  bClosed[1] = srf->IsClosed(1);
3001  if (bClosed[0] || bClosed[1]) {
3002  ON_Surface::ISO iso1, iso2, iso_type;
3003  int endpt_index = -1;
3004  iso1 = srf->IsIsoparametric(*loop[k]);
3005  if (ON_Surface::E_iso == iso1 && bClosed[0]) {
3006  iso_type = ON_Surface::W_iso;
3007  endpt_index = 1;
3008  } else if (ON_Surface::W_iso == iso1 && bClosed[0]) {
3009  iso_type = ON_Surface::E_iso;
3010  endpt_index = 1;
3011  } else if (ON_Surface::S_iso == iso1 && bClosed[1]) {
3012  iso_type = ON_Surface::N_iso;
3013  endpt_index = 0;
3014  } else if (ON_Surface::N_iso == iso1 && bClosed[1]) {
3015  iso_type = ON_Surface::S_iso;
3016  endpt_index = 0;
3017  }
3018  if (endpt_index != -1) {
3019  ON_Interval side_interval;
3020  const double side_tol = 1.0e-4;
3021  double s0, s1;
3022  bool seamed = false;
3023  side_interval.Set(loop[k]->PointAtStart()[endpt_index], loop[k]->PointAtEnd()[endpt_index]);
3024  if (((ON_Surface::N_iso == iso_type || ON_Surface::W_iso == iso_type) && side_interval.IsIncreasing())
3025  || ((ON_Surface::S_iso == iso_type || ON_Surface::E_iso == iso_type) && side_interval.IsDecreasing())) {
3026  for (int i = 0; i < breploop.m_ti.Count(); i++) {
3027  ON_BrepTrim &trim = brep->m_T[breploop.m_ti[i]];
3028  if (ON_BrepTrim::boundary != trim.m_type) {
3029  continue;
3030  }
3031  iso2 = srf->IsIsoparametric(trim);
3032  if (iso2 != iso_type) {
3033  continue;
3034  }
3035  s1 = side_interval.NormalizedParameterAt(trim.PointAtStart()[endpt_index]);
3036  if (fabs(s1 - 1.0) > side_tol) {
3037  continue;
3038  }
3039  s0 = side_interval.NormalizedParameterAt(trim.PointAtEnd()[endpt_index]);
3040  if (fabs(s0) > side_tol) {
3041  continue;
3042  }
3043 
3044  // Check 3D distances - not included in ON_Brep::IsValid().
3045  // So with this check, we only add seam trims if their end points
3046  // are the same within ON_ZERO_TOLERANCE. This will cause IsValid()
3047  // reporting "they should be seam trims connected to the same edge",
3048  // because the 2D tolerance (side_tol) are hardcoded to 1.0e-4.
3049  // We still add this check because we treat two vertexes to be the
3050  // same only if their distance < ON_ZERO_TOLERANCE. (Maybe 3D dist
3051  // should also be added to ON_Brep::IsValid()?)
3052  if (srf->PointAt(trim.PointAtStart().x, trim.PointAtStart().y).DistanceTo(
3053  srf->PointAt(loop[k]->PointAtEnd().x, loop[k]->PointAtEnd().y)) >= ON_ZERO_TOLERANCE) {
3054  continue;
3055  }
3056 
3057  if (srf->PointAt(trim.PointAtEnd().x, trim.PointAtEnd().y).DistanceTo(
3058  srf->PointAt(loop[k]->PointAtStart().x, loop[k]->PointAtStart().y)) >= ON_ZERO_TOLERANCE) {
3059  continue;
3060  }
3061 
3062  // We add another checking, which is not included in ON_Brep::IsValid()
3063  // - they should be iso boundaries of the surface.
3064  double s2 = srf->Domain(1 - endpt_index).NormalizedParameterAt(loop[k]->PointAtStart()[1 - endpt_index]);
3065  double s3 = srf->Domain(1 - endpt_index).NormalizedParameterAt(trim.PointAtStart()[1 - endpt_index]);
3066  if ((fabs(s2 - 1.0) < side_tol && fabs(s3) < side_tol) ||
3067  (fabs(s2) < side_tol && fabs(s3 - 1.0) < side_tol)) {
3068  // Find a trim that should share the same edge
3069  int ti = brep->AddTrimCurve(loop[k]);
3070  ON_BrepTrim &newtrim = brep->NewTrim(brep->m_E[trim.m_ei], true, breploop, ti);
3071  // newtrim.m_type = ON_BrepTrim::seam;
3072  newtrim.m_tolerance[0] = newtrim.m_tolerance[1] = MAX_FASTF;
3073  seamed = true;
3074  break;
3075  }
3076  }
3077  if (seamed) {
3078  continue;
3079  }
3080  }
3081  }
3082  }
3083 
3084  ON_Curve *c3d = NULL;
3085  // First, try the ON_Surface::Pushup() method.
3086  // If Pushup() does not succeed, use sampling method.
3087  c3d = face.SurfaceOf()->Pushup(*(loop[k]), INTERSECTION_TOL);
3088  if (!c3d) {
3089  ON_3dPointArray ptarray(101);
3090  for (int l = 0; l <= 100; l++) {
3091  ON_3dPoint pt2d;
3092  pt2d = loop[k]->PointAt(loop[k]->Domain().ParameterAt(l / 100.0));
3093  ptarray.Append(face.SurfaceOf()->PointAt(pt2d.x, pt2d.y));
3094  }
3095  c3d = new ON_PolylineCurve(ptarray);
3096  }
3097 
3098  if (c3d->BoundingBox().Diagonal().Length() < ON_ZERO_TOLERANCE) {
3099  // The trim is singular
3100  int i;
3101  ON_3dPoint vtx = c3d->PointAtStart();
3102  for (i = brep->m_V.Count() - 1; i >= 0; i--) {
3103  if (brep->m_V[i].Point().DistanceTo(vtx) < ON_ZERO_TOLERANCE) {
3104  break;
3105  }
3106  }
3107  if (i < 0) {
3108  i = brep->m_V.Count();
3109  brep->NewVertex(c3d->PointAtStart(), 0.0);
3110  }
3111  int ti = brep->AddTrimCurve(loop[k]);
3112  ON_BrepTrim &trim = brep->NewSingularTrim(brep->m_V[i], breploop, srf->IsIsoparametric(*loop[k]), ti);
3113  trim.m_tolerance[0] = trim.m_tolerance[1] = MAX_FASTF;
3114  delete c3d;
3115  continue;
3116  }
3117 
3118  ON_2dPoint start = loop[k]->PointAtStart(), end = loop[k]->PointAtEnd();
3119  int start_idx, end_idx;
3120 
3121  // Get the start vertex index
3122  if (k > 0) {
3123  start_idx = brep->m_T.Last()->m_vi[1];
3124  } else {
3125  ON_3dPoint vtx = face.SurfaceOf()->PointAt(start.x, start.y);
3126  int i;
3127  for (i = 0; i < brep->m_V.Count(); i++) {
3128  if (brep->m_V[i].Point().DistanceTo(vtx) < ON_ZERO_TOLERANCE) {
3129  break;
3130  }
3131  }
3132  start_idx = i;
3133  if (i == brep->m_V.Count()) {
3134  brep->NewVertex(vtx, 0.0);
3135  }
3136  }
3137 
3138  // Get the end vertex index
3139  if (c3d->IsClosed()) {
3140  end_idx = start_idx;
3141  } else {
3142  ON_3dPoint vtx = face.SurfaceOf()->PointAt(end.x, end.y);
3143  int i;
3144  for (i = 0; i < brep->m_V.Count(); i++) {
3145  if (brep->m_V[i].Point().DistanceTo(vtx) < ON_ZERO_TOLERANCE) {
3146  break;
3147  }
3148  }
3149  end_idx = i;
3150  if (i == brep->m_V.Count()) {
3151  brep->NewVertex(vtx, 0.0);
3152  }
3153  }
3154 
3155  brep->AddEdgeCurve(c3d);
3156  int ti = brep->AddTrimCurve(loop[k]);
3157  ON_BrepEdge &edge = brep->NewEdge(brep->m_V[start_idx], brep->m_V[end_idx],
3158  brep->m_C3.Count() - 1, (const ON_Interval *)0, MAX_FASTF);
3159  ON_BrepTrim &trim = brep->NewTrim(edge, 0, breploop, ti);
3160  trim.m_tolerance[0] = trim.m_tolerance[1] = MAX_FASTF;
3161  }
3162 }
3163 
3164 HIDDEN bool
3165 is_point_on_brep_surface(const ON_3dPoint &pt, const ON_Brep *brep, ON_SimpleArray<Subsurface *> &surf_tree)
3166 {
3167  // Decide whether a point is on a brep's surface.
3168  // Basic approach: use PSI on the point with all the surfaces.
3169 
3170  if (brep == NULL || pt.IsUnsetPoint()) {
3171  bu_log("is_point_on_brep_surface(): brep == NULL || pt.IsUnsetPoint()\n");
3172  return false;
3173  }
3174 
3175  if (surf_tree.Count() != brep->m_S.Count()) {
3176  bu_log("is_point_on_brep_surface(): surf_tree.Count() != brep->m_S.Count()\n");
3177  return false;
3178  }
3179 
3180  ON_BoundingBox bbox = brep->BoundingBox();
3181  bbox.m_min -= ON_3dVector(INTERSECTION_TOL, INTERSECTION_TOL, INTERSECTION_TOL);
3182  bbox.m_max += ON_3dVector(INTERSECTION_TOL, INTERSECTION_TOL, INTERSECTION_TOL);
3183  if (!bbox.IsPointIn(pt)) {
3184  return false;
3185  }
3186 
3187  for (int i = 0; i < brep->m_F.Count(); i++) {
3188  const ON_BrepFace &face = brep->m_F[i];
3189  const ON_Surface *surf = face.SurfaceOf();
3190  ON_ClassArray<ON_PX_EVENT> px_event;
3191  if (!ON_Intersect(pt, *surf, px_event, INTERSECTION_TOL, 0, 0, surf_tree[face.m_si])) {
3192  continue;
3193  }
3194 
3195  // Get the trimming curves of the face, and determine whether the
3196  // points are inside the outerloop
3197  ON_SimpleArray<ON_Curve *> outerloop;
3198  const ON_BrepLoop &loop = brep->m_L[face.m_li[0]]; // outerloop only
3199  for (int j = 0; j < loop.m_ti.Count(); j++) {
3200  outerloop.Append(brep->m_C2[brep->m_T[loop.m_ti[j]].m_c2i]);
3201  }
3202  ON_2dPoint pt2d(px_event[0].m_b[0], px_event[0].m_b[1]);
3203  try {
3204  if (!is_point_outside_loop(pt2d, outerloop)) {
3205  return true;
3206  }
3207  } catch (InvalidGeometry &e) {
3208  bu_log("%s", e.what());
3209  }
3210  }
3211 
3212  return false;
3213 }
3214 
3215 
3216 HIDDEN bool
3217 is_point_inside_brep(const ON_3dPoint &pt, const ON_Brep *brep, ON_SimpleArray<Subsurface *> &surf_tree)
3218 {
3219  // Decide whether a point is inside a brep's surface.
3220  // Basic approach: intersect a ray with the brep, and count the number of
3221  // intersections (like the raytrace)
3222  // Returns true (inside) or false (outside) provided the pt is not on the
3223  // surfaces. (See also is_point_on_brep_surface())
3224 
3225  if (brep == NULL || pt.IsUnsetPoint()) {
3226  bu_log("is_point_inside_brep(): brep == NULL || pt.IsUnsetPoint()\n");
3227  return false;
3228  }
3229 
3230  if (surf_tree.Count() != brep->m_S.Count()) {
3231  bu_log("is_point_inside_brep(): surf_tree.Count() != brep->m_S.Count()\n");
3232  return false;
3233  }
3234 
3235  ON_BoundingBox bbox = brep->BoundingBox();
3236  bbox.m_min -= ON_3dVector(INTERSECTION_TOL, INTERSECTION_TOL, INTERSECTION_TOL);
3237  bbox.m_max += ON_3dVector(INTERSECTION_TOL, INTERSECTION_TOL, INTERSECTION_TOL);
3238  if (!bbox.IsPointIn(pt)) {
3239  return false;
3240  }
3241 
3242  ON_3dVector diag = bbox.Diagonal() * 1.5; // Make it even longer
3243  ON_LineCurve line(pt, pt + diag); // pt + diag should be outside, if pt
3244  // is inside the bbox
3245 
3246  ON_3dPointArray isect_pt;
3247  for (int i = 0; i < brep->m_F.Count(); i++) {
3248  const ON_BrepFace &face = brep->m_F[i];
3249  const ON_Surface *surf = face.SurfaceOf();
3250  ON_SimpleArray<ON_X_EVENT> x_event;
3251  if (!ON_Intersect(&line, surf, x_event, INTERSECTION_TOL, 0.0, 0, 0, 0, 0, 0, surf_tree[face.m_si])) {
3252  continue;
3253  }
3254 
3255  // Get the trimming curves of the face, and determine whether the
3256  // points are inside the outerloop
3257  ON_SimpleArray<ON_Curve *> outerloop;
3258  const ON_BrepLoop &loop = brep->m_L[face.m_li[0]]; // outerloop only
3259  for (int j = 0; j < loop.m_ti.Count(); j++) {
3260  outerloop.Append(brep->m_C2[brep->m_T[loop.m_ti[j]].m_c2i]);
3261  }
3262  try {
3263  for (int j = 0; j < x_event.Count(); j++) {
3264  ON_2dPoint pt2d(x_event[j].m_b[0], x_event[j].m_b[1]);
3265  if (!is_point_outside_loop(pt2d, outerloop)) {
3266  isect_pt.Append(x_event[j].m_B[0]);
3267  }
3268  if (x_event[j].m_type == ON_X_EVENT::ccx_overlap) {
3269  pt2d = ON_2dPoint(x_event[j].m_b[2], x_event[j].m_b[3]);
3270  if (!is_point_outside_loop(pt2d, outerloop)) {
3271  isect_pt.Append(x_event[j].m_B[1]);
3272  }
3273  }
3274  }
3275  } catch (InvalidGeometry &e) {
3276  bu_log("%s", e.what());
3277  }
3278  }
3279 
3280  // Remove duplications
3281  ON_3dPointArray pt_no_dup;
3282  for (int i = 0; i < isect_pt.Count(); i++) {
3283  int j;
3284  for (j = 0; j < pt_no_dup.Count(); j++) {
3285  if (isect_pt[i].DistanceTo(pt_no_dup[j]) < INTERSECTION_TOL) {
3286  break;
3287  }
3288  }
3289  if (j == pt_no_dup.Count()) {
3290  // No duplication, append to the array
3291  pt_no_dup.Append(isect_pt[i]);
3292  }
3293  }
3294 
3295  return pt_no_dup.Count() % 2 != 0;
3296 }
3297 
3298 HIDDEN bool
3299 is_point_inside_trimmed_face(const ON_2dPoint &pt, const TrimmedFace *tface)
3300 {
3301  bool inside = false;
3302  if (is_point_inside_loop(pt, tface->m_outerloop)) {
3303  inside = true;
3304  for (size_t i = 0; i < tface->m_innerloop.size(); ++i) {
3305  if (!is_point_outside_loop(pt, tface->m_innerloop[i])) {
3306  inside = false;
3307  break;
3308  }
3309  }
3310  }
3311  return inside;
3312 }
3313 
3314 // TODO: For faces that have most of their area trimmed away, this is
3315 // a very inefficient algorithm. If the grid approach doesn't work
3316 // after a small number of samples, we should switch to an alternative
3317 // algorithm, such as sampling around points on the inner loops.
3318 HIDDEN ON_2dPoint
3320 {
3321  const int GP_MAX_STEPS = 8; // must be a power of two
3322 
3323  ON_PolyCurve polycurve;
3324  if (!is_loop_valid(tface->m_outerloop, ON_ZERO_TOLERANCE, &polycurve)) {
3325  throw InvalidGeometry("face_brep_location(): invalid outerloop.\n");
3326  }
3327  ON_BoundingBox bbox = polycurve.BoundingBox();
3328  double u_len = bbox.m_max.x - bbox.m_min.x;
3329  double v_len = bbox.m_max.y - bbox.m_min.y;
3330 
3331  ON_2dPoint test_pt2d;
3332  bool found = false;
3333  for (int steps = 1; steps <= GP_MAX_STEPS && !found; steps *= 2) {
3334  double u_halfstep = u_len / (steps * 2.0);
3335  double v_halfstep = v_len / (steps * 2.0);
3336 
3337  for (int i = 0; i < steps && !found; ++i) {
3338  test_pt2d.x = bbox.m_min.x + u_halfstep * (1 + 2 * i);
3339 
3340  for (int j = 0; j < steps && !found; ++j) {
3341  test_pt2d.y = bbox.m_min.y + v_halfstep * (1 + 2 * j);
3342  found = is_point_inside_trimmed_face(test_pt2d, tface);
3343  }
3344  }
3345  }
3346  if (!found) {
3347  throw AlgorithmError("Cannot find a point inside this trimmed face. Aborted.\n");
3348  }
3349  return test_pt2d;
3350 }
3351 
3352 enum {
3356 };
3357 
3358 // Returns the location of the face with respect to the brep.
3359 //
3360 // Throws InvalidGeometry if given invalid arguments.
3361 // Throws AlgorithmError if a point inside the TrimmedFace can't be
3362 // found for testing.
3363 HIDDEN int
3364 face_brep_location(const TrimmedFace *tface, const ON_Brep *brep, ON_SimpleArray<Subsurface *> &surf_tree)
3365 {
3366  if (tface == NULL || brep == NULL) {
3367  throw InvalidGeometry("face_brep_location(): given NULL argument.\n");
3368  }
3369 
3370  const ON_BrepFace *bface = tface->m_face;
3371  if (bface == NULL) {
3372  throw InvalidGeometry("face_brep_location(): TrimmedFace has NULL face.\n");
3373  }
3374 
3375  ON_BoundingBox brep2box = brep->BoundingBox();
3376  brep2box.m_min -= ON_3dVector(INTERSECTION_TOL, INTERSECTION_TOL, INTERSECTION_TOL);
3377  brep2box.m_max += ON_3dVector(INTERSECTION_TOL, INTERSECTION_TOL, INTERSECTION_TOL);
3378  if (!bface->BoundingBox().Intersection(brep2box)) {
3379  return OUTSIDE_BREP;
3380  }
3381 
3382  if (tface->m_outerloop.Count() == 0) {
3383  throw InvalidGeometry("face_brep_location(): the input TrimmedFace is not trimmed.\n");
3384  }
3385 
3386  ON_PolyCurve polycurve;
3387  if (!is_loop_valid(tface->m_outerloop, ON_ZERO_TOLERANCE, &polycurve)) {
3388  throw InvalidGeometry("face_brep_location(): invalid outerloop.\n");
3389  }
3390  ON_2dPoint test_pt2d = get_point_inside_trimmed_face(tface);
3391  ON_3dPoint test_pt3d = tface->m_face->PointAt(test_pt2d.x, test_pt2d.y);
3392 
3393  if (DEBUG_BREP_BOOLEAN) {
3394  bu_log("valid test point: (%g, %g, %g)\n", test_pt3d.x, test_pt3d.y, test_pt3d.z);
3395  }
3396 
3397  if (is_point_on_brep_surface(test_pt3d, brep, surf_tree)) {
3398  // because the overlap parts will be split out as separated trimmed
3399  // faces, if one point on a trimmed face is on the brep's surface,
3400  // the whole trimmed face should be on the surface
3401  return ON_BREP_SURFACE;
3402  }
3403 
3404  return is_point_inside_brep(test_pt3d, brep, surf_tree) ? INSIDE_BREP : OUTSIDE_BREP;
3405 }
3406 
3407 HIDDEN ON_ClassArray<ON_SimpleArray<SSICurve> >
3409  ON_SimpleArray<Subsurface *> &surf_tree1,
3410  ON_SimpleArray<Subsurface *> &surf_tree2,
3411  const ON_Brep *brep1,
3412  const ON_Brep *brep2,
3413  op_type operation)
3414 {
3415  std::set<int> unused1, unused2;
3416  std::set<int> finalform1, finalform2;
3417  int face_count1 = brep1->m_F.Count();
3418  int face_count2 = brep2->m_F.Count();
3419 
3420  /* Depending on the operation type and the bounding box behaviors, we
3421  * can sometimes decide immediately whether a face will end up in the
3422  * final brep or will have no role in the intersections - do that
3423  * categorization up front */
3424  for (int i = 0; i < face_count1 + face_count2; i++) {
3425  const ON_BrepFace &face = i < face_count1 ? brep1->m_F[i] : brep2->m_F[i - face_count1];
3426  const ON_Brep *brep = i < face_count1 ? brep2 : brep1;
3427  std::set<int> *unused = i < face_count1 ? &unused1 : &unused2;
3428  std::set<int> *intact = i < face_count1 ? &finalform1 : &finalform2;
3429  int curr_index = i < face_count1 ? i : i - face_count1;
3430  if (face.BoundingBox().MinimumDistanceTo(brep->BoundingBox()) > ON_ZERO_TOLERANCE) {
3431  switch (operation) {
3432  case BOOLEAN_UNION:
3433  intact->insert(curr_index);
3434  break;
3435  case BOOLEAN_DIFF:
3436  if (i < face_count1) {
3437  intact->insert(curr_index);
3438  }
3439  if (i >= face_count1) {
3440  unused->insert(curr_index);
3441  }
3442  break;
3443  case BOOLEAN_INTERSECT:
3444  unused->insert(curr_index);
3445  break;
3446  default:
3447  throw InvalidBooleanOperation("Error - unknown "
3448  "boolean operation\n");
3449  }
3450  }
3451  }
3452 
3453  // For the faces that we can't rule out, there are several possible roles they can play:
3454  //
3455  // 1. Fully utilized in the new brep
3456  // 2. Changed into a new set of faces by intersections, each of which must be evaluated
3457  // 3. Fully discarded by the new brep
3458  //
3459  // We won't be able to distinguish between 1 and 3 at this stage, but we can narrow in
3460  // on which faces might fall into category 2 and what faces they might interact with.
3461  std::set<std::pair<int, int> > intersection_candidates;
3462  for (int i = 0; i < face_count1; i++) {
3463  if (unused1.find(i) == unused1.end() && finalform1.find(i) == finalform1.end()) {
3464  for (int j = 0; j < face_count2; j++) {
3465  if (unused2.find(j) == unused2.end() && finalform2.find(j) == finalform2.end()) {
3466  // If the two faces don't interact according to their bounding boxes,
3467  // they won't be a source of events - otherwise, they must be checked.
3468  fastf_t disjoint = brep1->m_F[i].BoundingBox().MinimumDistanceTo(brep2->m_F[j].BoundingBox());
3469  if (!(disjoint > ON_ZERO_TOLERANCE)) {
3470  intersection_candidates.insert(std::pair<int, int>(i, j));
3471  }
3472  }
3473  }
3474  }
3475  }
3476 
3477  // For those not in category 2 an inside/outside test on the breps combined with the boolean op
3478  // should be enough to decide the issue, but there is a problem. If *all* faces of a brep are
3479  // inside the other brep and the operation is a subtraction, we don't want a "floating" inside-out
3480  // brep volume inside the outer volume and topologically isolated. Normally this is handled by
3481  // creating a face that connects the outer and inner shells, but this is potentially a non-trivial
3482  // operation. The only thing that comes immediately to mind is to find the center point of the
3483  // bounding box of the inner brep, create a plane using that point and the z+ unit vector for a normal, and
3484  // cut both breps in half with that plane to form four new breps and two new subtraction problems.
3485  //
3486  // More broadly, this is a problem - unioning two half-spheres with a sphere subtracted out of their
3487  // respective centers will end up with isolated surfaces in the middle of the union unless the routines
3488  // know they must keep one of the coplanar faces in order to topologically connect the middle. However,
3489  // in the case where there is no center sphere the central face should be removed. It may be that the
3490  // condition to satisfy for removal is no interior trimming loops on the face.
3491  //
3492  //
3493  // Also worth thinking about - would it be possible to then do edge comparisons to
3494  // determine which of the "fully used/fully non-used" faces are needed?
3495 
3496  if (DEBUG_BREP_BOOLEAN) {
3497  bu_log("Summary of brep status: \n unused1: %zd\n unused2: %zd\n finalform1: %zd\n finalform2 %zd\nintersection_candidates(%zd):\n", unused1.size(), unused2.size(), finalform1.size(), finalform2.size(), intersection_candidates.size());
3498  for (std::set<std::pair<int, int> >::iterator it = intersection_candidates.begin(); it != intersection_candidates.end(); ++it) {
3499  bu_log(" (%d,%d)\n", (*it).first, (*it).second);
3500  }
3501  }
3502 
3503  int surf_count1 = brep1->m_S.Count();
3504  int surf_count2 = brep2->m_S.Count();
3505  for (int i = 0; i < surf_count1; i++) {
3506  surf_tree1.Append(new Subsurface(brep1->m_S[i]->Duplicate()));
3507  }
3508  for (int i = 0; i < surf_count2; i++) {
3509  surf_tree2.Append(new Subsurface(brep2->m_S[i]->Duplicate()));
3510  }
3511 
3512  ON_ClassArray<ON_SimpleArray<SSICurve> > curves_array(face_count1 + face_count2);
3513 
3514  // count must equal capacity for array copy to work as expected
3515  // when the result of the function is assigned
3516  curves_array.SetCount(curves_array.Capacity());
3517 
3518  // calculate intersection curves
3519  for (int i = 0; i < face_count1; i++) {
3520  for (int j = 0; j < face_count2; j++) {
3521  if (intersection_candidates.find(std::pair<int, int>(i, j)) != intersection_candidates.end()) {
3522  ON_Surface *surf1, *surf2;
3523  ON_ClassArray<ON_SSX_EVENT> events;
3524  int results = 0;
3525  surf1 = brep1->m_S[brep1->m_F[i].m_si];
3526  surf2 = brep2->m_S[brep2->m_F[j].m_si];
3527  if (is_same_surface(surf1, surf2)) {
3528  continue;
3529  }
3530 
3531  // Possible enhancement: Some faces may share the same surface.
3532  // We can store the result of SSI to avoid re-computation.
3533  results = ON_Intersect(surf1,
3534  surf2,
3535  events,
3537  0.0,
3538  0.0,
3539  NULL,
3540  NULL,
3541  NULL,
3542  NULL,
3543  surf_tree1[brep1->m_F[i].m_si],
3544  surf_tree2[brep2->m_F[j].m_si]);
3545  if (results <= 0) {
3546  continue;
3547  }
3548  ON_SimpleArray<ON_Curve *> face1_curves, face2_curves;
3549  for (int k = 0; k < events.Count(); k++) {
3550  if (events[k].m_type == ON_SSX_EVENT::ssx_tangent ||
3551  events[k].m_type == ON_SSX_EVENT::ssx_transverse ||
3552  events[k].m_type == ON_SSX_EVENT::ssx_overlap)
3553  {
3554  ON_SimpleArray<ON_Curve *> subcurves_on1, subcurves_on2;
3555 
3556  get_subcurves_inside_faces(subcurves_on1,
3557  subcurves_on2, brep1, brep2, i, j, &events[k]);
3558 
3559  for (int l = 0; l < subcurves_on1.Count(); ++l) {
3560  SSICurve ssi_on1;
3561  ssi_on1.m_curve = subcurves_on1[l];
3562  curves_array[i].Append(ssi_on1);
3563 
3564  face1_curves.Append(subcurves_on1[l]);
3565  }
3566  for (int l = 0; l < subcurves_on2.Count(); ++l) {
3567  SSICurve ssi_on2;
3568  ssi_on2.m_curve = subcurves_on2[l];
3569  curves_array[face_count1 + j].Append(ssi_on2);
3570 
3571  face2_curves.Append(subcurves_on2[l]);
3572  }
3573  }
3574  }
3575 
3576  if (DEBUG_BREP_BOOLEAN) {
3577  // Look for coplanar faces
3578  ON_Plane surf1_plane, surf2_plane;
3579  if (surf1->IsPlanar(&surf1_plane) && surf2->IsPlanar(&surf2_plane)) {
3580  /* We already checked for disjoint above, so the only remaining question is the normals */
3581  if (surf1_plane.Normal().IsParallelTo(surf2_plane.Normal())) {
3582  bu_log("Faces brep1->%d and brep2->%d are coplanar and intersecting\n", i, j);
3583  }
3584  }
3585  }
3586 
3587  }
3588 
3589  }
3590  }
3591 
3592  return curves_array;
3593 }
3594 
3595 HIDDEN ON_SimpleArray<ON_Curve *>get_face_trim_loop(const ON_Brep *brep, int face_loop_index)
3596 {
3597  const ON_BrepLoop &loop = brep->m_L[face_loop_index];
3598  const ON_SimpleArray<int> &trim_index = loop.m_ti;
3599  ON_SimpleArray<ON_Curve *> face_trim_loop;
3600  for (int i = 0; i < trim_index.Count(); ++i) {
3601  ON_Curve *curve2d = brep->m_C2[brep->m_T[trim_index[i]].m_c2i];
3602  face_trim_loop.Append(curve2d->Duplicate());
3603  }
3604  return face_trim_loop;
3605 }
3606 
3607 HIDDEN ON_SimpleArray<TrimmedFace *>
3609 {
3610  ON_SimpleArray<TrimmedFace *> trimmed_faces;
3611  int face_count = brep->m_F.Count();
3612  for (int i = 0; i < face_count; i++) {
3613  const ON_BrepFace &face = brep->m_F[i];
3614  const ON_SimpleArray<int> &loop_index = face.m_li;
3615 
3616  TrimmedFace *trimmed_face = new TrimmedFace();
3617  trimmed_face->m_face = &face;
3618 
3619  if (loop_index.Count() > 0) {
3620  ON_SimpleArray<ON_Curve *> index_loop = get_face_trim_loop(brep, loop_index[0]);
3621  trimmed_face->m_outerloop = index_loop;
3622  for (int j = 1; j < loop_index.Count(); j++) {
3623  index_loop = get_face_trim_loop(brep, loop_index[j]);
3624  trimmed_face->m_innerloop.push_back(index_loop);
3625  }
3626  }
3627  trimmed_faces.Append(trimmed_face);
3628  }
3629  return trimmed_faces;
3630 }
3631 
3632 HIDDEN void
3634  ON_ClassArray<ON_SimpleArray<TrimmedFace *> > &trimmed_faces,
3635  const ON_Brep *brep1,
3636  const ON_Brep *brep2,
3637  ON_SimpleArray<Subsurface *> &surf_tree1,
3638  ON_SimpleArray<Subsurface *> &surf_tree2,
3639  op_type operation)
3640 {
3641  int face_count1 = brep1->m_F.Count();
3642  for (int i = 0; i < trimmed_faces.Count(); i++) {
3643  /* Perform inside-outside test to decide whether the trimmed face should
3644  * be used in the final b-rep structure or not.
3645  * Different operations should be dealt with accordingly.
3646  * Use connectivity graphs (optional) which represents the topological
3647  * structure of the b-rep. This can reduce time-consuming inside-outside
3648  * tests.
3649  */
3650  const ON_SimpleArray<TrimmedFace *> &splitted = trimmed_faces[i];
3651  const ON_Brep *another_brep = i >= face_count1 ? brep1 : brep2;
3652  ON_SimpleArray<Subsurface *> &surf_tree = i >= face_count1 ? surf_tree1 : surf_tree2;
3653  for (int j = 0; j < splitted.Count(); j++) {
3654  if (splitted[j]->m_belong_to_final != TrimmedFace::UNKNOWN) {
3655  // Visited before, don't need to test again
3656  continue;
3657  }
3658 
3659  int face_location = -1;
3660  try {
3661  face_location = face_brep_location(splitted[j], another_brep, surf_tree);
3662  } catch (InvalidGeometry &e) {
3663  bu_log("%s", e.what());
3664  } catch (AlgorithmError &e) {
3665  bu_log("%s", e.what());
3666  }
3667  if (face_location < 0) {
3668  if (DEBUG_BREP_BOOLEAN) {
3669  bu_log("Whether the trimmed face is inside/outside is unknown.\n");
3670  }
3671  splitted[j]->m_belong_to_final = TrimmedFace::NOT_BELONG;
3672  continue;
3673  }
3674 
3675  splitted[j]->m_rev = false;
3676  switch (face_location) {
3677  case INSIDE_BREP:
3678  if (operation == BOOLEAN_INTERSECT ||
3679  operation == BOOLEAN_XOR ||
3680  (operation == BOOLEAN_DIFF && i >= face_count1))
3681  {
3682  splitted[j]->m_belong_to_final = TrimmedFace::BELONG;
3683  }
3684  if (operation == BOOLEAN_DIFF || operation == BOOLEAN_XOR) {
3685  splitted[j]->m_rev = true;
3686  }
3687  break;
3688  case OUTSIDE_BREP:
3689  if (operation == BOOLEAN_UNION ||
3690  operation == BOOLEAN_XOR ||
3691  (operation == BOOLEAN_DIFF && i < face_count1))
3692  {
3693  splitted[j]->m_belong_to_final = TrimmedFace::BELONG;
3694  }
3695  break;
3696  case ON_BREP_SURFACE:
3697  // get a 3d point on the face
3698  ON_2dPoint face_pt2d = get_point_inside_trimmed_face(splitted[j]);
3699  ON_3dPoint face_pt3d = splitted[j]->m_face->PointAt(face_pt2d.x, face_pt2d.y);
3700 
3701  // find the matching point on the other brep
3702  ON_3dPoint brep_pt2d;
3703  const ON_Surface *brep_surf;
3704  bool found = false;
3705  for (int fi = 0; fi < another_brep->m_F.Count(); ++fi) {
3706  const ON_BrepFace &face = another_brep->m_F[fi];
3707  brep_surf = face.SurfaceOf();
3708  ON_ClassArray<ON_PX_EVENT> px_event;
3709 
3710  if (ON_Intersect(face_pt3d, *brep_surf, px_event,
3711  INTERSECTION_TOL, 0, 0, surf_tree[face.m_si]))
3712  {
3713  found = true;
3714  brep_pt2d = px_event[0].m_b;
3715  break;
3716  }
3717  }
3718  if (found) {
3719  // compare normals of surfaces at shared point
3720  ON_3dVector brep_norm, face_norm;
3721  brep_surf->EvNormal(brep_pt2d.x, brep_pt2d.y, brep_norm);
3722  splitted[j]->m_face->SurfaceOf()->EvNormal(face_pt2d.x, face_pt2d.y, face_norm);
3723 
3724  double dot = ON_DotProduct(brep_norm, face_norm);
3725  bool same_direction = false;
3726  if (dot > 0) {
3727  // normals appear to have same direction
3728  same_direction = true;
3729  }
3730 
3731  if ((operation == BOOLEAN_UNION && same_direction) ||
3732  (operation == BOOLEAN_INTERSECT && same_direction) ||
3733  (operation == BOOLEAN_DIFF && !same_direction && i < face_count1))
3734  {
3735  splitted[j]->m_belong_to_final = TrimmedFace::BELONG;
3736  }
3737  }
3738  // TODO: Actually only one of them is needed in the final brep structure
3739  }
3740  if (DEBUG_BREP_BOOLEAN) {
3741  bu_log("The trimmed face is %s the other brep.",
3742  (face_location == INSIDE_BREP) ? "inside" :
3743  ((face_location == OUTSIDE_BREP) ? "outside" : "on the surface of"));
3744  }
3745  }
3746  }
3747 }
3748 
3749 HIDDEN ON_ClassArray<ON_SimpleArray<TrimmedFace *> >
3750 get_evaluated_faces(const ON_Brep *brep1, const ON_Brep *brep2, op_type operation)
3751 {
3752  ON_SimpleArray<Subsurface *> surf_tree1, surf_tree2;
3753 
3754  ON_ClassArray<ON_SimpleArray<SSICurve> > curves_array =
3755  get_face_intersection_curves(surf_tree1, surf_tree2, brep1, brep2, operation);
3756 
3757  int face_count1 = brep1->m_F.Count();
3758  int face_count2 = brep2->m_F.Count();
3759 
3760  ON_SimpleArray<TrimmedFace *> brep1_faces, brep2_faces;
3761  brep1_faces = get_trimmed_faces(brep1);
3762  brep2_faces = get_trimmed_faces(brep2);
3763 
3764  ON_SimpleArray<TrimmedFace *> original_faces = brep1_faces;
3765  for (int i = 0; i < brep2_faces.Count(); ++i) {
3766  original_faces.Append(brep2_faces[i]);
3767  }
3768 
3769  if (original_faces.Count() != face_count1 + face_count2) {
3770  throw GeometryGenerationError("ON_Boolean() Error: TrimmedFace"
3771  " generation failed.\n");
3772  }
3773 
3774  // split the surfaces with the intersection curves
3775  ON_ClassArray<ON_SimpleArray<TrimmedFace *> > trimmed_faces;
3776  for (int i = 0; i < original_faces.Count(); i++) {
3777  TrimmedFace *first = original_faces[i];
3778  ON_ClassArray<LinkedCurve> linked_curves = link_curves(curves_array[i]);
3779 
3780  ON_SimpleArray<TrimmedFace *> splitted = split_trimmed_face(first, linked_curves);
3781  trimmed_faces.Append(splitted);
3782 
3783  // Delete the curves passed in.
3784  // Only the copies of them will be used later.
3785  for (int j = 0; j < linked_curves.Count(); j++) {
3786  for (int k = 0; k < linked_curves[j].m_ssi_curves.Count(); k++) {
3787  if (linked_curves[j].m_ssi_curves[k].m_curve) {
3788  delete linked_curves[j].m_ssi_curves[k].m_curve;
3789  linked_curves[j].m_ssi_curves[k].m_curve = NULL;
3790  }
3791  }
3792  }
3793  }
3794 
3795  if (trimmed_faces.Count() != original_faces.Count()) {
3796  throw GeometryGenerationError("ON_Boolean() Error: "
3797  "trimmed_faces.Count() != original_faces.Count()\n");
3798  }
3799 
3800  for (int i = 0; i < original_faces.Count(); i++) {
3801  delete original_faces[i];
3802  original_faces[i] = NULL;
3803  }
3804 
3805  categorize_trimmed_faces(trimmed_faces, brep1, brep2, surf_tree1, surf_tree2, operation);
3806 
3807  for (int i = 0; i < surf_tree1.Count(); i++) {
3808  delete surf_tree1[i];
3809  }
3810 
3811  for (int i = 0; i < surf_tree2.Count(); i++) {
3812  delete surf_tree2[i];
3813  }
3814 
3815  return trimmed_faces;
3816 }
3817 
3818 HIDDEN void
3820 {
3821  std::map<int, int> reversed_curve2d, reversed_edge;
3822  for (int face_idx = 0; face_idx < brep->m_F.Count(); ++face_idx) {
3823  const ON_BrepFace &eb_face = brep->m_F[face_idx];
3824 
3825  for (int loop_idx = 0; loop_idx < eb_face.LoopCount(); ++loop_idx) {
3826  const ON_BrepLoop &face_loop = brep->m_L[eb_face.m_li[loop_idx]];
3827  if (face_loop.m_type != ON_BrepLoop::outer &&
3828  face_loop.m_type != ON_BrepLoop::inner) {
3829  continue;
3830  }
3831 
3832  int loop_direction = brep->LoopDirection(face_loop);
3833  if ((loop_direction == LOOP_DIRECTION_CCW && face_loop.m_type == ON_BrepLoop::inner) ||
3834  (loop_direction == LOOP_DIRECTION_CW && face_loop.m_type == ON_BrepLoop::outer))
3835  {
3836  // found reversed loop
3837  int brep_li = eb_face.m_li[loop_idx];
3838  ON_BrepLoop &reversed_loop = brep->m_L[brep_li];
3839 
3840  // reverse all the loop's curves
3841  for (int trim_idx = 0; trim_idx < reversed_loop.TrimCount(); ++trim_idx) {
3842  ON_BrepTrim *trim = reversed_loop.Trim(trim_idx);
3843 
3844  // Replace trim curve2d with a reversed copy.
3845  // We'll use a previously made curve, or else
3846  // make a new one.
3847  if (reversed_curve2d.find(trim->m_c2i) != reversed_curve2d.end()) {
3848  trim->ChangeTrimCurve(reversed_curve2d[trim->m_c2i]);
3849  } else {
3850  ON_Curve *curve_copy = trim->TrimCurveOf()->DuplicateCurve();
3851  int copy_c2i = brep->AddTrimCurve(curve_copy);
3852 
3853  reversed_curve2d[trim->m_c2i] = copy_c2i;
3854 
3855  trim->ChangeTrimCurve(copy_c2i);
3856  trim->Reverse();
3857  }
3858  // Replace trim edge with a reversed copy.
3859  // We'll use a previously made edge, or else
3860  // make a new one.
3861  if (reversed_edge.find(trim->m_ei) != reversed_edge.end()) {
3862  trim->RemoveFromEdge(false, false);
3863  trim->AttachToEdge(reversed_edge[trim->m_ei], trim->m_bRev3d);
3864  } else {
3865  ON_BrepEdge *edge = trim->Edge();
3866  ON_BrepVertex &v_start = *edge->Vertex(0);
3867  ON_BrepVertex &v_end = *edge->Vertex(1);
3868  ON_Interval dom = edge->ProxyCurveDomain();
3869 
3870  ON_Curve *curve_copy = trim->EdgeCurveOf()->DuplicateCurve();
3871  int copy_c3i = brep->AddEdgeCurve(curve_copy);
3872  ON_BrepEdge &edge_copy = brep->NewEdge(v_start,
3873  v_end, copy_c3i, &dom, edge->m_tolerance);
3874 
3875  reversed_edge[trim->m_ei] = copy_c3i;
3876 
3877  trim->RemoveFromEdge(false, false);
3878  trim->AttachToEdge(edge_copy.m_edge_index, trim->m_bRev3d);
3879  trim->Edge()->Reverse();
3880  }
3881  }
3882  // need to reverse the order of trims in the loop
3883  // too so they appear continuous
3884  reversed_loop.m_ti.Reverse();
3885  }
3886  }
3887  }
3888 }
3889 
3890 int
3891 ON_Boolean(ON_Brep *evaluated_brep, const ON_Brep *brep1, const ON_Brep *brep2, op_type operation)
3892 {
3893  ON_ClassArray<ON_SimpleArray<TrimmedFace *> > trimmed_faces;
3894  try {
3895  /* Deal with the trivial cases up front */
3896  if (brep1->BoundingBox().MinimumDistanceTo(brep2->BoundingBox()) > ON_ZERO_TOLERANCE) {
3897  switch (operation) {
3898  case BOOLEAN_UNION:
3899  evaluated_brep->Append(*brep1);
3900  evaluated_brep->Append(*brep2);
3901  break;
3902  case BOOLEAN_DIFF:
3903  evaluated_brep->Append(*brep1);
3904  break;
3905  case BOOLEAN_INTERSECT:
3906  return 0;
3907  break;
3908  default:
3909  throw InvalidBooleanOperation("Error - unknown boolean operation\n");
3910  }
3911  evaluated_brep->ShrinkSurfaces();
3912  evaluated_brep->Compact();
3913  return 0;
3914  }
3915  trimmed_faces = get_evaluated_faces(brep1, brep2, operation);
3916  } catch (InvalidBooleanOperation &e) {
3917  bu_log("%s", e.what());
3918  return -1;
3919  } catch (GeometryGenerationError &e) {
3920  bu_log("%s", e.what());
3921  return -1;
3922  }
3923 
3924  int face_count1 = brep1->m_F.Count();
3925  int face_count2 = brep2->m_F.Count();
3926  for (int i = 0; i < trimmed_faces.Count(); i++) {
3927  const ON_SimpleArray<TrimmedFace *> &splitted = trimmed_faces[i];
3928  const ON_Surface *surf = splitted.Count() ? splitted[0]->m_face->SurfaceOf() : NULL;
3929  bool added = false;
3930  for (int j = 0; j < splitted.Count(); j++) {
3931  TrimmedFace *t_face = splitted[j];
3932  if (t_face->m_belong_to_final == TrimmedFace::BELONG) {
3933  // Add the surfaces, faces, loops, trims, vertices, edges, etc.
3934  // to the brep structure.
3935  if (!added) {
3936  ON_Surface *new_surf = surf->Duplicate();
3937  evaluated_brep->AddSurface(new_surf);
3938  added = true;
3939  }
3940  ON_BrepFace &new_face = evaluated_brep->NewFace(evaluated_brep->m_S.Count() - 1);
3941 
3942  add_elements(evaluated_brep, new_face, t_face->m_outerloop, ON_BrepLoop::outer);
3943  // ON_BrepLoop &loop = evaluated_brep->m_L[evaluated_brep->m_L.Count() - 1];
3944  for (unsigned int k = 0; k < t_face->m_innerloop.size(); k++) {
3945  add_elements(evaluated_brep, new_face, t_face->m_innerloop[k], ON_BrepLoop::inner);
3946  }
3947 
3948  evaluated_brep->SetTrimIsoFlags(new_face);
3949  const ON_BrepFace &original_face = i >= face_count1 ? brep2->m_F[i - face_count1] : brep1->m_F[i];
3950  if (original_face.m_bRev ^ t_face->m_rev) {
3951  evaluated_brep->FlipFace(new_face);
3952  }
3953  }
3954  }
3955  }
3956 
3957  for (int i = 0; i < face_count1 + face_count2; i++) {
3958  for (int j = 0; j < trimmed_faces[i].Count(); j++) {
3959  if (trimmed_faces[i][j]) {
3960  delete trimmed_faces[i][j];
3961  trimmed_faces[i][j] = NULL;
3962  }
3963  }
3964  }
3965 
3966  evaluated_brep->ShrinkSurfaces();
3967  evaluated_brep->Compact();
3968  standardize_loop_orientations(evaluated_brep);
3969 
3970  // Check IsValid() and output the message.
3971  ON_wString ws;
3972  ON_TextLog log(ws);
3973  evaluated_brep->IsValid(&log);
3974  if (ON_String(ws).Array()) {
3975  bu_log("%s", ON_String(ws).Array());
3976  }
3977 
3978  return 0;
3979 }
3980 
3981 
3982 // Local Variables:
3983 // tab-width: 8
3984 // mode: C++
3985 // c-basic-offset: 4
3986 // indent-tabs-mode: t
3987 // c-file-style: "stroustrup"
3988 // End:
3989 // ex: shiftwidth=4 tabstop=8
int source_loop
Definition: boolean.cpp:1465
bool ON_Intersect(const ON_3dPoint &pointA, const ON_3dPoint &pointB, ON_ClassArray< ON_PX_EVENT > &x, double tol)
Definition: intersect.cpp:647
HIDDEN std::multiset< CurveSegment > get_op_segments(std::multiset< CurveSegment > &curve1_segments, std::multiset< CurveSegment > &curve2_segments, op_type op)
Definition: boolean.cpp:1886
CurveSegment(ON_SimpleArray< ON_Curve * > &loop, CurvePoint f, CurvePoint t, CurveSegment::Location l)
Definition: boolean.cpp:1571
void bu_log(const char *,...) _BU_ATTR_PRINTF12
Definition: log.c:176
#define LOOP_DIRECTION_NONE
Definition: boolean.cpp:1677
HIDDEN IntervalPoints points_uv_to_3d(const IntervalPoints &interval_uv, const ON_Surface *surf)
Definition: boolean.cpp:843
HIDDEN std::vector< ON_Interval > interval_2d_to_3d(const ON_Interval &interval, const ON_Curve *curve2d, const ON_Curve *curve3d, const ON_Surface *surf)
Definition: boolean.cpp:879
ON_3dPoint mid
Definition: boolean.cpp:648
HIDDEN int loop_t_compare(const IntersectPoint *p1, const IntersectPoint *p2)
Definition: boolean.cpp:320
HIDDEN bool is_point_on_loop(const ON_2dPoint &pt, const ON_SimpleArray< ON_Curve * > &loop)
Definition: boolean.cpp:485
HIDDEN ON_ClassArray< LinkedCurve > get_joinable_ssi_curves(const ON_SimpleArray< SSICurve > &in)
Definition: boolean.cpp:1262
SSICurve(ON_Curve *curve)
Definition: boolean.cpp:83
const ON_Curve * Curve()
Definition: boolean.cpp:205
HIDDEN void append_faces_from_loops(ON_SimpleArray< TrimmedFace * > &out, const TrimmedFace *orig_face, const LoopBooleanResult &new_loops)
Definition: boolean.cpp:2380
if lu s
Definition: nmg_mod.c:3860
void Append(const LinkedCurve &lc)
Definition: boolean.cpp:188
bool set_loop_direction(ON_SimpleArray< ON_Curve * > &loop, int dir)
Definition: boolean.cpp:1735
HIDDEN ON_SimpleArray< ON_Curve * > get_face_trim_loop(const ON_Brep *brep, int face_loop_index)
Definition: boolean.cpp:3595
HIDDEN void standardize_loop_orientations(ON_Brep *brep)
Definition: boolean.cpp:3819
bool operator<(const CurveSegment &other) const
Definition: boolean.cpp:1648
Definition: nmg_tri.c:75
std::vector< ON_SimpleArray< ON_Curve * > > split_face_into_loops(const TrimmedFace *orig_face, LinkedCurve &linked_curve)
Definition: boolean.cpp:2401
void AppendCurvesToArray(ON_SimpleArray< ON_Curve * > &arr) const
Definition: boolean.cpp:198
HIDDEN void close_small_gaps(ON_SimpleArray< ON_Curve * > &loop)
Definition: boolean.cpp:1695
Definition: raytrace.h:368
const ON_Interval Domain()
Definition: boolean.cpp:230
const ON_BrepFace * m_face
Definition: boolean.cpp:260
std::vector< ON_SimpleArray< ON_Curve * > > outerloops
Definition: boolean.cpp:1656
HIDDEN bool is_point_on_brep_surface(const ON_3dPoint &pt, const ON_Brep *brep, ON_SimpleArray< Subsurface * > &surf_tree)
Definition: boolean.cpp:3165
enum IntersectPoint::@4 m_dir
HIDDEN ON_ClassArray< ON_SimpleArray< TrimmedFace * > > get_evaluated_faces(const ON_Brep *brep1, const ON_Brep *brep2, op_type operation)
Definition: boolean.cpp:3750
Header file for the BRL-CAD common definitions.
HIDDEN IntervalParams points_3d_to_params_3d(const IntervalPoints &pts_3d, const ON_Curve *curve3d)
Definition: boolean.cpp:857
TrimmedFace * make_face_from_loops(const TrimmedFace *orig_face, const ON_SimpleArray< ON_Curve * > &outerloop, const std::vector< ON_SimpleArray< ON_Curve * > > &innerloops)
Definition: boolean.cpp:2240
enum TrimmedFace::@5 m_belong_to_final
std::list< ON_SimpleArray< ON_Curve * > > innerloops_inside_outerloop(const ON_SimpleArray< ON_Curve * > &outerloop_curve, const std::vector< ON_SimpleArray< ON_Curve * > > &innerloop_curves)
Definition: boolean.cpp:2217
int IsAtSeam(const ON_Surface *surf, int dir, double u, double v, double tol)
double m_curve_t
Definition: boolean.cpp:60
TrimmedFace * Duplicate() const
Definition: boolean.cpp:298
#define MAX_FASTF
Definition: defines.h:340
#define LOOP_DIRECTION_CCW
Definition: boolean.cpp:1675
#define HIDDEN
Definition: common.h:86
HIDDEN bool is_point_inside_loop(const ON_2dPoint &pt, const ON_SimpleArray< ON_Curve * > &loop)
Definition: boolean.cpp:503
HIDDEN int curve_t_compare(const IntersectPoint *p1, const IntersectPoint *p2)
Definition: boolean.cpp:331
HIDDEN int point_loop_location(const ON_2dPoint &pt, const ON_SimpleArray< ON_Curve * > &loop)
Definition: boolean.cpp:429
std::multiset< CurveSegment > make_segments(std::multiset< CurvePoint > &curve1_points, ON_SimpleArray< ON_Curve * > &loop1, ON_SimpleArray< ON_Curve * > &loop2)
Definition: boolean.cpp:1767
void set_append_segments_at_location(std::multiset< CurveSegment > &out, std::multiset< CurveSegment > &in, CurveSegment::Location location, bool reversed_segs_cancel)
Definition: boolean.cpp:1845
CurvePoint(int loop, int li, double pt_t, ON_Curve *curve, const ON_SimpleArray< ON_Curve * > &other_loop)
Definition: boolean.cpp:1479
std::list< ON_SimpleArray< ON_Curve * > >::iterator find_innerloop(std::list< ON_SimpleArray< ON_Curve * > > &loops)
Definition: boolean.cpp:1719
#define ANGLE_TOL
Definition: boolean.cpp:52
std::list< ON_SimpleArray< ON_Curve * > > construct_loops_from_segments(std::multiset< CurveSegment > &segments)
Definition: boolean.cpp:1983
#define DEBUG_BREP_BOOLEAN
Definition: boolean.cpp:44
void free_loops(std::vector< ON_SimpleArray< ON_Curve * > > &loops)
Definition: boolean.cpp:2722
bool IsValid() const
Definition: boolean.cpp:163
HIDDEN double bbox_diagonal_length(ON_Curve *curve)
Definition: boolean.cpp:1189
HIDDEN void categorize_trimmed_faces(ON_ClassArray< ON_SimpleArray< TrimmedFace * > > &trimmed_faces, const ON_Brep *brep1, const ON_Brep *brep2, ON_SimpleArray< Subsurface * > &surf_tree1, ON_SimpleArray< Subsurface * > &surf_tree2, op_type operation)
Definition: boolean.cpp:3633
SSICurve * Duplicate() const
Definition: boolean.cpp:88
ON_Curve * Curve(void) const
Definition: boolean.cpp:1587
const ON_3dPoint PointAt(double t)
Definition: boolean.cpp:221
HIDDEN bool close_small_gap(ON_SimpleArray< ON_Curve * > &loop, int curr, int next)
Definition: boolean.cpp:1680
ON_3dPoint max
Definition: boolean.cpp:649
HIDDEN void replace_curve_with_subcurve(ON_Curve *&curve, const ON_Interval &interval)
Definition: boolean.cpp:538
ON_3dPoint PointAtEnd() const
Definition: boolean.cpp:146
ON_Curve * get_loop_curve(const ON_SimpleArray< ON_Curve * > &loop)
Definition: boolean.cpp:1709
ON_Curve * SubCurve(double t1, double t2)
Definition: boolean.cpp:239
double m_seg_t
Definition: boolean.cpp:56
void Append(const SSICurve &sc)
Definition: boolean.cpp:193
void MakeIncreasing(void)
Definition: boolean.cpp:659
CurvePoint to
Definition: boolean.cpp:1564
bool operator!=(const CurvePoint &other) const
Definition: boolean.cpp:1529
LinkedCurve & operator=(const LinkedCurve &_lc)
Definition: boolean.cpp:129
ON_3dPoint PointAtStart() const
Definition: boolean.cpp:137
std::multiset< CurveSegment > find_similar_segments(std::multiset< CurveSegment > &set, const CurveSegment &seg)
Definition: boolean.cpp:1868
CurvePoint(int loop, int li, double t, ON_2dPoint p, CurvePoint::Location l)
Definition: boolean.cpp:1491
HIDDEN LoopBooleanResult combine_loops(const TrimmedFace *orig_face, const LoopBooleanResult &new_loops)
Definition: boolean.cpp:2264
Definition: human.c:197
bool Reverse()
Definition: boolean.cpp:175
goto out
Definition: nmg_mod.c:3846
ON_SimpleArray< ON_X_EVENT > events
Definition: boolean.cpp:1258
CurvePoint from
Definition: boolean.cpp:1564
HIDDEN ON_ClassArray< ON_SimpleArray< SSICurve > > get_face_intersection_curves(ON_SimpleArray< Subsurface * > &surf_tree1, ON_SimpleArray< Subsurface * > &surf_tree2, const ON_Brep *brep1, const ON_Brep *brep2, op_type operation)
Definition: boolean.cpp:3408
HIDDEN IntervalPoints interval_2d_to_uv(const ON_Interval &interval_2d, const ON_Curve *curve2d, const ON_Surface *surf)
Definition: boolean.cpp:810
HIDDEN ON_SimpleArray< TrimmedFace * > split_trimmed_face(const TrimmedFace *orig_face, ON_ClassArray< LinkedCurve > &ssx_curves)
Definition: boolean.cpp:2786
HIDDEN ON_Interval interval_3d_to_2d(const ON_Interval &interval, const ON_Curve *curve2d, const ON_Curve *curve3d, const ON_BrepFace *face)
Definition: boolean.cpp:1011
void set_append_segment(std::multiset< CurveSegment > &out, const CurveSegment &seg)
Definition: boolean.cpp:1822
HIDDEN ON_Interval intersect_intervals(const ON_Interval &interval1, const ON_Interval &interval2)
Definition: boolean.cpp:528
void ClearInnerloops()
Definition: boolean.cpp:1666
HIDDEN ON_SimpleArray< ON_Interval > get_curve_intervals_inside_or_on_face(ON_Curve *curve2D, const ON_ClassArray< ON_SimpleArray< ON_Curve * > > &face_loops, double isect_tol)
Definition: boolean.cpp:551
bool IsDegenerate(void)
Definition: boolean.cpp:1623
std::vector< ON_SimpleArray< ON_Curve * > > innerloops
Definition: boolean.cpp:1657
HIDDEN void get_subcurves_inside_faces(ON_SimpleArray< ON_Curve * > &subcurves_on1, ON_SimpleArray< ON_Curve * > &subcurves_on2, const ON_Brep *brep1, const ON_Brep *brep2, int face_i1, int face_i2, ON_SSX_EVENT *event)
Definition: boolean.cpp:1070
enum CurvePoint::Location location
HIDDEN std::pair< IntervalPoints, IntervalPoints > interval_2d_to_2uv(const ON_Interval &interval_2d, const ON_Curve *curve2d, const ON_Surface *surf, double split_t)
Definition: boolean.cpp:825
ON_3dPoint m_pt
Definition: boolean.cpp:55
#define INTERSECTION_TOL
Definition: boolean.cpp:48
ON_Curve * sub_curve(const ON_Curve *in, double a, double b)
Definition: intersect.cpp:220
HIDDEN void split_curve(ON_Curve *&left, ON_Curve *&right, const ON_Curve *in, double t)
Definition: boolean.cpp:1204
bool m_rev
Definition: boolean.cpp:266
HIDDEN void append_to_polycurve(ON_Curve *curve, ON_PolyCurve &polycurve)
Definition: boolean.cpp:339
HIDDEN int compare_interval(const ON_Interval *a, const ON_Interval *b)
Definition: boolean.cpp:641
LoopBooleanResult loop_boolean(const ON_SimpleArray< ON_Curve * > &l1, const ON_SimpleArray< ON_Curve * > &l2, op_type op)
Definition: boolean.cpp:2108
SSICurve()
Definition: boolean.cpp:78
#define LOOP_DIRECTION_CW
Definition: boolean.cpp:1676
void Reverse(void)
Definition: boolean.cpp:1581
HIDDEN IntervalPoints uv_interval_from_points(IntervalPoints interval_pts, const ON_Surface *surf)
Definition: boolean.cpp:725
HIDDEN LoopBooleanResult make_result_from_loops(const std::list< ON_SimpleArray< ON_Curve * > > &loops)
Definition: boolean.cpp:2077
ON_2dPoint pt
Definition: boolean.cpp:1468
HIDDEN bool is_same_surface(const ON_Surface *surf1, const ON_Surface *surf2)
Definition: boolean.cpp:2910
HIDDEN ON_Interval union_intervals(const ON_SimpleArray< ON_Interval > &intervals)
Definition: boolean.cpp:515
ON_Curve * m_curve
Definition: boolean.cpp:76
bool operator==(const CurvePoint &other) const
Definition: boolean.cpp:1523
bool operator()(const CurvePoint &a, const CurvePoint &b) const
Definition: boolean.cpp:1538
void add_point_to_set(std::multiset< CurvePoint > &set, CurvePoint pt)
Definition: boolean.cpp:1759
HIDDEN bool is_point_outside_loop(const ON_2dPoint &pt, const ON_SimpleArray< ON_Curve * > &loop)
Definition: boolean.cpp:509
HIDDEN IntervalParams curve_interval_from_params(IntervalParams interval_t, const ON_Curve *curve)
Definition: boolean.cpp:678
HIDDEN bool is_loop_valid(const ON_SimpleArray< ON_Curve * > &loop, double tolerance, ON_PolyCurve *polycurve=NULL)
Definition: boolean.cpp:359
HIDDEN bool is_point_inside_trimmed_face(const ON_2dPoint &pt, const TrimmedFace *tface)
Definition: boolean.cpp:3299
static CurvePoint::Location PointLoopLocation(ON_2dPoint pt, const ON_SimpleArray< ON_Curve * > &loop)
Definition: boolean.cpp:1548
double curve_t
Definition: boolean.cpp:1467
HIDDEN bool is_point_inside_brep(const ON_3dPoint &pt, const ON_Brep *brep, ON_SimpleArray< Subsurface * > &surf_tree)
Definition: boolean.cpp:3217
int ON_Boolean(ON_Brep *evaluated_brep, const ON_Brep *brep1, const ON_Brep *brep2, op_type operation)
Definition: boolean.cpp:3891
HIDDEN double configure_for_linking(LinkedCurve *&first, LinkedCurve *&second, LinkedCurve &in1, LinkedCurve &in2)
Definition: boolean.cpp:1219
std::vector< ON_SimpleArray< ON_Curve * > > m_innerloop
Definition: boolean.cpp:259
seam_location
Definition: boolean.cpp:718
void Empty()
Definition: boolean.cpp:117
ON_SimpleArray< ON_Curve * > m_outerloop
Definition: boolean.cpp:257
HIDDEN ON_ClassArray< LinkedCurve > link_curves(const ON_SimpleArray< SSICurve > &in)
Definition: boolean.cpp:1403
int loop_index
Definition: boolean.cpp:1466
bool IsClosed() const
Definition: boolean.cpp:155
HIDDEN void add_elements(ON_Brep *brep, ON_BrepFace &face, const ON_SimpleArray< ON_Curve * > &loop, ON_BrepLoop::TYPE loop_type)
Definition: boolean.cpp:2986
double fastf_t
Definition: defines.h:300
ON_SimpleArray< ON_Curve * > orig_loop
Definition: boolean.cpp:1563
ON_SimpleArray< SSICurve > m_ssi_curves
Definition: boolean.cpp:109
ON_3dPoint min
Definition: boolean.cpp:647
bool loop_is_degenerate(const ON_SimpleArray< ON_Curve * > &loop)
Definition: boolean.cpp:2733
std::multiset< CurvePoint > get_loop_points(int source_loop, ON_SimpleArray< ON_Curve * > loop1, ON_SimpleArray< ON_Curve * > loop2)
Definition: boolean.cpp:2055
enum CurveSegment::Location location
bool operator<(const CurvePoint &other) const
Definition: boolean.cpp:1502
HIDDEN int face_brep_location(const TrimmedFace *tface, const ON_Brep *brep, ON_SimpleArray< Subsurface * > &surf_tree)
Definition: boolean.cpp:3364
void ClearOuterloops()
Definition: boolean.cpp:1659
HIDDEN ON_2dPoint get_point_inside_trimmed_face(const TrimmedFace *tface)
Definition: boolean.cpp:3319
bool ON_NearZero(double val, double epsilon)
Return truthfully whether a value is within a specified epsilon distance from zero.
HIDDEN ON_SimpleArray< TrimmedFace * > get_trimmed_faces(const ON_Brep *brep)
Definition: boolean.cpp:3608