PROC File Format - Revision history

Geep: /* About BSP */

2022-10-31T19:05:43Z

About BSP

← Older revision		Revision as of 19:05, 31 October 2022
Line 208:		Line 208:
	** BSP is explained with diagrams in Chapter 5.		** BSP is explained with diagrams in Chapter 5.
	** The Doom engine initially, before BSP, used simple raycasting inherited from Wolfenstein 3D. This would bog down in one of the more complex Mission 2 rooms. Concurrently, a contract with Nintendo to port Wolfenstein 3D to SNES was in trouble, because that console was even less powerful than the PC. John Carmack, aware of Bell Lab's Bruce Naylor and his presentations about BSP, had him visit and received his reprints. Subsequently, BSP was programmed by id Studios for the (technically easier) Wolfenstein 3D port first, then transferred into the Doom engine.		** The Doom engine initially, before BSP, used simple raycasting inherited from Wolfenstein 3D. This would bog down in one of the more complex Mission 2 rooms. Concurrently, a contract with Nintendo to port Wolfenstein 3D to SNES was in trouble, because that console was even less powerful than the PC. John Carmack, aware of Bell Lab's Bruce Naylor and his presentations about BSP, had him visit and received his reprints. Subsequently, BSP was programmed by id Studios for the (technically easier) Wolfenstein 3D port first, then transferred into the Doom engine.
	** Aside: This book also sheds light on the motivations, skills, and personalities at id Studio at the time. As such, it can be seen as complementary to "Masters of Doom" by David Kushner (Random House, (c) 2003, ISBN 978-0-8129-7215-3), a less-technical ~~biography~~ of ~~founders~~ John Carmack ~~and~~ John Romero.		** Aside: This book also sheds light on the motivations, skills, and personalities at id Studio at the time. As such, it can be seen as complementary to "Masters of Doom" by David Kushner (Random House, (c) 2003, ISBN 978-0-8129-7215-3), that has less-technical but more sweeping and insightful biographies of John Carmack, John Romero, and other contributors.

	===About Stencil Shadows===		===About Stencil Shadows===

Geep: /* About BSP */ Add ref to Game Engine Black Book

2022-10-30T21:05:34Z

About BSP: Add ref to Game Engine Black Book

