User Tools

Site Tools


devel:map_geometry

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision
Previous revision
map_geometry [2013-10-01 05:44] – /* Core elements */ danijmap_geometry [2013-10-01 05:52] (current) – /* Core elements */ danij
Line 1: Line 1:
 +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 ([[open_gl]] is currently targeted).
 +
 +
 +====== Historical context ======
 +
 +
 +The id Tech 1 map format can be thought of as a [[http://en.wikipedia.org/wiki/Boundary_representation|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 ======
 +
 +
 +
 +===== Core elements =====
 +
 +
 +Most of the building blocks of Doomsday's internal map format are direct descendants of their id Tech 1 counterparts.
 +
 +^ [[dmu]] identifier^ Description |
 +| 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 [[http://en.wikipedia.org/wiki/Binary_space_partitioning|binary space partition]] (BSP) from the line geometry and location of the various subspaces which it defines.
 +
 +
 +===== Subspace division =====
 +
 +
 +{{ file:mapsubspacedivision.svg }}
 +
 +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 [[map_geometry#Historical_context|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 [[map_geometry#Subspace_partitioning|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 =====
 +
 +
 +/writeme
 +
 +
 +====== Conversion process ======
 +
 +
 +===== Subspace partitioning =====
 +
 +
 +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".
 +
 +
  
devel/map_geometry.txt · Last modified: 2013-10-01 05:52 by danij