I have a grid of blocks which are 1x1x1, which can either be ‘empty’ or ‘solid’. I have a Ray (the purple point+line) and I would like to find where it intersects a solid block, and the normal of that intersection (the blue point+arrow).
In pure Lua (i.e. not using FindPartOnRay), how would I go about doing this? I’ve looked online and tried implementing a couple algorithms but it didn’t work correctly, and I didn’t quite understand them properly.
Any reason why you don’t want to use FindPartOnRay in the first place?
These blocks aren’t real parts, they’re data stored in a Lua array, so using FindPartOnRay would not be viable. The photo in the OP is just for reference.
You could turn them into real parts and then use raycast, if you make them invisible and non-cancollide and use RayCastWithWhitelist
I can’t do this as the actual grid of blocks is extremely large. There are over one million blocks, and the cost of initialising and destroying those instances would freeze the game for a short while.
I see. If you want to raycast on a block grid then you first need to define the ray. The ray as normal, has an origin and a direction. The line equation then is
Origin+Length*Direction
Then we have to find out when the line enters a new a grid-cell. This happens when a coordinate “crosses” a whole number boundary, so when for example the x-coordinate changes from 2.4 to 1.8 this would represent entering a new block on the grid. So you can go in intervals of Length 1 and check wether you’re in a new grid cell by looking at the change in x,y and z coordinates and then check if you hit a block by checking if the cell is solid. If it’s not you keep moving along in the direction of the ray.
I saw this solution some places online, but it wouldn’t be accurate. Consider this case:
Even though we are incrementing by a length of 1 each time, the ray can still cut corners. It’d be much more ideal if there was a way of getting the precise hit location algebraically.
I’ve found a paper online which appears to detail a method which may work.
Link: http://www.cse.yorku.ca/~amana/research/grid.pdf
I’ll mark this thread as solved since this seems to answer the question.
I still believe the old algorithm can be saved, if you check wether you’ve crossed more than a single whole number boundary. The algorithm in the pdf seems to be way better though.
