Create faces between vertices on a procedurally genererated map

My map looks like below. Currently it’s displayed with a few hundred planes, but I want to turn it into a mesh. The vertices are already figured out (the blue dots) and I can extrude the walls upwards, however I have no idea how to create the floor properly so that I only have triangles between the dots.

Came up with one idea that you put vertices at a distance of 1 between each other and then through a few literations join them where they can be connected to make a bigger face. This however is not optimal since you start with a gigantic mesh if you level is big.

If someone knows how to do this and care explain or atleast have something I can read I’d be happy :slight_smile:

As @Bunny83 says, the points alone are meaningless (or could mean anything!). You would need extra data to generate your mesh.

The most general approach would be if your only information is what points are connected to what other points (i.e. you know the edges), then you have a classic triangulation problem - you have an outer polygon (the list of connected points that form your outer wall boundary, and (in your example) 2 ‘holes’ - lists of connected points that define inner wall boundaries.

This problem is commonly referred to as ‘triangulation of a polygon with holes’. It’s none trivial, but there are various algorithms to solve it. This is a good paper on the subject:

Though I suggest you do your own googling and find one you’re happy trying to implement - or somebody else’s code that already implements it! :slight_smile:

-Chris

Phew… I could think of something like this:

  1. iterate trough all vertecies and create a line to the next closets vertex (in your case which is closest on a certain axis due your pretty rectangular geometry)
  2. iterate trough all lines and find line pairs who share the same vertex somewhere, then build a triangle in the folowing order: vertex, shared vertex, vertex.
  3. “discard” the vertex which is shared or rather make it not availabe anymore for other triangle creation. (otherwise you would have overlapping geometry, nasty!)

I can not prove that this would work, but I hope this gives you some input :slight_smile: