PROC File Format

From The DarkMod Wiki
Revision as of 20:50, 5 May 2022 by Geep (talk | contribs) (create this article)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

Title: PROC File Format

By Geep, 2022. Mostly derived from Danile Gibson’s 2014 article, except for Overview and Shadow Volumes.

Overview

While your MAP file defines the geometry of your FM, there are additional ways of re-structuring that information that greatly accelerates gametime processing. The computation of this re-structuring is done in advance, by "dmap", which saves the results to intermediary files in your "<FM>/maps/" folder. These files are then read into memory during game loading (e.g., "map" invocation). If the calculations were not done in advance, but instead during loading, game startup would be very slow.

One of these intermediary files is the PROC file. The structures in a PROC file help speed up rendering, texture-mapping to triangles, and visibility determinations. It contains the following.

  • For each named entity defined by primitives (i.e., brushes and patches), all its visible triangles, batched up into surfaces sharing a texture.
  • A Binary Space Partitioning (BSP) tree, subdividing the space into convex parts, that are then grouped into "Areas" (i.e., visLeafs).
  • For the content of each such Area, all its visible triangles, batched up into surfaces sharing a texture.
  • A listing of "Inter Area Portals" (i.e., visPortals), indicating visibility between Areas.
  • Shadow Volumes, those that can be precalculated.

Shadow Volumes support stencil shadows. The algorithm for this was made famous by Doom3. At runtime, conceptually, the view the player sees at any moment is rendered in two ways:

  1. lights off (except ambient). Everything is shadowed.
  2. lights on, with light rays passing through objects.

Then (2) is put in front of (1), with "stencil holes" cut through (2) where the shadows are. The shadow volumes are consulted to define the holes. (TDM also offers shadow mapping; this alternative ignores shadow volumes.)

Not found in the PROC file - but of course defined elsewhere - are:

  • a separate representation of each named entity defined by an .ase or .lwo models.
  • surface triangles that are invisible or never seen by the player.
  • Other precalculations: collision detection (CM file) and pathfinding (AAS file)

The File Format

The List of (Geometric) Models

After a 1-line header, the PROC file begins with a series of named "model" sections, which constitute the bulk of the file. These come in two groups, with a shared format. As we shall see, this format specifies constituent surfaces and their textures, grouped by the latter.

Models for Named Entities with Primitives

All these models are listed first. Each represents (and is named after) a named entity with primitives. Common example are those func_statics defined by primitives, and brush-derived doors. The surfaces are those of the object’s brushes and patches.

Models for Areas (Groups of BSP Leaves)

During binary space partitioning, an FM’s map-defined space is split into a list of convex parts, the leaves of the BSP tree. Information about adjacency among leaves is known. Subsequently, using a flood-fill algorithm, sets of leaves are grouped into Areas (aka visLeafs) separated by Inter Area Portals (aka visPortals). Each leaf of the BSP tree becomes marked either as part of a particular Area, or as an opaque solid (i.e., unreachable).

Areas contain information about worldspawn objects contained therein (in whole or in part). See the references for details.

In the PROC file, that information is limited to surfaces and textures.

The PROC model is given a name like "_area0". These area models are numbered consecutively, and referenced by number from the PROC-contained:

  • Nodes section, defining the tree of the BSP.
  • InterAreaPortals section, representing information about where there are visPortals representing lines-of-sight between adjacent or nearby Areas.

A Model and its Surfaces

Every model consists of one or more "surfaces", which containing information about the geometrical representation. The overall form is:

model { /* name = */ <name> /* numSurfaces = */ <number of surfaces>
<surface 0>
<surface 1>
...
}

where <name> is a quoted string literal, and <number of surfaces> is a count of the number of <surface i> that follow. Each <surface i> begins with information about a specific material used by this surface, the number of vertices, and the number of indices.

/* surface i */ { <material> /* numVerts = */ <number of vertices>  /* numIndexes = */ <number of indices>
<vertex 0> <vertex 1> ... <vertex k>
<index 0> <index 1> ... <index m>
}

where <material> is a quoted string literal, referring a material path-name defined in a core or FM-specific .mtr file. The <number of vertices> and <number of indices> are counts of the respective number of items that follow. The actual lists of vertices and indices will contain additional line breaks, which unfortunately impede understanding.

A <vertex> here has the format:

( x y z u v nx ny nz )

where all values are double precision floating point and

  • x, y and z locates the vertex in the world coordinate system.
  • u and v are the texture coordinates, used for mapping the texture maps onto this surface.
  • nx, ny and nz represent the surface normal at the vertex location.

