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