1 //-----------------------------------------------------------------------------
2 // Anything involving curves and sets of curves (except for the real math,
3 // which is in ratpoly.cpp).
4 //
5 // Copyright 2008-2013 Jonathan Westhues.
6 //-----------------------------------------------------------------------------
7 #include "../solvespace.h"
8
From(Vector4 p0,Vector4 p1)9 SBezier SBezier::From(Vector4 p0, Vector4 p1) {
10 SBezier ret = {};
11 ret.deg = 1;
12 ret.weight[0] = p0.w;
13 ret.ctrl [0] = p0.PerspectiveProject();
14 ret.weight[1] = p1.w;
15 ret.ctrl [1] = p1.PerspectiveProject();
16 return ret;
17 }
18
From(Vector4 p0,Vector4 p1,Vector4 p2)19 SBezier SBezier::From(Vector4 p0, Vector4 p1, Vector4 p2) {
20 SBezier ret = {};
21 ret.deg = 2;
22 ret.weight[0] = p0.w;
23 ret.ctrl [0] = p0.PerspectiveProject();
24 ret.weight[1] = p1.w;
25 ret.ctrl [1] = p1.PerspectiveProject();
26 ret.weight[2] = p2.w;
27 ret.ctrl [2] = p2.PerspectiveProject();
28 return ret;
29 }
30
From(Vector4 p0,Vector4 p1,Vector4 p2,Vector4 p3)31 SBezier SBezier::From(Vector4 p0, Vector4 p1, Vector4 p2, Vector4 p3) {
32 SBezier ret = {};
33 ret.deg = 3;
34 ret.weight[0] = p0.w;
35 ret.ctrl [0] = p0.PerspectiveProject();
36 ret.weight[1] = p1.w;
37 ret.ctrl [1] = p1.PerspectiveProject();
38 ret.weight[2] = p2.w;
39 ret.ctrl [2] = p2.PerspectiveProject();
40 ret.weight[3] = p3.w;
41 ret.ctrl [3] = p3.PerspectiveProject();
42 return ret;
43 }
44
From(Vector p0,Vector p1)45 SBezier SBezier::From(Vector p0, Vector p1) {
46 return SBezier::From(p0.Project4d(),
47 p1.Project4d());
48 }
49
From(Vector p0,Vector p1,Vector p2)50 SBezier SBezier::From(Vector p0, Vector p1, Vector p2) {
51 return SBezier::From(p0.Project4d(),
52 p1.Project4d(),
53 p2.Project4d());
54 }
55
From(Vector p0,Vector p1,Vector p2,Vector p3)56 SBezier SBezier::From(Vector p0, Vector p1, Vector p2, Vector p3) {
57 return SBezier::From(p0.Project4d(),
58 p1.Project4d(),
59 p2.Project4d(),
60 p3.Project4d());
61 }
62
Start(void)63 Vector SBezier::Start(void) {
64 return ctrl[0];
65 }
66
Finish(void)67 Vector SBezier::Finish(void) {
68 return ctrl[deg];
69 }
70
Reverse(void)71 void SBezier::Reverse(void) {
72 int i;
73 for(i = 0; i < (deg+1)/2; i++) {
74 swap(ctrl[i], ctrl[deg-i]);
75 swap(weight[i], weight[deg-i]);
76 }
77 }
78
ScaleSelfBy(double s)79 void SBezier::ScaleSelfBy(double s) {
80 int i;
81 for(i = 0; i <= deg; i++) {
82 ctrl[i] = ctrl[i].ScaledBy(s);
83 }
84 }
85
GetBoundingProjd(Vector u,Vector orig,double * umin,double * umax)86 void SBezier::GetBoundingProjd(Vector u, Vector orig,
87 double *umin, double *umax)
88 {
89 int i;
90 for(i = 0; i <= deg; i++) {
91 double ut = ((ctrl[i]).Minus(orig)).Dot(u);
92 if(ut < *umin) *umin = ut;
93 if(ut > *umax) *umax = ut;
94 }
95 }
96
TransformedBy(Vector t,Quaternion q,double scale)97 SBezier SBezier::TransformedBy(Vector t, Quaternion q, double scale) {
98 SBezier ret = *this;
99 int i;
100 for(i = 0; i <= deg; i++) {
101 ret.ctrl[i] = (ret.ctrl[i]).ScaledBy(scale);
102 ret.ctrl[i] = (q.Rotate(ret.ctrl[i])).Plus(t);
103 }
104 return ret;
105 }
106
107 //-----------------------------------------------------------------------------
108 // Does this curve lie entirely within the specified plane? It does if all
109 // the control points lie in that plane.
110 //-----------------------------------------------------------------------------
IsInPlane(Vector n,double d)111 bool SBezier::IsInPlane(Vector n, double d) {
112 int i;
113 for(i = 0; i <= deg; i++) {
114 if(fabs((ctrl[i]).Dot(n) - d) > LENGTH_EPS) {
115 return false;
116 }
117 }
118 return true;
119 }
120
121 //-----------------------------------------------------------------------------
122 // Is this Bezier exactly the arc of a circle, projected along the specified
123 // axis? If yes, return that circle's center and radius.
124 //-----------------------------------------------------------------------------
IsCircle(Vector axis,Vector * center,double * r)125 bool SBezier::IsCircle(Vector axis, Vector *center, double *r) {
126 if(deg != 2) return false;
127
128 if(ctrl[1].DistanceToLine(ctrl[0], ctrl[2].Minus(ctrl[0])) < LENGTH_EPS) {
129 // This is almost a line segment. So it's a circle with very large
130 // radius, which is likely to make code that tries to handle circles
131 // blow up. So return false.
132 return false;
133 }
134
135 Vector t0 = (ctrl[0]).Minus(ctrl[1]),
136 t2 = (ctrl[2]).Minus(ctrl[1]),
137 r0 = axis.Cross(t0),
138 r2 = axis.Cross(t2);
139
140 *center = Vector::AtIntersectionOfLines(ctrl[0], (ctrl[0]).Plus(r0),
141 ctrl[2], (ctrl[2]).Plus(r2),
142 NULL, NULL, NULL);
143
144 double rd0 = center->Minus(ctrl[0]).Magnitude(),
145 rd2 = center->Minus(ctrl[2]).Magnitude();
146 if(fabs(rd0 - rd2) > LENGTH_EPS) {
147 return false;
148 }
149 *r = rd0;
150
151 Vector u = r0.WithMagnitude(1),
152 v = (axis.Cross(u)).WithMagnitude(1);
153 Point2d c2 = center->Project2d(u, v),
154 pa2 = (ctrl[0]).Project2d(u, v).Minus(c2),
155 pb2 = (ctrl[2]).Project2d(u, v).Minus(c2);
156
157 double thetaa = atan2(pa2.y, pa2.x), // in fact always zero due to csys
158 thetab = atan2(pb2.y, pb2.x),
159 dtheta = WRAP_NOT_0(thetab - thetaa, 2*PI);
160 if(dtheta > PI) {
161 // Not possible with a second order Bezier arc; so we must have
162 // the points backwards.
163 dtheta = 2*PI - dtheta;
164 }
165
166 if(fabs(weight[1] - cos(dtheta/2)) > LENGTH_EPS) {
167 return false;
168 }
169
170 return true;
171 }
172
IsRational(void)173 bool SBezier::IsRational(void) {
174 int i;
175 for(i = 0; i <= deg; i++) {
176 if(fabs(weight[i] - 1) > LENGTH_EPS) return true;
177 }
178 return false;
179 }
180
181 //-----------------------------------------------------------------------------
182 // Apply a perspective transformation to a rational Bezier curve, calculating
183 // the new weights as required.
184 //-----------------------------------------------------------------------------
InPerspective(Vector u,Vector v,Vector n,Vector origin,double cameraTan)185 SBezier SBezier::InPerspective(Vector u, Vector v, Vector n,
186 Vector origin, double cameraTan)
187 {
188 Quaternion q = Quaternion::From(u, v);
189 q = q.Inverse();
190 // we want Q*(p - o) = Q*p - Q*o
191 SBezier ret = this->TransformedBy(q.Rotate(origin).ScaledBy(-1), q, 1.0);
192 int i;
193 for(i = 0; i <= deg; i++) {
194 Vector4 ct = Vector4::From(ret.weight[i], ret.ctrl[i]);
195 // so the desired curve, before perspective, is
196 // (x/w, y/w, z/w)
197 // and after perspective is
198 // ((x/w)/(1 - (z/w)*cameraTan, ...
199 // = (x/(w - z*cameraTan), ...
200 // so we want to let w' = w - z*cameraTan
201 ct.w = ct.w - ct.z*cameraTan;
202
203 ret.ctrl[i] = ct.PerspectiveProject();
204 ret.weight[i] = ct.w;
205 }
206 return ret;
207 }
208
Equals(SBezier * b)209 bool SBezier::Equals(SBezier *b) {
210 // We just test of identical degree and control points, even though two
211 // curves could still be coincident (even sharing endpoints).
212 if(deg != b->deg) return false;
213 int i;
214 for(i = 0; i <= deg; i++) {
215 if(!(ctrl[i]).Equals(b->ctrl[i])) return false;
216 if(fabs(weight[i] - b->weight[i]) > LENGTH_EPS) return false;
217 }
218 return true;
219 }
220
Clear(void)221 void SBezierList::Clear(void) {
222 l.Clear();
223 }
224
ScaleSelfBy(double s)225 void SBezierList::ScaleSelfBy(double s) {
226 SBezier *sb;
227 for(sb = l.First(); sb; sb = l.NextAfter(sb)) {
228 sb->ScaleSelfBy(s);
229 }
230 }
231
232 //-----------------------------------------------------------------------------
233 // If our list contains multiple identical Beziers (in either forward or
234 // reverse order), then cull them.
235 //-----------------------------------------------------------------------------
CullIdenticalBeziers(void)236 void SBezierList::CullIdenticalBeziers(void) {
237 int i, j;
238
239 l.ClearTags();
240 for(i = 0; i < l.n; i++) {
241 SBezier *bi = &(l.elem[i]), bir;
242 bir = *bi;
243 bir.Reverse();
244
245 for(j = i + 1; j < l.n; j++) {
246 SBezier *bj = &(l.elem[j]);
247 if(bj->Equals(bi) ||
248 bj->Equals(&bir))
249 {
250 bi->tag = 1;
251 bj->tag = 1;
252 }
253 }
254 }
255 l.RemoveTagged();
256 }
257
258 //-----------------------------------------------------------------------------
259 // Find all the points where a list of Bezier curves intersects another list
260 // of Bezier curves. We do this by intersecting their piecewise linearizations,
261 // and then refining any intersections that we find to lie exactly on the
262 // curves. So this will screw up on tangencies and stuff, but otherwise should
263 // be fine.
264 //-----------------------------------------------------------------------------
AllIntersectionsWith(SBezierList * sblb,SPointList * spl)265 void SBezierList::AllIntersectionsWith(SBezierList *sblb, SPointList *spl) {
266 SBezier *sba, *sbb;
267 for(sba = l.First(); sba; sba = l.NextAfter(sba)) {
268 for(sbb = sblb->l.First(); sbb; sbb = sblb->l.NextAfter(sbb)) {
269 sbb->AllIntersectionsWith(sba, spl);
270 }
271 }
272 }
AllIntersectionsWith(SBezier * sbb,SPointList * spl)273 void SBezier::AllIntersectionsWith(SBezier *sbb, SPointList *spl) {
274 SPointList splRaw = {};
275 SEdgeList sea, seb;
276 sea = {};
277 seb = {};
278 this->MakePwlInto(&sea);
279 sbb ->MakePwlInto(&seb);
280 SEdge *se;
281 for(se = sea.l.First(); se; se = sea.l.NextAfter(se)) {
282 // This isn't quite correct, since AnyEdgeCrossings doesn't count
283 // the case where two pairs of line segments intersect at their
284 // vertices. So this isn't robust, although that case isn't very
285 // likely.
286 seb.AnyEdgeCrossings(se->a, se->b, NULL, &splRaw);
287 }
288 SPoint *sp;
289 for(sp = splRaw.l.First(); sp; sp = splRaw.l.NextAfter(sp)) {
290 Vector p = sp->p;
291 if(PointOnThisAndCurve(sbb, &p)) {
292 if(!spl->ContainsPoint(p)) spl->Add(p);
293 }
294 }
295 sea.Clear();
296 seb.Clear();
297 splRaw.Clear();
298 }
299
300 //-----------------------------------------------------------------------------
301 // Find a plane that contains all of the curves in this list. If the curves
302 // are all colinear (or coincident, or empty), then that plane is not exactly
303 // determined but we choose the additional degree(s) of freedom arbitrarily.
304 // Returns true if all the curves are coplanar, otherwise false.
305 //-----------------------------------------------------------------------------
GetPlaneContainingBeziers(Vector * p,Vector * u,Vector * v,Vector * notCoplanarAt)306 bool SBezierList::GetPlaneContainingBeziers(Vector *p, Vector *u, Vector *v,
307 Vector *notCoplanarAt)
308 {
309 Vector pt, ptFar, ptOffLine, dp, n;
310 double farMax, offLineMax;
311 int i;
312 SBezier *sb;
313
314 // Get any point on any Bezier; or an arbitrary point if list is empty.
315 if(l.n > 0) {
316 pt = l.elem[0].Start();
317 } else {
318 pt = Vector::From(0, 0, 0);
319 }
320 ptFar = ptOffLine = pt;
321
322 // Get the point farthest from our arbitrary point.
323 farMax = VERY_NEGATIVE;
324 for(sb = l.First(); sb; sb = l.NextAfter(sb)) {
325 for(i = 0; i <= sb->deg; i++) {
326 double m = (pt.Minus(sb->ctrl[i])).Magnitude();
327 if(m > farMax) {
328 ptFar = sb->ctrl[i];
329 farMax = m;
330 }
331 }
332 }
333 if(ptFar.Equals(pt)) {
334 // The points are all coincident. So neither basis vector matters.
335 *p = pt;
336 *u = Vector::From(1, 0, 0);
337 *v = Vector::From(0, 1, 0);
338 return true;
339 }
340
341 // Get the point farthest from the line between pt and ptFar
342 dp = ptFar.Minus(pt);
343 offLineMax = VERY_NEGATIVE;
344 for(sb = l.First(); sb; sb = l.NextAfter(sb)) {
345 for(i = 0; i <= sb->deg; i++) {
346 double m = (sb->ctrl[i]).DistanceToLine(pt, dp);
347 if(m > offLineMax) {
348 ptOffLine = sb->ctrl[i];
349 offLineMax = m;
350 }
351 }
352 }
353
354 *p = pt;
355 if(offLineMax < LENGTH_EPS) {
356 // The points are all colinear; so choose the second basis vector
357 // arbitrarily.
358 *u = (ptFar.Minus(pt)).WithMagnitude(1);
359 *v = (u->Normal(0)).WithMagnitude(1);
360 } else {
361 // The points actually define a plane.
362 n = (ptFar.Minus(pt)).Cross(ptOffLine.Minus(pt));
363 *u = (n.Normal(0)).WithMagnitude(1);
364 *v = (n.Normal(1)).WithMagnitude(1);
365 }
366
367 // So we have a plane; but check whether all of the points lie in that
368 // plane.
369 n = u->Cross(*v);
370 n = n.WithMagnitude(1);
371 double d = p->Dot(n);
372 for(sb = l.First(); sb; sb = l.NextAfter(sb)) {
373 for(i = 0; i <= sb->deg; i++) {
374 if(fabs(n.Dot(sb->ctrl[i]) - d) > LENGTH_EPS) {
375 if(notCoplanarAt) *notCoplanarAt = sb->ctrl[i];
376 return false;
377 }
378 }
379 }
380 return true;
381 }
382
383 //-----------------------------------------------------------------------------
384 // Assemble curves in sbl into a single loop. The curves may appear in any
385 // direction (start to finish, or finish to start), and will be reversed if
386 // necessary. The curves in the returned loop are removed from sbl, even if
387 // the loop cannot be closed.
388 //-----------------------------------------------------------------------------
FromCurves(SBezierList * sbl,bool * allClosed,SEdge * errorAt)389 SBezierLoop SBezierLoop::FromCurves(SBezierList *sbl,
390 bool *allClosed, SEdge *errorAt)
391 {
392 SBezierLoop loop = {};
393
394 if(sbl->l.n < 1) return loop;
395 sbl->l.ClearTags();
396
397 SBezier *first = &(sbl->l.elem[0]);
398 first->tag = 1;
399 loop.l.Add(first);
400 Vector start = first->Start();
401 Vector hanging = first->Finish();
402 int auxA = first->auxA;
403
404 sbl->l.RemoveTagged();
405
406 while(sbl->l.n > 0 && !hanging.Equals(start)) {
407 int i;
408 bool foundNext = false;
409 for(i = 0; i < sbl->l.n; i++) {
410 SBezier *test = &(sbl->l.elem[i]);
411
412 if((test->Finish()).Equals(hanging) && test->auxA == auxA) {
413 test->Reverse();
414 // and let the next test catch it
415 }
416 if((test->Start()).Equals(hanging) && test->auxA == auxA) {
417 test->tag = 1;
418 loop.l.Add(test);
419 hanging = test->Finish();
420 sbl->l.RemoveTagged();
421 foundNext = true;
422 break;
423 }
424 }
425 if(!foundNext) {
426 // The loop completed without finding the hanging edge, so
427 // it's an open loop
428 errorAt->a = hanging;
429 errorAt->b = start;
430 *allClosed = false;
431 return loop;
432 }
433 }
434 if(hanging.Equals(start)) {
435 *allClosed = true;
436 } else {
437 // We ran out of edges without forming a closed loop.
438 errorAt->a = hanging;
439 errorAt->b = start;
440 *allClosed = false;
441 }
442
443 return loop;
444 }
445
Reverse(void)446 void SBezierLoop::Reverse(void) {
447 l.Reverse();
448 SBezier *sb;
449 for(sb = l.First(); sb; sb = l.NextAfter(sb)) {
450 // If we didn't reverse each curve, then the next curve in list would
451 // share your start, not your finish.
452 sb->Reverse();
453 }
454 }
455
GetBoundingProjd(Vector u,Vector orig,double * umin,double * umax)456 void SBezierLoop::GetBoundingProjd(Vector u, Vector orig,
457 double *umin, double *umax)
458 {
459 SBezier *sb;
460 for(sb = l.First(); sb; sb = l.NextAfter(sb)) {
461 sb->GetBoundingProjd(u, orig, umin, umax);
462 }
463 }
464
MakePwlInto(SContour * sc,double chordTol)465 void SBezierLoop::MakePwlInto(SContour *sc, double chordTol) {
466 SBezier *sb;
467 for(sb = l.First(); sb; sb = l.NextAfter(sb)) {
468 sb->MakePwlInto(sc, chordTol);
469 // Avoid double points at join between Beziers; except that
470 // first and last points should be identical.
471 if(l.NextAfter(sb) != NULL) {
472 sc->l.RemoveLast(1);
473 }
474 }
475 // Ensure that it's exactly closed, not just within a numerical tolerance.
476 if((sc->l.elem[sc->l.n - 1].p).Equals(sc->l.elem[0].p)) {
477 sc->l.elem[sc->l.n - 1] = sc->l.elem[0];
478 }
479 }
480
IsClosed(void)481 bool SBezierLoop::IsClosed(void) {
482 if(l.n < 1) return false;
483 Vector s = l.elem[0].Start(),
484 f = l.elem[l.n-1].Finish();
485 return s.Equals(f);
486 }
487
488
489 //-----------------------------------------------------------------------------
490 // Assemble the curves in sbl into multiple loops, and piecewise linearize the
491 // curves into poly. If we can't close a contour, then we add it to
492 // openContours (if that isn't NULL) and keep going; so this works even if the
493 // input contains a mix of open and closed curves.
494 //-----------------------------------------------------------------------------
From(SBezierList * sbl,SPolygon * poly,double chordTol,bool * allClosed,SEdge * errorAt,SBezierList * openContours)495 SBezierLoopSet SBezierLoopSet::From(SBezierList *sbl, SPolygon *poly,
496 double chordTol,
497 bool *allClosed, SEdge *errorAt,
498 SBezierList *openContours)
499 {
500 SBezierLoopSet ret = {};
501
502 *allClosed = true;
503 while(sbl->l.n > 0) {
504 bool thisClosed;
505 SBezierLoop loop;
506 loop = SBezierLoop::FromCurves(sbl, &thisClosed, errorAt);
507 if(!thisClosed) {
508 // Record open loops in a separate list, if requested.
509 *allClosed = false;
510 if(openContours) {
511 SBezier *sb;
512 for(sb = loop.l.First(); sb; sb = loop.l.NextAfter(sb)) {
513 openContours->l.Add(sb);
514 }
515 }
516 loop.Clear();
517 } else {
518 ret.l.Add(&loop);
519 poly->AddEmptyContour();
520 loop.MakePwlInto(&(poly->l.elem[poly->l.n-1]), chordTol);
521 }
522 }
523
524 poly->normal = poly->ComputeNormal();
525 ret.normal = poly->normal;
526 if(poly->l.n > 0) {
527 ret.point = poly->AnyPoint();
528 } else {
529 ret.point = Vector::From(0, 0, 0);
530 }
531
532 return ret;
533 }
534
GetBoundingProjd(Vector u,Vector orig,double * umin,double * umax)535 void SBezierLoopSet::GetBoundingProjd(Vector u, Vector orig,
536 double *umin, double *umax)
537 {
538 SBezierLoop *sbl;
539 for(sbl = l.First(); sbl; sbl = l.NextAfter(sbl)) {
540 sbl->GetBoundingProjd(u, orig, umin, umax);
541 }
542 }
543
544 //-----------------------------------------------------------------------------
545 // Convert all the Beziers into piecewise linear form, and assemble that into
546 // a polygon, one contour per loop.
547 //-----------------------------------------------------------------------------
MakePwlInto(SPolygon * sp)548 void SBezierLoopSet::MakePwlInto(SPolygon *sp) {
549 SBezierLoop *sbl;
550 for(sbl = l.First(); sbl; sbl = l.NextAfter(sbl)) {
551 sp->AddEmptyContour();
552 sbl->MakePwlInto(&(sp->l.elem[sp->l.n - 1]));
553 }
554 }
555
Clear(void)556 void SBezierLoopSet::Clear(void) {
557 int i;
558 for(i = 0; i < l.n; i++) {
559 (l.elem[i]).Clear();
560 }
561 l.Clear();
562 }
563
564 //-----------------------------------------------------------------------------
565 // An export helper function. We start with a list of Bezier curves, and
566 // assemble them into loops. We find the outer loops, and find the outer loops'
567 // inner loops, and group them accordingly.
568 //-----------------------------------------------------------------------------
FindOuterFacesFrom(SBezierList * sbl,SPolygon * spxyz,SSurface * srfuv,double chordTol,bool * allClosed,SEdge * notClosedAt,bool * allCoplanar,Vector * notCoplanarAt,SBezierList * openContours)569 void SBezierLoopSetSet::FindOuterFacesFrom(SBezierList *sbl, SPolygon *spxyz,
570 SSurface *srfuv,
571 double chordTol,
572 bool *allClosed, SEdge *notClosedAt,
573 bool *allCoplanar, Vector *notCoplanarAt,
574 SBezierList *openContours)
575 {
576 SSurface srfPlane;
577 if(!srfuv) {
578 Vector p, u, v;
579 *allCoplanar =
580 sbl->GetPlaneContainingBeziers(&p, &u, &v, notCoplanarAt);
581 if(!*allCoplanar) {
582 // Don't even try to assemble them into loops if they're not
583 // all coplanar.
584 if(openContours) {
585 SBezier *sb;
586 for(sb = sbl->l.First(); sb; sb = sbl->l.NextAfter(sb)) {
587 openContours->l.Add(sb);
588 }
589 }
590 return;
591 }
592 // All the curves lie in a plane through p with basis vectors u and v.
593 srfPlane = SSurface::FromPlane(p, u, v);
594 srfuv = &srfPlane;
595 }
596
597 int i, j;
598 // Assemble the Bezier trim curves into closed loops; we also get the
599 // piecewise linearization of the curves (in the SPolygon spxyz), as a
600 // calculation aid for the loop direction.
601 SBezierLoopSet sbls = SBezierLoopSet::From(sbl, spxyz, chordTol,
602 allClosed, notClosedAt,
603 openContours);
604 if(sbls.l.n != spxyz->l.n) return;
605
606 // Convert the xyz piecewise linear to uv piecewise linear.
607 SPolygon spuv = {};
608 SContour *sc;
609 for(sc = spxyz->l.First(); sc; sc = spxyz->l.NextAfter(sc)) {
610 spuv.AddEmptyContour();
611 SPoint *pt;
612 for(pt = sc->l.First(); pt; pt = sc->l.NextAfter(pt)) {
613 double u, v;
614 srfuv->ClosestPointTo(pt->p, &u, &v);
615 spuv.l.elem[spuv.l.n - 1].AddPoint(Vector::From(u, v, 0));
616 }
617 }
618 spuv.normal = Vector::From(0, 0, 1); // must be, since it's in xy plane now
619
620 static const int OUTER_LOOP = 10;
621 static const int INNER_LOOP = 20;
622 static const int USED_LOOP = 30;
623 // Fix the contour directions; we do this properly, in uv space, so it
624 // works for curved surfaces too (important for STEP export).
625 spuv.FixContourDirections();
626 for(i = 0; i < spuv.l.n; i++) {
627 SContour *contour = &(spuv.l.elem[i]);
628 SBezierLoop *bl = &(sbls.l.elem[i]);
629 if(contour->tag) {
630 // This contour got reversed in the polygon to make the directions
631 // consistent, so the same must be necessary for the Bezier loop.
632 bl->Reverse();
633 }
634 if(contour->IsClockwiseProjdToNormal(spuv.normal)) {
635 bl->tag = INNER_LOOP;
636 } else {
637 bl->tag = OUTER_LOOP;
638 }
639 }
640
641 bool loopsRemaining = true;
642 while(loopsRemaining) {
643 loopsRemaining = false;
644 for(i = 0; i < sbls.l.n; i++) {
645 SBezierLoop *loop = &(sbls.l.elem[i]);
646 if(loop->tag != OUTER_LOOP) continue;
647
648 // Check if this contour contains any outer loops; if it does, then
649 // we should do those "inner outer loops" first; otherwise we
650 // will steal their holes, since their holes also lie inside this
651 // contour.
652 for(j = 0; j < sbls.l.n; j++) {
653 SBezierLoop *outer = &(sbls.l.elem[j]);
654 if(i == j) continue;
655 if(outer->tag != OUTER_LOOP) continue;
656
657 Vector p = spuv.l.elem[j].AnyEdgeMidpoint();
658 if(spuv.l.elem[i].ContainsPointProjdToNormal(spuv.normal, p)) {
659 break;
660 }
661 }
662 if(j < sbls.l.n) {
663 // It does, can't do this one yet.
664 continue;
665 }
666
667 SBezierLoopSet outerAndInners = {};
668 loopsRemaining = true;
669 loop->tag = USED_LOOP;
670 outerAndInners.l.Add(loop);
671 int auxA = 0;
672 if(loop->l.n > 0) auxA = loop->l.elem[0].auxA;
673
674 for(j = 0; j < sbls.l.n; j++) {
675 SBezierLoop *inner = &(sbls.l.elem[j]);
676 if(inner->tag != INNER_LOOP) continue;
677 if(inner->l.n < 1) continue;
678 if(inner->l.elem[0].auxA != auxA) continue;
679
680 Vector p = spuv.l.elem[j].AnyEdgeMidpoint();
681 if(spuv.l.elem[i].ContainsPointProjdToNormal(spuv.normal, p)) {
682 outerAndInners.l.Add(inner);
683 inner->tag = USED_LOOP;
684 }
685 }
686
687 outerAndInners.point = srfuv->PointAt(0, 0);
688 outerAndInners.normal = srfuv->NormalAt(0, 0);
689 l.Add(&outerAndInners);
690 }
691 }
692
693 // If we have poorly-formed loops--for example, overlapping zero-area
694 // stuff--then we can end up with leftovers. We use this function to
695 // group stuff into closed paths for export when possible, so it's bad
696 // to screw up on that stuff. So just add them onto the open curve list.
697 // Very ugly, but better than losing curves.
698 for(i = 0; i < sbls.l.n; i++) {
699 SBezierLoop *loop = &(sbls.l.elem[i]);
700 if(loop->tag == USED_LOOP) continue;
701
702 if(openContours) {
703 SBezier *sb;
704 for(sb = loop->l.First(); sb; sb = loop->l.NextAfter(sb)) {
705 openContours->l.Add(sb);
706 }
707 }
708 loop->Clear();
709 // but don't free the used loops, since we shallow-copied them to
710 // ourself
711 }
712
713 sbls.l.Clear(); // not sbls.Clear(), since that would deep-clear
714 spuv.Clear();
715 }
716
AddOpenPath(SBezier * sb)717 void SBezierLoopSetSet::AddOpenPath(SBezier *sb) {
718 SBezierLoop sbl = {};
719 sbl.l.Add(sb);
720
721 SBezierLoopSet sbls = {};
722 sbls.l.Add(&sbl);
723
724 l.Add(&sbls);
725 }
726
Clear(void)727 void SBezierLoopSetSet::Clear(void) {
728 SBezierLoopSet *sbls;
729 for(sbls = l.First(); sbls; sbls = l.NextAfter(sbls)) {
730 sbls->Clear();
731 }
732 l.Clear();
733 }
734
FromTransformationOf(SCurve * a,Vector t,Quaternion q,double scale)735 SCurve SCurve::FromTransformationOf(SCurve *a,
736 Vector t, Quaternion q, double scale)
737 {
738 SCurve ret = {};
739
740 ret.h = a->h;
741 ret.isExact = a->isExact;
742 ret.exact = (a->exact).TransformedBy(t, q, scale);
743 ret.surfA = a->surfA;
744 ret.surfB = a->surfB;
745
746 SCurvePt *p;
747 for(p = a->pts.First(); p; p = a->pts.NextAfter(p)) {
748 SCurvePt pp = *p;
749 pp.p = (pp.p).ScaledBy(scale);
750 pp.p = (q.Rotate(pp.p)).Plus(t);
751 ret.pts.Add(&pp);
752 }
753 return ret;
754 }
755
Clear(void)756 void SCurve::Clear(void) {
757 pts.Clear();
758 }
759
GetSurfaceA(SShell * a,SShell * b)760 SSurface *SCurve::GetSurfaceA(SShell *a, SShell *b) {
761 if(source == FROM_A) {
762 return a->surface.FindById(surfA);
763 } else if(source == FROM_B) {
764 return b->surface.FindById(surfA);
765 } else if(source == FROM_INTERSECTION) {
766 return a->surface.FindById(surfA);
767 } else oops();
768 }
769
GetSurfaceB(SShell * a,SShell * b)770 SSurface *SCurve::GetSurfaceB(SShell *a, SShell *b) {
771 if(source == FROM_A) {
772 return a->surface.FindById(surfB);
773 } else if(source == FROM_B) {
774 return b->surface.FindById(surfB);
775 } else if(source == FROM_INTERSECTION) {
776 return b->surface.FindById(surfB);
777 } else oops();
778 }
779
780 //-----------------------------------------------------------------------------
781 // When we split line segments wherever they intersect a surface, we introduce
782 // extra pwl points. This may create very short edges that could be removed
783 // without violating the chord tolerance. Those are ugly, and also break
784 // stuff in the Booleans. So remove them.
785 //-----------------------------------------------------------------------------
RemoveShortSegments(SSurface * srfA,SSurface * srfB)786 void SCurve::RemoveShortSegments(SSurface *srfA, SSurface *srfB) {
787 // Three, not two; curves are pwl'd to at least two edges (three points)
788 // even if not necessary, to avoid square holes.
789 if(pts.n <= 3) return;
790 pts.ClearTags();
791
792 Vector prev = pts.elem[0].p;
793 int i, a;
794 for(i = 1; i < pts.n - 1; i++) {
795 SCurvePt *sct = &(pts.elem[i]),
796 *scn = &(pts.elem[i+1]);
797 if(sct->vertex) {
798 prev = sct->p;
799 continue;
800 }
801 bool mustKeep = false;
802
803 // We must check against both surfaces; the piecewise linear edge
804 // may have a different chord tolerance in the two surfaces. (For
805 // example, a circle in the surface of a cylinder is just a straight
806 // line, so it always has perfect chord tol, but that circle in
807 // a plane is a circle so it doesn't).
808 for(a = 0; a < 2; a++) {
809 SSurface *srf = (a == 0) ? srfA : srfB;
810 Vector puv, nuv;
811 srf->ClosestPointTo(prev, &(puv.x), &(puv.y));
812 srf->ClosestPointTo(scn->p, &(nuv.x), &(nuv.y));
813
814 if(srf->ChordToleranceForEdge(nuv, puv) > SS.ChordTolMm()) {
815 mustKeep = true;
816 }
817 }
818
819 if(mustKeep) {
820 prev = sct->p;
821 } else {
822 sct->tag = 1;
823 // and prev is unchanged, since there's no longer any point
824 // in between
825 }
826 }
827
828 pts.RemoveTagged();
829 }
830
EntireCurve(SShell * shell,hSCurve hsc,bool backwards)831 STrimBy STrimBy::EntireCurve(SShell *shell, hSCurve hsc, bool backwards) {
832 STrimBy stb = {};
833 stb.curve = hsc;
834 SCurve *sc = shell->curve.FindById(hsc);
835
836 if(backwards) {
837 stb.finish = sc->pts.elem[0].p;
838 stb.start = sc->pts.elem[sc->pts.n - 1].p;
839 stb.backwards = true;
840 } else {
841 stb.start = sc->pts.elem[0].p;
842 stb.finish = sc->pts.elem[sc->pts.n - 1].p;
843 stb.backwards = false;
844 }
845
846 return stb;
847 }
848
849