Three.js 源码阅读 #4 基础几何体

在math文件夹下，有许多基础的几何体，其中包括 Box , Line 等，同时，还有一些比如抽象几何体将其列入，比如 Ray 。这次就来看看这部分的源码。

Line3

Three中对line的表示应该就是两个点：起点和终点，都是vec3的格式。本体是很简单的，不过给这个类添加了好多方法，就还是有一百来行的代码。这其中，大部分的代码是对两个vec3操作的包装，比如计算终点，计算delta，计算长度，计算线上一点的坐标等等，比较常规。

closestPointToPoint

这个函数计算直线上距离某点最近的点，在某些情形下做计算的时候会比较有用。这个函数首先求出参数 t ，进而根据参数和两个端点得到坐标。

closestPointToPointParameter

closestPointToPointParameter: function ( point, clampToLine ) {
    _startP.subVectors( point, this.start );
    _startEnd.subVectors( this.end, this.start );
    var startEnd2 = _startEnd.dot( _startEnd );
    var startEnd_startP = _startEnd.dot( _startP );
    var t = startEnd_startP / startEnd2;
  if ( clampToLine ) {
        t = _Math.clamp( t, 0, 1 );
    }
    return t;
}

计算参数t，稍微看下源码画个图应该还是知道的，得到投影，然后除以总长度就得到了。

Plane

平面的表示，比较符合直觉，用平面的法线和一个常数表示，文档里提到：http://mathworld.wolfram.com/HessianNormalForm.html。对于方程：,有常数，如果a, b, c都是归一化的，就是这里的d了。

setFromNormalAndCoplanarPoint

平面的法线和平面上一点表示平面，反求d，只要做个点乘取负就可以了。

setFromCoplanarPoints

三点确定一条直线。先用叉乘得到法线，然后通过法线和点就可以得到平面了。

distanceToPoint

点到平面的距离。其实就是代入方程，如果没有归一化的话还需要归一化，如此简洁的表示，但是自己经常会忘掉。

projectPoint

点投影在平面上的点，平面上距离某点最近的点。

return target.copy( this.normal ).multiplyScalar( - this.distanceToPoint( point ) ).add( point );

这个代码也很省事啊，把这个点往法线负方向偏移到平面距离的长度就到平面上了。

applyMatrix4

对平面应用变换。不过由于对于平面应用变换的时候，不能只考虑几何体，还有它的法线信息，对平面上的点应用变换矩阵，对法线应用法线的变换矩阵。关于法线的变换矩阵如何得到见源码阅读#1里的内容。

intersectLine

找出与平面交点。这个还是有些trick的。思想还是参数表示吧。在实现的时候多使用向量的一些操作，比如点乘这样的来节省运算开销。

intersectsLine

判断是否相交 这个不用找交点，只用考虑直线点的两端是不是在平面的两侧就OK了。

剩下的 intersectsBox 和 intersectsSphere 留到对应的源码里再说。

Box2

平面上的一个矩形。用两个 vector2 来表示：min和max，可以理解成，左下角的点和右上角的点
这样表示有一定的便利，比如，其对应的进行expand时候，就特别方便：

expandByPoint: function ( point ) { // 包含所有的点
    this.min.min( point );
    this.max.max( point );
    return this;
},

expandByVector: function ( vector ) {
    this.min.sub( vector );
    this.max.add( vector );
    return this;
},

expandByScalar: function ( scalar ) {
    this.min.addScalar( - scalar );
    this.max.addScalar( scalar );
    return this;
},

另一种表示方式是center和size的表示，也是两个vector2，两者的转化也相对比较直观。

getParameter

getParameter: function ( point, target ) {
    return target.set(
        ( point.x - this.min.x ) / ( this.max.x - this.min.x ),
        ( point.y - this.min.y ) / ( this.max.y - this.min.y )
    );
},

这个API还是挺奇怪的，点在box中的参数表示，以min为零点，然后范围是0-1

intersectsBox

intersectsBox: function ( box ) {
    return box.max.x < this.min.x || box.min.x > this.max.x ||
        box.max.y < this.min.y || box.min.y > this.max.y ? false : true;
},

九块区域，保证不相交的判断方式，应该是比较高效的了。

distanceToPoint

distanceToPoint: function ( point ) {
    var clampedPoint = _vector.copy( point ).clamp( this.min, this.max );
    return clampedPoint.sub( point ).length();
},

