Question

A convex hull class. Implements the Quickhull algorithm by: Dirk Gregorius. March 2014, Game Developers Conference: Implementing QuickHull.

Constructor

ConvexHull()

Creates a new instance of ConvexHull.

Properties

.assigned : VertexList

This vertex list holds all vertices that are assigned to a face. Default is an empty vertex list.

.faces : Array

The generated faces of the convex hull. Default is an empty array.

.newFaces : Array

This array holds the faces that are generated within a single iteration. Default is an empty array.

.tolerance : Float

The epsilon value that is used for internal comparative operations. The calculation of this value depends on the size of the geometry. Default is -1.

.unassigned : VertexList

This vertex list holds all vertices that are not assigned to a face. Default is an empty vertex list.

.vertices : Array

The internal representation of the given geometry data (an array of vertices).

Methods

.addAdjoiningFace ( eyeVertex : VertexNode, horizonEdge : HalfEdge ) : HalfEdge

eyeVertex - The vertex that is added to the hull.
horizonEdge - A single edge of the horizon.

Creates a face with the vertices 'eyeVertex.point', 'horizonEdge.tail' and 'horizonEdge.head' in CCW order. All the half edges are created in CCW order thus the face is always pointing outside the hull

.addNewFaces ( eyeVertex : VertexNode, horizonEdge : HalfEdge ) : ConvexHull

eyeVertex - The vertex that is added to the hull.
horizon - An array of half-edges that form the horizon.

Adds 'horizon.length' faces to the hull, each face will be linked with the horizon opposite face and the face on the left/right.

.addVertexToFace ( vertex : VertexNode, face : Face ) : ConvexHull

vertex - The vertex to add.
face - The target face.

Adds a vertex to the 'assigned' list of vertices and assigns it to the given face.

.addVertexToHull ( eyeVertex : VertexNode ) : ConvexHull

eyeVertex - The vertex that is added to the hull.

Adds a vertex to the hull with the following algorithm

• Compute the 'horizon' which is a chain of half edges. For an edge to belong to this group it must be the edge connecting a face that can see 'eyeVertex' and a face which cannot see 'eyeVertex'.
• All the faces that can see 'eyeVertex' have its visible vertices removed from the assigned vertex list.
• A new set of faces is created with each edge of the 'horizon' and 'eyeVertex'. Each face is connected with the opposite horizon face and the face on the left/right.
• The vertices removed from all the visible faces are assigned to the new faces if possible.

.cleanup () : ConvexHull

Cleans up internal properties after computing the convex hull.

.compute () : ConvexHull

Starts the execution of the quick hull algorithm.

.computeExtremes () : Object

Computes the extremes values (min/max vectors) which will be used to compute the inital hull.

.computeHorizon ( eyePoint : Vector3, crossEdge : HalfEdge, face : Face, horizon : Array ) : ConvexHull

eyePoint - The 3D-coordinates of a point.
crossEdge - The edge used to jump to the current face.
face - The current face being tested.
horizon - The edges that form part of the horizon in CCW order.

Computes a chain of half edges in CCW order called the 'horizon'. For an edge to be part of the horizon it must join a face that can see 'eyePoint' and a face that cannot see 'eyePoint'.

.computeInitialHull () : ConvexHull

Computes the initial simplex assigning to its faces all the points that are candidates to form part of the hull.

.containsPoint ( point : Vector3 ) : ConvexHull

point - A point in 3D space.

Returns true if the given point is inside this convex hull.

.deleteFaceVertices ( face : Face, absorbingFace : Face ) : ConvexHull

face - The given face.
absorbingFace - An optional face that tries to absorb the vertices of the first face.

Removes all the visible vertices that 'face' is able to see.

• If 'absorbingFace' doesn't exist, then all the removed vertices will be added to the 'unassigned' vertex list.
• If 'absorbingFace' exists, then this method will assign all the vertices of 'face' that can see 'absorbingFace'.
• If a vertex cannot see 'absorbingFace', it's added to the 'unassigned' vertex list.

.intersectRay ( ray : Ray, target : Vector3 ) : Vector3

ray - The given ray.
target - The target vector representing the intersection point.

Performs a ray intersection test with this convext hull. If no intersection is found, null is returned.

.intersectsRay ( ray : Ray ) : Boolean

ray - The given ray.

Returns true if the given ray intersects with this convex hull.

.makeEmpty () : ConvexHull

Makes this convex hull empty.

.nextVertexToAdd () : VertexNode

Finds the next vertex to create faces with the current hull.

• Let the initial face be the first face existing in the 'assigned' vertex list.
• If a face doesn't exist then return since there're no vertices left.
• Otherwise for each vertex that face sees find the one furthest away from it.

.reindexFaces () : ConvexHull

Removes inactive (e.g. deleted) faces from the internal face list.

.removeAllVerticesFromFace ( face : Face ) : VertexNode

face - The given face.

Removes all the visible vertices that a given face is able to see which are stored in the 'assigned' vertext list.

.removeVertexFromFace ( vertex : VertexNode, face : Face ) : ConvexHull

vertex - The vertex to remove.
face - The target face.

Removes a vertex from the 'assigned' list of vertices and from the given face. It also makes sure that the link from 'face' to the first vertex it sees in 'assigned' is linked correctly after the removal.

.resolveUnassignedPoints ( newFaces : Array ) : ConvexHull

newFaces - An array of new faces.

Reassigns as many vertices as possible from the unassigned list to the new faces.

.setFromObject ( object : Object3D ) : ConvexHull

object - Object3D to compute the convex hull of.

Computes the convex hull of an Object3D (including its children),accounting for the world transforms of both the object and its childrens.

.setFromPoints ( points : Array ) : ConvexHull

points - Array of Vector3s that the resulting convex hull will contain.

Computes to convex hull for the given array of points.

Source

examples/jsm/math/ConvexHull.js