CODEWITHSUNDEEP
c++castinggeometryintersectionraytracing
Katastic Voyage
Katastic Voyage

Reputation: 1044

Optimal line intersection with a square grid

I have a ray casting algorithm for finding shadows/light.

While the rays are in pixel coordinates, the map itself is a square, constant size grid of tiles. A grid cell is either passable, or not passable (a square wall). Typical of many 2-D games.

I have ray casting code that steps rays forward, and flags when a ray is inside a wall. When this happens, the ray is usually INSIDE the cell, not at the edge. At that point I have the starting x/y pair from the light source, an angle the ray traveled, and the x/y pair inside the wall.

I want to find the point of first contact with the wall, so in essence, I need to "back up" the line. Using the angle that the ray came from, I probably only need to test one segment of the square to find the intersection point.

If I have a fixed TILE_WIDTH and TILE_HEIGHT (and in this case, they're equal too); is there any more optimal, specific method for finding the position of that line segment intersection? That is, it takes advantage of the relationships, and the information I already have to be simpler and/or faster than a general algorithm.

Upvotes: 1

Views: 1940

Answers (1)

MBo
MBo

Reputation: 80287

There is algorithm of Woo and Amanatides for Fast Voxel Traversal. It calculates the points of intersection of ray with rectangular grid edges.

Upvotes: 2

Related Questions