Hello kikito. I recently implemented this in my sweep and prune when I learned how to raycast.
The paper is a bit hard to understand so I'll try to explain it another way. I'm not good at explaining things so bare with me.
Imagine a ray traversing a grid. the ray initially starts in a cell within the grid. What happens initially is that the ray touches either a vertical line or a horizontal line in the first cell. The point at which the ray hits this first line is the starting point of your NEXT cell (the cell your ray starts in need to be checked too). You'll first need to figure this first hit.
First you'll need to rasterize your ray's origin (x,y) into grid coordinates. In my case I just use:
cell_x = math.floor(x/cell_size)
cell_y = math.floor(y/cell_size)
The next part is to figure out which direction your ray is moving on either the x axis or y axis. If your ray is moving to the right on the x axis, you would add one to the x component of your cell coordinate b/c your first vertical line hit is to the right of you. If your ray is moving downward, you would add one to the y component of your cell coordinate cause first horizontal line hit is below you.
Next you'll have to figure out the smallest distance ratio of your ray to figure out which line it starts at. So let's say you describe your ray as x+dx,y+dy where dx and dy are the length of the ray's component on each axis. You'll need to figure out the distance from your first line hit to your starting point on each axis.
To do this, you'll just turn the coordinate of your first line hit into "real" coordinates and subtract your starting point. So if my ray is moving right and downward:
xd = ((cell_x+1) * cell_size) - x
yd = ((cell_y+1) * cell_size) - y
Now what happens next is you divide the distance to your first lines by the maximum lengths the ray travels on either axis to figure out the smallest distance ratio. The logic behind this is that the first line you hit (vertical or horizontal) is controlled by the shortest distance the ray has to travel.
So:
x_ratio = xd/dx
y_ratio = yd/dy
Say that the y distance ratio of the ray is greater than x distance ratio; if we multiply the ray's component by the y ratio (x+y_ratio*dx) (y+y_ratio*dy), we will miss our next horizontal line because we traveled too far to hit the next vertical line.
We will need to check the ratio's in a loop whenever the ray is moving onto the next line to ensure that it takes the shortest distance possible.
Next we need to calculate the ratio needed on each axis to reach the next vertical or horizontal line. Just divide the cell size on both axis by its total lengths
So:
x_delta_ratio = cell_size/dx
y_delta_ratio = cell_size/dy
Explaination:
So let's say your cell size is 5 and your ray's dx is 10 --> (5/10) = 1/2 . What this means is that you'll need half the x length of your ray to hit the next vertical line.
So you have your initial ratio's and you know which line that ray hits first. To figure out the next line and cell to check, Add your delta ratio to your smallest ratio (because smallest ratio dictates length of ray to the next cell) and increase the cell step.
So:
Say the first cell that you hit is (0,0). This doesn't include the cell that you start in.
The x ratio and y ratio of this first cell are 0.1,0.2 respectively.
The x delta ratio and y delta ratio are 0.5,0.4 respectively.
The smallest ratio is the x ratio so we add x delta to it:
0.1 + 0.5 = 0.6 --> new x ratio
We increase the cell coordinate by -1 or 1 depending on our direction of the ray. The next cell to check is either (-1,0) or (1,0).
The next loop our y ratio is now smaller (0.2). We increase it and the cell stepping:
new y ratio = (0.2+0.4) = 0.6. The next cell is (-1,1) or (1,1)
Now we have equal ratio's (0.6 and 0.6). This means our next cell is next diagonal cell. Just step on either axis as we will reach our desire cells So:
(0,0) cell and next is (1,1). Increase x first ---> (1,0), then next loop increase y (1,1).
Here's the relevant code:
Code: Select all
local raycast = function(self,x,y,dx,dy,isCoroutine)
local set = {}
local x0,y0 = floor(x/self.width),floor(y/self.height)
local dxRatio,dyRatio,xDelta,yDelta,xStep,yStep,smallest,xStart,yStart
-- visualization of sides that we can check: [0 1]
-- if we're moving to the right, +1 to cell-x to
-- check the right side first as it's > our starting point
-- positive steps when moving right, neg steps when moving left
if dx > 0 then
xStep = 1
xStart = 1
else
xStep = -1
xStart = 0
end
if dy > 0 then
yStep = 1
yStart = y0 + 1
else
yStep = -1
yStart = 0
end
-- dxRatio: (x0*width-x)/dx precalculations
-- xDelta is the ratio of the ray's width to reach the next vertical line on the x-axis
-- always take the shortest ratio to reach the nearest line on the grid
-- zero hack
if dx == 0 then
dxRatio = math.huge
xDelta = 0
else
local a,b = self.width/dx,x/dx
dxRatio = a*(x0+xStart)-b
xDelta = a*xStep
end
if dy == 0 then
dyRatio = math.huge
yDelta = 0
else
local a,b = self.height/dy,y/dy
dyRatio = a*(y0+yStart)-b
yDelta = a*yStep
end
-- Use a repeat loop so that the ray checks its starting cell first before moving.
repeat
local row = self.cells[x0]
if row and row[y0] then
-- if called as an iterator, iterate through all objects in the cell and the next cells
-- otherwise, just look for the earliest hit and return
if isCoroutine then
for obj,hitx,hity in row[y0]:iterRay(x,y,dx,dy) do
if not set[obj] then coroutine.yield(obj,hitx,hity); set[obj]=true end
end
else
local obj,hitx,hity = row[y0]:rayQuery(x,y,dx,dy)
if obj then return obj,hitx,hity end
end
end
if dxRatio < dyRatio then
smallest = dxRatio
dxRatio = dxRatio + xDelta
x0 = x0 + xStep
else
smallest = dyRatio
dyRatio = dyRatio + yDelta
y0 = y0 + yStep
end
until smallest > 1
end
