three.js ConvexHull 完全指南：QuickHull 三维凸包算法的实现原理与实战用法

ConvexHull 是 three.js 中用于在三维空间中计算一组点凸包的数学工具类，位于 three/addons/math/ConvexHull.js。它的核心价值在于：给出一堆散点（或整个 3D 对象树），就能得到一个最小凸多面体包围体，进而支持点在体内的判断、射线与凸体的求交，以及最典型的用途——为 ConvexGeometry 提供面片数据，把任意点云渲染成封闭的凸包网格。读完全文，你将掌握 ConvexHull 的完整 API（构造、setFromPoints、setFromObject、containsPoint、intersectRay 等），理解其底层 QuickHull 算法的初始化、horizon 边界搜索与面片更新机制，并能把它接入场景与物理仿真。

定位与算法来源

官方文档对 ConvexHull 的定位非常明确：

可用于计算给定三维点集的凸包。它主要为 ConvexGeometry 而设计。当前的 QuickHull 3D 实现移植自 Mauricio Poppe 的 quickhull3d 项目。

这与 examples/jsm/math/ConvexHull.js 源码文件头部的 JSDoc 注释完全一致。QuickHull 是 Quickhull 算法在三维情形的扩展：先取一个初始四面体作为"初始凸包"，再反复挑选位于当前凸包外表面的点，找出该点能"看到"的面所构成的 horizon（地平线）边界，删除被看到的旧面并沿 horizon 生成一批新的三角形面片，直到没有点位于凸包之外为止。

需要注意的一个前提：算法至少需要 4 个点才能构成三维凸包，这一点在 setFromPoints 中有硬性检查：

// examples/jsm/math/ConvexHull.js
setFromPoints( points ) {

    // The algorithm needs at least four points.

    if ( points.length >= 4 ) {

        this.makeEmpty();

        for ( let i = 0, l = points.length; i < l; i ++ ) {

            this.vertices.push( new VertexNode( points[ i ] ) );

        }

        this._compute();

    }

    return this;

}

导入与构造

ConvexHull 属于 addon，必须显式导入（three.js 核心包 three 不直接导出它）：

import { ConvexHull } from 'three/addons/math/ConvexHull.js';

构造函数 new ConvexHull() 本身不接收任何参数，也不立即计算——它只是初始化内部状态。查看 构造器实现 可以看到成员布局：

constructor() {

    this.tolerance = - 1;

    this.faces = []; // the generated faces of the convex hull
    this.newFaces = []; // this array holds the faces that are generated within a single iteration

    this.assigned = new VertexList();
    this.unassigned = new VertexList();

    this.vertices = []; // vertices of the hull (internal representation of given geometry data)

}

几个关键内部结构值得了解，它们直接决定了算法的性能特征：

• faces：当前凸包的三角形面片数组，是算法的核心数据。ConvexGeometry 渲染时正是遍历这个数组。
• assigned / unassigned（VertexList）：两条双向链表，分别存放"已分配到某个外表面"的顶点和"游离待分配"的顶点。顶点的归属管理通过 _addVertexToFace / _removeVertexFromFace 维护，避免每轮迭代都全量扫描所有点。
• tolerance：浮点容差，初始为 -1，在计算开始时根据点集范围自动推导（见下文"容差"小节）。
• 所有顶点先被包装成 VertexNode 存入 vertices，内部采用半边（HalfEdge）数据结构连接各个面，使 horizon 搜索可以沿边高效游走。

设置输入数据：setFromPoints 与 setFromObject

凸包计算有两种数据入口，都返回 this，支持链式调用。

setFromPoints( points )

/**
 * Computes to convex hull for the given array of points.
 *
 * @param {Array<Vector3>} points - The array of points in 3D 空间。
 * @return {ConvexHull} A reference to this convex hull.
 */

• points：三维点数组，元素为 Vector3 实例，数量至少为 4；
• 内部把每个点包成 VertexNode 后调用私有方法 _compute() 执行完整 QuickHull 流程；
• 返回值：凸包自身引用。

