Skip to main content
GameDev.net gamedev.net
🔒 Locked

Raytracing

Started by manunderground Jul 21, 2008 at 12:09 PM 0 replies 700+ views
Original Post
manunderground
manunderground
Hey, I'm having some trouble implementing a ray tracing algorithm... I thought I'd ask for some help before sinking more hours into this. In a nutshell, the algorithm misses the target sometimes; it seems to occur when the target is positioned between two cells in the grid. I feel like this must be a problem with how my delta values are calculated, or with how I calculate the distance to the next cell. Here's the code:

	/* Get a list of contacts between the target and subject. */
	public Long[] ray(Body subject, Body target) {
		/* Create the ray to check for intersection. */
		Ray ray = new Ray(subject, target);
		/* Get the direction vector for the ray. */
		Vector2f direction = ray.getDirection();
		
		/* Get the ray's starting coordinates in the grid. */
		int startX = (int) Math.floor(subject.getCenterX() / cellWidth);
		int startY = (int) Math.floor(subject.getCenterY() / cellHeight);
		
		/* Distance in the x, y direction of the vector for a single step. */
		float deltaX = (float) Math.sqrt(1 + 
				(direction.y * direction.y) / (direction.x * direction.x));
		float deltaY = (float) Math.sqrt(1 + 
				(direction.x * direction.x) / (direction.y * direction.y));
				
		/* The current cell to examine. */
		int currentX = startX;
		int currentY = startY;
		/* The target's cell. */
		int targetX = (int) Math.floor(target.getCenterX() / cellWidth);
		int targetY = (int) Math.floor(target.getCenterY() / cellHeight);
		
		/* Length of the ray from current position to next x, y-side of a cell. */
		float sideDistX, sideDistY;
		/* 1 or -1 depending on the ray's direction. */
		int stepX, stepY;
		
		/* Initialize the step and distance. */
		if (direction.x < 0) {
			stepX = -1;
			sideDistX = (startX - currentX) * deltaX;
		} else {
			stepX = 1;
			sideDistX = (currentX + 1 - startX) * deltaX;
		}
		
		if (direction.y < 0) {
			stepY = -1;
			sideDistY = (startY - currentY) * deltaY;
		} else {
			stepY = 1;
			sideDistY = (currentY + 1 - startY) * deltaY;
		}
		
		/* Advance one step. */
		if (sideDistX < sideDistY) {
			sideDistX += deltaX;
			currentX += stepX;
		} else {
			sideDistY += deltaY;
			currentY += stepY;
		}
		
		
		LinkedList<Long> contacts = new LinkedList<Long>();
		while (!(currentX == targetX && currentY == targetY)) {
			contacts.addAll(cells[currentX][currentY].getContactsWith(ray));
			if (sideDistX < sideDistY) {
				sideDistX += deltaX;
				currentX += stepX;
			} else {
				sideDistY += deltaY;
				currentY += stepY;
			}
		}
		return contacts.toArray(new Long[0]);
	}

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.