AABB
AlignmentBehavior
ArriveBehavior
AStar
BFS
BoundingSphere
BVH
BVHNode
Cell
CellSpacePartitioning
CohesionBehavior
CompositeGoal
ConvexHull
Corridor
CostTable
DFS
Dijkstra
Edge
EntityManager
EvadeBehavior
EventDispatcher
Behavior
FollowPathBehavior
FuzzyAND
FuzzyCompositeTerm
FuzzyFAIRLY
FuzzyModule
FuzzyOR
FuzzyRule
FuzzySet
FuzzyTerm
FuzzyVariable
FuzzyVERY
GameEntity
Goal
GoalEvaluator
Graph
GraphUtils
HalfEdge
HeuristicPolicyDijkstra
HeuristicPolicyEuclid
HeuristicPolicyEuclidSquared
HeuristicPolicyManhattan
InterposeBehavior
LeftSCurveFuzzySet
LeftShoulderFuzzySet
LineSegment
Logger
MathUtils
Matrix3
Matrix4
MemoryRecord
MemorySystem
MeshGeometry
MessageDispatcher
MovingEntity
NavEdge
NavMesh
NavMeshLoader
NavNode
Node
NormalDistFuzzySet
OBB
ObstacleAvoidanceBehavior
OffsetPursuitBehavior
OnPathBehavior
Path
Plane
Polygon
Polyhedron
PriorityQueue
PursuitBehavior
Quaternion
Ray
RectangleTriggerRegion
Regular
RightSCurveFuzzySet
RightShoulderFuzzySet
SAT
SeekBehavior
SeparationBehavior
SingletonFuzzySet
Smoother
SphericalTriggerRegion
State
StateMachine
SteeringBehavior
SteeringManager
Task
TaskQueue
Telegram
Think
Time
TriangularFuzzySet
Trigger
TriggerRegion
Vector3
Vehicle
Version
WanderBehavior

build

描述

build 方法用于构建 BVH 节点树。

语法

BVHNode.build(primitives, options);

参数

  • primitives:可连接的物体列表,每个物体应该有一个 getBoundingBox 方法来返回该物体的边界框。
  • options:可选参数对象,可以包含以下子属性:
    • maxDepth:BVH 树的最大深度,默认为 50
    • minOverlap:节点之间的最小重叠面积比例,用于划分节点,默认为 0.2

返回值

返回一个 BVHNode 对象,表示 BVH 树的根节点。

示例

var primitives = [object1, object2, object3, ...];
var rootNode = BVHNode.build(primitives, {
  maxDepth: 60,
  minOverlap: 0.1
});

异常

  • 如果 primitives 参数是空数组,则抛出 TypeError 异常。
  • 如果 primitives 列表中的任何物体不包含 getBoundingBox 方法,则抛出 TypeError 异常。

实现细节

BVH 树的构建过程是一个递归过程,从根节点开始,将物体列表分为两个部分,分别构建左右子树,然后将其作为当前节点的子节点。划分物体列表的过程可以使用多种算法,包括:

  • SAH (Surface Area Heuristic) 算法。
  • Median Split 算法。
  • Object Median 算法。 在 Yuka 库中使用了 SAH 算法来构建 BVH 树,该算法计算了每个空间区域(节点)的表面积,并根据最小化表面积和体积之比来划分物体列表。对于深度超过 maxDepth 的节点,将使用 Object Median 算法(也称为叶节点 Bucket Sorting)来构建该节点。最后,一些优化技巧被用来提高建树的速度和效率,包括旋转贡献计算(通过计算平均重心)以及重新排序物体列表等。