setFromObject( object )

这是实战中最常用的入口——从任意场景对象树批量采样顶点：

/**
 * Computes the convex hull of the given 3D object (including its descendants),
 * accounting for the world transforms of both the 3D object and its descendants.
 *
 * @param {Object3D} object - The 3D object to compute the convex hull for.
 * @return {ConvexHull} A reference to this convex hull.
 */

• object：要计算凸包的 3D 对象，包含其所有子孙节点；
• 计算会同时考虑对象与其子孙的世界变换。

从 setFromObject 的源码 可以看到它的完整采样流程：

setFromObject( object ) {

    const points = [];

    object.updateMatrixWorld( true );

    object.traverse( function ( node ) {

        const geometry = node.geometry;

        if ( geometry !== undefined ) {

            const attribute = geometry.attributes.position;

            if ( attribute !== undefined ) {

                for ( let i = 0, l = attribute.count; i < l; i ++ ) {

                    const point = new Vector3();

                    point.fromBufferAttribute( attribute, i ).applyMatrix4( node.matrixWorld );

                    points.push( point );

                }

            }

        }

    } );

    return this.setFromPoints( points );

}

要点：先 updateMatrixWorld( true ) 刷新整棵子树的矩阵，再 traverse 遍历所有节点，逐个读取 geometry.attributes.position，把每个顶点经 applyMatrix4( node.matrixWorld ) 变换到世界空间后收集，最后委托给 setFromPoints。这意味着子对象即使有位置、旋转、缩放偏移，得到的也是正确的世界坐标凸包；但只读取了 position 属性，蒙皮、形态目标等动态顶点属性不在采样范围内。

makeEmpty()

/**
 * Makes the convex hull empty.
 *
 * @return {ConvexHull} A reference to this convex hull.
 */

清空 faces 与 vertices，返回自身引用，用于复用同一个 ConvexHull 实例重新计算（setFromPoints 内部第一步也是调用它）。

点包含测试：containsPoint( point )

/**
 * Returns `true` if the given point lies in the convex hull.
 *
 * @param {Vector3} point - The point to test.
 * @return {boolean} Whether the given point lies in the convex hull or not.
 */

• point：待测试的点；
• 返回：布尔值，点是否在凸包内部。

实现 基于"凸体是所有外平面半空间的交集"这一性质：

containsPoint( point ) {

    const faces = this.faces;

    for ( let i = 0, l = faces.length; i < l; i ++ ) {

        const face = faces[ i ];

        // compute signed distance and check on what half space the point lies

        if ( face.distanceToPoint( point ) > this.tolerance ) return false;

    }

    return true;

}

对每个面计算点相对于该面平面的有向距离，只要点在任一面外侧（距离超过 tolerance）立即返回 false；全部检查通过才返回 true。复杂度与面数成线性，非常适合作为物理宽相剔除或碰撞粗检测的手段。

射线求交：intersectRay / intersectsRay

intersectRay( ray, target )

/**
 * Computes the intersections point of the given ray and this convex hull.
 *
 * @param {Ray} ray - The ray to test.
 * @param {Vector3} target - The target vector that is used to store the method's result.
 * @return {?Vector3} The intersection point. Returns `null` if not intersection was detected.
 */

• ray：待测试的 Ray 射线；
• target：用于写入结果的 Vector3（可复用，避免 GC）；
• 返回：交点 Vector3；未检测到相交时返回 null。

源码 采用的是 Eric Haines 在 GRAPHICS GEMS II 中的 "Fast Ray-Convex Polyhedron Intersection" slab 算法：把每个面当作平面，计算射线进入/穿出该平面的参数 t，用 tNear/tFar 区间收敛：

// based on "Fast Ray-Convex Polyhedron Intersection" by Eric Haines, GRAPHICS GEMS II

let tNear = - Infinity;
let tFar = Infinity;

