[Proto] Generating Terrain from a Cloud of Points
-
I am working on the generation of smooth terrain from a cloud of points.
As you all know, there is no single solution to this problem, especially when the point cloud only contains a few points.
At this stage, I am investigating various interpolation algorithms and came up with a first generator of mesh with:
- adaptive triangular mesh, allowing some control of the smoothing
- original points are always on the surface generated
- some control of the 'roundness' of the terrain
- a boundary contour can be defined to clip the mesh
This is illustrated in the short video below
The bad news however is that the algorithm is very sensitive to the number of points. Above 50 points, it starts to take long, minutes or more. Not to insist that it cannot be used on Lidar data (which would require a different algorithm).
For instance, the terrain below is based on 207 points, with lot of sharp hills. The generation took more than 20 minutes on my machine.
So it seems to me that the technique can be used to shape terrains from a few points, which, with some habits, could possibly be used to generate organic shapes based on a few control points.
For the time being, I am interested by some 'real' point clouds to see if the generation gives something acceptable in real life where the resulting terrain is roughly known.
So if some kind users could post here or PM me some samples, that would help me to assess the relevance of the algorithms.
Thanks in advance
Fredo
-
@fredo- you could of written your own app by now
(joking.. but still)
i don't have any example clouds but maybe you could find some stuff via 'add location' (and add points) that will be acceptable for testing?
fwiw, i can also imagine this tool being helpful for refurb/remodels/etc when existing floors and whatnot are out of whack.. with today's lasers, it's pretty cheap and easy for a builder to get a set of spot checked points which could then be run through this plugin in order to have a truer representation of the existing conditions.
ultimately, scanning the space would be the best but as of right now, that's big time $$
-
here's some files from when I worked at a survey company. some of them are probably point clouds. I'll have to research to find out which. maybe you'll know by looking.
-
You do everything in pure ruby?
-
interesting research
For organic modeling, it is promising
but if someone looks for accuracy, there is no solution:
to be more accurate, you need more points
the more points ruby has to process, the slower it getsi noticed sketchup ruby gets very slow when the amount of data to process increases
[anchor= goto=:2xytkhdb]http://sketchucation.com/forums/viewtopic.php?f=323&t=59921#p548175[/anchor:2xytkhdb]and my experience is that it is getting worse with sketchup updates; SU8 is much faster than SU14
my guess is that the memory is managed more to make fast render, than answering to ruby questions as "if..., for e in ..."
-
As we all know this would be VERY USEFUL PLUGIN. Thank you Fredo for all you are doing.
-
This reminds me of the points cloud plugin.
-
Thank you in advance for a potential lovely plugin.
Can't wait
-
A land 'survey' of 'points' will typically use many 'key-points' - taken at clear changes of material, slope, plane etc - and then a general grid of other points - perhaps 5m sq...
If you link the 'key-points' by clines are they respected in the smoothed mesh's 'edges' ?How does it cope with points that are coincident in xy but have differing z values? - e.g. where a retaining-wall has coincident top and bottom points varying only in their z - I know the delauney algorithm chokes !
The ability to survey in proper 3d [wall-planes etc], rather than the pseudo-3d from a surveyed 'surface' cloud would be a great step forward. -
@tig said:
A land 'survey' of 'points' will typically use many 'key-points' - taken at clear changes of material, slope, plane etc - and then a general grid of other points - perhaps 5m sq...
If you link the 'key-points' by clines are they respected in the smoothed mesh's 'edges' ?Then, I think it's better to use TopoShaper with the iso-contours. What can however be added is a small plugin to link the points of similar altitudes to form these iso-contours.
If the points don't have similar altitudes, then we need to use Constrained Delaunay triangulation. Manageable, but again, it requires more calculation and thus takes longer.@tig said:
How does it cope with points that are coincident in xy but have differing z values? - e.g. where a retaining-wall has coincident top and bottom points varying only in their z - I know the delauney algorithm chokes !
The ability to survey in proper 3d [wall-planes etc], rather than the pseudo-3d from a surveyed 'surface' cloud would be a great step forward.Delaunay and many Terrain tools works in XY and interpolate the Z altitude. So walls, cliffs and other quasi vertical structure won't be welcome. Actually, In skecthup, it may be easier to manage first the natural terrain and then introduce the artificial structures by stamping and then push pull or via dedicated tools (plane road paths for instance).
More generally, I think there are powerful dedicated tools for terrain shaping. So plugins for Sketchup and Sandbox could only be a helper for simple cases.
Fredo
-
@juju said:
This reminds me of the points cloud plugin.
Yes, this one is the mother of all triangulation scripts (based on Delaunay), but I think it only generates the first-level triangulation.
By the way, I think TIG adpated the script to run in recent versions of Sketchup. See http://sketchucation.com/pluginstore?pln=TIG_points_cloud_triangulationFredo
-
@jiminy-billy-bob said:
You do everything in pure ruby?
Yes. This is pure Ruby. This is fine for small number of points.
I am actually quite impressed by the speed of Ruby. But indeed, with more calculations, it gets' slower.
The problem I have is that the Interpolation I use is O(M)O(N2), where M is the number of vertices of the triangulation and N is the number of cloud points. So no mystery, it does not scale well. Other interpolations don't give good results
The only possibility I see is to convert 2 calculation methods from Ruby to C (each method is 20 lines) hoping that it would speed up a little bit the calculation.
But I am too lazy to set up a C development environment, learn the C-Ruby bridging and make it work on PC and Mac!
Note that he triangulation is OK in Ruby. I can manage the calculation 10,000 triangles within 25 seconds, so it can stay in Ruby.
Fredo
-
-
I really recommend doing stuff in C++. Ruby was already pretty fast, but I've seen improvements up to 100 times faster. It's really worth it.
-
@jiminy-billy-bob said:
I really recommend doing stuff in C++. Ruby was already pretty fast, but I've seen improvements up to 100 times faster. It's really worth it.
Sure, that's a possibility to explore. With compilation it might be much faster, because the methods are pure calculation within a loop.
But even before I take care of performance, I must first evaluate if the algorithms are relevant for real terrains, which is the reason for my post at this stage.
Fredo
-
Will be a useful plugin for drawing terrains!
Thank you, Fredo!
-
would it not be simpler to make point clouds out of polyline topos and then compare the two?
-
@krisidious said:
would it not be simpler to make point clouds out of polyline topos and then compare the two?
Good idea and actually I did it and obtain similar shapes, but a little rounder with the triangulator.
The probleme however is that using iso contour cloud points is already a strong guide to the skeleton of the terrain and therefore does not validate that with scarce points here and there you would obtain a similar skeleton.
Toposhaper is based on a linear interpolation whereas Triangulator is based on a directional polynomial interpolation, in order to avoid that each point of the cloud becomes an isolated hill or basin.
Anyway, I am not trying to demonstrate that an algorithm can find the good solution because this is anyway wrong mathematically. There are always many solutions.
Instead, I am just trying to check if the plugin would be useful to users and landscapers on real cases.
Fredo
-
@krisidious said:
here's some files from when I worked at a survey company. some of them are probably point clouds. I'll have to research to find out which. maybe you'll know by looking.
I would need something in SKP. I have no Tools to pre-process and I don't even know what are the files.
Fred
-
@fredo6 said:
@krisidious said:
here's some files from when I worked at a survey company. some of them are probably point clouds. I'll have to research to find out which. maybe you'll know by looking.
I would need something in SKP. I have no Tools to pre-process and I don't even know what are the files.
Fred
Attached is a skp file with both mass points and break lines that you can hopefully use for testing. I have hundreds of such models if you want or need more.
Advertisement