I took the time to think a bit about a `wad2map`

tool, converting DOOM level descriptions to Brush based MAP
files. This is a more or less good idea because:

- one learns a lot about polygon-based representations vs. brush based representations
- DOOM editors might be used with wad2map and qbsp, as long as no decent Quake Editor is available with some OS
- as with QuakeEd, editing in an XYView is actually a bit like editing for DOOM : select a minZ, maxZ, and edit some 2D polygons
- semi-auto conversion of high quality DOOM levels would be eased
- there will be no need to write down a
`wad2bsp`

utility I considered, assuming that the processig suite John Carmack wrote will be available

Quoting John Carmack as of April 6th, 1996:
*"The proper way to do it to bring up a new editor that is going to
follow our conventions is to create two solid polyhedron brushes
for each leaf node, one that goes from the ceiling up to the highest
point of the level, and one that goes from the floor to the lowest
point. After running through the processing suite, it should be
comparable to converting the .wad directly to a .bsp."*

First something I did not think much about: texture alignment. This will only be possible if the s_scale/t_scale are actually used by Quake now, and not only dummies. It needs to take into account pegging/unpegging, offsets, and the 2D orientation of the LineDefs to use s_scale for correction of NAT-related distortion.

- The NAT coordinates of the vertices determine s,t offsets.
- Pegging affects t offsets.
- X_offset/Y_offset affect s,t offsets.
- The s_scale depends on the angle in XY.
- No rotation. No t_scale.

Then there is the issue of Palette conversion. It might be possible to use the DOOM palette with Quake, but status bar graphics, billboards and monster skins will have to be replaced - a Total Conversion. The two palettes match poorly, and we will not know whether there is an acceptable way to merge both until the final version is released.

Here's a a sketch of an algorithm. It has one intial step, and three main parts:

- Determining Loops
- Handle the Border
- Handle the Insides
- Handle the Sectors

I1) from LINEDEFS, extract all single-sided LineDefs only. I2) Now pick a LineDef, search for those sharing the vertices, and continue to create lists of single-sided LineDefs that represent a closed loop, a polygon. All LineDefs will be part of such loops. I3) From SECTORS, determine maxZ, minZ for whole level. I4) Find all loops that are clockwise - these are outside borders of the level (level parts). There is at least one. More are possible, as there are levels with areas connected only by teleport. I5) The remaining loops are counterclockwise - these represent solid interior areas. Now identify which outline those belong to: determine the center of each (does not matter whether convex or concave), and check which center the loop is in (signs of z-component of cross-product with each LineDef).Now we have the WAD level split into separate parts. For convenience, the parts are handeld separately - if there are two separate parts of the level with overlapping extended bounding boxes, you will get into trouble.

We handle one level part each time.

S1) Get the outline loop. S2) Determine extreme vertices vTop, vBottom, vLeft, vRight, i.e. topmost, leftmost etc. vertices. If those are degenerate, store all vertices with maxX, maxY, minX, minY. There are at least 3 extreme vertices. S3) From min/max X/Y now determine a world-aligned bounding box around the level. Extend these bounding box a bit (to make brushes massive), by some 10 percent. S4) This loop, and the four edges of the bounding box are one big polygon with one hole. Now separate the loop: For each extreme vertex, create a vertical (or horizontal) edge to the bounding box. This way, the extreme vertices split the polygon with a hole into at least three polygons w/o hole. For each of these, check whether convex (e.g. signed area, or sum of angles). If not, a polygon partition is in order. S5) For each partition (now a convex 2D polygon), create a Brush: one plane for each LineDef, one in XY at minZ, one in XY at maxZ.There might be algorithms to partition a polygon with one or more holes, but splitting the border polygon into several parts will be helpful, as a partition algorithm might run in O(n^3) for all I know.

We now have handled the border of the level. We now have to handle the inside loops.

S1) Get an inside loop. S2) Determine whether convex. If convex, create a Brush: one plane for each LineDef, one in XY at maxZ, one in XY at minZ. If concave, a polygon partition is in order. Next, create Brushes from all convex partitions of the polygon.

We now have the outside and the inside borders done. This is some kind of Wolfenstein level now, as we do not have the varying floor and ceiling heights, and we do not have uppers/lowers done. For this, we have to get convex polygons from the sectors. Those are already done - in the BSP. Thus we will use the BSP this time.

S1) For each leaf in the BSP, traverse the BSP from the root. Collect all LineSegs referenced by partition planes on the way, and all LineSegs in the leaf. S2) Now create two brushes for each leaf: The floor brush has one plane in XY at minZ, and one in XY at floor_height. Each LineSeg spawns one brush plane, ranging from floor_height down to minZ. The ceiling brush has one plane in XY at ceiling_height, and one in XY at maxZ. Again, each LineSeg spawns a vertical brush plane.Only uppers and lowers will create brush planes. We ignore the middle textures on two-sided LineDefs, as they cannot be represented by brushes if partly transparent. One could use billboard objects (sprites with fixed orientation), but this will look pretty ugly, because John Carmack decided not to support mipmapping for sprites (no RGBA blending, thus mipmapping would not be perfect, but, IMO would still be an improvement).

Now we are done. We have a wall composed of brushes that encloses the level in XY, and two sets of brushes that are the floor and the ceiling of the level. Even doors will be brushes now. The shape of the brushes depends on the polygon partition algorithm applied to the non-convex polygons.

Textured two-sided linedefs might be treated differently. Partly transparent textures cannot (yet) be done with Quake in a convincing way, as world-aligned as well as all other billboard entities are not mipmapped. Double-sided linedefs with non-transparent textures might be replaced by rectangular brushes of minimal thickness, though.

I learned that the DOOM editing approach (a 2D look down on the XY-plane, creating polygons) might work for some Quake editing modes as well. I am not sure whether QuakeEd allows for simply creating a polygon in XYView.

home dEr95 r3D dread netrsc quake doom legal web

Author: B., email to bernd@nero.uni-bonn.de, with public PGP key

Copyright (©) 1995, 1996 by author. All rights reserved.

Source: $Id: wad2map.html,v 1.1 1996/06/16 23:56:53 b1 Exp $