computing 3D reduced convex hull

Question

I'm looking for an algorithm that provides what I call a "shrunken convex hull" (as distinct from a "reduced convex hull") in 3D. I am defining the shrunken hull, H', as the volume of space that has, no less than D distance from some original convex hull, H.

Analytically, this can be formed by moving each plane of H inwards along its normal by D, then computing the convex hull (if it exists) of the resultant planes. The tricky bit is some planes might be trimmed or dropped, others may move past other planes, and get entirely "snipped" out due to normal reversal (if D is big enough). I’m a bit fuzzy on how to do the algorithm, but have some badly thought out ideas below.

I am doing this to to identify the subset of points in a dataset which are guaranteed to be no less than a given distance from the surface of the original point set (which is assumed to be convex, and I have this). This is to remove surface effects that are disrupting our signal in some calculations we are doing.

I'm really looking for a name, or examples of anyone doing this, or another way to compute this. Ideally some good-old open code would be great, but I think my problem is far too niche.

I found reduced convex hulls, but this seems to be a different idea. The current closest thing I can find is "Hausdorff Cores" - however this seems like the more complicated case of non-convex polygons, and is pretty damned dense.

---

Do not read beyond here, unless you really really want to.

Current, incomplete/badly thought out algorithm

The slow way (i.e. current way) of identifying the reduced point set it is to compute the signed distance for all points, and reject those that are less than a given distance. However, this is pretty damned slow, as the number of points can be up to 100M. I think operating on the original hull to generate the shrunken hull, and computing its AABB and spherical BB, then retaining only those inside the shrunken hull might be much faster (I hope -willing to accept comments saying this is stupid).

I think it should be possible, as I don't strictly need the full distance information for each point, just D_point > D. So once I know this I should be able to stop.

I can see how the shrunken hull might be done in 2D, where you look at each vertex, then use an analytical solution to a constant velocity Eikonal, then move the vertex along the vector derived from each corner.

However, the situation is more complex for the 3D version, afaics, as there are multiple facets (>2) for each vertex . My current plan is to look at each edge pair individually, then work from there to (somehow - create half spaces and union them?) to build this hull.

Answer 1

What your thinking of is downscaling the 3D convex hull, it works just like downscaling a 2D image, except for how the angle

Outline for the algorithm (in 2D) looks something like this:

1. Compute the convex hull.
2. For each point, P, in the convex hull:
3.     Find the hull points before and after, P
4.     Bisect the angle formed to obtain the angle, A, required.
5.     Create a new point, P', along the angle A at a distance, D, from `P`.
7.     Add P' to the scaled-down (shrunken) convex hull.

The only difference in 3D occurs in lines 3 and 4. In 3D, step 3 obtains 3 points. In step 4, a 3D angle is used. Thus you'll find a fair bit of benefit in using the 3D transforms in a graphics/geometry libary, as the math may be tricky.

Answer 2

If your objective is to remove surface effects, and it's not important that every surface of the convex hull be displaced by the same distance, you could instead

1. Identify a point known to be inside the hull (e.g. the centroid of the point cloud or the hull)
2. Scale the hull inward towards that point

Unless you scale infinitely (collapsing everything to a point), this operation should give an inwardly-displaced hull which has the same connectivity - no points added or removed.