Voxel raycasting algorithm is slighty offset

[index_nil]

I’m trying to raycast through a lua table of voxels, using this algorithm http://www.cse.yorku.ca/~amana/research/grid.pdf

My solution is slightly incorrect though.

(The purple line is the theoretical line, the transparent blocks are where it traversed, as shown, it didn’t traverse all blocks inside of the line.)

function WorldController:Raycast(Origin : Vector3, Direction : Vector3)	
	workspace.RaycastDebug:ClearAllChildren()
	
	local MaxDistance = Direction.Magnitude
	local End = Origin+Direction
		
	local RayPosition = Vector3.new(math.floor(Origin.X), math.floor(Origin.Y), math.floor(Origin.Z))
	Direction = (End-RayPosition).Unit
	
	local Step = Direction:Sign()

	local tDelta = Vector3.new(
		math.abs(1/Direction.X),	
		math.abs(1/Direction.Y),	
		math.abs(1/Direction.Z)
	)

	local tMax = Vector3.new(
		Direction.X < 0 and ((Origin.X - RayPosition.X) * tDelta.X) or ((RayPosition.X + 1) - Origin.X) * tDelta.X,
		Direction.Y < 0 and ((Origin.Y - RayPosition.Y) * tDelta.Y) or ((RayPosition.Y + 1) - Origin.Y) * tDelta.Y,
		Direction.Z < 0 and ((Origin.Z - RayPosition.Z) * tDelta.Z) or ((RayPosition.Z + 1) - Origin.Z) * tDelta.Z
	)  
	MakeLine(Origin, Origin+Direction*MaxDistance, 0.3)
	

	print("tMax: ", tMax)
	
	local function IsBlockPositionJustInBounds(Position)
		return (
			Position.X <= BlockLibrary.WorldBorder-1 
			and Position.X >= -BlockLibrary.WorldBorder 
			and Position.Y >= 0
			and Position.Y <= BlockLibrary.WorldBorder-1
			and Position.Z <= BlockLibrary.WorldBorder-1
			and Position.Z >= -BlockLibrary.WorldBorder
		)
		
	end
	
	local p = Instance.new("Part", workspace.RaycastDebug)
	p.Anchored = true 
	p.CanCollide = false 
	p.Size = Vector3.new(4, 4, 4)
	p.Transparency = 0.4
	p.Color = Color3.fromRGB(24, 97, 255)
	p.Position = RayPosition * 4

	
	local Distance = 0
	local Block
	while Distance < MaxDistance and Block == nil do
			
		if tMax.X < tMax.Y then
			if tMax.X < tMax.Z then
				RayPosition+=Vector3.new(Step.X, 0, 0)
				tMax+=Vector3.new(tDelta.X, 0, 0)
				Distance = tMax.X


			else 
				RayPosition+=Vector3.new(0, 0, Step.Z)
				tMax+=Vector3.new(0, 0, tDelta.Z)
				Distance = tMax.Z

			end
		else 
			if tMax.Y < tMax.Z then
				RayPosition+=Vector3.new(0, Step.Y, 0)
				tMax+=Vector3.new(0, tDelta.Y, 0)
				Distance = tMax.Y

			else 
				RayPosition+=Vector3.new(0, 0, Step.Z)
				tMax+=Vector3.new(0, 0, tDelta.Z)
				Distance = tMax.Z
			end
		end
		
		local p = Instance.new("Part", workspace.RaycastDebug)
		p.Anchored = true 
		p.CanCollide = false 
		p.Size = Vector3.new(4, 4, 4)
		p.Transparency = 0.4
		p.Position = RayPosition * 4

		Block = WorldController:GetBlock(RayPosition)
		
		if IsBlockPositionJustInBounds(RayPosition) ~= true then
			break
		end
		
	end
	
	local Normal = Vector3.new(
		Distance == tMax.X and -Step.X or 0,
		Distance == tMax.Y and -Step.Y or 0,
		Distance == tMax.Z and -Step.Z or 0

	)
	print("Normal: ", Normal)
	
	local p = Instance.new("Part", workspace.RaycastDebug)
	p.Anchored = true 
	p.CanCollide = false 
	p.Size = Vector3.new(2, 2, 2)
	p.Transparency = 0.1
	p.Color = Color3.fromRGB(229, 255, 0)
	p.Position = Origin*4+Direction*Distance * 4

	
	return {
		BlockPosition = RayPosition,
		Block = Block,
		Position = Origin*4+Direction*tDelta * 4,
		Normal = Normal
	}

end

(sorry the code is a bit of a mess, from debugging and constantly rewriting stuff.)
Does anyone know why? I suspect it might be the calculation of tMax, I’ve tried countless of different methods for calculating it.

[haotian2006]

After doing a bit of debugging it was indeed a rounding error and not offsetting the grid properly

floor(x) → floor(x+.5)

Part.Position = RayPosition → Part.Position = RayPosition + Vector3.one*.5

offsetting RayPosition by .5 should give you the correct results. I’ve attached the place file It is mainly your code with a few modifications

Place1.rbxl (58.1 KB)

[haotian2006]

[index_nil]

Part.Position = RayPosition → Part.Position = RayPosition + Vector3.one*.5

Surprisingly this works, but it’s just a visual offset though, the actual calculations and checks are still being performed incorrectly.

I tried doing this instead: RayPosition += Vector3.one*.5 After the tMax calculation, and that also achieved the same results. Doing it before the tMax calculation does not work, and this goes to show that there is likely something wrong in the actual tMax calculation. Do you have any idea what that could be?

[haotian2006]

Did you check out the test place. And for calculations also apply the offset

[index_nil]

Yes. For the 2nd part, did you see the second part of my message? And I shouldn’t have to make this clear, but applying an offset of 0.5 units is not viable, everything in the game is aligned to a 1 unit grid.

