6 ms·

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 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: https://en.wikipedia.org/wiki/Z-fighting https://en.wikipedia.org/wiki/Z-fighting https://www.sjbaker.org/steve/omniv/alpha_sorting.html https://www.sjbaker.org/steve/omniv/alpha_sorting.html

svantana 10y ago
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"?
- wlesieutre 10y ago
  My vote would go to perspective projection
  - dahart 10y ago
    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. ;)
    - santaclaus 10y ago
      > the math for perspective was developed long before computers with z-buffers existed I would say long before computers existed. Perspective projection was the key algorithm of renaissance art!
      - dahart 10y ago
        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! Sorry, history!
        megalodon 10y ago
        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!
        dahart 10y ago
        Sure! I'm not sure the complete thesis with the renaissance geometry images is online anywhere, but it's mostly an expanded version of this paper: http://www.graphics.cornell.edu/pubs/1999/HDG99.html http://www.graphics.cornell.edu/pubs/1999/HDG99.html 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.
- nhaehnle 10y ago
  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.
- pandaman 10y ago
  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.
dang 10y ago
> I don't know that I'd call that "the core algorithm of 3D" Ok, we replaced that phrase with "Z-buffering" above.
Artlav 10y ago
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.
rl3 10y ago
Since you mentioned Z-fighting, Three.js has an excellent logarithmic depth buffer example: http://threejs.org/examples/webgl_camera_logarithmicdepthbuffer.html http://threejs.org/examples/webgl_camera_logarithmicdepthbuf...

svantana 10y ago

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"?

wlesieutre 10y ago
My vote would go to perspective projection
- dahart 10y ago
  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. ;)
  - santaclaus 10y ago
    > the math for perspective was developed long before computers with z-buffers existed I would say long before computers existed. Perspective projection was the key algorithm of renaissance art!
    - dahart 10y ago
      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! Sorry, history!
      - megalodon 10y ago
        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!
        dahart 10y ago
        Sure! I'm not sure the complete thesis with the renaissance geometry images is online anywhere, but it's mostly an expanded version of this paper: http://www.graphics.cornell.edu/pubs/1999/HDG99.html http://www.graphics.cornell.edu/pubs/1999/HDG99.html 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.
nhaehnle 10y ago
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.
pandaman 10y ago
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.

dang 10y ago

> I don't know that I'd call that "the core algorithm of 3D" Ok, we replaced that phrase with "Z-buffering" above.

Artlav 10y ago

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.

rl3 10y ago

Since you mentioned Z-fighting, Three.js has an excellent logarithmic depth buffer example: http://threejs.org/examples/webgl_camera_logarithmicdepthbuffer.html http://threejs.org/examples/webgl_camera_logarithmicdepthbuf...