[Proto] Generating Terrain from a Cloud of Points
-
@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.
-
Sam,
Thanks very much, very useful.
Actually, I have tweaked the algorithm and got the tarrain below. So I think I may finally find heuristics to speed up the interpolation.
There are 1986 cloud points.
The terrain is generated with 3069 triangles. The calculation took 18.5 seconds on my machine.
It seems to be a quite large area and quite flat except a few hill and an overall gentle slope. I had to scale in Z a little bit however to make the relief more apparent.
sdmitch_ Alaska_NW-DTM 129 _ trg.skp
Indeed, if you are more samples, this is welcome
Fredo
-
Fredo,
These models have much more relief. They are bigger with many more points than you would normally use probably. But none of the projects I worked on were small.
Sam
-
Fredo if you want, this is a text file of a pair of Scissor handles that I recently managed to import into SU using the above mentioned Points Cloud as a CSV file of over 250,000 points.
It was very slow but worked and I was able to view the scissors in 3D as guide points. I didn't bother with triangulating the faces as it had actually taken several hours to import just the points.
It is without doubt overkill in the terrain context but it is the type of file people will be wanting, if not expecting, to be able to click, copy and 3d print in the very near future. Feel free to ignore it as it was something I found on the web while looking to solve terrain and point cloud imports.
-
I think it will depend on it's capability for detail. I don't find getting the raw terrain down is very difficult. It is all the detail that has to be built into it...i.e. garden beds, curbs, sidewalks, ditches, medians, grass edge transitions,...etc. For every minute I spend creating the ground, I spend ten on the detail.
-
Sam,
Thanks for the new models. There are a little big for the plugin, but I made some trials on a subset and it seems to be OK.
Below with 101 source points, generating roughly 3900 triangles to render the cliffs in 23 seconds.
Fredo
-
@unknownuser said:
I think it will depend on it's capability for detail. I don't find getting the raw terrain down is very difficult. It is all the detail that has to be built into it...i.e. garden beds, curbs, sidewalks, ditches, medians, grass edge transitions,...etc. For every minute I spend creating the ground, I spend ten on the detail.
My feeling is that it is better to generate first the natural terrain and then superimpose the artificial 'details', like limits, fences, roads, building.
Of course, these details may deserve some dedicated techniques (in particular roads and fences), but Sketchup has already a number of tools to handle many cases, with the Sandbox and with Projection and PushPull plugins.
I don't think it's easy (and fast enough anyway) to have interpolation generate the terrain and all details in one shot.
Fredo
-
"to have interpolation generate the terrain and all details" I agree that would be a trick. I use your wonderful tools-on-surface (and a couple other rubies) to build terrain. I can't guess how many square miles. I do believe your tools are the best. I am saying for me at least generating a terrain with cloud point is not very exciting. It would be selfish to say I would rather a talent like you work on other things.
-
@box said:
Fredo if you want, this is a text file of a pair of Scissor handles that I recently managed to import into SU using the above mentioned Points Cloud as a CSV file of over 250,000 points.
It was very slow but worked and I was able to view the scissors in 3D as guide points. I didn't bother with triangulating the faces as it had actually taken several hours to import just the points.
It is without doubt overkill in the terrain context but it is the type of file people will be wanting, if not expecting, to be able to click, copy and 3d print in the very near future. Feel free to ignore it as it was something I found on the web while looking to solve terrain and point cloud imports.LIDAR and other techniques generating dense cloud of points require very different techniques.
- First this is usually true 3D (not 2.5D like terrain).
- Second, there is no real need of interpolation, but triangulation with the nearest neighbours.
I imagine there exists dedicated applications written for this purpose, in C++ or so to be extremely scalable. Obviously, that won't be the case for Sketchup and Ruby!
Fredo
-
@roland joseph said:
I am saying for me at least generating a terrain with cloud point is not very exciting. It would be selfish to say I would rather a talent like you work on other things.
I think that generation of terrain is an essential feature for Sketchup, not to say that making organic shapes from control points can be useful too.
Actually, this is not something simple to develop in Ruby, because of the lack of efficient algorithms and the variety of topological situation. So nothing straightforward in this plugin project.Fredo
Advertisement