Making a geometry from points: How to shrink wrap a convex hull around some points?

Questions
1

I’m interested in generating a geometry given a set of points that were scanned (for example scanned using lidar).

Basically something like the following, but in 3D:

concave_hull_polygon1
concave_hull_polygon11530×528 27.8 KB

Here’s another example, a library that does it in 2D:

I think that ConvexHull can get me part way there. But it will not have the concave parts. Is there some way to generate concave parts assuming some threshold of concavity? Any other ideas?

Are there any known working examples?

2

Maybe https://github.com/mikolalysenko/alpha-shape?

3

Looks limited to 2D? I do see it says “any dimension”. Maybe it means “any size on a plane”.

I found another one for 3D alpha shapes, written in R. Found the link in the Alpha Shape Wikipedia article.

Interesting article, Introduction to Alpha Shapes.

Here’s another one using Delaunay Triangulation, in the browser: Surface meshing in the browser – Nervous System blog

Here’s a 3D Delaunay Triangulator in JS with live demo. Maybe I can use this, then discard the edges I don’t need?

7

Haven’t tested it myself, but I’d be very surprised if “a set of points in some dimension” didn’t mean 2D, 3D, 4D, etc. on the alpha-shape package. The source code does look dimension-agnostic.

1 Like
8

Hmmm :thinking:, it is using delaunay-triangulate (same one linked above with 3D triangulation) under the hood. Let me investigate how to do it…

9

@donmccurdy Made a small test on Runkit. I inputted this code:

var alphaShape = require("alpha-shape")

var points = []
for(var i=0; i<10; ++i) {
  points.push([Math.random(), Math.random(), Math.random()])
}

const result = alphaShape(1, points)

console.log(result)

and the result is an array like

[[7, 0, 1], [6, 2, 0], [3, 5, 1], [0, 9, 1], [2, 9, 0], …]

with 16 items.

I can’t seem to make sense of the resulting numbers though: if the points I supplied are all between 0 and 1, why do the result points have bigger numbers like 6,2,0?

EDIT: Ah, I see, each item in the result of my example is a triangle of the resulting concave hull, where each number in the triangle represents the index into the original array of points.

For example, let’s use hard coded points:

var alphaShape = require("alpha-shape")

var points = [
    [0.9016381627581787, 0.5003897457914939, 0.11064094454278495],
    [0.6677021645723598, 0.5190459142762935, 0.4221100146124732],
    [0.5813531630779389, 0.18900966289335175, 0.9217677173114724],
    [0.865059478284703, 0.71477564849315, 0.36260754458255406],
    [0.6939529153474795, 0.753540893509971, 0.8871682472417979],
    [0.7955499479483117, 0.3198809832101075, 0.8399213925680513],
    [0.25982865736532323, 0.33538550898296315, 0.2163119470963415],
    [0.04633728090568856, 0.8991183094645228, 0.8169232630725838],
    [0.08399524814515691, 0.2571676753335388, 0.5900703744472551],
    [0.5312113415688489, 0.07245885095901672, 0.4157959075950943],
]

const result = alphaShape(1, points)

console.log(result)

// output:
// [
//     [5, 3, 0],
//     [3, 6, 0],
//     [2, 4, 5],
//     [4, 3, 5],
//     [4, 2, 7],
//     [9, 5, 0],
//     [3, 4, 7],
//     [6, 9, 0],
//     [9, 2, 5],
//     [3, 7, 6],
//     [2, 8, 7],
//     [8, 2, 9],
//     [6, 7, 8],
//     [6, 8, 9],
// ]

Then in the result, the first item, [5, 3, 0] represents the triangle made from the items in the points array at indices 5, 3, and 0, which is the following triangle:

[
    [0.7955499479483117, 0.3198809832101075, 0.8399213925680513],
    [0.865059478284703, 0.71477564849315, 0.36260754458255406],
    [0.9016381627581787, 0.5003897457914939, 0.11064094454278495],
]

(runkit example)

2 Likes
10

I guess the problem is almost solved! I’ll mark it [SOLVED] after I make a working example.

12

@trusktr how far did you manage to get with a working example of 3D alphatest geometry sets? there’s quite a large amount of npm dependencies to consider, i’ve been trying to use THREE’s ConvexGeometry() to get a detailed external shell of a model, changing convexHull.tolerance seems to have no effect on the output geometry, being the most basic outer hull of an object, alpha-shape’s ‘alpha’ property seems to have a more refinable threshold, as well as hull.js which seems to only be 2D, would you know if there’s a solution to creating more complex 3D hulls as of yet?

13

I haven’t circled back to this, as I have moved onto other projects that had higher priority.