WebGL2 : 074 : Voxel Ray Intersection, (almost) completed in Delphi

[SkybuckFlying]

Hello,

I took your code from javascript, your github and your great youtube video web gl2 lessons and I was impressed and convinced that you had the most important parts of the algorithm down, much much much better than understand.

So I gave your code a conversion last, because I also wanted to try other people's code and also my own. But eventually I decided to turn your code into javascript code and then I noticed your algorithm wasn't yet fully complete. Or maybe it is, I just realized, you may want to trace the entire ray for multiple collections, that is valid ofcourse... and then you could extend the algorithm a bit further with ray ids and check for objects in multiple voxels and blabla, but if you just want to render voxels like you seem to do, then it would be nice if the ray just terminate within it's segment length basically the ray length and it would also be nice if it stayed within some virtual boundary.

So anyway I extended and fixed your code, kinda intertwined my own code to more or less complete it.

The only thing I ripped out of for now is the ray/bounding box intersection thing because I am not that very yet in the lessons and don't know yet how to do it perfectly and I want to investigate that later.

But anyway what I am trying to write to you is that here is the Delphi code and maybe then you can convert it back to JavaScript code:

The only things you need to add to your own code or change it is
mCellWidth, mCellHeight, mCellDepth

and add some mBoundaryMinX, mBoundaryMaxX, mBoundaryMinY, mBoundaryMaxY,mBoundaryMinZ, mBoundaryMaxZ variables

there is one thing I am unsure about and that is

these lines of code:
if (rayDirX > 0) then xOut := mBoundaryMaxX else xOut := mBoundaryMinX-1;
I think it should have been
if (rayDirX > 0) then xOut := mBoundaryMax+1 else xOut := mBoundaryMinX-1;
but apperently then it goes out of the grid, don't know exactly why yet... maybe cause then it's one wall too far...

I want to port this code later to C/C++ so I didn't bother with any structures or files or anything because that makes it harder to use in other project... the way it is written right now makes it easier to translate to other languages and use it there.

I intend to use this for OpenXCom project, maybe, most likely if I can also get that bounding box working and I will surely test this code somewhere, I already tested it pretty intensively on a grid, but more testing is always good.

Maybe this code will help or inspire you to finish yours, cause yours did not have a "fully fledged loop" it would just do 30 miserable tries =D and that is nononononno cheating, most have good end loop, very important for me at least and anybody else that wants some good peformance and doesn't want to go outside of important data structures for collision detection and such.

Thank you for your work, together we did something amazing as far as I am concerned and it's still not entirely finished but pretty damn good, only the start can go out of the grind, the end is already inside the grid thanks to this algorithm but ofcourse it's also possible for the line to be completely outside the grid, so that will be the next step to integrate "line"/"ray" vs box intersection testing and what not ! ;)

procedure TForm1.VoxalRayCast
(
rayStartX,
rayStartY,
rayStartZ,

rayStopX,
rayStopY,
rayStopZ : double

);
var
rayDeltaX,rayDeltaY,rayDeltaZ : double;
rayLength : double;
rayDirX, rayDirY, rayDirZ : double;
xDir, yDir, zDir : integer;
ix,iy,iz : integer;
xOut,yOut,zOut : integer;
xBound,yBound,zBound : integer;
xt,yt,zt : double;
xDelta, yDelta, zDelta : double;
ii : integer;
begin
if (RayStartX = RayStopX) and
(RayStartY = RayStopY) and
(RayStartZ = RayStopZ) then
begin
ProcessVoxel
(
Math.floor(rayStartX / mCellWidth),
Math.floor(rayStartY / mCellHeight),
Math.floor(rayStartZ / mCellDepth),

		0,0,0, 0
	);
	exit;
end;


//------------- Calc Voxel Coord Integer(x,y,z)
ix := Math.min( Math.floor(rayStartX / mCellWidth) , MaxCellX );
iy := Math.min( Math.floor(rayStartY / mCellHeight), MaxCellY );
iz := Math.min( Math.floor(rayStartZ / mCellDepth) , MaxCellZ );

rayDeltaX := rayStopX - rayStartX;
rayDeltaY := rayStopY - rayStartY;
rayDeltaZ := rayStopZ - rayStartZ;

rayLength := sqrt( (rayDeltaX*rayDeltaX) + (rayDeltaY*rayDeltaY) + (rayDeltaZ * rayDeltaZ) );

rayDirX := rayDeltaX / rayLength;
rayDirY := rayDeltaY / rayLength;
rayDirZ := rayDeltaZ / rayLength;

//------------- Simplify direction with -1,0,1
if rayDirX > 0 then
begin
	xDir := 1;