(In what comes next, it will help understanding to imagine that there is a line break after every <vertex i>, and that it is preceded by a comment indicating its vertex number, e.g.:

 /* vertex 0 */ ( -8 -8 -8 0.027777778 1 -1 0 0 )
 /* vertex 1 */ ( -8 8 -8 0.013888889 1 -1 0 0 )
 /* vertex 2 */ ( -8 8 8 0.013888889 0.9861111641 -1 0 0 ) 
 /* vertex 3 */ ( -8 -8 8 0.027777778 0.9861111641 -1 0 0 )

)

An <index> is simply an unsigned integer that succinctly indicates a vertex in the surface’s vertex list. Every three consecutive indices denote a triangle, suitable for rendering.

Inter Area Portals

An Inter Area Portal (IAP or just "portal" here) is the connection between two Areas. Any pair of Areas can be connected through a portal, even if the Areas are not spatially next to each other. Portals can be used for occlusion culling, wherein parts of the FM unseen in the current field of view are left unrendered.

The portals are found in a single list, appearing thusly:

interAreaPortals { /* numAreas = */ <number of areas>  /* numIAP = */ <number of portals>
/* interAreaPortal format is: numPoints positiveSideArea negativeSideArea ( point) ... */
/* iap 0 */ <inter area portal 0>
/* iap 1 */ <inter area portal 1>
...
}

In the header, <number of areas> is the total count of area models defined earlier in the file. The <number of portals> is the count of IAP, each represented by a line of data. As the comment indicates, the inter area portal format is:

<number of points> <positive side area> <negative side area> <point 0> <point 1> ....

where

  • <number of points> is a count of the portal’s vertices (that together make up its "winding"). Four is the typical number.
  • <positive side area> and <negative side area> are integers referencing the defined model Areas separated by the portal, e.g., 0 references _area0.
  • A <point> is a vertex location in world space, namely, 3 double precision floating point values of format ( x y z ). All the points of a winding appear on one line.

Here’s a few lines of an example:

