1 /** 2 Copyright: Copyright (c) 2015-2017 Andrey Penechko. 3 License: $(WEB boost.org/LICENSE_1_0.txt, Boost License 1.0). 4 Authors: Andrey Penechko. 5 */ 6 7 module voxelman.utils.trace; 8 9 import std.math : floor, abs; 10 import voxelman.math; 11 import voxelman.graphics : Batch; 12 import voxelman.world.block : sideFromNormal; 13 14 enum bool drawDebug = false; 15 16 // Implementation of algorithm found at 17 // http://playtechs.blogspot.co.uk/2007/03/raytracing-on-grid.html 18 19 /// Returns true if block was hit 20 bool traceRay( 21 bool delegate(ivec3) isBlockSolid, 22 vec3 startingPosition, // starting position 23 vec3 rayDirection, // direction 24 double maxDistance, 25 out vec3 hitPosition, // resulting position hit 26 out ivec3 hitNormal, // normal of hit surface 27 ref Batch batch) 28 { 29 assert(rayDirection != vec3(0,0,0), "Raycast in zero direction!"); 30 31 rayDirection *= maxDistance; 32 33 double x0 = startingPosition.x; 34 double y0 = startingPosition.y; 35 double z0 = startingPosition.z; 36 double x1 = startingPosition.x + rayDirection.x; 37 double y1 = startingPosition.y + rayDirection.y; 38 double z1 = startingPosition.z + rayDirection.z; 39 40 int x = cast(int)floor(x0); 41 int y = cast(int)floor(y0); 42 int z = cast(int)floor(z0); 43 44 double dt_dx = abs(1.0 / rayDirection.x); 45 double dt_dy = abs(1.0 / rayDirection.y); 46 double dt_dz = abs(1.0 / rayDirection.z); 47 48 int n = 1; 49 50 int inc_x; 51 int inc_y; 52 int inc_z; 53 54 double t_next_x; 55 double t_next_y; 56 double t_next_z; 57 58 if (rayDirection.x > 0) 59 { 60 inc_x = 1; 61 n += cast(int)floor(x1) - x; 62 t_next_x = (floor(x0) + 1 - x0) * dt_dx; 63 } 64 else if (rayDirection.x < 0) 65 { 66 inc_x = -1; 67 n += x - cast(int)floor(x1); 68 t_next_x = (x0 - floor(x0)) * dt_dx; 69 } 70 else 71 { 72 inc_x = 0; 73 t_next_x = dt_dx; // infinity 74 } 75 76 if (rayDirection.z > 0) 77 { 78 inc_z = 1; 79 n += cast(int)floor(z1) - z; 80 t_next_z = (floor(z0) + 1 - z0) * dt_dz; 81 } 82 else if (rayDirection.z < 0) 83 { 84 inc_z = -1; 85 n += z - cast(int)floor(z1); 86 t_next_z = (z0 - floor(z0)) * dt_dz; 87 } 88 else 89 { 90 inc_z = 0; 91 t_next_z = dt_dz; // infinity 92 } 93 94 if (rayDirection.y > 0) 95 { 96 inc_y = 1; 97 n += cast(int)floor(y1) - y; 98 t_next_y = (floor(y0) + 1 - y0) * dt_dy; 99 } 100 else if (rayDirection.y < 0) 101 { 102 inc_y = -1; 103 n += y - cast(int)floor(y1); 104 t_next_y = (y0 - floor(y0)) * dt_dy; 105 } 106 else 107 { 108 inc_y = 0; 109 t_next_y = dt_dy; // infinity 110 } 111 112 double t = 0; 113 static if (drawDebug) 114 vec3 prevPos = startingPosition; 115 116 for (; n > 0; --n) 117 { 118 if (isBlockSolid(ivec3(x, y, z))) 119 { 120 hitPosition = vec3(x, y, z); 121 return true; 122 } 123 124 if (t_next_x < t_next_y) 125 { 126 if (t_next_x < t_next_z) 127 { 128 x += inc_x; 129 t = t_next_x; 130 t_next_x += dt_dx; 131 hitNormal = ivec3(-inc_x, 0, 0); 132 } 133 else 134 { 135 z += inc_z; 136 t = t_next_z; 137 t_next_z += dt_dz; 138 hitNormal = ivec3(0, 0, -inc_z); 139 } 140 } 141 else 142 { 143 if (t_next_y < t_next_z) 144 { 145 y += inc_y; 146 t = t_next_y; 147 t_next_y += dt_dy; 148 hitNormal = ivec3(0, -inc_y, 0); 149 } 150 else 151 { 152 z += inc_z; 153 t = t_next_z; 154 t_next_z += dt_dz; 155 hitNormal = ivec3(0, 0, -inc_z); 156 } 157 } 158 159 static if (drawDebug) 160 { 161 batch.putLine(prevPos, startingPosition + rayDirection*t, 162 colorsArray[sideFromNormal(hitNormal)+2]); 163 prevPos = startingPosition + rayDirection*t; 164 165 batch.putCubeFace( 166 vec3(x, y, z), 167 vec3(1, 1, 1), 168 sideFromNormal(hitNormal), 169 Colors.black, 170 false); 171 } 172 } 173 174 return false; 175 }