Trivial navigation mesh generation I

This is going to be a intermediate level lecture so before you read this lessons there are a couple of things I'm going to assume that you have prior knowledge of.

• A*
• The different search space representations for it and how to use it on them.
  
• 2D Line vs 2D Line intersection
• 2D Triangle vs 2D Triangle Intersection
• 2D Triangle inside Triangle tests
• 2D Point inside Triangle test

That's it so it's not a too hefty list basically it means you understand A* and that it is a graph based algorithm and that the natures of the graph might change, and basic linear algebra knowledge or well access to a basic 2D intersection library. I'm sorry I can't touch on everything but I have to try to keep the articles short and focused on the target. I will spread the difficulty level around quite a bit but at the moment I am mostly looking at the things we teach at the beginning of the second year at TheGameAssembly but there will appear articles targeted to beginners too and some like the last series that can be enjoyed booth by beginners and intermediate students.


This is going to be a intermediate level lecture so before you read this lessons there are a couple of things I'm going to assume that you have prior knowledge of.

• A*
• The different search space representations for it and how to use it on them.
  
• 2D Line vs 2D Line intersection
• 2D Triangle vs 2D Triangle Intersection
• 2D Triangle inside Triangle tests
• 2D Point inside Triangle test

That's it so it's not a too hefty list basically it means you understand A* and that it is a graph based algorithm and that the natures of the graph might change, and basic linear algebra knowledge or well access to a basic 2D intersection library. I'm sorry I can't touch on everything but I have to try to keep the articles short and focused on the target. I will spread the difficulty level around quite a bit but at the moment I am mostly looking at the things we teach at the beginning of the second year at TheGameAssembly but there will appear articles targeted to beginners too and some like the last series that can be enjoyed booth by beginners and intermediate students.

With that out of the way let's get down to the subject of this article. I admit that the title is kind of challenging as a lot of people reading this will think that this is far from trivial in complexity. Well that might be true but at the same time the basic process is very simple and most important numerically stable on modern PC processors. I don't have the time here to rag around why you can't trust floating point numbers on a computer but to make it clear I will make one simple example.

If you have a line and intersects it with another line to find an intersection point, and thereafter splits the first line into two different lines one being the part of the line that was left of the intersection point and one being the part of the line that was right of the intersection point then these new lines won't be parallel to the original line. And they won't even be parallel to each either. This is because when you create the new line you have to select a position which to use as the new point on the line. We use the intersection point. The problem is that the original line was defined as having infinite precision mathematically between its start and end point, at the time we actually decided a intersection point we had to throw that away and use the computers floating points precision and as it is not possible for it to perfectly match the true intersection point due to precision differences the intersection point won't be on the actual mathematical line (except for trivial lines) which means that the direction of the new lines have changed compared to the original. in fact if you put them together with the original and zoom in it will form a small triangle but you won't be able to see this with your eyes. But it creates problems when trying to detect if lines are really parallel and so on.

Because of this the algorithm we propose here has no need to rely on floating point numbers to be consistent or even correct.  It is not the best algorithm for the job let's be honest with that. But it is trivial to implement and does a good job of getting something decent output which can later be optimized. But overall it is simple to implement and that's why I teach it. So our goal is not to create the most optimized navigation mesh ever. But it will have good support for handling dynamic updating especially removal of earlier blocks which can be completely precalculated.

But before that let's look at the basics of the algorithm. One of the basic concepts is that we are going to use triangles to update areas of the world. An update is something that changes the data in the triangles that are inside the triangle that is used to update it might for example change a flag telling if the triangle is blocked for movement or not or change the cost of movement inside it. An update is required to only affect the area inside of the triangle used to update with. If the triangles of the mesh don't exactly match the updating triangle the algorithm will split those triangles until it achieves a perfect match up with the updating triangle.

So basically we can use any triangle to change the value of a triangle anywhere in the world or well change the value of the area defined by it. By combining multiple triangles we can update an area of any shape. I will stop typing the word update in bold now since I hope we have established that it is used as a special term with a special meaning during the scope of this article.

Here we have an example of where the technique will be usable our world consists of the 2 triangles showed by the red lines. But for some reason we want to update the area inside the blue triangle. It might be that a building has been placed there blocking any paths through that area or it might be that it is a swamp and we will move slower through it. We don't know and we don't need to. All we need to do is detect which triangles we should call the update function on with the data we have been called with. That is the meaning of an update.