interAreaPortals { /* numAreas = */ 100 /* numIAP = */ 139
/* interAreaPortal format is: numPoints positiveSideArea negativeSideArea ( point) ... */
/* iap 0 */ 4 1 2 ( 2382 2558 189 ) ( 3226.125 2558 189 ) ( 3226.125 521.5 189 ) ( 2382 521.5 189 ) 
/* iap 1 */ 4 1 3 ( 1846 513 189 ) ( 3228.125 513 189 ) ( 3228.125 -8.5 189 ) ( 1846 -8.5 189 ) 
....

Nodes of the BSP Tree

In the PROC file, the BSP tree structure is defined by a list of nodes, with format:

nodes { /* numNodes = */ <number of nodes>
/* node format is: ( planeVector ) positiveChild negativeChild */
/* a child number of 0 is an opaque, solid area */
/* negative child numbers are areas: (-1-child) */
/* node 0 */ <node 0>
/* node 1 */ <node 1>
...
}

where <number of nodes> is a count of nodes in the BSP tree, each on its own line following. As the comment indicates, a node contains information about its splitting plane and two indices which points to either a child node or a leaf. A leaf is either a reference to an Area or to an "opaque, solid" inaccessible location. Specifically, <node> is:

( nx ny nz d ) <positive child> <negative child>

The values of nx , ny and nz (each in range -1 to 1) represent the plane normal (with vector length 1) of the splitting plane. The value of d is the distance of the plane from the world origin. These four double precision floating point values define the plane's position in space.

<positive child> and <negative child> are, in tree terms, right and left branches. They are implemented as integers. If an integer is:

  • positive, it's an index pointing to another node in the node list.
  • zero, it's a tree leaf with a solid, opaque location.
  • negative, it's a tree leaf that references an Area-model. For this case, the actual index is computed as (-1-index). So, for instance, a value of -6 would refer to _area5.

Here’s a partial example:

nodes { /* numNodes = */ 19477
/* node format is: ( planeVector ) positiveChild negativeChild */
/* a child number of 0 is an opaque, solid area */
/* negative child numbers are areas: (-1-child) */
/* node 0 */ ( 1 0 0 0 ) 1 13426
/* node 1 */ ( 1 0 0 -3072 ) 2 110
/* node 2 */ ( 1 0 0 -5120 ) 3 18
...
}

Shadow Models – Background about Shadow Volumes

Briefly, to support stencil shadows, a shadow-causing light source shining on a shadow-casting object projects a "shadow volume" on the other side. The projected surfaces of that volume are determined by the object’s "silhouette", the set of vertices at the transition from triangles that face towards the light and away. Also, some shadow volumes must be closed for algorithmic reasons. A closed shadow volume has both:

  • a "front cap" (nearest the light source, and typically derived from the silhouette.)
  • a "rear cap" (e.g., at the end of a light's range or at some "infinity" set by a system max)

Once created, a shadow volume can be treated as a model object, independent of the object that created it. In some cases, for a particular light source, the shadow volumes of multiple objects overlap, and can be merged. Precalculation of a shadow volume is not always possible, e.g., when either the light source or object is mobile.

Shadow Models - Format for Shadow Volumes

A series of "shadowModel" sections occur, organized by light source, with name of form "_prelight_<name of light>". An example:

shadowModel { /* name = */ "_prelight_light_4"
/* numVerts = */ 4228 /* noCaps = */ 2820 /* noFrontCaps = */ 5250 /* numIndexes = */ 7680 /* planeBits = */ 63
( 479 1841 256 ) ( 516 1815.0402832031 302.1007995605 ) ( 479 1841 270.9410400391 ) ( 516 1815.0402832031 321.5000610352 ) ( 479 1841 256 ) 
( 516 1815.0402832031 302.1007995605 ) ( 468.0658874512 1841 256 ) ( 516 1804.1162109375 321.5000610352 ) ( 479 1841 256 ) ( 516 1815.0402832031 302.1007995605 )
...
32 24 25 32 25 33 758 760 759 760 761 759 762 764 765 762 765 763 
766 768 767 768 769 767 770 772 773 770 773 771 24 42 25 42 43 25 
774 6 777 774 777 775 778 780 779 780 781 779 94 96 95 96 97 95
...

The first header field, "numVerts", gives the number of vertices in vertex list (i.e., the first listing to follow). Each vertex is of form "(x y z)", with an output maximum of 5 vertices per line. (This is similar to the earlier "model" vertex lists, but without the normal or UV information.)

Then come 3 header fields that indicate counts within the indices list, the second listing to follow. As with the models earlier, each index is an integer number pointing to a vertex in the vertex list, and every 3 indices define a triangle of the shadow volume’s surface. Output has a maximum of 18 per line. There are 3 subgroups, which are all run together in the listing, but appear in order:

  1. Shadow volumes with no caps, i.e., both front and rear caps omitted.
  2. Shadow volumes with front caps omitted.
  3. Shadow volumes with front and rear caps.

The border between these is defined by header fields, which are unobviously cumulative:

  1. noCaps. Count of Indices with no caps;
  2. noFrontCaps. noCaps + count of indices with no front caps.
  3. numIndexes. noCaps + noFrontCaps + count of indices with both caps (= total count)

The remaining header field is "planeBits", referring to Shadow Cap Plane Bits. Consider a light’s axis-aligned range box. Some of the range-limit planes may have shadow volume triangles projected onto them. PlaneBits indicates which planes:

Bit 0 = min x; 1 = max x; 2 = min y; 3 = max y; 4 = min z; 5 = max z

PlaneBits is a shortcut to help decide if drawing a rear cap is necessary, given the player’s location.

See Also

About the PROC File Format

Regrettably, the creators of the PROC format never released an official description of it. As mentioned at the outset, Danile Gibson’s 2014 piece on the PROC File Format was the basis for much of this page.

Also helpful was the DMAP section of Fabine Sanglard’s 2012 Doom 3 Source Code Review. This extensive overview is still largely pertinent to TDM engine code today.

Related TDM forum postings about PROC include:

About BSP

Specifics of how TDM constructs and uses BSP is beyond the scope here; see the reference to Fabien Sanglard Doom 3 Review above.

General information about BSP is covered in gaming-related CS textbooks, for example, Foley and van Dam, "Computer Graphics: Principles & Practice", now in 3rd edition.

Among online resources:

  • Wikipedia’s "Binary Space Partitioning" article covers the topic well and has a step-by-step example.
  • Another thoughtful overview are these slides of a BSP Tutorial (within a PDF). See particularly the "Solid Leaf BSP" section.

About Stencil Shadows

Wikipedia’s article about Shadow volume informed the discussion here, and has considerably more about stencil shadow algorithms, including Doom 3 contributions.

For a helpful explanation and diagrams of how stencil shadows works (in an OpenGL context), including use of a shadow volume and stencil buffer to define stencil holes, see:

See Shadow within Performance: Essential Must-Knows for TDM shadow volume diagnostic visualization.

Mappers: As described here, you can turn off loading of the prelight/shadow volumes with r_useOptimizedShadows 0. Better do reloadModels after you change this cvar. Subsequently, stencil shadows should recompute without dmap.