Friday, November 25, 2011

First generation 3D engine done!

Finally! 'Tis done! The first generation of my 3D engine is done! I fished it a couple of days ago but it has been a terribly busy week so I did not have time to post.

So I'll go over the final touches faster, but compensate by talking about next steps a little.

First, I finished the fine tuning and profiling for LOD switching. The problem was with the buffers: I have two arrays for each buffer, one for vertices, one for indices. Pretty standard stuff. In Irrlicht these arrays are instances of the standard Irrlicht array class and you use push_back to add items, which in turn calls a standard insert. Normally I am a huge proponent of using standard containers everywhere and amortized constant cost growing containers, but here it was performance bottleneck. Check out the code for insert. First is check if it needs to grow the container. Because of the volume of data I have to process I made sure ages ago that containers do not need to grow. Array capacity is computed and stored for future use and when you create a buffer the arrays are automatically set to required capacity. So insert will never enter the grow path. But still, this is a completely unnecessary if in my case. Then it checks if the item is inserted at the end or not. I always insert at the end, so this is a second unnecessary if. So basically, for every single vertex or index, I get two unnecessary branches and only after you fall though them you get to the desired code. Then, I have one extra if that is necessary and introduced on a higher level by me for each vertex/index. So why am I bitching about 3 ifs? Is this not a premature optimization? Well, no, since in the context of the volume of data processed and the requirement of real time camera movement, 3 ifs have a noticeable impact on the smoothness of movement. I eliminated these ifs and rewrote the insertion code to use pointers. The solution is less elegant, but it was worth it. The great part is that this code could work for (unmanaged only?) C#, which supports pointers. I couldn't implement something as computationally intensive in a managed environment because there arrays are checked both for insertion and access.

Then I managed to get XEffects - Reloaded to work. Had to chase down a new modified Irrlicht DLL, but in the end it worked as advertised. Only it does not fit my needs. You see, lighting is an art. More so that a lot of other things. And it is hard as hell to do. Lighting is single-handedly the most difficult task I have encountered in this project. I went over several iterations of it. A few night ago I spent two hours just tweaking lighting. Right now I am using a 3 light system: a spot light and two directional lights to simulate outside lighting conditions. Light only illuminates items, terrain is not illuminated because I can only get if very dark and not uniform or extremely bright. Lighting and stencil shadows are somewhat decoupled. but with XEffects and shadow mapping, lighting and shadows are very tightly coupled. So I was forced to illuminate terrain. In the end I almost managed to get illumination to look like and outside scene, but here is where I found the first big obstacle: realistic lighting came at the price of having to position lights very far away from the terrain. Shadow mapping is very dependent on the distance between the light and the object it illuminates because it works with a fixed resolution shadow map. So with the distance I was using shadows for objects were barely a few pixels wide in the shadow map.

The second problem is probably related to the complexity of the scene: it is so high that I had to modify Irrlicht in order not to crash. XEffects also crashes. I could only add shadows to terrain and other discrete meshes  like dwarves. When adding it to the item meshes, it would crash as vanilla Irrlicht does.

So in the end I did not manage to get XEffects to take over shadows for me. I did learn some important lessons and I think I know what can be done: either figure out a new lighting model that does not rely on distant lights, or create a special version of the XEffects shadow mapping tehnicques that decouples lights from shadows. Use the isolated lights to illuminate everything and a directional shadow with a fixed "reach", similar to the case where you would have shadows cast for every object by one light each that is very close, but follows the direction of a sun ray.

Needless to say, my skill level is no way near the level it needs to be in order to implement such lighting and shadows. And it would take me months to implement and test it. So I'll stick with stencil shadows for now. For Tech Demo 1, there will be two options, one controlling item shadows and one controlling terrain shadows. Low LOD objects do not cast shadows. With low item density performance is more than acceptable with stencil shadows, with medium density it is way to slow, so shadows must be turned off and with very high density the engine crashes.

The engine can also handle animations as long as the number of actors is low (hundreds at most). I am yet to find a good format to export meshes with skeleton animations from Blender, but meshes that are already exported work fine.

