How much of a genius-level move was binary space partitioning in Doom? (2019)

Original Article ↗ Hacker News Discussion ↗

BSP in Doom: Genius vs. Solid Application

  • Many commenters note BSP trees were already standard in computer graphics and SIGGRAPH literature.
  • The “genius” is framed less as invention and more as choosing the right known technique and making it work on very weak early‑90s PCs.
  • Some recall BSP and related structures (octrees, sector/portal systems) being common knowledge among graphics programmers, but acknowledge implementing BSP robustly was non‑trivial and relatively rare in games.

Alternative Visibility / Partitioning Techniques

  • Other engines of the era (e.g., Jedi, Build, Unreal) used sectors and portals rather than BSP, trading preprocessing cost for runtime flexibility.
  • Discussion covers tradeoffs:
    • BSP: elegant, good visibility culling, but expensive preprocessing, numeric fragility, tree-walks with poor cache/branch behavior on modern CPUs/GPUs, and modding pain.
    • Portals/sectors: simpler, map‑structure‑aligned, batch‑friendly, but cause sudden visibility step-changes and can blow triangle budgets.
    • Grids/voxels and quad/octrees are mentioned as alternatives; memory/perf tradeoffs on 386‑class hardware are described as unclear.

Hardware Constraints and PC Gaming History

  • Debate over whether early PCs were “meant” for games or primarily for business:
    • One side says games were common and drove home PC purchases by the early 90s.
    • The other emphasizes that PCs lacked dedicated gaming hardware (sprites, scrolling, audio) that contemporaneous home computers and consoles had.
  • Doom is portrayed as a software‑driven workaround for missing graphics hardware: VGA framebuffers vs. sprite/scrolling chips.
  • Discussion traces a rough transition: early 90s “multimedia” era (sound cards, SVGA, CD‑ROM), then mid‑late 90s 3D accelerators as the real turning point.

Research, Old Papers, and Not‑Invented‑Here

  • Strong theme: reading older literature is a “superpower”; many breakthroughs in practice come from rediscovering 1960s–1980s work made practical by modern RAM/cache/CPUs.
  • Examples include old “impossible” algorithms becoming trivial on contemporary hardware and classic routing/vision/ML methods outperforming newer ideas.
  • Several complain about:
    • Paywalled ACM/IEEE papers.
    • “Write‑once‑read‑never” preprint flood, especially in ML.
    • Industry’s ahistorical tendency and NIH syndrome leading to repeated reinvention.
  • Others point out that in some domains (graphics, cryptography) deep literature use is normal and modern papers add necessary formalism.

Paper Readability and Jargon

  • Mixed views on whether research should use “plain English” vs. dense formalism and domain jargon.
  • Older CS papers are remembered as shorter and more readable but often underspecified; newer ones are longer, more precise, and proof‑heavy but harder for non‑experts.

Tools, Books, and Learning Culture

  • Commenters reminisce about foundational graphics texts (e.g., major graphics textbooks, gem collections), early compilers, and learning from books and magazines before ubiquitous open source and Stack Overflow.
  • One thread laments that modern agile/SaaS environments and dopamine‑driven open source make it harder to justify days spent just reading.

Other Game‑Engine Anecdotes

  • Crash Bandicoot is highlighted as an example of “inelegant but better” engineering:
    • Precomputed per‑position visibility instead of runtime VSD.
    • Per‑vertex animation with custom compression.
    • Heavy CD streaming pushing hardware beyond its nominal seek lifetime.
  • There are notes on vertex animation and streaming in other 90s engines, and on early VR projects also using BSP trees.