Doomsday converts all maps into it's own internal map format. While loosely comparable to the id Tech 1 map format, various new components are introduced and several key design changes are made to simplify the task of rendering the map with a hardware accelerated graphics library (OpenGL is currently targeted).
The id Tech 1 map format can be thought of as a boundary representation (B-REP), where the boundaries are defined using map lines and subspaces described with "sector" references.
This representation implies that for a subspace to be valid all lines along the boundary should reference the same sector on that side of the boundary (however, map authors realised they could achieve various "special effects" through specifying otherwise invalid references, due to the particular way in which DOOM's software renderer was implemented). This format design decision is solely responsible for the majority of the complication involved in supporting the id Tech 1 map format.
Internal map format
Most of the building blocks of Doomsday's internal map format are direct descendants of their id Tech 1 counterparts.
|DMU_VERTEX||2D map space point on the XY plane used as a geometry vertex|
|DMU_LINE||Line geometry which defines a single map subspace boundary|
|DMU_SIDE||One side of a map line geometry|
|DMU_SECTOR||Describes both physical and visual properties of map subspaces|
|DMU_PLANE||Collated sector properties pertaining to a plane geometry|
|DMU_SURFACE||Describes the visual properties of a surface (plane and line side section)|
Once the core elements of a map are converted/loaded the next job of preparing the map for use is to produce a binary space partition (BSP) from the line geometry and location of the various subspaces which it defines.
The lowest level of map subspace component is the BSP leaf. A BSP leaf describes a simple convex polygon, which, is attributed to a sector of the map. Without at least one BSP leaf a sector is considered to have no world volume.
The next level of map subspace component is the sector cluster. A sector cluster describes a group of one or more BSP leafs which share a common edge and sector attribution. It is important to note that the only time two clusters of the same sector can directly contact one another is when only vertices are shared (it is this trait which makes the clustering pivotal in the support of id Tech 1 map hacks).
The highest level of subspace division is the map sector. A single sector may comprise multiple disjoint clusters.
The boundary representation of the id Tech 1 format means that the map subspaces may not always conform to the somewhat idealistic view depicted in the above diagram). Mismatched subspace references are resolved during the partitioning process to yield a manifold mesh and valid contiguous subspaces.
Note: Presently the same BSP is used for both rendering and collision detection.
Half-edge data structure
It is during this phase of map conversion that mismatched subspace references are resolved.
After the BSP is produced, groups of adjoining leafs sharing a common edge and sector attribution are collected into "clusters".