# CSG algorithm in JS

May 3rd, 2021
533
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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.
12. class CSG {
13.     constructor() {
14.         this.polygons = [];
15.     }
16.     clone() {
17.         let csg = new CSG();
18.         csg.polygons = this.polygons.map(function(p) {
19.             return p.clone();
20.         });
21.         return csg;
22.     }
23.
24.     toPolygons() {
25.         return this.polygons;
26.     }
27.
28.     union(csg) {
29.         let a = new Node(this.clone().polygons);
30.         let b = new Node(csg.clone().polygons);
31.         a.clipTo(b);
32.         b.clipTo(a);
33.         b.invert();
34.         b.clipTo(a);
35.         b.invert();
36.         a.build(b.allPolygons());
37.         return CSG.fromPolygons(a.allPolygons());
38.     }
39.
40.     subtract(csg) {
41.         let a = new Node(this.clone().polygons);
42.         let b = new Node(csg.clone().polygons);
43.         a.invert();
44.         a.clipTo(b);
45.         b.clipTo(a);
46.         b.invert();
47.         b.clipTo(a);
48.         b.invert();
49.         a.build(b.allPolygons());
50.         a.invert();
51.         return CSG.fromPolygons(a.allPolygons());
52.     }
53.
54.     intersect(csg) {
55.         let a = new Node(this.clone().polygons);
56.         let b = new Node(csg.clone().polygons);
57.         a.invert();
58.         b.clipTo(a);
59.         b.invert();
60.         a.clipTo(b);
61.         b.clipTo(a);
62.         a.build(b.allPolygons());
63.         a.invert();
64.         return CSG.fromPolygons(a.allPolygons());
65.     }
66.
67.     // Return a new CSG solid with solid and empty space switched. This solid is
68.     // not modified.
69.     inverse() {
70.         let csg = this.clone();
71.         csg.polygons.forEach(p=>p.flip());
72.         return csg;
73.     }
74. }
75.
76. // Construct a CSG solid from a list of `Polygon` instances.
77. CSG.fromPolygons=function(polygons) {
78.     let csg = new CSG();
79.     csg.polygons = polygons;
80.     return csg;
81. }
82.
83. // # class Vector
84.
85. // Represents a 3D vector.
86. //
87. // Example usage:
88. //
89. //     new CSG.Vector(1, 2, 3);
90.
91.
92.
93. class Vector {
94.     constructor(x=0, y=0, z=0) {
95.         this.x=x;
96.         this.y=y;
97.         this.z=z;
98.     }
99.     copy(v){
100.         this.x=v.x;
101.         this.y=v.y;
102.         this.z=v.z;
103.         return this
104.     }
105.     clone() {
106.         return new Vector(this.x,this.y,this.z)
107.     }
108.     negate() {
109.         this.x*=-1;
110.         this.y*=-1;
111.         this.z*=-1;
112.         return this
113.     }
115.         this.x+=a.x
116.         this.y+=a.y
117.         this.z+=a.z
118.         return this;
119.     }
120.     sub(a) {
121.         this.x-=a.x
122.         this.y-=a.y
123.         this.z-=a.z
124.         return this
125.     }
126.     times(a) {
127.         this.x*=a
128.         this.y*=a
129.         this.z*=a
130.         return this
131.     }
132.     dividedBy(a) {
133.         this.x/=a
134.         this.y/=a
135.         this.z/=a
136.         return this
137.     }
138.     lerp(a, t) {
140.     }
141.     unit() {
142.         return this.dividedBy(this.length())
143.     }
144.     length(){
145.         return Math.sqrt((this.x**2)+(this.y**2)+(this.z**2))
146.     }
147.     normalize(){
148.         return this.unit()
149.     }
150.     cross(b) {
151.         let a = this;
152.         const ax = a.x, ay = a.y, az = a.z;
153.         const bx = b.x, by = b.y, bz = b.z;
154.
155.         this.x = ay * bz - az * by;
156.         this.y = az * bx - ax * bz;
157.         this.z = ax * by - ay * bx;
158.
159.         return this;
160.     }
161.     dot(b){
162.         return (this.x*b.x)+(this.y*b.y)+(this.z*b.z)
163.     }
164. }
165.
166. //Temporaries used to avoid internal allocation..
167. let tv0=new Vector()
168. let tv1=new Vector()
169.
170.
171. // # class Vertex
172.
173. // Represents a vertex of a polygon. Use your own vertex class instead of this
174. // one to provide additional features like texture coordinates and vertex
175. // colors. Custom vertex classes need to provide a `pos` property and `clone()`,
176. // `flip()`, and `interpolate()` methods that behave analogous to the ones
177. // defined by `CSG.Vertex`. This class provides `normal` so convenience
178. // functions like `CSG.sphere()` can return a smooth vertex normal, but `normal`
179. // is not used anywhere else.
180.
181. class Vertex {
182.
183.     constructor(pos, normal, uv, color) {
184.         this.pos = new Vector().copy(pos);
185.         this.normal = new Vector().copy(normal);
186.         this.uv = new Vector().copy(uv);
187.         this.uv.z=0;
188.         color && (this.color = new Vector().copy(color));
189.     }
190.
191.     clone() {
192.         return new Vertex(this.pos,this.normal,this.uv,this.color);
193.     }
194.
195.     // Invert all orientation-specific data (e.g. vertex normal). Called when the
196.     // orientation of a polygon is flipped.
197.     flip() {
198.         this.normal.negate();
199.     }
200.
201.     // Create a new vertex between this vertex and `other` by linearly
202.     // interpolating all properties using a parameter of `t`. Subclasses should
203.     // override this to interpolate additional properties.
204.     interpolate(other, t) {
205.         return new Vertex(this.pos.clone().lerp(other.pos, t),this.normal.clone().lerp(other.normal, t),this.uv.clone().lerp(other.uv, t), this.color&&other.color&&this.color.clone().lerp(other.color,t))
206.     }
207. }
208. ;
209. // # class Plane
210.
211. // Represents a plane in 3D space.
212.
213. class Plane {
214.     constructor(normal, w) {
215.         this.normal = normal;
216.         this.w = w;
217.     }
218.
219.     clone() {
220.         return new Plane(this.normal.clone(),this.w);
221.     }
222.
223.     flip() {
224.         this.normal.negate();
225.         this.w = -this.w;
226.     }
227.
228.     // Split `polygon` by this plane if needed, then put the polygon or polygon
229.     // fragments in the appropriate lists. Coplanar polygons go into either
230.     // `coplanarFront` or `coplanarBack` depending on their orientation with
231.     // respect to this plane. Polygons in front or in back of this plane go into
232.     // either `front` or `back`.
233.     splitPolygon(polygon, coplanarFront, coplanarBack, front, back) {
234.         const COPLANAR = 0;
235.         const FRONT = 1;
236.         const BACK = 2;
237.         const SPANNING = 3;
238.
239.         // Classify each point as well as the entire polygon into one of the above
240.         // four classes.
241.         let polygonType = 0;
242.         let types = [];
243.         for (let i = 0; i < polygon.vertices.length; i++) {
244.             let t = this.normal.dot(polygon.vertices[i].pos) - this.w;
245.             let type = (t < -Plane.EPSILON) ? BACK : (t > Plane.EPSILON) ? FRONT : COPLANAR;
246.             polygonType |= type;
247.             types.push(type);
248.         }
249.
250.         // Put the polygon in the correct list, splitting it when necessary.
251.         switch (polygonType) {
252.         case COPLANAR:
253.             (this.normal.dot(polygon.plane.normal) > 0 ? coplanarFront : coplanarBack).push(polygon);
254.             break;
255.         case FRONT:
256.             front.push(polygon);
257.             break;
258.         case BACK:
259.             back.push(polygon);
260.             break;
261.         case SPANNING:
262.             let f = []
263.               , b = [];
264.             for (let i = 0; i < polygon.vertices.length; i++) {
265.                 let j = (i + 1) % polygon.vertices.length;
266.                 let ti = types[i]
267.                   , tj = types[j];
268.                 let vi = polygon.vertices[i]
269.                   , vj = polygon.vertices[j];
270.                 if (ti != BACK)
271.                     f.push(vi);
272.                 if (ti != FRONT)
273.                     b.push(ti != BACK ? vi.clone() : vi);
274.                 if ((ti | tj) == SPANNING) {
275.                     let t = (this.w - this.normal.dot(vi.pos)) / this.normal.dot(tv0.copy(vj.pos).sub(vi.pos));
276.                     let v = vi.interpolate(vj, t);
277.                     f.push(v);
278.                     b.push(v.clone());
279.                 }
280.             }
281.             if (f.length >= 3)
282.                 front.push(new Polygon(f,polygon.shared));
283.             if (b.length >= 3)
284.                 back.push(new Polygon(b,polygon.shared));
285.             break;
286.         }
287.     }
288.
289. }
290.
291. // `Plane.EPSILON` is the tolerance used by `splitPolygon()` to decide if a
292. // point is on the plane.
293. Plane.EPSILON = 1e-5;
294.
295. Plane.fromPoints = function(a, b, c) {
296.     let n = tv0.copy(b).sub(a).cross(tv1.copy(c).sub(a)).normalize()
297.     return new Plane(n.clone(),n.dot(a));
298. }
299.
300.
301. // # class Polygon
302.
303. // Represents a convex polygon. The vertices used to initialize a polygon must
304. // be coplanar and form a convex loop. They do not have to be `Vertex`
305. // instances but they must behave similarly (duck typing can be used for
306. // customization).
307. //
308. // Each convex polygon has a `shared` property, which is shared between all
309. // polygons that are clones of each other or were split from the same polygon.
310. // This can be used to define per-polygon properties (such as surface color).
311.
312. class Polygon {
313.     constructor(vertices, shared) {
314.         this.vertices = vertices;
315.         this.shared = shared;
316.         this.plane = Plane.fromPoints(vertices[0].pos, vertices[1].pos, vertices[2].pos);
317.     }
318.     clone() {
319.         return new Polygon(this.vertices.map(v=>v.clone()),this.shared);
320.     }
321.     flip() {
322.         this.vertices.reverse().map(v=>v.flip())
323.         this.plane.flip();
324.     }
325. }
326.
327. // # class Node
328.
329. // Holds a node in a BSP tree. A BSP tree is built from a collection of polygons
330. // by picking a polygon to split along. That polygon (and all other coplanar
331. // polygons) are added directly to that node and the other polygons are added to
332. // the front and/or back subtrees. This is not a leafy BSP tree since there is
333. // no distinction between internal and leaf nodes.
334.
335. class Node {
336.     constructor(polygons) {
337.         this.plane = null;
338.         this.front = null;
339.         this.back = null;
340.         this.polygons = [];
341.         if (polygons)
342.             this.build(polygons);
343.     }
344.     clone() {
345.         let node = new Node();
346.         node.plane = this.plane && this.plane.clone();
347.         node.front = this.front && this.front.clone();
348.         node.back = this.back && this.back.clone();
349.         node.polygons = this.polygons.map(p=>p.clone());
350.         return node;
351.     }
352.
353.     // Convert solid space to empty space and empty space to solid space.
354.     invert() {
355.         for (let i = 0; i < this.polygons.length; i++)
356.             this.polygons[i].flip();
357.
358.         this.plane && this.plane.flip();
359.         this.front && this.front.invert();
360.         this.back && this.back.invert();
361.         let temp = this.front;
362.         this.front = this.back;
363.         this.back = temp;
364.     }
365.
366.     // Recursively remove all polygons in `polygons` that are inside this BSP
367.     // tree.
368.     clipPolygons(polygons) {
369.         if (!this.plane)
370.             return polygons.slice();
371.         let front = []
372.           , back = [];
373.         for (let i = 0; i < polygons.length; i++) {
374.             this.plane.splitPolygon(polygons[i], front, back, front, back);
375.         }
376.         if (this.front)
377.             front = this.front.clipPolygons(front);
378.         if (this.back)
379.             back = this.back.clipPolygons(back);
380.         else
381.             back = [];
382.         return front.concat(back);
383.     }
384.
385.     // Remove all polygons in this BSP tree that are inside the other BSP tree
386.     // `bsp`.
387.     clipTo(bsp) {
388.         this.polygons = bsp.clipPolygons(this.polygons);
389.         if (this.front)
390.             this.front.clipTo(bsp);
391.         if (this.back)
392.             this.back.clipTo(bsp);
393.     }
394.
395.     // Return a list of all polygons in this BSP tree.
396.     allPolygons() {
397.         let polygons = this.polygons.slice();
398.         if (this.front)
399.             polygons = polygons.concat(this.front.allPolygons());
400.         if (this.back)
401.             polygons = polygons.concat(this.back.allPolygons());
402.         return polygons;
403.     }
404.
405.     // Build a BSP tree out of `polygons`. When called on an existing tree, the
406.     // new polygons are filtered down to the bottom of the tree and become new
407.     // nodes there. Each set of polygons is partitioned using the first polygon
408.     // (no heuristic is used to pick a good split).
409.     build(polygons) {
410.         if (!polygons.length)
411.             return;
412.         if (!this.plane)
413.             this.plane = polygons[0].plane.clone();
414.         let front = []
415.           , back = [];
416.         for (let i = 0; i < polygons.length; i++) {
417.             this.plane.splitPolygon(polygons[i], this.polygons, this.polygons, front, back);
418.         }
419.         if (front.length) {
420.             if (!this.front)
421.                 this.front = new Node();
422.             this.front.build(front);
423.         }
424.         if (back.length) {
425.             if (!this.back)
426.                 this.back = new Node();
427.             this.back.build(back);
428.         }
429.     }
430. }
431.
432.
433. CSG.fromJSON=function(json){
434.     return CSG.fromPolygons(json.polygons.map(p=>new Polygon(p.vertices.map(v=> new Vertex(v.pos,v.normal,v.uv)),p.shared)))
435. }
436.
437. export {CSG,Vertex,Vector,Polygon,Plane}
438.
439.
440.
441. // Return a new CSG solid representing space in either this solid or in the
442. // solid `csg`. Neither this solid nor the solid `csg` are modified.
443. //
444. //     A.union(B)
445. //
446. //     +-------+            +-------+
447. //     |       |            |       |
448. //     |   A   |            |       |
449. //     |    +--+----+   =   |       +----+
450. //     +----+--+    |       +----+       |
451. //          |   B   |            |       |
452. //          |       |            |       |
453. //          +-------+            +-------+
454. //
455. // Return a new CSG solid representing space in this solid but not in the
456. // solid `csg`. Neither this solid nor the solid `csg` are modified.
457. //
458. //     A.subtract(B)
459. //
460. //     +-------+            +-------+
461. //     |       |            |       |
462. //     |   A   |            |       |
463. //     |    +--+----+   =   |    +--+
464. //     +----+--+    |       +----+
465. //          |   B   |
466. //          |       |
467. //          +-------+
468. //
469. // Return a new CSG solid representing space both this solid and in the
470. // solid `csg`. Neither this solid nor the solid `csg` are modified.
471. //
472. //     A.intersect(B)
473. //
474. //     +-------+
475. //     |       |
476. //     |   A   |
477. //     |    +--+----+   =   +--+
478. //     +----+--+    |       +--+
479. //          |   B   |
480. //          |       |
481. //          +-------+
482. //
483.
484.
RAW Paste Data

# Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!