[Proto] Generating Terrain from a Cloud of Points

fredo6 · 4 Dec 2014, 22:29

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

jeff hammond · 5 Dec 2014, 04:18

@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 $$

Krisidious · 5 Dec 2014, 05:58

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.

MyWork.zip

jiminy-billy-bob · 5 Dec 2014, 07:46

You do everything in pure ruby?

glro · 5 Dec 2014, 09:04

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 gets

i 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 ..."

srx · 5 Dec 2014, 09:33

As we all know this would be VERY USEFUL PLUGIN. Thank you Fredo for all you are doing.

juju · 5 Dec 2014, 09:46

This reminds me of the points cloud plugin.

http://www.crai.archi.fr/rld/plugin_details.php?id=292

Openspaces · 5 Dec 2014, 10:13

Thank you in advance for a potential lovely plugin.
Can't wait

TIG · 5 Dec 2014, 12:40

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.

fredo6 · 5 Dec 2014, 14:35

@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

fredo6 · 5 Dec 2014, 14:45

@juju said:

This reminds me of the points cloud plugin.

http://www.crai.archi.fr/rld/plugin_details.php?id=292

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_triangulation

Fredo

fredo6 · 5 Dec 2014, 14:55

@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

cotty · 5 Dec 2014, 16:40

jiminy-billy-bob · 5 Dec 2014, 17:37

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.

fredo6 · 5 Dec 2014, 19:25

@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

Anton_S · 5 Dec 2014, 20:09

Will be a useful plugin for drawing terrains!

Thank you, Fredo!

Krisidious · 5 Dec 2014, 20:43

would it not be simpler to make point clouds out of polyline topos and then compare the two?

fredo6 · 5 Dec 2014, 21:05

@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

fredo6 · 6 Dec 2014, 12:04

@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

sdmitch · 6 Dec 2014, 14:21

@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.

Alaska_NW-DTM 129.skp