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

A convex-hull is, by definition, 2D. Perhaps you mean a convex polyhedron?

Let your structure of your algorithm be thus:

int pixelMap[][] = zeroes(NUM_HORIZ_PIXELS,NUM_VERT_PIXELS);
for(int xpxl = 0; xpxl < NUM_HORIZ_PIXELS; xpxl++) {
    for(int ypxl = 0; ypxl < NUM_VERT_PIXELS; ypxl++) {
       float xcoord = getXCoordForPixel(xpxl);
       float ycoord = getYCoordForPixel(ypxl);
       if(withinHull(xcoord,ycoord)) {
           pixelMap[xpxl][ypxl] = 1;
       } // end if
    } // end for y
} // end for x

Now you need to define your getCoord functions (which are just converting from screen-space to real-space, and are pretty straightforward) and your withinHull function.

Because you're dealing with 2d, it's pretty much safe to assume that your hull will end up being 2d - even if it's 3d, you'll wind up with it's 2d projection on the plane you're dealing with anyway. For algorithms for creating a hull from a set of points, see http://en.wikipedia.org/wiki/Convex_hull_algorithms (I remember learning the D&C algorithm in uni).

Once you have your 2d hull defined, you should be able to treat it as a polygon. From here, you can use a polygon intersection test to determine if your coordinates passed fall within the polygon. An easy one is to pick a point known to be outside the polygon, make a line between the coords given and your known outside point, and test intersection against each line of the polygon. Even number of intersections means point is not in the polygon, odd number means it is in the polygon. This algorithm also works for non convex polygons too, in case you ever need it again.

Matlab may or may not have some of these functions predefined (line intersection, polygon representation, etc.)

cheers!

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

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 4

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.