-
Notifications
You must be signed in to change notification settings - Fork 208
/
AlternatingConvexClipTree.ts
552 lines (535 loc) · 21.5 KB
/
AlternatingConvexClipTree.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
/*---------------------------------------------------------------------------------------------
* Copyright (c) Bentley Systems, Incorporated. All rights reserved.
* See LICENSE.md in the project root for license terms and full copyright notice.
*--------------------------------------------------------------------------------------------*/
/** @packageDocumentation
* @module CartesianGeometry
*/
import { BSplineCurve3d } from "../bspline/BSplineCurve";
import { Arc3d } from "../curve/Arc3d";
import { CurveCollection } from "../curve/CurveCollection";
import { CurveLocationDetail, CurveLocationDetailPair } from "../curve/CurveLocationDetail";
import { CurvePrimitive } from "../curve/CurvePrimitive";
import { LineSegment3d } from "../curve/LineSegment3d";
import { LineString3d } from "../curve/LineString3d";
import { Angle } from "../geometry3d/Angle";
import { GrowableXYZArray } from "../geometry3d/GrowableXYZArray";
import { IndexedXYZCollection } from "../geometry3d/IndexedXYZCollection";
import { Point3d, Vector3d } from "../geometry3d/Point3dVector3d";
import { Point3dArray } from "../geometry3d/PointHelpers";
import { PolygonOps } from "../geometry3d/PolygonOps";
import { Range1d } from "../geometry3d/Range";
import { GrowableXYZArrayCache } from "../geometry3d/ReusableObjectCache";
import { Range1dArray } from "../numerics/Range1dArray";
import { ClipPlane } from "./ClipPlane";
import { ClipUtilities, PolygonClipper } from "./ClipUtils";
import { ConvexClipPlaneSet } from "./ConvexClipPlaneSet";
/**
* An AlternatingConvexClipTreeNode is a node in a tree structure in which
* <ul>
* <li>Each node contains a ConvexClipPlaneSet.
* <li>Each node contains an array of children which are also AlternatingConvexClipTreeNode.
* <li>The rule for an in/out decision is that a point is IN the subtree under a node if
* <ul>
* <li>It is IN the node's ConvexClipPlaneSet.
* <li>It is NOT IN any of the children.
* </ul>
* <li>Applying "NOT IN any of the children" locally to children at each level means that the ConvexClipPlaneSet
* at adjacent levels flip between being positive areas and holes.
* <li>Use an AlternatingConvexClipTreeNodeBuilder to construct the tree from a polygon.
* <li>It is possible for the root clip plane set to be empty. An empty clip plane set returns "true"
* for all point tests, so the meaning is just that holes are to be subtracted from the rest
* of space.
* <li>Although the interpretation of in/out alternates with tree levels, the ConvexClipPlaneSets
* at each level are all "enclosing" planes in the usual way.
* </ul>
*/
export class AlternatingCCTreeNode implements PolygonClipper {
public points: Point3d[] = [];
public planes: ConvexClipPlaneSet = ConvexClipPlaneSet.createEmpty();
public children: AlternatingCCTreeNode[] = [];
public startIdx: number = -1; // Start index into the master array (not the local points array)
public numPoints: number = -1; // Number of points used in the master array
private constructor() { }
/** Initialize this node with index data referencing the parent polygon. */
public static createWithIndices(index0: number, numPoints: number, result?: AlternatingCCTreeNode): AlternatingCCTreeNode {
result = result ? result : new AlternatingCCTreeNode();
result.startIdx = index0;
result.numPoints = numPoints;
result.children.length = 0;
return result;
}
/**
* <ul>
* <li>Build the tree for a polygon.
* <li>Caller creates the root node with empty constructor AlternatingConvexClipTreeNode.
* </ul>
*/
public static createTreeForPolygon(points: Point3d[], result?: AlternatingCCTreeNode): AlternatingCCTreeNode {
result = result ? result : new AlternatingCCTreeNode();
result.empty();
const builder = AlternatingCCTreeBuilder.createPointsRef(points);
builder.buildHullTree(result); // <-- Currently ALWAYS returns true
return result;
}
/** Build the outer convex hull with inlets as first level children. */
public static createHullAndInletsForPolygon(points: Point3d[], result?: AlternatingCCTreeNode): AlternatingCCTreeNode {
result = result ? result : new AlternatingCCTreeNode();
result.empty();
const builder = AlternatingCCTreeBuilder.createPointsRef(points);
builder.buildHullAndInletsForPolygon(result); // <-- Currently ALWAYS returns true
return result;
}
private extractLoopsGo(loops: Point3d[][]) {
loops.push(Point3dArray.clonePoint3dArray(this.points));
for (const c of this.children)
c.extractLoopsGo(loops);
}
/**
* Return an array with all the loops in the tree.
* This loses the alternating structure of the tree, but the collection still matches well-formed polygons by
* parity rules.
*/
public extractLoops(): Point3d[][] {
const loops: Point3d[][] = [];
this.extractLoopsGo(loops);
return loops;
}
/** Resets this AlternatingConvexClipTreeNode to a newly-created state. */
public empty() {
this.points.length = 0;
this.planes.planes.length = 0;
this.children.length = 0;
this.startIdx = -1;
this.numPoints = -1;
}
/** Creates a deep copy of this node (expensive - copies Geometry, and is recursive for children array). */
public clone(result?: AlternatingCCTreeNode): AlternatingCCTreeNode {
result = result ? result : new AlternatingCCTreeNode();
for (const point of this.points)
result.points.push(point.clone());
result.planes = ConvexClipPlaneSet.createEmpty();
for (const plane of this.planes.planes)
result.planes.planes.push(plane.clone());
for (const node of this.children)
result.children.push(node.clone());
result.startIdx = this.startIdx;
result.numPoints = this.numPoints;
return result;
}
/** Add a new child that has an empty plane set and given indices. */
public addEmptyChild(index0: number, numPoints: number) {
const newNode = AlternatingCCTreeNode.createWithIndices(index0, numPoints);
this.children.push(newNode);
}
/** Add a plane to the ConvexClipPlaneSet. */
public addPlane(plane: ClipPlane) {
this.planes.addPlaneToConvexSet(plane);
}
/** Search with alternating in and out semantics. */
public isPointOnOrInside(point: Point3d): boolean {
const inRoot = this.planes.isPointOnOrInside(point, 0.0);
if (!inRoot)
return false;
for (const child of this.children) {
if (child.isPointOnOrInside(point))
return false;
}
return true;
}
/**
* Add an AlternatingConvexClipTreeNode as a child of this one -- i.e. a hole.
* * The child pointer is pushed directly to the tree -- not cloned.
*/
public captureConvexClipPlaneSetAsVoid(child: AlternatingCCTreeNode) {
this.children.push(child);
}
/** Append start-end positions for curve intervals classified as inside or outside. */
public appendCurvePrimitiveClipIntervals(
curve: CurvePrimitive, insideIntervals: CurveLocationDetailPair[], outsideIntervals: CurveLocationDetailPair[],
): void {
const clipper = new AlternatingCCTreeNodeCurveClipper();
clipper.appendSingleClipPrimitive(this, curve, insideIntervals, outsideIntervals);
}
/** Append start-end positions for curve intervals classified as inside or outside. */
public appendCurveCollectionClipIntervals(
curves: CurveCollection, insideIntervals: CurveLocationDetailPair[], outsideIntervals: CurveLocationDetailPair[],
): void {
const clipper = new AlternatingCCTreeNodeCurveClipper();
clipper.appendCurveCollectionClip(this, curves, insideIntervals, outsideIntervals);
}
/**
* @param xyz input polygon. This is not changed.
* @param insideFragments Array to receive "inside" fragments. Each fragment is a GrowableXYZArray grabbed from
* the cache. This is NOT cleared.
* @param outsideFragments Array to receive "outside" fragments. Each fragment is a GrowableXYZArray grabbed
* from the cache. This is NOT cleared.
* @param arrayCache cache for reusable GrowableXYZArray.
*/
public appendPolygonClip(
xyz: IndexedXYZCollection,
insideFragments: GrowableXYZArray[],
outsideFragments: GrowableXYZArray[],
arrayCache: GrowableXYZArrayCache,
): void {
// At first level ..
// newInside is subject to re-clip by children.
// outside is definitively outside
const oldOutsideCount = outsideFragments.length;
const newInside = this.planes.clipInsidePushOutside(xyz, outsideFragments, arrayCache);
if (newInside === undefined) {
ClipUtilities.restoreSingletonInPlaceOfMultipleShards(outsideFragments, oldOutsideCount, xyz, arrayCache);
} else {
let carryForwardA = [newInside];
let carryForwardB: GrowableXYZArray[] = [];
let tempAB;
let shard;
for (const c of this.children) {
carryForwardB.length = 0;
while (undefined !== (shard = carryForwardA.pop())) {
// Anything inside this child is truly outside ...
c.appendPolygonClip(shard, outsideFragments, carryForwardB, arrayCache);
arrayCache.dropToCache(shard);
}
tempAB = carryForwardB;
carryForwardB = carryForwardA; // and that is empty
carryForwardA = tempAB;
}
while (undefined !== (shard = carryForwardA.pop())) {
insideFragments.push(shard);
}
}
}
public depth(): number {
const myDepth = 1;
let maxChildDepth = 0;
for (const c of this.children) {
maxChildDepth = Math.max(maxChildDepth, c.depth());
}
return myDepth + maxChildDepth;
}
}
/**
* Context structure for building an AlternatingConvexClipTreeNode from a polygon.
* <ul>
* <li> The polygon is copied to the local m_points structure.
* <li> During construction, m_stack contains indices of a sequence of points with uniform concavity.
* </ul>
*/
export class AlternatingCCTreeBuilder {
private _points: Point3d[] = [];
private _stack: number[] = [];
private constructor() { }
public static createPointsRef(points: Point3d[], result?: AlternatingCCTreeBuilder): AlternatingCCTreeBuilder {
result = result ? result : new AlternatingCCTreeBuilder();
result._points = points;
if (PolygonOps.areaXY(points) < 0.0)
result._points.reverse();
if (result._points[result._points.length - 1].isAlmostEqualMetric(result._points[0]))
result._points.pop();
return result;
}
public get period(): number {
return this._points.length;
}
public indexAfter(i: number) {
return (i + 1) % this._points.length;
}
public indexBefore(i: number) {
return (i + this._points.length - 1) % this._points.length;
}
public pushIndex(primaryPointIndex: number) {
this._stack.push(primaryPointIndex);
}
private static cross(pointA: Point3d, pointB: Point3d, pointC: Point3d): number {
return pointA.crossProductToPointsXY(pointB, pointC);
}
/*
public isInsideTurn(pointA: Point3d, pointB: Point3d, pointC: Point3d, sign: number) {
return sign * AlternatingCCTreeBuilder.cross(pointA, pointB, pointC) > 0;
}
*/
public cyclicStackPoint(cyclicIndex: number): Point3d { // SIGNED index -- but negatives must be in first 10 periods?
let stackIndex: number;
const stack = this._stack;
if (cyclicIndex > 0)
stackIndex = cyclicIndex;
else
stackIndex = cyclicIndex + 10 * stack.length;
stackIndex = stackIndex % stack.length;
return this._points[stack[stackIndex]];
}
public signFromStackTip(pointIndex: number, sign: number) {
const pointA = this.cyclicStackPoint(-2);
const pointB = this.cyclicStackPoint(-1);
const pointC = this._points[pointIndex];
return sign * AlternatingCCTreeBuilder.cross(pointA, pointB, pointC) >= 0.0 ? 1 : -1;
}
/*
* Test of xyz is in the convex region bounded by stack points:
* <ul>
* <li>polygon[i0]..polygon[i1]
* <li>polygon[j0]..polygon[j1]
* <li>polygon[i0]..polygon[i1]
* </ul>
* with "inside" controlled by sign multiplier.
public isConvexContinuation(point: Point3d, i0: number, i1: number, j0: number, j1: number, sign: number): boolean {
const points = this.points;
const stack = this.stack;
return this.isInsideTurn(points[stack[i0]], points[stack[i1]], point, sign)
&& this.isInsideTurn(points[stack[i0]], points[stack[j0]], point, sign)
&& this.isInsideTurn(points[stack[j1]], points[stack[i1]], point, sign);
}
*/
public get indexOfMaxX() {
let k = 0;
const points = this._points;
const nPoints = this._points.length;
for (let i = 1; i < nPoints; i++) {
if (points[i].x > points[k].x)
k = i;
}
return k;
}
/** Pop from the stack until the sign condition is satisfied */
public extendHullChain(k: number, sign: number, pushAfterPops: boolean) {
while (this._stack.length > 1 && this.signFromStackTip(k, sign) < 0.0)
this._stack.pop();
if (pushAfterPops)
this.pushIndex(k);
}
public collectHullChain(kStart: number, numK: number, sign: number) {
this._stack.length = 0;
if (numK > 2) {
let k = kStart;
for (let i = 0; i < numK; i++) {
this.extendHullChain(k, sign, true);
k = this.indexAfter(k);
}
}
}
public collectHullPointsInArray(points: Point3d[], kStart: number, numK: number, _sign: number) {
points.length = 0;
if (numK > 2) {
let k = kStart;
for (let i = 0; i < numK; i++) {
points.push(this._points[k]);
k = this.indexAfter(k);
}
}
}
private buildHullTreeGo(
root: AlternatingCCTreeNode, isPositiveArea: boolean, recurseToChildren: boolean = true,
): boolean {
this.collectHullChain(root.startIdx, root.numPoints, isPositiveArea ? 1.0 : -1.0);
root.points.length = 0;
const stack = this._stack;
const points = this._points;
const stackLen = stack.length;
for (let i = 0; i < stackLen; i++) {
const k0 = stack[i];
root.points.push(points[k0]);
if (i + 1 < stackLen) {
let k1 = stack[i + 1];
if (k1 === this.indexAfter(k0)) {
// two original points in sequence -- need a clip plane right here!!!
const plane = ClipPlane.createEdgeAndUpVector(
points[k0], points[k1], Vector3d.create(0, 0, 1), Angle.createRadians(0),
);
if (plane !== undefined) {
if (isPositiveArea)
plane.negateInPlace();
root.addPlane(plane);
}
} else {
if (k1 < k0)
k1 += this.period;
root.addEmptyChild(k0, k1 - k0 + 1);
}
}
}
if (recurseToChildren) {
for (const child of root.children)
this.buildHullTreeGo(child, !isPositiveArea);
} else {
for (const child of root.children)
this.collectHullPointsInArray(child.points, child.startIdx, child.numPoints, isPositiveArea ? -1.0 : 1.0);
}
return true; // Are there failure modes? What happens with crossing data?..
}
/**
* <ul>
* <li> Input a ClipTreeRoot that has start and count data
* <li> Build the hull for that data range
* <li> Store the hull points in the root
* <li> Add children with start and count data
* <li> Recursively move to children
* </ul>
*/
public buildHullAndInletsForPolygon(root: AlternatingCCTreeNode): boolean {
AlternatingCCTreeNode.createWithIndices(this.indexOfMaxX, this.period + 1, root);
return this.buildHullTreeGo(root, true, false);
}
/**
* <ul>
* <li> Input a ClipTreeRoot that has start and count data
* <li> Build the hull for that data range
* <li> Store the hull points in the root
* <li> Add children with start and count data
* <li> Recursively move to children
* </ul>
*/
public buildHullTree(root: AlternatingCCTreeNode): boolean {
AlternatingCCTreeNode.createWithIndices(this.indexOfMaxX, this.period + 1, root);
return this.buildHullTreeGo(root, true);
}
}
export class AlternatingCCTreeNodeCurveClipper {
private _curve: CurvePrimitive | undefined;
private _intervalStack: Range1d[][];
private _stackDepth: number;
public constructor() {
this._stackDepth = 0;
this._intervalStack = [];
}
private setCurveRef(curve: CurvePrimitive) { this._curve = curve; }
private popSegmentFrame() {
if (this._stackDepth > 0) {
this._topOfStack.length = 0; // formality.
this._stackDepth -= 1;
}
}
private clearSegmentStack() {
while (this._stackDepth > 0)
this.popSegmentFrame(); // and that will reduce stack depth
}
private pushEmptySegmentFrame() {
this._stackDepth += 1;
while (this._intervalStack.length < this._stackDepth)
this._intervalStack.push([]);
this._topOfStack.length = 0;
}
private get _topOfStack(): Range1d[] { return this._intervalStack[this._stackDepth - 1]; }
// set the top of the stack (as defined by stackDepth -- not array length)
private set _topOfStack(value: Range1d[]) {
const n = this._stackDepth;
if (n > 0)
this._intervalStack[n - 1] = value;
}
/** Access entry [topOfStack() - numSkip] */
private stackEntry(numSkip: number): Range1d[] {
if (numSkip <= this._stackDepth)
return this._intervalStack[this._stackDepth - 1 - numSkip];
else
return [];
}
private isTopOfStackEmpty(): boolean {
return this._topOfStack.length === 0;
}
// Is re-used by method calls
private static _fractionIntervals: number[] = [];
private appendSingleClipToStack(planes: ConvexClipPlaneSet, insideSegments: Range1d[]): boolean {
const fractionIntervals = AlternatingCCTreeNodeCurveClipper._fractionIntervals;
if (this._curve instanceof LineSegment3d) {
const segment = this._curve;
let f0: number;
let f1: number;
if (segment.announceClipIntervals(planes, (a0: number, a1: number, _cp: CurvePrimitive) => { f0 = a0; f1 = a1; })) {
insideSegments.push(Range1d.createXX(f0!, f1!));
}
return true;
} else if (this._curve instanceof Arc3d) {
const arc = this._curve;
fractionIntervals.length = 0;
arc.announceClipIntervals(planes, (a0: number, a1: number, _cp: CurvePrimitive) => {
fractionIntervals.push(a0); fractionIntervals.push(a1);
});
for (let i = 0; i < fractionIntervals.length; i += 2)
insideSegments.push(Range1d.createXX(fractionIntervals[i], fractionIntervals[i + 1]));
return true;
} else if (this._curve instanceof LineString3d && (this._curve).points.length > 1) {
const linestring = this._curve;
let f0: number;
let f1: number;
const nPoints = linestring.points.length;
const df = 1.0 / (nPoints - 1);
for (let i = 0; i < nPoints - 1; i++) {
const segment = LineSegment3d.create(linestring.points[i], linestring.points[i + 1]);
if (segment.announceClipIntervals(planes, (a0: number, a1: number, _cp: CurvePrimitive) => { f0 = a0; f1 = a1; })) {
insideSegments.push(Range1d.createXX((i + f0!) * df, (i + f1!) * df));
}
}
return true;
} else if (this._curve instanceof BSplineCurve3d) {
const bcurve = this._curve;
fractionIntervals.length = 0;
bcurve.announceClipIntervals(planes, (a0: number, a1: number, _cp: CurvePrimitive) => {
fractionIntervals.push(a0); fractionIntervals.push(a1);
});
for (let i = 0; i < fractionIntervals.length; i += 2)
insideSegments.push(Range1d.createXX(fractionIntervals[i], fractionIntervals[i + 1]));
return true;
}
return false;
}
/**
* Run one level of recursion. On return, the stack is one level deeper than at entry and the new top of the stack
* has clip for this node (expensive -- must clone items of arrays during "swaps").
*/
private recurse(node: AlternatingCCTreeNode) {
this.pushEmptySegmentFrame();
this.appendSingleClipToStack(node.planes, this._topOfStack);
Range1dArray.sort(this._topOfStack);
if (this.isTopOfStackEmpty())
return;
for (const child of node.children) {
this.recurse(child);
if (!this.isTopOfStackEmpty()) {
const ranges = Range1dArray.differenceSorted(this.stackEntry(1), this.stackEntry(0));
this.popSegmentFrame();
this._topOfStack = ranges;
} else {
this.popSegmentFrame();
}
if (this.isTopOfStackEmpty())
break;
}
}
/**
* Modifies the insideIntervals array given in place.
* Note: curve given is passed by reference and stored.
*/
public appendSingleClipPrimitive(root: AlternatingCCTreeNode, curve: CurvePrimitive,
insideIntervals: CurveLocationDetailPair[], _outsideIntervals: CurveLocationDetailPair[]) {
this.setCurveRef(curve);
this.clearSegmentStack();
this.recurse(root);
if (this._stackDepth !== 1)
return;
const intervals = this._topOfStack;
for (const interval of intervals) {
const f0 = interval.low;
const f1 = interval.high;
const xyz0 = curve.fractionToPoint(f0);
const xyz1 = curve.fractionToPoint(f1);
insideIntervals.push(CurveLocationDetailPair.createCapture(
CurveLocationDetail.createCurveFractionPoint(curve, f0, xyz0),
CurveLocationDetail.createCurveFractionPoint(curve, f1, xyz1),
));
}
this.popSegmentFrame();
}
/**
* Modifies the insideIntervals array given in place.
* Note: curve given is passed by reference and stored.
*/
public appendCurveCollectionClip(root: AlternatingCCTreeNode, curve: CurveCollection,
insideIntervals: CurveLocationDetailPair[], outsideIntervals: CurveLocationDetailPair[]) {
for (const cp of curve.children) {
if (cp instanceof CurvePrimitive)
this.appendSingleClipPrimitive(root, cp, insideIntervals, outsideIntervals);
else if (cp instanceof CurveCollection)
this.appendCurveCollectionClip(root, cp, insideIntervals, outsideIntervals);
}
}
}