drout

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.     }
  114.     add(a) {
  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) {
  139.         return this.add(tv0.copy(a).sub(this).times(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!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×