3
\$\begingroup\$

There is a popular paper, and numerous examples, on how to efficiently perform collision detection for a line with a grid. However, I'm drawing up blanks on how to do the same thing but with a line that has thickness.

In my game, I'm considering adding projectiles that are not infinitly thin (for example, a giant plasma ball launcher), and I need to figure out which cells along a grid that it collides with. Initially I thought it'd be as simple as just using the Minkowski Sum method of adding the width/height of the projectile to each cell of the grid, and then treating the projectile as infinity thin line along a bloated-overlapping-grid, but that doesn't look like it's going to work with the existing algorithm.

Are there any other papers/algorithms that describe how to accomplish this? Or is there a way to modify the existing algorithm to accomplish this? Or are there any tricks to implementing this indirectly?

\$\endgroup\$
  • \$\begingroup\$ Consider the problem as a sequence of circle tests against the grid and along that ray. If the projectile is moving less than 1 radius per frame along that path, you can be performing these checks once per frame after each motion step, without the need for a raycasting solution at all. If the projectile is moving very fast, then raycasting makes sense. Even in that case, you can run a series of circle/grid checks for points along the ray that are close enough not to miss any grid cells for the motion during that time step. \$\endgroup\$ – Romen Oct 26 '20 at 20:14
  • \$\begingroup\$ "but that doesn't look like it's going to work with the existing algorithm" No? Why not? First we can look only at the lines/planes where you enter a new grid cell, so rather than "thickening" the grid, all you're really doing is shifting it. Then we can look at the lines/planes where we exit the previous grid cell - a second shift. Walking two rays through these shifted grids gives us the range of voxels spanned by our sphere at any given step. This works as long as your sphere is less than 6 cells wide - any bigger and we risk including some unnecessary voxels. \$\endgroup\$ – DMGregory Oct 26 '20 at 21:05
  • \$\begingroup\$ @DMGregory two rays won't enter the cells at the same timestep; you can't use two rays with the algorithm in the paper without some really inefficient storage and sorting to workaround the mismatched timestep \$\endgroup\$ – Mr. Smith Oct 26 '20 at 21:39
  • \$\begingroup\$ You don't need them to enter at the same timestep. You just care about where the tail is at the timestep when the head enters a new row/column, because the position of the tail tells you how many voxels you're spanning as you slide your way in. The storage is a few floats, nothing that would break the bank. \$\endgroup\$ – DMGregory Oct 26 '20 at 21:42
3
+25
\$\begingroup\$

If the thickness of your line / the radius of the circle following it is substantially narrower than your grid spacing, then it suffices to take the circle traversing your line and approximate it as a bounding square.

This bounding square has a leading corner (furthest ahead along its velocity vector) and a trailing corner (furthest behind).

We can use the original algorithm on these two points. Every time the leading corner enters a new cell, our bounding square has begun to overlap one or more new cells (since it spans some area, and can cross into multiple cells at once). Every time the trailing corner enters a new cell, our bounding square has exited one one more previously-occupied cells.

Animation of the algorithm at work

Here's code that does that, in Unity-style C#:

public Vector2 gridSpacing = new Vector2(1, 1);

public struct CastEvent : System.IComparable<CastEvent> {
    public readonly float time;
    public readonly bool entering;
    public readonly Vector2Int cell;
    public readonly Vector2 direction;
    
    CastEvent(float time, bool entering, Vector2Int cell, Vector2 direction) {
        this.time = time;
        this.entering = entering;
        this.cell = cell;
        this.direction = direction;
    }

    public CastEvent Adjust(float delta, Vector2 direction) {
        return new CastEvent(time + delta, entering, cell, direction);
    }

    public static CastEvent Enter(float time, Vector2Int cell, Vector2 direction) {
        return new CastEvent(time, true, cell, direction);
    }

    public static CastEvent Exit(float time, Vector2Int cell, Vector2Int direction) {
        return new CastEvent(time, false, cell, direction);
    }

    public int CompareTo(CastEvent other) {
        return time.CompareTo(other.time);
    }
}

