To: times9 AT clark DOT net Cc: djgpp AT delorie DOT com Subject: Re: Question about Doom. Message-ID: <19970320.170313.6775.2.fwec@juno.com> References: From: fwec AT juno DOT com (Mark T Logan) Date: Thu, 20 Mar 1997 17:05:08 EST On Wed, 19 Mar 1997 21:14:15 -0500 (EST) Guess 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 ||