Copyright	(c) axionbuster 2025
License	BSD-3-Clause
Safe Haskell	None
Language	GHC2021

M.Collision.Internal.March

Description

Implements ray marching algorithm for finding intersections with grid points. Used for precise collision detection in voxel-based environments.

Synopsis

data March (f :: Type -> Type) a = March {
- mtot :: a
- mpct :: f a
- mict :: [f Int]
}
march :: (Foldable f, Representable f, Rep f ~ E f, RealFloat a, Epsilon a) => f a -> f a -> [March f a]

Documentation

data March (f :: Type -> Type) a Source #

march data structure

Constructors

March
Fields mtot :: a total time mpct :: f a grid intersection (lies on boundaries of grid cells) 'pct' is for 'punctum', which is Latin for point mict :: [f Int] grid points (e.g., cubes, squares) intersected

march Source #

Arguments

:: (Foldable f, Representable f, Rep f ~ E f, RealFloat a, Epsilon a)
=> f a	starting point. use either f ~ `V2` or f ~ `V3` or other `Representable` vector types where 'fmap f x' agrees with `tabulate` \i -> f (`index` x i))
-> f a	direction (no need to be normalized)
-> [March f a]	list of (total time, point, [grid point]) pairs

march along a line segment, finding all intersections with grid squares or cubes (depending on the dimensionality) as well as the time it takes to reach each intersection and the cubes that are intersected

the cubes are represented by their low corner coordinates

in 2D, when a point is intersected, the two squares about the point that the line (that extends rhe ray) does NOT intersect will be included. it's because this routine is used for collision detection

in 3D, there are many edge cases, but generally only the cubes needed for collision detection are returned. so about a corner, three cubes will be returned; abour an edge, two (assuming ray is not parallel to a coordinate plane)

a compensated sum is used to reduce floating point error. the compensation applies to the coordinates and times

the returned list being infinite, it is recommended to use take to limit the number of points to be computed

the starting point is not included in the list unless it happens to be a grid intersection

if the direction is (near) zero, or if any component of the direction is not finite, then the function will return an empty list