comments on raycast

[williame]

lovely! I've adapted this for my own code: http://stackoverflow.com/a/17496872/15721

Here's some issues I looked at when porting:

1) rather than a ray, treat it as a line segment. Then clip this line to world bounds. You then don't need the complex while() loop. Instead, when you increment x you can check if x is beyond end of line and abort; same for y and z. So you end up just checking the dimension that changes each loop, and you don't need radius; to implement a max-distance simply shorten the line you are checking.

2) the if-statements ought to check for <= instead of < to find the nearest edge? Else what if a == b and a < c?

3) I had trouble with the intbounds, and rather than trying to fix it, I use this: return (ds > 0? Math.ceil(s)-s: s-Math.floor(s)) / Math.abs(ds);

4) finally, if you keep your world in 8x8x8 sectors or whatever, you can easily step over whole sectors that are empty by multiplying the coords by 8 etc. So it is easy to adapt this to hierarchical spatial structures e.g. octrees

[kpreid]

Thanks for your comments.

(1) is an interesting idea, and I agree that it would simplify things. I wouldn't necessarily want to make each caller responsible for adjusting the length of the line segment, but that could be a wrapper function providing something like the existing interface. On the other hand, it does entirely remove the option for a raycast of unbounded length — but one never truly wants that anyway. I think I'll adopt this, considering how it simplifies the inner loop.

(Another little optimization I've thought of is to make the caller supply the 'face' object or to pass 3 coordinate arguments; all the callers either ignore it, extract the coordinates or copy it, so allocating is mostly useless.)

(2) Could you describe the problematic case you're thinking of more precisely? If tMaxX is equal to tMaxY, then the outer second branch is taken, and if tMaxX < tMaxZ, then also tMaxY < tMaxZ, so the first branch in there is taken, so it will increment in the y direction, which is a valid choice. As far as I've seen, changing the operators would only cause it to make different-but-acceptable choices when the ray passes exactly through edges/corners. Can you describe what you think happens in a specific case where it would fail? (I agree that <= would be more sensible, but absent a reason I'd rather stick to the original paper's algorithm.)

(3) Please describe a case where intbound returns an incorrect result. I am aware that people have had trouble with negative coordinates, but as far as I know those were cases of incorrectly implementing mod as %.

(4) Certainly, but I don't have a chunked or octree world yet. In the event I switch to an infinite world, I will probably do chunks including such an optimization.

[williame]

I think (2) and (3) are distractions; I think (2) is really when I re-rolled the decision tree in my own code to keep it tidy (but add extra comparisons). I had problems with negative coordinates and your mod, but I didn't try and fix it, I simply imagined that Math.floor and Math.ceiling are likely to be faster than the % operator. You could also use |0, which is the missing Math.trunc, and which is used by V8 and FF to optimise by knowing things are integer. In a speed test |0 probably wins. Something like trunc = s|0; return ds>0? ((1+trunc)-s)/ds: (s-(trunc-1))/-ds;

The face vector is definitely likely to be fairly hot. All temporary allocations hurt game loops! I pass around an int instead, because this makes a lot of sense in my own code: 0=LEFT, 1=RIGHT and so on. I have an enum of these. It dramatically speeds up a lot of other code - from meshing to ambient occlusion shading - http://0fps.wordpress.com/2013/07/03/ambient-occlusion-for-minecraft-like-worlds/ - if you store a bitmask of neighbours in each block itself.