Mail Archives: djgpp/1997/03/20/17:17:51
On Wed, 19 Mar 1997 21:14:15 -0500 (EST) Guess <times9 AT clark DOT net> writes:
>-> Wolfenstein 3D used ray casting.
>-> Doom used BSP trees and a one dimensional completion mask.
>-> Duke3D used sector flowing.
>-> Quake used BSP trees, a PVS, and an edge list.
>Btw, what is one-d completion mask,sector flowing, pvs and an edge
>list:)?
As I was lying awake in bed last night, it occured to me what a one-d
completion mask is. Doom probably stores the vertical spans of pixels
which have been drawn in each row, so that it doesn't draw over them.
The way doom draws with bsp trees will result in the fact that no more
than one vertical span of pixels will exist per row in the screen buffer.
This way, one span, (y1, y2) is stored for each row of pixels, and is
updated anytime a new wall or floor is drawn on top of that row. Nothing
is ever drawn within that span, so there is zero overdraw during a front
to back traversal of the bsp tree.
A pvs is a potentially visible set. what this means is that id
precalculated
a list of all leaves which were potentially visible from the leaf that
the player
is in. It then draws each leaf back to front, based on the bsp tree.
BTW,
a leaf is just a convex subdivision of the world model.
Also, if you think I hacked the quake source and am now spreading stolen
trade secrets, you are wrong. Quake was discussed at length in Zen of
Graphics Programming by Micheal Abrash.
An edge list is an implementation of 1/z sorted spans that quake uses to
eliminate overdraw. I don't know exactly how they work.
I don't know anything about sector flowing.
|| Fwec AT juno DOT com
|| The secret of life.
|| -42
|| Douglas Adams
||
- Raw text -