5 ms·

IIRC, both the Jedi engine (1995, Dark Forces) [1] and the Build engine (1995, Duke Nukem 3D) [2] which were of the same era used "sectors" rather than BSP tree

by a_e_k 2y ago

IIRC, both the Jedi engine (1995, Dark Forces) [1] and the Build engine (1995, Duke Nukem 3D) [2] which were of the same era used "sectors" rather than BSP trees for resolving visibility. Basically, it would traverse a graph as rays exited one sector and entered a neighboring sector. The approach is very much akin to walks through tet meshes in modern science apps. In ray tracing, there are three commonly used spatial acceleration structures these days: grids, binary space partitions, and bounding volume hierarchies. Any one of those might have worked for Doom. Though this post mentions marching through grids (as in Wolfenstein 3D) as not working for the arbitrarily positioned and angled walls, the usual way of using grids for ray tracing is to have each grid cell hold a list of the primitives that overlap it (many-to-many). Then you march the ray through the grid and test the ray against the list of primitives for each cell. You'd often use "mailboxing" (i.e., tiny LRU) to prevent retesting the same primitives over and over, since adjacent grid cells would often share primitives. So basically extending the Wolfenstein 3D grid approach to Doom would have mean voxelizing the map to get lists of candidate walls for each cell, but testing the rays against the walls themselves (rather than say, the voxels themselves like in Minecraft). I'm not sure what the tradeoffs for memory or performance on the 386s of the time would have been, however. But I think it's clear that while BSPs were a clever solution, they weren't the only possible choice. [1] https://en.wikipedia.org/wiki/Jedi_(game_engine) https://en.wikipedia.org/wiki/Jedi_(game_engine) [2] https://en.wikipedia.org/wiki/Build_(game_engine) https://en.wikipedia.org/wiki/Build_(game_engine)

jiggawatts 2y ago
Unreal engine also uses "portals" between rooms, where each room is either entirely visible or entirely invisible. The two approaches have different pros and cons: BSP is theoretically elegant, but requires a fairly expensive "tree walk" step for each frame. This is random in memory and not efficient for modern CPUs because the branch predictor is ineffective and the memory layout is typically not contiguous. It is even worse on GPUs. Doom was written in 1993 when this was much less of a concern, but with Quake and later engines it become a scalability bottleneck. BSP maps require a very compute-intensive pre-processing step. Back then this limited modding and third-party maps because a very high-end PC was needed. This processing also had numerical precision issues. Theoretically this isn't a problem, but in practice it is. Designers had to be careful to make sure the map is completely closed ("airtight") and that the BSP process didn't create thin triangles. This meant that map design tools had to have all sorts of constraints on alignment and snapping to prevent the geometry "blowing up". A gotcha is that BSP splits polygons and hence the processing eats into the the map geometry polygon budget! Portals are much simpler to implement, and each room can scale to any number of triangles. They're much more efficient with modern CPUs and GPUs, because each room can be sent as a single draw call ("batch" processing) instead of a list of individual triangles. The problem with portal-based techniques is that there are sudden step-changes in the number of triangles needed to draw each frame as the camera moves. This can result in stuttering and sudden framerate drops. It can also blow through triangle budgets. A common technique is to limit portal traversal depth in some way, which would cause "black" doorways in the distance and other similar artefacts. Similarly, certain map geometries were poorly supported, such as complex outdoor spaces with visibility from many directions into many rooms.
- tadfisher 2y ago
  > Doom was written in 1993 when this was much less of a concern, but with Quake and later engines it become a scalability bottleneck. Worth clarifying that the 386 and 486 were not pipelined, so they didn't feature branch prediction. The Pentium was, but it had released during Doom"s development and essentially no home user owned one. Quake made extensive use of the Pentium's faster FPU, so they didn't optimize for earlier CPUs.
  - jiggawatts 2y ago
    As an aside, this is also why people keep saying that functional languages are "not much slower" than traditional procedural languages against all evidence. People that learned and like LISP probably did so in the 1980s or 1990s when CPUs were much simpler, memory access times were constant, and "cache lines" weren't even a thing yet! Back then, randomly jumping around memory following a linked list was only about 2x slower than reading an array. Linked lists were much faster for some incremental operations, so the net result was that the two were very comparable. These days arrays can be processed using AVX-512 instructions at a rate of 64 bytes per clock or even higher, whereas even one missed cache entry of a linked-list pointer will stall the CPU for several hundred cycles, during which time the array logic could have chunked through kilobytes.
    - lispm 2y ago
      > memory access times were constant My Symbolics 3640 Lisp Machine, a model introduced in the mid 1980s had 20 MB RAM and 200 MB virtual memory on one or two disks. The OS was already a 50 MB image. The memory used by Lisp was typically much larger than the available (and/or affordable) RAM. Access times were far from constant. A full Garbage Collection over virtual memory took 30 minutes. That's why it had extensive support for incremental garbage collection, copying GC, manual memory management, areas for various data types, ephemeral GC with hardware support, cdr-coded lists, various types of multidimensional arrays, graphics cards with special video memory, 36 bit memory with additional ECC, ... Before saving a new Lisp image to disk, one was using a special command to reorder objects in memory to optimize access times. That command also took 20-30 minutes. Lisp Machines like this were developed because Lisp systems on Mainframes or Mini Computers were thrashing the machines during GC and making performance hell for Lisp users and other time sharing users. Thus a personal machine was needed where the memory and CPU belong to one user. They were among the very first commercially available GUI based personal workstations in 1981.
