linecasting

Linecasting is a computational query used to determine whether a straight line segment between two points intersects any geometry or objects in a scene, and if so, where along the segment the first intersection occurs. It is widely used in video games, robotics, computer graphics, and geographic information systems for purposes such as collision detection, visibility testing, and sensor simulation. Unlike raycasting, linecasting is finite in length and yields a specific exit distance.

In two dimensions and grid-based environments, linecasting often advances along the line using Bresenham's line algorithm or a digital differential analyzer (DDA) to visit tested cells or tiles until an obstacle is found. In continuous geometry, it uses standard line-segment intersection tests against polygons, meshes, or analytic primitives, frequently aided by spatial data structures to prune candidates.

Common algorithms include Bresenham/DDA for grid traversal, and clipping or intersection tests such as Liang–Barsky, Cohen–Sutherland, or segment-triangle intersection for 3D scenes. Implementations typically report the intersection point, the distance from the segment start, and the object hit, with optional information about the surface normal or material.

Applications span weapon hit detection (hitscan), line-of-sight checks, laser beams, shadow or camera visibility tests, and sensor simulation for robotics or GIS analyses. Performance is a key concern, often addressed with spatial partitioning, early exit on first hit, or batch processing.

Linecasting shares concepts with raycasting but is constrained to a finite segment. Its robustness depends on numerical precision and object representation; common pitfalls include near-tangential intersections and missed hits due to discretization.