Converting convex hull to binary mask

Question

I want to generate a binary mask that has ones for all voxels inside and zeros for all voxels outside a volume. The volume is defined by the convex hull around a set of 3D coordinates (<100; some of the coordinates are inside the volume).

I can get the convex hull using CONVHULLN, but how do I convert that into a binary mask?

In case there is no good way to go via the convex hull, do you have any other idea how I could create the binary mask?

Answer 1

You can solve this problem using the DelaunayTri class and the pointLocation method. Here's an example:

pointMatrix = rand(20,3);       %# A set of 20 random 3-D points
dt = DelaunayTri(pointMatrix);  %# Create a Delaunay triangulation
[X,Y,Z] = meshgrid(0:0.01:1);   %# Create a mesh of coordinates for your volume
simplexIndex = pointLocation(dt,X(:),Y(:),Z(:));  %# Find index of simplex that
                                                  %#   each point is inside
mask = ~isnan(simplexIndex);    %# Points outside the convex hull have a
                                %#   simplex index of NaN
mask = reshape(mask,size(X));   %# Reshape the mask to 101-by-101-by-101

The above example creates a logical mask for a 101-by-101-by-101 mesh spanning the unit volume (0 to 1 in each dimension), with a 1 (true) for the mesh points inside the convex hull of the 3-D point set.

Answer 2

It's late here, so only a very sketchy suggestion:

1. With the points from your convex hull construct a Delaunay tessellation.
2. Using the pointLocation method of the DelaunayTri class test every point in your array of pixels.

I expect that this will be very slow, and that there are better solutions, if one comes in my dreams I'll post again tomorrow.

Answer 3

This is a scan conversion problem. Check out section 8 of 3D Scan-Conversion Algorithms for Voxel-Based Graphics.

The algorithm you want is the solid one, and is slightly simpler since you are voxelizing a convex polyhedron whose faces are triangles - each "voxel" run is bounded by two triangles.