]> git.localhorst.tv Git - tacos.git/blob - src/world/world.cpp
better ray/floor intersection algorithm
[tacos.git] / src / world / world.cpp
1 #include "Cursor.hpp"
2 #include "Floor.hpp"
3
4 #include <iostream>
5 #include <glm/gtx/io.hpp>
6
7
8 namespace tacos {
9
10 Cursor::Cursor()
11 : vao(0)
12 , buffers{0}
13 , size(3)
14 , offset(0.1f)
15 , mode(HIDDEN) {
16         glGenVertexArrays(1, &vao);
17         glGenBuffers(2, buffers);
18
19         glBindVertexArray(vao);
20         glBindBuffer(GL_ARRAY_BUFFER, buffers[0]);
21         glEnableVertexAttribArray(0);
22         glVertexAttribPointer(0, 3, GL_FLOAT, 0, sizeof(Attributes), reinterpret_cast<const void *>(offsetof(Attributes, position)));
23         glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, buffers[1]);
24         glBindVertexArray(0);
25 }
26
27 Cursor::~Cursor() {
28         glDeleteBuffers(2, buffers);
29         glDeleteVertexArrays(1, &vao);
30 }
31
32 void Cursor::Hide() noexcept {
33         mode = HIDDEN;
34 }
35
36 void Cursor::FloorTile(const Floor &floor, int tile_x, int tile_z) {
37         // TODO: only update if changed
38         mode = FLOOR;
39
40         int x_begin = glm::clamp(tile_x, 0, floor.Width() - size);
41         int x_end = x_begin + size;
42         int z_begin = glm::clamp(tile_z, 0, floor.Depth() - size);
43         int z_end = z_begin + size;
44
45         glBindVertexArray(vao);
46         glBindBuffer(GL_ARRAY_BUFFER, buffers[0]);
47         glBufferData(GL_ARRAY_BUFFER, size * size * sizeof(Attributes), nullptr, GL_DYNAMIC_DRAW);
48         Attributes *attrib = reinterpret_cast<Attributes *>(glMapBuffer(GL_ARRAY_BUFFER, GL_WRITE_ONLY));
49         for (int z = z_begin, index = 0; z < z_end; ++z) {
50                 for (int x = x_begin; x < x_end; ++x, ++index) {
51                         attrib[index].position = glm::vec3(x, floor.GetElevation(x, z) + offset, z);
52                 }
53         }
54         glUnmapBuffer(GL_ARRAY_BUFFER);
55
56         glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, buffers[1]);
57         glBufferData(GL_ELEMENT_ARRAY_BUFFER, (size - 1) * (size - 1) * 6, nullptr, GL_DYNAMIC_DRAW);
58         unsigned char *element = reinterpret_cast<unsigned char *>(glMapBuffer(GL_ELEMENT_ARRAY_BUFFER, GL_WRITE_ONLY));
59         for (int z = 0, index = 0; z < size - 1; ++z) {
60                 for (int x = 0; x < size - 1; ++x, ++index) {
61                         element[index * 6 + 0] = (z + 0) * size + (x + 0);
62                         element[index * 6 + 1] = (z + 0) * size + (x + 1);
63                         element[index * 6 + 2] = (z + 1) * size + (x + 0);
64                         element[index * 6 + 3] = (z + 0) * size + (x + 1);
65                         element[index * 6 + 4] = (z + 1) * size + (x + 1);
66                         element[index * 6 + 5] = (z + 1) * size + (x + 0);
67                 }
68         }
69         glUnmapBuffer(GL_ELEMENT_ARRAY_BUFFER);
70         glBindVertexArray(0);
71 }
72
73 void Cursor::Draw() const noexcept {
74         glBindVertexArray(vao);
75         glDrawElements(GL_TRIANGLES, (size - 1) * (size - 1) * 6, GL_UNSIGNED_BYTE, nullptr);
76 }
77
78
79 constexpr int Floor::VAO_DIVISOR;
80
81 Floor::Floor(int w, int d)
82 : width(w)
83 , depth(d)
84 , elevation(w * d)
85 , tile_width(width - 1)
86 , tile_depth(depth - 1)
87 , unclean_width(tile_width % VAO_DIVISOR)
88 , unclean_depth(tile_depth % VAO_DIVISOR)
89 , vao_width(tile_width / VAO_DIVISOR + bool(unclean_width))
90 , vao_depth(tile_depth / VAO_DIVISOR + bool(unclean_depth))
91 , vaos(vao_width * vao_depth)
92 , general_elements(vao_width * vao_depth)
93 , unclean_width_elements(general_elements + bool(unclean_width))
94 , unclean_depth_elements(unclean_depth ? (unclean_width_elements + 1) : general_elements)
95 , unclean_corner_elements(std::max(unclean_width_elements, unclean_depth_elements) + (unclean_width && unclean_depth))
96 , buffers(unclean_corner_elements + 1) {
97         glGenVertexArrays(vaos.size(), vaos.data());
98         glGenBuffers(buffers.size(), buffers.data());
99         int x_end = vao_width - bool(unclean_width);
100         int z_end = vao_depth - bool(unclean_depth);
101         for (int z = 0; z < z_end; ++z) {
102                 for (int x = 0; x < x_end; ++x) {
103                         SetupVAO(z * vao_width + x, buffers[general_elements], (VAO_DIVISOR + 1) * (VAO_DIVISOR + 1));
104                 }
105         }
106         // always fill general element buffer (there won't be one needed for maps with x or z less than divisor,
107         // but that shouldn't happen in practice, only during tests in which case I don't care about the overhead
108         FillElementBuffer(buffers[general_elements], VAO_DIVISOR, VAO_DIVISOR);
109         if (unclean_width) {
110                 for (int z = 0; z < z_end; ++z) {
111                         SetupVAO(z * vao_width + x_end, buffers[unclean_width_elements], (unclean_width + 1) * (VAO_DIVISOR + 1));
112                 }
113                 FillElementBuffer(buffers[unclean_width_elements], unclean_width, VAO_DIVISOR);
114         }
115         if (unclean_depth) {
116                 for (int x = 0; x < x_end; ++x) {
117                         SetupVAO(z_end * vao_width + x, buffers[unclean_depth_elements], (VAO_DIVISOR + 1) * (unclean_depth + 1));
118                 }
119                 FillElementBuffer(buffers[unclean_depth_elements], VAO_DIVISOR, unclean_depth);
120         }
121         if (unclean_width && unclean_depth) {
122                 SetupVAO(z_end * vao_width + x_end, buffers[unclean_corner_elements], (unclean_width + 1) * (unclean_depth + 1));
123                 FillElementBuffer(buffers[unclean_corner_elements], unclean_width, unclean_depth);
124         }
125 }
126
127 Floor::~Floor() noexcept {
128         glDeleteBuffers(buffers.size(), buffers.data());
129         glDeleteVertexArrays(vaos.size(), vaos.data());
130 }
131
132 void Floor::SetupVAO(int which, GLuint element_buffer, int vertex_count) noexcept {
133         glBindVertexArray(vaos[which]);
134         glBindBuffer(GL_ARRAY_BUFFER, buffers[which]);
135         glBufferData(GL_ARRAY_BUFFER, vertex_count * sizeof(Attributes), nullptr, GL_STATIC_DRAW);
136         glEnableVertexAttribArray(0);
137         glVertexAttribPointer(0, 3, GL_FLOAT, 0, sizeof(Attributes), reinterpret_cast<const void *>(offsetof(Attributes, position)));
138         glEnableVertexAttribArray(1);
139         glVertexAttribPointer(1, 3, GL_FLOAT, 0, sizeof(Attributes), reinterpret_cast<const void *>(offsetof(Attributes, normal)));
140         glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, element_buffer);
141 }
142
143 void Floor::FillElementBuffer(GLuint which, int tile_width, int tile_depth) {
144         // unbind VAO so we don't accidentally trash an element buffer binding
145         glBindVertexArray(0);
146         glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, which);
147         glBufferData(GL_ELEMENT_ARRAY_BUFFER, tile_width * tile_depth * sizeof(short) * 6, nullptr, GL_STATIC_DRAW);
148         // TODO: this can return null on error (out of memory in this case)
149         //       might be worth checking eventually
150         short *data = reinterpret_cast<short *>(glMapBuffer(GL_ELEMENT_ARRAY_BUFFER, GL_WRITE_ONLY));
151         for (int z = 0, i = 0; z < tile_depth; ++z) {
152                 for (int x = 0; x < tile_width; ++x, ++i) {
153                         data[i * 6 + 0] = (z + 0) * (tile_width + 1) + (x + 0);
154                         data[i * 6 + 1] = (z + 0) * (tile_width + 1) + (x + 1);
155                         data[i * 6 + 2] = (z + 1) * (tile_width + 1) + (x + 0);
156                         data[i * 6 + 3] = (z + 0) * (tile_width + 1) + (x + 1);
157                         data[i * 6 + 4] = (z + 1) * (tile_width + 1) + (x + 1);
158                         data[i * 6 + 5] = (z + 1) * (tile_width + 1) + (x + 0);
159                 }
160         }
161         glUnmapBuffer(GL_ELEMENT_ARRAY_BUFFER);
162 }
163
164 void Floor::FillAttribBuffer(int vao_x, int vao_z) {
165         glBindBuffer(GL_ARRAY_BUFFER, buffers[vao_z * vao_width + vao_x]);
166         Attributes *data = reinterpret_cast<Attributes *>(glMapBuffer(GL_ARRAY_BUFFER, GL_WRITE_ONLY));
167         glm::ivec2 tiles(Tiles(vao_x, vao_z));
168         for (int z = 0, abs_z = vao_z * VAO_DIVISOR, i = 0; z < tiles.y + 1; ++z, ++abs_z) {
169                 for (int x = 0, abs_x = vao_x * VAO_DIVISOR; x < tiles.x + 1; ++x, ++abs_x, ++i) {
170                         data[i].position = glm::vec3(x, GetElevation(abs_x, abs_z), z);
171                         data[i].normal = GetNormal(abs_x, abs_z);
172                 }
173         }
174         glUnmapBuffer(GL_ARRAY_BUFFER);
175 }
176
177 glm::vec3 Floor::GetNormal(int x, int z) const noexcept {
178         // TODO: not sure about the sign here
179         return normalize(glm::vec3(
180                 ClampedElevation(x - 1, z) - ClampedElevation(x + 1, z),
181                 2.0f,
182                 ClampedElevation(x, z - 1) - ClampedElevation(x, z + 1)
183         ));
184 }
185
186 glm::ivec2 Floor::Tiles(int vao_x, int vao_z) const noexcept {
187         return glm::ivec2(
188                 (unclean_width && vao_x == vao_width - 1) ? unclean_width : VAO_DIVISOR,
189                 (unclean_depth && vao_z == vao_depth - 1) ? unclean_depth : VAO_DIVISOR);
190 }
191
192 int Floor::NumTiles(int vao_x, int vao_z) const noexcept {
193         glm::ivec2 tiles = Tiles(vao_x, vao_z);
194         return tiles.x * tiles.y;
195 }
196
197 int Floor::NumVertices(int vao_x, int vao_z) const noexcept {
198         glm::ivec2 tiles = Tiles(vao_x, vao_z);
199         return (tiles.x + 1) * (tiles.y + 1);
200 }
201
202 void Floor::GenerateVertices() {
203         for (int z = 0; z < vao_depth; ++z) {
204                 for (int x = 0; x < vao_width; ++x) {
205                         FillAttribBuffer(x, z);
206                 }
207         }
208 }
209
210 void Floor::DrawVAO(int vao_x, int vao_z) const noexcept {
211         glBindVertexArray(vaos[vao_z * vao_width + vao_x]);
212         // TODO: this cries for triangle strips
213         glDrawElements(GL_TRIANGLES, NumTiles(vao_x, vao_z) * 6, GL_UNSIGNED_SHORT, nullptr);
214 }
215
216 bool Floor::Intersection(const Ray &ray, glm::vec3 &point) {
217         // see http://www.cse.yorku.ca/~amana/research/grid.pdf and
218         // http://www.flipcode.com/archives/Raytracing_Topics_Techniques-Part_4_Spatial_Subdivisions.shtml section Grid Traversal
219
220         // cache 1/dir to avoid some conditionals and divisions
221         glm::vec3 inverse_direction(ray.InverseDirection());
222
223         // cell indicates the current tile we're considering
224         glm::ivec2 cell(int(ray.origin.x), int(ray.origin.z));
225
226         // holds the distance along the ray to advance by one cell in each direction
227         glm::vec3 tDelta(glm::abs(inverse_direction));
228         // holds the distance along the ray to the next cell boundary
229         // TODO: not sure if that is always correct (e.g. with negative components in ray direction)
230         glm::vec3 tMax(tDelta * (1.0f - glm::fract(ray.origin)));
231
232         // if ray's origin is outside the grid, advance to the first cell it hits
233         float x_near, x_far, z_near, z_far, t_min, t_max;
234         if (cell.x < 0 || cell.x >= width || cell.y < 0 || cell.y >= depth) {
235                 x_near = (-ray.origin.x) * inverse_direction.x;
236                 // subtracting one so the point is in the last cell, rather than after it, when approaching from the far end
237                 x_far = (width - 1 - ray.origin.x) * inverse_direction.x;
238                 z_near = (-ray.origin.z) * inverse_direction.z;
239                 z_far = (depth - 1 - ray.origin.z) * inverse_direction.z;
240                 t_min = std::max(std::min(x_near, x_far), std::min(z_near, z_far));
241                 t_max = std::min(std::max(x_near, x_far), std::max(z_near, z_far));
242                 if (t_max < 0.0f || t_min > t_max) {
243                         // ray doesn't touch our grid at all
244                         return false;
245                 }
246                 glm::vec3 contact = ray.origin + t_min * ray.direction;
247                 cell.x = int(contact.x);
248                 cell.y = int(contact.z);
249                 // TODO: not sure if this is correct, could be that contact has to be recalculated with
250                 //       outer planes instead of the -1 ones (that might actually also apply to cell calculation)
251                 tMax.x = (float(cell.x) - contact.x) * inverse_direction.x;
252                 tMax.z = (float(cell.y) - contact.z) * inverse_direction.z;
253         }
254
255         // step hold the direction we're traversing the grid
256         glm::ivec2 step(glm::sign(ray.direction.x), glm::sign(ray.direction.z));
257
258         if (step.x == 0 && step.y == 0) {
259                 // ray shoots straight up or down
260                 // check the current cell (if it's valid)
261                 if (cell.x >= 0 && cell.x < width && cell.y >= 0 && cell.y < depth) {
262                         if (TriangleIntersection(
263                                 ray,
264                                 glm::vec3(float(cell.x + 0), GetElevation(cell.x + 0, cell.y + 0), float(cell.y + 0)),
265                                 glm::vec3(float(cell.x + 1), GetElevation(cell.x + 1, cell.y + 0), float(cell.y + 0)),
266                                 glm::vec3(float(cell.x + 0), GetElevation(cell.x + 0, cell.y + 1), float(cell.y + 1)),
267                                 point
268                         )) {
269                                 return true;
270                         }
271                         if (TriangleIntersection(
272                                 ray,
273                                 glm::vec3(float(cell.x + 1), GetElevation(cell.x + 1, cell.y + 0), float(cell.y + 0)),
274                                 glm::vec3(float(cell.x + 1), GetElevation(cell.x + 1, cell.y + 1), float(cell.y + 1)),
275                                 glm::vec3(float(cell.x + 0), GetElevation(cell.x + 0, cell.y + 1), float(cell.y + 1)),
276                                 point
277                         )) {
278                                 return true;
279                         }
280                 }
281                 return false;
282         }
283
284         // cache for the height of the vertices of the current cell
285         float height[4];
286
287         while (cell.x >= 0 && cell.x < width && cell.y >= 0 && cell.y < depth) {
288                 // pull heights for the current cell
289                 height[0] = GetElevation(cell.x + 0, cell.y + 0);
290                 height[1] = GetElevation(cell.x + 1, cell.y + 0);
291                 height[2] = GetElevation(cell.x + 0, cell.y + 1);
292                 height[3] = GetElevation(cell.x + 1, cell.y + 1);
293                 // the triangles used for rendering are (x,z), (x+1,z), (x,z+1) and
294                 // (x+1,z),(x+1,z+1), (x,z+1), so height indices 012 and 132
295                 if (TriangleIntersection(
296                         ray,
297                         glm::vec3(float(cell.x + 0), height[0], float(cell.y + 0)),
298                         glm::vec3(float(cell.x + 1), height[1], float(cell.y + 0)),
299                         glm::vec3(float(cell.x + 0), height[2], float(cell.y + 1)),
300                         point
301                 )) {
302                         return true;
303                 }
304                 if (TriangleIntersection(
305                         ray,
306                         glm::vec3(float(cell.x + 1), height[1], float(cell.y + 0)),
307                         glm::vec3(float(cell.x + 1), height[3], float(cell.y + 1)),
308                         glm::vec3(float(cell.x + 0), height[2], float(cell.y + 1)),
309                         point
310                 )) {
311                         return true;
312                 }
313                 // advance to the next cell
314                 if (tMax.x < tMax.z) {
315                         tMax.x += tDelta.x;
316                         cell.x += step.x;
317                 } else {
318                         tMax.z += tDelta.z;
319                         cell.y += step.y;
320                 }
321         }
322
323         return false;
324 }
325
326 }