From: edkiser AT jaxnet DOT com (M. Edward Kiser)
Newsgroups: comp.os.msdos.djgpp
Subject: Re: Question about Doom.
Date: Wed, 26 Mar 1997 06:14:16 GMT
Organization: Southeast Network Services, Inc.
Lines: 119
Message-ID: <5haeu4$206@news.southeast.net>
References: <199703211735 DOT JAA29516 AT netcom9 DOT netcom DOT com>  <19970325 DOT 162400 DOT 6823 DOT 0 DOT fwec AT juno DOT com>
Reply-To: edkiser AT jaxnet DOT com
NNTP-Posting-Host: ts10-010.southeast.net
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp

fwec AT juno DOT com (Mark T Logan) wrote:

>On Mon, 24 Mar 1997 20:36:19 GMT edkiser AT jaxnet DOT com (M. Edward Kiser)
>writes:
>>It has been asked: what is sector flowing? What is a one-dimensional
>>completion mask? I think I can make guesses. Maybe they're wrong, but
>>I'll make them anyway.
>>
>>I think Doom drew one vertical line at a time, sweeping left to right
>>to create a frame. My evidence is the "reduce detail" option that
>>halved the horizontal resolution but not the vertical. It just
>>repeated each line twice instead of drawing new ones. The
>>one-dimensional completion mask would probably be an array of booleans
>>that indicates whether each pixel in the current vertical line is
>>complete. For each scan line, Doom would draw front-to-back, walking
>>the BSP tree, visiting entities in each node, then walls and floors.
>>When the whole array is "true," the line is done.
>
>Doom doesn't sweep left to right for each frame.  That would be
>raycasting,
>and could not really use a bsp tree AFAIK.

Let me put it this way. Any graphics engine must have at least three
nested loops:

for each object (polygon, sprite, whatever)
{ for each X coordinate
  { for each Y coordinate
    { ...
    }
  }
}

The nesting order of the loops can be interchanged without affecting
what algorithm is used for depth-sorting (BSP, sector-flowing,
blockmap, Z-buffer, whatever.) However, the order can have a BIG
effect on what optimizations are possible. For speed, the idea is to
use every opportunity to end the inner loops prematurely, or shorten
them, or never begin them. I think Doom does it like this:

for each X coordinate
{ for each subsector, walking AWAY from the viewpoint on the BSP, and
  while the line is not full
  { for each sprite in the subsector, then each wall, then floor and 
    ceiling
    { for each Y coordinate spanned by the object
      { if that y coordinate is not already drawn and is not
        explicitly transparent
        { draw the pixel, and mark it drawn
} } } } }

I have omitted calculations that would precede each "for" and all the
early-outs, but I think this is basically it.

>
>>If my guess about vertical lines is correct, Doom would work well in
>>Mode-X.
>
>Doom does use mode-X.  Can't prove it, but feel free to count pixels.

No need to count pixels; check the specs. (Matt Fell's Unofficial Doom
Specs.)

I think it uses 320x200, VGA mode 19 (0x13 hex). I don't think it uses
Mode-X because I don't think Mode-X was well-known at the time the
first Doom was written. It could use 320x200 Mode-X, but I'm not sure
there would be any advantage for Doom to do so.

>>My guess on sector flowing is... [snip]
>
>Thank you, thank you, thank you.  Even if this is not how Sector flowing
>works, it is a damn good drawing algorythm.  Only draw back is that
>you have to keep track of which portions of the screen have been drawn
>yet, since you are drawing front to back.

So iterate by scan lines and use a one-dimensional completion mask.
;-)

>I think we all owe John Carmack
>one for _not_ explaining sector flowing.  Otherwise you would never have
>come up with this wonderful algorythm.

No, I came up with it months ago. This was a great opportunity to
publish it. But it's probably been done before, or at least thought of
before.

I can't imagine what "sector flowing" is, if it isn't this.

>>Oh, and PVS stands for _Potentially_ Visible Set, not Partial.
>
>Right on.  Did you read "Zen of Graphics Programming"?

I only skimmed the last few chapters. Most of my knowledge has come
from reading the Doom and Quake specs and playing the games on slow
computers where you can see them working. :-)

3D engines don't draw circles and all those other primitives, except
maybe in the automap. Also, I don't know any of the "prerequisites"
for the first chapters, the VGA stuff. I couldn't find any other books
in the bookstore about VGA. So, since I didn't like paying $50 for a
few short chapters, I returned Abrash's book.

>>Those are my guesses. Now the dumb question. What is ray casting? Is
>>it a form of ray tracing?
>
>Hope I explained that enough up there.  Ray casting is like ray tracing,
>but
>you cast one ray per column of pixels, intstead of one ray per pixel. 
>Faster,
>less accurate.

Got it. Thanks. No need for anyone else to answer the question now.
:-)

--------
Ed Kiser (edkiser AT southeast DOT net)
"The man who does not read good books has no advantage over
the man who can't read them." -- Mark Twain