9 ms·
How much of a genius-level move was binary space partitioning in Doom? (2019)
- blakesterz 2y ago[flagged]
- daft_pink 2y agoThey also created wolfenstein, which I feel was more incredible given the limited hardware it ran on.
- tejohnso 2y agoAnd in fact, from TFA, 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.
- anonzzzies 2y agoEven more amazing that the company they hired to do the Nintendo port copped out so they had to stall doom dev to do the Nintendo port and because the hardware was not good enough they had to do bsp to make it work at all…
- DennisL123 2y agoA neat thing in Wolfenstein is the use of LFSR to transition the screen to red when you die. https://fabiensanglard.net/fizzlefade/ https://fabiensanglard.net/fizzlefade/
- deleted 2y ago[deleted]
- gumby 2y ago> So Carmack ... started reading research papers. 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.
- vslira 2y agoOne of the first "hacker" breakthroughs in my first startup was due to following citations on a paper kind of related to my problem until I got to a paper from '61 implementing the exact algorithm I was needing at the time. Numerical approximations to a gnarly probabilistic problem that would make any engineer proud. Worked like a charm and, in a hardware thousands of times faster than it was designed to run, it was crazy efficient.
- richrichie 2y agoCould you please share the paper reference? Thank you.
- sitkack 2y agoOne of the nicest things about finding old papers is that often the "unworkable" technique now fits in L1 or L2 cache.
- fxtentacle 2y agoOr that RAM is practically endless now. I still remember when I was reading an old pattern recognition paper and they dismissed one simple, elegant solution as "obviously impossible" because they estimated it would need 10485760 KB of RAM. We then bought a server with 128 GB of RAM and shipped their impossible approach in production :) where it's been running nicely for 9 years now.
- wheels 2y ago> In the early ’90s, when id Software first began publishing games, the games had to be programmed to run efficiently on computers not designed to run them, computers meant for word processing, spreadsheet applications, and little else. 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.
- woofcat 2y agoIt is true, games were present but it wasn't in the objectives of the hardware manufacturers to have "better game support" at this time.
- MBCook 2y agoI don’t think the author meant that computers weren’t designed for games, I think they specifically were referring to 3D games. 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.
- Maxatar 2y agoCan't say I agree. I also remember the late 80s and early 90s and PCs were simply not well equipped to run video games. Home computers that did run video games had special hardware dedicated for it, like the Commodore 64, the MSX, and the ZX Spectrum, but PCs weren't geared for games. 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.
- brcmthrowaway 2y agoWeird article. Everyone stands on the shoulders of someone else. Even North Korean Linux
- dang 2y agoRelated: The genius of binary space partitioning in Doom (2019) - https://news.ycombinator.com/item?id=33692947 https://news.ycombinator.com/item?id=33692947 - Nov 2022 (159 comments) Using Binary Space Partitioning in Doom - https://news.ycombinator.com/item?id=21906051 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 https://news.ycombinator.com/item?id=21467817 - Nov 2019 (6 comments)
- Nition 2y agoFor Crash Bandicoot (1996), Naughty Dog sidestepped the entire VSD performance problem. Since the camera is on rails and only moves forward and back, they pre-calculated the visibility for every position and stored it in the game's data. That meant no visibility calculation needed in real time at all, and they could do it per-pixel. As a result of that and some other brilliant tricks, they were able achieve probably the best graphics on Playstation.
- mh- 2y agoThat's a very cool example of doing the "inelegant" thing and it just being objectively better. Am always on the lookout for these anecdotes, thanks!
- Nition 2y agoIn the same game, for character animations, instead of just using bones like others were doing - often resulting in some big distortions with low-poly characters - they set up per-vertex animation, letting the artists manually position any vertex every frame. Then wrote a custom compression algorithm in assembly to store it.
- knome 2y agoNot to mention actively streaming levels from the disk while you were playing them. The whole thing is a great story. https://all-things-andy-gavin.com/2011/02/02/making-crash-bandicoot-part-1/ https://all-things-andy-gavin.com/2011/02/02/making-crash-ba...
- Nition 2y agoYes! And the best part of that feature: > 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.
- a_e_k 2y agoIIRC, 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 agoUnreal 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.
- DFHippie 2y agoTangentially related: a sort of whimsical ASCII art Doom using ray casting: https://github.com/TurkeyMcMac/ts3d 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.
- danparsonson 2y agoVery cool, and evocative of games from my own school days in the 80s. 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.
- tadfisher 2y agoMy condolences for your loss.
- Pseudomanifold 2y agoMy condolences for your loss. May his memory be a blessing.
- richrichie 2y agoI take pleasure in reminding my colleagues that ML is approximation theory and the concepts are 70-100 years old. All we have now is new hardware.
- bruce343434 2y agoRight, the theory around large language models was already worked out by then.
- richrichie 2y agoAnd what theory about LLM has been worked out in recent times?
- phkahler 2y agoMy preferred structure is the octtree over the BSP. or I guess for Doom it could have been a quad-tree. No surface splitting, and delete/re-insert for moving objects is possible. But I can claim to have known that until several years after Doom came along.
- drcode 2y agoSince lots of surfaces in Doom are diagonal, using that approach would have required an enormous amount of splitting of polygons, to fit the geometry to an orthogonal tree, probably increasing the amount of geometry an order of magnitude. The benefit of BSP is that it minimizes the amount of new geometry that needs to be created (even if it still requires some new geometry)
- HellDunkel 2y agoI dont understand. BSPs produce a lot more intersections.
- phkahler 2y agoNo, my octree doesn't split any geometry. Large primitives go in large nodes of the tree and can be in more than one node if needed. I was using it for interactive 3d ray tracing more than 20 years ago.
- keeptrying 2y agoI implemented a BSP based renderer too in around 1998- 2000. 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.
- Foobar8568 2y agoEverQuest was from 99, and first alpha 97 or 98. Supposedly among the first pre alpha game rendering https://m.youtube.com/watch?v=U0GyQCYVb2s https://m.youtube.com/watch?v=U0GyQCYVb2s EverQuest was truly a crazy game considering the era.
- weinzierl 2y agoFrom my memory: In the 90, if you had anything to do with computer graphics[1] you knew about binary space partitioning trees. 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.
- torusle 2y agoCorrect. 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.
- layer8 2y agoYep, that’s my recollection as well that it was common knowledge to the point of being a (the?) default approach for 3D rendering of any complexity.
- rurban 2y agoIn my university we worked on VR on cheap PC Hardware, and Amadeus, our Windows VR viewer for Hyper-G (the precursor of the WWW) used BSP trees for its scenes, long before DOOM. Implemented by my former boss. It was not considered genius level then, just good old compgeom. We had a lot of very good compgeom researchers back then in Graz.
- HellDunkel 2y agoIf this was true, why did so few games implement BSPs? I remember reading the graphics programming blackbook and it took me quite a while to understand the concept. My guess is that, of all space partitioning techniques BSPs where harder to do right and a lot less common.
- HellDunkel 2y agoIf this was true, why did so few games implement BSPs? I remember reading the graphics programming blackbook and it took me quite a while to understand the concept. My guess is that, of all space partitioning techniques BSPs where harder to do right and a lot less common.
- deleted 2y ago[deleted]
- hnthrowaway0328 2y agoReading the development history of the graphics engine of DOOM and especially QUAKE, it's a demonstration of John Carmack's perseverance. 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.
- dannyobrien 2y agoCarmack is definitely someone who was determined -- and quick. 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 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 http://www.ntk.net/1998/02/13/?l=114#l
- rasz 2y agoCarmack: - 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?