ConvexHull()

Class representing a convex hull. This is an implementation of the Quickhull algorithm based on the presentation Implementing QuickHull by Dirk Gregorius (Valve Software) from GDC 2014. The algorithm has an average runtime complexity of O(nlog(n)), whereas in the worst case it takes O(n²).

new ConvexHull()

Constructs a new convex hull.

Author:

Extends

Members

centroid :Vector3

The centroid of this polyhedron.

Overrides:

edges :Array.<HalfEdge>

A list of unique edges (no opponent half edges).

Overrides:

faces :Array.<Polygon>

The faces of this polyhedron.

Overrides:

mergeFaces :Boolean

Whether faces of the convex hull should be merged or not.

Default Value:
  • true

vertices :Array.<Vector3>

A list of unique vertices.

Overrides:

Methods

computeCentroid() → {Polyhedron}

Computes the centroid of this polyhedron. Assumes its faces have valid centroids.

Returns:
Polyhedron -

A reference to this polyhedron.

Overrides:

computeUniqueEdges() → {Polyhedron}

Computes unique edges of this polyhedron. Assumes Polyhedron#faces is properly set.

Returns:
Polyhedron -

A reference to this polyhedron.

Overrides:

computeUniqueVertices() → {Polyhedron}

Computes unique vertices of this polyhedron. Assumes Polyhedron#faces is properly set.

Returns:
Polyhedron -

A reference to this polyhedron.

Overrides:

containsPoint(point) → {Boolean}

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

Parameters:
Name Type Description
point Vector3

A point in 3D space.

Returns:
Boolean -

Whether the given point is inside this convex hull or not.

fromAABB() → {Polyhedron}

Configures this polyhedron so it does represent the given AABB.

Returns:
Polyhedron -

A reference to this polyhedron.

Overrides:

fromPoints(points) → {ConvexHull}

Computes a convex hull that encloses the given set of points. The computation requires at least four points.

Parameters:
Name Type Description
points Array.<Vector3>

An array of 3D vectors representing points in 3D space.

Returns:
ConvexHull -

A reference to this convex hull.

intersectsAABB(aabb) → {Boolean}

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

Parameters:
Name Type Description
aabb AABB

The AABB to test.

Returns:
Boolean -

Whether this convex hull intersects with the given AABB or not.

intersectsConvexHull(convexHull) → {Boolean}

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

Parameters:
Name Type Description
convexHull ConvexHull

The convex hull to test.

Returns:
Boolean -

Whether this convex hull intersects with the given one or not.