-
Notifications
You must be signed in to change notification settings - Fork 56
/
trees.js
510 lines (470 loc) · 16.4 KB
/
trees.js
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
const {_CSGDEBUG, EPS} = require('./constants')
const Vertex = require('./math/Vertex3')
const Polygon = require('./math/Polygon3')
// Returns object:
// .type:
// 0: coplanar-front
// 1: coplanar-back
// 2: front
// 3: back
// 4: spanning
// In case the polygon is spanning, returns:
// .front: a Polygon of the front part
// .back: a Polygon of the back part
function splitPolygonByPlane (plane, polygon) {
let result = {
type: null,
front: null,
back: null
}
// cache in local lets (speedup):
let planenormal = plane.normal
let vertices = polygon.vertices
let numvertices = vertices.length
if (polygon.plane.equals(plane)) {
result.type = 0
} else {
let thisw = plane.w
let hasfront = false
let hasback = false
let vertexIsBack = []
let MINEPS = -EPS
for (let i = 0; i < numvertices; i++) {
let t = planenormal.dot(vertices[i].pos) - thisw
let isback = (t < 0)
vertexIsBack.push(isback)
if (t > EPS) hasfront = true
if (t < MINEPS) hasback = true
}
if ((!hasfront) && (!hasback)) {
// all points coplanar
let t = planenormal.dot(polygon.plane.normal)
result.type = (t >= 0) ? 0 : 1
} else if (!hasback) {
result.type = 2
} else if (!hasfront) {
result.type = 3
} else {
// spanning
result.type = 4
let frontvertices = []
let backvertices = []
let isback = vertexIsBack[0]
for (let vertexindex = 0; vertexindex < numvertices; vertexindex++) {
let vertex = vertices[vertexindex]
let nextvertexindex = vertexindex + 1
if (nextvertexindex >= numvertices) nextvertexindex = 0
let nextisback = vertexIsBack[nextvertexindex]
if (isback === nextisback) {
// line segment is on one side of the plane:
if (isback) {
backvertices.push(vertex)
} else {
frontvertices.push(vertex)
}
} else {
// line segment intersects plane:
let point = vertex.pos
let nextpoint = vertices[nextvertexindex].pos
let intersectionpoint = plane.splitLineBetweenPoints(point, nextpoint)
let intersectionvertex = new Vertex(intersectionpoint)
if (isback) {
backvertices.push(vertex)
backvertices.push(intersectionvertex)
frontvertices.push(intersectionvertex)
} else {
frontvertices.push(vertex)
frontvertices.push(intersectionvertex)
backvertices.push(intersectionvertex)
}
}
isback = nextisback
} // for vertexindex
// remove duplicate vertices:
let EPS_SQUARED = EPS * EPS
if (backvertices.length >= 3) {
let prevvertex = backvertices[backvertices.length - 1]
for (let vertexindex = 0; vertexindex < backvertices.length; vertexindex++) {
let vertex = backvertices[vertexindex]
if (vertex.pos.distanceToSquared(prevvertex.pos) < EPS_SQUARED) {
backvertices.splice(vertexindex, 1)
vertexindex--
}
prevvertex = vertex
}
}
if (frontvertices.length >= 3) {
let prevvertex = frontvertices[frontvertices.length - 1]
for (let vertexindex = 0; vertexindex < frontvertices.length; vertexindex++) {
let vertex = frontvertices[vertexindex]
if (vertex.pos.distanceToSquared(prevvertex.pos) < EPS_SQUARED) {
frontvertices.splice(vertexindex, 1)
vertexindex--
}
prevvertex = vertex
}
}
if (frontvertices.length >= 3) {
result.front = new Polygon(frontvertices, polygon.shared, polygon.plane)
}
if (backvertices.length >= 3) {
result.back = new Polygon(backvertices, polygon.shared, polygon.plane)
}
}
}
return result
}
// # class PolygonTreeNode
// This class manages hierarchical splits of polygons
// At the top is a root node which doesn hold a polygon, only child PolygonTreeNodes
// Below that are zero or more 'top' nodes; each holds a polygon. The polygons can be in different planes
// splitByPlane() splits a node by a plane. If the plane intersects the polygon, two new child nodes
// are created holding the splitted polygon.
// getPolygons() retrieves the polygon from the tree. If for PolygonTreeNode the polygon is split but
// the two split parts (child nodes) are still intact, then the unsplit polygon is returned.
// This ensures that we can safely split a polygon into many fragments. If the fragments are untouched,
// getPolygons() will return the original unsplit polygon instead of the fragments.
// remove() removes a polygon from the tree. Once a polygon is removed, the parent polygons are invalidated
// since they are no longer intact.
// constructor creates the root node:
const PolygonTreeNode = function () {
this.parent = null
this.children = []
this.polygon = null
this.removed = false
}
PolygonTreeNode.prototype = {
// fill the tree with polygons. Should be called on the root node only; child nodes must
// always be a derivate (split) of the parent node.
addPolygons: function (polygons) {
if (!this.isRootNode())
// new polygons can only be added to root node; children can only be splitted polygons
{
throw new Error('Assertion failed')
}
let _this = this
polygons.map(function (polygon) {
_this.addChild(polygon)
})
},
// remove a node
// - the siblings become toplevel nodes
// - the parent is removed recursively
remove: function () {
if (!this.removed) {
this.removed = true
if (_CSGDEBUG) {
if (this.isRootNode()) throw new Error('Assertion failed') // can't remove root node
if (this.children.length) throw new Error('Assertion failed') // we shouldn't remove nodes with children
}
// remove ourselves from the parent's children list:
let parentschildren = this.parent.children
let i = parentschildren.indexOf(this)
if (i < 0) throw new Error('Assertion failed')
parentschildren.splice(i, 1)
// invalidate the parent's polygon, and of all parents above it:
this.parent.recursivelyInvalidatePolygon()
}
},
isRemoved: function () {
return this.removed
},
isRootNode: function () {
return !this.parent
},
// invert all polygons in the tree. Call on the root node
invert: function () {
if (!this.isRootNode()) throw new Error('Assertion failed') // can only call this on the root node
this.invertSub()
},
getPolygon: function () {
if (!this.polygon) throw new Error('Assertion failed') // doesn't have a polygon, which means that it has been broken down
return this.polygon
},
getPolygons: function (result) {
let children = [this]
let queue = [children]
let i, j, l, node
for (i = 0; i < queue.length; ++i) { // queue size can change in loop, don't cache length
children = queue[i]
for (j = 0, l = children.length; j < l; j++) { // ok to cache length
node = children[j]
if (node.polygon) {
// the polygon hasn't been broken yet. We can ignore the children and return our polygon:
result.push(node.polygon)
} else {
// our polygon has been split up and broken, so gather all subpolygons from the children
queue.push(node.children)
}
}
}
},
// split the node by a plane; add the resulting nodes to the frontnodes and backnodes array
// If the plane doesn't intersect the polygon, the 'this' object is added to one of the arrays
// If the plane does intersect the polygon, two new child nodes are created for the front and back fragments,
// and added to both arrays.
splitByPlane: function (plane, coplanarfrontnodes, coplanarbacknodes, frontnodes, backnodes) {
if (this.children.length) {
let queue = [this.children]
let i
let j
let l
let node
let nodes
for (i = 0; i < queue.length; i++) { // queue.length can increase, do not cache
nodes = queue[i]
for (j = 0, l = nodes.length; j < l; j++) { // ok to cache length
node = nodes[j]
if (node.children.length) {
queue.push(node.children)
} else {
// no children. Split the polygon:
node._splitByPlane(plane, coplanarfrontnodes, coplanarbacknodes, frontnodes, backnodes)
}
}
}
} else {
this._splitByPlane(plane, coplanarfrontnodes, coplanarbacknodes, frontnodes, backnodes)
}
},
// only to be called for nodes with no children
_splitByPlane: function (plane, coplanarfrontnodes, coplanarbacknodes, frontnodes, backnodes) {
let polygon = this.polygon
if (polygon) {
let bound = polygon.boundingSphere()
let sphereradius = bound[1] + EPS // FIXME Why add imprecision?
let planenormal = plane.normal
let spherecenter = bound[0]
let d = planenormal.dot(spherecenter) - plane.w
if (d > sphereradius) {
frontnodes.push(this)
} else if (d < -sphereradius) {
backnodes.push(this)
} else {
let splitresult = splitPolygonByPlane(plane, polygon)
switch (splitresult.type) {
case 0:
// coplanar front:
coplanarfrontnodes.push(this)
break
case 1:
// coplanar back:
coplanarbacknodes.push(this)
break
case 2:
// front:
frontnodes.push(this)
break
case 3:
// back:
backnodes.push(this)
break
case 4:
// spanning:
if (splitresult.front) {
let frontnode = this.addChild(splitresult.front)
frontnodes.push(frontnode)
}
if (splitresult.back) {
let backnode = this.addChild(splitresult.back)
backnodes.push(backnode)
}
break
}
}
}
},
// PRIVATE methods from here:
// add child to a node
// this should be called whenever the polygon is split
// a child should be created for every fragment of the split polygon
// returns the newly created child
addChild: function (polygon) {
let newchild = new PolygonTreeNode()
newchild.parent = this
newchild.polygon = polygon
this.children.push(newchild)
return newchild
},
invertSub: function () {
let children = [this]
let queue = [children]
let i, j, l, node
for (i = 0; i < queue.length; i++) {
children = queue[i]
for (j = 0, l = children.length; j < l; j++) {
node = children[j]
if (node.polygon) {
node.polygon = node.polygon.flipped()
}
queue.push(node.children)
}
}
},
recursivelyInvalidatePolygon: function () {
let node = this
while (node.polygon) {
node.polygon = null
if (node.parent) {
node = node.parent
}
}
}
}
// # class Tree
// This is the root of a BSP tree
// We are using this separate class for the root of the tree, to hold the PolygonTreeNode root
// The actual tree is kept in this.rootnode
const Tree = function (polygons) {
this.polygonTree = new PolygonTreeNode()
this.rootnode = new Node(null)
if (polygons) this.addPolygons(polygons)
}
Tree.prototype = {
invert: function () {
this.polygonTree.invert()
this.rootnode.invert()
},
// Remove all polygons in this BSP tree that are inside the other BSP tree
// `tree`.
clipTo: function (tree, alsoRemovecoplanarFront) {
alsoRemovecoplanarFront = alsoRemovecoplanarFront ? true : false
this.rootnode.clipTo(tree, alsoRemovecoplanarFront)
},
allPolygons: function () {
let result = []
this.polygonTree.getPolygons(result)
return result
},
addPolygons: function (polygons) {
let _this = this
let polygontreenodes = polygons.map(function (p) {
return _this.polygonTree.addChild(p)
})
this.rootnode.addPolygonTreeNodes(polygontreenodes)
}
}
// # class Node
// Holds a node in a BSP tree. A BSP tree is built from a collection of polygons
// by picking a polygon to split along.
// Polygons are not stored directly in the tree, but in PolygonTreeNodes, stored in
// this.polygontreenodes. Those PolygonTreeNodes are children of the owning
// Tree.polygonTree
// This is not a leafy BSP tree since there is
// no distinction between internal and leaf nodes.
const Node = function (parent) {
this.plane = null
this.front = null
this.back = null
this.polygontreenodes = []
this.parent = parent
}
Node.prototype = {
// Convert solid space to empty space and empty space to solid space.
invert: function () {
let queue = [this]
let node
for (let i = 0; i < queue.length; i++) {
node = queue[i]
if (node.plane) node.plane = node.plane.flipped()
if (node.front) queue.push(node.front)
if (node.back) queue.push(node.back)
let temp = node.front
node.front = node.back
node.back = temp
}
},
// clip polygontreenodes to our plane
// calls remove() for all clipped PolygonTreeNodes
clipPolygons: function (polygontreenodes, alsoRemovecoplanarFront) {
let args = {'node': this, 'polygontreenodes': polygontreenodes}
let node
let stack = []
do {
node = args.node
polygontreenodes = args.polygontreenodes
// begin "function"
if (node.plane) {
let backnodes = []
let frontnodes = []
let coplanarfrontnodes = alsoRemovecoplanarFront ? backnodes : frontnodes
let plane = node.plane
let numpolygontreenodes = polygontreenodes.length
for (let i = 0; i < numpolygontreenodes; i++) {
let node1 = polygontreenodes[i]
if (!node1.isRemoved()) {
node1.splitByPlane(plane, coplanarfrontnodes, backnodes, frontnodes, backnodes)
}
}
if (node.front && (frontnodes.length > 0)) {
stack.push({'node': node.front, 'polygontreenodes': frontnodes})
}
let numbacknodes = backnodes.length
if (node.back && (numbacknodes > 0)) {
stack.push({'node': node.back, 'polygontreenodes': backnodes})
} else {
// there's nothing behind this plane. Delete the nodes behind this plane:
for (let i = 0; i < numbacknodes; i++) {
backnodes[i].remove()
}
}
}
args = stack.pop()
} while (typeof (args) !== 'undefined')
},
// Remove all polygons in this BSP tree that are inside the other BSP tree
// `tree`.
clipTo: function (tree, alsoRemovecoplanarFront) {
let node = this
let stack = []
do {
if (node.polygontreenodes.length > 0) {
tree.rootnode.clipPolygons(node.polygontreenodes, alsoRemovecoplanarFront)
}
if (node.front) stack.push(node.front)
if (node.back) stack.push(node.back)
node = stack.pop()
} while (typeof (node) !== 'undefined')
},
addPolygonTreeNodes: function (polygontreenodes) {
let args = {'node': this, 'polygontreenodes': polygontreenodes}
let node
let stack = []
do {
node = args.node
polygontreenodes = args.polygontreenodes
if (polygontreenodes.length === 0) {
args = stack.pop()
continue
}
let _this = node
if (!node.plane) {
let bestplane = polygontreenodes[0].getPolygon().plane
node.plane = bestplane
}
let frontnodes = []
let backnodes = []
for (let i = 0, n = polygontreenodes.length; i < n; ++i) {
polygontreenodes[i].splitByPlane(_this.plane, _this.polygontreenodes, backnodes, frontnodes, backnodes)
}
if (frontnodes.length > 0) {
if (!node.front) node.front = new Node(node)
stack.push({'node': node.front, 'polygontreenodes': frontnodes})
}
if (backnodes.length > 0) {
if (!node.back) node.back = new Node(node)
stack.push({'node': node.back, 'polygontreenodes': backnodes})
}
args = stack.pop()
} while (typeof (args) !== 'undefined')
},
getParentPlaneNormals: function (normals, maxdepth) {
if (maxdepth > 0) {
if (this.parent) {
normals.push(this.parent.plane.normal)
this.parent.getParentPlaneNormals(normals, maxdepth - 1)
}
}
}
}
module.exports = Tree