To help you get started, we've collected the most common ways that quickhull3d is being used within popular public projects.

cruise-automation / webviz / packages / webviz-core / src / panels / ThreeDimensionalViz / commands / LinedConvexHulls.js View on Github

.map((line) => {
      // Make sure all points are in vec3 format and unique.
      const points = uniqBy(
        line.points.map((point) => (shouldConvert(point) ? pointToVec3(point) : point)),
        ([x, y, z]) => `${x}:${y}:${z}`
      );
      // We need a minimum of 4 points to do the convex hull algorithm.
      if (points.length < 4) {
        return null;
      }
      // Try to run hulling on the face indices. If there is an error, discard the result.
      let faceIndices;
      try {
        faceIndices = qh(points);
      } catch (error) {
        console.error(error);
        return null;
      }

      // From the point indices of each face, find the points and flatmap to get the points of the triangles.
      const trianglePoints = flatMap(faceIndices, ([index1, index2, index3]) => {
        return [points[index1], points[index2], points[index3]];
      });
      const convertedColor = typeof line.color.r === "number" ? line.color : vec4ToRGBA(line.color);
      return {
        pose: line.pose,
        scale: line.scale,
        color: convertedColor,
        points: trianglePoints,
        originalMarker: line.originalMarker,

View more ways to use quickhull3d

quickhull3d

A robust quickhull implementation to find the convex hull of a set of 3d points in O(n log n) ported from John Lloyd implementation

Additional implementation material:

• Dirk Gregorius presentation: https://archive.org/details/GDC2014Gregorius
• Convex Hull Generation with Quick Hull by Randy Gaul (lost link)

This library was incorporated into ThreeJS!. Thanks to https://github.com/Mugen87 for his work to move the primitives to ThreeJS primitives, the quickhull3d library will always be library agnostic and will operate with raw arrays.

Features

• Key functions are well documented (including ascii graphics)
• Faster than other JavaScript implementations of convex hull

Demo

Click on the image to see a demo!

Minimal browser demo (using v3 or above)

Installation

$ npm install --save quickhull3d

Usage

import qh from 'quickhull3d'

qh(points, options)

params

• points {Array>} an array of 3d points whose convex hull needs to be computed
• options {Object} (optional)
• options.skipTriangulation {Boolean} True to skip the triangulation of the faces (returning n-vertex faces)

returns An array of 3 element arrays, each subarray has the indices of 3 points which form a face whose normal points outside the polyhedra

isPointInsideHull(point, points, faces)

params

• point {Array} The point that we want to check that it's a convex hull.
• points {Array>} The array of 3d points whose convex hull was computed
• faces {Array>} An array of 3 element arrays, each subarray has the indices of 3 points which form a face whose normal points outside the polyhedra

returns true if the point point is inside the convex hull

example

import qh, { isPointInsideHull } from 'quickhull3d'

const points = [
  [0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 1],
  [1, 1, 0], [1, 0, 1], [0, 1, 1], [1, 1, 1]
]
const faces = qh(points)
expect(isPointInsideHull([0.5, 0.5, 0.5], points, faces)).toBe(true)
expect(isPointInsideHull([0, 0, -0.1], points, faces)).toBe(false)

Constructor

import QuickHull from 'quickhull3d/dist/QuickHull'

instance = new QuickHull(points)

params

• points {Array} an array of 3d points whose convex hull needs to be computed

instance.build()

Computes the quickhull of all the points stored in the instance

time complexity O(n log n)

instance.collectFaces(skipTriangulation)

params

• skipTriangulation {Boolean} (default: false) True to skip the triangulation and return n-vertices faces

returns

An array of 3-element arrays (or n-element arrays if skipTriangulation = true) which are the faces of the convex hull

Example

import qh from 'quickhull3d'
const points = [
  [0, 1, 0],
  [1, -1, 1],
  [-1, -1, 1],
  [0, -1, -1]
]

qh(points)
// output:
// [ [ 2, 0, 3 ], [ 0, 1, 3 ], [ 2, 1, 0 ], [ 2, 3, 1 ] ]
// 1st face:
//   points[2] = [-1, -1, 1]
//   points[0] = [0, 1, 0]
//   points[3] = [0, -1, -1]
//   normal = (points[0] - points[2]) x (points[3] - points[2])

Using the constructor:

import { QuickHull } from 'quickhull3d'
const points = [
  [0, 1, 0],
  [1, -1, 1],
  [-1, -1, 1],
  [0, -1, -1]
];
const instance = new QuickHull(points)
instance.build()
instance.collectFaces()   // returns an array of 3-element arrays

Benchmarks

Specs:

MacBook Pro (Retina, Mid 2012)
2.3 GHz Intel Core i7
8 GB 1600 MHz DDR3
NVIDIA GeForce GT 650M 1024 MB

Versus convex-hull

// LEGEND: program:numberOfPoints
quickhull3d:100 x 6,212 ops/sec 1.24% (92 runs sampled)
convexhull:100 x 2,507 ops/sec 1.20% (89 runs sampled)
quickhull3d:1000 x 1,171 ops/sec 0.93% (97 runs sampled)
convexhull:1000 x 361 ops/sec 1.38% (88 runs sampled)
quickhull3d:10000 x 190 ops/sec 1.33% (87 runs sampled)
convexhull:10000 x 32.04 ops/sec 2.37% (56 runs sampled)
quickhull3d:100000 x 11.90 ops/sec 6.34% (34 runs sampled)
convexhull:100000 x 2.81 ops/sec 2.17% (11 runs sampled)
quickhull3d:200000 x 5.11 ops/sec 10.05% (18 runs sampled)
convexhull:200000 x 1.23 ops/sec 3.33% (8 runs sampled)

License

Mauricio Poppe. Licensed under the MIT license.