Thread Subject: 3D surface recon from point cloud

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’s algorithm to generate the EMST. Once, I
have the EMST, I am orienting the normal’s to point
outward.

Step 3: Surface Contouring: I am planning to use the
marching cube algorithm but haven’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’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

Can you send me a reference to this paper?
I have a bunch of 2-D data points of a hallway in my
building (laser scanner mounted on robot with SLAM). And
I want to plot it as a wireframe model of the hall way.

Is this the type of algoirthm you would have to use? or
is there an easy way to do this?

"Ashish A" <aashi6uf@mathworks.com> wrote in message
<fnqvbu$mvm$1@fred.mathworks.com>...
> 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’s algorithm to generate the EMST. Once, I
> have the EMST, I am orienting the normal’s to point
> outward.
>
> Step 3: Surface Contouring: I am planning to use the
> marching cube algorithm but haven’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’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
>