IEnumerator<CastEvent> CircleCastApproximate(Vector2 startPosition, Vector2 velocity, float radius, float maxTime = float.PositiveInfinity)
{
    Vector2Int direction = new Vector2Int(velocity.x >= 0f ? 1 : -1, velocity.y >= 0f ? 1 : -1);
    Vector2 leadPosition = (startPosition + radius * (Vector2)direction)/gridSpacing;
    Vector2 tailPosition = (startPosition - radius * (Vector2)direction)/gridSpacing;

    // The cells in which the top-left and bottom-right 
    // corners of the circle's bounding box fall.
    Vector2Int leadCell = Vector2Int.FloorToInt(leadPosition);
    Vector2Int tailCell = Vector2Int.FloorToInt(tailPosition);

    // Cell-aligned bounding box of the circle.
    Vector2Int minCorner = Vector2Int.Min(leadCell, tailCell);
    Vector2Int maxCorner = Vector2Int.Max(leadCell, tailCell);

    // Set lead and tail positions to values in the range 0...1
    // to represent their fractional progress through their cell.
    leadPosition -= leadCell;
    tailPosition -= tailCell;

    // The time it takes to traverse one full grid cell, horizontally, and vertically.
    Vector2 timeDelta = (gridSpacing / velocity) * direction;

    // Initialize the timestamps when each point enters a new column...
    Vector2 nextEntryTime;
    Vector2 nextExitTime;
    if (velocity.x > 0f) {
        nextEntryTime.x = (1f - leadPosition.x) * timeDelta.x;
        nextExitTime.x = (1f - tailPosition.x) * timeDelta.x;
    } else if (velocity.x < 0f) {
        nextEntryTime.x = leadPosition.x * timeDelta.x;
        nextExitTime.x = tailPosition.x * timeDelta.x;
    } else {
        nextEntryTime.x = nextExitTime.x = float.PositiveInfinity;
    }

    // ...or row.
    if (velocity.y > 0f) {
        nextEntryTime.y = (1f - leadPosition.y) * timeDelta.y;
        nextExitTime.y = (1f - tailPosition.y) * timeDelta.y;
    } else if (velocity.y < 0f) {
        nextEntryTime.y = leadPosition.y * timeDelta.y;
        nextExitTime.y = tailPosition.y * timeDelta.y;
    } else {
        nextEntryTime.y = nextExitTime.y = float.PositiveInfinity;
    }

    // Log an initial collision with all of the cells we're overlapping
    // in our starting position. (Skip this to ignore initial overlaps)
    for (int x = minCorner.x; x <= maxCorner.x; x++) {
        for (int y = minCorner.y; y <= maxCorner.y; y++) {
            yield return CastEvent.Enter(0f, new Vector2Int(x, y), Vector2Int.zero);
        }
    }

    float accumulatedTime = 0f;
    while(true) {
        float nextEventTime = Mathf.Min(nextEntryTime.x, nextEntryTime.y, nextExitTime.x, nextExitTime.y);

        float totalTime = accumulatedTime + nextEventTime;

        if (totalTime > maxTime)
            yield break;

        if(nextEventTime == nextExitTime.x) {
            int height = (leadCell.y - tailCell.y) * direction.y;
            for (int i = 0; i <= height; i++) {
                int y = tailCell.y + i * direction.y;
                yield return CastEvent.Exit(totalTime, new Vector2Int(tailCell.x, y), new Vector2Int(direction.x, 0));
            }
            tailCell.x += direction.x;
            nextExitTime.x += timeDelta.x;
        }

        if (nextEventTime == nextExitTime.y) {
            int width = (leadCell.x - tailCell.x) * direction.x;
            for (int i = 0; i <= width; i++) {
                int x = tailCell.x + i * direction.x;
                yield return CastEvent.Exit(totalTime, new Vector2Int(x, tailCell.y), new Vector2Int(0, direction.y));
            }
            tailCell.y += direction.y;
            nextExitTime.y += timeDelta.y;
        }

        if (nextEventTime == nextEntryTime.x) {                
            leadCell.x += direction.x;
            int height = (leadCell.y - tailCell.y) * direction.y;
            for (int i = 0; i <= height; i++) {
                int y = tailCell.y + i * direction.y;
                yield return CastEvent.Enter(totalTime, new Vector2Int(leadCell.x, y), new Vector2Int(direction.x, 0));
            }
            nextEntryTime.x += timeDelta.x;
        }

        if (nextEventTime == nextEntryTime.y) {
            leadCell.y += direction.y;
            int width = (leadCell.x - tailCell.x) * direction.x;
            for (int i = 0; i <= width; i++) {
                int x = tailCell.x + i * direction.x;
                yield return CastEvent.Enter(totalTime, new Vector2Int(x, leadCell.y), new Vector2Int(0, direction.y));
            }
            nextEntryTime.y += timeDelta.y;
        }

        // Shift our time horizon so the most recent event is zero.
        // This avoids loss of precision in our event ordering as the time becomes large.
        accumulatedTime = totalTime;
        nextEntryTime -= nextEventTime * Vector2.one;
        nextExitTime -= nextEventTime * Vector2.one;
    }
}