计算box到点的距离还是很巧妙的，先找到平面上的clamp point，两个一连的长度就是了。

这种min，max表示，在计算expand，计算clamp，以及计算intersect和union，都是比较方便的。

Triangle

最基础的二维物体，一半越基础，需要支持的操作也越多。

表示的话，就是三个顶点，比较直观。

在代码组织方面，有些方法名，比如 getNormal , getUV 等，分别在Triangle的属性和Triangle的原型上都写到了。在原型上的方法基本上调用属性的，相当于是一种静态方法吧。可能因为这样的函数有时候会在其它地方用到，这样不需要 this ，可以作为个静态方法来使用。

先来看几个静态方法，应该是一些基础的。

getNormal 比较常规，叉乘下就有了。

getBarycoord

重心坐标！https://zh.wikipedia.org/wiki/%E9%87%8D%E5%BF%83%E5%9D%90%E6%A0%87
源码附带的参考已经讲得很详细了：https://blackpawn.com/texts/pointinpoly/default.html
主要是数学运算，自己也不想推导，知道思想就OK了，尤其是重心坐标的表示形式。

containsPoint

这就是重心坐标的优越性了。保证三个分量都>=0.

getUV

TODO: 这个也不明白，文档里也没有说，也没有看到源码其它地方用到，到时候再看
**

isFrontFacing

判断是不是向前的面，其实就是三角形三个顶点确定的顺序，是不是和三角形的direction正负号相同。

然后看值得注意的对象的属性，也就是原型上的方法。

getArea

求面积，叉乘出来的向量模长就是两个向量张成的平行四边形的面积，除以二即可。

closestPointToPoint

跟平面不同，需要考虑是不是在点上或者在边上，因此需要分情况讨论，在判断是否在点或边上的时候用到很多trick，看来实现效率还是要花费一番功夫的。
判断在边上还是不够明白，但是能够理解思想就可以了。

closestPointToPoint: function ( p, target ) {

    var a = this.a, b = this.b, c = this.c;
    var v, w;

    // algorithm thanks to Real-Time Collision Detection by Christer Ericson,
    // published by Morgan Kaufmann Publishers, (c) 2005 Elsevier Inc.,
    // under the accompanying license; see chapter 5.1.5 for detailed explanation.
    // basically, we're distinguishing which of the voronoi regions of the triangle
    // the point lies in with the minimum amount of redundant computation.

    _vab.subVectors( b, a );
    _vac.subVectors( c, a );
    _vap.subVectors( p, a );
    var d1 = _vab.dot( _vap );
    var d2 = _vac.dot( _vap );
    if ( d1 <= 0 && d2 <= 0 ) {
        // vertex region of A; barycentric coords (1, 0, 0)
        return target.copy( a );
    }

    _vbp.subVectors( p, b );
    var d3 = _vab.dot( _vbp );
    var d4 = _vac.dot( _vbp );
    if ( d3 >= 0 && d4 <= d3 ) {
        // vertex region of B; barycentric coords (0, 1, 0)
        return target.copy( b );
    }

    var vc = d1 * d4 - d3 * d2;
    if ( vc <= 0 && d1 >= 0 && d3 <= 0 ) {
        v = d1 / ( d1 - d3 );
        // edge region of AB; barycentric coords (1-v, v, 0)
        return target.copy( a ).addScaledVector( _vab, v );
    }

    _vcp.subVectors( p, c );
    var d5 = _vab.dot( _vcp );
    var d6 = _vac.dot( _vcp );
    if ( d6 >= 0 && d5 <= d6 ) {
        // vertex region of C; barycentric coords (0, 0, 1)
        return target.copy( c );
    }

    var vb = d5 * d2 - d1 * d6;
    if ( vb <= 0 && d2 >= 0 && d6 <= 0 ) {
        w = d2 / ( d2 - d6 );
        // edge region of AC; barycentric coords (1-w, 0, w)
        return target.copy( a ).addScaledVector( _vac, w );
    }

    var va = d3 * d6 - d5 * d4;
    if ( va <= 0 && ( d4 - d3 ) >= 0 && ( d5 - d6 ) >= 0 ) {
        _vbc.subVectors( c, b );
        w = ( d4 - d3 ) / ( ( d4 - d3 ) + ( d5 - d6 ) );
        // edge region of BC; barycentric coords (0, 1-w, w)
        return target.copy( b ).addScaledVector( _vbc, w ); // edge region of BC
    }

    // face region
    var denom = 1 / ( va + vb + vc );
    // u = va * denom
    v = vb * denom;
    w = vc * denom;

    return target.copy( a ).addScaledVector( _vab, v ).addScaledVector( _vac, w );
}