← Older revision		Revision as of 21:05, 30 October 2022
Line 198:		Line 198:
	===About BSP===		===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.		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:		Among online resources:
	* [https://en.wikipedia.org/wiki/Binary_space_partitioning Wikipedia’s "Binary Space Partitioning" article] covers the topic well and has a step-by-step example.		* [https://en.wikipedia.org/wiki/Binary_space_partitioning Wikipedia’s "Binary Space Partitioning" article] covers the topic well and has a step-by-step example.
	* Another thoughtful overview are these [https://documen.site/download/bsp-trees_pdf slides of a BSP Tutorial (within a PDF)]. See particularly the "Solid Leaf BSP" section.		* Another thoughtful overview are these [https://documen.site/download/bsp-trees_pdf slides of a BSP Tutorial (within a PDF)]. See particularly the "Solid Leaf BSP" section.

			Among offline resources:
			* 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.
			* Fabien Sanglard's book "Game Engine Black Book: DOOM v1.1", (c) 2018, reveals the technology development at id Studios behind early Doom. Available through online vendors as print-on-demand or eBook, ISBN 9781099819773. Among highlights:
			** BSP is explained with diagrams in Chapter 5.
			** The Doom engine initially, before BSP, used simple raycasting inherited from Wolfenstein 3D. This would bog down in one of the more complex Mission 2 rooms. Concurrently, a contract with Nintendo to port Wolfenstein 3D to SNES was in trouble, because that console was even less powerful than the PC. John Carmack, aware of Bell Lab's Bruce Naylor and his presentations about BSP, had him visit and received his reprints. Subsequently, BSP was programmed by id Studios for the (technically easier) Wolfenstein 3D port first, then transferred into the Doom engine.
			** Aside: This book also sheds light on the motivations, skills, and personalities at id Studio at the time. As such, it can be seen as complementary to "Masters of Doom" by David Kushner (Random House, (c) 2003, ISBN 978-0-8129-7215-3), a less-technical biography of founders John Carmack and John Romero.

	===About Stencil Shadows===		===About Stencil Shadows===

Geep at 21:18, 8 May 2022

2022-05-08T21:18:06Z

← Older revision		Revision as of 21:18, 8 May 2022
Line 45:		Line 45:

	* Nodes section, defining the tree of the BSP.		* Nodes section, defining the tree of the BSP.
	* InterAreaPortals ~~section~~, ~~about~~ visPortals, each of which defines a ~~light~~-of-sight boundary between two Areas.		* Section about InterAreaPortals (essentially, visPortals), each of which defines a line-of-sight boundary between two Areas.

	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/connectivity among leaves is known. Subsequently, using a flood-fill algorithm, sets of connected leaves are grouped into Areas (visLeafs) separated by Inter Area Portals. Each leaf of the BSP tree becomes marked either as part of a particular Area, or as an opaque solid (i.e., unreachable). Each Area-model in the PROC file lists the visible surfaces of worldspawn objects contained therein, as explained further below.		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/connectivity among leaves is known. Subsequently, using a flood-fill algorithm, sets of connected leaves are grouped into Areas (visLeafs) separated by Inter Area Portals. Each leaf of the BSP tree becomes marked either as part of a particular Area, or as an opaque solid (i.e., unreachable). Each Area-model in the PROC file lists the visible surfaces of worldspawn objects contained therein, as explained further below.
Line 137:		Line 137:
	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.		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 child> and <negative child> are implemented as integers. If an integer is:

	* positive, it's an index pointing to another node in the node list.		* positive, it's an index pointing to another node in the node list.

Geep: /* Nodes of the BSP Tree */ rewrite

2022-05-06T21:57:55Z

Nodes of the BSP Tree: rewrite

← Older revision		Revision as of 21:57, 6 May 2022
Line 117:		Line 117:

	===Nodes of the BSP Tree===		===Nodes of the BSP Tree===
	In the PROC file, the BSP tree structure is defined by a list of nodes~~, with format~~:		In the PROC file, the BSP tree structure is defined by a list of nodes. Here’s a partial example:

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

	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:		where numNodes 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.

			Formally, a node is:

	( nx ny nz d ) <positive child> <negative child>		( nx ny nz d ) <positive child> <negative child>
Line 138:		Line 141:
	* positive, it's an index pointing to another node in the node list.		* positive, it's an index pointing to another node in the node list.
	* zero, it's a tree leaf with a solid, opaque location.		* 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.		* 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===		===Shadow Models – Background about Shadow Volumes===

Geep: /* Inter Area Portals (basically visPortals) */

2022-05-06T21:48:08Z

Inter Area Portals (basically visPortals)

← Older revision		Revision as of 21:48, 6 May 2022
Line 95:		Line 95:

	===Inter Area Portals (basically visPortals) ===		===Inter Area Portals (basically visPortals) ===
	An Inter Area Portal (IAP) is ~~essentially~~ a visPortal (or occasionally, a portion of a fragmented visPortal). As the name suggests, it defines both ~~the~~ separation between two Areas and the visibility connection between them. IAPs are used for occlusion culling, wherein parts of the FM unseen in the current field of view are left unrendered.		An Inter Area Portal (IAP) is summary information about a visPortal (or occasionally, a portion of a fragmented visPortal). As the name suggests, it defines both a separation between two Areas and the location of the visibility connection between them. IAPs are used for occlusion culling, wherein parts of the FM unseen in the current field of view are left unrendered. See [[Visportals]] for more.

	Only a single instance of this listing appears in a PROC file. Here’s a few lines of an example:		Only a single instance of this listing appears in a PROC file. Here’s a few lines of an example:

Geep: /* Inter Area Portals (basically visPortals) */

2022-05-06T21:41:12Z

Inter Area Portals (basically visPortals)

← Older revision		Revision as of 21:41, 6 May 2022
Line 95:		Line 95:

	===Inter Area Portals (basically visPortals) ===		===Inter Area Portals (basically visPortals) ===
	An Inter Area Portal (IAP) is essentially a visPortal (or occasionally, a portion of a fragmented visPortal). As the name suggests, it's the ~~connection~~ between two Areas. IAPs are used for occlusion culling, wherein parts of the FM unseen in the current field of view are left unrendered.		An Inter Area Portal (IAP) is essentially a visPortal (or occasionally, a portion of a fragmented visPortal). As the name suggests, it defines both the separation between two Areas and the visibility connection between them. IAPs are used for occlusion culling, wherein parts of the FM unseen in the current field of view are left unrendered.

	Only a single instance of this listing appears in a PROC file. Here’s a few lines of an example:		Only a single instance of this listing appears in a PROC file. Here’s a few lines of an example:

Geep: /* Inter Area Portals */ rewrite

2022-05-06T21:32:44Z

Inter Area Portals: rewrite

← Older revision		Revision as of 21:32, 6 May 2022
Line 94:		Line 94:
	Finally, 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.		Finally, 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.

	===Inter Area Portals===		===Inter Area Portals (basically visPortals) ===
	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.		An Inter Area Portal (IAP) is essentially a visPortal (or occasionally, a portion of a fragmented visPortal). As the name suggests, it's the connection between two Areas. IAPs are 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~~:		Only a single instance of this listing appears in a PROC file. Here’s a few lines of an example:

	interAreaPortals { /* numAreas = / ~~<number of areas>~~ / numIAP = */ ~~<number of portals>~~		interAreaPortals { /* numAreas = / 100 / numIAP = */ 139
	/* interAreaPortal format is: numPoints positiveSideArea negativeSideArea ( point) ... */		/* interAreaPortal format is: numPoints positiveSideArea negativeSideArea ( point) ... */
	/* iap 0 */ ~~<inter area portal 0>~~		/* iap 0 */ 4 1 2 ( 2382 2558 189 ) ( 3226.125 2558 189 ) ( 3226.125 521.5 189 ) ( 2382 521.5 189 )
	/* iap 1 */ ~~<inter area portal~~ 1>		/* iap 1 */ 4 1 3 ( 1846 513 189 ) ( 3228.125 513 189 ) ( 3228.125 -8.5 189 ) ( 1846 -8.5 189 )
	...		....
	}		}

	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:		In the header, numAreas is the total count of Area-models defined earlier in the file, and numIAPs is the count of portals, each represented by a line of data. For the latter, as the comment indicates, the format is:

	<number of points> <positive side area> <negative side area> <point 0> <point 1> ....		<number of points> <positive side area> <negative side area> <point 0> <point 1> ....
Line 112:		Line 112:
	where		where

	* <number of points> is a count of the ~~portal’s~~ vertices (that together make up its "winding"). Four is the typical number.		* <number of points> is a count of the IAP'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.		* <positive side area> and <negative side area> are integers referencing the defined Area-models separated by the IAP, e.g., "0" refers to "_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.		* 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===		===Nodes of the BSP Tree===

Geep: /* A Model and its Surfaces */

2022-05-06T21:09:11Z

A Model and its Surfaces

← Older revision		Revision as of 21:09, 6 May 2022
Line 73:		Line 73:
	where <material> is a quoted 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 as output will contain additional line breaks, after every 6 vertices and every 18 indices, which may impede understanding.		where <material> is a quoted 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 as output will contain additional line breaks, after every 6 vertices and every 18 indices, which may impede understanding.

	A <vertex> here has the format:		A <vertex ...> here has the format:

	( x y z u v nx ny nz )		( x y z u v nx ny nz )
Line 92:		Line 92:
	)		)

	Finally, an <index j> is simply an unsigned integer that succinctly indicates a vertex in the surface’s vertex list. Every three consecutive indices denote a triangle.		Finally, 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.

	===Inter Area Portals===		===Inter Area Portals===

