3d voxel picking with Bresenham’s line algorithm

After some research on 3d picking it came to me that most obvious solution for non-octree ‘voxel’ world would be plotting a 3d line through the chunks grid, checking for collision with blocks along the line. And that is where Bresenham’s line algorithm is really usefull. Took me a while to find 3d adopted pascal version so I’m repostiong it here for anyone to use :P. For my project I modified it to go certain amount of steps before failing if no collision is found.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
procedure SwapAB(var a,b :integer);
var
    c   :integer;
begin
    c := a;
    a := b;
    b := c;
end;
 
procedure line3D(x0,y0,z0,x1,y1,z1:integer);
var
    x, delta_x, step_x  :integer;
    y, delta_y, step_y  :integer;
    z, delta_z, step_z  :integer;
    swap_xy, swap_xz            :boolean;
    drift_xy, drift_xz          :integer;
    cx, cy, cz,stepCount        :integer;
begin
    //start and end points (change these values)
    //x0 := 0     x1 := -2
    //y0 := 0     y1 := 5
    //z0 := 0     z1 := -10
 
    //'steep' xy Line, make longest delta x plane
    swap_xy := Abs(y1 - y0) > Abs(x1 - x0);
    if swap_xy then begin
        SwapAB(x0, y0);
        SwapAB(x1, y1);
    end;
 
    //do same for xz
    swap_xz := Abs(z1 - z0) > Abs(x1 - x0);
    if swap_xz then begin
        SwapAB(x0, z0);
        SwapAB(x1, z1);
    end;
 
    //delta is Length in each plane
    delta_x := Abs(x1 - x0);
    delta_y := Abs(y1 - y0);
    delta_z := Abs(z1 - z0);
 
    //drift controls when to step in 'shallow' planes
    //starting value keeps Line centred
    drift_xy  := delta_x div 2;
    drift_xz  := (delta_x div 2);
 
    //direction of line
    step_x := 1;  if (x0 > x1) then  step_x := -1;
    step_y := 1;  if (y0 > y1) then  step_y := -1;
    step_z := 1;  if (z0 > z1) then  step_z := -1;
 
    //starting point
    y := y0;
    z := z0;
 
    //step through longest delta (which we have swapped to x)
    x:= x0;
    stepCount:=0;
    while (stepCount<256) do begin
        inc(stepCount);
        //copy position
        cx := x;    cy := y;    cz := z;
 
        //unswap (in reverse)
        if swap_xz then SwapAB(cx, cz);
        if swap_xy then SwapAB(cx, cy);
 
        //spit results
        log(': ' + inttostr(cx) + ', ' + inttostr(cy) + ', ' + inttostr(cz));
 
        //update progress in other planes
        drift_xy := drift_xy - delta_y;
        drift_xz := drift_xz - delta_z;
 
        //step in y plane
        if drift_xy < 0 then begin
            y := y + step_y;
            drift_xy := drift_xy + delta_x;
        end;
        //same in z
        if drift_xz < 0 then begin
            z := z + step_z;
            drift_xz := drift_xz + delta_x;
        end;
        x:=x+step_x;
    end;
end;

picking and culling

Leave a Reply

Your email address will not be published. Required fields are marked *