I've shown the 2-dimensional case here, but it should be clear how to extend this to 3D if that's what you need.

Note that potentially all 4 crossing events could be the next, if they all occur at the same time stamp. That's why they're all if instead of some being else if. As long as we handle the exit events before the enter events, we don't artificially enlarge our bounding box.

One caution when adapting this code: proofread very carefully. One x that didn't get changed to a y due to a copy-paste error can easily give you wrong results or an infinite loop. (I found three such mistakes while I was drafting it) There may be opportunities to refactor some of the common operations into functions/lambdas to reduce this copy-paste risk.

This is an approximation, but it's a conservative approximation: using this, you'll never miss a collision you should have detected. When travelling diagonally, we can get into a situation where the bounding box of the circle clips a cell that the circle itself never touches, giving us a false positive. In this event, you could do some redundant collision checks inside that cell.

When the bounding box enters a row or column of multiple cells all at once, the true circle will usually enter one of those cells slightly before the others. So you'd want to check for a collision in all cells this algorithm reports as being entered at the same time stamp, to be sure you find the earliest of them.

If you need tighter precision than just the bounding box, you can buffer a range of outputs from this algorithm and perform a more detailed circle cast or ray-versus-rounded-rectangle check against each cell, and use that to reject false positives or re-order them. The algorithm above then serves as a kind of broad phase, helping you zero-in on a small set of cells that need the more expensive detailed check.

Animation with a circle much larger than the grid cells

Here's an example of how we can augment the bounding box algorithm to get an exact fit:

// Compute how long it takes for a point particle to hit a circle at the origin.
float TimeToHitCircle(Vector2 startPosition, Vector2 velocity, float radius, out Vector2 direction, bool entering) {   

    // Basic quadratic formula.
    float a = Vector2.Dot(velocity, velocity);
    float b = 2f * Vector2.Dot(startPosition, velocity);
    float c = Vector2.Dot(startPosition, startPosition) - radius * radius;

    float discriminant = b * b - 4f * a * c;

    if (discriminant < 0f) {
        direction = Vector2.zero;
        return float.NaN;
    }

    float sign = entering ? -1f : 1f;
    // TODO: There are ways to rearrange this for better numerical stability.
    float t = (-b + sign * Mathf.Sqrt(discriminant)) / (2f * a);

    if (sign * t > 0f) {
        Debug.LogErrorFormat("start {0}, vel {1}, rad {2}, entering {3}", startPosition, velocity, radius, entering);
    }

    direction = sign * (startPosition + t * velocity).normalized;
    return t;
}

// Used to maintain our sorted buffer of events.
// TODO: A heap/priority queue may handle this more efficiently.
void InsertSorted(List<CastEvent> eventBuffer, CastEvent item) {
    int index = eventBuffer.BinarySearch(item);
    if (index < 0)
        index = ~index;
    eventBuffer.Insert(index, item);
}

Vector2 OffsetFromCenterOfCell(Vector2Int cell, Vector2 position) {
    return position - gridSpacing * (cell + Vector2.one * 0.5f);
}

