# Solving the “bullet problem” [duplicate]

I have a 3D matrix filled with "empty space" where I put some objects (objects are represented as bunch of occupied space).

The bullet is fired from coordinates (x1,y1,z1) at angles (verticalAngle,horizontalAngle).

How do I find the first coordinates in the bullet's trajectory line which is not market as "empty space"?

I suppose I'd have to loop through all the coordinates in that line till I find the not empty one (or the end of the matrix). But how do I calculate what are those coordinates that I have to go through?

When firing a bullet in 2D space I suppose this would be calculated as
y = cos(angle) * x + startPosition where I'd increment x (in a for loop) to get y and check (x,y) cell for objects or "empty". Actually I'd have to increment y in the for loop to get x instead in case the trajectory line is closer to y-axis than x-axis.

But can someone help me with doing this in 3D space?

EDIT: Well I found this formula: (x,y,z)=(x0,y0,z0)+t(a,b,c) where (x0,y0,z0) are starting points and (a,b,c) direction factors, so I think I could increment t in a loop to get the coordinates.

• Did you consider using a physics engine? All physics engine I know of detect collisions too. If your target objects are rectangles or circles, you don't have to traverse to check for collisions, you can actually compute the equation and check if the ray intersects with that cube or sphere. – AturSams Dec 25 '14 at 21:44
• @Zehelvion I actually have to write this by myself. And the objects are of no regular shape. – zoran404 Dec 26 '14 at 13:16

You are looking for a grid traversal algorithm I think. I implemented mine based on this paper: http://www.cse.chalmers.se/edu/year/2011/course/TDA361/grid.pdf.

The key points are below:

"""

The traversal algorithm consists of two phases: initialization and incremental traversal. The initialization phase begins by identifying the voxel in which the ray origin, → u, is found. If the ray origin is outside the grid, we find the point in which the ray enters the grid and take the adjacent voxel. The integer variables X and Y are initialized to the starting voxel coordinates. In addition, the variables stepX and stepY are initialized to either 1 or -1 indicating whether X and Y are incremented or decremented as the ray crosses voxel boundaries (this is determined by the sign of the x and y components of →v).

Next, we determine the value of t at which the ray crosses the first vertical voxel boundary and store it in variable tMaxX. We perform a similar computation in y and store the result in tMaxY. The minimum of these two values will indicate how much we can travel along the ray and still remain in the current voxel. 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. The incremental phase of the traversal algorithm is very simple. The basic loop is outlined below:

loop {
if(tMaxX < tMaxY) {
tMaxX= tMaxX + tDeltaX;
X= X + stepX;
} else {
tMaxY= tMaxY + tDeltaY;
Y= Y + stepY;
}
NextVoxel(X,Y);
}


"""

See the paper for extension to 3D.

You can contain your 3d world into a spatial hierarchy system like an octree. Then use ray casting to navigate the levels of the octree and end up only needing a handful of collision checks to narrow down the collision to the exact triangle of the object (regular or irregular shape) that gets hit by the ray first.

You can check if a ray or in your case a bullet that travels in a very high speed hits a spherical target by performing this computation:

The sphere's radius is r and it's center is in c = (x0,y0,z0). The ray's origin is o = (x1,y1,z1) and direction d = (x2,y2,z2).

if:

(d * (o - c)^2) - ||o - c||^2 +r^2) >= 0


Then the bullet that originates from o with direction d will hit the sphere at c of size r

You may hit multiple targets and then may simply need to check which target is closest to the origin afterwards. That depends on the complexity of your game, if there is not instance where targets overlap, that will suffice.

You can use this to prune the targets.

After that you would need to check for ray to polygon intersection. You can define an axis aligned box around your target, then find the box inside it with which the ray intersects. You will probably need to check for ray / polygon intersection after that. There are many example available online.

• Unfortunately my objects are of no regular shape, so calculating this wont help. I could although wrap them in cubes and calculate this for the cube, but I'd still have to check inside the cube this way, to see if it his it. – zoran404 Dec 26 '14 at 13:21
• @zoran404 Hmm.. If they are not of any regular shape, why would any of these techniques help? The stepping you suggest is too slow for a real time application unless the bullets travel at a very slow speed. You need to check for ray polygon intersection. I modified the answer to reflect that. – AturSams Dec 26 '14 at 21:07