Parabolic trace

[slipher]

In https://github.com/Unvanquished/Unvanquished/issues/1722 a need for a parabolic trace. This means sweeping an axis-aligned bounding box along a parabola, rather than along a line as in a standard trace. Not sure if it's worthwhile, but I can sketch out how it would be implemented.

A BSP brush is a set of oriented planes. The brush volume is the intersection of the half-spaces defined by these planes. Consider the trace with the line extended infinitely, so that any point on the line corresponds to some trace "fraction" which can be any real number. For a given plane we can calculate the trace fractions, if any, at which the AABB enters and exits the half-space. Consider the part of the (number line corresponding to the trace fraction) in which the AABB intersects the half-space. If the trace line is orthogonal to the plane normal this is either (-∞, ∞) or nothing. Otherwise it is (-∞, x) or (x, ∞) for some x. Now to find the result of the trace against the brush, begin by assigning the line segment L = (0, 1). For each half-space, update L to the instersection of L and the line segment corresponding to the half-space. If the final value of L is empty, the trace didn't hit anything, fraction = 1.0. If the final value of L is (0, 1) it's allsolid. If the final value of L includes 0 it's startsolid.

For a parabola trace, the only difference is that the path of the trace may re-enter a half-space after exiting it. So the part of the trace number line in which the AABB overlaps the half-space constitutes up to two line segments (as opposed to 0 or 1 segments with the linear trace). To compute the final result you just have to intersect pairs of line segments.

[sweet235]

Not sure if it's worthwhile

Notice mantis and especially dragoon bots pounce along parabolic curves. For that reason, I have been thinking about a parabolic trace just a few days ago.

[DolceTriade]

I've never been good at understanding traces, so maybe a sketch might be helpful