Ok, so a project coming up may require that I deal with some very large 
point clouds?

I've done a fair bit of research into this and have a few techniques and 
tools in hand that aid working with large point clouds.


I am trying to get a feel for what else is out there that I might be 
missing.

Anyone have any brain matter than they can throw out about how to work 
with large point clouds?



Thanky....  Tom

Post a reply to this message

Tom Austin wrote:
> Anyone have any brain matter than they can throw out about how to work 
> with large point clouds?

That depends quite a bit on what you want to do with them or use them for.

Post a reply to this message

Kevin Wampler wrote:
> Tom Austin wrote:
>> Anyone have any brain matter than they can throw out about how to work 
>> with large point clouds?
> 
> That depends quite a bit on what you want to do with them or use them for.

Man, I was curious!  I really am more than happy to help, it's just that 
which algorithm you want to use depends on the application.  As a 
general suggestion, spatial partitioning hierarchies (like octrees or 
kd-trees) are good when you want to quickly do operations that are 
localized around a small area in space, but that's about the most I can 
say without knowing more.

Post a reply to this message

Kevin Wampler wrote:
> Kevin Wampler wrote:
>> Tom Austin wrote:
>>> Anyone have any brain matter than they can throw out about how to 
>>> work with large point clouds?
>>
>> That depends quite a bit on what you want to do with them or use them 
>> for.
> 
> Man, I was curious!  I really am more than happy to help, it's just that 
> which algorithm you want to use depends on the application.  As a 
> general suggestion, spatial partitioning hierarchies (like octrees or 
> kd-trees) are good when you want to quickly do operations that are 
> localized around a small area in space, but that's about the most I can 
> say without knowing more.

Sorry about the delayed response - been VERY busy lately and have not 
had much other time.  I guess given the economic climate this is a good 
thing.


Essentially I am using a 3D laser based scanner to gather portions of 
mine tunnels.  The scanner gathers data as points in a spherical format.

   I estimate that there will be ~150 separate scans totaling ~30 
million points.


I currently deal with the scans only as point clouds.

I have methods to align the scans.

I can put all of the points into one large point cloud that has 30 
million points.



What I am looking for is:


Methods or programs to 'simplify' the resulting point cloud so that it 
still is a fair representation of the overall area, but has much fewer 
points ~300k.

Methods or programs to create a single mesh of the resulting point cloud 
that can represent tunnels.



I've 2D draped for a mesh before - that's no problem.  It's the 3D 
meshing of arbitrary points that I have not experienced yet.

I'm pretty good about taking an approach (steps or algorithm) and 
putting them into code.



If you would like more info just ask questions and I will provide what I 
can.

I might be able to dig up some past work that is similar to what I am 
trying to do.



Tom

Post a reply to this message

Tom Austin wrote:
> 
> Methods or programs to 'simplify' the resulting point cloud so that it 
> still is a fair representation of the overall area, but has much fewer 
> points ~300k.
> 
> Methods or programs to create a single mesh of the resulting point cloud 
> that can represent tunnels.
> 


That's a nifty problem! I might have some ideas, but first I have a few 
questions about it:

* I'm talking it that each scan was done from a different location, so 
while each individual scan can be represents a `spherical' cloud of 
points the union of the scans does not?

* I assume that the final goal is the mesh and that the first task is 
just needed so that the resulting mesh is relatively small?  I ask 
because if so then it might be reasonable to generate a large mesh and 
then simplify it later, which would allow different algorithms.

* In terms of simplifying the point cloud/mesh, what are the accuracy 
requirements of the simplification with respect to the density of the 
point cloud from the scans?  In other words, if the scans are very dense 
but you don't actually need that sort of accuracy in the mesh/simplified 
cloud then you can probably get away with simpler algorithms than if you 
need really high resolution in some areas and can only get away with 
discarding points which don't contribute anything useful to the 
geometry.  For instance, would it be sufficient to simplify the point 
cloud by simply discarding all points which are within, say 10cm, of 
each other?

* Have you tried existing approaches for generating a mesh from a point 
cloud?  If so, did they not work because you have too many points for 
them to operate effectively?

Post a reply to this message

Am Tue, 17 Feb 2009 11:44:49 -0800 schrieb Kevin Wampler:

> 
> * Have you tried existing approaches for generating a mesh from a point
> cloud?  If so, did they not work because you have too many points for
> them to operate effectively?

Maybe you are looking for something else (and I didn't understood the 
question), but I think, I was wondering about this problem 7 years ago 
(56K modem - wow it has been some time :))

http://news.povray.org/povray.newusers/thread/<3c62e3dc%
40news.povray.org>/

Post a reply to this message

Am Tue, 17 Feb 2009 11:52:47 -0500 schrieb Tom Austin:

> 
> Methods or programs to create a single mesh of the resulting point cloud
> that can represent tunnels.
> 

Have you thought about Voronoi tesselation? That could give you a basic 
mesh, if you cut away the outer layers.

Post a reply to this message

Kevin Wampler wrote:
> Tom Austin wrote:
>>
>> Methods or programs to 'simplify' the resulting point cloud so that it 
>> still is a fair representation of the overall area, but has much fewer 
>> points ~300k.
>>
>> Methods or programs to create a single mesh of the resulting point 
>> cloud that can represent tunnels.
>>
> 
> 
> That's a nifty problem! I might have some ideas, but first I have a few 
> questions about it:
> 

It's actually pretty fun - if only I had lots of time to work on it!


> * I'm talking it that each scan was done from a different location, so 
> while each individual scan can be represents a `spherical' cloud of 
> points the union of the scans does not?
> 

