1
\$\begingroup\$

I'm currently trying to randomly generate obstacles in the hyperbolic plane. Obstacles are polygons with holes, in a hole there can be other obstacles. The hyperbolic plane term is unimportant for my question. I just want you to know that, for generating these obstacles, I'm limited to only use a Delaunay triangulation.

Until now, I've implemented a basic algorithm, it uniformly assigns every vertex of the triangulation a number from -1 to 1, then each face of the triangulation is set to be part of an obstacle (the boolean "in_domain"), if the average of the values of its three vertices is bigger than some threshold. After this initial assignment of the in_domain values, I iterate several times through the faces of the triangulation and if a face has the opposite in_domain value than its two neighboring faces, it changes its in_domain value. From the in_domain values, we can infer our obstacles.

Results look like the following: Starting with a Delaunay triangulation on 10k vertices

There are some parameters that I can adjust to get other "kinds of terrain", for example the number of vertices in the Delaunay triangulation is the "level of detail" and increasing the threshold parameter for the faces to decide if they are obstacle or not, gives more obstacles. The problem is that the results look fragmented, the only smoothing that happens is what I describes above: if a triangle has two neighbors that are obstacle, the triangle gets part of an obstacle too. Without the "smoothing" it would look like this: enter image description here

So I'm looking for a way to go from a Delaunay triangulation to a smooth looking terrain, perlin noise would be perfect, it would induce "good" values for every vertex, so that neighboring vertices in a certain radius all have roughly the same value, and from these values I could assign each triangle whether it's an obstacle or not. But as I searched the internet, I couldn't find any implementations of perlin noise in the hyperbolic plane. But you see, that my problem is that I want to propagate high/low vertex values to its neighboring vertices, to get less fragmented terrain. I also thought about choosing a vertex and then assigning each neighboring face that it is part of an obstacle, then take all neighboring vertices of that vertex and do it again with a certain probability and so on. So that, I do some k-nearest vertices searches and turn all neighboring faces of this vertex set into obstacles. But than obstacles would probably look too circular.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ I don't know if there are any standard algorithms, but I can certainly think of a couple of things to try. Are there particular output criteria (larger blobs, fewer holes, more maze-like, etc.) you have in mind? \$\endgroup\$ Commented Nov 5, 2024 at 22:33
  • \$\begingroup\$ Blobs would be great. Some parameters would be cool, but in a systematic way. The way I have it right now feels too arbitrary, many parameters but their impact isn't that clear. The use case is to apply some shortest path/visibility algorithms on the polygonal domain. So if you have any idea, I would be glad to hear it! \$\endgroup\$ Commented Nov 5, 2024 at 23:01
  • 2
    \$\begingroup\$ I'd recommend editing your question to focus more narrowly on what you want the algorithm to achieve, and establishing the criteria by which we should judge which answers better achieve your goals. \$\endgroup\$ Commented Nov 6, 2024 at 0:51

1 Answer 1

Reset to default
2
\$\begingroup\$

The hyperbolic aspect is bigger factor than lead suggests because as you've discovered, it presents a significant challenge to using Perlin / Simplex noise. Those functions are one of the first things I would try for making procedurally generated blob shapes.

Those functions are useful in this context because they have a good balance between randomness and continuity. By continuity, I mean that there aren't a lot of abrupt changes and the values in a very local region tend to be similar (as opposed to say sampling directly from random noise). But because of the randomness, they don't have repeating patterns. (At least not usually. Patterns either result from implementation errors or algorithms that are similar to, but not the same as actual gradient noise functions).

They're not the only option though. Abstractly, we want to be able to flag contiguous groupings of triangles in a manner that's compatible with the hyperbolic plane requirement. Since you're already using a Delaunay triangulation a related concept that should be available is a Voronoi diagram. (Mathematically, a Voronoi diagram is the dual of a Delaunay triangulation. We can use a Voronoi diagram to partition your space and from there develop strategies to select groups of triangles.

I already had a 2D Poisson disk sampler (generates blue noise), so I used that to produce the following Delaunay triangulation:

Delaunay triangulation

Next, I generated a Voronoi diagram:

Voronoi diagram

One key thing to notice is that the average Voronoi cell size is several times larger than the average triangle cell size. Another is that this Voronoi diagram is not the dual of the Delaunay triangulation I had in the previous step. It is a separate randomly generated structure.

I used a distance function within the cells to further restrict the areas of interest:

distance function inside Voronoi cells

Finally, use the areas of interest to select triangles to be obstacles. I used a strict overlap – if the triangle touched the area of interest, I flagged it as an obstacle. I've superimposed a semitransparent version of the previous image over the top to show how the obstacles (in orange) cover the ball formed on each distance function.

triangles masked by distance function balls

There's a lot of room for experimentation. Here's an alternative approach where I first selected random pairs of Voronoi cells. Specifically, I pick a random cell, then I see if it has an adjacent cell that is both unselected & not touching any other selected cells – if both criteria are met, I add the pair:

Voronoi cell pairs

Then used the entire cell (rather than a distance function within the cell) to mask out obstacles in the triangle mesh. Again, I've superimposed the previous step to show how the obstacles triangles cover the area of interest.

triangles masked with cell pairs

Here are some other tunable parameters and things to experiment with:

Voronoi cell size

I selected a cell size that was large enough relative to my masking strategy such that I got interesting islands of obstacles. If the cell size is too small, you'll end up selecting too many triangles. On the other end, if the cells are to large, you get too much empty space and little or possible no clumps that bridge between adjacent Voronoi cells. Also, the triangles set the granularity of the output. If the difference in scale between the triangles and the Voronoi cells is vast enough, the triangles effective act like pixels and you'll see the pattern generated by the Voronoi cells themselves.

Voronoi cell selection

I picked a couple of simple options as a starting point. For something more complex, you could probabilisticly grow islands of cells or modify a maze generation algorithm to tunnel through the Voronoi diagram.

Triangle selection

Instead of a full overlap/collision calculation, you could check the triangle vertices or the centroids. For more complex example, you could use the triangle vertices to sample the distance function in the Vornonoi cell and only flag the triangle if the sum of the samples exceeded some threshold.

All of the above have some interdependence and changing one will likely require tweaking the others.

\$\endgroup\$
1
  • \$\begingroup\$ Thank you very much! Some interesting ideas! \$\endgroup\$ Commented Nov 6, 2024 at 22:38

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.