Issue Triangulating a Grid Map

Hello everyone,

I have a simple but very tricky problem.

TriangleLib: https://www.cs.cmu.edu/~quake/triangle.html
With this library i can triangulate a set of random points. I wanna implement this in my map system. but there r several problems with segmenting all the random holes in it.. because i don' want to create a convex of my map.

So basically i have a 2 dimensional grid of integers and it's filled with noise.

1 = Terrain / 0 = Air



The next step is to find the edge points calculated with the surrounding points..



..and finally i should loop through all outline points in the right order like the picture below..


Remember: It's a grid so i cant calc this with a simple magnitude.. and it's also random.. so i cant check it with neighbour points...

Thanks
BR Michael

 

Maybe you could make a doubly linked list of the outline points?

 

Thanks for the fast reply... "doubly linked" ?

 

Yes so each "node" in your case the square knows both what square is in front of it and behind it. I only suggested this because you said the order in which it iterates the squares is important but maybe this is redundant..

 

the order is the very important thing.. remember it is all random.. so in some cases it would creat this error..

 

And I assume you want the square that yields the shortest path (in number of squares traversed)?

 

the final output should be a "List<List<Vector2>>" for each square group..

 

I guess i solved it myself...



so worst case would be there r 2 ways to follow..

8 points arround each cell
- 1 where we come from = 7
- 4 all diagonals = 3
- 1 the not active cell (middle right) = 2

then I have to do a simple switch statement

case 0: follows the first way -> Gives me an Error if next point is not the start position or we come to an cell that is allready checked or there is no other cell

case 1: follows the second way -> Gives me no error -> Follow that way

 

ok i guess that doesn't solve my problem.. just tried to solve it with some performance saving tricks... but the best method would be shortest path as "vikankraft" already said

 

If the "smaller area" would be closer to the "big area" these squares might be adjecent, so maybe you will also need a marker to tell in some way what area the squares belong to. Or just disregard holes to close to the border.

 

Ok, i guess no solution works..
the problem is that i cant make any changes to the chunk because they dont fitt together.

The original problem came up when i triangulated the terrain with "Marching Squares"... so any tile thats inside the terrain would also be triangulated and the performance is gone :/

Does somebody now a performance saving marching square algorithm or maybe a different algorithm how i can triangulate a grid?

 

We're not dealing with triangulating yet though... you're currently getting the edge data, finding the border.

Also, what sort of triangles do you want? You post this larger image above, and the triangles formed are all tiny... is this what you considered not optimal? Would you prefer fewer, but larger, triangles? I could see usefulness for both, large triangles being less memory with fewer faces... while the tiny ones result in more minutia which can be used for all sorts of useful data like pathfinding.

Also, with your border walking here:

You could tell which direction to go because when in the position that image is in, you'd head in the direction whose outside neighbours (border) shares closer relations to the current tile. The current tile and the left tile share the outside tile as direct neighbours. Where as the tile to the north has one outside tile that is 2 tiles away from the current. We should pick the shortest relationship, so we turn left.

 

Sry for those misunderstandings.
My current problem is that i wanna generate terrain and my triangulation(marching sqaures) is pretty slow.

So I need something like that:


Just ignore the extruding.. so does somebody now a fast c# lib to create something like this "Greedy Marching Squares"
If you look at my old terrain all the middle party are also small cells.

I found this: http://github.prideout.net/marching-squares
But i don't now how to implement this in unity or compile it into an .dll

 

It might be slow because marching squares works with all the "cells" of the scene and needs the lookup table with all the cases and all that, but what you wanna do is find the edges really and just fill in the rest. Try some edge detection algorithms maybe.

 

Marching Squares is highly parallelizable. Multithreading is an option on most platforms. I believe that GPU implementations exist, if you're targeting platforms that allow compute shaders.

 

Success!

following the outline was a good idea generated from the marching squares. So now the terrain is based on a grid and optimized.
Now i just have 2-3 issues with performance and some isolated parts of the terrain but i guess i'll export the marching squares and the triangulation in a compute shader.

Thank u all

 

If a cell is neighbor(horizontal/vertical/45-degree) to an empty cell, it is an edge cell.