Ray casting in a Spatial Hash with DDA

For quite some time I have been thinking of adding some ray casting into the Spatial Hash. The Spatial Hash is used for broad phase culling, eliminating objects that can’t intersect with what we want to test.

My former implementation only allowed tests against rectangles – when shooting a ray this might be very inefficient. For example, consider a diagonal ray going from x,y (0,0) to (100,100) in world coordinates. This world is represented in a spatial hash with, say, cell size 10. This means that the Spatial Hash would return all objects from the 100 cells that are overlapped by the rectangle set up by the ray. If we instead could only return the cells that the ray touches on its way from (0,0) to (100,100) we would reduce the number of potential objects a lot. Once we have obtained this subset we can do the narrow phase testing (fine grained ray tracing).

DDA

Now walking along a line from point A to B can be done in many ways, the most common is perhaps Bresenhams line algorithm. The problem with this approach is that it can make diagonal jumps and hence miss cells that the line actually pass over. This is where the DDA, or Digital Differential Analyzer yada yada, comes into the picture. I don’t know why anybody would name it such. Perhaps it’s just me that don’t get it. Bresenham seems like a decent guy, “hey I have a line algorithm, lets name it after myself and with the word line to it.”

Anyway, as opposed to Bresenhams line algorithm, DDA will touch all cells the line is moving over. So if you move from (0,0) to (1,1) it will not make a direct jump to (1,1) but first go via (1,0) or (0,1). This is exactly what we need to make sure we capture all cells along a rays direction.

A visual demo

Click somewhere in the flash to mark the start position of the line, then click again to mark the end pos. The grid is the cells in the spatial hash and the objects are random hash values. Objects that are returned by the raycast are highlighten.

Code

Here is the code! Sorry about the copying pasting trouble here, I might set up a code repository to make all this easier.

DDA.as

package com.playchilla.algorithm.spatial
	/**
	 * DDA line algorithm.
	 *
	 * @author playchilla.com
	 */
	public class DDA
	{
		public function DDA(cellSizeX:Number, cellSizeY:Number)
		{
			_cellSizeX = cellSizeX;
			_cellSizeY = cellSizeY;
		}
		
		public function run(x1:Number, y1:Number, x2:Number, y2:Number, traverseCallback:IDDACallback):void
		{
			var gridPosX:int = int(x1 / _cellSizeX);
			var gridPosY:int = int(y1 / _cellSizeY);
			if (!traverseCallback.onTraverse(gridPosX, gridPosY))
				return;
			
			var dirX:Number = x2 - x1;
			var dirY:Number = y2 - y1;
			const distSqr:Number = dirX * dirX + dirY * dirY;
			if (distSqr < 0.00000001)
				return;
			
			const nf:Number = 1 / Math.sqrt(distSqr);
			dirX *= nf;
			dirY *= nf;
			
			const deltaX:Number = _cellSizeX / Math.abs(dirX);
			const deltaY:Number = _cellSizeY / Math.abs(dirY);
			
			var maxX:Number = gridPosX * _cellSizeX - x1;
			var maxY:Number = gridPosY * _cellSizeY - y1;
			if (dirX >= 0) maxX += _cellSizeX;
			if (dirY >= 0) maxY += _cellSizeY;
			maxX /= dirX;
			maxY /= dirY;
			
			const stepX:int = dirX < 0 ? -1 : 1;
			const stepY:int = dirY < 0 ? -1 : 1;
			const gridGoalX:int = int(x2 / _cellSizeX);
			const gridGoalY:int = int(y2 / _cellSizeY);
			var currentDirX:int = gridGoalX - gridPosX;
			var currentDirY:int = gridGoalY - gridPosY;
			while (currentDirX * stepX > 0 || currentDirY * stepY > 0)
			{
				if (maxX < maxY)
				{
					maxX += deltaX;
					gridPosX += stepX;
  					currentDirX = gridGoalX - gridPosX;
				}
				else
				{
					maxY += deltaY;
					gridPosY += stepY;
  					currentDirY = gridGoalY - gridPosY;
				}
				
				if (!traverseCallback.onTraverse(gridPosX, gridPosY))
					return;
			}
		}
		
		private var _cellSizeX:Number;
		private var _cellSizeY:Number;
	}
}

IDDACallback.as

package com.playchilla.algorithm.spatial
{
	/**
	 * ...
	 * @author playchilla.com
	 */
	public interface IDDACallback
	{
		/**
		 * Return false to cancel traversal.
		 */
		function onTraverse(cx:int, cy:int):Boolean;
	}
}

Paste into SpatialHash.as
Also:
- Make the SpatialHash implement IDDACallback
- put this in the constructor "_dda = new DDA(cellSize, cellSize);"
- put this at the bottom "private var _dda:DDA;"
- put this at the bottom "private var _rayCastResult:Vector.;"

Perhaps time to open up an account on google code or similar? 🙂

	
public function rayCast(startPos:Vec2Const, stopPos:Vec2Const):Vector.<SpatialHashValue>
{
	_rayCastResult = new Vector.<SpatialHashValue>;
	_dda.run(startPos.x, startPos.y, stopPos.x, stopPos.y, this);
	++_timeStamp;
	return _rayCastResult;
}
		
public function onTraverse(cx:int, cy:int):Boolean
{
	const bucket:Vector.<SpatialHashValue> = _hash[_getKey(cx, cy)];
	if (bucket == null)	return true;
	for each (var b:SpatialHashValue in bucket)
	{
		if (b.timeStamp >= _timeStamp) continue;
		b.timeStamp = _timeStamp;
		_rayCastResult.push(b);
	}
	return true;
}

Credits
When I first wrote the DDA code perhaps 2 years ago I remember reading a pdf that explained it and had some c/c++ code. I can't find this article anymore, however, thank you mysterious author. Also thanks to Maurycy Zarzycki for inspiring me to finally get around to do this.