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

   06/17/1999, I Am A Naughty Little Boy ;( But I Have A Way To Make Up

Well, as I said, it is possible there was a problem with HTPS, and this morning, when I woke up and read the posting of my techfile it came to me. There is a possiblity, although rare that in an arrangement of occluders, we could end up marking a object invisible, that could be visible. This is because if all the edges are covered by the buffer, then it is still possible for "some" of the node to be visible. Curses, so I went back to the drawing board, rather literally in fact. It came to me while I was working in art on the design for my sculpture studio piece. I could use instead a 2d + Quad tree to instead test whole faces in nodes.

Fortunately, it is actually impossible, that I know of, for the occluded object to be visible if the tangent planes cover all the faces. Phew. But, why the hell am I thinking about this?

Well, currently, the potential set I use to ease up the load on the secondary culler works for very generic scenes, whether they be outdoor urban or suburban scenes, or indoor dungeon roaming. Unfortunately however, there is the possibility that the set ( which you can read about in "Precalculated Nice Visibility Sets" ) will not be 100% efficient for the node based potential set it builds. This is because it is possible for two occluders to occlude one node totally from the perspective of another, but they the node is not set as invisible, as each test is done singularily.

Effectively, I could have solved this by simply clipping nodes on each new tangent beam, and only testing one occluded object at a time. I don't like this method though.

So, I thought for a bit, and came up with HTPS. Unfortunately, my hopes for the system turned out to be a premature relief of anguish. So, angst ridden again, I came up with this new system, I dubbed CSS. CSS stands for Confeti Scatz System. A bit of a joke at the fact that I made up an abbreviation for a system that didn't work.

The idea is creating a set of 2d BSPS, with a quadtree which allows us quick reference to the partitioning lines. These partitioning lines occur where the tangent beam planes cut the axis aligned plane. So, effectively, on each pass in our generic potential system, we can build up a set of these axis aligned planar 2d BSPs. The quadtree comes from the fact that each face on each node in the tree must be facing a 2d bsp, so we can cross section the entire tree, and make a quadtree. Even when nodes are split partially by the system. Then, for each possibly occluded object, we insert its corresponding planes into the trees, and create them. When we insert a new beam into the bsp, we then check if any of the faces in the quadtree are now covered. As soon as a face in the quadtree is covered, we can mark it and not worry about it anymore. Once a node has all 6 of its faces marked, then the node or occluded polygon is invisible (I only test nodes). Bonza.

So, for each possibly occluded node, we insert the tangent planes between it and its occluders into the 2d bsps. When we move onto the next possibly occluded node, we can start again. By doing this, in the right order, we can efficiently compute an more efficient potential set.

There is another bonus of this set, that I have not mentioned. If you wish, you can allow the plane of the quadtree to go through a node without being one of its faces. You still get your square in teh quadtree, but it doesn't correspond to a face. In this way, if the visibility changes, we can partition the node into two parts, one where a polygon is visible, and one where it isn't. I think this could be used at lower level nodes to again increase the level of accuracy.

This fairly simple idea allows us fast management of the entire potential set for a node rather well, and although I personally feel the data set would be too large for realtime purposes, it would be useful to generate the potential set I use. It would offer a very generic potential set, capable of handling many areas that are often not handled by a portal based pvs system well.

Another thing, not my own invention, but that of a friend, Martin Hristov, is the idea of using a mini-sbuffer within nodes to gain sorted visibility, then sending it to a global s-buffer. This means you can skip the set of the mini-bsp. How ever, in mentioning this to Phantom, he came up with the idea that you could switch between the mini-bsp and the mini-s-buffer in dealling with dynamically altered nodes. Expanding on this idea, we could allow this, with the case that we still use the pre-generated mini-bsp, but we do this to get our static polygons in s-buffer inserted order first, skipping the sorting step here. Then we can simply determine which static scans the dynamic ones lie between, and then sort only the dynamic scans. So, this way we could quickly sort scans, by using a depth list of the scans, based on the mini bsp. This would avoid the hassles of sorting all the scans.

  • 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]