[haotian2006]

The problem is still with your offset

I modified how tMax is calculated by offsetting it by .5

DebugFolder=  workspace.RaycastDebug
local function drawLine(startVector, endVector,color,name)

    local linePart = Instance.new("Part")
    linePart.Size = Vector3.new(0.2, 0.2, (startVector - endVector).Magnitude)
    linePart.Anchored = true
    linePart.CanCollide = false
    linePart.Name = name or ""
    linePart.Material = Enum.Material.Neon
    linePart.Position = (startVector + endVector) / 2

    local rotation =  CFrame.lookAt(startVector+(endVector-startVector)/2,endVector)
    linePart.CFrame = rotation

    linePart.BrickColor = color or BrickColor.new("Bright red") 

    linePart.Parent = DebugFolder
end


local function round(x)
    return math.floor(x+.5)--+ workspace.Offset.Value
end

local offset = Vector3.one*.5

function Raycast(Origin : Vector3, Direction : Vector3)	
    DebugFolder:ClearAllChildren()

    local MaxDistance = Direction.Magnitude
    local End = Origin+Direction
    local oriDir = Direction

local RayPosition = Vector3.new(round(Origin.X), round(Origin.Y), round(Origin.Z))
    Direction = Direction.Unit

    local Step = Direction:Sign()

    local tDelta = Vector3.new(
        math.abs(1/Direction.X),	
        math.abs(1/Direction.Y),	
        math.abs(1/Direction.Z)
    )

    local tMax = Vector3.new(
        Direction.X <= 0 and ((Origin.X - RayPosition.X+.5) * tDelta.X) or ((RayPosition.X + .5) - Origin.X) * tDelta.X,
        Direction.Y <= 0 and ((Origin.Y - RayPosition.Y+.5) * tDelta.Y) or ((RayPosition.Y + .5) - Origin.Y) * tDelta.Y,
        Direction.Z <= 0 and ((Origin.Z - RayPosition.Z+.5) * tDelta.Z) or ((RayPosition.Z + .5) - Origin.Z) * tDelta.Z
    )  
    drawLine(Origin*4, (Origin+oriDir)*4)


    print("tMax: ", tMax)

    local grid = RayPosition-- + offset

    local p = Instance.new("Part", workspace.RaycastDebug)
    p.Anchored = true 
    p.CanCollide = false 
    p.Size = Vector3.new(4, 4, 4)
    p.Transparency = 0.4
    p.Color = Color3.fromRGB(24, 97, 255)
    p.Position =(grid) * 4


    local Distance = 0
    local Block
    while Distance < MaxDistance  do

        grid = RayPosition -- offset

        local p = Instance.new("Part", workspace.RaycastDebug)
        p.Anchored = true 
        p.CanCollide = false 
        p.Size = Vector3.new(4, 4, 4)
        p.Transparency = 0.4
        p.Position = (grid) * 4

        local p = Instance.new("Part", workspace.RaycastDebug)
        p.Name = "small"
        p.Anchored = true 
        p.CanCollide = false 
        p.Size = Vector3.new(1, 1, 1)*.5
        p.Transparency = 0
        local hitPos = Vector3.new(Origin.X + Distance* Direction.X,Origin.Y + Distance* Direction.Y,Origin.Z + Distance* Direction.Z)
        p.Position = hitPos * 4

        if tMax.X < tMax.Y then
            if tMax.X < tMax.Z then
                RayPosition+=Vector3.new(Step.X, 0, 0)
                Distance = tMax.X
                tMax+=Vector3.new(tDelta.X, 0, 0)


            else 
                RayPosition+=Vector3.new(0, 0, Step.Z)
                Distance = tMax.Z
                tMax+=Vector3.new(0, 0, tDelta.Z)

            end
        else 
            if tMax.Y < tMax.Z then
                RayPosition+=Vector3.new(0, Step.Y, 0)
                Distance = tMax.Y
                tMax+=Vector3.new(0, tDelta.Y, 0)

            else 
                RayPosition+=Vector3.new(0, 0, Step.Z)
                Distance = tMax.Z
                tMax+=Vector3.new(0, 0, tDelta.Z)
            end
        end




    end

    local Normal = Vector3.new(
        Distance == tMax.X and -Step.X or 0,
        Distance == tMax.Y and -Step.Y or 0,
        Distance == tMax.Z and -Step.Z or 0

    )
    print("Normal: ", Normal)

    local p = Instance.new("Part", workspace.RaycastDebug)
    p.Anchored = true 
    p.CanCollide = false 
    p.Size = Vector3.new(2, 2, 2)
    p.Transparency = 0.1
    p.Color = Color3.fromRGB(229, 255, 0)
    p.Position = Origin*4+Direction*Distance * 4


end



local char = game.Players.LocalPlayer.Character or game.Players.LocalPlayer.CharacterAdded:Wait()


game:GetService("UserInputService").InputBegan:Connect(function(input: InputObject, gameProcessedEvent: boolean) 
    if input.KeyCode == Enum.KeyCode.Q then
        local head = char:FindFirstChild("Head",true)::BasePart
        Raycast(head.Position/4,workspace.CurrentCamera.CFrame.LookVector*100)
    end    
end)

[haotian2006]

The original alg was made it so the block is at corner but because Roblox parts have their position at the center you need to apply an offset to achieve the right results

[index_nil]

Thanks, that adjustment to the tMax calculation solved it. For the RayPosition i just used math.round.

[Yal_f (yal)]

you could just use math.round for this, its what it was made for. you dont need a custom function for adding .5

[haotian2006]

math.round isn’t the same as math.floor(x+.5) and the performance really does not matter since it’s only being used 3 times at the start of a script.