Raycasting and collision

[Stormy]

I'm trying to wrap my head around how to check for collision along a raycast. What I am doing is raycasting from a source to a goal and I want to check if that path is clear. I am doing this in a HTML canvas so it's a 2d environment.

Since raycasting is a one-frame thing I can't iteratively check each pixel unless I map them to an array or something, and checking the pixel colour doesn't seem like a good idea anyway, since that's not really a programmatic solution. I could record the boundary space of every object on screen and check my raycast against them but that would require me to map the pixels of my raycast again, and would require that I record in an array and loop through every pixel on screen.

How do you cast a ray and check that it is clear? And if it isn't clear, how do you find out where it is blocked and what it hit?

EDIT: on a side note, what is the usually accepted way to programmatically record and define the entirety of an edge or face in 2d space? I am recording the four corners of the bounding box and then figuring out the location of all the pixels in between the points and recording them on a multidimensional array. It's really clunky. Is there a better data type to use for this? Or is it something that can be sidestepped entirely?

[zombie@computer]

I've never ray-casted with JavaScript so i don't know if there is a specialized method, but normally a ray-cast iterates the bounding boxes of all objects and see if they intersect the ray. If a bounding box intersects it, a more detailed per-pixel check can be performed if required.

Of course this isn't efficient and you can optimize this in many ways. For instance using binary space partitioning, object sorting (check largest or most likely to hit objects first). In a limited canvas size with a lot of objects, checking per pixel might be faster than any mathematical approaches though. Also, dont forget to cache your casts. If the ray doesn't change, you only need to recheck when objects moved or resized.

The casting itself (i take it you need help with the mathematical side?) is as simple as rewriting your ray to

Y = bX + a
Y_coordinate = (slope * X_coordinate + offset_at_origin)

example: Let a ray be cast from vector one to vector two

b is then (two.y - one.y) / (two.x - one.x);
a is then one.y - (one.x * b);

Once you've done that, do a bounding box check by filling in the formula. Say you have a bounding box between vector min and vector max

var outcome_min = b * min.X + a; //we hit the bounding box if outcome_min is > min.y and < max.y
var outcome_max = b * max.X + a; //we hit the bounding box if outcome_max is > min.y and < max.y
//finally, we also hit the box if outcome_min < min.y and outcome_max > max.y or vice versa

you can simplify this by making exceptions for ray-casts along the x or y axis, tiny objects etc, but you get the general idea.

line-poligon intersection is a lot more difficult. I suggest googling for it. there's tons of algoritms, but none are easy to grasp (to me at least).

hope the post makes sense. its late and im tired.

[Stormy]

I'm farmiliar with linear algebra, polar and cartesian tangents and such, thanks anyway. By 'slope' do you mean the polar angle? What I was trying to figure out was a good algorithm for figuring exactly where the ray gets intercepted. From the sounds of it I'll have to loop through each collidable object on screen anyway. Here's what I'm thinking:

Code: Select all

cast the ray from a to b
plot every pixel in the line between a and b and record them in an array
while there are more onscreen objects to check:
  plot the pixels along the edges of the current object and record them in an array
  for every entry in the raycast array:
    check that none of the pixels of our raycast array match the pixels in the current objects edge array
    if one matches, add it to an array of possible collision points
find the closest entry to point a in the possible collision points array and return it


if I was going to check the pixel colour, which I could in this case since I am going to have bold colours and clear collision points but it just doesn't seem to be a good idea, I would do this:

Code: Select all

cast the ray from a to b
plot every pixel in the line between a and b and record them in an array
record the colour of the first pixel in that array
for every entry in the raycast array:
  if the colour of the current pixel is different than the last:
    return it and break loop


Actually that would be quite easy since I only have to check the pixels in the raycast array. Maybe I'll just do that. Thoughts?

[zombie@computer]

Sounds okay, i guess. Like i said, i never worked with Javascript to draw shit. An alternative might be to use matrices (or built in functions) to rotate and translate your images along the raycast (so the raycast becomes the x-axis). That way you only need to check objects that intersect the x-axis and only need to check the pixels at y=0.

[SM Sith Lord]

Damn, you are taking JavaScript to a whole new level.

Looked over your algorithm and this stuff is a little beyond me, but to save time you might think about 1st detecting which objects even have their bounding box penetrated by the ray, and then perform the rest of the collision detection logic on only those objects.

(It seems like determining the actual edge pixels rather than the bounding box would be a much more intensive task.)

[Stormy]

Well here is an experiment I did to check if I could map the pixels out programatically, and it works pretty well.

http://www.modelsforthemasses.com/jsfiddles/absoluteCollision/abs.html

When you press shift the program loops through all drawn elements to see which bounding boxes the mouse is in, then maps the pixels of each line in those bounding boxes, and checks the mouse position against those pixels. This way I am not checking the colors on screen and I am not mapping every single line on screen on every frame. I think this is the only way I can really check collision with a raycast but I need to be able to do it within one frame, which is the part I am having issues with. I think I'll have to map the raycast pixels the same way I do with the lines...

On a side note, if anyone ever uses Math.atan(y/x) in javascript, dump it and use Math.atan2(y, x). It compensates for negative degrees and stuff given by Math.atan() and figures out which sector of the circle you are rotating through. Goddamn cut out like 20 lines of code.

[stoopdapoop]

yeah, atan2 is really nice when working with 2D stuff.

About your algorithm, I think you're messing up by testing collision with pixels. the way you're doing it means that longer lines take longer to check against, and a single diagonal line across a a large canvas would mean tons of extra calculations per test. When you have lots of objects each doing tests like this, it will start getting crazy before you know it. It doesn't scale well.

What zombie said about transform your point against the ray's direction is a much better solution, this also means you can check ray-point collisions in constant (very fast) time.

If you can read C# then I might be able to dig up an old XNA project where I had continuous collision detection for projectiles using raycasts the way we're describing for you.