Thursday, September 13, 2012

Delaunay Triangulation and a Plane

When reconstructing a surface especially in three dimensional, its almost inevitable that you need to generate planes based on a set of vertices. In the case, when the facets are unknown, we basically have a cloud of three dimensional points. Based on the cloud of points, our eyes may be able to tell us what the sillouette or the contour of the three dimensional model in question is; however it is quite difficult or this is not trivial and it is a well-studied problem in computational geometry.

Certainly, there are a lot of recently proposed and well-developed methodologies for estimating or reconstructing a surface based on a given cloud of points. This post is written just to provide an idea of one of the basics: delaunay triangulation.  In short delaunay triangulation is to create a triangular mesh for a set of vertices that meets the Delaunay conditions(the main idea is to prevent any surface-within-a-surface).

In matlab, it is fair easy to follow the example (provided by Matlab).  Or if you want to explore further, you can try to make a cube. Basically you just need to write down the vertices and let Matlab do its job. I will leave the readers to do this on your own.

X, Y, Z are the column vectors of a cube(meaning all the x coords, y coords and z coords, say you have 2 vertices (0,0,0) and (0,0,1), X=[0 0]; Y=[0 0]; Z=[0 1];).

> dt = delaunay(X,Y,Z); 
> trimesh(dt,X,Y,Z); 

Now, that's pretty straightforward. However, if you have a problem similar to mine, when you only want to create a 3D plane with delaunay(you have your own reasons, i don't have to tell you mine). In the above example, if you only specify one of the faces of the cube, Matlab will probably tell you that they cannot proceed because all vertices are on a plane or are co-linear.

In order to do so, you need to trick Matlab into thinking the plane is no longer a plane; basically you just have to 'extrapolate' the plane in the perpendicular direction

Originally 
X =[0 1 1 0];
Y =[0 1 1 0];
Z =[0 0 1 1];

Perturbed 
X =[ 0 1 1.01 1.01 1 0];
Y =[0 1 0.99 0.99 1 0];
Z =[0 0 0 1 1 1];

Running the same command in the previous section should give you the following rendering.

No comments:

Post a Comment