Yes - exactly



> * I assume that the final goal is the mesh and that the first task is 
> just needed so that the resulting mesh is relatively small?  I ask 
> because if so then it might be reasonable to generate a large mesh and 
> then simplify it later, which would allow different algorithms.
> 

a possible final result is a mesh

I may use an AutoCAD 3D solid or just the simplified points themselves.

I am still interested in what may work on meshes as opposed to points as 
the final product may be a mesh.


> * In terms of simplifying the point cloud/mesh, what are the accuracy 
> requirements of the simplification with respect to the density of the 
> point cloud from the scans?  In other words, if the scans are very dense 
> but you don't actually need that sort of accuracy in the mesh/simplified 
> cloud then you can probably get away with simpler algorithms than if you 
> need really high resolution in some areas and can only get away with 
> discarding points which don't contribute anything useful to the 
> geometry.  For instance, would it be sufficient to simplify the point 
> cloud by simply discarding all points which are within, say 10cm, of 
> each other?
> 

That's some of what I've been thinking about - simplifying where 
possible, and providing some more detail where the *object* is more complex.

I would like to figure out a relatively simple method of simplifying the 
mesh so that the actual work involved is low - even if processing time 
is high.




> * Have you tried existing approaches for generating a mesh from a point 
> cloud?  If so, did they not work because you have too many points for 
> them to operate effectively?

Honestly, I have not worked with anything to make a 3D mesh out of a 
*unified* pointcloud of several scans.

I have made meshes out of 2D point clouds (terrain) made from several scans.

I have made 3D meshes with only 1 scan (somewhat easy).




I'll try to make some time tomorrow to post a video of what I have done 
in the past so that you can get a better idea.







Tom

Post a reply to this message

Tom Austin wrote:
> 
> a possible final result is a mesh
> 
> I may use an AutoCAD 3D solid or just the simplified points themselves.
> 
> I am still interested in what may work on meshes as opposed to points as 
> the final product may be a mesh.
> 

It will almost certainly be simpler to avoid attempting to reconstruct a 
mesh unless you want to use some third-party software or you have a lot 
of time to work on it (which as I understand you don't).  Fortunately 
there is some free software you can try. Although I've never used any 
myself and haven't looked into the licensing requirements I suspect most 
are only available for personal use.

This one is pretty recent, and should be able to handle large number of 
points pretty efficiently:

http://students.cs.tamu.edu/jmanson/programs_wavelet_reconstruct.html


This one is based on some relatively recent work from from MSR and 
should also be able to manage large numbers of points:

http://research.microsoft.com/en-us/um/people/hoppe/proj/mlstream/


The software here is a bit older but might be useful (links at bottom of 
page):

http://grail.cs.washington.edu/projects/scanning/


> 
> That's some of what I've been thinking about - simplifying where 
> possible, and providing some more detail where the *object* is more 
> complex.
> 
> I would like to figure out a relatively simple method of simplifying the 
> mesh so that the actual work involved is low - even if processing time 
> is high.

The conceptually simplest way to do this would be to generate a 
high-detail mesh from the points and then simplify the mesh, so if you 
can get a third-party mesh reconstruction algorithm to work that's a 
good possibility.

I'll still see if I can think of a good mesh-free simplification 
algorithm in case you can't generate a mesh.

Post a reply to this message

Florian Pesth wrote:
> Am Tue, 17 Feb 2009 11:44:49 -0800 schrieb Kevin Wampler:
> 
>> * Have you tried existing approaches for generating a mesh from a point
>> cloud?  If so, did they not work because you have too many points for
>> them to operate effectively?
> 
> Maybe you are looking for something else (and I didn't understood the 
> question), but I think, I was wondering about this problem 7 years ago 
> (56K modem - wow it has been some time :))
> 
> http://news.povray.org/povray.newusers/thread/<3c62e3dc%
> 40news.povray.org>/

I actually remember that conversation and was wondering about it!  The 
problems that are being solved are very similar, but it fortunately 
looks like there's more software available now for constructing the meshes.

Post a reply to this message