Beamcasting

I am Topi "Sharph" Talvitie, the other coder in the Umbrella Project. I've been mostly helping with path finding related algorithms in the project.

Efficient path finding algorithms run on a graph of links between vertices. These graphs are a bit large to be distributed as precalculated data, so they need to be generated at runtime. If possible, this process should be fast enough to be unnoticeable. Our solution to the problem is casting a beam from each vertex to find the vertices that this vertex is linked to.

In the figure below there is a beam (the red area) cast from vertex A of polygon P. The vertices seen from vertex A are circled.



If we are able to query the whole visible polygon from any point, we can use the same algorithm for many interesting effects too, such as checking if the player is seen by a character in the game. Thus we need an algorithm that can cast a beam from both polygon vertices and free space.



So how to do this efficiently? After considering some grid accelerated algorithms that turned out to be quite complex, we realized that a triangle tessellation (triangulation) of the map would be very useful.



We will shortly describe the algorithm. There's still a cake for you in the action phase after that.

Initiating the Cast

Because the polygon map is tessellated, the starting point of the beam O (lower right) is an interior point of exactly one triangle T. We divide the beam (lower left) into at most three smaller beams (lower right: A, B and C) by splitting it by the sectors to the triangle edges.

Each of these smaller beams sees exactly one edge of the triangle T. If that edge is a wall of a polygon, just add it. For the unblocked beams, we advance to the next neighboring triangle. (N1 for A, N3 for B, N2 for C)



The case of starting from a vertex is very similar.

Recursion

In the recursion step we consider a smaller beam, recursed to a triangle (the lower triangle in the figures below). Due to splitting the beam when entering new triangles, the beam will enter the neighboring triangle (gray) through exactly one edge (L-R).

We take the line to the opposite vertex of this new triangle (lower right, O-S) and use this line to deduce which neighbors of the current triangle (gray) will need to be recursed into. If both edges (L-S, S-R) are seen, both neighboring triangles will need to be analyzed (lower right).




If only the leftmost edge is seen, only the left triangle will need to be analyzed (lower left). If only the rightmost edge is seen, only the right triangle will need to be analyzed.





Again, if the triangle we are advancing into is part of an obstacle polygon, just add the edge. And finally, to keep the result polygon correctly ordered, the search should be done depth-first and always to the same direction first.

There exist many good libraries for triangulation. We used poly2tri, licensed under the New BSD License.

Something to think...

It is proven that in pathfinding, links from vertex A to vertices in beam C are not needed. Can you figure out why? Might be confusing at first!



And at last...

Action!

We prepared a scene for your investigation for this very realistic simulation of a
crime-in-action, a western style bank robbery. The blue casting star represents the sheriff and the red casting robber represents the bad guy. Enjoy!






(Written by Topi Talvitie, edited by Markus Kettunen)

2010-10-18. A Game Engine from Scratch

After modifying the collision detection algorithm to suit a vector map, and fixing some very nontrivial floating point problems I decided that it might be time to take a step towards the level editor. Back then I had no nice means for more advanced interaction with the user, so my next step was to make a widget system.

While playing with Google's V8 engine, which I later abandoned, I had become familiar with Javascript and its event system. I found it quite nice so I decided to take its design as a base for designing my own system. It appeared to be a rather good plan.

Here is the debugging view I used at this point.



On the left lower corner you can see some widgets, one of them showing the mouse position and the other being an automatic FPS calculator. Whoa!

The small squares in the ground show the space division that is used to accelerate collision detection. Collision detection against the walls only needs to be done when the player is inside one of those bluish rectangles, and only the walls going through the same rectangle need to be checked against. In real use, though, the rectangles should be a lot larger.

Another noteworthy object in the picture is that steamtank. Alas, this time without all that eye candy. When the time is right I will have finished generalizing the rendering engine for arbitrary scenes, also supporting a large variety of options to make the game playable on a bit older computers too. This is something that I'm doing with ubershaders, though more on them later.

Currently I'm writing a more user friendly exporter for Milkshape 3d for our model and animation formats. Why not use an existing format? That's an interesting question with an even more interesting answer. I have also been rewriting the animation system to better support animation changes. But all this will be ready soon enough, and there will be so many interesting things to discuss.

It surely isn't a small job to make a complete game engine from scratch, but it's so much fun!

2010-09-12. Path finding

After abandoning V8 I wrote some code for collision detection. The plan was that our maps would be made of squares, and inside those squares we would have a grid for more precise collisions. I also wanted that the player would slide along the walls instead of getting stuck, so I needed to do some raycasting. The resulting collision map would be too large to keep in memory, so I ended up writing a system for raycasting edges that were created in real-time...

At this point another competent coder joined the team and we were discussing path finding algorithms for the game. He made a quick A* implementation for testing, and it was soon apparent that the desired grid size was far too large.

After thinking of this for a while we deduced that our lives would be much easier if we changed the maps into vector maps and forgot about the tiles. It also made my life easier. This one was a really good decision!