**

Box3

可以从box2自然扩充到box3，不过由于加了个维度，好多操作会变复杂。
因为 Box3 这个结构在三维世界里用到很多，比如物体的AABB包围盒，因此还是有很多的和其他模块关联的地方。
比如，有 setFromBufferAttribute 函数，直接从buffer设置，提升效率。

expandByObject

通过物体张成，那其实就是物体的AABB包围盒。
思想还是简单的，就是物体的所有点张成。不过需要考虑空间的变换，这个具体的相关的变换应该在object相关代码里边，先留下TODO：

object.updateWorldMatrix( false, false ); // TODO: word matrix

在取所有点之前，先调用这个函数，不知道作用是什么，等看了源码再补上，光看文档https://threejs.org/docs/index.html#api/en/core/Object3D.updateWorldMatrix，也不是很清楚。

intersectsSphere

intersectsSphere: function ( sphere ) {
    // Find the point on the AABB closest to the sphere center.
    this.clampPoint( sphere.center, _vector );
    // If that point is inside the sphere, the AABB and sphere intersect.
    return _vector.distanceToSquared( sphere.center ) <= ( sphere.radius * sphere.radius );
},

clamp操作真滴好用，原来这样做判断与球相交。

intersectsPlane

intersectsPlane: function ( plane ) {
    // We compute the minimum and maximum dot product values. If those values
    // are on the same side (back or front) of the plane, then there is no intersection.
    var min, max;
    if ( plane.normal.x > 0 ) {
        min = plane.normal.x * this.min.x;
        max = plane.normal.x * this.max.x;
    } else {
        min = plane.normal.x * this.max.x;
        max = plane.normal.x * this.min.x;
    }
    if ( plane.normal.y > 0 ) {
        min += plane.normal.y * this.min.y;
        max += plane.normal.y * this.max.y;
    } else {
        min += plane.normal.y * this.max.y;
        max += plane.normal.y * this.min.y;
    }
    if ( plane.normal.z > 0 ) {
        min += plane.normal.z * this.min.z;
        max += plane.normal.z * this.max.z;
    } else {
        min += plane.normal.z * this.max.z;
        max += plane.normal.z * this.min.z;
    }
    return ( min <= - plane.constant && max >= - plane.constant );
},

这里边的计算还是需要值得注意的。

参考：http://what-when-how.com/advanced-methods-in-computer-graphics/collision-detection-advanced-methods-in-computer-graphics-part-3/
从上图看，其实就是检测，是不是所有的点都在一侧。这个，由于box的几何属性，只要找到距离平面最远的点，以及其对角线的点，判断两个是不是在图片的同侧就可以了。

所以源码中的种种正负值的判断也就清楚了，因为min和max两个点的坐标就包含了所有的8个点的分量，相互组合可以找到所有的点。，其中p就是最远的点，因为max中的坐标值永远比min里的坐标大，所以就可以通过法线正负值，找到最远的点和对应的对角点。

intersectsTriangle

intersectsTriangle: function ( triangle ) {
    // compute box center and extents
    this.getCenter( _center );
    _extents.subVectors( this.max, _center );

    // translate triangle to aabb origin
    _v0.subVectors( triangle.a, _center );
    _v1.subVectors( triangle.b, _center );
    _v2.subVectors( triangle.c, _center );

    // compute edge vectors for triangle
    _f0.subVectors( _v1, _v0 );
    _f1.subVectors( _v2, _v1 );
    _f2.subVectors( _v0, _v2 );

    // test against axes that are given by cross product combinations of the edges of the triangle and the edges of the aabb
    // make an axis testing of each of the 3 sides of the aabb against each of the 3 sides of the triangle = 9 axis of separation
    // axis_ij = u_i x f_j (u0, u1, u2 = face normals of aabb = x,y,z axes vectors since aabb is axis aligned)
    var axes = [
        0, - _f0.z, _f0.y, 0, - _f1.z, _f1.y, 0, - _f2.z, _f2.y,
        _f0.z, 0, - _f0.x, _f1.z, 0, - _f1.x, _f2.z, 0, - _f2.x,
        - _f0.y, _f0.x, 0, - _f1.y, _f1.x, 0, - _f2.y, _f2.x, 0
    ];
    if ( ! satForAxes( axes, _v0, _v1, _v2, _extents ) ) {
        return false;
    }

    // test 3 face normals from the aabb
    axes = [ 1, 0, 0, 0, 1, 0, 0, 0, 1 ];
    if ( ! satForAxes( axes, _v0, _v1, _v2, _extents ) ) {
        return false;
    }

    // finally testing the face normal of the triangle
    // use already existing triangle edge vectors here
    _triangleNormal.crossVectors( _f0, _f1 );
    axes = [ _triangleNormal.x, _triangleNormal.y, _triangleNormal.z ];

    return satForAxes( axes, _v0, _v1, _v2, _extents );
}

