Hit-testing

Last updated

In computer graphics programming, hit-testing (hit detection, picking, or pick correlation [1] ) is the process of determining whether a user-controlled cursor (such as a mouse cursor or touch-point on a touch-screen interface) intersects a given graphical object (such as a shape, line, or curve) drawn on the screen. Hit-testing may be performed on the movement or activation of a mouse or other pointing device.

Contents

Hit-testing is used by GUI environments to respond to user actions, such as selecting a menu item or a target in a game based on its visual location. In web programming languages such as HTML, SVG, and CSS, this is associated with the concept of pointer-events (e.g. user-initiated cursor movement or object selection).

Collision detection is a related concept for detecting intersections of two or more different graphical objects, rather than intersection of a cursor with one or more graphical objects.

Algorithm

There are many different algorithms that may be used to perform hit-testing, with different performance or accuracy outcomes. One common hit-test algorithm for axis aligned bounding boxes. A key idea is that the box being tested must be either entirely above, entirely below, entirely to the right or left of the current box. If this is not possible, they are colliding. Example logic is presented in the pseudo-code below:

functionHitTest(Rectangler1,Rectangler2)returnsboolean{returnnot((r1.X+r1.Width<r2.X)or(r1.X>r2.X+r2.Width)or(r1.Y+r1.Height<r2.Y)or(r1.Y>r2.Y+r2.Height));}

In Python:

defhit_test(r1:Rectangle,r2:Rectangle)->bool:"""Return true if it hits else return false."""return(not(r1.x+r1.width<r2.x)or(r1.x>r2.x+r2.width)or(r1.y+r1.Height<r2.y)or(r1.y>r2.y+r2.height))

See also

Related Research Articles

<span class="mw-page-title-main">Graphical user interface</span> User interface allowing interaction through graphical icons and visual indicators

A graphical user interface, or GUI, is a form of user interface that allows users to interact with electronic devices through graphical icons and visual indicators such as secondary notation. In many applications, GUIs are used instead of text-based UIs, which are based on typed command labels or text navigation. GUIs were introduced in reaction to the perceived steep learning curve of command-line interfaces (CLIs), which require commands to be typed on a computer keyboard.

<span class="mw-page-title-main">Pointing device</span> Human interface device for computers

A pointing device is a human interface device that allows a user to input spatial data to a computer. Graphical user interfaces (GUI) and CAD systems allow the user to control and provide data to the computer using physical gestures by moving a hand-held mouse or similar device across the surface of the physical desktop and activating switches on the mouse. Movements of the pointing device are echoed on the screen by movements of the pointer and other visual changes. Common gestures are point and click and drag and drop.

<span class="mw-page-title-main">Graphics Device Interface</span> Microsoft Windows API

The Graphics Device Interface (GDI) is a legacy component of Microsoft Windows responsible for representing graphical objects and transmitting them to output devices such as monitors and printers. It was superseded by DirectDraw API and later Direct2D API. Windows apps use Windows API to interact with GDI, for such tasks as drawing lines and curves, rendering fonts, and handling palettes. The Windows USER subsystem uses GDI to render such UI elements as window frames and menus. Other systems have components that are similar to GDI; for example: Mac OS has QuickDraw, and Linux and Unix have X Window System core protocol.

<span class="mw-page-title-main">Scene graph</span> Form of data structure

A scene graph is a general data structure commonly used by vector-based graphics editing applications and modern computer games, which arranges the logical and often spatial representation of a graphical scene. It is a collection of nodes in a graph or tree structure. A tree node may have many children but only a single parent, with the effect of a parent applied to all its child nodes; an operation performed on a group automatically propagates its effect to all of its members. In many programs, associating a geometrical transformation matrix at each group level and concatenating such matrices together is an efficient and natural way to process such operations. A common feature, for instance, is the ability to group related shapes and objects into a compound object that can then be manipulated as easily as a single object.

Collision detection is the computational problem of detecting an intersection of two or more spatial objects, commonly computer graphics objects. It has applications in various computing fields, primarily in computer graphics, computer games, computer simulations, robotics and computational physics. Collision detection is a classic problem of computational geometry. Collision detection algorithms can be divided into operating on 2D or 3D spatial objects.

<span class="mw-page-title-main">Text box</span> Boxes where text is entered in computing

A text box is a control element of a graphical user interface, that should enable the user to input text information to be used by a program. Human Interface Guidelines recommend a single-line text box when only one line of input is required, and a multi-line text box only if more than one line of input may be required. Non-editable text boxes can serve the purpose of simply displaying text.

In computer science, human–computer interaction, and interaction design, direct manipulation is an approach to interfaces which involves continuous representation of objects of interest together with rapid, reversible, and incremental actions and feedback. As opposed to other interaction styles, for example, the command language, the intention of direct manipulation is to allow a user to manipulate objects presented to them, using actions that correspond at least loosely to manipulation of physical objects. An example of direct manipulation is resizing a graphical shape, such as a rectangle, by dragging its corners or edges with a mouse.

<span class="mw-page-title-main">Ray casting</span> Methodological basis for 3D CAD/CAM solid modeling and image rendering

