Tuesday All-Nighter

Day Night and Day

The view from my office window has less snow in it every time I look.  My day started about 4PM Monday and apart from two hours to eat one meal and 30 minutes to eat a second meal I have been at my keyboard the entire time, and it is now 2PM on Tuesday. That's 22 hours minus 3 hours solid typing text and reading text. Not even any FPS games in there too, just solid graft.  My mission is to get this 'go to bed' trick accomplished. I messed up on Saturday Sunday when I passed the 7PM milestone, got my third wind and worked through to 2AM. This time I plan on pulling the plug at 7PM and collapsing. This should get me up in the AM for Wednesday.  Let's hope.

Emails and Things

It is fair to say lots of my hours are spent answering emails, blog comments, forum posts, chasing bits of AGK work and generally bobbing about, but it never really feels like progress to me. Today I have progress to report.

My Progress

I decided to kickstart the P002 prototype on Monday evening, which was to tackle the visibility occlusion (or hidden surface removal) problem. The old system chopped everything into a 100x100x100 grid and attempted to make portals out of everything. That ate memory, took ages to build and the result was not super fast or 100% reliable.

My new idea is to keep it simple. Give every object in the scene a sphere and bound box (and convex hull volume if need be), then produce occlusion volumes for each object from the cameras perspective. Anything entirely enclosed in one of these volumes gets hidden, and also removed from the occlusion test (as it is a given that anything they may have occluded has already been occluded by the larger volume that swallowed it whole).  The sphere to volume check is quicker, so will act as an early out condition and speed things up.  I am also tinkering with the idea of grouping objects casually into a basic hierarchy, simply to allow all objects contained in what will be understood as a large interior space to be occluded in one go if the entire encompassing structure is hidden. That is, if there are 200 objects inside Building A, and Building A is occluded/hidden, then I instantly hide the 200 objects inside that building by traversing a pre-prepared list of objects, rather than asking each object if they where inside the building (in real-time). I won't go nuts and put everything in a hierarchy as tree traversal can be just as costly when you have n * n to deal with, but something efficient that makes sense would be smart.

This P002 prototype will NOT take a weekend as I have to write my own 3D vector / plane / volume / frustum math code, and it takes my brain a while to wrap itself around it.  After a good 4-5 hours the current prototype creates 100 objects randomly in the scene with a camera roaming around, then works out the bounds of the box and produces eight vectors, one for each corner of the 3D box in world space, then works out a left and right plane from the camera to each side of the box. This effectively allows me to hide any objects that are to the right of the left plane and the left of the right plane. It works great for two planes, but for my next version (on Wednesday) I will need top and bottom planes and up to three front facing planes to describe the visible faces of the box. Also all boxes are current unrotated so you only ever see two sides, but ideally I want to spin all boxes in random angles on three axis so I can create an occlusion volume that perfectly matches the shape of the oriented boxes.  The far plane I can forget about as it stretches into infinity and I absolutely want to hide everything beyond the box. I then apply this technique to every box in the scene and in theory each box should be able to hide every other box no matter where the camera is placed, even if it is placed high up looking down on the boxes.

All sounds a bit complex without lots of illustrations but a simple search on Google should show you what I am talking about as it's a common technique in most engines.  If I need more definition I will upgrade to convex hulls or quick hulls which will enclose the object much nicer than a big stonking box, but we will see if that is required.  The key here is to get a technique that FPSC Reloaded can use for outdoor and indoor scenes, and the best way to know that is to mock-up some typical scenes and throw this new occlusion system at it.  Ideally I want to start with a disorganised scatter of seemingly arbitrary object meshes, and have a system that automatically groups them and then occludes them, all at real-time speeds (no build time allowed).  If I succeed, I will have defeated the second biggest bottle neck of FPSC. The first being light mapping which was squashed thanks to P001 prototype (see previous blogs).  Once P002 has been conquered, I will play a little more FPSC classic to see what the third biggest bottle neck in the build step is, and come up with an P003 that defeats it.

Signing Off

Have a good five hours still to go, but I am over the hill now so it's just a case of keeping busy until 5PM. An FPS game might be in order, but my inbox generally fills up in the afternoon so I dare say more important things will emerge as the afternoon unfolds. Last time I made a snowman to keep myself awake during the weekend. This time there is only enough powder for a snow gnome one foot tall so that's definitely out.  Coffee is also not a good idea right now. I will probably open up Google and do some casual research into techniques such as LPP, occlusion tricks, real-time shadow mapping and the like.  All useful stuff to pack my brain with for the many tasks ahead!