 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> 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.
This might be useful:
http://en.wikipedia.org/wiki/Delaunay_triangulation
How accurate are your points? If there is some noise in them you might want
to work on that before creating the mesh (eg using some nearest neighbour
averaging scheme). If they are all pretty accurate then just generate the
mesh first from the points, then simplify the mesh afterwards.
For simplifying the mesh there are probably some known algorithms, but you
could start by just merging smallest triangles with similar normals etc,
maybe even some 3D modellers like Blender have some functions for
simplifying meshes?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Kevin Wampler wrote:
>
> 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/
>
>
I uploaded a video of what I am talking about.
to some this should look familiar as I posted it in the animation group
a while back.
www.stineconsulting.com/s/anim_large.mpg
This is the type of environment that I will be dealing with. Tho the
are will be much larger - more tunnels.
The data in this example is 9 scans located at the red spheres, total
about 2 million points. Each scan was individually converted into a
POV-Ray mesh and all 9 meshes were rendered together. You can see where
the meshes overlap
As you can see, near the scanner locations, the detail is very high
(lots of points) and away from the locations the data is more sparse. -
the nature of spherical data gathering.
Ideally I would be able to simplify all 9 scans into one thinned point
cloud that may have about 30K points in it - then mesh the point cloud.
I have routines that will 'simplify' large point clouds, but once they
are combined, I don't have methods to make a mesh from the resulting
point cloud.
Imagine if the animation that I posted were simplified into 1 point per
foot, then made into one mesh and rendered.
Note: my goal is not necessarily to get the stuff into POV-Ray - but
into any mesh format that I can manipulate.
I appreciate the tips and info that you've already thrown out. I'll be
looking into them closer as time allows.
Tom
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Tom Austin wrote:
>
> www.stineconsulting.com/s/anim_large.mpg
>
Nice! Looking at the video it seems that the only thing which you're
lacking are tools to manage the merged point clouds -- it sounds like
you can both mesh and simplify the individual scans perfectly well. Is
this assessment correct?
If so, is not not sufficient to get a simplified point cloud for the
entire scene by just merging the simplified clouds for each scan? You'd
get some redundant data on the overlap, but I wouldn't think that would
increase the point count too dramatically.
With regards to generating a mesh, are you satisfied with the quality of
the meshes generated from the single scans? If so, then it would
probably be much easier to clean up the seams when merging them than to
generate a mesh from scratch (unless, of course, one of the tools I
linked to solves everything for you).
I suppose my main question is that since it looks from the video like
you have a somewhat reasonable solution already, what about it isn't
satisfactory?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Kevin Wampler wrote:
> Tom Austin wrote:
>>
>> www.stineconsulting.com/s/anim_large.mpg
>>
>
> Nice! Looking at the video it seems that the only thing which you're
> lacking are tools to manage the merged point clouds -- it sounds like
> you can both mesh and simplify the individual scans perfectly well. Is
> this assessment correct?
>
Yes, creating a mesh from a single scan is somewhat easy - there is a
point of view from which to 'look' at the data and make triangles.
> If so, is not not sufficient to get a simplified point cloud for the
> entire scene by just merging the simplified clouds for each scan? You'd
> get some redundant data on the overlap, but I wouldn't think that would
> increase the point count too dramatically.
>
I think I have some fairly good ideas on how to simplify a point cloud -
I was just wondering if anyone had more meat to add to the feast.
So, handling point clouds isn't too big of a deal.
> With regards to generating a mesh, are you satisfied with the quality of
> the meshes generated from the single scans?
Not really. Areas close to the scanner are very dense with data, areas
far away are rather sparse. I would like to 'even' out the point
distribution. Say a point per foot type thing. I'm not after
'creating' data in the far away places - but I defiantly need to thin
the data that is up close.
If I do anything more than remove rows and column from the spherical
data set I start to lose my point of view and it becomes more difficult
to generate meshes using the methods that I have.
If so, then it would
> probably be much easier to clean up the seams when merging them than to
> generate a mesh from scratch (unless, of course, one of the tools I
> linked to solves everything for you).
>
If making everything a mesh, then merging the meshes gives me a good
result, I am not opposed to going that way.
I've always worked with the points, and then made something from the
points. But it seems that I can work with meshes and if I need to, make
points from the mesh.
> I suppose my main question is that since it looks from the video like
> you have a somewhat reasonable solution already, what about it isn't
> satisfactory?
To use the video as an example, I would like to have a fairly ordered
distribution of data. If you look close to the red spheres, you will
see very dense data - too dense to even be useful. If I could merge all
of the data into something like a 1 food cells, that would be great.
My end goal is to have something that is manageable on a normal PC (as
opposed to a souped up one) - likely in a AutoCAD format. The amount of
data in the video does not lend itself to that.
IIRC, the video is about 1000 frames with an hour to generate each frame
in POV-Ray.
I just don't have the experience to make meshes from what seems to be an
unordered point cloud. - That's what I am really after.
Thanks for your interest and help - I really appreciate it.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Ahh, I finally think I understand.
First off, making meshes from unordered point clouds is a well-studied
but tricky problem, and it's probably not worth attempting to solve
yourself unless you really want to spend some time on it. The best bet
if you want to go with this approach is to try the software I linked or
look for other existing packages (google for `point cloud mesh' or
`point cloud reconstruction' or something like that).
Since you have well ordered meshes for each scan the easiest way to go
if you're writing your own software is almost certainly to operate on
the individual scans as meshes and then merge them at the end. Since
(as I understand it) the structure of the scans is essentially a wrapped
rectangular grid, like the intersection of the latitude and longitude
lines on a globe, the process to simplify a scan mesh is almost
identical to those used in LOD (level of detail) terrain
simplifications. You can google it for more info, but time permitting
I'll see if I can whip up some example code for you to look at in the
next few days.
Simplifying the point clouds themselves is relatively simple to do
(depending on how smart you want to make the simplification process),
but if you want a mesh at the end it's probably easier just to stick
with meshes throughout.
On another note, this commercial software looks like it may do what you
want as well:
http://www.3dreshaper.com/en1/En_software.htm
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Kevin Wampler wrote:
> I'll see if I can whip up some example code for you to look at in the
> next few days.
I was a bit busier than I expected, but here's some code which will
(hopefully) do something similar to what you want. It's in Python and
you'll need pyopengl to run it. Once the window pops up, hit 'h' or '?'
to print the list of available commands. I've also tried to commend the
code a lot, but I can clarify things if they're still unclear.
Let me know if you can get it to work or not, if it seems to do what you
want, and if there's anything else I can help with.
Post a reply to this message
Attachments:
Download 'us-ascii' (20 KB)
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Kevin Wampler wrote:
> Kevin Wampler wrote:
>> I'll see if I can whip up some example code for you to look at in the
>> next few days.
>
> I was a bit busier than I expected, but here's some code which will
> (hopefully) do something similar to what you want. It's in Python and
> you'll need pyopengl to run it. Once the window pops up, hit 'h' or '?'
> to print the list of available commands. I've also tried to commend the
> code a lot, but I can clarify things if they're still unclear.
>
> Let me know if you can get it to work or not, if it seems to do what you
> want, and if there's anything else I can help with.
>
Kevin,
what can I say - you've gone way above and beyond what I have expected
anyone to do. You must be really excited about this stuff.
I've been pretty busy myself lately, but I have been able to look over
the programs that you presented - I especially like the one from
washington.edu - but some of the others look very promising as well.
The code that you posted is great - humbles me greatly in my knowledge
of 3D and data handling. It is much appreciated. I will try to work it
in this week to take a look at it.
What can I do in return for your help?
Maybe some of the 3D data that I have lying around?
Tom
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Tom Austin <taustin> wrote:
> If making everything a mesh, then merging the meshes gives me a good
> result, I am not opposed to going that way.
As a quick guess, I'd expect this approach to be the most performant (though
this doesn't say whether it will be easy to implement). After all, you don't
have to re-assemble your meshes from scratch, but just "weave" them together.
Some nice properties of this approach:
- You don't have to bother about points in the same mesh, except for the few
direct neighbors (which are already known) in this mesh.
- You typically don't even have to bother about many points in the other mesh:
Typically you will already have "weaved in" one or two neighboring points,
which gives you a nice start where to insert the next point into the combined
mesh.
The only tricky thing is where to start, but an algorithm to find *some* pair of
fairly close points should be possible to come up with. Octrees come to my mind
here - or just plain user interaction: Pick any point in mesh A for which you
know that mesh B has points nearby, then just brute-force search through mesh B
for the nearest neighbor. And there you go.
For reducing the sample resolution, one very naive (but possibly sufficient)
approach would be to just search the mesh for any faces (or edges) with an area
(or distance) below a certain threshold, and collapse them to a point.
More sophisticated approaches would of course collapse the smallest ones first,
but maybe that's not even necessary for your purposes.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Tom Austin wrote:
> what can I say - you've gone way above and beyond what I have expected
> anyone to do. You must be really excited about this stuff.
Every year I like doing a few small free-time programing projects just
so I can get some variety in what I code and some of the quick
gratification that comes form finishing a small project. This seemed to
be a pretty fun problem to choose for one of them!
> I've been pretty busy myself lately, but I have been able to look over
> the programs that you presented - I especially like the one from
> washington.edu - but some of the others look very promising as well.
I hope they work well -- the algorithms will certainly by much more
sophisticated than what I wrote.
> The code that you posted is great - humbles me greatly in my knowledge
> of 3D and data handling. It is much appreciated. I will try to work it
> in this week to take a look at it.
I am too flattered by your kind words. If you have any trouble
understanding any piece of the code. The data structure I used was a
binary triangle tree similar to that employed by the ROAM algorithm:
http://www.cognigraph.com/ROAM_homepage/
> What can I do in return for your help?
> Maybe some of the 3D data that I have lying around?
No need to worry about repaying me in any way, I wouldn't have done it
if I didn't enjoy it. If I do end up having a use for some 3D laser
scan data, however, I'll let you know!
Actually, wait, I can think of one thing. How about, if you get
something nice working for this project, you post a small video so I can
see what it ended up looking like?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
