1 /**
2 Copyright: Copyright (c) 2015-2016 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 dlib.math.vector;
11 import voxelman.utils.renderutils : Batch;
12 import voxelman.core.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 }