4 ms·

Interesting post. It feels quite closely analogous to the virtual-DOM diffing approaches that have dominated client-side JS frameworks lately. Is there any his

by mrec 9y ago

Interesting post. It feels quite closely analogous to the virtual-DOM diffing approaches that have dominated client-side JS frameworks lately. Is there any history of this technique being used in game engine design? Or is that more concerned about optimizing for the worst case (thou shalt not drop frames) than for the average case?

speps 9y ago
It's very common, even OpenGL had a way to do that way back in OpenGL 1.3[1][2]... I said it before with they "Off Main Thread" feature, it's been in game engines for decades now... Meh, what's not known is bound to be reinvented. [1] https://www.khronos.org/registry/OpenGL-Refpages/gl2.1/xhtml/glNewList.xml https://www.khronos.org/registry/OpenGL-Refpages/gl2.1/xhtml... [2] http://www.songho.ca/opengl/gl_displaylist.html http://www.songho.ca/opengl/gl_displaylist.html
- mrec 9y ago
  Not quite the same - I remember using GL display lists, but once you'd compiled one it was set in stone. There was no way to mostly reuse it but with a few changes here and there.
  - speps 9y ago
    It all depends on how your organize them really. If you follow the DOM hierarchy then you would only need to change one if the element has changed color for example, not position, scale, rotation as that would be done with the transform.
    - mrec 9y ago
      Aren't you assuming one display list per leaf element, which kind of negates the whole benefit of batching? If DOM node X hasn't rotated but one of its grandchildren has, a display list representing the whole of X will definitely need updating!
royjacobs 9y ago
Game engines have never had the approach of recalculating everything every frame. Instead, aggressively reusing data and only changing what you need is the default approach (as it should be if you want to squeeze the most out of a CPU/GPU). Things like command lists, vertex and index buffers and textures are retained from frame to frame as much as possible. Anything dynamic is usually handled on the GPU-side by taking a static input and applying simple (animated) parameters on top or, more commonly now, feeding back into the original buffer thereby updating it from the GPU calculations themselves. The fact that web development has finally caught up to this approach is certainly welcome, but this is nothing new at all.
- mrec 9y ago
  I think vbuffers/ibuffers/textures are a red herring here - the browser equivalent there would be re-requesting CSS files or images every frame, which nobody has ever suggested. And yes, reusing unmodified GPU command buffers is a very old technique. The interesting thing here seems to be the equivalent of selectively patching a command buffer without rebuilding the whole thing, and I wasn't aware of any game-engine precedent there. (Though I haven't really followed graphics closely for years.) > Anything dynamic is usually handled on the GPU-side That mostly only applies to cosmetic stuff, e.g. particle systems or bone-weighted skinning. For anything where the output has to feed back into CPU-based logic like collision physics or AI or even coarse frustum culling, it gets messier. I believe there are async readback APIs these days so that you don't have to stall the whole pipeline to get anything out, but it's still tricksy.
