Sign in to follow this  

Raycasting: Fixed grid tracing...

This topic is 4196 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I've posted a few times about my simple 2D Raycaster (a la wolfenstien) and it has been driving me nuts that I dont understand exactly why a particular function works. The function traces the map starting from the player position untill it hits a wall. The algorithm is based on this paper: http://www.cs.yorku.ca/~amana/research/grid.pdf Also this this web page has a tutorial which follows the same algoritm:http://student.kuleuven.be/~m0216922/CG/raycasting.html With both of thoes resources I was able to scrape together a function that works, but I have no Idea the reasoning behind it. Pecisely speaking, I have no Idea how tDeltaX and tDeltaY variables were computed, and to a lesser extent I'm slightly confused as to why you have to multiply tMaxX and tMaxY with tDeltaX and tDeltaY.
int Trace_Ray(){
	
	/*
	tMaxX represents the value of at which the ray crosses the first vertical grid boundary.
	tMaxX represents the value of at which the ray crosses the first vertical grid boundary.
	The	minimum of these two values tells us how much we can travel along the ray in it's respective direction
	and still remain in the	current voxel.
	*/
	float tMaxX, tMaxY;
	/*
	Finally, we compute tDeltaX and tDeltaY. TDeltaX indicates how far along the ray we must move
	(in units of t) for the horizontal component of such a movement to equal the width of a voxel. Similarly,
	we store in tDeltaY the amount of movement along the ray which has a vertical component equal to the
	height of a voxel.
	*/
	float tDeltaX, tDeltaY;
	/*
	Globals stepX and stepY are initialized to either 1 or -1 
	*/
		
	if (ray_direction.x >= 0){
		stepX = 1;
		tDeltaX = sqrt((ray_direction.y * ray_direction.y) / (ray_direction.x * ray_direction.x) + 1);
		tMaxX = (map_x + 1 - ray_position.x) * tDeltaX;
	}else{
		stepX = -1;
		tDeltaX = sqrt((ray_direction.y * ray_direction.y) / (ray_direction.x * ray_direction.x) + 1);
		tMaxX = (ray_position.x - map_x) * tDeltaX;
	}
	if (ray_direction.y > 0){
		stepY = 1;
		tDeltaY = sqrt((ray_direction.x * ray_direction.x) / (ray_direction.y * ray_direction.y) + 1);
		tMaxY = (map_y + 1.0 - ray_position.y) * tDeltaY;
	}else{
		stepY = -1;
		tDeltaY = sqrt((ray_direction.x * ray_direction.x) / (ray_direction.y * ray_direction.y) + 1);
		tMaxY = (ray_position.y - map_y) * tDeltaY;
	}
	
	hit = NO_HIT;

	do{                  
		if (tMaxX < tMaxY)
		{
			tMaxX += tDeltaX;
			map_x += stepX;           
			if (map[map_x][map_y] > 0) 
				hit = HIT_X_SIDE; 
		}else{
			tMaxY += tDeltaY;
			map_y += stepY;
			if (map[map_x][map_y] > 0) 
				hit = HIT_Y_SIDE; 
		}                          
	} while (!hit);

	return hit;
}


Share this post


Link to post
Share on other sites
Guest Anonymous Poster

Imagine that your ray is represented parametrically, like this:

p(t) = O + t*D

Where O is the start position if the ray, D is the ray direction vector, and t is a parameter that defines how far along the ray you are. P(t) gives you the position along the ray at distance t.

The function works by gradually increasing T and stepping through the cells of the grid until the ray hits an object.

tDeltaX and tDeltaY are the amounts by which you need to increase T in order to move exactly one cell-length in either the X or Y directions.


tMaxX and tMaxY are how far you have to travel in T before you cross the boundary of the next voxel in either direction. To compute that, you need to compute the distance from where you are to the next cell in the grid (which is what those subtracts are doing). You also need to multiply by tDeltaX so that the result is the amount of change in T needed to travel that far in the X direction.

Share this post


Link to post
Share on other sites
In particular, How do the following represent tDeltaX and tDeltaY

        
____________________________________________
tDeltaX = \/ ray_direction.x^2 / ray_direction.y^2 plus 1
____________________________________________
tDeltaY = \/ ray_direction.y^2 / ray_direction.x^2 plus 1




So as you explained it (as well as in the paper) the values tDeltaX and tDeltaY represent "t" in the parametric line equation.

How is it that these particular equations solve for "t"?

Share this post


Link to post
Share on other sites

I'm the AP from above, forgot to log in last time

If you read the Amantides and Woo paper, you find that tDeltaX and tDeltaY are the amount by which you have to change T to move one unit in X or Y. (Dt/Dx). If rayDirX is the amount by which you change in X, given a unit change in t (Dx/Dt), then tDeltaX = 1 / rayDirX.

This assumes that the ray direction vector is normalized (unit length). If it isn't, then you first need to divide both components of the vector by its length. The length of a 2D vector (X,Y) is sqrt( (X*X) + (Y*Y) )

So, what you end up with, for a non-normalized vector, is:
tDeltaX = sqrt( (rayDirX*rayDirX) + (rayDirY*rayDirY) ) / rayDirX



The tutorial that you referenced has this:

Scalar deltaDistX = sqrt(1 + (rayDirY * rayDirY) / (rayDirX * rayDirX));
Scalar deltaDistY = sqrt(1 + (rayDirX * rayDirX) / (rayDirY * rayDirY));

The way they got this is a bit confusing. What they did is apply the pathagorean theorem to those blue and green triangles in their figure (they didn't bother to explain the math behind this at all, and they really should have).

If you look at the figure. 1 is the length of the bottom side of the blue triangle. The length of the vertical side is DirY / DirX (the distance traveled in Y per unit change in X). Applying the pathagorean theorem to that gives you what you see above.

It ends up being the same as the tDeltaX value that I just derived for you.


Share this post


Link to post
Share on other sites

This topic is 4196 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this