Search code examples
matlabgeometrycomputational-geometry

Convert Delaunay Trinagulation to Volume

I'm trying to go from a point cloud to a volume (3D cube).

I can get a pretty good representation of the volume by making a delaunay triangulation.

How do I go from the triangulation to a 3D mat?

I'm thinking maybe test a bunch of query points and figure out if they lie inside a triangle/tetrahedron, but I can't figure out the best way to do this:

clc; clear all;
% Build a cube, in my target application this going to be from a point cloud
d = [-1 1];
[x,y,z] = meshgrid(d,d,d); % a cube
x = [x(:);0];
y = [y(:);0];
z = [z(:);0];
DT = delaunayTriangulation(x,y,z);
V=ones(size(x),'like',x);
%Build a volume from these points?
n=5;samples=linspace(-2,2);
[xq,yq,zq]=meshgrid(samples,samples,samples);
pq=[xq(:),yq(:),zq(:)];
vi = nearestNeighbor(DT,pq);
res=reshape(vi,size(xq));
%As expected, edges are messed up, not a cube...
imagesc(res(:,:,round(end/2)));
% %tetramesh(DT);
Solution

  • I think I figured it out:

    vi = nearestNeighbor(DT,pq);

    could be

    vi = pointLocation(DT,pq);

    This returns nan when the point isn't enclosed:

    Anyways, leaving this open for a while because I'm not sure my solution is optimal.

    Also this is somewhat computationally intensive.