The first step however must be to split the existing triangles in a way so that we only have triangles by the end and so that the edges of the triangles inside of that blue area perfectly matches up with the original blue triangle.  The algorithm to perform this is what we will spend most of this article exploring. But before we delve into the specifics let's take a look at the expected result of the algorithm.

You can still see the original blue triangle here and hopefully you can see that along each blue line there is also a red line showing the edge between 2 triangles if we look at it we should find that we have 4 triangles that are inside the area and will be called with the update data. All 4 of this are newly created by the triangle splitting step. The rest of the triangles are artifacts of the algorithm that can't be removed in a simple way. While it might look like it we cant remove a single edge without turning a triangle into a polygon this doesn't mean the new mesh is optimal I think I could have removed 2 polygons. But it is pretty tight for being triangles only.

This article will consist of two main parts the first part is just teaching you how to perform the algorithm that does the polygon splitting and the second will discuss the power of the concept of updating and how it can be used to create a dynamic world. This is really important modern games need to be dynamic we solved most problems of precalculated path finding years ago. But times have moved on and just as graphics are looking at dynamic solutions so must the AI.

For the rest of the article for simplicity I will assume that the world that the unit can path find on is a 2D space so there can be no room above a room. This is not a problem in the algorithm by itself it's just to keep the math and steps simply. To make it in 3d you exchange the updating triangle with a triangular rod which height and position in 3d space is used to find it's intersections with triangles and edges instead after which it is projected so that it is 2 dimensional compared to the surface you are updating which allows all the math in the innermost step to be executed in 2D.

Since the meat of the algorithm is splitting triangles the first thing we are going to look at is what happens when we try to split a triangle along a single line and the different results that we can achieve. The idea is that if we can resolve splitting around a line robustly we should be able to perform any kind of splits we want later to achieve the end result since we already know how to split with the line.

Again Red is the color of edges of out triangle and this time the blue line is the line we want to split the triangle along. While making sure that the end result only consists of triangles.

The obvious first step is to just split the triangle straight along the cutting line.

You should be able to see that inside the triangle the blue line has been replaced with a red denoting a new edge between triangles. However this split has resulted in a case where while the upper part of the triangle is still a triangle the lower part has turned into a 4 sided polygon. Since we can only accept triangles as a valid output we have to turn this polygon into triangles. There are only 2 possible ways to turn a 4 point polygon into two triangles since for each vertex there is only one vertex that it isn't directly connected to. And while there are 4 pairs of these vertexes 2 of them are identical except for which vertex is the first and the second we end up with only 2 choices.

These are our two possible options you can take out a pen and paper for yourself and try to find different ways of doing it if you want to. But you won't find any other options than these 2 that results in only 3 triangles in the end. Since these are the minimal number of triangles to represent this data. Because of this we can say that both of these splits are optimal. Neither of them produced any extra triangles or edges so either of these is fine.

Now that we have examined how a optimal splitting looks like it is time to sit down and try to figure out an algorithm that can duplicate this (And of course work no matter what direction the splitting line comes from and no matter how the triangle looks. While I am using this case as an example the algorithm is perfectly general.). But first of all let's look at the data structures we are going to be using during this article.

The normal approach to think about a triangle is to think that it consists of 3 points and that these points form 3 edges. We are going to try to think about it differently. One of the reasons is that we want an edge to know what triangles it belongs to. And if we want to split an edge between two triangles we don't want to perform two intersection tests one for each triangles representation of that edge. One of the big reasons for this is obviously performance 2 tests are twice as slow as one. But this is not the main reason. The big reason is that there is no guarantee that the intersection points on the two triangles will be identical since the ordering of the points inside the triangles might be different causing the limited floating point precision to select different intersection points. And as this is the problem of going from infinite precision to finite precision using doubles instead of floats won't solve the problems.

So because of all of this we are going to use an unorthodox data structure where the edge is the main component and the Triangle is just a container of 3 Edges.

Vector2f is the data format of a 2D vector it has two members x and y which are both floats and can perform all standard vector operations on those.

class Edge
{
public:
    Edge(const Vector2f aFirstPoint,const Vector2f aFirstPoint);
    ~Edge();