Reading this you may be wondering why I am not using an existing engine for this game. Well, first of all, Irrlicht is considered a 3D engine, so probably the discussion should be about higher level engines. Finding such and engine is not a trivial task. Even if I were to assume that porting to the new engine would take zero time and effort, I have very specific needs. I need a fairly high level engine that can do a lot without the standard overhead of high level engines, while being focused on supporting huge number of objects and destructible terrain. I am not aware of such and engine and if one exists, it would probably have steep licensing fees.

When working with engines it is the small details that get to you. Let me give Ogre3D as an example. Ogre3D requires each scene node to be identified by an unique identifier. The documentation says that it checks the identifiers and gives an error if it finds duplicates. Identifiers are strings. Not let us consider my video about 300k barrels and let's consider that each barrel would be an unique scene node (in my implementation this was not true; I used batching for performance reasons). So I would need to create a fast algorithm that assigned 300k strings to nodes on the fly and pray that Ogre3D finishes the checking fast enough. You may think that this should be fast, but I had problems with 3 if statements. Even if this discussion is theoretical, who know what Ogre3D does behind the scenes and how fast it is. So before I can choose an engine, I would need to do a very thorough evaluation of each and make sure that such details are never and obstacle.

So what next?

I don't know about you, but I am getting tired of working on the engine and would very much appreciate a palette cleanse. A second generation 3D engine will be created, but I am sincerely hoping that I wont start working on it until March 2012 and spend that time on fishing workshops and crafting. Workshops will be my next focus, with some effort spent on the overworld map.

But December is not going to be a productive month. With 3 official holydays and at least two larger events I won't get that much work done. Still, updates will come. I'll put the code base on feature freeze for Tech Demo 1, iron out a few bugs and search for a good installer generator so I can make it available.

Since most of the changes are implementation details, I can't find a screenshot to summarize up the progress since it would look like previous screenshots. Or maybe I can:

Here's a lovely levitating land trout. A formidable foe indeed. A bane to the existence of any peaceful fortress! Thank you very much InfecteD for modeling this beast!

PS: I really need to add a test skybox, maybe something from here:


  1. Ahahaha, I love the trout :D

    Good work!

  2. I'm still not sure why... Why do you need a full 3D system for a DF-like game?

    Granted, one of the biggest problems with DF is the complete lack of any interface work that renders the game pretty much unplayable for me.

    But it looks like you're going entirely the opposite way. You've done so much work on interface stuff, but you don't actually have a game. You don't really have anything at all. There's a bit of stuff on world gen and whatnot hinted at, but that's all directly taken from DF.

    So I guess, the question again is why?

  3. You don't need a 3D engine. On the other hand, there is nothing stopping you and since it was not really done before it is a great opportunity to do something new and extremely challenging. There is also the fact that this is a long term project. Like you said, it is a DF like game and developing something like this alone takes years. Maybe by the time it is done there won't be any 2D games left :). A frikin' smart phone that you can carry in your packet is stronger nowadays than one of my older computers which still lives today.

    Also, the interface has not gone anywhere. It is just hidden because of a random DirectX bug that I am not sure I fixed yet. But I agree that it has been quite a while since I last shown the interface.

    I will create a video showing interface interaction and a few actions from a more traditional topdown/isometric camera to demonstrate how it looks and feels with the new engine.

    The overworld serves two purposes. One is to have a persistent world where you can create multiple fortresses and what now. The second is to provide "natural borders" around the expedition area. I do not like the look of a square landmass floating in void.

  4. I can recommend Inno Setup as your installer. Its a pretty smart program, and very intuitive.
    And its free =)

  5. Why would you need an installer? Surely you can just zip the folder up and create that as you download. Installing tech demos is no fun.

  6. Ok random question but... if it is going to be similar to dwarf fortress then can you make characters out of pieces?
    Like if you chop of hand or leg you can see it flying off or chopping somebodey in half....

  7. mmm, to much time without news :S

  8. Maybe the tech demo is being readied?

  9. Are you there my good sir?

  10. It's been a month... what now?

  11. The masses clamor! No time off for you!

  12. It's 2012, let's see some updates!