RE: Map Files

Bernd Kreimeier (Bernd.Kreimeier@NeRo.Uni-Bonn.DE)
Mon, 22 Apr 1996 18:14:25 +0200 (MET DST)

From: Bernd Kreimeier <Bernd.Kreimeier@NeRo.Uni-Bonn.DE>
Date: Mon, 22 Apr 1996 18:14:25 +0200 (MET DST)
Message-Id: <>
Subject: RE: Map Files

>>What I need to know is how would you take a list of planes and turn that
>>into a list of vertices and lines (a convex polyhedron)?

> sounds like the kind of stuff that happens in the simplex's algorithm
> (a classic stuff used in optimisation).

I do not think so, frankly.

> No idea how id does this, but the result isn't perfect (many duplicated
> segment references). I assume most vertex will appear naturally when doing
> the BSP splitting.

Again: beg to differ.

It seems that our current understanding of the MAP format is incomplete.
In my opinion, there are the following processing steps that have to
be done *within QuakeEd*:

define/modify planes of a single brush
calculate a boundary representation of the brush.
based on plane-plane-intersections
add brush to the map as already done

Note that the boundary representation is necesary, as human beings are
not likely to think in infinite planes. We need the building blocks to
be convex polyhedra, solid bricks of material. See QuakeEd screenshots,
the top-down view.

Note that all planes of one brush do intersect, but that planes of
different brushes do not intersect. Brush-brush intersection
is calculated using CSG with the polygons, not the planes.

I refer to the "recommended readings" page, the book by Martti Mantyla
(and his Geometric Workbench source), and the Ian Ashdown code in the
HELIOS radiosity package - both use half-edge representations, IIRC,
that allow for boolean operations with boundary representations: solid
modeling, that is. There is a reprint of the CSG book by Mantyla
scheduled for May, it is currently out of print.

The "qbsp", as much as my two cents are worth, calculates brush-brush
intersection - the QuakeEd screenshot does not demonstrate the 3D camera
view. A z-buffer for slow preview will work nicely with
intersecting polyhedras, so there it might be better to keep that
calculations out of the editor.

To understand the MAP files, we should ask ourselves:

What does a MAP with only one brush looks like,
i.e. one solid that is surrounded by nothing.

What does a MAP look like with only non-intersecting and
non-touching brushes?

What does "sealing the world" mean (mentioned by Abrash and Carmack),
but removal of all outside surfaces that cannot be seen from
the interior?

Will there be anything left in the two MAPs described above,
once "qbsp" is done?

Note that John Carmack mentions "convex polyhedra operations" in both
"qbsp" and QuakeEd. Again, anybody who is working on a MAP editor should
be aware of the processing of planes and brushes necessary for any
previewing during editing. Vertices and edges are only implicit in the
MAP files, but they have to be made explicit to the user.