Editing Doom engine (section)

==Binary space partitioning==
''Doom'' makes use of a system known as [[binary space partitioning]] (BSP).<ref name=Engine>{{cite web|last=Abrash|first=Michael|title=Quake's 3-D Engine: The Big Picture|url=http://www.bluesnews.com/abrash/|access-date=22 August 2012}}</ref>  A tool is used to generate the BSP data for a level beforehand. This process can take quite some time for a large level. It is because of this that it is not possible to move the walls in ''Doom''; while doors and lifts move up and down, none of them ever move sideways.

The level is divided up into a [[binary tree]]: each location in the tree is a "node" which represents a particular area of the level (with the root node representing the entire level). At each branch of the tree there is a dividing line which divides the area of the node into two subnodes. At the same time, the dividing line divides linedefs into line segments called "segs".<ref name=bsptree>{{cite web|last=Apted|first=Andrew|title=SPECIFICATION for GL-Nodes|url=http://www.faqs.org/faqs/graphics/bsptree-faq/|access-date=22 August 2012|archive-date=2 September 2012|archive-url=https://web.archive.org/web/20120902064055/http://www.faqs.org/faqs/graphics/bsptree-faq/|url-status=live}}</ref>

At the leaves of the tree are [[convex polygon]]s, where further division of the level is not needed. These convex polygons are referred to as subsectors (or "SSECTORS"), and are bound to a particular sector. Each subsector has a list of segs associated with it.<ref name=Engine />

The BSP system sorts the subsectors into the right order for rendering. The algorithm is fairly simple:

#Start at the root node.
#Draw the child nodes of this node recursively. The child node closest to the camera is drawn first using a [[Scanline algorithm]]. This can be found from looking at which side of the node's dividing line the camera is on.
#When a subsector is reached, draw it.<ref name=EngineReview>{{cite web|last=Sanglard|first=Fabien|title=Doom engine code review|url=http://fabiensanglard.net/doomIphone/doomClassicRenderer.php|access-date=23 August 2012|archive-date=3 September 2012|archive-url=https://web.archive.org/web/20120903074732/http://fabiensanglard.net/doomIphone/doomClassicRenderer.php|url-status=live}}</ref>

The process is complete when the whole column of pixels is filled (i.e., there are no more gaps left). This ordering ensures that no time is used drawing objects that are not visible and as a result maps can become very large without any speed penalty.