Recast Detail Mesh Fixes

I just update the detail mesh generation code in SVN, which should improve the possible bad cases of the detail mesh generation.

One case where the detail mesh generation failed previously was the Delaunay triangulation which is used to generate the triangulation of per polygon detail surface mesh. This should be now fixed.

Next time around I will design a system which will dodge any kind of triangulation.

The algorithm is a little slower than the previous one and has worse big O behavior too. So large areas will take longer time to compute. If you have really horrible performance, I suggest using the tiled mesh generation so that larger polys will be split because of the tiling.

Another case where the detail polymesh was sometimes bugging out was how the height samples were picked from the voxelized representation. This should be improved now a bit, but I was not able to create a simple fix for the case where radius is zero. It is surprisingly complicated task to gather all the height samples which fall under a polygon. Most of the time it works ok, but some corner cases are just nightmare to get right.

So, if you have had problems with the detail meshes, grab the latest source from the SVN and give it a go.

[EDIT] I also added few convenience versions of rcRasterizeTriangles. One which accepts indices as unsigned shorts and another which can be used to rasterize non-indexed meshes.

Delaunay Triangulations

I have a love-hate relationship to all kinds of triangulations. They are super useful tools for many problems, but at the same time they are super annoying to get robust. I have been pounding my head to the wall trying to get one Delaunay triangulator to work properly.

Bourke's code is broadly used and seems quite robust too, but it fails to deliver one feature, convex hull, which is really important for my use. This seems to be common problem with Delaunay triangulators which rely on super triangle as the initial state of the triangulator.