end else
if rayDirX = 0 then
begin
	xDir := 0
end else
begin
	xDir := -1;
end;

if rayDirY > 0 then
begin
	yDir := 1;
end else
if rayDirY = 0 then
begin
	yDir := 0
end else
begin
	yDir := -1;
end;

if rayDirZ > 0 then
begin
	zDir := 1;
end else
if rayDirX = 0 then
begin
	zDir := 0
end else
begin
	zDir := -1;
end;

//------------- Index value to exit loop -1,MaxCell
if (rayDirX > 0) then xOut := mCellWidth else xOut := -1;
if (rayDirY > 0) then yOut := mCellHeight else yOut := -1;
if (rayDirZ > 0) then zOut := mCellDepth else zOut := -1;

if (rayDirX > 0) then xOut := mBoundaryMaxX else xOut := mBoundaryMinX-1;
if (rayDirY > 0) then yOut := mBoundaryMaxY else yOut := mBoundaryMinY-1;
if (rayDirZ > 0) then zOut := mBoundaryMaxZ else zOut := mBoundaryMinZ-1;

//------------- Position of the closest boundary line for each axis at the ray direction. Depends on direction.
if (rayDirX >= 0) then xBound := ix+1 else xBound := ix; xBound := xBound * mCellWidth;
if (rayDirY >= 0) then yBound := iy+1 else yBound := iy; yBound := yBound * mCellHeight;
if (rayDirZ >= 0) then zBound := iz+1 else zBound := iz; zBound := zBound * mCellDepth;

//------------- Time for axis //(xBound - inPos.x) / ray.dir.x,
if rayDirX <> 0 then xt := (xBound - rayStartX) / rayDirX else xt := 100000000;
if rayDirY <> 0 then yt := (yBound - rayStartY) / rayDirY else yt := 100000000;
if rayDirZ <> 0 then zt := (zBound - rayStartZ) / rayDirZ else zt := 100000000;

//------------- Delta T for each axis as we traverse one voxel at a time
if rayDirX <> 0 then xDelta := (mCellWidth  * xDir) / rayDirX else xDelta := 100000000;
if rayDirY <> 0 then yDelta := (mCellHeight * yDir) / rayDirY else yDelta := 100000000;
if rayDirZ <> 0 then zDelta := (mCellDepth  * zDir) / rayDirZ else zDelta := 100000000;

// ii; //Voxel Index of a specific axis

mCellNumber := 0;
while true do
begin
	ProcessVoxel( ix, iy, iz, 0,0,0, 0 );

	if(xt < yt) and (xt < zt) then
	begin
		ii := ix + xDir;
		if(ii = xOut) then break;	// When out of bounds of the voxel chunk.
		ix := ii;			// Move to next voxel
		xt := xt + xDelta;		// Move T so the next loop has a chance to move in a different axis
	end else
	if (yt < zt) then begin
		ii := iy + yDir;
		if(ii = yOut) then break;
		iy := ii;
		yt := yt + yDelta;
	end else
	begin
		ii := iz + zDir;
		if(ii = zOut) then break;
		iz := ii;
		zt := zt + zDelta;
	end;

	if (xt > RayLength) and (yt > RayLength) and (zt > RayLength) then
	begin
		ProcessVoxel( ix, iy, iz, 0,0,0, 0 );
		break;
	end;

	mCellNumber := mCellNumber + 1;
end;
//Sample on how to get the intersection point where the voxel was hit.

// var boundPos = (( dir[nAxis] > 0)? iAxis+1 : iAxis) * cellSize, // Position of boundary
// tt = ( boundPos - ray.origin[nAxis] ) / ray.vecLen[nAxis], // Time when at axis boundary
// ip = ray.getPos(tt); // Intersection point on voxel face
// console.log(ip);
end;

Bye for now,
Skybuck Flying

and may you enjoy this code and be the raytracer power with you ! Alwayzzzzzzzz yessszzz bye bye. Haha zzz for all the timez timmmmeeezzz spent on trying to get this working well. Also numerical stability may be analyzed further ! Yes numerical stability tests will have to be performed still... Yeah I just did some basic tests and it looks pretty good, just some simple line on boundary tests. Your idea to use integers as voxels was pretty interesting maybe even brilliant and I recommend you do that anyway, and don't use any cell scaling unless you really want to, because otherwise you may risk floating point instability, then again it probably won't be so bad cause your code seems to acquire the cell boundaries/chunk boundaries quite nicely.

I solve it by making sure the line stays within (mBoundaryMaxX * mCellWidth)-1

So this -1 represents your idea of simply subtracting one little integer/voxel from this quantity to keep things stable and inside ! ;) =D