I'm trying to create (implement) a navigation system… I want to be able to place various rectangular polygons (not rotated) and make a unique shape out of them (union). I'm having trouble though coming up with an algorithm to do it. I guess I want to end with a list of consecutive points that represent the shape… then I need to break those into triangles and lastly use it in conjunction with A*.
So my main problem is creating the Mesh and splitting it into triangles.. I'm working from scratch here so no external libraries :( just wanted to understand the process to try and do it myself.

2 options come into my mind:

Make BSP tree from the rectangles. (Requires to clip polygons with a given split lines; Subdivides input polygons into a set of non overlapping convex polygons.)

Or raster your rectangles int a bitmap, make a high resolution mesh with quad for each drawn pixel, use mesh simplification to get efficient low poly triangles.

The former option seems easier to implement and also more efficient. The latter could be more flexible if input becomes more complex (also if you want to create navmesh automatically from real level geometry).
Both options would work with generic (non rectangular) polygons without more effort.

hmm… 3rd option: Rasterize the rectangles, find singularities in the image (== corners, so in a 2*2 pixel tile there is either 1 or 3 pixels set), and trace a motorcycle graph from the singularities.
This would be faster than mesh simplification and would generate nice rectangles. But it's limited to rectangles as input to detect corners robustly.

@xdgamestudios I've never worked with nav meshes before, but I believe the way it works is by selecting all “walkable” triangles in your scene's geometry, and putting them together into a single mesh. So, maybe your scene is made up of multiple objects with different models, but they all connect together spatially. You'll want to grab a list of all walkable triangles from all of these models, and then put them together into a mesh. We don't modify the existing geometry in any way, this is a pure copy.

If you find that your nav mesh has a lot of detail in it, then consider making a simplified version of that nav mesh. It doesn't have to be 100% accurate, nor should it. You just want a rough shape of the walkable area because a complex mesh makes the search algorithm exponentially more complex.

Once you have that working, you need to do the following:

• Figure out which triangle your actor(s) are currently in. This part of the algorithm shouldn't be part of your navmesh algorithm, but having a utility function that can take a vector/position, and somehow select a triangle in the navmesh should do.
• Develop the path algorithm to get from one triangle to another. This will take a bit of thought to figure out as I'm only familiar with A*, but I'm sure it's something simple like that. This will take some work, but if you're developing your mesh from multiple, separate models, then not all triangles in your mesh will line up with one-another perfectly. I'd recommend getting the algorithm to work with triangles that all share adjacent triangles first, then go from there. Maybe the answer is to make a separate mesh for each different object entirely, and then have an algorithm on top of the mesh-nav algorithm that can find a path across multiple nav meshes first, then the navigation across all selected nav meshes?

thank you so much for your time and ideas ? will look into them, I'm already more confident!

@JoeJ Okay in on my way to a finished navmesh… I've successfully generate a list of triangles for a shape…
but now I have a problem I cant figure a way through creating the neighbour relationship between the triangles.

I have 2 arrays:

1 for DATA ((p1x, p1y), (p2x, p2y), (p3x, p3y), (p4x, p4y)) → containing a tuple for each point
1 for TRIANGLES ((0,1,2), (2,3,0)) → containing a tuple of 3 point indexes (then I can track them in the data array)

I'm able to create an adjacency matrix for the TRIANGLE VERTICES… I created a square grid size of DATA and then loop for all entry on TRIANGLES and for each tuple mark the indexes as adjacent between each other. But that's it… I'm having a hard time..

I was going for a NEIGHBOURS array, that would have the length of TRIANGLES array and for each entry would have a list of neighbour triangle index.
In this case
((1), (0)) → meaning:
- triangle 0 (index 0 of TRIANGLE ARRAY → (0,1,2)) is neighbour to 1 (index 1 of TRIANGLE ARRAY → (2,3,0))

- triangle 1 (index 1 of TRIANGLE ARRAY → (2,3,0)) is neighbour to 0 (index 0 of TRIANGLE ARRAY → (0,1,2))

Any ideas?!

1 for DATA ((p1x, p1y), (p2x, p2y), (p3x, p3y), (p4x, p4y)) → containing a tuple for each point
1 for TRIANGLES ((0,1,2), (2,3,0)) → containing a tuple of 3 point indexes (then I can track them in the data array)

That's the usual 3 vertex indices per triangle, which is fine for rendering, but it lacks adjacency information.

For adjacency, in the past i came up with my own data structures. Just add what's needed without much thoughts. So i ended up a lot of stuff: Per vertex a list of clockwise sorted edges and polygons, per polygon clockwise list of edges and neighbor polys. That's a lot of data and not really good. For example, mesh editing operations become really hard to implement because a lot of data needs update.

