https://shifthappens.site/js/lib/three/csg-lib.js

1
2// ## License
3// 
4// Copyright (c) 2011 Evan Wallace (http://madebyevan.com/), under the MIT license.
5// THREE.js rework by thrax
6
7// # class CSG
8// Holds a binary space partition tree representing a 3D solid. Two solids can
9// be combined using the `union()`, `subtract()`, and `intersect()` methods.
10
11
12class CSG {
13    constructor() {
14        this.polygons = [];
15    }
16    clone() {
17        let csg = new CSG();
18        csg.polygons = this.polygons.map(p=>p.clone())
19        return csg;
20    }
21
22    toPolygons() {
23        return this.polygons;
24    }
25
26    union(csg) {
27        let a = new Node(this.clone().polygons);
28        let b = new Node(csg.clone().polygons);
29        a.clipTo(b);
30        b.clipTo(a);
31        b.invert();
32        b.clipTo(a);
33        b.invert();
34        a.build(b.allPolygons());
35        return CSG.fromPolygons(a.allPolygons());
36    }
37
38    subtract(csg) {
39        let a = new Node(this.clone().polygons);
40        let b = new Node(csg.clone().polygons);
41        a.invert();
42        a.clipTo(b);
43        b.clipTo(a);
44        b.invert();
45        b.clipTo(a);
46        b.invert();
47        a.build(b.allPolygons());
48        a.invert();
49        return CSG.fromPolygons(a.allPolygons());
50    }
51
52    intersect(csg) {
53        let a = new Node(this.clone().polygons);
54        let b = new Node(csg.clone().polygons);
55        a.invert();
56        b.clipTo(a);
57        b.invert();
58        a.clipTo(b);
59        b.clipTo(a);
60        a.build(b.allPolygons());
61        a.invert();
62        return CSG.fromPolygons(a.allPolygons());
63    }
64
65    // Return a new CSG solid with solid and empty space switched. This solid is
66    // not modified.
67    inverse() {
68        let csg = this.clone();
69        csg.polygons.forEach(p=>p.flip());
70        return csg;
71    }
72}
73
74// Construct a CSG solid from a list of `Polygon` instances.
75CSG.fromPolygons=function(polygons) {

76    let csg = new CSG();
77    csg.polygons = polygons;
78    return csg;
79}
80
81// # class Vector
82
83// Represents a 3D vector.
84// 
85// Example usage:
86// 
87//     new CSG.Vector(1, 2, 3);
88
89
90
91class Vector {
92    constructor(x=0, y=0, z=0) {
93        this.x=x;
94        this.y=y;
95        this.z=z;
96    }
97    copy(v){
98        this.x=v.x;
99        this.y=v.y;
100        this.z=v.z;
101        return this
102    }
103    clone() {
104        return new Vector(this.x,this.y,this.z)
105    }
106    negate() {
107        this.x*=-1;
108        this.y*=-1;
109        this.z*=-1;
110        return this
111    }
112    add(a) {
113        this.x+=a.x
114        this.y+=a.y
115        this.z+=a.z
116        return this;
117    }
118    sub(a) {
119        this.x-=a.x
120        this.y-=a.y
121        this.z-=a.z
122        return this
123    }
124    times(a) {
125        this.x*=a
126        this.y*=a
127        this.z*=a
128        return this
129    }
130    dividedBy(a) {
131        this.x/=a
132        this.y/=a
133        this.z/=a
134        return this
135    }
136    lerp(a, t) {
137        return this.add(tv0.copy(a).sub(this).times(t))
138    }
139    unit() {
140        return this.dividedBy(this.length())
141    }
142    length(){
143        return Math.sqrt((this.x**2)+(this.y**2)+(this.z**2))
144    }
145    normalize(){
146        return this.unit()
147    }
148    cross(b) {
149        let a = this;
150		const ax = a.x, ay = a.y, az = a.z;
151		const bx = b.x, by = b.y, bz = b.z;
152
153		this.x = ay * bz - az * by;
154		this.y = az * bx - ax * bz;
155		this.z = ax * by - ay * bx;
156
157		return this;
158    }
159    dot(b){
160        return (this.x*b.x)+(this.y*b.y)+(this.z*b.z)
161    }
162}
163
164//Temporaries used to avoid internal allocation..
165let tv0=new Vector()
166let tv1=new Vector()
167
168
169// # class Vertex
170
171// Represents a vertex of a polygon. Use your own vertex class instead of this
172// one to provide additional features like texture coordinates and vertex
173// colors. Custom vertex classes need to provide a `pos` property and `clone()`,
174// `flip()`, and `interpolate()` methods that behave analogous to the ones
175// defined by `CSG.Vertex`. This class provides `normal` so convenience
176// functions like `CSG.sphere()` can return a smooth vertex normal, but `normal`
177// is not used anywhere else.
178
179class Vertex {
180
181    constructor(pos, normal, uv, color) {
182        this.pos = new Vector().copy(pos);
183        this.normal = new Vector().copy(normal);
184        uv && (this.uv = new Vector().copy(uv)) && (this.uv.z=0);
185        color && (this.color = new Vector().copy(color));
186    }
187
188    clone() {
189        return new Vertex(this.pos,this.normal,this.uv,this.color);
190    }
191
192    // Invert all orientation-specific data (e.g. vertex normal). Called when the
193    // orientation of a polygon is flipped.
194    flip() {
195        this.normal.negate();
196    }
197
198    // Create a new vertex between this vertex and `other` by linearly
199    // interpolating all properties using a parameter of `t`. Subclasses should
200    // override this to interpolate additional properties.
201    interpolate(other, t) {
202        return new Vertex(this.pos.clone().lerp(other.pos, t),this.normal.clone().lerp(other.normal, t),this.uv&&other.uv&&this.uv.clone().lerp(other.uv, t), this.color&&other.color&&this.color.clone().lerp(other.color,t))
203    }
204}
205;
206// # class Plane
207
208// Represents a plane in 3D space.
209
210class Plane {
211    constructor(normal, w) {
212        this.normal = normal;
213        this.w = w;
214    }
215
216    clone() {
217        return new Plane(this.normal.clone(),this.w);
218    }
219
220    flip() {
221        this.normal.negate();
222        this.w = -this.w;
223    }
224
225    // Split `polygon` by this plane if needed, then put the polygon or polygon
226    // fragments in the appropriate lists. Coplanar polygons go into either
227    // `coplanarFront` or `coplanarBack` depending on their orientation with
228    // respect to this plane. Polygons in front or in back of this plane go into
229    // either `front` or `back`.
230    splitPolygon(polygon, coplanarFront, coplanarBack, front, back) {
231        const COPLANAR = 0;
232        const FRONT = 1;
233        const BACK = 2;
234        const SPANNING = 3;
235
236        // Classify each point as well as the entire polygon into one of the above
237        // four classes.
238        let polygonType = 0;
239        let types = [];
240        for (let i = 0; i < polygon.vertices.length; i++) {
241            let t = this.normal.dot(polygon.vertices[i].pos) - this.w;
242            let type = (t < -Plane.EPSILON) ? BACK : (t > Plane.EPSILON) ? FRONT : COPLANAR;
243            polygonType |= type;
244            types.push(type);
245        }
246
247        // Put the polygon in the correct list, splitting it when necessary.
248        switch (polygonType) {
249        case COPLANAR:
250            (this.normal.dot(polygon.plane.normal) > 0 ? coplanarFront : coplanarBack).push(polygon);
251            break;
252        case FRONT:
253            front.push(polygon);
254            break;
255        case BACK:
256            back.push(polygon);
257            break;
258        case SPANNING:
259            let f = []
260              , b = [];
261            for (let i = 0; i < polygon.vertices.length; i++) {
262                let j = (i + 1) % polygon.vertices.length;
263                let ti = types[i]
264                  , tj = types[j];
265                let vi = polygon.vertices[i]
266                  , vj = polygon.vertices[j];
267                if (ti != BACK)
268                    f.push(vi);
269                if (ti != FRONT)
270                    b.push(ti != BACK ? vi.clone() : vi);
271                if ((ti | tj) == SPANNING) {
272                    let t = (this.w - this.normal.dot(vi.pos)) / this.normal.dot(tv0.copy(vj.pos).sub(vi.pos));
273                    let v = vi.interpolate(vj, t);
274                    f.push(v);
275                    b.push(v.clone());
276                }
277            }
278            if (f.length >= 3)
279                front.push(new Polygon(f,polygon.shared));
280            if (b.length >= 3)
281                back.push(new Polygon(b,polygon.shared));
282            break;
283        }
284    }
285
286}
287
288// `Plane.EPSILON` is the tolerance used by `splitPolygon()` to decide if a
289// point is on the plane.
290Plane.EPSILON = 1e-5;
291
292Plane.fromPoints = function(a, b, c) {
293    let n = tv0.copy(b).sub(a).cross(tv1.copy(c).sub(a)).normalize()
294    return new Plane(n.clone(),n.dot(a));
295}
296
297
298// # class Polygon
299
300// Represents a convex polygon. The vertices used to initialize a polygon must