One of the problems we had with the new polygon-based path finding algorithm was that the precalculation time required for fast path finding would be all too large. We needed to search all the visible polygon corners from all the other polygon corners in the map. Each one of these would require checking all the other polygons. This was unacceptable. Moving from a map to map had to be fast.

Even after heavily optimizing visibility tests: raycasting with grid-based acceleration and limited polygon density, it would still be at least O(n²). For fast precalculation times we really didn't have the time to find all the visible corners. We needed a local approximation, caring only of the nearest polygons. We achieved this by limiting the visibility range and adding 'dummy points' where there were no polygon corners nearby, to connect to the far-away polygons. The resulting precalculation time was unbelievably fast and the actual path-finding part didn't suffer much.



Here's an image of the precalculation process. The green grid represents the grid used in the acceleration. It should be a lot sparser in a real use case. The blue polygons represent the actual walls used in the path finding, pulled out from the red original walls next to them. The resulting, somewhat optimized network of links, is drawn in red.

This local system requires the found route to be cleaned afterwards, by dropping any possible unnecessary waypoints. But there's also a bug in the image. Can you spot it? Can you be sure? :-)

2010-07-26. Scripting with V8

Map scripting

After a long break in writing here I'm back again, and the project has taken some nice steps forward. We have been researching useful scripting languages for map scripting. This process isn't what I'm most interested in, nor does it produce cool images, so I haven't been too motivated to write about it before. I will now, shortly.

To implement complex behaviour in maps we need to use some scripting language. Common scripting languages include Javascript, Lua and Python, among others. These all have been good candidates for us.

At first I took a look at embedding Python into a C++ program. Python's micromanagement of resources, like manually incrementing and decrementing reference counters, looked shuddering. It's also a rather slow language, typical efficiency (compared to C) being around 1/200th.

I had also heard horror stories about people needing ridiculous optimizations in their Lua scripts to get even decent speed. On the other hand, Google's Chrome is one of the fastest web browsers out there when it comes to Javascript. And Google's Javascript engine, V8, is out there for free. And it natively supports C++ too. Javascript by itself isn't a dirty language either. Sounds like a dream, no?

I took some time to experiment with it. I wrote wrappers to understand it better, experimented with it, made test APIs and tools and other small libraries for it. It worked somewhat, but I ended up rewriting stuff too many times, trying to find a clean general solution for my needs.

There wasn't too much documentation for the new V8 library yet so I ended up having lots of trouble and frustration with it. I had gotten it to work, even in a way that would be useful for a small project, but I couldn't get it clean enough to use in a large game, without the frustration of having to cope with dirty code.

On top of that, when trying to compile Sad Umbrella for Arch Linux, it then appeared that the V8 release didn't even compile; it had constructs in the source code that weren't supported by the newest GCC version. Maybe they have fixed it by now, maybe not, but that wasn't the only Linux distribution having problems with V8. Many other people reported difficulties getting V8 from their Linux distribution's repositories, and it would be almost impossible to get V8 for a handheld device. If we ever decided to port the game for one.

I feel the library is still too immature for actual use by 3rd parties.

2010-05-19. Music for the Umbrella Project

Coining the term 'idea music'

I am Pauli "Gwaur" Marttinen. I am the appointed composer for the Umbrella Project, though one other composer has also been invited to fill some of the stylistic gaps that I don't span. I specialize in music in the symphonic or otherwise classical sense. I am far for being a pro, but I'm aiming for professional studies in percussion and/or conducting.



At this point of the Umbrella Project, virtually no game exists. There's an incomplete graphics engine, the game and scripting engines are just being conceived, and the plot setting is only starting to get out of the "vague idea" state. This is the opposite of an ideal phase for making the score: I have no idea what I am making music for.

I have practically no mental image of where the project is headed to. There's too little concept art, 3D models, scripts or storyboards to follow. It is hard to get any inspiration that's directly linked to this game. If I make a piece of music for the game at this point, who knows if it will it be used in a cutscene or a playable place, or in the closing credits? Should I make it repeatable? Should I make other versions of it, for different situations?

It is of course never a bad idea to store ideas beforehand. Even if a piece I go ahead and finish now will ultimately be unused, ideas can be recycled. Maybe a new piece with a new structure but some same themes. Or the same structure and new themes in the same style. On the other hand, changing things may be difficult if, for instance, some pieces have music played with real instruments instead of computerized ones.

Something like this has been done at Studio Ghibli, a film studio that produces some of the most popular animated features. If you look for soundtracks of Ghibli's films, you might come across some albums subtitled "Image Album". These are albums of music inspired by storyboards and concept art, composed by the composer in the earliest phases of filmmaking, as opposed to music often being one of the last things to be made. With this, the composer has more time to fine-tune the music, discard some and make some new, according to the project leader's wish.

In our case, we are currently trying out something I might call "idea music" instead of image music, since we have no images yet. What happens right now is that the project coordinator asks me to make "something based on this idea". I try to follow that idea, make something, and suggest whatever I come up with. By now we have three pieces of music, but none of us knows exactly where and how to use them.

