Thursday, 14 November 2013

Thursday Spacial Indexing

A Rare Day

It is not often I read up on contemporary literature of the day, as my old school habits lead me astray towards the 'do it yourself' approach. Today however I was impressed with the promise of a C++ library called BOOST to spend some time on pure reading.

A pretty well rounded library, and a fiendishly fast set of routines to speed up spacial searching and database creation. After 2 hours of reading, I had learned the API and all the examples, and was ready to do some prototyping. I then decided to sketch out what I needed to build a much faster scene management system for Reloaded.

After two pages of A4, it was apparent that for my initial coding I did not need a spacial query system as the current system I was using in the Instance Stamp system was FASTER than the BOOST library, and used only marginally more memory.  I thus decided plan A was to re-activate the Instance Stamp solution with the changes required to reflect the way static entities exist in the current engine. So I don't chew off too much, I have put occlusion and quad engine to one side so I can focus on the 'up close and personal' polygons that would surround the player immediately in the scene.  From there, I can create bounding volumes of geometry to reflect the instance stamp buffer collections and do the occlusion, and finally fill the missing 'distance' objects with quads. My sketch told me the order of the work as well as highlighting the specific details of what was missing to get from task A to task B.

Instance Stamp

As a recap, instance stamps is the idea that instances of objects are placed in a reference grid, and when the player is close enough to these references, a dynamic copy of that geometry is created in a common buffer for rendering. As it moves out of view, the dynamic buffer is destroyed and as new references come into view, they are created using the discarded buffers. Essentially the level can be extremely large without consuming a large amount of static geometry memory.  The performance hit is the dynamic creation, which if kept low enough becomes completely unnoticeable (and in prototypes have proven I can achieve hundreds of FPS no problem).

It's about 9:15PM now and my plan of a regular day went out the window today as I only rose after dinner time, meaning my day was already on a skew. I also have a 5AM appointment on Saturday which forces me to either stay up amazingly late on Friday, or go to bed insanely early to get up on Saturday before the larks and seagulls.  I have no doubt I will manage it either way, but it makes for an interesting schedule between now and then. It is for this reason, and while my brain is keen, to get some of the instance stamp engine coded now so I can see some early results.  All the commands are still in place from last time, so it's just a case of familiarizing myself with the old prototype, and migrating those ideas over to how the static entities are situated right now.  Hopefully before Friday I can report a speed up :)

Signing Off

Looking back on my blogs, I must apologies for the lack of screenshots and lovely eye candy.  This is the essential truth of the programmer, and what most weeks actually looks like down in the coding dungeon. Lots and lots of ideas, much code and very little visuals to show for it.  You only get visuals when some PR guy taps you on the shoulder and asks for something 'real' to show :)  Alas, this is the way of the world.  Until my next 'real' blog, I shall continue to crank out more of this alien gobbledygook and look forward to the day when I can report some serious performance boosts.

In the meantime, here is the small scene I am using as a template to first test my instance stamp batcher and ultimately my occluder.  As you can see, from an FPS point of view, and with occlusion working, very few of the buildings should ever actually be rendered and result in low polygons and draw calls, and high FPS as a result. Here's hoping!!


  1. More progress every day lee,keep it up.

  2. I know what you mean by old school. I can't seem to break out of "C" (without the pluses). I did make it to VB6 because that's where it ended as I retired just as ".NET" came out. :SMILE: