Quake's PVS: A hidden gem of rendering optimization
ฝัง
- เผยแพร่เมื่อ 7 มิ.ย. 2024
- A look at how Quake uses portal graphs to pre-calculate visibility information.
Support: www.buymeacoffee.com/mattsram...
Mastodon: mastodon.cloud/@mattsramblings/
00:00 Intro
00:43 Portal graphs
01:57 Visibility in a linear graph
05:15 Recursive trace
Music Credits:
-----------------------
Heavy Interlude by Kevin MacLeod is licensed under a Creative Commons Attribution 4.0 licence. creativecommons.org/licenses/...
Source: incompetech.com/music/royalty-...
Artist: incompetech.com/
-----------------------
Pioneers by Audionautix is licensed under a Creative Commons Attribution 4.0 licence. creativecommons.org/licenses/...
Artist: audionautix.com/
----------------------- - เกม
As I mention in the video, there's a load of algorithmic optimizations on top of what I've described in the video, but wanted to explain the core concept without digging too deep.
It's a great idea to start with the fundamental idea, I'd like to see a video explaining the specific tricks they used as well.
Please explain deeper the difference between all bsp files of Quake trilogy.
Edited: AFAIK, Quake 2 uses detail brushes and areaportals and Quake 3 adds B-spline surfaces in map format. These things were used to beat the limits of Q1BSP culling system.
BSP Tree (Binary Space Partitioning) is actually what Quake used.
@@orangehatmusic225 it uses both. Pvs is calculated based on a bsp
@@golarac6433 Therefore it's called BSP.. not PVS. The visible set is calculated based on a binary space partioning tree. This was actually stolen from the game Starsiege: Tribes.
This video was 6 minutes, 47 seconds long. It explained things clearly, simply, with an understandable VO and amazingly clear diagrams, and explained only what it needed to explain. More TH-camrs who explain things need to take lessons from you.
I used to make quake maps in my free time back in the day. I was always curious about what the computer was doing behind the scenes of each of those log lines. This filled in those gaps perfectly!
And man, John Carmack's had one heck of a groundbreaking career, hasn't he?!
same here! this video gave me flashbacks to noclipping around my maps trying to figure out where the leaks were
His BSP system was so good that CoD and Source still use it to this day!
Hahaha, yeah, so many memories. I once spent months to make a quake level and just when I was about to release it I touched the back of my beige computer to plug in my headphones and fricking STATIC ELECTRICITY fried my hard drive, unbelievable. But turned out better when I had to remake it so blessing in disguise I guess :) I overlooked aligning ONE texture face in WC. It still haunts me.
oooh and when radiosity lighting was introduced for q2, took forever to compile. Hard to believe unreal has real-time dynamic realistic lighting these days, funnily enough the lumen/nanite algorithm with billions of subdivided triangles reminds me a little bit of bsp trees
@@SomeKindOfMattias even with a 12600K at 5ghz it takes me several minutes to compile a Q3 map. I can only imagine what it was like back in the day. What i think is crazy is that CryEngine can just do everything in real time and you can jump from the editor straight into the game with no compile. Unity can too now. Idk about Unreal, probably, i don't use it because Epic can piss off for not finishing UT4.
@@eclipsegst9419 Each unreal code file takes about 400ms to compile
Carmack is a god
Give Michael Abrash some love too- He helped Carmack solve these rendering and optimization challenges
@@curcumin417 I believe Carmack also said that most of quake's assembly was Abrash's right?
@@archthearchvile Yes exactly, especially for the Pentium CPU architecture which was new at the time. Many of these challenges were documented by Abrash in Dr. Dobb's graphics programming Journal.
@@curcumin417 Cool, I wish Abrash got more love too TBH.
I feel like that's a little over stating, sure these are neat algorithms but it's not like only carmac had been able to come up with them
I remember using BSP compilers when making maps for HL1 engine. One would build BSP data, the other one would calculate the lighting, and so on. You could run the unfinished map without lighting calculated in order to test the gameplay faster.
Now this also works with csgo
I remember doing that as well, using the hammer editor back in the kill box days. The source engines still pretty much uses the exact same method as far as I'm aware
I remember that calculating lighting on my PC took hours because I was short on RAM. I had to upgrade from 96 to 128MB to solve this :D
this is true for any Quake 2 and 3 engine game as well
@@JeanBaptisteEmanuelZorg And Unreal Engine 1.5 was much faster. It took only a few seconds to compile the map. After that you could play it with lightning in UT99.
Your visualizations are so good!
@Matt's Ramblings Indeed, been wondering: how do you make them? Modified quake engine or editor?
@@yiannos3009 This must be a custom renderer or at least a heavily instrumented one. I think you would be right to assume there is some Quake map compiler code in there. The recursive trace animation is basically impossible to input by hand.
Quake 1 really did change everything with 3D. So insane how deep every part of the development of it was.
I grew up on PVS rendering.... so when I jump into a game today like Halo Infinite or Ghost Recon: Breakpoint, with open worlds seamlessly merged with super detailed indoor environments, I am still blown away. Not even difficult to do anymore but I remember when going from outdoors to indoors with zero loading was a HUGE deal.
I agree. Fallout 3 did still use separated outdoor and indoor maps with a loading screen. And this was in 2008.
Great explanation of the vis system, love the example animations.
This approach had a lasting legacy too; the source engine uses the same technique.
VVis and leaks were a nightmare ^^
For Stranger's Wrath (XBoxOrig game), we had a dynamic portal system that would clip portals at runtime.
Since we were built for hardware we could allow more overdraw than Quake could, but it was still important to reduce it. We also used the portals for streaming.
Source is a tower of duct tape going all the way back to actual Quake 1 code, from what I've heard. GoldSrc extended Quake, Source extended GoldSrc, Source2 extended Source...
Precomputed PVS only had a lasting legacy in engines which derived from the Quake source code; as far as I know (and I should know), nobody else did this. For example, Descent (pre-Quake) and Thief/System Shock 2 (post-Quake) both used dynamic portal traversal rather than precomputing a PVS.
@@ugu8963 And in Unreal Engine leaks were impossible because you carved your 3d world in a 3d cube.
I watched John Carmack's talk about VR and at some point he was analyzing the latency inside the motherboard circuits themselves, I think he was counting the micro, or probably even nano, seconds he needed to get his VR hardware work as perfectly and close to reality as possible. The man is simply .... a legend.
I grew up making levels for the HL1 and Source engines, which had basically the same PVS and culling calculations, and you really had to design your level around how the engine worked. Now I work in triple-A game development, and making a level that runs well means designing whatever you want up front, and then ripping out most of the foliage just before you ship the beta.
This series is a gem. Complex topics condensed down into very concise, well animated, easy to understand bits. Love it!
I remember buying the Orchid Righteous 3D (the first 3DFx Voodoo card) and running early beta versions of GLQuake. This supports transparent water but since the previs data didn't include the geometry on the other side of the surface you had to disable the feature making the framerate tank. Then someone made a tool that could recalculate the previs for transparent water and patch the levels. This was something you started before going to bed and ran over night 😅
Absolutely love these videos about rendering and collision. I have had so many questions about these things, and your visualizations always help so much.
Such a good series you have here on Quake! Love it, well done.
Fascinating! This must have been the 'VIS' stage when I complied my maps in WorldCraft all those years ago. Happy memories of spending hours building deathmatch levels.
Good video, but Quake's BSP data contains n-sided convex polygons, not explicit triangles.
Hardware-accelerated renderers converts those n-sided polygons into triangles, but the software renderer does render n-sided polygons directly with no conversion.
Good point 👍
As someone who worked with older engines (including those from the original Call of Duty) I absolutely hated having to design around portals and making sure everything was working properly. On large maps things got really complex and annoying to troubleshoot. Thank God modern engines just cull everything automatically. I mean it's great all that tech was there, but I'm definitely glad it's over, no artists liked working with it.
Every other explanation for BSP and visleaves never made any sense to me, but I finally found a video that explains it well. This is awesome, thanks!
Great video. Always look forward to your quake videos. From what I remember, the PVS data structure was compressed and stored directly on the BSP nodes.
Also, (again, If I recall correctly) Quake drew on the screen via pixel strip lists. Are you planning a video on that part too?
It is compressed, but not stored directly in a BSP node. Each node contains an offset to a big PVS array, and that offset points to the start of the compressed visibility list for the BSP node in particular.
Your content is simply brilliant. It exemplifies just how genius John Carmack and the rest of the very small development team were. Thank you for all of the hard work and very long hours you put into making this content for a seemingly very small audience.
So good content, keep up the great work
These last two videos on the algorithms in Quake are fantastic. Looking forward to more in-depth explanations of algorithmic innovations and tricks-of-the-trade presented in such a beautiful manner, on Quake or other games/software.
Omg getting to see the vis graph as a texture was so cool!
I know the renderer in the Dark engine (Thief, System Shock 2) wasn't implemented exactly like Quake's, but both referenced the same papers about BSPs and portals so I guess the theory is the same. When I was a kid I pored through page after page of words and math, but I think I only ever understood maybe 8% of it. I wish you made these videos 20 years ago because everything just finally clicked! What do use to make your animations? I'd love to play around with these data structures and algorithms, I know about Red Blob Games but it would be so cool to extend it to 3d game concepts.
I love your videos so much, genuinely my favorite channel on all of youtube.
Beautiful video. I know a little about PVS through Seth Teller's early work involving line stabbing methods and was wondering how Quake's conservative approach differs in its execution. Ultimately, I would probably go with Quake's implementation as it seems (at least on paper) easier to implement. One day I'll finally get around to writing a BSP-renderer :).
Overall, I believe surface determination algorithms are a lost art form forgotten due to the rapid advances in hardware accelerated graphics. Quake did so many things correctly at the right time and is truly a wonder for nerds like us to peek into :).
I knew that the Quake engine didn’t support deformable geometry, now I understand why (lots of pre-processing) - thank you 😀
Now to watch it again so I can understand what’s actually being pre-processed…
I don't think I've ever subbed to a channel faster. This video is clear, concise, and the visualization is extremely good.
Congrats in advance on 10k, looking forward to that number blowing up!
A wonderful video mate! Just pure awesomeness.
Amazing visualisation of a complex subject. Thanks for taking the time!
I was promised rambling but instead got a skilfully illustrated explanation of a useful concept.
Culling visibility is an important aspect of rending back in this era. It's fascinating to study how different games achieved it. You can look at something like Mario 64 and find that they use doors and other gates to control what's visible in a very simple fashion, but first person games require for more in-depth control because the player has so much freedom to look around.
Unreal used a series of portals set up within the map itself to determine what visuals needed to be culled; it calculated more visibility at run-time but it reduced the complexity of those calculations to make that possible.
The quality bar on these videos is SO high, well done!
It's fascinating to learn about prerequisites of modern optimization techniques. Today we Unity 3D devs take so much as given, like baking whole level occlusion culling at the press of a button.
oh man, I've been looking for videos on the 3d rendering process of the original Quake, and you are first one with actually useful information in it that I have finally found! Thank you.
ace! i always understood the rough way this worked from michael abrash' quake postmortem clip but this is so much more understandable actually seeing it happen. shout out to the q1sp mapping community, going stronger than ever in 2023
Excellent video. There are so many ingenious solutions implemented in videogames!
This was mind-blowing, thank you so much! I will have to rewatch this five times to get it even a bit but totally worth it! Makes me remember Michael Abrash's Dr dobb's journal and his zen of assembly like optimizations. Thank you from the bottom of my heart ❤️ for making this... And that you did it so professionally... Wooow ❤
The algo has blessed me today
very well done, nothing seemed confusing with all the good illustrations
Back in the day you had to re-vis all the maps to allow transparent water with QLQuake. That's how I learned there was such a system. I just had no clue how it worked.
So glad to see this video after the last one! A great explanation of the concept - excellent work!
love your vids, some bits went over my head (even from the last vid w/ the BSP), but I'm sure I'll get it eventually :D
Wow, great video!
TH-cam recommended this to me yesterday, and I ended up watching every single video on your channel. Great stuff. I'm looking forward to seeing more from you.
Priceless! Big thanks for that visuals and explanation!
Beautifully simple explanation. Thank you.
Damn, what a gem of a video.
Totally a motivation for learning graph theory.
Great vid. I recently have been reverse engineering and re-implementing how Halo 1's Blam engine implements their BSP data structures and rendering optimizations, so this vid reaching my feed is very on the nose.
such a small content creator giving out this level of quality content god damn, seriously: good job. I got interested in quake a few weeks ago and im now trying to learn some of the internals and this is just very cool to see
If you haven't subscribed to dumptruck_ds, you should.
@@charlieking7600 thanks for the recommendation, i can see some really interesting videos!
Severely underrated video
Game optimization is such a cool area. Loved this video!
Very interesting and I understood it all, nicely shown and explained. Something I never really thought about.
Gold standard teaching.....
well done....
This was interesting to see the logic of bsps as I did many quake2 maps back in the day but much wasn't understood. I recall some brush entity thing was available to put within door geometry to prevent whatever on the opposite side of the door from loading before the door is opened, though I rarely used them either because my maps weren't geometrically complex, weren't all that large, or more likely cuz I was being lazy...
Please make more videos like this asap! I love watching this kind of stuff
The modern term for this would be occlusion culling. Very cool to see how this common game engine feature came to be.
Wow this brings back fond memories ❤
nice to see, this was known before, but with modern styles of visualization and presentation of material, it's cool🤗
A nostalgia trip for someone who made maps back then.
These visuals are incredible for explaining such a complicated subject
I knew it was just never described properly rather than just me not having a clue htf bsp trees worked. thnx, very informative.
The obvious effort put into these videos is clear
I would like to see an explanation of the function that implements the visibility test. As it was in the video with the line segment tracing.
Your channel is the first one that I subscribed to after seeing one vid. It's that good. It's super satisfying to see these algorithms being animated in 3D.
youtube recommended this to me, excellent video! very interesting subject and great visuals
excellent rundown
Ingenious!
That's extremely well explained, thank you!
That was facinating. Thanks.
I've learned about this in school but you summarize it very well. I feel like this would be enough information to start making it on your own given you have the programming know how
This helps to understand the Source engine since the concepts are very similar.
Cool video, explained well, thanks! :D
Great explanation, thanks for the video.
That's some good ass visuals man, good job!
I was always curious to learn about the basics of visibility graph computation, and how to perform it reasonably fast. This is excellent for both programmers and non-technical people. Granted, if they watch enough of your videos, they may become technical as well ;)
Really good video. Thanks! I've learnt a lot!!
I see Quake video, I'm happy
Great work!
Beautiful video!
Underrated content as usual , Thank you!
Great deep dive and visualization
Just a beautyfull work of art
love your vids a lot
I watch this video every day with my morning coffee.
Incredible visualizations
I used to work on Microsoft's Flight Simulators back then. It used BSPs and I always wondered how Quake did this.
Quake was something else. Right in the era where you had to check if you could look up and down in a game
Great Video!!!
thanks matt
Wow, this is just insane.
I always thought that all the techniques were invented later.
great video
This video is a pearl. Awesome. Although I didn't get some of the concepts, I gotta say the animations are perfect and explanation very clear. Question: how did the compiler find a good portal? And how did carmack arrive to all those ideas?
OMG back in the early 2000's I used QOOLE to make maps for Quake II and my maps suffered from this oversurfacing/overdrawing and eventually just got frustrated and gave up on the hobby entirely. I never figured out how to remove the extra colliding poligons and to this day I don't know if QOOLE is even capable of doing so. If I would come back to map making I'd probably be using TrenchBroom instead. 😑
I believe the new Quake 2021 re-release engine ignores VIS data for rendering purposes, and just throws everything at the GPU, which is often faster than traversing the PVS I guess!
I worked with ID tech in 2000 and portals were cool feature to reduce visible polys below max engine limit. How surprised I was in 2010 working with a new engine without portals need anymore. New games can learn so much from old optimization technique.
The more polygons a world has, the less BSP trees make sense. Imagine a single room with 3D sculptures or where the sculptures are carved into the walls. Or a rock face made up of millions of triangles. The overhead for BSP trees would be so great that they no longer make sense. That's why you are taking another approach today and the much faster hardware does allow that.
Very interesting!
Great video.
This is awesome
very interesting video. Right now I'm trying to make a software renderer similar to build/idtech1. The idea I had for this kind of problem is to have invisible walls that would act as portals. After rendering the current sector, if any of the pixels of the portal passes the depth test, then the next sector is considered to be visible and gets drawn. This process continues recursively until no more visible portals remain.
Interesting, do you do depth-first or breadth-first portal traversal?
I also am working on a "2.5D"/3D doom-style engine, but I have heavy hardware constraints, and depth-first traversal just bogs down too much, so I'll be working on a pvs solution soon.
It brings tears to my eyes when I see optimisation of modern 150Gb games😭
90s-early 2000s were the golden age of video games