Fabien Sanglard's Website

submited by

Style Pass

2021-05-24 04:00:04

Before studying the iPhone version, it was important for me to understand how Doom engine WAS performing rendition back in 1993. After all the OpenGL port must reuse the same data from the WAD archive. Here are my notes about Doom 1993 renderer, maybe it will help someone to dive in. January 13th, 2010 : Reddit annihilated my bandwidth (4 hours after publication). Back online. February 8th, 2010 : Slashdotted, moving videos to YouTube.com. I can't keep up with 5000 visitors a day. July 23th, 2011 : Two videos surfaced about doom development: A Visit to id Software and Doom: Post-Mortem 2011.

Maps were designed in 2D by a level designer using Doom editor (DoomED). LINEDEFS were describing closed sectors (SECTORS in the source code), the third dimension (height) was defined on a per sector basis. The first level of Doom E1M1 looks like this: When the map was finished, it was sliced via Binary Space Partitioning. Recursively a LINEDEF was chosen and its plan extended as splitting plan. LINEDEF were hence cut into segments (SEGS) until only convex SubSectors (SSECTOR in the code) remained. Trivia: Both DoomED and iBSP were programmed using....Objective-C on a NextStep workstation. Fifteen years later, the same language, running on almost the same operating system are running the game in the palm of our hand! I did a bit of web archeology and managed to find the original source code of idbsp, it's worth taking a look: Following is an example of the first map being recursively split: Recursion level 1 In blue a wall is selected and extended as splitting plan (red). Splitter were selected in order to balance the BSP tree but also to limit the number of SEGS generated. The green bounding boxes are used later to discard entire chunks of map. Recursion level 2 (only right subspace) In the end, SECTORS were spliced into convex sub-sectors (called SSECTORS) and LINEDEFS were sliced into segments (called SEGS):

Two examples with E1M1 (Doom first map) and a BSP looking as follow: //Coordinate system origin in lower left corner // Plane equation ax + by + c = 0 with // unit normal vector = (a,b) // Root plane (splitting map between zone A and B): normal = (-1,0) c = 3500 // A plane (splitting zone A between zone A1 and A2): normal = (1,0) c = -2500 // B plane (splitting zone B between zone B1 and B2): normal = (-0.24,0.94) c = -650 // Injecting any point coordinate (x,y) in a // plane equation gives the distance from that plane. BSP walking always start at the root node, sorting both subspaces. Recursion follows on both node children. Example 1 : Player (green dot) watching through the window from point p=(2300,1900): // Player position = ( 2300, 1900 ) // R_RenderBSPNode run against AB splitter (-x + 3500 = 0): -2300 + 3500 = 1200 Result is positive: Closest subspace is in the FRONT of the splitting plane. (A is closer than B). // R_RenderBSPNode now run recursively against the two child of the root node: A1/A2 splitter and B1/B2 splitter. // R_RenderBSPNode run against A1/A2 splitter (x - 2500 = 0): 2300 - 2500 = -200 Result is negative so the closest subspace is in the BACK of the splitting plane. (A1 is closer than A2). // R_RenderBSPNode run against B1/B2 splitter (-0.24x +0.97y - 650 = 0): -0.24 * 2300 + 0.97 * 1900- 650 = 641 Result is positive so the closest subspace is in the FRONT of the splitting plane. (B1 is closer than B2). Result: Sorted zones, from near to far: { A1, A2, B1, B2 }