WAD to MAP Conversion

Introduction

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:

Proposal by John Carmack

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

Texture Alignment conversion

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.

Color Palette conversion

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.

Level Geometry conversion

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

We will look at each processing step separately.

Determine Loops

 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.

Handle the Borders

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.

Handling the Insides

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.

Handle the Sectors

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.

Summary

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 qdev qdev dread rsc qdev doom license web
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 $