301// be coplanar and form a convex loop. They do not have to be `Vertex`
302// instances but they must behave similarly (duck typing can be used for
303// customization).
304// 
305// Each convex polygon has a `shared` property, which is shared between all
306// polygons that are clones of each other or were split from the same polygon.
307// This can be used to define per-polygon properties (such as surface color).
308
309class Polygon {
310    constructor(vertices, shared) {
311        this.vertices = vertices;
312        this.shared = shared;
313        this.plane = Plane.fromPoints(vertices[0].pos, vertices[1].pos, vertices[2].pos);
314    }
315    clone() {
316        return new Polygon(this.vertices.map(v=>v.clone()),this.shared);
317    }
318    flip() {
319        this.vertices.reverse().forEach(v=>v.flip())
320        this.plane.flip();
321    }
322}
323
324// # class Node
325
326// Holds a node in a BSP tree. A BSP tree is built from a collection of polygons
327// by picking a polygon to split along. That polygon (and all other coplanar
328// polygons) are added directly to that node and the other polygons are added to
329// the front and/or back subtrees. This is not a leafy BSP tree since there is
330// no distinction between internal and leaf nodes.
331
332class Node {
333    constructor(polygons) {
334        this.plane = null;
335        this.front = null;
336        this.back = null;
337        this.polygons = [];
338        if (polygons)
339            this.build(polygons);
340    }
341    clone() {
342        let node = new Node();
343        node.plane = this.plane && this.plane.clone();
344        node.front = this.front && this.front.clone();
345        node.back = this.back && this.back.clone();
346        node.polygons = this.polygons.map(p=>p.clone());
347        return node;
348    }
349
350    // Convert solid space to empty space and empty space to solid space.
351    invert() {
352        for (let i = 0; i < this.polygons.length; i++)
353            this.polygons[i].flip();
354        
355        this.plane && this.plane.flip();
356        this.front && this.front.invert();
357        this.back && this.back.invert();
358        let temp = this.front;
359        this.front = this.back;
360        this.back = temp;
361    }
362
363    // Recursively remove all polygons in `polygons` that are inside this BSP
364    // tree.
365    clipPolygons(polygons) {
366        if (!this.plane)
367            return polygons.slice();
368        let front = []
369          , back = [];
370        for (let i = 0; i < polygons.length; i++) {
371            this.plane.splitPolygon(polygons[i], front, back, front, back);
372        }
373        if (this.front)
374            front = this.front.clipPolygons(front);
375        if (this.back)
376            back = this.back.clipPolygons(back);
377        else 
378            back = [];
379            //return front;
380        return front.concat(back);
381    }
382
383    // Remove all polygons in this BSP tree that are inside the other BSP tree
384    // `bsp`.
385    clipTo(bsp) {
386        this.polygons = bsp.clipPolygons(this.polygons);
387        if (this.front)
388            this.front.clipTo(bsp);
389        if (this.back)
390            this.back.clipTo(bsp);
391    }
392
393    // Return a list of all polygons in this BSP tree.
394    allPolygons() {
395        let polygons = this.polygons.slice();
396        if (this.front)
397            polygons = polygons.concat(this.front.allPolygons());
398        if (this.back)
399            polygons = polygons.concat(this.back.allPolygons());
400        return polygons;
401    }
402
403    // Build a BSP tree out of `polygons`. When called on an existing tree, the
404    // new polygons are filtered down to the bottom of the tree and become new

405    // nodes there. Each set of polygons is partitioned using the first polygon
406    // (no heuristic is used to pick a good split).
407    build(polygons) {
408        if (!polygons.length)
409            return;
410        if (!this.plane)
411            this.plane = polygons[0].plane.clone();
412        let front = []
413          , back = [];
414        for (let i = 0; i < polygons.length; i++) {
415            this.plane.splitPolygon(polygons[i], this.polygons, this.polygons, front, back);
416        }
417        if (front.length) {
418            if (!this.front)
419                this.front = new Node();
420            this.front.build(front);
421        }
422        if (back.length) {
423            if (!this.back)
424                this.back = new Node();
425            this.back.build(back);
426        }
427    }
428}
429
430// Inflate/deserialize a vanilla struct into a CSG structure webworker.
431CSG.fromJSON=function(json){
432    return CSG.fromPolygons(json.polygons.map(p=>new Polygon(p.vertices.map(v=> new Vertex(v.pos,v.normal,v.uv)),p.shared)))
433}
434
435export {CSG,Vertex,Vector,Polygon,Plane}
436
437
438
439// Return a new CSG solid representing space in either this solid or in the
440// solid `csg`. Neither this solid nor the solid `csg` are modified.
441// 
442//     A.union(B)
443// 
444//     +-------+            +-------+
445//     |       |            |       |
446//     |   A   |            |       |
447//     |    +--+----+   =   |       +----+
448//     +----+--+    |       +----+       |
449//          |   B   |            |       |
450//          |       |            |       |
451//          +-------+            +-------+
452// 
453// Return a new CSG solid representing space in this solid but not in the
454// solid `csg`. Neither this solid nor the solid `csg` are modified.
455// 
456//     A.subtract(B)
457// 
458//     +-------+            +-------+
459//     |       |            |       |
460//     |   A   |            |       |
461//     |    +--+----+   =   |    +--+
462//     +----+--+    |       +----+
463//          |   B   |
464//          |       |
465//          +-------+
466// 
467// Return a new CSG solid representing space both this solid and in the
468// solid `csg`. Neither this solid nor the solid `csg` are modified.
469// 
470//     A.intersect(B)
471// 
472//     +-------+
473//     |       |
474//     |   A   |
475//     |    +--+----+   =   +--+
476//     +----+--+    |       +--+
477//          |   B   |
478//          |       |
479//          +-------+
480// 
481