Path: news.mathworks.com!not-for-mail
From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: 3D surface recon from point cloud
Date: Wed, 30 Jan 2008 22:57:02 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 45
Message-ID: <fnqvbu$mvm$1@fred.mathworks.com>
Reply-To: <HIDDEN>
NNTP-Posting-Host: webapp-02-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1201733822 23542 172.30.248.37 (30 Jan 2008 22:57:02 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Wed, 30 Jan 2008 22:57:02 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1264951
Xref: news.mathworks.com comp.soft-sys.matlab:448426



Hello

I have been working on a project to do a surface 
reconstruction from a point cloud.  I am writing my code 
in Matlab and using the algorithm described by Hoppe et 
al.  

Step 1: finding k neighbors and using principal component 
analysis to find a center and a normal for the plane.

Step 2: Orienting the normals: this is where I am having 
some difficulty.  I am generating a Euclidean minimum 
spanning tree in 3d based on the algorithm described at 
wikipedia.  Basically, first calculating Delaunay 
triangulation to calculate edges (distance between 
points).  Then starting from the point with highest z, I 
am using prim&#8217;s algorithm to generate the EMST.  Once, I 
have the EMST, I am orienting the normal&#8217;s to point 
outward.  

Step 3:  Surface Contouring:  I am planning to use the 
marching cube algorithm but haven&#8217;t written the code yet.

The step 2 seems to work fine for small set of data points 
(sample data points up to 100-200) but when I try it with 
the actual data set (~20000 points), it seems to take it 
forever.  I have let it run for over 8 hours without 
getting any results.  Even if it is working, I don&#8217;t think 
it is acceptable.  I am sure the surface contouring part 
will be computationally long as well.  So, my question is 
that are there any tricks that other have been using for 
orienting the normals of the tangent planes.  Or are there 
any already existing functions for this?

My other question is about surface contouring.  I feel 
confident that if I can get the normal orientation right, 
I should be able to do this by a brute force marching cube 
algorithm.  But, I would like to use the iso-surface 
function of the matlab instead of writing the whole new 
code to generate facets information.  Any helpful pointers 
there?

Many thanks,
Ashish