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; |