iforgotpassword 2y ago
I was looking for a post mentioning the build engine. Obviously it came a little later and has higher hardware requirements, but I wonder if this is really related to the sector approach, or whether it's mostly other parts of the engine. It seems much more elegant as it directly uses the data structures that represent the level layout, thus not requiring a preprocessing step, and intuitively I don't see how it's more expensive than walking a tree for every frame. Did anyone do a more thorough investigation into this? I know Doom's engine has been analyzed to death regarding every little detail, but build/duke3d didn't get nearly as much attention.
- vrighter 2y ago
  https://www.fabiensanglard.net/duke3d/build_engine_internals.php https://www.fabiensanglard.net/duke3d/build_engine_internals...

by a_e_k 2y ago

jiggawatts 2y ago

Unreal engine also uses "portals" between rooms, where each room is either entirely visible or entirely invisible. The two approaches have different pros and cons: BSP is theoretically elegant, but requires a fairly expensive "tree walk" step for each frame. This is random in memory and not efficient for modern CPUs because the branch predictor is ineffective and the memory layout is typically not contiguous. It is even worse on GPUs. Doom was written in 1993 when this was much less of a concern, but with Quake and later engines it become a scalability bottleneck. BSP maps require a very compute-intensive pre-processing step. Back then this limited modding and third-party maps because a very high-end PC was needed. This processing also had numerical precision issues. Theoretically this isn't a problem, but in practice it is. Designers had to be careful to make sure the map is completely closed ("airtight") and that the BSP process didn't create thin triangles. This meant that map design tools had to have all sorts of constraints on alignment and snapping to prevent the geometry "blowing up". A gotcha is that BSP splits polygons and hence the processing eats into the the map geometry polygon budget! Portals are much simpler to implement, and each room can scale to any number of triangles. They're much more efficient with modern CPUs and GPUs, because each room can be sent as a single draw call ("batch" processing) instead of a list of individual triangles. The problem with portal-based techniques is that there are sudden step-changes in the number of triangles needed to draw each frame as the camera moves. This can result in stuttering and sudden framerate drops. It can also blow through triangle budgets. A common technique is to limit portal traversal depth in some way, which would cause "black" doorways in the distance and other similar artefacts. Similarly, certain map geometries were poorly supported, such as complex outdoor spaces with visibility from many directions into many rooms.

tadfisher 2y ago
> Doom was written in 1993 when this was much less of a concern, but with Quake and later engines it become a scalability bottleneck. Worth clarifying that the 386 and 486 were not pipelined, so they didn't feature branch prediction. The Pentium was, but it had released during Doom"s development and essentially no home user owned one. Quake made extensive use of the Pentium's faster FPU, so they didn't optimize for earlier CPUs.
- jiggawatts 2y ago
  As an aside, this is also why people keep saying that functional languages are "not much slower" than traditional procedural languages against all evidence. People that learned and like LISP probably did so in the 1980s or 1990s when CPUs were much simpler, memory access times were constant, and "cache lines" weren't even a thing yet! Back then, randomly jumping around memory following a linked list was only about 2x slower than reading an array. Linked lists were much faster for some incremental operations, so the net result was that the two were very comparable. These days arrays can be processed using AVX-512 instructions at a rate of 64 bytes per clock or even higher, whereas even one missed cache entry of a linked-list pointer will stall the CPU for several hundred cycles, during which time the array logic could have chunked through kilobytes.
  - lispm 2y ago
    > memory access times were constant My Symbolics 3640 Lisp Machine, a model introduced in the mid 1980s had 20 MB RAM and 200 MB virtual memory on one or two disks. The OS was already a 50 MB image. The memory used by Lisp was typically much larger than the available (and/or affordable) RAM. Access times were far from constant. A full Garbage Collection over virtual memory took 30 minutes. That's why it had extensive support for incremental garbage collection, copying GC, manual memory management, areas for various data types, ephemeral GC with hardware support, cdr-coded lists, various types of multidimensional arrays, graphics cards with special video memory, 36 bit memory with additional ECC, ... Before saving a new Lisp image to disk, one was using a special command to reorder objects in memory to optimize access times. That command also took 20-30 minutes. Lisp Machines like this were developed because Lisp systems on Mainframes or Mini Computers were thrashing the machines during GC and making performance hell for Lisp users and other time sharing users. Thus a personal machine was needed where the memory and CPU belong to one user. They were among the very first commercially available GUI based personal workstations in 1981.

iforgotpassword 2y ago

I was looking for a post mentioning the build engine. Obviously it came a little later and has higher hardware requirements, but I wonder if this is really related to the sector approach, or whether it's mostly other parts of the engine. It seems much more elegant as it directly uses the data structures that represent the level layout, thus not requiring a preprocessing step, and intuitively I don't see how it's more expensive than walking a tree for every frame. Did anyone do a more thorough investigation into this? I know Doom's engine has been analyzed to death regarding every little detail, but build/duke3d didn't get nearly as much attention.

vrighter 2y ago
https://www.fabiensanglard.net/duke3d/build_engine_internals.php https://www.fabiensanglard.net/duke3d/build_engine_internals...