WAD to MAP Conversion
WAD to MAP Conversion
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:
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.
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:
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.
