7

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.

PiFace
  • 526
  • 3
  • 19

1 Answers1

5

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:

    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:

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

Spektre
  • 49,595
  • 11
  • 110
  • 380
  • so, for clarification: let's suppose I have a 200x100 rectangular button, at position (700,400) on a 1600x900 screen. This index buffer would be of size 1600*900=1440000, and I should set its indexes in the interval `(x,y) | 700 <= x <= 900, 400 <= y <= 500` to the button ID. Is that correct? – PiFace May 04 '21 at 03:19
  • @PiFace if the button is rectangle then yes... if it is rounded rectangle or different shape then you set ID only for those x,y which belongs to the button (unless you are happy with just BBOX selection then rectangle is fine too). It is usual to merge the actual render to rgb and index together (like using color attachment in OpenGL etc ... which makes implementing this approach with very little effort) If the GUI elements do not change shape or position then this can be done just once at any window resize event and use that from then ... – Spektre May 04 '21 at 05:53
  • @PiFace In case you got memory problems you can use n times lower resolution for the index buffer (resulting in less accurate selection) .. you know one pixel in index buffer is covering 2x2 , 3x3 , ... pixels in RGB – Spektre May 04 '21 at 05:54
  • Do you have any references/material for further reading into this topic? I'd like to know more about it in order to actually implement it. AFAIK, the tools I'm currently using don't allow me direct access to buffers like in the examples you showed, so I'll try other alternatives. But your answer was very helpful to give an idea of possible approaches despite the language or library used! Maybe one day I'll try and learn OpenGL – PiFace May 05 '21 at 01:01
  • @PiFace No I do not have any tutorials or docs about this... this is so simple like implementing Depth buffer so apart of code and this simple description there is not much else to add. What gfx api/lib you use? Its very hard to believe you do not have access to pixels ... you obviously can render so making index buffer is just a matter of rendering image. In some libs there are alternatives that can be used like Depth, Stencil, Shadow, ... buffers ... or render to texture, render to bitmap ,... or render to screen but not show it store the result and then rerender normal RGB output. – Spektre May 05 '21 at 07:14
  • @PiFace If you want I got 2 low level C++/VCL examples (GDI) ready one for first approach ~16KB of GUI code looking like [this](https://stackoverflow.com/a/21658139/2521214) so simple knobs, interpolation boxes sliders buttons ... and the second approach is used in `VCL/GDI index buffer based mouse select` link in answer however the new code ~54.8KB containing it did not fit the 30KB limit so its not posted there. I can post them somewhere if you want ... however both will depend on stuff I can not share and onm VCL itself so you would not be able to use them directly without porting. – Spektre May 05 '21 at 07:26
  • It's actually not a gfx lib, i'm using a simple game engine, called LÖVE. It doesn't provide a GUI module by default, so I wanted to write a GUI lib for it, just for practice. There's a layer of abstraction between the app/game code and the engine, so I can draw to the screen, but I can't read back the values of pixels, AFAIK. My question was intentionally not specific to LÖVE because I wanted to know about this problem in general before trying to implement anything. – PiFace May 07 '21 at 17:14