-4

The given problem is to find a way to efficiently return all boxes hit by a ray.

So I came up with an idea but I want to know your opinion before I waste time in programming something not working.

Basically, the idea is to have a grid of boxes with height = width, all of these boxes are the same size and they don't have a gap between each other, I also have a function to calculate the box index which belongs to a point.(in which box the point is)

Now I calculate a box around the grid and calculate the hit points of a ray with the edges. So I know the intersection points and of course the direction of the rays, now I take the direction, normalize it and divide it by 2. ( I'm not really sure if I need /2 but I feel better with it) The resulting vector is now my "step size". (I call this vector v) So if I take now my first intersection point add v, calculate the box which belongs to the resulting point and does this again and again until I reach my second intersection point I shouldn't miss any box. (right?)

But I'm not sure about that so I ask for your opinion.

Kenster
  • 23,465
  • 21
  • 80
  • 106
noName
  • 132
  • 1
  • 9
  • 2
    `So I came up with an idea but I want toknow your oppinion before I waste time in programming something not working.` It's never a waste of time to program your solution to see if it's working. – biziclop May 26 '17 at 13:00
  • 3
    I'm voting to close this question as off-topic because the author does not even try to implement and test his idea himself. – MrSmith42 May 26 '17 at 13:08
  • Sounds like ray tracing: https://en.wikipedia.org/wiki/Ray_tracing_(graphics) – duffymo May 26 '17 at 13:23
  • By the way, here's a hint: a ray will enter and exit each block it touches in exactly one location. The exit location is the same as the entry location into the next block. – biziclop May 26 '17 at 13:25
  • https://stackoverflow.com/questions/12367071/how-do-i-initialize-the-t-variables-in-a-fast-voxel-traversal-algorithm-for-ray/12370474#12370474 – MBo May 27 '17 at 08:01

1 Answers1

2

This algorithm does not work completely, because in any given square you can take a path through it (by cutting corners) that was a lower distance than whatever you put your step size as. This means that, no matter what you make your step size is, certain vectors will cause this function to omit blocks. That being said, if you use a smaller step size (say v=.05), this isn't a bad estimation algorithm (supposing the grid isn't too large).

Edit: Here is an algorithm that will work. Do the step size thing you are doing with step size < 1 (I think v = .9 should be fine), but after each step, check the relation of each box to the previous one. If you are in the same box or an adjacent box, do nothing. If you are in a diagonal box, you probably passed through an adjacent box to get there. Figure out if and which one it was, and also add it to your list.

Owen Cummings
  • 68
  • 7