So at some point i switched to the half edge data structure, which is what most people use for advanced geometry processing.
It looks like this:

	class HEMesh
	{
	public:

		typedef int32_t Index;

		// half edges
		struct HalfEdge
		{
			Index pair;
			Index next;
			Index poly;
			Index vertex;

			HalfEdge ()
			{
				pair = -1;
				next = -1;
				poly = -1;
				vertex = -1;
			}
		};
		std::vector<HalfEdge> mEdge;

		// vertices
		std::vector<Index> mVertexEdge;
		std::vector<vec> mVertexPosition;
		
		// polys
		std::vector<Index> mPolyEdge;

That's pretty compact and most data is in the edges, also no need for std::vector per vertex or polygon, which is really bad for performance.

Imagine two adjacent triangles left and right, and split the edge between them into a left an right half.
Left half edge goes from top to bottom vertex, and right half edge goes from bottom to top vertex.
This way each half edge has clockwise ordering which is not possible if we would use a single edge.

So the pair index points to the other half, and the next index points to the next edge in a polygon or triangle, and we need only a single vertex pointer per half edge because we can get the other one from the other half.

To traverse edges of a polygon in order, code looks like this:

int h = mPolyEdge(polyIndex); 
do {
		// vertex = mEdge[h].vertex;
		h = mEdge[h].next;
} while (h!= mPolyEdge(polyIndex));

And to traverse around a vertex:

int h = mVertexEdge(vertexIndex); 
do {
		// poly = mEdge[h].poly;
		h = mEdge[h].pair;
		// adjacent vertex = mEdge[h].vertex;
		h = mEdge[h].next;
} while (h!= mVertexEdge(vertexIndex));

So you can do all that's necessary with little data.

Half edge is not super intuitive at first, but it made my life easier. (Though, mesh editing operations are still hard and tedious to implement.)

I've heard some people also use it for collision detection in physics engines, which means it's fast to traverse. It's also flexible to optimize for memory access. For example you could arrange halfs, polys and vertices in morton order to help with cache misses.

---

But personally i do not use it for path finding, because traversal still hops around in memory in any case.
For tasks like path finding or solvers where we want adjacency as fast as possible, but topology of mesh is usually static, i simply convert to compacted adjacency lists.
So i have one std::vector, then for each vertex i do traversal as above and add the neighbors to the vector. And for each vertex i store its start index to the vector to find the adjacent vertices and edges.

My Dijkstra path finding then looks like this (pay attention to how i get adjacent vertices but ignore the other logic):

		int Next ()
 /// return the next shortest paths segment
		{
			int c = -1;
			for (;;)
			{
				if (queue.empty()) return -1;
				c = queue.top().second;
				queue.pop();
				if (mExtracted[c]) continue; // prevent duplicates + speed up
				mExtracted[c] = true;
				break;
			}
			
			int begin = (*mPrimAdjList)[c];
 /// c can be the current vertex, and i get it's start from compacted adjacency lists here
			int end = (*mPrimAdjList)[c+1];
 /// c+1 would be the start index for the next vertex in memory orther, so this also gives the end of the list for the current one
			for (int i=begin; i<end; i++)
			{
				int n = (*mPrimAdjacency)[i][1];
 /// my lists store both the adjacent vertex,
				int e = (*mPrimAdjacency)[i][0];
 /// and the edge between (which i need to get the cost (or length) of the edge)
				float w = (*mEdgeWeights)[e];

				if (!mExtracted[n] &amp;&amp; mPathMinDistance[n] > mPathMinDistance[c] + w)
				{
					mPathMinDistance[n] = mPathMinDistance[c] + w;
					queue.push(std::make_pair(-mPathMinDistance[n], n));
					mPathPreviousEdge[n] = e;
				}
			}
			return c;		
		}

So if all you want is efficient path finding, such compacted lists might be a good choice and no need to worry about the difficult topic of what's the ideal mesh data structure.
For me it's also a nice abstraction because i can use the same path finding code for paths between vertices or paths between polygons. I could also use it for any other graph not related to geometry at all.
Compacted lists need usually much less memory than a adjacency matrix, we could look at it as a sparse version of that.

JoeJ did a good job of suggesting different data structures for navigation. This is important!

General Purpose: Finned Edges

Personally, for reasoning about triangle geometry, I find the the “finned edges” data structure is pretty useful. Basically, throw away all information about rendering (texture coordinates, colors, vertex normals, etc.) Then build three arrays: Vertices, Edges, and Triangles. Each Triangle has three vertices and three edges. Each Edge has two Triangles. Vertices just have position – you never “navigate” your data structure through vertices.

You can calculate triangles normals through cross product if you need it, or you can store triangle normals if it's important.

Now, you have a graph – two triangles share an edge, so you can go from triangle A to three (or fewer) other triangles by looking for shared edges. This graph may be all that you need for building a navigation mesh!

Special Purpose: Quad Trees

If you need something coarser, then I've had success with quad trees. As a pre-process step, I cast capsule collision against terrain, with some thickness, to figure out where a character can pass. Just do it on a grid – it'll be thousands of capsules, but that's fine! Make a finest-grain grid of the spacing you use for these capsules. Then, clump these gridd cells together in quad tree cells (meaning, well-aligned cells clump better than mis-aligned cells for narrow features – that's acceptable.) Keep a maximum cell size you allow, to keep things local-ish.

Now, you can run a-star through this quad tree, between centers of neighboring-cell-border-segments. You can run a later pass to make the path prettier, by, for example, connecting the centers of each cell to the edges, and then relaxing the path to straighten it out and reducing zig-zagging.