Three.js 几何体二元操作插件ThreeBSP源码分析

三维几何体二元操作,可以求两个几何体的交集,并集,差集等等,是比较酷炫的功能,例如一个立方体减去一个球体得到
Three.js 几何体二元操作插件ThreeBSP源码分析
这是简单的案例,没有这个插件,也可以想象出一个立方体减去一个球体能到什么样子的三维形状,但是稍微复杂一点,就无法直接想象出来了,比如两个相同的圆柱体,互相垂直相交,求相交形成的几何体;两个相同的圆锥体相互垂直后,求他们之间的交集。

我对研究了一下开源插件ThreeBSP.js 的源码,为源码加了一些注释

(function() {
  var BACK, COPLANAR, EPSILON, FRONT, SPANNING,
  EPSILON = 1e-5;

  COPLANAR = 0;

  FRONT = 1;

  BACK = 2;

  SPANNING = 3;


  window.ThreeBSP = (function() {
    function ThreeBSP(treeIsh, matrix) {
      this.matrix = matrix;
      if (this.matrix == null) {
        this.matrix = new THREE.Matrix4();
      }
      this.tree = this.toTree(treeIsh);
    }

    ThreeBSP.prototype.toTree = function(treeIsh) {
      var polygons = [], geometry;

      if ( treeIsh instanceof THREE.Geometry ) {
        geometry = treeIsh;
      } else if ( treeIsh instanceof THREE.Mesh ) {
        // #todo: add hierarchy support
        treeIsh.updateMatrix();
        this.matrix = treeIsh.matrix.clone();
        geometry = treeIsh.geometry;
      } else if ( treeIsh instanceof ThreeBSP.Node ) {
        return treeIsh;
      } else {
        throw 'ThreeBSP: Given geometry is unsupported';
      }

      var faces = geometry.faces;
      for (var i = 0, _len = faces.length; i < _len; i++) {
        var face = faces[i];
        var faceVertexUvs = [new THREE.Vector2(), new THREE.Vector2(), new THREE.Vector2(), new THREE.Vector2()];
        if (geometry.faceVertexUvs != null) {
          faceVertexUvs = geometry.faceVertexUvs[0][i];
        }
        let polygon = new ThreeBSP.Polygon();
        let fields = ['a', 'b', 'c', 'd'];
        for (var j = 0; j < fields.length; j++) {
          if (face[fields[j]] != null) {
            var index = face[fields[j]];
            var vector = geometry.vertices[index];
            var vertex = new ThreeBSP.Vertex(vector.x, vector.y, vector.z, face.vertexNormals[0], new THREE.Vector2(faceVertexUvs[j].x, faceVertexUvs[j].y));
            vertex.applyMatrix4(this.matrix);
            polygon.vertices.push(vertex);
          }
        }
        polygons.push(polygon.calculateProperties())
      }
      var ret = new ThreeBSP.Node(polygons);
      return ret;
    };

    ThreeBSP.prototype.toMesh = function(material) {
      var geometry = this.toGeometry(),
        mesh = new THREE.Mesh( geometry, material );

      mesh.position.setFromMatrixPosition( this.matrix );
      mesh.rotation.setFromRotationMatrix( this.matrix );

      return mesh;
    };

    ThreeBSP.prototype.toGeometry = function() {
      var geometry = new THREE.Geometry();
      var matrix = new THREE.Matrix4().copy(this.matrix).invert();
      var face, polyVerts, polygon, vertUvs, verts;
      var polygons = this.tree.allPolygons();

      for (var i = 0, len = polygons.length; i < len; i++) {
        polygon = polygons[i];
        polyVerts = polygon.vertices.map(vertex => vertex.clone().applyMatrix4(matrix));

        for (var j = 2; j < polyVerts.length; j++ ) {
          verts = [polyVerts[0], polyVerts[j - 1], polyVerts[j]];
          vertUvs = verts.map(vertex => new THREE.Vector2(vertex.uv.x, vertex.uv.y));
          let indices = [];
          for (let k = 0; k < verts.length; k++) {
            indices.push(geometry.vertices.push(verts[k]) - 1);
          }
          face = new THREE.Face3(indices[0], indices[1], indices[2], polygon.normal.clone());

          geometry.faces.push(face);
          geometry.faceVertexUvs[0].push(vertUvs)
        }
      }
      return geometry;
    };

    ThreeBSP.prototype.subtract = function(other) {
      let me = this.tree.clone(), other2 = other.tree.clone();
      me.invert().clipTo(other2);
      other2.clipTo(me).invert().clipTo(me).invert();
      let ret = new ThreeBSP(me.build(other2.allPolygons()).invert(), this.matrix);
      return ret;

      // let a4 = me.invert().clipTo(other2.invert() );
      // let a3 = other2.clipTo(me);
      // let a1 = other2.clipTo(me);
      // let a2 = a1.clipTo(me).invert();
      // return new ThreeBSP(me.build(a4.allPolygons()).invert(), this.matrix);
    };

    ThreeBSP.prototype.union = function(other) {
      let me = this.tree.clone(), other2 = other.tree.clone();
      me.clipTo(other2);
      other2.clipTo(me).invert().clipTo(me).invert();
      return new ThreeBSP(me.build(other2.allPolygons()), this.matrix);
    };

    ThreeBSP.prototype.intersect = function(other) {
      let me = this.tree.clone(), other2 = other.tree.clone();
      other2.clipTo(me.invert()).invert().clipTo(me.clipTo(other2));
      return new ThreeBSP(me.build(other2.allPolygons()).invert(), this.matrix);
    };

    return ThreeBSP;

  })();

  //ThreeBSP.Vertex 点的数据集合(空间三维坐标,法向量,纹理坐标)
  ThreeBSP.Vertex = function( x, y, z, normal, uv ) {
    this.x = x;
    this.y = y;
    this.z = z;
    this.normal = normal || new THREE.Vector3();
    this.uv = uv || new THREE.Vector2();
  };
  ThreeBSP.Vertex.prototype.clone = function() {
    return new ThreeBSP.Vertex( this.x, this.y, this.z, this.normal.clone(), this.uv.clone() );
  };
  ThreeBSP.Vertex.prototype.add = function( vertex ) {
    this.x += vertex.x;
    this.y += vertex.y;
    this.z += vertex.z;
    return this;
  };
  ThreeBSP.Vertex.prototype.subtract = function( vertex ) {
    this.x -= vertex.x;
    this.y -= vertex.y;
    this.z -= vertex.z;
    return this;
  };
  ThreeBSP.Vertex.prototype.multiplyScalar = function( scalar ) {
    this.x *= scalar;
    this.y *= scalar;
    this.z *= scalar;
    return this;
  };
  ThreeBSP.Vertex.prototype.cross = function( vertex ) {
    var x = this.x,
      y = this.y,
      z = this.z;

    this.x = y * vertex.z - z * vertex.y;
    this.y = z * vertex.x - x * vertex.z;
    this.z = x * vertex.y - y * vertex.x;

    return this;
  };
  ThreeBSP.Vertex.prototype.normalize = function() {
    var length = Math.sqrt( this.x * this.x + this.y * this.y + this.z * this.z );

    this.x /= length;
    this.y /= length;
    this.z /= length;

    return this;
  };
  ThreeBSP.Vertex.prototype.dot = function( vertex ) {
    return this.x * vertex.x + this.y * vertex.y + this.z * vertex.z;
  };
  ThreeBSP.Vertex.prototype.lerp = function( a, t ) {
    this.add(
      a.clone().subtract( this ).multiplyScalar( t )
    );

    this.normal.add(
      a.normal.clone().sub( this.normal ).multiplyScalar( t )
    );

    this.uv.add(
      a.uv.clone().sub( this.uv ).multiplyScalar( t )
    );

    return this;
  };
  ThreeBSP.Vertex.prototype.interpolate = function( other, t ) {
    return this.clone().lerp( other, t );
  };
  ThreeBSP.Vertex.prototype.applyMatrix4 = function ( m ) {
    // input: THREE.Matrix4 affine matrix

    var x = this.x, y = this.y, z = this.z;

    var e = m.elements;

    this.x = e[0] * x + e[4] * y + e[8]  * z + e[12];
    this.y = e[1] * x + e[5] * y + e[9]  * z + e[13];
    this.z = e[2] * x + e[6] * y + e[10] * z + e[14];

    return this;

  }

  //ThreeBSP.Polygon 通常只包含三个点,是三角形
  ThreeBSP.Polygon = (function() {
    function Polygon(vertices, normal, w) {
      this.vertices = vertices != null ? vertices : [];
      this.normal = normal;
      this.w = w;
      if (this.vertices.length) {
        this.calculateProperties();
      }
    }

    Polygon.prototype.calculateProperties = function() {
      var a = this.vertices[0],
        b = this.vertices[1],
        c = this.vertices[2];

      this.normal = b.clone().subtract( a ).cross(
        c.clone().subtract( a )
      ).normalize();

      //this.w 表示 oa 向量在 normal上的投影
      //this.w ==  this.normal.clone().dot( b ) == this.normal.clone().dot( c )
      //a, b, c三个坐标定义的平面,沿着法线normal相反的方向移动 w 距离,则该平面正好过原点
      this.w = this.normal.clone().dot( a );

      return this;
    };

    Polygon.prototype.clone = function() {
      var i, vertice_count,
        polygon = new ThreeBSP.Polygon;

      for ( i = 0, vertice_count = this.vertices.length; i < vertice_count; i++ ) {
        polygon.vertices.push( this.vertices[i].clone() );
      };
      polygon.normal = this.normal.clone();
      polygon.w = this.w;

      return polygon;
    };

    //翻转三角面的朝向,front => back, back => front
    Polygon.prototype.invert = function() {
      this.normal.multiplyScalar( -1 );
      this.w *= -1;

      this.vertices.reverse();

      return this;
    };

    //返回当前polygon所在平面和 三维空间点vertex 的位置关系
    Polygon.prototype.classifyVertex = function(vertex) {
      //this.normal.dot( vertex ), 向量vertex在投影平面法线上的长度
      var side_value = this.normal.dot( vertex ) - this.w;

      if ( side_value < -EPSILON ) {
        return BACK;  //vertex 在平面的背面
      } else if ( side_value > EPSILON ) {
        return FRONT; //vertex 在平面的前面
      } else {
        return COPLANAR;  //vertex 几乎在平面的上
      }
    };

    Polygon.prototype.classifySide = function(polygon) {
      var i, vertex, classification,
        front = 0,
        back = 0,
        vertice_count = polygon.vertices.length;

      for ( i = 0; i < vertice_count; i++ ) {
        vertex = polygon.vertices[i];
        classification = this.classifyVertex( vertex );
        if ( classification === FRONT ) {
          front++;
        } else if ( classification === BACK ) {
          back++;
        }
      }

      if (front > 0 && back === 0) {
        return FRONT; // polygon在我前面
      }
      if (front === 0 && back > 0) {
        return BACK;  // polygon在我后面
      }
      if ((front === back && back === 0)) {
        return COPLANAR;  // polygon几乎和我同在一个平面
      }
      //我所在的平面和 polygon定义的三角面片相交,并且两平面相交产生的直线正好穿过polygon定义的三角面片
      //注意:返回FRONT,BACK 时,通常情况下我所在的平面 和 polygon所在平面是相交的,(极端情况下,是平行关系)
      // 但两平面相交产生的直线,不会穿过polygon定义的三角面片
      //设有三角面片A,三角面片B, 可能A在B前面,同时B在A后面;也可能A在B前面,同时B 和 A所在平面相交(B不在A后面)
      return SPANNING;
    };

    //以我的法向为基准,定义polygon和我的位置关系
    //coplanar_front, coplanar_back, front, back 都是输出
    Polygon.prototype.subdivide = function(polygon, coplanar_front, coplanar_back, front, back) {
      var classification = this.classifySide( polygon );

      if ( classification === COPLANAR ) {

        ( this.normal.dot( polygon.normal ) > 0 ? coplanar_front : coplanar_back ).push( polygon );

      } else if ( classification === FRONT ) {

        front.push( polygon );

      } else if ( classification === BACK ) {

        back.push( polygon );

      } else {
        var t, v,
          f = [],
          b = [];

        for (var i = 0, vertice_count = polygon.vertices.length; i < vertice_count; i++ ) {

          var j = (i + 1) % vertice_count;
          var vi = polygon.vertices[i];
          var vj = polygon.vertices[j];
          var ti = this.classifyVertex( vi );
          var tj = this.classifyVertex( vj );

          if ( ti != BACK ) f.push( vi );
          if ( ti != FRONT ) b.push( vi );
          if ( (ti | tj) === SPANNING ) {
            //参考THREE.Plane.js的源码,再画出示意图,容易看出(this.w - this.normal.dot( vi ))是vi到切割平面的最短距离
            //且符号为正,this.normal.dot( vj.clone().subtract( vi ) )为向量i->j在平面法线上的投影,符号也为正
            //vi在平面下方,vj在平面上方
            t = ( this.w - this.normal.dot( vi ) ) / this.normal.dot( vj.clone().subtract( vi ) );
            v = vi.interpolate( vj, t );
            f.push( v );
            b.push( v );
          }
        }

        if ( f.length >= 3 ) front.push( new ThreeBSP.Polygon( f ).calculateProperties() );
        if ( b.length >= 3 ) back.push( new ThreeBSP.Polygon( b ).calculateProperties() );
      }
    };

    return Polygon;

  })();

  ThreeBSP.Node = (function() {
    Node.prototype.clone = function() {
      var node = new ThreeBSP.Node();

      node.divider = this.divider.clone();  //ThreeBSP.Polygon 类型
      //node.polygons为数组类型,保存和divider几乎共面的 ThreeBSP.Polygon
      node.polygons = this.polygons.map( function( polygon ) { return polygon.clone(); } );
      node.front = this.front && this.front.clone();  //ThreeBSP.Node 类型
      node.back = this.back && this.back.clone(); //ThreeBSP.Node 类型

      return node;
    };

    function Node(polygons) {
      this.polygons = [];
      if ((polygons != null) && polygons.length) {
        this.build(polygons);
      }
    }

    //面与面之间空间位置关系来构造二叉树,构造完毕后,和divider几乎同一平面的存入this.polygons
    //若平面在divider的前方,则放入this.front(ThreeBSP.Node类型)的polygons中,或者其后代节点的polygons中
    //若平面在divider的后方,则放入this.back 的polygons中,或者其后代节点的polygons中
    //注意:当divider认为 平面和自己相交时,会拆分此平面,从而多出一些平面来
    //Node.prototype.build 更适合的名称应该为 Node.prototype.append
    //该函数有两种用法,当一个节点刚刚被 new 出来,则根据polygons来组织二叉树
    //当一个节点已经包含一些平面时,则把polygons中的元素附加到已经存在二叉树中
    Node.prototype.build = function(polygons) {
      var i, polygon_count,
        front = [],
        back = [];

      if ( !this.divider ) {
        this.divider = polygons[0].clone();
      }

      for ( i = 0, polygon_count = polygons.length; i < polygon_count; i++ ) {
        this.divider.subdivide( polygons[i], this.polygons, this.polygons, front, back );
      }

      if ( front.length > 0 ) {
        if ( !this.front ) this.front = new ThreeBSP.Node();
        this.front.build( front );
      }

      if ( back.length > 0 ) {
        if ( !this.back ) this.back = new ThreeBSP.Node();
        this.back.build( back );
      }
      return this;
    };

    Node.prototype.isConvex = function(polygons) {
      var i, j;
      for ( i = 0; i < polygons.length; i++ ) {
        for ( j = 0; j < polygons.length; j++ ) {
          if ( i !== j && polygons[i].classifySide( polygons[j] ) !== BACK ) {
            return false;
          }
        }
      }
      return true;
    };

    Node.prototype.allPolygons = function() {
      var polygons = this.polygons.slice();
      if ( this.front ) polygons = polygons.concat( this.front.allPolygons() );
      if ( this.back ) polygons = polygons.concat( this.back.allPolygons() );
      return polygons;
    };

    Node.prototype.invert = function() {
      var i, polygon_count, temp;

      for ( i = 0, polygon_count = this.polygons.length; i < polygon_count; i++ ) {
        this.polygons[i].invert();
      }

      this.divider.invert();
      if ( this.front ) this.front.invert();
      if ( this.back ) this.back.invert();

      temp = this.front;
      this.front = this.back;
      this.back = temp;

      return this;
    };

    //把polygons中的平面,用我和我后代的平面进行分割
    //polygons 中的一个平面如果在我和我后代的平面的上方,则必被保留
    //polygons 中的一个平面如果在我和我后代的平面的下方,则可能被丢弃
    Node.prototype.clipPolygons = function(polygons) {
      var back, front, poly;
      if (!this.divider) {
        return polygons.slice();
      }
      front = [];
      back = [];
      for (var i = 0, len = polygons.length; i < len; i++) {
        poly = polygons[i];
        this.divider.subdivide(poly, front, back, front, back);
      }
      if (this.front) {
        front = this.front.clipPolygons(front);
      }
      if (this.back) {
        back = this.back.clipPolygons(back);
      }
      return front.concat(this.back ? back : []);
    };

    //我的所有平面被node的所有平面 分割; 并改写this.polygons
    //clipTo不会产生全新的平面,只会从我已有的平面中去选择一部分保留下来,
    // 或者从我已有的平面中切割出一些来替换掉被切割的平面,无法无中生有的创造新平面出来
    Node.prototype.clipTo = function(node) {
      // node.clipPolygons( this.allPolygons() ); //没有改写this.polygons
      this.polygons = node.clipPolygons( this.polygons );
      if ( this.front ) this.front.clipTo( node );
      if ( this.back ) this.back.clipTo( node );
      return this;
    };

    return Node;

  })();

}).call(this);

