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.
One 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.
Or 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.
Is there a name for this phenomenon, where with limited resources humans get more creative? There are still some astonishing technologies that are ongoing today, but much more limited to the early era of computer science.
Fully agree. There's so many people who succumb to "not invented here" and then run blindly into solved issues.
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.
The disconnect between laypeople and research is often compounded by the stilted language, undefined terminology and related knowledge assumptions, underspecified details, and incomplete presentation of code or examples for independent reproducibility.
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. ;-)
My experience has been that the older CS papers (from the 60s, 70s, 80s) commonly have very clear, readable text, not weighed down with unnecessary "academic style" verbiage. It's the newer stuff that's painful to read.
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.
As a researcher I can say the opposite. In my field (cryptography) modern papers usually start by specifying formally exactly what the algorithm APIs look like; then they provide precise security definitions; then they describe algorithms; then they provide formal (if detailed) proofs of security. It’s long and detailed, but you get all the pieces you need for precision and you know where to find it.
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.
The constant fighting between Schmidhuber and LeCunn should be well known in here. But in my opinion, both of them have been involved with fantastic papers that are both painless to read and full of useful info:
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.
This is exactly what they do, even domain specific language is selected to precisely convey meaning and differentiate from incorrect but close interpretations.
> 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. ;-)
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.
Back in the day access to knowledge was quite hard, everyone first started with random file dumps from BBS exchanges, then followed by books. After that if you were of the right age and lived in the right place you might have had access to a university library with papers.
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.
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.
What's really remarkable is that so much of the last decade or so of research has been grounded in work done in the 1970s and 1980s, when computational boundaries were narrow enough that the work was often largely speculative or significantly restricted in application, so it's only now that we're really seeing that work bear fruit. It's a pleasure reading old comp-sci papers, and I wish more developers took the time.
> 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.
Abrash's Black Book was more in the style of Numerical Recipes than graphics gems, from what I recall. I also remember Nvidia putting out something annually around the late 2000s that was pretty good, can't remember the name though.
From the same era, folks may also enjoy the three volumes of collected articles from Jim Blinn's Corner. Some of it is a bit dated now, but plenty is still relevant.
Exactly. Research and it’s practical application is pretty common in computer graphics, and particularly cutting edge graphics engine development. There’s no need to dig around in academic papers unless you’re dealing with deep technical problems and off-the-shelf solutions are out of the question.
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.
Most of my career as an algorithm designer has been to boil problems down to their abstract essence, categorizing what kind of problem it is, reading papers to find a solution and implementing it.
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.
One of the things that drives me nuts about this industry is how ahistorical it is. The end result is that we keep reinventing the same things over and over especially around operating systems, databases, and languages.
At least in open source, I would claim that it's a result of volunteers doing the work for fun, which necessarily means they follow the dopamine: implementing someone else's work is not nearly as fun as figuring out a problem for yourself.
My theory is that open-source projects are a reflection of the language and all languages have the same flaw. Languages make it impossible to create simple objects with simple logic that can then evolve to more complex ability without modifying the simple object.
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 bucks the trend with its static duck typing; it's one of few languages where composition really works well. If your type defines + and * you can make matrices of them and multiply them together, then do linear algebra with them or format them as spreadsheets. Numpy, despite Python's duck typing, fails here because it's a thin wrapper over C, so the types are merely proxies and not extensible. Julia's compiled and heavily optimized, so it lives up to the promise. Also, unlike most static languages, the type system looks at the body of functions to infer what types they'll support - everything is maximally generic by default.
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.
This has nothing to do with open source. For GraphHopper I researched many papers regarding fast routing algorithms or advanced data structures etc ... and I'm pretty sure that this is true for other open source projects too.
It could be even the opposite: because many people can look into the code the code converges to the state of the art.
And the reading comprehension of CS people is near zero. You can give someone a paper with the solution, they will skim, not understand anything and then going back to reimplementing something poorly from first principles.
The industry is fundamentally conservative and un-imaginative. That being the case the M.O. is always a slightly tiny spin on an existing thing or a recreation of something that has been around forever but is currently slightly less popular then it once was.
Writing code is more fun than reading. Trying to solve problems is more fun than researching previous problems. It takes a special kind of discipline to get to the point where your first instinct is "Let me book out a few days and survey the literature" instead of "Let me use all of my IQ points to try to implement an ad hoc, informally-specified, bug-ridden, slow implementation of half of $ANYTHING".
I never had this impression. For me reading papers is way more fun and easier than developing a new solution in code and painstakingly work over all the bugs until they are gone, or worse, find bugs that you don't have solutions for. Or finding that it is too slow for your target machines.
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.
In truth, I'm much more this way myself than the median dev. Unfortunately it's not the greatest strategy for climbing the ranks and getting yourself to a top paying senior engineering gig to be a talented bug-fixer, and never a talented full program creator (or wheel-reinventor).
My favorite tech has a handful of patents expired in the past two years. But they are written in a way that doesn't expose the underlying algorithms, just the "steps" which seems to be a very keen well-designed patent informed by lawyers. Designed to the letter of the law. Mitsubisi Research Laboratories funded the work, it's clear they wanted to protect their investment. The text inside the patent is this absurd abstraction of the algorithm such that it could apply to anything.
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.
I blame agile and SaaS, neither of which are super tolerant of developers taking a few days just to read up on things. When you're both an owner of the company and/or just need to ship one good version of something, you get a little more space to do it right.
And this is the power of ChatGPT. Instead of reading a ton of literature, you can ask it for algorithms in literature that map to your problem.
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.
That's a very biased point of view. I use it for mathematical formulations for optimization problems and it gives me very good answers most of the time. The literature is very strong but hard to search via keywords. ChatGPT manages to digest the literature and does a good job pattern matching to the right problem.
We're talking about finding references or details of existing algorithms to solve a specific problem. What you are trying to do has nothing to do with that and it's a waste of time with an LLM.
For 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.
In 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.
> 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.
The rating was the minimum number of reads the motors in the CD drive of the Playstation would work for. Most likely, the rating was really low compared to what the drives could actually do.
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.
It might not have hah. Early version Playstation 1 consoles had notoriously bad CD drives that failed all the time. It had something to do with poor quality plastic gearing on the laser carrier or something.
An anecdote: I regularly played Crash Bandicoot with my family while young on a PlayStation, and our device always had disc drive issues. Pretty sure we even went through two PlayStations while playing that game lol. Still loved it!
Looking at the data sheet for a contemporary Sony CD-ROM mechanism
◆ 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)
Quake 1 and 2 did this as well. I wasted so much time with details that later got botched by the vertex compression. I think Quake 3 had vertex animation too, but they split the character at the hips so it could face away from the direction of travel.
There must have been some cleverness in representing this data in a compact way, esp as it would have competed with the 150 kB/sec CD-ROM bandwidth streaming other asset data?
Weirdly the excellent devblog that I got all this info from[1] mentions crazy compression algorithms for the vertex animation and for the level files, but not specifically for the occlusion data.
> 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.
There's a video series on YouTube where game devs talk about the challenges they faced while driving the game. Crash Bandicoot is covered in one episode, and there is another fantastic episode about Dead Space with the tentacle scene. Much recommended view.
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.
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.
I remember building Unreal maps as a teen. I didn't really understand bsp back then, and online discussions regarding mapping where full of cargo-culting weird methods to avoid "bsp holes". They were basically holes in the level geometry that sometimes even only appeared at specific camera angles, and not just in the distance, sometimes right in the corner of the room you're standing in. There were also two sliders in the dialog where you rebuilt the bsp, but I forgot what they were called and at least back then didn't understand what they did anyways, but changing them slightly could resolve the issue - only so you'd realize there's now a new hole somewhere else after 5 minutes.
> 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.
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.
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.
Sure, machines with virtual memory and caches were available in small numbers for a long time, but the vast majority of programming was done on PCs since the 1980s. The first Intel PC with a cache was the 486.
I learned LISP on systems like an IBM mainframe, DEC-10 with TOPS-10, the DEC VAX 11/780 with VMS, SUN 3 & 4, Symbolics 3600/3640, ... all these had large virtual memories, with the resulting feature that the speed of memory access varies widely between cached memory, main memory and virtual memory.
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...
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.
From 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.
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.
In 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.
If 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.
If 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.
> 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.
Can'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.
I'm not saying PCs were especially good for games, but that that was one of the main things they were bought and used for, at least at home. Again, we're talking 90s, not 80s. By the 1993, Windows had already won, and a home computer was almost always going to be an x86 running Windows or DOS. Saying they weren't meant for gaming is paramount to saying computer games weren't a thing in that period. We're way past Commodore being relevant by then.
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.
I think you're now shifting from your original claim that games were always a part of PC sales, which I disagree with, and a cursory review of market share supports my stance, to now focusing on 1993 and beyond. To that end I think the article is fair to point out that DOOM was programmed to run on computers that did not have the kind of hardware support for gaming that many other home computer systems had, and because of that techniques had to be carefully engineered to get such games to run on them.
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.
I think you read more into my initial point than I was trying to say -- there are two things:
- 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.
The turning point I recall being the "multimedia" era. Sounds cards, video cards, and CD drives took things to another level and leap frogged many consoles.
I think it is difficult to pinpoint the turning point, but I would say it was the launch of the 3dfx Voodoo in late 1996, and the release of GLQuake the following year. Up until that point you could argue that consoles were more powerful or adequate for gaming, but after that point there was no discussion.
It was already with games like Comanche (voxel graphics) and Wolfenstein 3D in 1992, which weren’t possible on the home computers of the time. Basically, it was with the advent of relatively affordable 486 PCs with VGA cards. Next came the CD-ROM based games like Rebel Assault in 1993. At that point it was literally “game over” for home computers.
I was thinking more about consoles. I remember reading some articles about the PSX and the N64 and how they would kill PC gaming, and then the Voodoo happened...
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...
I would estimate my parents to have bought a 486dx back in 91/92 in Europe, I remember we had https://www.computinghistory.org.uk/det/44379/Sound-Blaster-... with Indianapolis 500 and lemmings.
And I remember to have played wolf3d at a neighbor before we had that computer.
Atari/Amiga were better but I'd say it was indeed the turning point.
I suppose I assumed you were objecting to the article saying that PCs were not designed to run games. No one is disputing that games did run on PCs, but PCs did not have the kind of hardware nor the kind of architecture that computers at that time had which were designed for games.
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?
My parents bought PC in 1993. 95% of the usage by me were games. 100% of the reasons for upgrades for next decade and a half were only due to games.
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.
Absolutely if you bought a PC in 1993 it would have been suitable for gaming, but that was not the claim I replied to which claimed that PCs had always been suitable for gaming and that games were always a significant part of the PC market.
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.
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.
Not only sprites, but also scrolling backgrounds! There is no question that those machines were much more suited for 2D games, at least until the 486 could brute force them.
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!
That's not really true. The era of IBM designing computers was like the 8086 era. Clones were already dominant by the time the 286 came out, and Doom came out about half a year after the Pentium, or 586. That was very far into the era of "IBM compatible" machines being gaming machines.
There's more than a decade gap between "IBM compatible" clones taking over, and Doom coming out.
But even the clones, until the mid nineties, had at most a SuperVGA video card, which was little better than the annoying IBM VGA video card, which was certainly not designed for games.
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.
The computer my family bought about 1-2 years before Doom came out (and which I eventually played Doom on) had Soundblaster, stereo speakers, SVGA, a CD-ROM drive. I feel like folks are mixing up eras a bit here.
Pentium arrived at the same time as Doom, but wasn't something you could reliably target as your minimal requirements until Quake, and even then it was controversial a bit.
I 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.
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.
Even 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…
Very 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.
My 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.
Since 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)
No, 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.
Reading 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.
Carmack 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.
- 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?
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.