function satForAxes( axes, v0, v1, v2, extents ) {
    var i, j;
    for ( i = 0, j = axes.length - 3; i <= j; i += 3 ) {
        _testAxis.fromArray( axes, i );
        // project the aabb onto the seperating axis
        var r = extents.x * Math.abs( _testAxis.x ) + extents.y * Math.abs( _testAxis.y ) + extents.z * Math.abs( _testAxis.z );
        // project all 3 vertices of the triangle onto the seperating axis
        var p0 = v0.dot( _testAxis );
        var p1 = v1.dot( _testAxis );
        var p2 = v2.dot( _testAxis );
        // actual test, basically see if either of the most extreme of the triangle points intersects r
        if ( Math.max( - Math.max( p0, p1, p2 ), Math.min( p0, p1, p2 ) ) > r ) {
            // points of the projected triangle are outside the projected half-length of the aabb
            // the axis is seperating and we can exit
            return false;
        }
    }
    return true;
}

这个计算box和三角形的相交应该是最复杂的一个了。

首先减去center，消除box和triangle的偏移，便于处理。

然后这里用到了一个 satForAxes ，先来看一下。
SAT（Separating Axis Theorem）是一种用来检测是否相交的方法，见：http://www.dyn4j.org/2010/01/sat/
它可以用来检测两个凸包是否相交。思想是，如果能找到一个轴，使两个凸包到该轴的投影没有交集，那么就不相交，反之两者相交。
比如：

左图找到了一个轴，两个投影不相交，右图找不到这样的轴。

具体如何实现呢，我们看源码中怎么写的。
首先计算r，就是半径所在区间。然后接下来，计算三个点的投影。
这里需要注意一点，看：

if ( Math.max( - Math.max( p0, p1, p2 ), Math.min( p0, p1, p2 ) ) > r )

这个判断条件看了半天没有明白，其实，就是为了保证，不管正负，最小的绝对值肯定要大于r，这里其实还挺误解的，为什么不直接用 Math.abs() ，但其实法线，这个能保证，如果三个值里有正有负，能保证左边一定是小于零，此时条件不成立，因为extent投影的区间是[0,r]，所以，还是很精妙的。

要测试box和三角形是否有交点，就是疯狂的找出这样的轴了，能找到就说明不相交。这里选择了三种轴：

1. 3个坐标轴和3条边叉乘出来的9个
2. 3个坐标轴
3. 三角形的法线

不过为啥这些就覆盖了所有的可能性呢？
TODO：搞不懂

参考：
https://gdbooks.gitbooks.io/3dcollisions/content/Chapter4/aabb-triangle.html
https://gamedevelopment.tutsplus.com/tutorials/collision-detection-using-the-separating-axis-theorem—gamedev-169

Sphere

看完box这个三维物体之后，后续的可能都会简单一点。
圆心坐标和半径，表示上应该没有疑问。

setFromPoints

根据点得到求的方程，应该是包含所有点的球。

setFromPoints: function ( points, optionalCenter ) {
    var center = this.center;
    if ( optionalCenter !== undefined ) {
        center.copy( optionalCenter );
    } else {
        _box.setFromPoints( points ).getCenter( center );
    }

    var maxRadiusSq = 0;
    for ( var i = 0, il = points.length; i < il; i ++ ) {
        maxRadiusSq = Math.max( maxRadiusSq, center.distanceToSquared( points[ i ] ) );
    }
    this.radius = Math.sqrt( maxRadiusSq );
    return this;
}

引用文档中的话：

Computes the minimum bounding sphere for an array of points. If optionalCenteris given, it is used as the sphere’s center. Otherwise, the center of the axis-aligned bounding box encompassing points is calculated.

所以其实并不算是真正的包围球，center可能不是最优的。