How to implement DDA algorythm for 3D visualisation in javascript?

364 views Asked by At

I'm working on a voxel engine and i have problem with my DDA algorythm, the engine is written in javascript. The data is a basic 3D grid. For now, the algorythm look like that :


function RayDDA(Xs,Zs,d,xB,yB) {
                var directionVector = [Math.round(Xs*100000000)/100000000,Math.round(d*100000000)/100000000,Math.round(Zs*100000000)/100000000]
                
                var step = [0,0,0]
                var invDir = [0,0,0]
                var T = [0,0,0]
                var DeltaT = [0,0,0]
                var VoxelIncr = [0,0,0]
                var CurrentV = [camera[0],camera[1],camera[2]]
                
                for (var i = 0;i<3;i++) {
                    if (directionVector[i] != 0) {
                        if (directionVector[i]<0) {
                            step[i] = -1
                        }
                        else {
                            step[i] = 1
                        }
                        invDir[i] = 1/directionVector[i]
                        T[i] = CurrentV[i]-directionVector[i]
                        //T[i] = Math.sqrt((CurrentV[0]-directionVector[0])**2+(CurrentV[1]-directionVector[1])**2+(CurrentV[2]-directionVector[2])**2)
                    }
                    else {
                        invDir[i] = 100000000000000011111
                        T[i] = 111111111111111102221
                    }
                }
                
                for (var i =0;i<3;i++) {
                    DeltaT[i]=invDir[i]
                }
                
                while (true) {
                    VoxelIncr[0] = (T[0]<=T[1] && T[0]<=T[2])
                    VoxelIncr[1] = (T[1]<=T[0] && T[1]<=T[2])
                    VoxelIncr[2] = (T[2]<=T[0] && T[2]<=T[1])
                    
                    T[0]+=DeltaT[0]
                    T[1]+=DeltaT[1]
                    T[2]+=DeltaT[2]
                    
                    CurrentV[0]+=VoxelIncr[0]*step[0]
                    CurrentV[1]+=VoxelIncr[1]*step[1]
                    CurrentV[2]+=VoxelIncr[2]*step[2]
                    
                    var rotateDir = [CurrentV[0],CurrentV[1],CurrentV[2]]
                    if (Math.sqrt(CurrentV[0]**2+CurrentV[1]**2+CurrentV[2]**2)>ray_length) {
                        break
                    }
                    if (parseInt(rotateDir[2]) < map.length && parseInt(rotateDir[1]) < map[0].length && parseInt(rotateDir[0]) < map[0][0].length && parseInt(rotateDir[2]) >= 0 && parseInt(rotateDir[1]) >= 0 && parseInt(rotateDir[0]) >= 0 && map[parseInt(rotateDir[2])][parseInt(rotateDir[1])][parseInt(rotateDir[0])][0] == 1) {
                        //drawn the pixel
                        break
                    }
                }
            }

The algorythm come from this paper : The pdf

What did i do wrong?

EDIT : so at the end i found the problem. In fact, i have forgotten to put some value. But for the people intersted in raycast engine : here's the DDA algorithm in javascript.

1

There are 1 answers

1
Druide On BEST ANSWER

So all is my fault, i forgot to copy correctly the algorithm, so here's the correct code :

function RayDDA(Xs,Zs,d,xB,yB) {
                
                var directionVector = rotateZ(Math.round(Xs*100000000)/100000000,Math.round(d*100000000)/100000000,Math.round(Zs*100000000)/100000000,direction[0])
                
                var step = [0,0,0]
                var invDir = [0,0,0]
                var T = [0,0,0]
                var DeltaT = [0,0,0]
                var VoxelIncr = [0,0,0]
                var CurrentV = [camera[0],camera[1],camera[2]]
                
                for (var i = 0;i<3;i++) {
                    if (directionVector[i] != 0) {
                        if (directionVector[i]<0) {
                            step[i] = -1
                        }
                        else {
                            step[i] = 1
                        }
                        invDir[i] = Math.abs(1/directionVector[i])
                        T[i] = CurrentV[i]-directionVector[i]
                    }
                    else {
                        invDir[i] = 100000000000000011111
                        T[i] = 111111111111111102221
                    }
                }
                
                for (var i =0;i<3;i++) {
                    DeltaT[i]=invDir[i]
                }
                
                while (true) {
                    if (T[0]<=T[1] && T[0]<=T[2]) {
                        VoxelIncr[0] = 1
                    }
                    else {
                        VoxelIncr[0] = 0
                    }
                    
                    if (T[1]<=T[0] && T[1]<=T[2]) {
                        VoxelIncr[1] = 1
                    }
                    else {
                        VoxelIncr[1] = 0
                    }
                    
                    if (T[2]<=T[1] && T[2]<=T[0]) {
                        VoxelIncr[2] = 1
                    }
                    else {
                        VoxelIncr[2] = 0
                    }
                    
                    T[0]+=DeltaT[0]*VoxelIncr[0]
                    T[1]+=DeltaT[1]*VoxelIncr[1]
                    T[2]+=DeltaT[2]*VoxelIncr[2]
                    
                    CurrentV[0]+=VoxelIncr[0]*step[0]
                    CurrentV[1]+=VoxelIncr[1]*step[1]
                    CurrentV[2]+=VoxelIncr[2]*step[2]
                    var rotateDir = [CurrentV[0],CurrentV[1],CurrentV[2]]
                    if (Math.sqrt(CurrentV[0]**2+CurrentV[1]**2+CurrentV[2]**2)>ray_length) {
                        break
                    }
                    if (parseInt(rotateDir[2]) < map.length && parseInt(rotateDir[1]) < map[0].length && parseInt(rotateDir[0]) < map[0][0].length && parseInt(rotateDir[2]) >= 0 && parseInt(rotateDir[1]) >= 0 && parseInt(rotateDir[0]) >= 0 && map[parseInt(rotateDir[2])][parseInt(rotateDir[1])][parseInt(rotateDir[0])][0] == 1) {
                        var color = map[parseInt(rotateDir[2])][parseInt(rotateDir[1])][parseInt(rotateDir[0])][1]
                        ctx.fillStyle = 'rgb('+color[0]+","+color[1]+","+color[2]+")"
                        ctx.fillRect(xB*canvas.width/resolution[0],yB*canvas.height/resolution[1],canvas.width/resolution[0],canvas.height/resolution[1]);
                        break
                    }
                }
            }