After browsing through countless of other implementations and papers I finally found a O(n^2) algorithm last night, which seems to suit my need very well (I'm talking about the O(N^2) algorithm of the Java applet). I'm not sure which algorithm it is, it does not look like any of the usual suspects. But it does not require super triangle, and there is a case which handles the hull too. Even better, the algorithm behaves well even if manually set the hull edges myself. And finally as an added bonus, the idea of the algorithm is easy to understand visually, hence, I'm able to debug it myself too when I run into problems with it again.

Most (if not all) of the existing Delaunay triangulation implementations I could find out there fail sooner or later if you have points in your input data which are along the same line. That is a condition which majority of my input points satisfies.

I'm yet to do full set of test, but so far it looks good. The Java implementation has a couple of bugs in it, especially how it handles face labels.

Looks like I can finally move the detail mesh generation off the TODO list...

[EDIT] The algorithm in question seems to be a gift wrapping variant of Delaunay triangulation. See A Comparison of Sequential Delaunay Triangulation Algorithms, the papers that paper refers to seem to be pretty hard to find.

Blast from the Past pt. 2

I was browsing my old hard drive last night while trying to find some old material in preparation for a lecture in a local game dev school. I found a couple of good docs I've written in 2006, which I thought would be worth sharing. The grammar in the docs is the same awful you are used when reading this blog.

Moppi Flower Explained
During the years, quite a few people have begged the source code for our demo from BP'04. Instead of sharing the code, I thought it was better to share the knowledge.

Proto Watch
I got a nice and shiny wrist watch for Christmas Present in 2006. It had the most horrible UI ever! Since I did not have internet at home during the Christmas breaks since my room mate took the ADSL modem with him, I thought I'll try to see if I can figure out a better UI for a wrist watch.

For the sake of proving my point, I also wrote a simple prototype of the concept. All the functionality was written in C using only unsigned bytes. I wanted to implement the using a micro-controller too, but then the company I was working for at the time decided it was time for yet another crunch. So we crunched instead.

Blast from the Past

I just found this nice repository of old from from International Joint Conference on Artificial Intelligence. Lots of good stuff all the way from 1969.

http://dli.iiit.ac.in/ijcai/


One of my favorite findings was this paper from 1989 (If not mistake, the classic paper on velocity obstacles was published a decade later):

A Maneuvering-Board Approach to Path Planning with Moving Obstacles
Lou Tychonievich, David Zaret, John Mantegna, Robert Evans, Eric Muehle and Scott Martin


The year 1989 was like 20 years ago and yet we manage to produce games where NPCs have trouble avoiding walls and other kinds of minor things. So nice we have Google nowadays.

One quite important trick present in that '89 paper, that is missing from the Fiorini paper (IIRC) is the cone truncation. Applying the truncation helps a lot in many practical cases. Especially when trying to reach your final destination. Gladly it is well represented in Reciprocal n-body Collision Avoidance.

Status Update

I decided to put the area stuff on hold for a while. The update was becoming too heavy, and I need to revise my plan of attack, and probably just simplify few things too.

I'm thinking about dropping the statNavMesh and just keeping the tileNavMesh and add helper functions to make the use similar as using the statmesh. It is already quite tedious to keep different generation processes as well as runtimes up to date when a new feature is added. In the same vain, I was thinking about to only use the monotone area partitioning. As it is way simpler than the watershed partitioning code, it is much easier to add new features to it, such as making it aware of the areas.

The current SVN version has several fixes which should make Recast to compile on Linux and 64bit systems. There's a couple of good bug fixes there too, which were kindly pointed to me by August Gustavsson. One was in the tile navmesh path finder and another was crash in the border vertex remove process.

The detail mesh has raised its hairy head again. The Delaunay triangulation algorithm I used to generate the triangles for the detail mesh does not always create a mesh which includes the convex hull of the points. Some of the Delaunay triangulators I have used in the past do that, though. I have tried a couple of alternative methods, but the ones which create the necessary convex hull usually create extra vertices along the tesselated edges or they crash in some sliver triangles. Do I just hate triangulations.

I will try to see if I can hack some sort of constraining code for the outer edges by flipping few triangles around after the triangulation so that removing the super triangle will not eat the useful triangles away.

I will fix the detail mesh edge vertex explosion on radius zero, too.

Tiles, Tiles, Tiles...

This is what I have been up to recently. The lack of updates the past couple of weeks is mostly due to my involvement in renovating my bathroom. It's been a lot of fun, but I think the romanticism of hard work is slowly wearing off and I'd like to do some coding for a change.

I have an apartment in an old building and none of the walls are straight, so I had to cut a lot of custom fit tiles around the walls. One interesting thing I noticed was that in order to optimize that repretitive work, I started to use fuzzy measures, such as "a little less than 5 cm" or "a bit more than 3 and a half cm" instead if 52 mm or 38mm.

In Finland we use metric system and everything construction related is always expressed in mm or cm (except two-by-fours and two-by-twos). But in places where imperial units are used you often see fractional units being used, for example something measuring 2"1/4 is not that uncommon. Even if I like that we have universal system of units, I think it is not very practical in many cases in every day life.

I want fractional measures back to metric system too. Humans do a lot of work using binary search when estimating measures. "Five centimeters and a half and a little less and nudge to the right" is more accurate than a millimeter!
__

Despite being engaged in that physical excersice, the work on Recast has not stopped. The area stuff has progressed pretty well. I have generation side working pretty OK. It needs quite a lot of clean up and API massaging to be released.

Quite a few people have also reported patches to make Recast compile and work under Linux and 64bit. I was silly to actually do those changes in the same codebase where I did my area work, so I cannot submit those changes quite yet. But for those who are waiting for it, those changes are coming.

Once I get all the hackery peeled off, I will release an intermediate release which includes some of the area progress as well as the Linux fixes.

Area Progress

I have got some pretty good progress on the areas. I have been concentrating on marking the areas. Volume based areas were pretty simple to do. So far I have only axis aligned box, but I do not expect the rest to be too complicated.

The height based areas were a bit more challenging. In above picture, the blue are is marked by the black box, the yellow area is where the character can stand, the red areas are where the character can crouch and on blue ares the character needs to go "prone". Those are dummy categories just to test that I can handle more than one height value.

That kind of sampling tends to generate a lot of small areas here and there. For example if a wall is slightly tilted, you may get one voxel worth of proning and three voxels worth of crouching. I tried several kinds of filtering methods to get rid of those artifacts.

First I tried median filter, but I either had to do too many passes or the filter ate away certain small bridge areas, which should have been left unaffected. After some fiddling, I tried similar filtering method I used for the region merging and it turned out much better. The filter checks adjacency, so it will not remove small areas which connects two neighbor regions (such as low doors), it does a bit smarter merging, so that tiny 'crouch' area can be merged to a 'prone' area but not to 'stand' area or else the character collision would fail.

Next up is to enable the partition system to understand the areas. I expect that to be the most challenging part of the this whole feature.