Ray casting is the methodological basis for 3D CAD/CAM solid modeling and image rendering. It is essentially the same as ray tracing for computer graphics where virtual light rays are "cast" or "traced" on their path from the focal point of a camera through each pixel in the camera sensor to determine what is visible along the ray in the 3D scene. The term "Ray Casting" was introduced by Scott Roth while at the General Motors Research Labs from 1978–1980. His paper, "Ray Casting for Modeling Solids", describes modeled solid objects by combining primitive solids, such as blocks and cylinders, using the set operators union (+), intersection (&), and difference (-). The general idea of using these binary operators for solid modeling is largely due to Voelcker and Requicha's geometric modelling group at the University of Rochester. See solid modeling for a broad overview of solid modeling methods. This figure on the right shows a U-Joint modeled from cylinders and blocks in a binary tree using Roth's ray casting system in 1979.

<span class="mw-page-title-main">Bounding volume</span> Closed volume that completely contains the union of a set of objects

In computer graphics and computational geometry, a bounding volume for a set of objects is a closed region that completely contains the union of the objects in the set. Bounding volumes are used to improve the efficiency of geometrical operations, such as by using simple regions, having simpler ways to test for overlap.

In the field of computing and web design, a mouseover, also called a hover effect, is a graphical control element. This element responds when a user moves their mouse pointer over a designated area. This area can be a button, image, or hyperlink. This simple action can trigger different responses. The element's color or appearance can change. Additional information or interactive content can be displayed. The mouseover effect is an essential part of user interaction. It adds layers of interactivity and responsiveness to websites and applications.

<span class="mw-page-title-main">Real-time computer graphics</span> Sub-field of computer graphics

Real-time computer graphics or real-time rendering is the sub-field of computer graphics focused on producing and analyzing images in real time. The term can refer to anything from rendering an application's graphical user interface (GUI) to real-time image analysis, but is most often used in reference to interactive 3D computer graphics, typically using a graphics processing unit (GPU). One example of this concept is a video game that rapidly renders changing 3D environments to produce an illusion of motion.

Windows Presentation Foundation (WPF) is a free and open-source user interface framework for Windows-based desktop applications. WPF applications are based in .NET, and are primarily developed using C# and XAML.

In computer graphics, the Liang–Barsky algorithm is a line clipping algorithm. The Liang–Barsky algorithm uses the parametric equation of a line and inequalities describing the range of the clipping window to determine the intersections between the line and the clip window. With these intersections it knows which portion of the line should be drawn. So this algorithm is significantly more efficient than Cohen–Sutherland. The idea of the Liang–Barsky clipping algorithm is to do as much testing as possible before computing line intersections.

In human–computer interaction, a cursor is an indicator used to show the current position on a computer monitor or other display device that will respond to input.

Desktop Window Manager is the compositing window manager in Microsoft Windows since Windows Vista that enables the use of hardware acceleration to render the graphical user interface of Windows.

A bounding volume hierarchy (BVH) is a tree structure on a set of geometric objects. All geometric objects, which form the leaf nodes of the tree, are wrapped in bounding volumes. These nodes are then grouped as small sets and enclosed within larger bounding volumes. These, in turn, are also grouped and enclosed within other larger bounding volumes in a recursive fashion, eventually resulting in a tree structure with a single bounding volume at the top of the tree. Bounding volume hierarchies are used to support several operations on sets of geometric objects efficiently, such as in collision detection and ray tracing.

<span class="mw-page-title-main">OptiX</span> Nvidia ray tracing API using CUDA to compute on GPUs

Nvidia OptiX is a ray tracing API that was first developed around 2009. The computations are offloaded to the GPUs through either the low-level or the high-level API introduced with CUDA. CUDA is only available for Nvidia's graphics products. Nvidia OptiX is part of Nvidia GameWorks. OptiX is a high-level, or "to-the-algorithm" API, meaning that it is designed to encapsulate the entire algorithm of which ray tracing is a part, not just the ray tracing itself. This is meant to allow the OptiX engine to execute the larger algorithm with great flexibility without application-side changes.

<span class="mw-page-title-main">Cobalt (CAD program)</span> 3D computer graphics software

Cobalt is a parametric-based computer-aided design (CAD) and 3D modeling program that runs on both Macintosh and Microsoft Windows operating systems. The program combines the direct-modeling way to create and edit objects and the highly structured, history-driven parametric way exemplified by programs like Pro/ENGINEER. A product of Ashlar-Vellum, Cobalt is Wireframe-based and history-driven with associativity and 2D equation-driven parametrics and constraints. It offers surfacing tools, mold design tools, detailing, and engineering features. Cobalt includes a library of 149,000 mechanical parts.

QML is a user interface markup language. It is a declarative language for designing user interface–centric applications. Inline JavaScript code handles imperative aspects. It is associated with Qt Quick, the UI creation kit originally developed by Nokia within the Qt framework. Qt Quick is used for mobile applications where touch input, fluid animations and user experience are crucial. QML is also used with Qt3D to describe a 3D scene and a "frame graph" rendering methodology. A QML document describes a hierarchical object tree. QML modules shipped with Qt include primitive graphical building blocks, modeling components, behavioral components, and more complex controls. These elements can be combined to build components ranging in complexity from simple buttons and sliders, to complete internet-enabled programs.

References

  1. Computer Graphics: Principles and Practice 2nd Edition in C, Foley et al, Addison-Wesley, 1997.