为研究分析源码,编写的最简单的用例

<!DOCTYPE html>

<html>

<head>
<meta charset="UTF-8">
<script type="text/javascript" src="assets/three.js"></script>
<script type="text/javascript" src="assets/ThreeBSP2.js"></script>
<script type="text/javascript" src="assets/OrbitControls.js"></script>

<script type="text/javascript">
let renderer, scene, camera, light, light2;
window.onload = function() {

	renderer = new THREE.WebGLRenderer({antialias: true});
	renderer.setSize( window.innerWidth, window.innerHeight );
	document.getElementById('viewport').appendChild(renderer.domElement);

	scene = new THREE.Scene();

	light = new THREE.DirectionalLight( 0xffffff );
	light.position.set( 1, 1, 1 ).normalize();
	scene.add( light );

	light2 = new THREE.DirectionalLight( 0xffffff );
	light2.position.set( -1, -1, -1 ).normalize();
	scene.add( light2 )

	camera = new THREE.PerspectiveCamera(
		77,
		window.innerWidth / window.innerHeight,
		1,
		1000
	);
	camera.position.set( 5, 5, 5 );
	camera.lookAt( scene.position );
	scene.add( new THREE.AxesHelper(200) );

	let orbit = new THREE.OrbitControls( camera, renderer.domElement );
	let mat = new THREE.MeshLambertMaterial({
		shading: THREE.SmoothShading,
		map: new THREE.TextureLoader().load('texture.png')
	});
	let matNormal = new THREE.MeshNormalMaterial();
	let matBasic = new THREE.MeshBasicMaterial({color:"#fff", wireframe:true})

	function flatten(vertices) {
		let size = vertices[0].z != undefined ? 3 : 2;
		let arr = new Float32Array(vertices.length * size);
		let count = 0;
		vertices.forEach(vector => {
			arr[count++] = vector.x;
			arr[count++] = vector.y;
			if (size == 3)
				arr[count++] = vector.z;
		});
		return arr;
	}

	let arr1 = [{x: -2, y: 2, z:2}, {x: 1, y: 0, z:2}, {x: -2, y: -2, z:2},  {x: -2, y: 2, z:0}, {x: 1, y: 0, z:0}, {x: -2, y: -2, z:0}];
	let arr2 = [{x: 2, y: 2, z:2}, {x: 2, y: -2, z:2}, {x: -1, y: 0, z:2}, {x: 2, y: 2, z:0}, {x: 2, y: -2, z:0}, {x: -1, y: 0, z:0}];
	let uv = [{x: 0, y: 0}, {x: 1, y: 0}, {x: 0, y: 1},  {x: 0, y: 0}, {x: 1, y: 0}, {x: 0, y: 1}];
	let indices = [1,0,2, 4,5,3, 1,5,4, 1,2,5, 1,4,3, 1,3,0, 0,3,2, 2,3,5];
	let geometry1 = new THREE.BufferGeometry();
	geometry1.setIndex( indices );
	geometry1.setAttribute( 'position', new THREE.BufferAttribute( flatten(arr1), 3 ) );
	geometry1.setAttribute( 'uv', new THREE.BufferAttribute( flatten(uv), 2 ) );
	// geometry1.computeVertexNormals();
	// let mesh1 = new THREE.Mesh( geometry1, matNormal);	//matBasic
	// scene.add( mesh1 );

	let geometry2 = new THREE.BufferGeometry();
	geometry2.setIndex( indices );
	geometry2.setAttribute( 'position', new THREE.BufferAttribute( flatten(arr2), 3 ) );
	geometry2.setAttribute( 'uv', new THREE.BufferAttribute( flatten(uv), 2 ) );
	// geometry2.computeVertexNormals();
	// let mesh2 = new THREE.Mesh( geometry2, matNormal);	//matBasic
	// scene.add( mesh2 );

	let geo1 = new THREE.Geometry().fromBufferGeometry(geometry1);
	let geo2 = new THREE.Geometry().fromBufferGeometry(geometry2);
	let meshA = new THREE.Mesh(geo1, matBasic), meshB = new THREE.Mesh(geo2, matBasic);
	let bspA = new ThreeBSP( meshA );
	let bspB = new ThreeBSP( meshB );
	let subtract_bsp = bspA.subtract( bspB );
	let result = subtract_bsp.toMesh(matBasic );
	result.geometry.computeVertexNormals();
	scene.add( result );

	// let start_time = (new Date()).getTime();
	// let cube_geometry = new THREE.CubeGeometry( 3, 3, 3 );
	// let cube_mesh = new THREE.Mesh( cube_geometry );
	// cube_mesh.position.x = -7;
	// let cube_bsp = new ThreeBSP( cube_mesh );
	// let sphere_geometry = new THREE.SphereGeometry( 1.8, 32, 32 );
	// let sphere_mesh = new THREE.Mesh( sphere_geometry );
	// sphere_mesh.position.x = -7;
	// let sphere_bsp = new ThreeBSP( sphere_mesh );
	//
	// let subtract_bsp = cube_bsp.subtract( sphere_bsp );
	// let result = subtract_bsp.toMesh(matNormal );
	//
	// result.geometry.computeVertexNormals();
	// scene.add( result );
	// console.log( 'Example 1: ' + ((new Date()).getTime() - start_time) + 'ms' );

	(function render() {
		requestAnimationFrame( render );
		renderer.render(scene, camera);
	})();
}
</script>

<style type="text/css">
	html, body {
		margin: 0;
		padding: 0;
		overflow: hidden;
	}
</style>

</head>

<body>

	<div id="viewport"></div>

</body>

</html>

Polygon.prototype.subdivide 是最核心的函数,其中的切割情况,画的示意图
Three.js 几何体二元操作插件ThreeBSP源码分析
Node.prototype.clipTo也是核心函数,同时也是最难理解的,之所以编写简单的用例,就是为了理解这个函数
Three.js 几何体二元操作插件ThreeBSP源码分析

上一篇:什么是微信CRM?


下一篇:转载 | 图解WebGL&Three.js工作原理