To: edkiser AT jaxnet DOT com
Cc: djgpp AT delorie DOT com
Subject: Re: Question about Doom.
Message-ID: <19970325.162400.6823.0.fwec@juno.com>
References: <199703211735 DOT JAA29516 AT netcom9 DOT netcom DOT com> 
From: fwec AT juno DOT com (Mark T Logan)
Date: Tue, 25 Mar 1997 16:25:51 EST

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.  I think you are pretty close
here.
Seems to me that doom goes through the bsp, and when it gets to a
polygon that needs to be drawn, it sort of raycasts that polygon by
itself.
That means that starting at the left edge, it sends out a ray, and finds
the
intersection point of the ray and the polygon.  Then, using the distance
to
that point, it can draw a single vertical line for that part of the wall.
 This continues
to the end of the polygon.  I don't know if this is faster than normal
polygon drawing
code, but it has the advantage a producing perspective correct texture
mapping.  I 
think.

>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.

>My guess on sector flowing is harder to explain. The method I was
>thinking of is this: divide space into convex regions. Each region has
>faces with normals pointing IN. You can draw the inside of any region
>by drawing any face whose normal points toward you (not away.) But
>that's the solid faces. The transparent ones have regions on the other
>side, connected sort of like a linked list. So you recurse: draw the
>region you're in, then if there's any part of the screen that was
>transparent and still hasn't been drawn, draw the region on the other
>side of it, as seen from the same point. No BSP needed, but every
>region has to be convex, or split into convex pieces.

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.  I think we all owe John
Carmack
one for _not_ explaining sector flowing.  Otherwise you would never have
come up with this wonderful algorythm.

>Oh, and PVS stands for _Potentially_ Visible Set, not Partial.

Right on.  Did you read "Zen of Graphics Programming"?

>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.


||                Fwec AT juno DOT com
||  "If ya don take your meat, ya can't have any pudding!!!!
||    How can ya have any pudding if ya don take your meat?"
||   -Pink Floyd
||