🚀 go-pugleaf

On May 27, 8:41 am, bob&carole <bobandcarole1...@hotmail.com> wrote:


<a whole bunch of shit>

 Scince this topic sucks, and the hate mongers suck even more, I think
we'll talk about 3d engines....

The Doom engine is the game engine that powers the id Software games
Doom and Doom II. It is also used by HeXen, Heretic, Strife and HacX,
and other games produced by licensees. It was created by John Carmack,
with auxiliary functions written by Mike Abrash, John Romero, Dave
Taylor and Paul Radek. Originally developed on NeXT computers, it was
ported to DOS for Doom's initial release and was later ported to
several game consoles and operating systems.

The source code for the Linux version of Doom was released to the
public in 1997 under a license that granted rights to non-commercial
use, and was re-released under the GNU General Public License in 1999.
The dozens of unofficial Doom source ports that have been created
since then allow Doom to run on previously unsupported operating
systems and sometimes radically expand the engine's functionality with
new features.

It is not a true "3D" engine, as it is not possible to look up and
down properly, and two sectors cannot be placed above and under each
other, but it is a fairly elegant system that allows pseudo-3D
rendering. In its time, Doom was revolutionary in its ability to
provide a fast texture-mapped 3D environment.
Contents
[hide]

    * 1 Doom level structure
          o 1.1 Basic objects
          o 1.2 Sectors
          o 1.3 Sidedefs
          o 1.4 Things
    * 2 Binary space partitioning
    * 3 Rendering
          o 3.1 Drawing the walls
          o 3.2 Floor and ceiling
          o 3.3 Things (sprites)
    * 4 See also
    * 5 References

[edit] Doom level structure

A simple setup demonstrating how Doom represents levels internally
Map view in editor
Map view in editor
In-game view
In-game view

Viewed from the top down, all Doom levels are actually two-
dimensional, demonstrating one of the key limitations of the Doom
engine: it is not possible to have "rooms above rooms". This
limitation, however, has a silver lining: a "map mode" can be easily
displayed, which represents the walls and the player's position, much
like the first image to the right.

[edit] Basic objects

The base unit is the vertex, which represents a single 2D point.
Vertices (or "vertexes" as they are referred to internally) are then
joined to form lines, known as "linedefs". Each linedef can have
either one or two sides, these are known as "sidedefs". Sidedefs are
then grouped together to form polygons; these are called "sectors".
Sectors represent particular areas of the level.

[edit] Sectors

Each sector contains a number of properties: a floor height, ceiling
height, light level, a floor texture and a ceiling texture. To have a
different light level in a particular area, for example, a new sector
must be created for that area with a different light level. One-sided
linedefs therefore represent solid "walls", while two-sided linedefs
represent "bridge" lines between sectors.

[edit] Sidedefs

Sidedefs are used to store wall textures; these are totally separate
from the floor and ceiling textures. Each sidedef can have three
textures; these are called the middle, upper and lower textures. In
one-sided linedefs, only the "middle" texture is used for the texture
on the wall. In two-sided linedefs, the situation is more complex. The
lower and upper textures are used to fill the gaps where adjacent
sectors have different floor and ceiling heights: lower textures are
used for steps, for example. The sidedefs can have a middle texture as
well, although most do not; this is used to make textures "hang" in
mid air. For example, when a transparent bar texture is seen forming a
cage, this is an example of a middle texture on a two-sided linedef.

[edit] Things

Finally, there is a list of objects in the level; objects are known as
"things" in Doom. These are used to place players, monsters, powerups,
etc. Each thing is given a 2D coordinate, as with the vertices. Things
are then automatically placed on the floor or the ceiling depending on
their type.

This is only an overview of the basic structure of Doom levels; most
of the data structures here carry extra properties, for example,
texture offsets, and special properties for gameplay.

[edit] Binary space partitioning

Doom makes use of a system known as binary space partitioning (BSP). A
tool is used to generate the BSP data for a level beforehand.
Depending on the size of the level, this process can take quite some
time. It is because of this that it is not possible to move the walls
in Doom; while doors and lifts move up and down, none of them ever
move sideways.

The level is divided up into a binary tree: each location in the tree
is a "node" which represents a particular area of the level (with the
root node representing the entire level). At each branch of the tree
there is a dividing line which divides the area of the node into two
subnodes. At the same time, the dividing line divides linedefs into
line segments called "segs".

At the leaves of the tree are convex polygons, where it is not useful
to divide the level up any further. These convex polygons are referred
to as subsectors (or "SSECTORS"), and are bound to a particular
sector. Each subsector has a list of segs associated with it.

