Mail Archives: djgpp/1997/03/25/20:20:56
What you describe is in fact raycasting (see P.S. about previous post on
ray-casting VS ray tracing). You might call it "sector flowing", but all
you're really doing is calling a rose by any other name. The fact that the
vertical portion of the cast is optimized to use the horizontal distance
(all sectors in doom are perpendicular to the "floor") rather than cast a
new ray for each pixel is irrelevant. The code is basically saying " hey,
if you can see part of that vertical line, I'll just draw the whole damned
thing to save time".
P.S. In a previous message, I stated that ray tracing and ray casting are
the same thing. This is not entirely true. Ray casting is a sub-set of
ray tracing. Ray tracing uses a complete 3-D model and plots trillions of
vectors to produce a photo-realistic image. This is not possible to do in
real-time even on a Cray-2. Ray casting is an optimized form of ray
tracing that only does what is needed to produce an acceptable view. It
also goes about doing it backwards. As an example, if DOOM used ray
tracing, you could see yourself in the glare of a monsters eye, and see the
shadows produced by a monster around the corner.
::-)
----------------------------------------------------------------------------
---
C code is like assholes, everyone's stinks but your own.
Looking at C code is like looking at your bedroom, a
complete mess to everone else, but you can tell them
where every little thing is.
C code is like Ex-Lax, great when it works but a pain
in the ass when it doesn't.
Explaining why C is better than Pascal is like explaining
why peanut butter is better than toe jam.
Explaining why Assembler is better than anything is like
explaining why being deaf is better than listening to
'The artist formerly known as Prince'.
----------
> From: Mark T Logan <fwec AT juno DOT com>
> To: edkiser AT jaxnet DOT com
> Cc: djgpp AT delorie DOT com
> Subject: Re: Question about Doom.
> Date: Tuesday, March 25, 1997 15:25
>
> 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
> ||
- Raw text -