Right Foot, Left Foot (III)

Continuing with my work on navigation meshes, the latest changes made during the past few days bring a lot of new and exiting improvements:

Visualizing the navigation mesh

Having a good look at how the nav mesh is defined is very important in order to understand where its problems are.

Screen Shot 2017-09-17 at 6.59.59 PM.png

As the image above shows, each cell will display its center and normal vectors now (and correctly ordered)

Vertex order

The first change in the list was to enforce the order of the vertices for each cell to make it clockwise. This is a must in when identifying which points are inside or outside of a given cell. Otherwise, normal vectors won’t be pointing in the right direction and results will end up all mixed up.

I also modified the OBJ loader also transform vertices accordingly.

Edge Sliding

Probably the most noticeable change of all, the new implementation is able to handle collisions with walls and borders in a more friendlier fashion than before. Instead of just stopping movement once a character has reach an unshared edge (a wall, for example), the nav mesh will now compute a sliding vector in order to make the movement more fluid.

Screen Shot 2017-09-17 at 6.59.59 PM copy

In the picture above, the player attempts to walk forward (red arrow). Since there’s no valid cell in that direction, the nav mesh will slide the movement slightly to the up and to the right.

Enhanced navigation controller

All the above changes lead to an enhanced NavigationController component. Now, it will keep track of the current cell (so we don’t have to compute that every iteration) and provide new methods for movement, teleport and snap (soon). And it will update the current node’s position automatically, too.

One big commit

All of these changes, plus a couple more, have been pushed to the devel branch in Github. Feel free to take a look here

Bonus track: Math fixes

I took some time to revise and improve some of the math tools related with nav meshes, like planes, distance and intersection methods. It’s funny how there’s still a lot of room for improvement in code that I’ve been using for the past 10 years or more…


Sorting particles the right way… I guess…

Close your eyes.

Actually, keep them opened because you have to keep reading.

Imagine a train moving at a constant speed. You’re traveling inside the train, in a seat near a window. There’s a computer resting on a table right in front of you. On its screen, a random frame from a secret project is being rendered looking like this:

Screen Shot 2017-09-09 at 12.10.35 PM.png

The Problem

The above image is the result of using a mixture of offscreen render targets and particle systems to generate a lot of soldiers in real-time, in a similar fashion as other impostor techniques out there. In this case, each particle represents a group of soldiers (in order to avoid clones as much as possible) and they are walking from the left to the right of the screen. Don’t pay attention to the bearded guy at the front.

Did you noticed how the “density” of the soldiers seems to increase after some point at around the middle of the screen? That’s the symptom for the problem. Particles are generated using a uniform distribution random algorithm, and therefore there’s no reason for the empty spaces between them.

If we look at the debug version of the same frame, we would see something like this:

Screen Shot 2017-09-10 at 5.18.59 PM.png

As shown in the image above, the particles are indeed uniformly distributed. Then, where are the soldiers?

Here’s another clue: if I turn the camera just a little bit to the left, I get the following result:

Screen Shot 2017-09-10 at 5.22.22 PM.png

This seems to indicated that, although the soldier-particles do exist, they are just not being rendered in the right way. Actually, I’ve dealt with this kind of problems before and they always seem to be related with object sorting and transparency.

Distance to the Camera

Before any particle is rendered on the screen, they must be sorted in the right order for the transparency to work. OK, so particles are not being sorted and we just need to implement that, right? Alas, after checking the code, it turns out that the particle system does perform sorting over live particles, ordering them from back to front based on the camera position. And yet the problem remains.

It turns out I was making the wrong assumption here. Particles are being reordered, true, but the algorithm handles them as points instead of billboards (quads that always face the camera).

Let’s look at the following diagram:


The above diagram is quite self explanatory, right? No? OK, let me try and explain it then.

In the first case, particles are sorted using the camera position (just as in the current implementation). There are tree distances to the camera (d1, d2, d3). If we use the camera position as reference, the order in which the particles will be rendered will end up being 3, 2, 1 (back-to-front, remember). But that result is incorrect.

Particle 2 (the one in the middle) is indeed closer than particle 3 to the camera position, but it should be rendered before particle 3 in order to prevent artifacts like before.

Near-plane distance

The second scenario is the right one. We have to sort particles based on their distance to the near plane of the camera, not its position. That way, particles are correctly rendered as 2, 3, 1 (again, back-to-front).

This change produces the correct result:

Screen Shot 2017-09-10 at 5.32.11 PM.png

All soldiers are successfully rendered and our army is completed.

Final comments

We should keep in mind that, while this method fixes this particular sorting problem, it may not work when particles are rotated or they intersect each other. There are other approaches that attempt to solve those cases and, depending on what we’re targeting for, those might end up being too expensive to implement.

That’s it for today. Time to get back to my cave now.

See you later

PS: If you’re still wondering what that thing about the train was, well, I guess I’ve been watching too much Genius lately…


Crimild v4.6.0 is out!

Crimild v4.6.0 has just been released!!

This new version includes the long awaited Navigation Mesh support. Now you can have characters running around your scenes without them walking through objects and walls.

Screen Shot 2017-09-03 at 7.30.49 PM

Other improvements and fixes included in this release:

  • Version control for streams
  • The particle system update can be pause and resumed
  • The Console now supports for a command history
  • Composite render passes
  • OpenGL Core Profile 3.3 by default

Check out the full release at Github!

All demo projects have been updated to use the latest release. Make sure to take a look at the newest Navigation demo to see nav meshes in action.

Finally, if you haven’t done it yet, check out The P.U.R.G.E. Protocol, a game developed in under 48 hours for the latest Ludum Dare Compo using Crimild, of course.

Screen Shot 2017-07-30 at 4.32.11 PM