The link is a demonstration of Z-buffering. I don't know that I'd call that "the core algorithm of 3D", but it is pretty important for most real-time rendering.
The description doesn't give a lot of detail about the algorithm or its issues. The main problems to be aware of with Z-buffering are Z-fighting and the lack of support for transparency, neither of which are demonstrated. Here are a couple of links that go into a bit more detail:
I agree, there are many other pieces there. Perspective correct texture mapping is another big one, and above this all are shaders.
I wanted to visualize the part that is at the very base - the scanline Z-buffer rendering. The foundation of the pyramid of complications that is the mainline 3D rendering.
If you slow it to the minimum, you can see how it fills the triangles pixel per pixel. That, along with depth testing and the iteration over triangles, could possibly be called the "core algorithm"?
Funnily enough, filling triangles pixel per pixel is so outdated that it's already misleading. In reality, all GPUs work at least on 2x2 pixel "quads", because pixel shaders must be able to approximate derivatives. The approximation is done simply by taking the difference between neighbouring, simultaneously computed pixels.
Of course, in practice the rasterization happens in terms of larger tiles that contain many 2x2 pixel quads, and many quads are shaded in parallel, with the shader executing in lockstep for all pixels simultaneously. But that's an optimization that can be ignored for exposition, unlike the 2x2 quads.
There are three basic, independent parts of graphics: drawing shapes, lighting and light vs surface interaction.
Z-buffer is a very clever way to draw shapes. The only other way used practically is ray-tracing, where you cast rays through pixels on the screen and see where they intersect with the surface. Z-buffer reverses it - instead of casting rays towards surface we project set points on the surface (vertices) onto the screen. Even though it's asymptotically O(n) vs ray tracing's O(log n), practically it's very fast. The vast majority of CG, from movies to video games relies on this algorithm and I don't know what could be more important. All the stuff listed in other comments: texture mapping, texture mapping, shaders, perspective projection etc are specific algorithms, which don't deal with the shape drawing directly and not used everywhere.
Agreed, but I'd have to first put in a vote for not claiming one part is the mostest.
I like this post, among other things, it's a nice demonstration of the crazy amount of work your graphics card is doing to display a frame of your game. And it took some work and was put together with love.
But if you're going to call one single thing "the core algorithm of 3d", then yeah I'd have to second this one, perspective projection might be it - perspective is what makes 3d look 3d, you can do it without solid surfaces, and the math for perspective was developed long before computers with z-buffers existed.
I will totally grant that depth testing is the core algorithm of z-buffering, and iterating over triangles is the core algorithm of rendering triangle meshes. ;)
Maybe I'm biased here by spending an awful lot of time in AutoCAD, but I'd tend toward the wireframe parts as being all you need for 3D. All this "shading," "hidden surface removal," and "triangles" shenanigans is just sugar on top.
Though I'm having second thoughts about calling perspective projection the most basic part, since most of my work happens from an orthographic camera. Let's call that a perspective projection from a camera at infinity and it all works out.
At any rate, mapping points in world space to points in screen space and then drawing lines between them is a pretty clever system, and the new software and hardware we've added since then is so incredible that it's hard to comprehend sometimes.
You're absolutely right, I'd hoped that was my implication. ;)
Funny story though, speaking of renaissance art- I was doing research for my Master's thesis on computer graphics, and got direct access to several books from the 1700s that outlined the geometry of perspective projection as well as the geometry of shadows. (My thesis was about rendering shadows.) They were hand-written tomes, with very ornate covers and bindings and hand-drawn diagrams. The books weren't allowed to leave, but they had a special reading room for them, with archive-safe lead weights to hold the pages down so I wouldn't spread my damaging finger oils everywhere. I was taking some digital photos, and at one point I forgot about the lead weights and turned the page. It tore a little bit, and I was completely mortified!
Are you by any chance comfortable with sharing your thesis here (if you still have it around)? It sounds interesting. I would have asked via email if I had known where to send it!
This is old now, and modern techniques have mostly surpassed it, but the basic idea was to combine single-sample ray casting for finding occluders probabilistically with an image-plane flood-fill using analytic methods to render the shadows. It's a way to only pay for accurate shadow calculations where shadows actually exist, and skip the shadow calculations in all the un-occluded areas.
When GL-enabled Quake came out, it had a benchmark mode that would draw directly to the front buffer while you watched. There was also a pure software opengl32.dll you could pop in that would technically work correctly, but was very slow. Put those together on a Pentium 60 and you could watch Quake draw each triangle individually then watch it go back over each on and multiply the lightmap pass over them :)
I can't find one. Probably the best way to repro would be to run the Quake 1 shareware demo under DOSBOX. The command is ~ (open the console) then 'timerefresh'.
Hopefully, you can turn down the DOSBOX CPU budget low enough to see the software rasterizer in action.
This is amazing, thanks for sharing! Haven't really programmed much in 3D so this is a great resource to understand the concept behind a render engine.
Very good work. I enjoyed it and while viewing I just reminded myself the following:
By watching it at full speed, I am causing the CPU on my machine to do so much computational work in so short a time just so that I can enjoy the animation.
I wonder, how much computational power (measured in CPU/GPU cycles) is used all over the world for animations/games.
Computers have greatly changed our lives and our perspectives too.
If you're watching this on a phone, keep in mind that this is NOT how a mobile GPU would render this. Instead it would render the whole thing in screen tiles, completing a tile before going on to the next.
Tiled renderers or "chunkers" are common on mobile because the memory bandwidth is much less (1/10th to 1/5th) than desktop GPUs. The color/depth buffers are stored in on-chip memory which is much faster.
This isn't exposed to the programmer directly (Vulkan's multi pass API is related) but it has performance characteristics that we engine programmers need to be aware of.
It is common (universal?) on mobile GPUs because VRAM is slow. In some sense, you could think of it as manual management of the depth/color buffer cache (which all GPUs have).
This is not directly exposed in any common API, although Vulkan's renderpasses are intended to help write applications that behave efficiently on tiling renderers (as this kind of GPU is often called).
This is excellent! How much more can we learn by slowing down time and watching a process unfold? I think many in this thread are overly focusing on what is being presented, rather than the technique used to present it. The technique is what is being demonstrated.
The nice thing, is that this timescope comes with its own visualizer. Other processes have no such luck, it would be interesting to use machine learning to create abstract structured visualizations from the evolution of a process so that one needn't hand code them.
fun, but what am I learning from this that I don't already know, namely that 3d scenes in OpenGL/Vulkan/D3d are made up of triangles? Haven't I seen this already 1000 times when I select a "wireframe" option on every 3d scene that's ever been around for the past 30 years? Every casual gamer who's ever run unigine heaven knows this.
Am I being instructed here about the matrix math that creates the perspective illusion on a 2d plane? Not really. All I'm seeing is a bunch of triangles creating a scene. This is not going to instruct a beginner about the principles of the z-buffer in any way that I can see. That requires linear algebra. Unfortunately. No shortcut.
On the right side, you see new pixels being painted only if they are lighter than the pixels they are painted over. It shows that this is happening for every triangle, regardless of what order the triangles are iterated over.
This is a visualization. If you already know how it works, so what? Now you have a visualization of it that isn't confined to your brain.
GTA V: http://www.adriancourreges.com/blog/2015/11/02/gta-v-graphic...
Supreme Commander: http://www.adriancourreges.com/blog/2015/06/23/supreme-comma...
Deus Ex: http://www.adriancourreges.com/blog/2015/03/10/deus-ex-human...
HN Discussion about GTA V: https://news.ycombinator.com/item?id=10492876