Terrain modeling algorithm


I am trying to force the order of the points in a Delaunay algorithm.

I admit, I crack and I can’t, but I know that there are people here who are more talented than me in algorithms.

My goal is therefore to model a terrain using points and an elevation curve.

It is very common but I have constraints of details which exclude the usual practice.

I model terrains to make architectural models (real). So I have constraints of a few tenths.

For 10 years I have had time to try a lot of things, Hollo’s script on this forum, Ball’s or Poisson’s algorithms and even paid libraries like https://www.geom.at/.

I tried to reinterpret the behavior of PMMA and wood using Kangaroo or with other physical calculation libraries.

But none of this makes it possible to have an acceptable precision or speed of calculation to be able to use it during the phase of modeling.

Delaunay’s algorithms are the most promising I have tried. But it works in 2D.

I am strangely convinced that it is possible to adapt this algorithm in a 2.5D form.

And I’m not far from it

Errors occur when the dots are below each other

It is possible to resolve these corners by shifting the end points slightly. (What I already do on vertical cuts.)

But I have two problems with this.

Corner points are usually attached to a specific elevation that I wish I could keep
And I couldn’t find any logic to run this task using a program.
The terrains have very varied complexes which currently obliges me to detach the points one by one manually.

You can extract the code from the grasshopper component but it’s not open source and it’s too complicated. So I use a c# version of the Delaunator code of mapbox which seemed clearer to me.

Terrain.gh (133.6 KB)

Of all the tests I failed to force the algorithm to take the top points before the bottom points.
And when I get there he totally ignores the low points.
It may not be possible.

I have to admit that my job is more like a carpenter than an engineer. If anyone likes puzzles, this sounds like a good topic.

That’s an interesting situation, but your code is very long and that someone is going to reverse-engineer it is unlikely.

You have duplicated curves, you use some segment (or sub-curve) more than once and in different places, that result in “dirty” Delaunay and other problems, imho.
I would do it differently.
Create mesh > unweld > create step by moving vertexes on Z > close holes

- Create all the polylines with nothing overlapping.
- Use the polyline control points to make the Delaunay mesh.
- split the mesh where it is supposed to have a vertical wall by using some polylines, and move/edit right side vertexes differently from left side
- patch the mesh by creating vertical quad faces

See this piece of code as reference:

Hello Riccardo.

Thank you for your reply. It’s a different approach but one that makes sense.
I had already imagined injecting points into the mesh but never sectioning it.
By following your advice I will start from zero and test a version “high points → Delaunay mesh – low points → projection → cuts → displacement and filling”.

Yes, this file is a stress test. and for duplicate points the code is responsible for eliminating them.
Thanks, I think this is a good way to go.

I did not know that “UnweldEdge” doubled the points and edges.
Is it this function which takes care of cutting the mesh?
In Rhino, the UnweldEdge command does not cut the mesh.

…i did made a custom c# script to “open” the cut.

I’m giving you an idea, sadly currently i have not time to try it…

Ok, I was asking if it was the “UnweldEdge” function that allowed to cut the mesh.
I say thank you again for this idea, I think it is a good way to go.

As Riccardo pointed out, the code is quite long and deserves some explanation.

The algorithm used here is not the same as that of the Grasshopper component.
We are talking about the [Sweephull] algorithm (S-hull: a fast sweep-hull routine for Delaunay triangulation) http://www.s-hull.org/paper/s_hull.pdf
It’s very fast, removes duplicates and creates non-overlapping triangles.
It is perfect for use with large point clouds (if they can be flattened in 2D)
In comparison with the native component:

The points are sorted radially and a convex hull is generated from the center to the edge.


The principle is simple, it takes a point outside the current convex-hull and adds a triangle to it.
The convex-hull + this new triangle becomes the current convex-hull. And so on for each sorted point.

Voila. This is the reason why I am convinced that the order of the points can be hacked.

I wrote the code in a somewhat automatic and “dumb” way. But I don’t give up. )

(I made several tests by cutting the ground then filling the holes. Currently, I have very little complexity on the terrain but the Grashopper script is already getting very long. However, I haven’t optimized it yet.)