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

three.js ConvexHull 完全指南QuickHull 三维凸包算法的实现原理与实战用法【免费下载链接】three.jsJavaScript 3D Library.项目地址: https://gitcode.com/GitHub_Trending/th/three.jsConvexHull是 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/unassignedVertexList两条双向链表分别存放已分配到某个外表面的顶点和游离待分配的顶点。顶点的归属管理通过_addVertexToFace/_removeVertexFromFace维护避免每轮迭代都全量扫描所有点。tolerance浮点容差初始为-1在计算开始时根据点集范围自动推导见下文容差小节。所有顶点先被包装成VertexNode存入vertices内部采用半边HalfEdge数据结构连接各个面使 horizon 搜索可以沿边高效游走。设置输入数据setFromPoints 与 setFromObject凸包计算有两种数据入口都返回this支持链式调用。setFromPoints( points )/** * Computes to convex hull for the given array of points. * * param {ArrayVector3} 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 / intersectsRayintersectRay( 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 methods 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 rays 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是模块级复用向量无额外分配开销。算法内幕从极值到 horizonsetFromPoints背后的_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 按经典三步构造初始简单体在 x/y/z 三个方向上取一维分离最大的一对顶点v0、v1取到v0–v1直线距离最远的顶点v2取到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.htmlAmmo 物理破碎示例就使用了ConvexHull物理引擎Ammo.js 的btConvexHullShape体系需要把网格转换为凸形状才能参与刚体碰撞ConvexHull提供的点包含、射线求交等接口恰好服务于这类用凸近似包围复杂物体的碰撞与剔除场景。除此之外containsPoint与intersectsRay的组合也适合做相机拾取的粗检测先用凸包判定射线是否擦过物体包围体再决定是否做昂贵的网格级 raycast点云可视化的外壳渲染直接new ConvexGeometry( points )展示数据分布的外包场景级包围对整棵对象子树调用setFromObject一次性获得考虑了世界变换的整体凸包围。使用注意事项与小结点数量下限少于 4 个点的输入会被setFromPoints静默忽略不计算凸包保持为空调用方需自行保证点数。输入是快照setFromPoints/setFromObject采样后不会随对象后续移动自动更新动态场景需要重新调用。复用实例配合makeEmpty()可以复用同一个ConvexHull反复计算减少对象创建。结果读取faces是公开可遍历的数组ConvexGeometry就这么用但faces中的面片通过半边结构互相链接只读遍历、不要手动增删。数值行为所有判定都经过自动推导的tolerance滤波点恰好落在表面上时结果依赖该容差属于预期行为。综上ConvexHull以 QuickHull 增量算法为核心用半边结构 顶点链表实现了高效且数值稳健的三维凸包计算对外则提供了setFromPoints、setFromObject、containsPoint、intersectRay、intersectsRay、makeEmpty一组简洁 API并作为 ConvexGeometry 的数据源是 three.js 中连接散点数据 / 场景对象与凸包几何 / 碰撞检测的桥梁。【免费下载链接】three.jsJavaScript 3D Library.项目地址: https://gitcode.com/GitHub_Trending/th/three.js创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考