Right. If you were building a scalable UI with a flat hierarchy of objects that do not move often (scrolling is OK, since scrolling is just an offset across the whole set of objects), then one solution is known as a quadtree. The idea here is that you recursively subdivide the scene into quadrants and try to balance it such that each quadrant has 5-10 objects. You spend a lot more time building the quadtree but it will significantly cut down on lookup time. On Mon, May 11, 2015 at 2:37 PM, Paul Davis <paul@xxxxxxxxxxxxxxxxxxxxx> wrote: > > > On Mon, May 11, 2015 at 5:30 PM, Jasper St. Pierre <jstpierre@xxxxxxxxxxx> > wrote: >> >> Computers are *fast*. It turns out that simply recursively walking >> down all children is fast enough for most cases. It's a complicated >> walk, but it's entirely doable. You can see the code for the walk >> here: >> >> https://git.gnome.org/browse/gtk+/tree/gdk/gdkwindow.c#n7247 > > > > notice the assumption that there's no Z-axis ordering. this is important and > simplifies the code/algorithm significantly. many modern applications occupy > what we might call "2-1/2D", where the 3rd dimension doesn't represent real > space, but the stacking of items does have some semantic significance. > > the tree walking algorithm also causes issues with any situations (which > admittedly are rare) where objects are highly non-rectangular. > >> >> >> More complex data structures, like a map of pixel to object, would >> take up too much memory, or require too much effort to suitably parse. >> The simple and brute force solution often works well, because you'll >> never have more than 100 visible children in the worst case, and 100 >> is not a big enough number to optimize for. > > > this number isn't realistic in the more general case where the "things" on > the screen are less heavy-weight than widgets. So certainly it works OK for > the GDK/GTK case, but in terms of a general mapping, optimizations do and > can matter. A typical somewhat complex session in Ardour that involves MIDI > and audio data might have in excess of 2k objects on the screen, and in > extreme cases, a factor of ten larger. > > unfortunately, the map of pixel to object is also too expensive in that > case. we don't have the right answer (yet), so we too walk the tree, but we > have to take layering (z-axis) into account. it easy to see this slow down > certain aspects of GUI performance. > > > -- Jasper _______________________________________________ gtk-list mailing list gtk-list@xxxxxxxxx https://mail.gnome.org/mailman/listinfo/gtk-list