   Vector2f GetFirstPoint();
   Vector2f  GetSecondPoint();
   void ConnectToTriangle(Triangle* aTriangle);
// Adds the triangles to myTriangles
   void DisconnectFromTriangle(Triangle* aTriangle);
// Removes the Triangle from myTriangles

private:
   Vector2f myFirstPoint;
   Vector2f mySecondPoint;
   Triangle myTriangles[2];
// Because an Edge can at most be connected to two triangles at a time


};


This looks pretty basic, one question that can rise is why I went through the trouble of using accessor functions. There are a couple of reasons for this. First an edge is constant from the time it is created until the time it is destroyed if you split an edge you create two new ones you don't modify the original. Another reason is because you will most of the time use a number of helper functions to get access to the two positions because you don't have a fixed winding order in your triangles. I will get to that in a second but first we'll look at the Triangle class before moving on. I am also using straight C style arrays just to keep this example code clean from external libraries.

class Triangle()
{
public:
   Triangle(Edge* someEdges[3]);
   ~Triangle();


   Edge* GetEdges();

private:
   Edge* myEdges[3];
}


You will also notice that booth our classes have forced constructors you can't create a edge without booth its points and you can't create a triangle without 3 edges. This is to guarantee that we always work on complete data types. Now before we go on we will quickly add some really useful helper functions that will make your life a lot easier later on.

We'll start out with Edge


bool IsConnected(Edge* aEdge);
/* This function checks if this edge is sharing a point with the edge sent in. */
bool IsConnectedTo(Vector2f aPosition);
/* This function checks if the point is a part of the Edge */


Vector2f GetOtherPoint(Vector2f aPosition);
/* This assumes that the point is a part of the edge it returns the other point of the edge*/


Vector2f GetconnectedPoint(Edge* aEdge);
/* This functions returns the shared point of these two edges, You should use IsConnected to verify that these edges are connected */


Vector2f GetUnconnectedPoint(Edge* aEdge);
/* This function which assumes the edges are connected returns the point on the first edge that is not connected to the edge that is sent in */
bool IsPartOf(Triangle* aTriangle)
/* Validation function asserts that the triangle is connected to the edge */


Triangle* GetTriangle()
/* Returns aTriangle if the edges is connected to triangles else it returns NULL*/
Triangle* GetOtherTriangle(Triangle* aTriangle)
/* This function assumes that aTriangle is connected to the edge it returns the other triangle connected to it. If there is only one triangle connected to the edge it will return NULL*/

This should keep us safe for now. Don't worry if you don't realize the needs of those functions yet it will become apparent once you get down and dirty with the code.

And on the Triangle Class we have a few helper functions too


void GetVertexes(Vector2f someVertices[3]);
/* Iterates through the edges and collects the unique vertexes and fills the list with them */
bool IsPartOf(Edge* aEdge);

/* Validation function returns true if the edge is a part of this triangle */

Edge* GetEdgeLeftOf(Edge* aEdge);

/* Returns the other edge connected to the first point of the edge sent in */

Edge* GetEdgeRightOf(Edge* aEdge);

/* Returns the other edge connected to the second point of the edge sent in */

Vector2f GetUnconnectedPoint(Edge* aEdge)
/* Returns the point on the triangle that isn't connected to the edge */

You will notice that in order to implement the triangle functions you will need to use the edge functions and even that the edge functions are implemented using other edge functions so all of this is just building a toolkit to allow us to later perform the operations we want to do easily. And the reason for this is that we can't be guaranteed any specific order of the vertexes in an edge. the first point in one might be the same as the second in another but it might also be the same as the first. So you can't assume any kind of ordering. This is because the triangles share the edges and there doesn't exist an ordering that will be consistent for the entire world as for different triangles you are using the same edge but walking around the triangle in different directions.

Enough preparations now let's get on with our algorithm for splitting triangles. The algorithm I propose is quite simple but for our default case of a single triangle splitting it will guarantee the same optimal results as in our earlier test.

Again it's time to define some terminology. We will call that blue Line a cutting line and all the red lines are Edges using the classes we just defined and together creates a Triangle.

Well  first formulate the algorithm in pseudo code and then we'll move to actual C++ code.

For Each Edge Intersected by The CuttingLine
    Split that edge into two edges.
    For each Triangle connected to the original Edge
        Split it into two triangles by drawing an Edge from the intersection point to the point on the       triangle not connected to the original edge

Actual code for performing these tasks is a bit more complex mostly taking care of the destruction and creation of new edges and triangles. But we'll walk through our test case before we start to look at that. Most of the visuals are the same as earlier but we have added one more visual clue we show an intersection between an edge and a cuttingLine.

