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/16/1999, What the hell? A new data structure for visibility? I don't know, I haven't heard of it.

Well, what can I say, the title says it all. HTPS is the name of this wierd structure. HTPS stands for Hierachal Tangent Plane Scans (Note, this is only theory at the moment). What does it mean?

Following the post on "Pre-Computable Nice Visibility Sets" I was aware of something in the system that really made it less effective. This little ineffectiveness comes from the fact that it is possible for two non adjacent occluders to partially occlude a node partially to the perspective of another, but together they always occlude the object.

Forutnately, this is little problem can be solved by another system I thought about, HTPS. HTPS actually works on axis aligned lines. A beam from a convex outline, such as that from a polygon or node, can either split this into 2 or 3 line segments. With a tangent beam, after the segment splitting, the line segment that lies within the beam is the important bit. Actually, the two points where the beam cut the line is important.

This little segment is great. If you slide your camera along our line, as soon as it moved on to the segment between these two points, then the object which the tangent beam was testing for occlusion is not visible. Odd that.

Now, imagine a c-buffer. If you have two different filled areas, and they overlap, you join the spans together. Well, the HTPS is a little different. We maintain each line in the HTPS as a 1D binary linked list like a c-buffer. But, we don't use scans. We use axis aligned lines. These could either run left->right, top->bottom, or front->back.

This is the class I would use, represented in C++ pseudo code.

 class HTPSNode
 //Some stuff


 //The next node in the list
 HTPSNode* m_next;

 //Starting Position
 float m_startpos

 //The length of this span
 float m_spanlength;

 //Object that became occluded since last span
 object3d* m_occluded;


Now, simply you can see may see the use of these variables. The first variable is the next node in the list. The next one is the starting position along the line. The third is the length of the span, or the space along the line in which the object is occluded. Now, these spans can overlap. But, in a simmilar circumstance to the c-buffer, if two spans that contain the same occluded object overlap, they can be linked together. Bingo, here is the important property of the tree.

Luckily, this can all be precalculated. But, how can these lines be relevant to a real system? Well, I like the octree data structure, in which many nodes share axis aligned edges. There is also the chance that some nodes may share lines, but to save on the possibly large data set built up, we make sure that the HTPS only operates on parts of the line that are an edge.

Well, luckily, if each edge in the octree node just happens to have a span that covers the edge eg

 ||=Beginning and end of span. +=Beginning and end of node edge. 

Then we can say that the camera would always be invisible to that line. Now, if this occurs for all edges, then the object is occluded. This is good, because the set doesn't have to rely on large occluders to get rid of objects. It is very efficient at removing occluded objects. It is reasonably quick. It is precalculatable. It could be large, if complex set was involved, but fortunately, it is precalculated.

Actually, perfect visibility to all the polygons outside the node could be calculated with some thought. A volume can be created using the end points of the spans to recreate a larger tangent beam.

I am considering this system, but I am not sure it is un-flawed. I can not personally spot an error, but If you do please reply.

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