Things are starting out slow, and there are several reasons for it. None of us are professionals, and we have little experience on working on such an ambitious project. We live quite far away from each other, so we are relayed through the Internet and seldom meet in real life, but the Internet doesn't always do it for you. Also, frankly, my personal video game interests don't match with this one. ;)

2010-04-18. Emission maps

Terrain generation from a height map

I spent some time pondering how to implement terrain to the engine. The choices were either heightmap-based or tile-based terrain. Tiles fit the engine better but our modeler already has enough work... We'd need a second modeler I guess.

The initial plan was to support multiple levels of detail (LOD) and draw areas farther away with less triangles. But I also wanted the terrain to have adaptive precision. Combining these two proved to be quite tricky.

Here are some results of the tessellation algorithm I wrote. The sand castle is only a test to see how the algorithm does. No castles like this in the real game, done with a heightmap at least.



The results are quite nice. This is the same with real shading:



Sadly, with adaptive terrain it's not easy to make the level of detail changes seamless. There would be unacceptable artifacts, pixels of the sky seen through artifacts in the height map. No wai.


Edges again!

Someone complained about the jaggy edges in the pictures. HDR rendering requires rendering to texture but rendering to texture with high precision doesn't support Multisample Anti-Aliasing (MSAA). This means there's not much I can do without a huge cost, like using Fullscreen Anti-Aliasing.

There is still hope, though. An OpenGL extension named GL_EXT_framebuffer_multisample could possibly save the situation. I must take another look at it later.

Inspired by the complainment aboud jaggy edges I decided to try enabling the edges again. Jagginess still persists but it might be a bit better.




Light bleeding

If you take a close look in the fullscreen version of the picture above you can see that the shadows aren't as soft as they used to be. This is because I encountered horrible light bleeding with the variance shadows. You can see some of it in the image below. Please don't mind the burnt terrain, it was a bug in the terrain normals.



Now this doesn't look much like a shadow, does it? This is why I replaced the shadows with a quick implementation of Percentage-Closer Shadows (PCF).


Emission textures

I watched some demos from Breakpoint 2010. One of them had very impressive lighting effects. I wondered if I could produce similar effects too.

This effect is done by giving a material a high emission factor so that it is self-lit. Now that its color is very bright the bloom filter of HDR rendering gives it a nice halo, making it look very bright.

Our modeler, Juutis, had been asking for specular maps for some time. I hadn't implemented them yet since there were no free channels in our textures. But now I needed another channel for emission so it was clear that I needed to replace the traditional material-wide properties with an emission-specular-diffusion map.

Here are a few samples with some temporary hearts and a lit warning label. ;)






Cel-shading?

I took some time to play around with cel-shading. I'm not sure how well it fits a HDR rendering system, but at least I figured that cel-shading systems need a huge amount of parameter tweaking to get them to work in different lighting options.

I don't find these results very pleasing but I thought it would still be fun sharing them. But this is not the direction we'll be taking in the near future.

2010-04-05. Death to the bottlenecks

Larger VBOs for speed, yes?

While playing with the engine I noticed the steamtank looked possibly better without the dark edges so I took them off. I may put them back later though. We'll probably play around here quite a bit.

So here I was at 20 fps with a cool Steamtank. I decided to add another tank and boom, frame rate was down at 10 fps. Huh? For other computers this didn't affect the frame rate at all. Yummy.

At the moment I was using Vertex Buffer Objects of size of one mesh each, where by mesh I mean a part of model that consists of a single material. I have read that the VBO size should be kept between around half and two megabytes. Mine were closer to few dozen kilos, so maybe this was a source of slowness? I went and combined the VBOs.

Here's a screenshot I took while the process wasn't quite ready yet.



Got it ready and, oh the speed increase. Frame rate had dropped from 10 to 5 per second. Software fallback? Too large VBOs? Pfft.


No software fallback for me, please

The size of my vertex information was 76 bytes per vertex. It had vertex position, vertex normal, vertex tangent, four joint IDs and four joint weights for skeletal animation. It's said that this number should be a multiple of 32 bytes for best performance. Our model was using at most two vertex weights so we thought three vertex weights should be enough, saving 8 bytes. As the sum of the vertex weights has to be one, I could calculate the third one from the remaining two in the vertex shader. I had reached the goal of 64 bytes.

No significant performance increase.

Then something caught my eye. Everything else in the vertex information was floating point numbers but the joint numbers were integers... Like they naturally should be. I vaguely remembered that for optimal performance only floats should be used here, but at the time I read this I didn't pay too much attention to it. I tried changing them to floats and boom, the program was running at 45 frames per second. Huh!

Apparently the graphics hardware didn't support integer parameters in the vertex structure so it resorted to software fallback instead... Vertex shaders in software, no thanks.

Here's a video capture of the engine running at 40 fps on HD 4650 Mobility with resolution 1280x720.



Oh and by the way, toggling larger VBOs increases the frame rate by around one frame per second.