Here is our basic case again we have a a triangle consisting of 3 red edges and a blue cuttingline.

The green point shows an intersection with an edge. We could as easily have gone with the other edge as we are going to cover later.

Since the edge that we intersected is only linked to a single triangle we split that triangle and the edge creating two new triangles instead of the original one. Remember that the original edge is gone replaced by two new to create the two triangles.

 

We identify the second intersection. An important point is that you should only intersect vs edges that existed before you made the first split (They will only be intersected on one of their vertexes anyway so it's just a waste of performance) . This edge is also connected to only one triangle and those will split that triangle.

This shape should be familiar as one of our two optimal splits from earlier. And if we had intersected the rightmost edge first it would have resulted in the other configuration. You are free to try this out on paper to prove it to yourself.

Now we should see if we can't convert the pseudo code for this to something closer to real code. This part is the splitting part. This code is written for clarity and not performance in the hope that this will help you grasp the algorithm.

The function SplitEdgesWithCuttingLine is not a part of the triangle or edge structure but rather a part of your TriangleContainer. SomeOriginalEdges is a temporary list of edges created for this specific update before this function is called that contains the edges relevant for the algorithm .It won't be used again after this function so we can do what we want with it.

For the record I have booth a TriangleContainer and an EdgeContainer class any edges created is automatically added to an edge container and each triangle to a triangle container this is done by forcing an appropriate container to be sent through their constructor this means that every edge or triangle created or deleted automatically handles its own memory. Also if A triangle is deleted it automatically removes itself from all its edges and any edge with no connected triangles after this will be deleted. This is the reason this code might seem to be sloppy with memory handling because it's all taken care of elsewhere.

void SplitEdgesWithCuttingLine(std::vector& someOriginalEdges,Vector2f aFirstPoint,Vector2f aSecondPoint)

{

  std::vector newEdges;  // starts empty

  std::vector  edgesToDelete; // starts empty


  for(i=0;i<someOriginalEdges. size();i++)
  {
     if(someOriginalEdges[i]->IsIntersectedByInfiniteLine(aFirstPoint,aSecondPoint)
     {
        /* we have an intersection . To keep things easy we always assume that our cutting lines are  infinite. While the edges aren't */
           someOriginalEdges[i]->Split(aFirstPoint,aSecondPoint);
           delete(someOriginalEdges[i]);
     }


  }
}



As we can see we are calling two functions on the Edge class that we haven't talked about earlier. The first one is trivial it performs line to line intersection between the incoming line and the edges considering the incoming line as an infinite line while the Edge is finite and returns the result of the test.

The split function assumes that the lines are intersecting before being called and it's there some of the work happens so let's look at it. A short disclaimer here about the code in this article it is all written specifically for this blog and is not the real code I would use so it might have some small compilation errors or even logical mistakes in it.

void Edge::Split(Vector2f aFirstPoint,Vector2f aSecondPoint)
{
    Vector2f intersectionPoint;
    bool intersects = LineVsInfineLineIntersection(myFirstPoint,mySecondPoint,aFirstPoint,aSecondPoint,intersectionPoint);      // Calculates the intersection point of the two lines 

     assert(intersects==true);
   Edge* firstEdge= new Edge( myFirstPoint,intersectionPoint);
   Edge* secondEdge= new Edge( intersectionPoint,mySecondPoint);
   // Creates 2 new edges to replace this edge please observe that they currently aren't connected to any triangles

   for(int i=0 ;i<2;i++)
   {
      if(myTriangles[i]!=NULL) 
      // Only do this if the Edge is connected to triangles

      {
          myTriangles[i]->SplitByEdge(this,firstEdge,secondEdge);
          // inform the triangle that should be split what edge should be split and what the replacing edges look like.

      }

  }
}


That was a bit of code but I would say it's hopefully really simple to grasp so far because we have divided the problem down into small parts. First we detect intersections. Then we determine the intersection points. And then we will split the triangles by telling it which edge that was split and what edges will be replacing it. So let's look at code for performing that split.

void Triangle::SplitByEdge(Edge* aSplitEdge,Edge* aFirstNewEdge,Edge* aSecondNewEdge)
{
    assert(IsPartof(aSplitEdge)==true);  
    // Make certain it is really a part of this triangle else we have a bug somewhere.

   Edge* edgeConnectTheFirstNewEdge=GetEdgeLeftOf(aSplitEdge);
   Edge* edgeConnectTheSecondNewEdge=GetEdgeRightOf(aSplitEdge);
/* get the two other edges of the triangle first get the one connected to a FirstNewEdge if your code is flexible you should even be able to send in aFirstNewEdge and aSecond new Edge instead of aSplitEdge*/
   Edge* middleEdge= new Edge(GetUnconnectedPoint(aSplitEdge),aFirstNewEdge->GetconnectedPoint(aSecondNewEdge));
/* This creates an edge that goes from the point of the triangle that isn't a part of the original edge to the cutting point. This works because the cutting point is the only point that will be connected between the two new edges. Else you could just pass the intersection point to the function too */

    aSplitEdge->DisconnectFromTriangle(this);
    edgeConnectTheFirstNewEdge->DisconnectFromTriangle(this);

    edgeConnectTheSecondNewEdge->DisconnectFromTriangle(this);
/* prepare for the creation of the new triangles by removing the old one from the edges this could and should be done in the current triangles destructor but then you wouldn't see the code so */
  Triangle* firstTriangle=new Triangle (edgeConnectTheFirstNewEdge,aFirstNewEdge,middleEdge);
  Triangle* secondTriangle=new Triangle (edgeConnectTheSecondNewEdge,aSecondNewEdge,middleEdge);
/* Here we create the new triangles that is the result of the split. Observe that they connect to the edges by themselves in their constructor this is the reason we had to disconnect the edges earlier so that we could add new ones*/
  delete (this);
/*  The final step. The triangle is already not connected to anything anymore so it's free to delete without destroying anything it will just peacefully remove itself from it's container and die */

}

So we have written quite a bit of code now however observe that except for the comments for you readers, none of the functions is larger than 20-30 lines of code so we have managed to split our big problems into a few really small parts which has helped us to solve it smoothly.

But how do we use this algorithm to update an area and does this algorithm really work on more complex cases? Let's take a look at the case that we showed in the start of this article it can be considered kind of a nightmare case even though there exists more complex cases for a human to follow from the perspective of the algorithm it doesn't get any worse than this.

First out how are we going to use this to perform an update. The basic idea is that we will use all three edges of the blue triangle as cutting lines. And apply each of them separately. After this we will identify which of the triangles that are inside of the blue triangle and call their update.  We will look into this later. But for now we assume that we call SplitEdgesWithCuttingLine one time for every cutting edge and input all the edges in the world in our list someOriginalEdges after this step we will look at how to optimize that so that we don't have to intersect as many edges.

 Here we have an image of the three cutting lines generated from our blue triangle. As they cutting lines counts as infinitely long we have drawn them so that they pass through the entire world.

You will notice that we are using green cutting lines here instead of blue as in the earlier examples. The reason for this is that we want to be able to keep the blue triangle visual in the world and therefore we need another colour to denote our cutting lines.

Following the algorithm explained above we are going to call SplitEdgesWithCuttingLine once for each of these lines. We could start with anyone of them but since we only want to perform one example we will select a order and start with the one marked as a green line in the image to the left.

The deep green point shows us the position of an intersection. Since the edges in someOriginalEdges can be in any order there is no guarantee that the first edge we intersect will be one of the leftmost or rightmost edges. We will use a fixed order for the rest of these images but I want to be sure you know that this isn't necessary or even easily enforceable. All the triangles connected with the intersected edge is marked with a light green color so that you can easily follow what is happening.

Following the steps of the algorithm if an intersection is created we split that edge and all the triangles sharing that edge. Once we have done this the rest is just repetition of the same steps but for sake of clarity I will walk you through them. For newly created triangles we will mark them in a light blue color so that it will be easy to follow the flow. You will surely notice that what is green always become blue as we split the old green triangles into the new blue ones.

As we have resolved the edge in the earlier case we move forward to the next Edge intersection again marked with the deep green marker. As you can see clearly this edge is only connected to a single triangle and this is why we have only one light green triangle.









All the triangles connected to the intersected edge are split and so is the edge. It might be slightly unclear but you should be able to see the red line over the green for the blue triangle pair.

 And finally here is the last edge that is intersected by the cutting line. Again it is marked with a deep green marker and the triangles to be split is slightly green,

And we perform the final split for this line.  Resulting in the two light blue triangles

As we have split all lines intersecting the cutting line it is time to move on to the next one. This means we call SplitEdgesWithCuttingLine again with all the current edges in someOriginalEdges. So all the new edges created through the last pass are now possible to intersect vs.

We intersect the first edge marked with a deep green node. The triangles connected to that node are marked with light green.

And the light green marked triangle is split by a line from the deep green intersection point to the corner not a part of the edge being intersected into two light blue triangles.

And we move on to the next edge which connects the two light green triangles (If this sounds like a repeating record it's because it is. But this kind of clarity has been requested by my students).

And the two light green triangles were split into 4 light blue triangles.

The next edge is connected to by the two light green triangles. The deep green dot is the intersection point between the edge and the cutting line.

And the light blue triangles show the split created by the intersection of the line at the deep green dot.

I think we can start speeding this up now as you know the drill so we're going to start just showing the before and after split pictures.

With the last cutting line we restart the process again and all lines that were created by the last line is also feed to the SplitEdgesWithCuttingLine function.

 

In this final picture after we have cut with all the cutting lines we go through all the triangles in the world and detect which are inside the original blue triangle (those are marked blue in the above image). We should notice here that this isn't as expensive as it seems. In reality we only need to test newly created triangles or triangles which was inside the updating triangle before the splitting started. Also we don't need to perform a true triangle vs triangle test. Because no triangle will ever cross the edge of the updating triangle all we need to check is if the middle of the triangle is inside the updating triangle. Then the entire triangle is too.

But you might have noticed that we had to do a lot of splitting that seemed unnecessary in this example splitting triangles that wasn't affected by the original blue triangle in any way. This is a correct observation. It is however not a fault within SplitEdgesWithCuttingLine it's rather that we feed it the entire world as it's input data instead of just what is necessary.

The solution is to only feed SplitEdgesWithCuttingLine with edges from triangles intersecting with the updating triangle or those that are containing it. You do need to flag which triangles are inside it so that you can update them later but you do not need to take their edges unless of course that edge is shared with a triangle that is intersecting or containing the updating triangle.

void TriangleContainer::UpdateTriangle(Triangle* aUpdatingTriangle);

{

    for(int cuttingLineIndex=0;cuttingLineIndex<3;cuttingLineIndex++) 

    {

       std::vector intersectignOrContainingTriangles;

       GetInteractingTriangles( aUpdatingTriangle,intersectignOrContainingTriangles);

   /* This function calculates the intersecting or containing while strong contained triangles in a special array in the triangle container so that it can remove triangles that gets deleted from that queue */

     UniqueVector uniqueEdges;

/* Any vector that can detect and avoid duplicates works fine you can even do the checks by yourself but for code simplicity I am assuming this class */ 

     for(int i=0;i

     { 

        for(int j=0;j<3;j++)

        { 

            uniqueEdges.AddIfUnique(intersectignOrContainingTriangles[i]->GetEdges()[j]);

        }

     }

   /* this code adds all edges from all the triangles that interacts with the updating triangle making sure that no edge is copied twice */

    SplitEdgesWithCuttingLine(uniqueEdges,aUpdatingTriangle->GetEdges()[cuttingLineIndex]->GetFirstPoint(),UpdatingTriangle->GetEdges()[cuttingLineIndex]->GetSecondPoint());

// calls split edges with the cutting edge

  }

/*

 GetContainedTriangles() is a function that returns a reference to the std::vector that contains all the triangles that was contained by the updating triangle and haven't been deleted so far */

  for(int i=0;i

  {

     GetContainedTriangles()[i]->Update();

  }

  GetContainedTriangles().Empty()

// empties the temproary contained triangle vector

/*

 GetNewTriangles() is a function that returns a reference to the std::vector that contains all the triangles that was created during the splitting by the updating triangle and haven't been deleted so far 

The way this is implemented is simple each triangles constructor is forced to take a triangle container as input and in the constructor it adds itself to it. And when it does this it also adds itself to this queue and in the triangle destructor it calls the triangle container and tells it to remove it from it. And at this time it removes it from the new triangle queue if it is in it and from the contained triangle queue if it is in it.*/

  for(int i=0;i

  {

     if( aUpdatingTriangle->PointInsideTriangle(GetNewTriangles()[i]->GetCenter())==true)

     {

        GetNewTriangles()[i]->Update();

     }

  }

  GetNewTriangles().Empty()

// empties the temporary new Triangles vector

}

That was it, actually there isn't more to it and we even discussed some of the optimizations that we use that complicate things a bit.  if the two vectors in the triangle container confuses you then you can just test all the triangles after the cutting lines lope has finished and update those that are inside the updating triangle. As a last step of this article I will walk you through the optimized updating process and during the next article we will look at how we can use this system to do really cool stuff.

Here we go with the default case again not much to say about it.

Here you can see a beige color on the rightmost triangle. We use this beige color to show which triangles are interacting (intersecting, containing or being contained by counts as interacting). So that you can clearly see what each step of the algorithm does. This is the result of the call to GetInteractingTriangles.

After we had gotten the interacting triangles we collected all the edges from them until we had a list of edges from those triangles where every edge only exists once. We use the pink thick line coloring to show lines that are being sent to SplitEdgesWithCuttingLine.

And here is the first cutting line again. I have decided to try to match the length of the cutting line visually here to the edges it actually intersect, this doesn't change the fact that when making the intersection it is treated as infinite all we have changed is which edges we send a input to SplitEdgesWithCuttingLine.

We still use the color coding of light green for triangles that are going to be split. Worth of notice here is that the lower left triangle is going to be split despite not interacting with the blue triangle. This is because it shares an edge with a triangle that needs to be split. If we didn't split that triangle we would end up with a triangle with 4 edges and those even though it may look like a triangle visually it would no longer be one and that would cause all sorts of problems in the long run.

And we perform the splits just as usual and we color the new triangles light blue. So far the only difference is that we have an ugly pink color here too.

Moving on to your second and final split for this cutting edge, this is one less than the last time thanks to detecting which edges are part of interacting triangles and which aren't we can skip unnecessary splits.

And we split it. This should be very familiar by now.

We move onto the second cutting line. So again we detect which triangles are interacting with ours. Please note that due to floating point precision problems the lower triangle on the right side may also be selected as an interacting triangle this is perfectly normal as its edge is parallel to one of the blue triangles. But for this case we are going to assume our intersection tests works exactly as we want them to.

And here is the list of edges being connected to the edges of the triangles that was interacting with the blue triangle.

And we run through the process using the next cutting line. It feels kind of like magic that if it works for a single line then it will work for any triangle and if it works for any triangle it will work for any mesh consisting of triangles (we will talk about optimizations for those in the next article)

Seems the light blue color has changed slightly here but it still means the same thing new triangles after the split.

And the splitting keeps running it's natural course.

The correct blue color seems to be back again.

And we're going for the final split. This time we saved two splits compared to if we had to split all the edges but we also saved extra on some triangles not even being generated on the last pass.

And the second cutting line is a wrap so time to repeat the process one last time for the third line.

We detect the triangles interacting with our blue triangle. Once again assuming the intersection detection code does exactly what we want it to.

And here we have the Edges belonging to the interacting triangles. It should be clear that the optimization works better as there are more triangles in the world because then there are more triangles that can be rejected.

Once again triangles outside of the interacting area is affected because of a shared edge but please observe that it can't spread furtehr away cause the split on those triangles doesn't affects any of its edges except the split one.

I really have nothing to add this is just repeating the process once more.

It might be tough seeing the triangles coloring here as they are getting smaller but hopefully you know enough about how it works by now to follow along.

And it's a wrap no more splits are necessary.

And here we can see the results of the tests for which triangles are inside the updating triangle. I went on quite a bit about updating and why I called it that. Why couldn't I just say that I was setting the blocked flag on triangle?

The reason is that we can do a lot more cool stuff with updating but that will have to wait to the next article together with some optimization stuff because by now this is the monster post from hell. I have one last thing to think about before we can sign this off however and you can start implementing it.

It's about how to handle intersections on a point of an edge or really close to them. If you do intersect exactly at one of the points of an edge it means you already have an edge following the cutting line there and you don't need to perform any splits. In fact I wouldn't perform any splits if i was within 0.01 meters of the point of an edge (I am assuming you work in a metric system because anything else wouldn't make much sense) This is because I have no use for triangles smaller than 1 cm no one will notice the difference in the path finding anyway and this helps me from getting swamped with invisible triangles that drags down performance. And of course if I am having any problems with numerical stability in parallel lien intersection tests etc this will make them go away. It's the only magical epsilon value I would allow in my system and I can allow it because the system works without it. It's not essential just an optimization.

That's all for this time the rest will come in part II which should be smaller than this monster post.