Author |
Topic: Constructing approximate surface for point cloud (Read 1158 times) |
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
 |
Constructing approximate surface for point cloud
« on: Aug 13th, 2010, 4:43am » |
 Quote  Modify
|
I'm looking for some useful approaches to constructing an approximate surface on a point cloud. There may be tens of thousands of points in the cloud, and they do not only lie close to the surface (so it's not like reconstructing a surface from a laserscan of a 3D object).
I'm not looking for a convex hull (unless the cloud happens to be convex), but for some 'smoothed' surface that best approximates the 'real' surface (in as far as you can speak of it) using a triangulated network with a given number of vertices (or perhaps within a certain range).
One approach I've considered is first approximating the cloud as an object built from cubes, then construct a triangulation on the outside surface of the cube-approximated object, and then let the resultant network converge to a better fit using a similar approach to that in a Kohonen network. However, one of the problems I'm facing is that the last step would require knowing the points on the surface of the cloud, and I can't think of a good way to find them.
So, does anyone have any ideas?
|
|
 IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
MathsForFun
Full Member
Posts: 153
|
|
Re: Constructing approximate surface for point clo
« Reply #1 on: Aug 13th, 2010, 5:37am » |
Quote Modify
|
I think that cubes are a good idea.
If I may switch to 2 dimensions to aid my own thinking: put the cloud in a rectangle, and replace each point with a square (the 2d equivalent of a cube) which is opaque. If a cube can "see" any point on the rectangle, then count it as a surface point.
The larger the squares, the smoother the surface will be.
|
|
IP Logged |
Everything is interesting if you look at it closely enough
|
|
|
MathsForFun
Full Member
Posts: 153
|
|
Re: Constructing approximate surface for point clo
« Reply #2 on: Aug 13th, 2010, 6:09am » |
Quote Modify
|
Again, working in 2d: suppose, in the middle of a field, some rods were sticking up out of the ground. One way to approximate the 2d surface would be for 2 people to hold a long string: one of them would stand still, while the other, with the string at full stretch, would walk around the rods. Each time the string touched a rod, that rod would be defined as "surface", and the string would rotate around that rod (or you could think of that rod as being the new endpoint for the string). Continue until all rods are enclosed by the string (or the string revisits the first surface rod).
In 3d, the geometry would be trickier, because the string (a line) becomes a sheet (a plane).
|
|
IP Logged |
Everything is interesting if you look at it closely enough
|
|
|
MathsForFun
Full Member
Posts: 153
|
|
Re: Constructing approximate surface for point clo
« Reply #3 on: Aug 13th, 2010, 6:47am » |
Quote Modify
|
Again, working in 2d: how about:
Code:make a square that encloses the cloud (the outer square)
while (not happy) {
divide each square into four squares
for each square {
if ((square contains no points) and ((square touches outer square) or (square touches discarded square))) then
discard square
}
} |
|
The remaining squares form the cloud.
|
|
IP Logged |
Everything is interesting if you look at it closely enough
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Constructing approximate surface for point clo
« Reply #4 on: Aug 13th, 2010, 7:30am » |
Quote Modify
|
Your second idea seems similar to the ball-pivotting algorithm. I'm not quite sure how I'd go about implementing that though.
Additionally, the algorithm is patented by IBM, which would make it problematic to use in an application.
|
| « Last Edit: Aug 13th, 2010, 7:31am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
MathsForFun
Full Member
Posts: 153
|
|
Re: Constructing approximate surface for point clo
« Reply #5 on: Aug 13th, 2010, 8:09am » |
Quote Modify
|
on Aug 13th, 2010, 7:30am, towr wrote:| Your second idea seems similar to the ball-pivotting algorithm. I'm not quite sure how I'd go about implementing that though. |
|
How about simulating a net being thrown around the cloud? The dynamics of each hole in the net need not be correct (though the holes need to remain connected to each other correctly). A net hole would stop advancing if a point passed through it.
|
|
IP Logged |
Everything is interesting if you look at it closely enough
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Constructing approximate surface for point clo
« Reply #6 on: Aug 13th, 2010, 12:43pm » |
Quote Modify
|
One problem with that is that it wouldn't work well on a cup-like cloud (i.e. with a large deep cavity). Although if you start with a decent initial shape it might work. But how to detect when a point moves through a hole? (Bearing in mind that if you move one hole, or one point, the surrounding holes also move.)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
MathsForFun
Full Member
Posts: 153
|
|
Re: Constructing approximate surface for point clo
« Reply #7 on: Aug 13th, 2010, 12:43pm » |
Quote Modify
|
Again, in 2d: how about a chain around the cloud?
Put a rectangle around the cloud, and lower a line from the top. The first point it meets will be the first link in the chain. Each time a "link" (a short line) is added to the chain, it starts at the end of the previous link, and its angle is calculated on the basis of nearby points. The chain thus becomes the surface of the cloud.
|
|
IP Logged |
Everything is interesting if you look at it closely enough
|
|
|
MathsForFun
Full Member
Posts: 153
|
|
Re: Constructing approximate surface for point clo
« Reply #8 on: Aug 15th, 2010, 12:53am » |
Quote Modify
|
This is "blue sky" thinking - I don't know whether it would work or not - but how about constructing a graph from the points by connecting each point to its 5 (or 10 or whatever works) nearest neighbours? Having done this, here are a couple of possible ideas to find surface points:
1. average length of connecting edges will be above the average for all the points
2. the average shortest tour (counting number of edges traversed) from the point to a nearest neighbour, and then back to itself without using the same edge twice, will be longer
|
|
IP Logged |
Everything is interesting if you look at it closely enough
|
|
|
MathsForFun
Full Member
Posts: 153
|
|
Re: Constructing approximate surface for point clo
« Reply #9 on: Aug 15th, 2010, 1:31am » |
Quote Modify
|
Working id 2d: how about counting a point as surface if its 1 centimetre circle has a 10 degree sector that is free of other points?
|
|
IP Logged |
Everything is interesting if you look at it closely enough
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Constructing approximate surface for point clo
« Reply #10 on: Aug 15th, 2010, 6:50am » |
Quote Modify
|
on Aug 15th, 2010, 1:31am, MathsForFun wrote:| Working id 2d: how about counting a point as surface if its 1 centimetre circle has a 10 degree sector that is free of other points? |
|
Do you perhaps mean 100 degrees? Because 10 is a bit small.
So in 3D that would be a cone; but how to easily out whether there is such an empty adjacent space? I'm not even sure how I'd find out whether there's a plane through a point such that all points (in a certain sized neighbourhood) fall on just one side (which ought to be easier, although it's not a sufficient criterion).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
MathsForFun
Full Member
Posts: 153
|
|
Re: Constructing approximate surface for point clo
« Reply #11 on: Aug 15th, 2010, 8:35am » |
Quote Modify
|
on Aug 15th, 2010, 6:50am, towr wrote:| Do you perhaps mean 100 degrees? Because 10 is a bit small. |
|
The angle is obviously not my decision to make - I'm just enjoying being creative - but what if the surface had a hollow in it?
Quote:| So in 3D that would be a cone; but how to easily out whether there is such an empty adjacent space? I'm not even sure how I'd find out whether there's a plane through a point such that all points (in a certain sized neighbourhood) fall on just one side (which ought to be easier, although it's not a sufficient criterion). |
|
I would create a database structure and put each point into a small cube (I might consider using a high-speed open-source in-memory database to save me from having to think about issues like data structure and indexing). Then for each cone in the sphere around a point, I would calculate which cubes might contain other points. Then I would only have to check whether the points in those cubes are within the cone - which would reduce the job to a manageable size.
|
|
IP Logged |
Everything is interesting if you look at it closely enough
|
|
|
MathsForFun
Full Member
Posts: 153
|
|
Re: Constructing approximate surface for point clo
« Reply #12 on: Aug 15th, 2010, 9:02am » |
Quote Modify
|
on Aug 15th, 2010, 6:50am, towr wrote:| I'm not even sure how I'd find out whether there's a plane through a point such that all points (in a certain sized neighbourhood) fall on just one side (which ought to be easier, although it's not a sufficient criterion). |
|
That sounds as though it could be resolved very quickly by linear programming.
Important caveat - double check that everything is linear first: on several occasions, I have spent quite some time encoding a puzzle in a linear programming model, only to discover a non-linearity.
Here's how I think it can be done, though (roughly - it's for you to work out the details. Also, for simplicity, this description is in 2d).
* define a square that encloses the points of interest
* build a linear programming model to draw a line from the left side of the square to the right as low as possible, and under which all the points lie. If the line is low enough, then accept it as a surface line
A couple of points:
1. you cannot measure the area above the line, because that would entail multiplying variables - which is not possible in linear programming. I would consider minimising the y value of the line where it meets the left of the box plus the y value of the line where it meets the right of the box
2. if lowest line top-to-bottom didn't work, then you may also need to test for the highest line bottom-to-top. You might also need to do the same thing on the x axis - right-to-left and left-to-right
|
|
IP Logged |
Everything is interesting if you look at it closely enough
|
|
|
MathsForFun
Full Member
Posts: 153
|
|
Re: Constructing approximate surface for point clo
« Reply #13 on: Aug 15th, 2010, 4:26pm » |
Quote Modify
|
on Aug 15th, 2010, 9:02am, MathsForFun wrote:| * build a linear programming model to draw a line from the left side of the square to the right as low as possible, and under which all the points lie. If the line is low enough, then accept it as a surface line |
|
My compulsiveness got the better of me: for points in the range [0,0] to [5,5], the LP Solve model below will calculate a line which all the points are below, and which will minimise x0+x5, where x0 is the y value when x=0, and x5 is the y value when x=5:
Code:min: intercept + Y5Intercept;
// given 2 points, slope = (y2 – y1) / (x2 - x1)
dividend = Y5Intercept - intercept;
// divisor = 5
slope = 0.2 dividend;
/* points (0<x<5, 0<y<5): [0.1, 3], [4.7, 0.4], [4.8, 0.3]*/
0.1 slope + intercept >= 3;
4.7 slope + intercept >= 0.4;
4.8 slope + intercept >= 0.3;
free slope, intercept, Y5Intercept, dividend; |
|
All you have to do now is:
1. convert the model to 3d
2. encode it 6 times (2 directions in each dimension)
3. choose cube sizes
4. decide what value of x0+x5 gives a reasonable probability of being a surface
5. apply other criteria to decide whether it is a surface or not
IMO, even with a lot of points, the LP Solve DLL will be able to calculate the dividing planes for you very quickly - giving you a good return on CPU time.
|
|
IP Logged |
Everything is interesting if you look at it closely enough
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print