flipCode - Tech File - Conor Stokes [an error occurred while processing this directive]
Conor Stokes
(aka DirtyPunk)
Click the name for some bio info

E-Mail: cstokes@crytek.com

   07/25/1999, I'm Back Baby

Hey ladies and Gents, as the title says, I'm back. You see, I have been away. I got back just over a week ago, but soon I was off to school. Of course I have plenty of new ideas (not all of which will go here), and I have just had time to do some work.

Following Carmacks post about virtual machines, I feel inclined to talk about the virtual machine I have designed, and plan on implementing, after the renderer and compiler are fully functional (All the other stuff needed is). Now, I went down a different root to most people, in that the code I am using will be multi-threaded. Meaning that you can have many different modules, each with priorities, and they run by themselves, in their own address space. A group of the same threads can be in the same address space, but they require global variable locks, which stalls the system. So I intend to make most threads stand alone.

The advantage of using a thread system is interupt base priority. Basically, this is a clever optimisation, that allows you to cheat some. Now, this works on what I like to call my "Lazy Boy" system. In that, the engine gets away with doing the minimum needed to produce the same experience. Think about it. You may already be saying, "But that is just a crappy excuse," Yet already it is done all the time, with AI, LOD and others.

Now the idea of interupt base priority is to change "priority" when a specified "event" occurs (Dr EviL). Rather simple, yet rather potent. Windows does this, if an application is in the foreground, its thread gets higher priority. Think about Q3:A as a case. Now, the server code which John "Lay Down the Smack" Carmack is doing would probably include things like bot handling. Well, its obvious that if you handle 16 bots at once your frame rate is going to drop.

The problem is, bots, unlike other AI monsters and such, need to still be moving and thinking, even if they are invisible to you. The AI of bots is also more CPU intense than that of monsters. Oh my. We have a problem brewing here. Now here is the kicker. Even though bots still have to be "moving", they don't have to move every frame, if they are not visible. So, if you update your bots at 2 frames per second, put an interupt on the event of a bot becoming visible, which bumps the priority up to realtime (every frame per second) you are going to realize a bit of CPU saving. When all bots come on screen at once, CPU time will drop. But, chances are you will only have one or two on screen at once. Pretty simple.

So, if you work on FPS, you don't really need a complex schedular to do threads. Now, the major bottleneck is thread communication. Messaging systems would be the key to this bottleneck. So, a usual message stack will not do. You must change to a hash style table, with trees in each table slot. So, messages are sent and checked based on thread id (which would be only a word, I can't imagine running more than 64k of threads). The tree in the array slot referenced by that word could be pruned, and traversal would be easy. A tree is more efficient, because you can easily group simmilar messages. This means if a thread is checking all collision events that occured with it, then it would traverse to the first collision event in the stack, and then branch off to all the other collision events. This is much faster than popping through the whole stack.

Moving on from that, I also have done some research, and I think I have developed a fast way to do soft shadows and area lights, mainly in realtime (some static pre-calculated). This would mean high image quality. I'm not going to detail the method here, until I've played around a bit. But it involves a c-buffer.

Code wise, I've just done the mini-BSP traversal code. Which was rather simple. Just a few lines of re-cursive code. I also got the 3d and 2d drivers to connect to an executable, and the 2d driver now works perfectly. The 3d driver works well, and initialises what will be the renderer, and just for test sake clears the screen to a nice blue (ogl call). All I can say is, thank god 3dfx updated their Voodoo 3 ICD, and made it work good and proper. Before it didn't even pick up the driver in windowed modes, and in full screen something went wrong with the PFD. Now it works smoothly. Believe me, it was a bother that it worked on every other card except the one in my development machine.

Now, going back yet again to "Pre-Computable Nice Visibility Sets" and the CSS which is an improvement on that, I've been thinking of ways to trim the set further. One idea is introducing the idea of conditional node visibility. Being that the 2d bsp can cover 90% of the node, and still not say "invisible". This is good, and I would worry if it marked visible. But, it is innefficient. Now that whole node would go to the next culler. More efficient is to instead work out the holes in the 2d BSP, connect up corresponding planes, and give conditional visibility. If the camera is in the volume between the connected holes, then the node is visible, if it isn't, invisible.

I also thought about the problem of solving inner node visibility, eg inside the mini-bsp. The obvious answer would be either a mini-pvs, or portals, both of which aren't the best. Mini-pvs may work. Something better that came of it though is a way to cull nodes quickly based on the inner mini-bsp.

Thinking of it, we could use portals in a non-complex way. That is, get the portals from the mini-bsp inside a octree leaf node, and get the portals leading from that node. Obviously inner node visibility, as mentioned before could be done this way (if you only clip portals to portals, rather efficiently). But, another idea is to get the portals which are leaving the node. So, you clip down your portals that are leaving the octree node you are in (in the meantime, getting visibility for your camera node) and then work out which of the potentially visible nodes are in those portals. This system is rather efficient, and would provide a good optimised set for your more dynamic secondary culler.

Food For thought.

Also, I think I may do a fully fledged, actually understandable (instead of techfile rambling) document on various visibility schemes, some developed by me, some others, that aren't known by the majority. This will not include the visibility skeleton.

Conor Stokes

"Seeing Sunday Morning through Bloody Eyes, I feel so dead, yet I'm so alive" - Mr Chi Pig.

  • 12/29/2000 - Techfile From Somewhere Different
  • 10/10/2000 - Some Fun, And A Cameo Appearance
  • 08/10/2000 - Déjà vu - And I've Done It Before
  • 07/08/2000 - Various Loose Ends To Hang
  • 05/15/2000 - The Way To Hit A Ball With A Bat. Or Not
  • 03/28/2000 - The Fine Art Of
  • 02/13/2000 - A Life Time of Learning, Teaching and Eating M&Ms
  • 12/09/1999 - Strangeness And Wondering If You Are Taking Innovation A Tad Too Far
  • 11/12/1999 - How to Break Exam Tension? Update Your Techfile
  • 09/14/1999 - Lots of Ramblings, personal things and comments on why SNFU
  • 08/23/1999 - Trials and Tribulations of Being Cerebrally Defunct
  • 07/29/1999 - Quick Update about Stuff and Things
  • 07/25/1999 - I'm Back Baby
  • 07/01/1999 - Is it so? Or am I just a Psycho Babbling Mental Hobo, who's Brain has No Home?
  • 06/25/1999 - Another Couple of Things
  • 06/17/1999 - I Am A Naughty Little Boy ;( But I Have A Way To Make Up
  • 06/16/1999 - What the hell? A new data structure for visibility? I don't know, I haven't heard of it.
  • 06/05/1999 - A Little Right Brained
  • 05/12/1999 - A Couple O Things
  • 05/08/1999 - Pre Computable Nice Visibility Sets
  • 05/04/1999 - More on Volumetrics
  • 04/30/1999 - Generic Update
  • 04/27/1999 - Spherical Volumetric Rendering (Mapping)
  • 04/25/1999 - Fractal Curves, Emulation Of Nature
  • 04/25/1999 - Claustrophobic Irony Level Loading and Manufacture
  • 04/24/1999 - Visibility Ramblings
  • 04/21/1999 - Why Software Rendering Is Not Dead
  • 04/17/1999 - Optimizing For Specific 3D Hardware

  • This document may not be reproduced in any way without explicit permission from the author and flipCode. All Rights Reserved. Best viewed at a high resolution. The views expressed in this document are the views of the author and NOT neccesarily of anyone else associated with flipCode.

    [an error occurred while processing this directive]