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.
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
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.
|