for ( let i = 0, l = faces.length; i < l; i ++ ) {

    const face = faces[ i ];

    // interpret faces as planes for the further computation

    const vN = face.distanceToPoint( ray.origin );
    const vD = face.normal.dot( ray.direction );

    // if the origin is on the positive side of a plane (so the plane can "see" the origin) and
    // the ray is turned away or parallel to the plane, there is no intersection

    if ( vN > 0 && vD >= 0 ) return null;

    // compute the distance from the ray's origin to the intersection with the plane

    const t = ( vD !== 0 ) ? ( - vN / vD ) : 0;

    if ( t <= 0 ) continue;

    if ( vD > 0 ) {

        // plane faces away from the ray, so this plane is a back-face

        tFar = Math.min( t, tFar );

    } else {

        // front-face

        tNear = Math.max( t, tNear );

    }

    if ( tNear > tFar ) {

        // if tNear ever is greater than tFar, the ray must miss the convex hull

        return null;

    }

}

// always try tNear first since its the closer intersection point

if ( tNear !== - Infinity ) {

    ray.at( tNear, target );

} else {

    ray.at( tFar, target );

}

return target;

细节解读：

• vN 是射线起点相对平面的有向距离，vD 是射线方向与平面法线的点积；vN > 0 && vD >= 0 时起点在平面正侧且射线背向该平面（或平行），射线必然擦凸体而过，直接短路返回 null；
• 前向面（vD <= 0）抬高 tNear，后向面（vD > 0）压低 tFar；一旦 tNear > tFar，说明射线从间隙中穿过，立即判定 miss；
• 最终优先取 tNear（更近的交点）；若 tNear 仍为 -Infinity（即射线起点在凸体内），则取 tFar 作为穿出点——这解释了"点在体内时射线求交仍能返回交点"的行为，与 containsPoint 的语义互补。

intersectsRay( ray )

/**
 * Returns `true` if the given ray intersects with this convex hull.
 *
 * @param {Ray} ray - The ray to test.
 * @return {boolean} Whether the given ray intersects with this convex hull or not.
 */

只关心"是否相交"的便捷方法，内部直接复用上面的计算：

intersectsRay( ray ) {

    return this.intersectRay( ray, _v1 ) !== null;

}

其中 _v1 是模块级复用向量，无额外分配开销。

算法内幕：从极值到 horizon

setFromPoints 背后的 _compute() 流程由几个私有方法组成，理解它们有助于把握该实现的性能与数值行为。

容差 tolerance 的自动推导

_computeExtremes 在求出六个方向的极值点后，用点集的外接尺度推导容差：

// use min/max vectors to compute an optimal epsilon

this.tolerance = 3 * Number.EPSILON * (
    Math.max( Math.abs( min.x ), Math.abs( max.x ) ) +
    Math.max( Math.abs( min.y ), Math.abs( max.y ) ) +
    Math.max( Math.abs( min.z ), Math.abs( max.z ) )
);

即容差与点集坐标量级成正比，避免大坐标下浮点误差把共面点误判为"在外侧"。所有后续的距离比较（面是否可见点、顶点是否应分配到面）都以该 tolerance 为阈值。

初始四面体

_computeInitialHull 按经典三步构造初始简单体：

1. 在 x/y/z 三个方向上取一维分离最大的一对顶点 v0、v1；
2. 取到 v0–v1 直线距离最远的顶点 v2；
3. 取到 v0–v1–v2 平面距离最远的顶点 v3。

四点构成初始四面体，四个面按 v3 相对平面的朝向确定顶点绕序（保证法线朝外），并用"孪生边"（twin edge）把四个面连成封闭的半边结构。随后，其余顶点按"离哪个面最远"分配到对应面的外侧顶点链中——这就是 assigned 链表的首次填充。

horizon 搜索与面片重建

增量阶段中，_nextVertexToAdd 从 assigned 链表里挑出离所属面最远的"观察点"（eye vertex），_computeHorizon 递归地沿半边结构找出所有"一侧可见 eyePoint、另一侧不可见"的边，形成逆时针 horizon 链，同时把被看到的面标记为 Deleted 并将其外侧顶点摘入 unassigned；_addNewFaces 则沿每条 horizon 边生成新的朝外面片并首尾相连。摘除的顶点优先尝试"吸收"到新面（_deleteFaceVertices 中的 absorbingFace 分支），否则留在 unassigned 待 _resolveUnassignedPoints 重新分配——这套顶点复用机制使得迭代过程中大部分点不需要重复计算距离，是平均复杂度接近 O(n log n) 的关键。