- pcwalton 9y ago
  This is something different from what game engines do. A game engine can typically just walk the scene graph, emitting draw calls as it encounters potentially visible objects. The equivalent approach on the Web would be walking the render tree/frame tree, issuing draw calls as it goes. This is indeed the traditional method that Gecko and WebKit used to use, but it has a lot of problems, which are why Blink and Gecko use display lists: 1. The CSS 2.1 Appendix E painting order is complex: it's not enough to traverse the tree in breadth-first or depth-first order. You could get around that by traversing the tree multiple times, as Blink and WebKit do, but that gets complex. It's a lot more straightforward, not to mention cache friendlier, to build display items into a list and then later sort them into the proper CSS stacking order. This is actually similar to what game engines do for transparent objects (assuming they actually care about rendering them properly and aren't using any fancy OIT techniques). 2. For security reasons, these days you don't want direct GPU access in the same process as JavaScript. Display lists enable an elegant solution to this, as they can be transmitted over IPC to a trusted process. 3. Display lists can be rendered in a separate thread from the layout and/or JavaScript execution, enabling better use of concurrency. 4. Unlike a typical game, which has the luxury of being able to build up vertex and index buffers beforehand and can cache them on the individual nodes in the scene graph, on the Web each individual display item only has a tiny amount of GPU data. Slow rendering on the Web is often the result of "death by a thousand cuts", where the GPU is swamped in draw calls from lots of unrelated items. The only scalable solution to this problem is to batch across display items, using knowledge of the entire scene to construct VBOs and IBOs. This is only possible if the renderer has a global view of the entire scene, and the display list is a natural way to achieve that. I certainly think that Web browsers can learn a lot from game engines (and WebRender is designed to do just that). But display lists are one of those cases in which the problem space is just different: trying to do exactly what a game engine does doesn't work well.
westmeal 9y ago
It sounds kind of like culling in game engines. Is it truly similar though? I'm not familiar how you can quickly test for an object being in view without doing an O(n) operation first and then retaining the list visible if the scene didn't change. Is there any way to do so?
- royjacobs 9y ago
  Look at spatial partitioning schemes like BSP, octrees, etc. In fact, look at another trending story[1] about the Unreal editor because it discusses this exact concept (except this was being done in the early to mid 90s). [1] https://www.gamasutra.com/blogs/DavidLightbown/20180109/309414/Classic_Tools_Retrospective_Tim_Sweeney_on_the_first_version_of_the_Unreal_Editor.php https://www.gamasutra.com/blogs/DavidLightbown/20180109/3094...
- sp332 9y ago
  Firefox has been changing the rendering system pretty dramatically lately. https://hacks.mozilla.org/2017/10/the-whole-web-at-maximum-fps-how-webrender-gets-rid-of-jank/ https://hacks.mozilla.org/2017/10/the-whole-web-at-maximum-f... They describe the direction they're going as: "make it more like a 3D game engine."
muizelaar 9y ago
The current approach without retained display lists is actually closer to the virtual-DOM diffing approach. i.e. Without retained display lists: - build up a display list of the entire scene. - diff this display list with the previous one to see what areas have changed. - paint the areas that have changed With retained display lists: - keep a list of elements that have changed - build a display list for part of the screen that have changed elements in them - merge the new partial display list into the old one - diff this display list with the previous to see what areas have changed - paint the areas that have changed

by mrec 9y ago

speps 9y ago

It's very common, even OpenGL had a way to do that way back in OpenGL 1.3[1][2]... I said it before with they "Off Main Thread" feature, it's been in game engines for decades now... Meh, what's not known is bound to be reinvented. [1] https://www.khronos.org/registry/OpenGL-Refpages/gl2.1/xhtml/glNewList.xml https://www.khronos.org/registry/OpenGL-Refpages/gl2.1/xhtml... [2] http://www.songho.ca/opengl/gl_displaylist.html http://www.songho.ca/opengl/gl_displaylist.html

mrec 9y ago
Not quite the same - I remember using GL display lists, but once you'd compiled one it was set in stone. There was no way to mostly reuse it but with a few changes here and there.
- speps 9y ago
  It all depends on how your organize them really. If you follow the DOM hierarchy then you would only need to change one if the element has changed color for example, not position, scale, rotation as that would be done with the transform.
  - mrec 9y ago
    Aren't you assuming one display list per leaf element, which kind of negates the whole benefit of batching? If DOM node X hasn't rotated but one of its grandchildren has, a display list representing the whole of X will definitely need updating!

royjacobs 9y ago

Game engines have never had the approach of recalculating everything every frame. Instead, aggressively reusing data and only changing what you need is the default approach (as it should be if you want to squeeze the most out of a CPU/GPU). Things like command lists, vertex and index buffers and textures are retained from frame to frame as much as possible. Anything dynamic is usually handled on the GPU-side by taking a static input and applying simple (animated) parameters on top or, more commonly now, feeding back into the original buffer thereby updating it from the GPU calculations themselves. The fact that web development has finally caught up to this approach is certainly welcome, but this is nothing new at all.

mrec 9y ago
I think vbuffers/ibuffers/textures are a red herring here - the browser equivalent there would be re-requesting CSS files or images every frame, which nobody has ever suggested. And yes, reusing unmodified GPU command buffers is a very old technique. The interesting thing here seems to be the equivalent of selectively patching a command buffer without rebuilding the whole thing, and I wasn't aware of any game-engine precedent there. (Though I haven't really followed graphics closely for years.) > Anything dynamic is usually handled on the GPU-side That mostly only applies to cosmetic stuff, e.g. particle systems or bone-weighted skinning. For anything where the output has to feed back into CPU-based logic like collision physics or AI or even coarse frustum culling, it gets messier. I believe there are async readback APIs these days so that you don't have to stall the whole pipeline to get anything out, but it's still tricksy.
pcwalton 9y ago
This is something different from what game engines do. A game engine can typically just walk the scene graph, emitting draw calls as it encounters potentially visible objects. The equivalent approach on the Web would be walking the render tree/frame tree, issuing draw calls as it goes. This is indeed the traditional method that Gecko and WebKit used to use, but it has a lot of problems, which are why Blink and Gecko use display lists: 1. The CSS 2.1 Appendix E painting order is complex: it's not enough to traverse the tree in breadth-first or depth-first order. You could get around that by traversing the tree multiple times, as Blink and WebKit do, but that gets complex. It's a lot more straightforward, not to mention cache friendlier, to build display items into a list and then later sort them into the proper CSS stacking order. This is actually similar to what game engines do for transparent objects (assuming they actually care about rendering them properly and aren't using any fancy OIT techniques). 2. For security reasons, these days you don't want direct GPU access in the same process as JavaScript. Display lists enable an elegant solution to this, as they can be transmitted over IPC to a trusted process. 3. Display lists can be rendered in a separate thread from the layout and/or JavaScript execution, enabling better use of concurrency. 4. Unlike a typical game, which has the luxury of being able to build up vertex and index buffers beforehand and can cache them on the individual nodes in the scene graph, on the Web each individual display item only has a tiny amount of GPU data. Slow rendering on the Web is often the result of "death by a thousand cuts", where the GPU is swamped in draw calls from lots of unrelated items. The only scalable solution to this problem is to batch across display items, using knowledge of the entire scene to construct VBOs and IBOs. This is only possible if the renderer has a global view of the entire scene, and the display list is a natural way to achieve that. I certainly think that Web browsers can learn a lot from game engines (and WebRender is designed to do just that). But display lists are one of those cases in which the problem space is just different: trying to do exactly what a game engine does doesn't work well.

westmeal 9y ago

It sounds kind of like culling in game engines. Is it truly similar though? I'm not familiar how you can quickly test for an object being in view without doing an O(n) operation first and then retaining the list visible if the scene didn't change. Is there any way to do so?

royjacobs 9y ago
Look at spatial partitioning schemes like BSP, octrees, etc. In fact, look at another trending story[1] about the Unreal editor because it discusses this exact concept (except this was being done in the early to mid 90s). [1] https://www.gamasutra.com/blogs/DavidLightbown/20180109/309414/Classic_Tools_Retrospective_Tim_Sweeney_on_the_first_version_of_the_Unreal_Editor.php https://www.gamasutra.com/blogs/DavidLightbown/20180109/3094...
sp332 9y ago
Firefox has been changing the rendering system pretty dramatically lately. https://hacks.mozilla.org/2017/10/the-whole-web-at-maximum-fps-how-webrender-gets-rid-of-jank/ https://hacks.mozilla.org/2017/10/the-whole-web-at-maximum-f... They describe the direction they're going as: "make it more like a 3D game engine."

muizelaar 9y ago

The current approach without retained display lists is actually closer to the virtual-DOM diffing approach. i.e. Without retained display lists: - build up a display list of the entire scene. - diff this display list with the previous one to see what areas have changed. - paint the areas that have changed With retained display lists: - keep a list of elements that have changed - build a display list for part of the screen that have changed elements in them - merge the new partial display list into the old one - diff this display list with the previous to see what areas have changed - paint the areas that have changed