The BSP system is really a very clever way of sorting the subsectors
into the right order for rendering. The algorithm is fairly simple:

   1. Start at the root node.
   2. Draw the child nodes of this node recursively. The child node
closest to the camera is drawn first. This can be found from looking
at which side of the node's dividing line the camera is on.
   3. When a subsector is reached, draw it.

The process is done when the whole column of pixels is filled (i.e.,
there are no more gaps left). This ordering ensures that no time is
wasted drawing objects that are not visible and as a result maps can
become very large without any speed penalty.

[edit] Rendering

[edit] Drawing the walls

All walls in Doom are drawn vertically; it is because of this that it
is not possible to properly look up and down. It is possible to
perform a form of look up/down via "y-shearing", and many modern Doom
source ports do this. Essentially this works by increasing the
vertical resolution, and then providing a "window" on that space. By
moving the window up and down, it is possible to give the illusion of
looking up and down. However, this will distort the view the further
up and down the player looks.

The Doom engine renders the walls as it traverses the BSP tree,
drawing subsectors by order of distance from the camera so that the
closest segs are drawn first. As the segs are drawn, they are stored
in a linked list. This is used to clip other segs rendered later on,
reducing overdraw. This is also used later to clip the edges of
sprites.

Once the engine reaches a solid (1-sided) wall at a particular x
ordinate, no more lines need to be drawn at that area. For clipping
the engine stores a "map" of areas of the screen where solid walls
have been reached. This allows far away parts of the level which are
invisible to the player to be clipped completely.

The Doom graphic format stores the wall textures as sets of vertical
columns; this is useful to the renderer, which essentially renders the
walls by drawing lots of vertical columns of texture.

[edit] Floor and ceiling

The system for drawing floors and ceilings ("flats") is less elegant
than that used for the walls. Flats are drawn with a flood fill-like
algorithm. Because of this, it is sometimes possible if a bad BSP
builder is used to get "holes" where the floor or ceiling bleeds down
to the edges of the screen. This is also the reason that if the player
travels outside of the level using the noclip cheat the floors and
ceilings will appear to stretch out from the level over the empty
space.

The floor and ceiling are drawn as "visplanes". These represent
horizontal runs of texture, from a floor or ceiling at a particular
height, light level and texture (if two adjacent sectors have the
exact same floor, these can get merged into one visplane). Each x
position in the visplane has a particular vertical line of texture
which is to be drawn.

Because of this limit of drawing one vertical line at each x position,
it is sometimes necessary to split visplanes into multiple visplanes.
For example, consider viewing a floor with two concentric squares. The
inner square will vertically divide the surrounding floor. In that
horizontal range where the inner square is drawn, two visplanes are
needed for the surrounding floor.

This leads to one of Doom's classic limitations which frustrated many
mappers for a long time. DOOM contained a static limit on the number
of visplanes; if exceeded, it would crash back to DOS with the
message, "No more visplanes!". The easiest way to invoke the visplane
limit is a large checkerboard floor pattern; this creates a large
number of visplanes.

As the segs are rendered, visplanes are also added, extending from the
edges of the segs towards the vertical edges of the screen. These
extend until they reach existing visplanes. Because of the way this
works, the system is dependent on the fact that segs are rendered in
order by the overall engine; it is necessary to draw close up
visplanes first, so that they can "cut off" by the further away ones.
If unstopped, the floor or ceiling will "bleed out" to the edges of
the screen, as previously described. Eventually, the visplanes form a
"map" of particular areas of the screen in which to draw particular
textures.

While visplanes are constructed essentially from vertical "strips",
the actual low level rendering is performed in the form of horizontal
"spans" of texture. After all the visplanes have been constructed,
they are converted into spans which are then rendered to the screen.
This appears to be a tradeoff: it is easier to construct visplanes as
vertical strips, but because of the nature of how the floor and
ceiling textures appear it is easier to draw them as horizontal
strips. Because of the nature of visplanes, the conversion is fairly
trivial, however.

[edit] Things (sprites)

Each sector within the level has a linked list of things stored in
that sector. As each sector is drawn the sprites are placed into a
list of sprites to be drawn. If not within the field of view these are
ignored.

The edges of sprites are clipped by checking the list of segs
previously drawn. Sprites in Doom are stored in the same column based
format as the walls are, which again is useful for the renderer. The
same functions which are used to draw walls are used to draw sprites
as well.

While subsectors are guaranteed to be in order, the sprites within
them are not. Doom stores a list of sprites to be drawn ("vissprites")
and sorts the list before rendering. Far away sprites are drawn before
close ones. This causes some overdraw but usually this is negligible.

There is a final issue of middle textures on 2-sided lines, used in
transparent bars for example. These are mixed in and drawn with the
sprites at the end of the rendering process, rather than with the
other walls.