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 http://www.claustrophobe.8m.com

 05/08/1999, Pre Computable Nice Visibility Sets

It has been rather cold today, so, I have been inside most of the time. I was planning to do some stuff around the house, and I did. One of the things I set about doing was organising the white papers I had been downloading, and putting them into a nice little directories.

Some of them, I started to read. One such one of these was one of Teller's on large occluders. One thing that struck me, that should have made a dent before was the idea of using tangent planes to decide on the visibility of objects. Basically a tangent plane, is a plane between a possibly occluded point an an edge on a polygon. Now, if you know your 3d maths, you may see what I have been blind to, in my researching. Which is, that by making beams out of these planes and deciding if the camera is within these planes, you can cull the invisibilities. The beams I means (pun) are the ones of all the points behind the polygon being tested.

Really if you wanted to, you could indeed pre-compute the set of all these planes, for all possibly occluded points, and then make a sort of "BSP", which you can quickly traverse to find out which node the camera is in, which would give you a list of all the polygons that where visible, if the camera had 360 degree vision. Of course, you can just frustum clip this, and walla, quick perfect set.

But really, the computation would be rather large to store, considering a plane is created for every point behind a polygon, for every edge in the polygon. So reallistically, you would have to say, if all the polygons were triangles, that the number of planes created would be, 3/2n^2 planes, where n was the number of points. This would make a lot end nodes in your virtual "BSP". If these triangles had winged information, this number could easily drop by a large percentage. When I say alot 5000 points would need 37(*4 floats worth) megs worth of planes. Of course, if you consider having a preset far plane, this number can be reduced to more manageable sizes, but still large.

Now, this may seem ridiculous to even mention, just because of its size. But, there is validity to this information, to probably most programs out there. It is good for many reasons.

Before Phantom and I began work on our vis system, he was planning to use a PVS for his OCTREE. Basically it involved precomputing possible visibility for an octree end node, by rendering a polygon buffer for EVERY single possible point in the node, and then saving any polygon mentioned in the set. How ever. Imagine using this set instead. You simply gather all the points/polygons in the sphere (with of the radius of the far clipping plane + the distance from the centre of the node to the corner) and then, one by one generate your tangent planes beams, and if the node you are working on is entirely inside the beam, that polygon is never visible from that node. Extending this theory, we can add a flag to the PVS array for that node. This flag is set if the beam partially cuts the node. If the node is never cut by any beam from the possibly occluded polygon it is simply always visible.

Also remember, you can test OCTREE nodes aswell, to speed up quick culling.

This method should work alot quicker for a PVS pre-process than the one Phantom proposed. Interesting, it can be combined with the beam-tree+OCTREE, to make quick work of your visibility.

So, if your world contains static points, you can apply this PVS to them, and then chop out the dead wood using the OCTREE + BEAMTREE, which will gain the perfect set + allow for dynamic polygons, which move or are suddenly created to be catered for. I cannot see any reason for such a vis set to be discounted as possibly one of the fastest available.

One more point, which is relavant to Seth Tellers original doc, is that you may wish to keep some beams which are from "large" occluders, and optimise to get rid of redundant overlaps, if your world is rather dynamic, but has some static elements, which a PVS wouldn't be useful for.

DirtyPunk

PS Visit my page, I update reasonably often. Write to me, tell me what you think about the contents of the Techfiles (cstokes@tpgi.com.au).

• 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