Not logged in, Join Here! or Log In Below:  
 
News Articles Search    
 

 Home / 3D Theory & Graphics / Your opinions on an algorithm Account Manager
 
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
 
Russell Klenk

March 25, 1999, 12:52 AM

Even though I'm sure someone else has thought of this first, I was thinking:

1. If the world is divided up into "rooms" (a room is a special bounding sector and can contain detail sectors) then generate a BSP tree for each room as a preprocessing step.

2. Beginning with the room that the camera is in, push that room onto a stack.

3. Check to see if there are any visible portals (doors that are actually open, etc.) and if so recurse into those rooms, pushing them onto the stack as well. Repeat until all rooms visible from the current viewpoint have been pushed onto the stack.

4. Render the rooms as they are popped off the stack. This means that the nearer rooms will occlude the farther ones. Repeat until the stack is empty.

Does this sound reasonable?

 
Jaap Suter@student.utwente.nl

March 25, 1999, 04:57 AM

Sure this sounds reasonable.

As a matter of fact. If the room is cube shaped you are talking about
a sort of Octree algo. And if the rooms you talk about are arbitrary shaped then you talk
about a portal algo. (I believe i'm right, but am not sure.)

Jaap Suter

 
Timo

March 25, 1999, 09:52 AM

And if the geometry is statical, you can preprocess some visibility information
(which rooms can be seen from a given room) .. this is the VIS step in the level building step
of the Quake engines.

Tim

Jaap Suter@student.utwente.nl wrote:
>>Sure this sounds reasonable.
>>
>>As a matter of fact. If the room is cube shaped you are talking about
>>a sort of Octree algo. And if the rooms you talk about are arbitrary shaped then you talk
>>about a portal algo. (I believe i'm right, but am not sure.)
>>
>>Jaap Suter

 
Harmless

April 07, 1999, 09:05 PM

Russell Klenk wrote:
>>Even though I'm sure someone else has thought of this first, I was thinking:
>>
>>1. If the world is divided up into "rooms" (a room is a special bounding sector and can contain detail sectors) then generate a BSP tree for each room as a preprocessing step.
>>
>>2. Beginning with the room that the camera is in, push that room onto a stack.
>>
>>3. Check to see if there are any visible portals (doors that are actually open, etc.) and if so recurse into those rooms, pushing them onto the stack as well. Repeat until all rooms visible from the current viewpoint have been pushed onto the stack.
>>
>>4. Render the rooms as they are popped off the stack. This means that the nearer rooms will occlude the farther ones. Repeat until the stack is empty.

>>Does this sound reasonable?

This is a recursive portal engine. There are some problems with this design. It works, but it needs a couple of modifications in one direction or another.

Given the following cel arrangement, where A can see both B and C and can see D through both B and C you have a problem when the eye is in A.

If you modify your stated algorithm to continually clip what is rendered to the portals between each cel as you walk outward you will visit: A,B,D then A,C,D which means D will get visited twice. In practice this will start to happen in any room with more than bare bones geometry in it, ledges will cause this, multiple doors will cause this, etc. It gets worse when you consider the rooms beyond D that get recursed into multiple times. It works, but you will visit the same nodes multiple times.

A
/
B C
/
D
/
E F

Alternatives are to render the entire node when you visit it the first time and to never recurse into the same node twice, the problem is now you have to rely on some means of sorting the nodes, like having the nodes be generated by a BSP tree and let hardware handle the overdraw or use a second stage sorting algorithm like an active edge table

 
This thread contains 4 messages.
 
 
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.