   Raycasting: Fixed grid tracing...
  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.pdfAlso this this web page has a tutorial which follows the same algoritm:http://student.kuleuven.be/~m0216922/CG/raycasting.htmlWith 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.Theminimum of these two values tells us how much we can travel along the ray in it's respective directionand still remain in thecurrent 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 theheight 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;}
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.   ;  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"?;I'm the AP from above, forgot to log in last timeIf 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) ) / rayDirXThe 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.