How much of a genius-level move was binary space partitioning in Doom? (2019)
twobithistory.org
twobithistory.org
This in itself is a superpower, especially in computer science where history is considered a waste of time.
This is commonly even true in actual research computer science, where you'd think papers were crucial. Nowadays with the flood of "PR" preprints particularly in machine learning, it would be impossible to keep up and so nobody tries -- most of those papers write-once-read-never.
When I moved out of computing into biochemistry and medicine, and now into climate, I found people take papers seriously, which is a pleasure.
SIGGRAPH had been around since 1974 and was well-known if you were doing anything graphics related--especially 3D. You couldn't help but trip over the algorithms you needed.
The genius was putting any of these algorithms meant for super-expensive 3D graphics hardware on a wimpy-ass 1990 PC.
But you might be thinking of Graphics Gems (vols 1–5). https://www.realtimerendering.com/resources/GraphicsGems/
Not-invented-here syndrome in practice. Which kinda works for the n-th shitty web framework. But it goes really poorly in any complex domain.
It could be even the opposite: because many people can look into the code the code converges to the state of the art.
This results in new contributors being overwhelmed with the complexity of the classes and totally pushing aside the prior work in favor of starting at the basic level.
The module systems of common languages (like C# and Rust) tend to represent a "bag" of structs and traits, whereas a more advanced "evolutionary" language would represent source files or modules in a hierarchy of simple to advanced behavior.
Julia has many flaws, but they're a different kind of flaws. Mostly caused by choosing function overloads based on vibes, and reckoning with the pandemonium caused by modules being glued together in unanticipated ways.
I work in a space where I simply don't have bandwidth to read every paper out there, but a few question on ChatGPT managed to narrow the field for me in 30 seconds, and I could take it from there. It could even prototype the algorithm tailored to my specs. Game changer.
I’m working on a React UI based SQL query builder, where the entire data structure is recursive.
ChatGPT is literally unusable for this
(I also use the paid version).
Well, there’s your problem.
You're underselling it. Not only will it give you a crap answer, but it'll give it to you with unerring confidence!
I feel it was more common in the earlier days of programming. With no open source "game engines" and the Githubbed, Stackoverflown internet we have now fetching about for some of the "programming secrets" whether that was in a university library or a technical computer magazine was about all you had.
Unfortunately, ACM and IEEE are paywalled, as are many of the specialty journals for operations research and the like. Newer stuff is often on Arxiv, but the simple algorithms usually live in older papers that aren't.
Does someone know a good way how to put a filter on these "write-once-read-never" papers and just get the top 10 papers each month?
I keep repeating the story, but in 2020, I surprisingly got #1 on the MPI Sintel benchmark for optical flow in the category "Clean EPE matched", by re-implementing a 15 year old paper. (And replacing their approximation of a quadratic solver with actually using a quadratic solver.)
That said, I feel like it's not just machine learning which is flooded with useless preprints. It's the entire internet now. When I wanted to look up some context for quaternion math, it was surprisingly challenging to find something a bit more in-depth than motivated amateurs who try to sell their self-published ebook and/or Udemy course. No, "np.quaternion" is not a mathematical formula. In the end, it was easier to dig up my old paper book, which had a nice A4 overview page with all the relevant formulas.
Research papers, to be maximally reusable and future-proof, should prefer to present information in as plain English as possible and commonly-used mathematic terminology and symbols rather than obscure forms where possible. Using big words (or Latin) doesn't add profoundness, but they can add artistic flair in other contexts where elucidation isn't the goal. ;-)
This is exactly what they do, even domain specific language is selected to precisely convey meaning and differentiate from incorrect but close interpretations.
I don't know whether this is a general change in fashion, or because the early papers in a field are dealing with simpler ideas (at least ideas that are not reliant on a decade of prior papers and terminology), or because it's only the good old papers that still come up in literature reviews and all the badly written stuff has long since been forgotten.
CTC loss: https://www.cs.toronto.edu/~graves/icml_2006.pdf
DeepLearning: https://hal.science/hal-04206682/document
And both of these papers are new and on more recent research, so it's not just old papers that are good. It's just that there is a flood of bad new papers drowning out a constant signal with additional noise.
Papers in the same conferences from 1982 are full of beautiful insights and they’re easy to read. But often that’s because they’re a five-page long story that might provide only a tiny subset of what we expect nowadays. They often don’t specify exactly what the algorithms do, they just kind of describe the ideas in English. Formal definitions are like three sentences of handwave. Proofs are similarly short or missing. Typically if you follow the citation chain you’ll find a dozen papers saying “we show that the original construction by Seminal Author is totally broken in this situation, but we show how to fix that with a small tweak and a better security definition.” Eventually you get to modern papers that actually start with the right definitions to deal with all that stuff, but take longer to read.
Obviously to the layperson the short old papers are fun and full of insight! To an expert they’re still full of insight, but we wouldn’t let them out of our lab in that condition. It’s very much like comparing a beautiful old classic car to a modern car with safety features. They both look great: but you don’t want to get into even a minor fender bender in the old car.
As someone with a background in academia, I have to disagree with the assertion that papers should be written in "plain English" and some lowest-common-denominator of symbolism.
It doesn't make me happy to argue against that, but the truth is that scientific papers MUST build on previous knowledge. No leading gene editing research paper is coming out with long-winded prose explaining what DNA and RNA are. No particle physics paper coming out of CERN is going to avoid quantum field theory jargon and terminology in the hopes that a lay person with a pre-calculus level of math education is going to be able to study the results and understand it. How many times longer would these papers be if they did try to do that? My calculus book from undergrad was some 600 pages long (it covered three semesters, to be fair)--now imagine that the people writing these papers read that 600 page book in their first one or two years of undergrad, and then proceeded to study their subject for AT LEAST another 6 years (closer to 8 for physics) before getting "Dr" in front of their name. How many pages would a research paper need to be for a lay person to understand? Probably pretty long.
The truth is that there sometimes IS NOT a "plain English" way to explain something. Yes, you can use inaccurate metaphors and analogies about cats in boxes, but that doesn't lead to someone actually understanding the Schrodinger equation and Hilbert spaces. Believe it or not, scientists are not sitting around all day figuring out which Latin words will sound the most "profound" in their prose. Those are just the words they really actually use. Because words have meaning and some ideas are so common that they deserve to be condensed into a word, or an equation, or a symbol...
At the end of the day, these papers are written to advance the respective field of study. The best way to do that is to write papers that are going to be relevant to people who might actually build on the results. The people who might actually build on the results are going to be people who understand the requisite background information. If Joe Schmoe wants to read a particle physics paper, then he better pull out his high school math books and work his way up to at least a masters degree level understanding of physics and mathematics.
I would never go into the kitchen of a professional chef and tell her to stop referring to a "paring knife" or a "fillet knife" because I'm not familiar with cooking jargon. I wouldn't tell her that she has to re-explain what shape those knives have every time she explains a new recipe or technique. I would just have to learn the jargon if I actually cared enough.
Creating something new is so much work.
Like skying it could be fun when you are not a professional and you do it on your terms, but once you are a professional it is something different.
Software patents exist in this space where the patent holder gets the best of both worlds: they get to argue that an infringer nebulously infringes on the ambiguous "steps". Meanwhile the source code is not in the patent, therefore protected from public eyes. Patents should require exposing the source code.
Talking of knowledge and books: It was around 1995 or so and I was in my last year of high school. We went on a small field trip to a local computer show and only about 4-5 students in the whole school were interested in going, at that time computer science was still a very new topic over here in the 3rd world.
At the show I found a stall in a corner with some random hardware books and then this giant white tome about computer graphics. The size of it was intimidating and while scanning through it I saw some ridiculous mathematical formulas that I couldn't make head or tails of. But either way I had to have it and luckily I had gotten just enough money from my mom that I was able to buy it.
That was how I lucked into Computer Graphics - Principles and Practice (2nd Edition) which had just come out. That book was a literal gold mine of concentrated topics for a kid, I spent more time studying that book in the next year than I had done for all my high school subjects combined.
My deepest thanks to everyone who contributed to it, it's shown here on Fabien's page: https://fabiensanglard.net/Computer_Graphics_Principles_and_...
Not to ramble, but a funny addition to the story. The only compilers/languages I could find locally were DOS Basic and then Pascal with Assembly which I learned most of my programming skills in. I had heard of this magical C language that was so fast and all the games were now being made in it, but for probably 3 years I couldn't find a compiler for it anywhere.
Then randomly one day right around the Doom 1994 release date my uncle who had started working with hardware had been given a promotional Watcom C/C++ compiler which he gifted to me, and I could suddenly work with the same language and compiler that they had used! Of course it took me a bit of time to learn but by the time I got the CG Bible in 1995 I was set.
The whole thing is a great story.
https://all-things-andy-gavin.com/2011/02/02/making-crash-ba...
> Andy had given Kelly a rough idea of how we were getting so much detail through the system: spooling. Kelly asked Andy if he understood correctly that any move forward or backward in a level entailed loading in new data, a CD “hit.” Andy proudly stated that indeed it did. Kelly asked how many of these CD hits Andy thought a gamer that finished Crash would have. Andy did some thinking and off the top of his head said “Roughly 120,000.” Kelly became very silent for a moment and then quietly mumbled “the PlayStation CD drive is ‘rated’ for 70,000.”
> Kelly thought some more and said “let’s not mention that to anyone” and went back to get Sony on board with Crash.
◆ Service life of feed motor
The current consumption of feed motor must be less than initial value plus 30% after 50,000 cycles. (1cycle : innermost track → outermost track → innermost track)
◆ Service life of limit switch
The contact resistance must be less than 100mΩ after 50,000 cycles. (1cycle : innermost track → outermost track → innermost track)
◆ Pick-up slide operation
The pick-up should operate perfectly after 50,000 cycles. (1cycle : innermost track → outermost track → innermost track)
https://github.com/JonathanDotCel/psx_clean_laser_mirror
https://psxplanetcodes.tripod.com/repair.htm
Plastic, unlike brass, wears out quickly due to friction. Quickest test was flipping PSX upside down, worn out sled unit would start playing perfectly again in this orientation.
so Yes, there was a rather low seek (move up and down) limit on first units caused by cheap design and inferior manufacturing process.
Was the vertex compression responsible for the wobbling/swimming effect you'd see on models, when running Q1 and Q2 in OpenGL mode?
[1] https://all-things-andy-gavin.com/2011/02/02/making-crash-ba... Especially part 3.
> Our occlusion worked on a texture level. That is, if we had a giant polygon with a fern texture on it (think many leaves but lots of empty space) the occlusion could actually get rid of polygons behind the leaf part of the texture but leave the polygons seen through the alpha channel holes. No other game had that kind of detail in occlusion, and it paid off immensely. Given how small ground polygons could be in the distance, a little fern action went a long way.
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.
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.
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.
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.
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.
I doubt that the early small memory Intel-based machines played much of a role for Lisp programmers or even education (other than being used as a terminal to a different machine). Lisp was memory hungry, due to the interactive use (with resident dev tools) with a garbage collected heap. The 386 supported virtual memory and various other ways to extend the available RAM was used on early intel machines under the various DOS variants...
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.
Off the top of my head I remember two different articles from local German computer magazines (that are still in my basement) discussing and implementing them.
But so were many, many other ideas and approaches.
Not taking away from Carmack's genius, in my opinion it was not in inventing a horse and neither in finding one, but in betting on the right one.
[1] If you were a programmer in the 90s - any kind of programmer - you most certainly had.
And every graphic programmer worth it's salt had a copy of "Computer Graphics - Principles and Practice" on the desk and followed whatever came out of the "Graphics Gems" series.
We knew about BSP, Octrees and all that stuff. It was common knowledge.
That isn't really true. Games were there pretty much for all of the PC era. I was using a computer at the time Doom came out, and there were a bajillion (obviously less graphically sophisticated) games in common circulation, and gaming was a significant and widely accepted part of home computer sales.
Wolfenstein only worked, as the article pointed out, by significantly constraining the problem. While Doom wasn’t as unconstrained as Quake it enabled a significant amount of complexity compared to Wolfenstein.
In fact, another one of Carmack's contributions to PC gaming was porting Super Mario 3 to the PC and demoing it to Nintendo as a proof of concept for smooth pixel sized scrolling, which was something that PCs were very poor at. His approach was to basically do a graphical diff frame by frame and only render the parts of the screen that changed, whereas all the other home computers I mentioned and even gaming consoles like the NES and Sega Master System had dedicated hardware for scrolling sprites.
Nintendo did not go forward with Carmack's proposal, wanting to keep their games exclusive to their own platform, but Carmack and id Software did manage to use that technology to develop Commander Keen. Prior to Commander Keen there were maybe 3-4 PC games that had any kind of pixel scrolling whatsoever and it was fairly limited.
That was the era of Lemmings, Prince of Persia, Dune, Sim City, Wolfenstein 3D, Leisuresuit Larry -- plus a bajillion other smaller games. It wasn't the best gaming platform, but it's bonkers to say that computer games weren't really a thing then, or that the designers of computers were blind to that.
We're at that point at the era where "multimedia" was a buzz word, and I remember getting CD-ROMS with edutainment stuff that had real video in it -- that was a big deal around then.
Consider that many of the games you mentioned such as Lemmings, Prince of Persia, and Sim City were not even released on the PC originally and were ported to the PC often times years after their initial release.
In 1990 PCs including clones made up only 15% of market share, whereas by 1994 they made up over half of the home computer market share. The 90s were a wild time and a lot of things changed over a small period of time.
- PCs were always used for games (softening that: at least by the 286 era that was already true)
- By 1993 PCs were also designed with games in mind
But it doesn't follow that PCs were always designed with gaming in mind. They weren't, but since they were always used for that, even if they weren't designed for them, after a decade of such usage, it became a design concern.
Atari/Amiga were better but I'd say it was indeed the turning point.
So yeah your comment is spot on.
But if we are talking about home computers like the Amiga, Ataris and such, then I fully agree with you. My first computer was a 486 with the big Creative Discovery CD 16 kit, so many good memories...
You had graphical games available on a PC XT with Hercules monochrome, people. Mind, not all of them but you had them.
I finished Prince of Persia on that.
Of course, games exploded when the VGA and Sound Blaster were out. But not having 256 colours or sound didn't stop people.
If your argument is simply that PCs had games, then sure, and the article isn't disputing that. The article is explicitly saying that games were on PCs, and the way you got them to run on PCs was by making use of careful software techniques to compensate for the lack of hardware support.
If you still object to this, then by all means let us know what features did PCs have that supported gaming. I can tell you numerous features that other home computer systems had to explicitly support video games, but I can't name any that the PC had prior to around the mid 90s. Maybe the Sound Blaster?
Doom made folks want PC, it just didnt work that well on consoles. Then multimedia and windows 95 in PCs steamrolled everything else, even with high prices and famous MS instability.
If you needed all-in-1 solution, PC was the way to go.
If you bought a PC in the 80s, you didn't buy it for gaming and PCs did not have hardware support for gaming like other home computer systems did.
Finally, and I would have thought a website like this would be aware of this fact, you don't develop video games to run on the latest hardware. DOOMs official system requirements was a 386 with 4 MB of RAM.
The fact that they could run games was great for a lot of us. But they weren't designed to do it.
There's more than a decade gap between "IBM compatible" clones taking over, and Doom coming out.
Doom and pentium come out at the same time. I guess my xUSSR got the latter much later, as I remember struggling on my 386
Also, the clones had nothing better than the PC speaker for audio, even if that could be used very creatively by games like Monkey Island. The PC speaker was most definitely not designed for games.
The SoundBlaster cards can be said to have been designed for games, but they were a separate product that could be bought as an add-on for IBM PCs or clones.
Only during the second half of the nineties, after Windows 95, IBM PC clones with video cards and audio cards really suitable for games have become common.
even the most hardware-deficient gaming systems had them. The PC didn't.
Systems with hardware sprites include arcade video games of the 1970s and 1980s; game consoles including as the Atari VCS (1977), ColecoVision (1982), Famicom (1983), Genesis/Mega Drive (1988); and home computers such as the TI-99/4 (1979), Atari 8-bit computers (1979), Commodore 64 (1982), MSX (1983), Amiga (1985), and X68000 (1987). Hardware varies in the number of sprites supported, the size and colors of each sprite, and special effects such as scaling or reporting pixel-precise overlap.
https://en.wikipedia.org/wiki/Sprite_(computer_graphics)
the pc had: VGA
Not quite! The Apple II didn't. Neither did the IIgs nor the Mac.
On the other hand, the simple framebuffer of the VGA was much more flexible, and was the better approach for those early 3D games. Mode 13h for the win!
Probably from that same paper.
It was/is such a cool fun little algorithm to implement.
We were building virtual reality worlds 24 years ago and people are still not using it.
Supposedly among the first pre alpha game rendering https://m.youtube.com/watch?v=U0GyQCYVb2s
EverQuest was truly a crazy game considering the era.
It was actually for the Super Nintendo port of Wolfenstein that Carmack first researched and implemented binary space partitioning. In Wolfenstein, this was relatively straightforward because all the walls were axis-aligned; in Doom, it would be more complex. But Carmack realized that BSP trees would solve Doom’s speed problems too.
The genius of binary space partitioning in Doom (2019) - https://news.ycombinator.com/item?id=33692947 - Nov 2022 (159 comments)
Using Binary Space Partitioning in Doom - https://news.ycombinator.com/item?id=21906051 - Dec 2019 (8 comments)
How Much of a Genius-Level Move Was Using Binary Space Partitioning in Doom? - https://news.ycombinator.com/item?id=21467817 - Nov 2019 (6 comments)
https://github.com/TurkeyMcMac/ts3d
Full disclosure: TurkeyMcMac was my son. He wasn't much of a gamer, but he was a pretty good programmer. He wrote this in high school.
I hope I haven't misunderstood your use of the past tense when I say: I'm sorry for your loss. He clearly had a fun imagination and a lot of potential.
He would try a lot of algorithms until he hits something genius enough to solve the problem. I have a feeling this is the situation when you dig in something so hard that solution eventually comes to you.
When Carmack was working (I think on Quake), you could follow his todo list, which he kept stored in a .plan file on his server. If you used the Unix shell command "finger johnc@idsoftware.com" command, it would send the text of that file. It was pretty amazing to watch him crank through his tasks in near real time.
The texts are archived here: https://github.com/ESWAT/john-carmack-plan-archive
He is also pretty good at poker, apparently: http://www.ntk.net/1998/02/13/?l=114#l
- develops Wolf 3D
- develops Doom, realizes there is more optimal algorithm for Wolf 3D, implements it for SNES port
- develops Quake, realizes there is optimal algorithm for Doom allowing for zero overdraw. Sadly never implemented or documented further than a footnote in Abrash book, maybe portals like in Duke 3D?