与 ConvexGeometry 的配合：从凸包到网格

ConvexHull 的文档页开篇即说明它"主要为 ConvexGeometry 而设计"。examples/jsm/geometries/ConvexGeometry.js 是这一设计意图的直接体现——它只是 BufferGeometry 的一个薄封装，构造时把点集交给 ConvexHull，再把 convexHull.faces 展平为 position/normal 缓冲：

constructor( points = [] ) {

    super();

    const vertices = [];
    const normals = [];

    const convexHull = new ConvexHull().setFromPoints( points );

    const faces = convexHull.faces;

    for ( let i = 0; i < faces.length; i ++ ) {

        const face = faces[ i ];
        let edge = face.edge;

        // we move along a doubly-connected edge list to access all face points (see HalfEdge docs)

        do {

            const point = edge.head().point;

            vertices.push( point.x, point.y, point.z );
            normals.push( face.normal.x, face.normal.y, face.normal.z );

            edge = edge.next;

        } while ( edge !== face.edge );

    }

    this.setAttribute( 'position', new Float32BufferAttribute( vertices, 3 ) );
    this.setAttribute( 'normal', new Float32BufferAttribute( normals, 3 ) );

}

典型用法即官方 JSDoc 示例：

const geometry = new ConvexGeometry( points );
const material = new THREE.MeshBasicMaterial( { color: 0x00ff00 } );
const mesh = new THREE.Mesh( geometry, material );
scene.add( mesh );

由于每个面片法线在 QuickHull 中已经按逆时针绕序算好并朝外，ConvexGeometry 生成的网格天然带正确法线，可直接用于光照材质。文档页 ConvexGeometry 有该类的完整 API。

实际应用场景

仓库中的 examples/physics_ammo_break.html（Ammo 物理破碎示例）就使用了 ConvexHull：物理引擎（Ammo.js 的 btConvexHullShape 体系）需要把网格转换为凸形状才能参与刚体碰撞，ConvexHull 提供的点包含、射线求交等接口恰好服务于这类"用凸近似包围复杂物体"的碰撞与剔除场景。除此之外，containsPoint 与 intersectsRay 的组合也适合做：

• 相机拾取的粗检测：先用凸包判定射线是否擦过物体包围体，再决定是否做昂贵的网格级 raycast；
• 点云可视化的外壳渲染：直接 new ConvexGeometry( points ) 展示数据分布的外包；
• 场景级包围：对整棵对象子树调用 setFromObject，一次性获得考虑了世界变换的整体凸包围。

使用注意事项与小结

1. 点数量下限：少于 4 个点的输入会被 setFromPoints 静默忽略（不计算），凸包保持为空，调用方需自行保证点数。
2. 输入是快照：setFromPoints / setFromObject 采样后不会随对象后续移动自动更新，动态场景需要重新调用。
3. 复用实例：配合 makeEmpty() 可以复用同一个 ConvexHull 反复计算，减少对象创建。
4. 结果读取：faces 是公开可遍历的数组（ConvexGeometry 就这么用），但 faces 中的面片通过半边结构互相链接，只读遍历、不要手动增删。
5. 数值行为：所有判定都经过自动推导的 tolerance 滤波，点恰好落在表面上时结果依赖该容差，属于预期行为。

综上，ConvexHull 以 QuickHull 增量算法为核心，用半边结构 + 顶点链表实现了高效且数值稳健的三维凸包计算；对外则提供了 setFromPoints、setFromObject、containsPoint、intersectRay、intersectsRay、makeEmpty 一组简洁 API，并作为 ConvexGeometry 的数据源，是 three.js 中连接"散点数据 / 场景对象"与"凸包几何 / 碰撞检测"的桥梁。