What are common ways that GUIs detect which element is being clicked, in a low level?

Question

I've been trying to search for this problem all around, but all I find is related to a high level thing, like "how to know which HTML is being clicked". That's not the kind of thing I'm looking for. I'm looking for a more low level detail.

Let's suppose someone is trying to write a GUI library for a given system. Also, let's say this programmer has already managed to display graphics, text, buttons, etc on screen. Now they want to implement ways for the user to interact with that interface, more specifically, using mouse clicks (or maybe touch input).

The system on which their GUI engine runs is capable of telling them when a click happens, and in what (x, y) point on the screen it occurs. To find which elements on the screen are being clicked, a simple approach would be to just loop through every element and test each of them. But is this how it is usually done in existing GUIs? For example, is this what browsers do when they display HTML pages? Is this what operating systems do with their GUIs and windows? Do they use more complex data structures like R-Trees? How do they handle moving elements?

This question is not specific to any software, I'm just wondering how this problem is usually adressed in this context of GUI development.

Answer 1

There are 2 basic approaches. One you already figured out:

1. testing "each" object versus mouse position

   That can be speeded up by using spatial subdivision structures (similar to BVH and octree just in 2D). However this approach will always be slower and bound to complexities like O(log(n)) or O(n) where n is number of GUI elements. Here the naive O(n) example:

   • simple C++ Drag&Drop example

   However once the tested items number grows or their shape is too complex this method is cumbersome.

2. using index buffer

   This approach is pixel perfect with complexity O(1) and in most implementations is also almost for free fast.

   The idea is to have index buffer of the same resolution as screen holding ID (index) of tested element instead of color. So while you rendering your GUI in addition to setting each pixel of element with color you also set rendered item index or ID at the same position in the index buffer.

   After this the detection is just obtaining the index buffer value at mouse position. Here few examples:

   • OpenGL ray picking
   • VCL/GDI index buffer based mouse select

   This method is usable for 2D and projected 3D->2D or even higher dimensions too.