delorie.com/archives/browse.cgi   search  
Mail Archives: djgpp/1997/03/20/17:17:51

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: <Pine DOT GSO DOT 3 DOT 95 DOT 970319211330 DOT 23060C-100000 AT explorer2 DOT clark DOT net>
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 <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 -


  webmaster     delorie software   privacy  
  Copyright © 2019   by DJ Delorie     Updated Jul 2019