IEnumerator<CastEvent> CircleCastExact(Vector2 startPosition, Vector2 velocity, float radius, float maxTime = float.PositiveInfinity) {
    
    // Spin up our crude bounding box version to enumerate the cells we *might* touch.
    var broadPhase = CircleCastApproximate(startPosition, velocity, radius, maxTime);
    broadPhase.MoveNext();              

    // Compute how much earlier/later the circle might touch a corner, compared to the square.
    // This is how much time we need to look ahead to ensure we correctly order our intersections.
    float timeError = TimeToHitCircle(new Vector2(Mathf.Sign(velocity.x), Mathf.Sign(velocity.y)) * -radius, velocity, radius, out Vector2 unused, true);
    
    // First, filter the initial overlaps to only the ones we actually touch.
    Vector2 halfGrid = gridSpacing * 0.5f;
    while (broadPhase.Current.time == 0) {
        var offset = OffsetFromCenterOfCell(broadPhase.Current.cell, startPosition);

        var onCell = new Vector2(
                Mathf.Clamp(offset.x, -halfGrid.x, halfGrid.x),
                Mathf.Clamp(offset.y, -halfGrid.y, halfGrid.y)
        );
        if ((offset - onCell).sqrMagnitude < radius * radius)
            yield return broadPhase.Current;
        broadPhase.MoveNext();
    }

    // We'll keep a sorted buffer of upcoming events.
    var eventBuffer = new List<CastEvent>();

    do {
        var current = broadPhase.Current;

        // As long as the next event from the broad phase is far enough past the start of our buffer,
        // then we know no undiscovered event can intervene. So it's safe to emit our earliest buffered event.
        while (eventBuffer.Count > 0 && eventBuffer[0].time + timeError <= current.time) {
            yield return eventBuffer[0];
            eventBuffer.RemoveAt(0);
        }
        
        // We've emptied out the events we know are in the correct order.
        // Time to take this next approximate event from the broad phase and put it in order.

        // Shift our situation so the cell we're entering/exiting is centered on the origin.
        Vector2 offset = OffsetFromCenterOfCell(current.cell, startPosition);

        // Compute our position relative to the cell center at the time our bounding box touches it.
        Vector2 positionAtTime = offset + current.time * velocity;

        // If we entered this cell horizontally, we care about our vertical alignment, and vice versa.
        Vector2 alongSide = new Vector2(current.direction.y, current.direction.x);

        // How far are we off the cell's center line at the moment of bounding box contact with its edge?
        float deviation = Mathf.Abs(Vector2.Dot(positionAtTime, alongSide));
        float limit = Mathf.Abs(Vector2.Dot(gridSpacing, alongSide)) / 2f;

        // If we're less than half the grid spacing off-center, then we've hit the edge right on time.
        if (deviation <= limit) {
            InsertSorted(eventBuffer, current);
            continue;
        }

        // Otherwise, we're sweeping past the corner, and we might hit it at a different time, or miss.

        // Shift our position again, so the corner is centered at (0, 0).
        positionAtTime -= new Vector2(Mathf.Sign(positionAtTime.x), Mathf.Sign(positionAtTime.y)) * halfGrid;

        // The time when a moving circle hits a stationary point 
        // is the same as the time when a moving point hits a stationary circle.
        float addedTime = TimeToHitCircle(positionAtTime, velocity, radius, out Vector2 direction, current.entering);

        // We actually miss this cell. Discard it without adding it to our buffer.
        if (float.IsNaN(addedTime)) {
            continue;
        }

        // Adjust the timing of this event: later for entering, earlier for exiting.
        current = current.Adjust(addedTime, direction);
                   
        // We exit cells from "before" the ray started. Ignore them.
        if(current.time > 0f)
            InsertSorted(eventBuffer, current);

    } while (broadPhase.MoveNext());

    // Our broadphase ray has terminated, now we just need to empty any events left in our queue.
    foreach(var item in eventBuffer) {
        if (item.time > maxTime)
            yield break;

        yield return item;
    }
}

Note that you only need to add the time error offset if you care about the "exit" events. If you just want to correctly order the cells the circle enters, then it's safe to get rid of the exit events entirely and treat the time error as zero (entrance events from the broadphase can only happen later than reported, never earlier)

\$\endgroup\$
  • \$\begingroup\$ Wow; this is surprisingly detailed. However, the projectiles may be whole multiples of the grid spacing, so the condition that the projectiles behave just nearly infinitely-thin doesn't hold. :( \$\endgroup\$ – Mr. Smith Nov 2 '20 at 0:24
  • \$\begingroup\$ That's fine, you can use the method outlined at the end to refine this square approximation into one that respects the circle shape. \$\endgroup\$ – DMGregory Nov 2 '20 at 0:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.