# 凸包([name])

凸包类。Quickhull 算法的实现者： Dirk Gregorius。2014 年 3 月，游戏开发者大会： [link:http://media.steampowered.com/apps/valve/2014/DirkGregorius_ImplementingQuickHull.pdf Implementing QuickHull]

## 引入

[name] 是一个附加组件，必须显式导入。请参阅 [link:#manual/introduction/Installation Installation / Addons].

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

## 构造函数

### [name]()

创建一个 [name] 实例。

## 属性

### [property:VertexList assigned]

该 [page:VertexList vertex list] 包含分配给面的所有顶点。默认是一个空的顶点列表。

### [property:Array faces]

生成的凸包面。默认是一个空数组。

### [property:Array newFaces]

该数组保存在单次迭代中生成的面。默认是一个空数组。

### [property:Float tolerance]

用于内部比较运算的 epsilon 值。该值的计算取决于几何形状的大小。默认值为 -1。

### [property:VertexList unassigned]

该 [page:VertexList vertex list] 包含未分配给面的所有顶点。默认是一个空的顶点列表。

### [property:Array vertices]

给定几何数据的内部表示（ [page:VertexNode vertices] 数组）。

## 方法

### [method:HalfEdge addAdjoiningFace]( [param:VertexNode eyeVertex], [param:HalfEdge horizonEdge] )

[page:VertexNode eyeVertex] - 添加到凸包的顶点。
[page:HalfEdge horizonEdge] - 地平线的单个边缘。
创建一个面，顶点顺序为 'eyeVertex.point'、'horizonEdge.tail' 和 'horizonEdge.head'，顺序为逆时针（CCW）。所有半边按照逆时针顺序创建，因此该面始终指向凸包的外部。

### [method:this addNewFaces]( [param:VertexNode eyeVertex], [param:HalfEdge horizonEdge] )

[page:VertexNode eyeVertex] - 添加到凸包的顶点。
[page:HalfEdge horizon] - 形成地平线的半边数组。
将 'horizon.length' 个面添加到凸包，每个面将与地平线上的相对面以及左/右相邻的面连接。

### [method:this addVertexToFace]( [param:VertexNode vertex], [param:Face face] )

[page:VertexNodeNode vertex] - 要添加的顶点。
[page:Face face] - 目标面。
将一个顶点添加到 “分配(assigned)” 顶点列表，并将其分配给给定的面。

### [method:this addVertexToHull]( [param:VertexNode eyeVertex] )

[page:VertexNode eyeVertex] - 添加到凸包的顶点。
使用以下算法向凸包添加顶点：

- 计算“地平线”，这是一系列半边。要使一条边属于这个组，它必须是连接一个能够看到 'eyeVertex' 的面和一个不能看到 'eyeVertex' 的面的边。
- 所有能够看到 'eyeVertex' 的面都会从已分配顶点列表中移除其可见的顶点。
- 使用“地平线”和 'eyeVertex' 的每条边创建一组新的面。每个面都与相对的地平线面以及左/右相邻的面连接。
- 从所有可见面中移除的顶点将被分配给新的面，如果可能的话。

### [method:this cleanup]()

计算凸包后清理内部属性。

### [method:this compute]()

开始执行快速凸包算法。

### [method:Object computeExtremes]()

计算将用于计算初始凸包的极值（最小/最大向量）。

### [method:this computeHorizon]( [param:Vector3 eyePoint], [param:HalfEdge crossEdge], [param:Face face], [param:Array horizon] )

[page:Vector3 eyePoint] - 点的 3D 坐标。
[page:HalfEdge crossEdge] - 用于跳转到当前面的边。
[page:Face face] - 当前正在测试的面。
[page:Array horizon] - 按 CCW 顺序构成地平线一部分的边。
计算一个逆时针(CCW)顺序的半边链，称为“地平线”（'horizon'）。要使一条边成为地平线的一部分，它必须连接一个能够看到 'eyePoint' 的面和一个不能看到 'eyePoint' 的面。

### [method:this computeInitialHull]()

计算初始的单纯形，将所有可能成为凸包一部分的点分配给其面。

### [method:this containsPoint]( [param:Vector3 point] )

[page:Vector3 point] - 3D 空间中的一个点。
返回 `true` 如果定点在此凸包内。

### [method:this deleteFaceVertices]( [param:Face face], [param:Face absorbingFace] )

[page:Face face] - 给定的面。
[page:Face absorbingFace] - 尝试吸收第一个面的顶点的可选面。
删除 “面(face)” 能够看到的所有可见顶点。

- 如果 'absorbingFace' 不存在，则所有已移除的顶点将被添加到 'unassigned' 顶点列表。
- 如果 'absorbingFace' 存在，则该方法将分配所有 'face' 中可以看到 'absorbingFace' 的顶点。
- 如果一个顶点不能看到 'absorbingFace'，则将其添加到 'unassigned' 顶点列表。

### [method:Vector3 intersectRay]( [param:Ray ray], [param:Vector3 target] )

[page:Ray ray] - 给定的射线。
[page:Vector3 target] - 表示交点的目标向量。
与该凸包执行光线相交测试。如果没有找到交集则返回 `null`。

### [method:Boolean intersectsRay]( [param:Ray ray] )

[page:Ray ray] - 给定的射线。
返回给的射线是否与此凸包相交，如果相交则返回 `true`。

### [method:this makeEmpty]()

使这个凸包为空。

### [method:VertexNode nextVertexToAdd]()

查找下一个顶点以使用当前凸包创建面。

- 让初始面成为存在于“已分配(assigned)”顶点列表中的第一个面。
- 如果面不存在则返回，因为没有顶点剩下。
- 否则，对于面能看到的每个顶点，找到距离它最远的那个。

### [method:this reindexFaces]()

从内部面列表中移除不活跃的（例如已删除的）面。

### [method:VertexNode removeAllVerticesFromFace]( [param:Face face] )

[page:Face face] - 给定的面。
移除给定面能够看到的所有可见顶点，这些顶点存储在“已分配(assigned)”顶点列表中。

### [method:this removeVertexFromFace]( [param:VertexNode vertex], [param:Face face] )

[page:VertexNode vertex] - 要删除的顶点。
[page:Face face] - 目标面。
从“已分配”顶点列表和给定面中移除一个顶点。在移除后，它还确保从“面”到它在“已分配”中看到的第一个顶点的链接被正确连接。

### [method:this resolveUnassignedPoints]( [param:Array newFaces] )

[page:Face newFaces] - 一组新的面。
尽可能从未分配的顶点列表中重新分配顶点给新的面。

### [method:this setFromObject]( [param:Object3D object] )

[page:Object3D object] - 用于计算凸包的 [page:Object3D]
计算 [page:Object3D] 的凸包（包括其子元素），考虑到对象及其子元素的世界变换。

### [method:this setFromPoints]( [param:Array points] )

[page:Array points] - 生成的凸包将包含的 [page:Vector3 Vector3s] 数组
计算给定点数组的凸包。

## 源代码

[link:https://github.com/mrdoob/three.js/blob/master/examples/jsm/math/ConvexHull.js examples/jsm/math/ConvexHull.js]