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?
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.
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.
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.
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.
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.
Display lists actually remind me a lot of sprite batching, where game engines also build up VBOs based on the whole scene. Probably not as common in 3D (maybe particles?) but standard practice for 2D.
And for what it's worth, the last game engine I worked on used display lists for opaque objects as well as transparent- that let us sort by material (to reduce state changes) and approximate depth (to reduce overdraw). We just regenerated and sorted this list every frame from scratch.
Game content is not built in a vacuum, and is built by a team of people who were trained on the engine and have a large bag of tools to help improve performance. You can't just plug a random scene into any game engine and expect it to perform beautifully. There is good tech in game engines, but a lot of it comes down to an incredible amount of manual labor because you can target the internals of the engine. The web has to handle any random content thrown at it.
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?
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).
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
When we do this, the submission timestamp on the front page becomes the time it was put in the queue, approximately. That's why it looked like a later post than yours. I don't like doing this, but not doing it invariably triggers a barrage of questions and complaints ("what is this 2-day old story with 3 upvotes doing on the front page"). You can always see the original timestamp by looking at the submission in the user history (https://news.ycombinator.com/submitted?id=agnivade) or the site history (https://news.ycombinator.com/from?site=mozillagfx.wordpress....).
That's not so easy, because in cases where we don't notice the story and re-up it, reposts are key to giving good articles multiple chances at attention.
That second graph and discussion is really frustrating. The claim is that latencies from 38-50 get shifted down into other buckets, and the the 51+ bucket increases is an artifact of the lower aggregate numbers.
Maybe the data supports this, but there's no way to know looking at the graph. The histogram should be scaled against total counts rather than the subcounts (just zoomed in appropriately for the dataset). As shown, its bad statistics at best, and disingenuous lies at worst
So I'll be that person: if it can be enabled in the 58 beta, does that mean it's on track for being included in that or another specific release? Or is it not planned yet?
If it can be enabled in 58 beta, you'll likely be able to enable it in 58 release. But there may not be any stability guarantees on it working correctly.
I believe the target is 59, though it might stretch to 60.
26 comments
[ 2.9 ms ] story [ 57.7 ms ] threadIs 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?
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... [2] http://www.songho.ca/opengl/gl_displaylist.html
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!
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.
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.
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.
And for what it's worth, the last game engine I worked on used display lists for opaque objects as well as transparent- that let us sort by material (to reduce state changes) and approximate depth (to reduce overdraw). We just regenerated and sorted this list every frame from scratch.
Game content is not built in a vacuum, and is built by a team of people who were trained on the engine and have a large bag of tools to help improve performance. You can't just plug a random scene into any game engine and expect it to perform beautifully. There is good tech in game engines, but a lot of it comes down to an incredible amount of manual labor because you can target the internals of the engine. The web has to handle any random content thrown at it.
[1] https://www.gamasutra.com/blogs/DavidLightbown/20180109/3094...
Without retained display lists:
With retained display lists:When we do this, the submission timestamp on the front page becomes the time it was put in the queue, approximately. That's why it looked like a later post than yours. I don't like doing this, but not doing it invariably triggers a barrage of questions and complaints ("what is this 2-day old story with 3 upvotes doing on the front page"). You can always see the original timestamp by looking at the submission in the user history (https://news.ycombinator.com/submitted?id=agnivade) or the site history (https://news.ycombinator.com/from?site=mozillagfx.wordpress....).
More here if anyone cares: https://hn.algolia.com/?sort=byDate&dateRange=all&type=comme...
Maybe the data supports this, but there's no way to know looking at the graph. The histogram should be scaled against total counts rather than the subcounts (just zoomed in appropriately for the dataset). As shown, its bad statistics at best, and disingenuous lies at worst
I believe the target is 59, though it might stretch to 60.