What are the algorithms and the data structures for GUIs and input management?

Question

I'm studying how, given:

• an input from the user ( like a click of the mouse or the input from a key )
• a well defined data structure that represent the graphical layout inside a window ( a tree/graph like structure for now )

I could possibly create what is generally called as a "G/UI toolkit", which means that I should be able to create a responsive UI and a mapping between the input from the user and the functionality given to the UI itself.

I found absolutely no paper, no technical explanation, no articles, about both the data structure and the algorithms used to perform this kind of mapping, and I'm wondering if someone could help me with this.

I found some sparse reference to some tree-like data structure like kd-tree or quadtree that are used to subdivide the 2D space in the window and so when the signal will be fired, the coordinates generated by the signal, the click of a mouse, will be injected in the tree to find the corresponding widget to activate. This approach feels really old and I don't think it will scale that well.

I also found some reference to what is called the third generation of rasterizers and UIs which seems to be based on linear algebra/vectors and sounds really nice because it's highly scalable and simple to reason about, the problem is I can't see any implementation or algorithms or data structures.

Someone can point me in the right direction ?

Answer 1

I'll first restate your question, and then try to answer it. As I understand it, the question you are trying to answer is, "if I have a scene graph/widget tree, and I get an event, how can I figure out how to dispatch that event to the appropriate subnodes of the tree?"

The answer is that the data structures you have outlined are not sufficient by themselves to do the job; you need a bit more information.

The primitive events the OS produces tell you the positions of the mouse, and the scene graph gives you a logical decomposition of the structure of the GUI. Therefore, you need some additional data structures to translate between the widget tree and what it looks like geometrically.

The simplest case is when every widget is an axis-aligned rectangle. What you do then is:

1. Every widget node stores its position and shape.
2. In addition to the widget tree, you keep a separate doubly-linked list storing all of the clickable widgets in their z-order, so that the widget which is visually "on top" is at the head of the list.
3. You also keep track of the current mouse position (you have to do this anyway, because the OS only gives you relative position changes).

When an event occurs, what you do is:

1. When an event occurs you iterate through the z-order list, doing a simple hit test for the bounding box of each widget.
2. The first time the hit test succeeds, you know where the event occurred, and can do event dispatch.

With fancier graphics geometry (say with vector graphics), each widget will store a data structure representing the shape, and your hit test gets more complicated to match. The things to Google for:

• "collision detection" or "hit detection".
• "spatial indices" -- often these data structures are variants of quadtrees and the like. It really does work pretty well, even though the geometric data can be quite large, because user events are generally relatively infrequent.

Answer 2

A graphical user interface that contains more than a few tens of components would be very confusing for the user. This means that, whatever data structure is used, it doesn't have to scale to large instances. The user is unlikely to generate more than a couple of mouse-clicks per second, so whatever data structure is used, it doesn't even have to be processed very fast.

So it sounds like this is a problem that has already been solved as well as it needs to be solved and, in fact, that almost anything you could try would work on a modern computer.