Geep: /* A Model and its Surfaces */

2022-05-06T21:04:55Z

A Model and its Surfaces

← Older revision		Revision as of 21:04, 6 May 2022
Line 50:		Line 50:

	===A Model and its Surfaces===		===A Model and its Surfaces===
	Every model consists of one or more "surfaces", with overall form is:		Every model consists of one or more "surfaces", where a "surface" is a set of visible triangles sharing a particular material/texture. For an entity with primitives, these are the triangles making up its faces. For an Area-model, these are triangles contained in this Area, independent of which worldspawn object they come from. The overall form is:

	model { /* name = / <name> / numSurfaces = */ <number of surfaces>		model { /* name = / <name> / numSurfaces = */ <number of surfaces>
Line 58:		Line 58:
	}		}

	where <number of surfaces> ~~is a~~ count ~~of the number~~ of <surface i> that follow. ~~For an Area~~-~~model, "surface" should be interpreted as "set of all visible triangles of~~ this ~~material contained in this Area, independent of which worldspawn object they come from".~~		where <number of surfaces> gives the count of <surface i> that follow. Each <surface i> begins a one-line header like this example:

	~~Each <~~surface ~~i> begins with information about a specific material used by this surface, the number of vertices, and the number of indices~~.		/* surface 2 / { "textures/darkmod/wood/boards/old_small_grainy" / numVerts = / 118 / numIndexes = */ 198
			...
			}

			The overall form is:

	/* surface i / { <material> / numVerts = / <number of vertices> / numIndexes = */ <number of indices>		/* surface i / { <material> / numVerts = / <number of vertices> / numIndexes = */ <number of indices>
Line 67:		Line 71:
	}		}

	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.		where <material> is a quoted 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 as output will contain additional line breaks, after every 6 vertices and every 18 indices, which may impede understanding.

	A <vertex> here has the format:		A <vertex> here has the format:
Line 88:		Line 92:
	)		)

	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~~.		Finally, an <index j> is simply an unsigned integer that succinctly indicates a vertex in the surface’s vertex list. Every three consecutive indices denote a triangle.

	===Inter Area Portals===		===Inter Area Portals===

Geep: /* A Model and its Surfaces */ rewrite start

2022-05-06T20:07:49Z

A Model and its Surfaces: rewrite start

← Older revision		Revision as of 20:07, 6 May 2022
Line 50:		Line 50:

	===A Model and its Surfaces===		===A Model and its Surfaces===
	Every model consists of one or more "surfaces", ~~which containing information about the geometrical representation. The~~ overall form is:		Every model consists of one or more "surfaces", with overall form is:

	model { /* name = / <name> / numSurfaces = */ <number of surfaces>		model { /* name = / <name> / numSurfaces = */ <number of surfaces>
Line 58:		Line 58:
	}		}

	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.		where <number of surfaces> is a count of the number of <surface i> that follow. For an Area-model, "surface" should be interpreted as "set of all visible triangles of this material contained in this Area, independent of which worldspawn object they come from".

			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>		/* surface i / { <material> / numVerts = / <number of vertices> / numIndexes = */ <number of indices>