src/world/chunk.cpp

   1 #include "BlockLookup.hpp"
   2 #include "Chunk.hpp"
   3 #include "ChunkIndex.hpp"
   4 #include "ChunkLoader.hpp"
   5 #include "ChunkRenderer.hpp"
   6 #include "ChunkStore.hpp"
   7
   8 #include "Generator.hpp"
   9 #include "WorldCollision.hpp"
  10 #include "../app/Assets.hpp"
  11 #include "../graphics/BlockLighting.hpp"
  12 #include "../graphics/Viewport.hpp"
  13 #include "../io/WorldSave.hpp"
  14 #include "../model/BlockModel.hpp"
  15
  16 #include <algorithm>
  17 #include <limits>
  18 #include <ostream>
  19 #include <queue>
  20
  21
  22 namespace blank {
  23
  24 constexpr int Chunk::width;
  25 constexpr int Chunk::height;
  26 constexpr int Chunk::depth;
  27 constexpr int Chunk::size;
  28
  29
  30 Chunk::Chunk(const BlockTypeRegistry &types) noexcept
  31 : types(&types)
  32 , neighbor{0}
  33 , blocks{}
  34 , light{0}
  35 , position(0, 0, 0)
  36 , ref_count(0)
  37 , dirty_model(false)
  38 , dirty_save(false) {
  39
  40 }
  41
  42 Chunk::Chunk(Chunk &&other) noexcept
  43 : types(other.types)
  44 , position(other.position)
  45 , dirty_model(other.dirty_model)
  46 , dirty_save(other.dirty_save) {
  47         std::copy(other.neighbor, other.neighbor + sizeof(neighbor), neighbor);
  48         std::copy(other.blocks, other.blocks + sizeof(blocks), blocks);
  49         std::copy(other.light, other.light + sizeof(light), light);
  50 }
  51
  52 Chunk &Chunk::operator =(Chunk &&other) noexcept {
  53         types = other.types;
  54         std::copy(other.neighbor, other.neighbor + sizeof(neighbor), neighbor);
  55         std::copy(other.blocks, other.blocks + sizeof(blocks), blocks);
  56         std::copy(other.light, other.light + sizeof(light), light);
  57         position = other.position;
  58         dirty_model = other.dirty_save;
  59         dirty_save = other.dirty_save;
  60         return *this;
  61 }
  62
  63
  64 namespace {
  65
  66 struct SetNode {
  67
  68         Chunk *chunk;
  69         Chunk::Pos pos;
  70
  71         SetNode(Chunk *chunk, Chunk::Pos pos)
  72         : chunk(chunk), pos(pos) { }
  73
  74         int Get() const noexcept { return chunk->GetLight(pos); }
  75         void Set(int level) noexcept { chunk->SetLight(pos, level); }
  76
  77         const BlockType &GetType() const noexcept { return chunk->Type(Chunk::ToIndex(pos)); }
  78
  79         bool HasNext(Block::Face face) noexcept {
  80                 const BlockType &type = GetType();
  81                 if (type.block_light && !type.luminosity) return false;
  82                 const BlockLookup next(chunk, pos, face);
  83                 return next;
  84         }
  85         SetNode GetNext(Block::Face face) noexcept {
  86                 const BlockLookup next(chunk, pos, face);
  87                 return SetNode(&next.GetChunk(), next.GetBlockPos());
  88         }
  89
  90 };
  91
  92 struct UnsetNode
  93 : public SetNode {
  94
  95         int level;
  96
  97         UnsetNode(Chunk *chunk, Chunk::Pos pos)
  98         : SetNode(chunk, pos), level(Get()) { }
  99
 100         UnsetNode(const SetNode &set)
 101         : SetNode(set), level(Get()) { }
 102
 103
 104         bool HasNext(Block::Face face) noexcept {
 105                 const BlockLookup next(chunk, pos, face);
 106                 return next;
 107         }
 108         UnsetNode GetNext(Block::Face face) noexcept { return UnsetNode(SetNode::GetNext(face)); }
 109
 110 };
 111
 112 std::queue<SetNode> light_queue;
 113 std::queue<UnsetNode> dark_queue;
 114
 115 void work_light() noexcept {
 116         while (!light_queue.empty()) {
 117                 SetNode node = light_queue.front();
 118                 light_queue.pop();
 119
 120                 int level = node.Get() - 1;
 121                 for (int face = 0; face < Block::FACE_COUNT; ++face) {
 122                         if (node.HasNext(Block::Face(face))) {
 123                                 SetNode other = node.GetNext(Block::Face(face));
 124                                 if (other.Get() < level) {
 125                                         other.Set(level);
 126                                         light_queue.emplace(other);
 127                                 }
 128                         }
 129                 }
 130         }
 131 }
 132
 133 void work_dark() noexcept {
 134         while (!dark_queue.empty()) {
 135                 UnsetNode node = dark_queue.front();
 136                 dark_queue.pop();
 137
 138                 for (int face = 0; face < Block::FACE_COUNT; ++face) {
 139                         if (node.HasNext(Block::Face(face))) {
 140                                 UnsetNode other = node.GetNext(Block::Face(face));
 141                                 // TODO: if there a light source here with the same level this will err
 142                                 if (other.Get() != 0 && other.Get() < node.level) {
 143                                         other.Set(0);
 144                                         dark_queue.emplace(other);
 145                                 } else {
 146                                         light_queue.emplace(other);
 147                                 }
 148                         }
 149                 }
 150         }
 151 }
 152
 153 }
 154
 155 void Chunk::SetBlock(int index, const Block &block) noexcept {
 156         const BlockType &old_type = Type(blocks[index]);
 157         const BlockType &new_type = Type(block);
 158
 159         blocks[index] = block;
 160         Invalidate();
 161
 162         if (&old_type == &new_type) return;
 163
 164         if (new_type.luminosity > old_type.luminosity) {
 165                 // light added
 166                 SetLight(index, new_type.luminosity);
 167                 light_queue.emplace(this, ToPos(index));
 168                 work_light();
 169         } else if (new_type.luminosity < old_type.luminosity) {
 170                 // light removed
 171                 dark_queue.emplace(this, ToPos(index));
 172                 SetLight(index, 0);
 173                 work_dark();
 174                 SetLight(index, new_type.luminosity);
 175                 light_queue.emplace(this, ToPos(index));
 176                 work_light();
 177         } else if (new_type.block_light && !old_type.block_light) {
 178                 // obstacle added
 179                 if (GetLight(index) > 0) {
 180                         dark_queue.emplace(this, ToPos(index));
 181                         SetLight(index, 0);
 182                         work_dark();
 183                         work_light();
 184                 }
 185         } else if (!new_type.block_light && old_type.block_light) {
 186                 // obstacle removed
 187                 int level = 0;
 188                 Pos pos(ToPos(index));
 189                 for (int face = 0; face < Block::FACE_COUNT; ++face) {
 190                         BlockLookup next_block(this, pos, Block::Face(face));
 191                         if (next_block) {
 192                                 level = std::max(level, next_block.GetLight());
 193                         }
 194                 }
 195                 if (level > 1) {
 196                         SetLight(index, level - 1);
 197                         light_queue.emplace(this, pos);
 198                         work_light();
 199                 }
 200         }
 201 }
 202
 203 namespace {
 204
 205 // propagate light from a's edge to b
 206 void edge_light(
 207         Chunk &a, const Chunk::Pos &a_pos,
 208         Chunk &b, const Chunk::Pos &b_pos
 209 ) noexcept {
 210         if (a.GetLight(a_pos) > 1) {
 211                 const BlockType &b_type = b.Type(Chunk::ToIndex(b_pos));
 212                 if (!b_type.block_light) {
 213                         light_queue.emplace(&a, a_pos);
 214                 }
 215                 if (b_type.visible) {
 216                         b.Invalidate();
 217                 }
 218         }
 219 }
 220
 221 }
 222
 223 void Chunk::SetNeighbor(Block::Face face, Chunk &other) noexcept {
 224         neighbor[face] = &other;
 225         other.neighbor[Block::Opposite(face)] = this;
 226
 227         switch (face) {
 228
 229                 default:
 230                         // error
 231                         break;
 232
 233                 case Block::FACE_LEFT:
 234                         for (int z = 0; z < depth; ++z) {
 235                                 for (int y = 0; y < height; ++y) {
 236                                         Pos my_pos(0, y, z);
 237                                         Pos other_pos(width - 1, y, z);
 238                                         edge_light(*this, my_pos, other, other_pos);
 239                                         edge_light(other, other_pos, *this, my_pos);
 240                                 }
 241                         }
 242                         break;
 243
 244                 case Block::FACE_RIGHT:
 245                         for (int z = 0; z < depth; ++z) {
 246                                 for (int y = 0; y < height; ++y) {
 247                                         Pos my_pos(width - 1, y, z);
 248                                         Pos other_pos(0, y, z);
 249                                         edge_light(*this, my_pos, other, other_pos);
 250                                         edge_light(other, other_pos, *this, my_pos);
 251                                 }
 252                         }
 253                         break;
 254
 255                 case Block::FACE_DOWN:
 256                         for (int z = 0; z < depth; ++z) {
 257                                 for (int x = 0; x < width; ++x) {
 258                                         Pos my_pos(x, 0, z);
 259                                         Pos other_pos(x, height - 1, z);
 260                                         edge_light(*this, my_pos, other, other_pos);
 261                                         edge_light(other, other_pos, *this, my_pos);
 262                                 }
 263                         }
 264                         break;
 265
 266                 case Block::FACE_UP:
 267                         for (int z = 0; z < depth; ++z) {
 268                                 for (int x = 0; x < width; ++x) {
 269                                         Pos my_pos(x, height - 1, z);
 270                                         Pos other_pos(x, 0, z);
 271                                         edge_light(*this, my_pos, other, other_pos);
 272                                         edge_light(other, other_pos, *this, my_pos);
 273                                 }
 274                         }
 275                         break;
 276
 277                 case Block::FACE_BACK:
 278                         for (int y = 0; y < height; ++y) {
 279                                 for (int x = 0; x < width; ++x) {
 280                                         Pos my_pos(x, y, 0);
 281                                         Pos other_pos(x, y, depth - 1);
 282                                         edge_light(*this, my_pos, other, other_pos);
 283                                         edge_light(other, other_pos, *this, my_pos);
 284                                 }
 285                         }
 286                         break;
 287
 288                 case Block::FACE_FRONT:
 289                         for (int y = 0; y < height; ++y) {
 290                                 for (int x = 0; x < width; ++x) {
 291                                         Pos my_pos(x, y, depth - 1);
 292                                         Pos other_pos(x, y, 0);
 293                                         edge_light(*this, my_pos, other, other_pos);
 294                                         edge_light(other, other_pos, *this, my_pos);
 295                                 }
 296                         }
 297                         break;
 298
 299         }
 300         work_light();
 301 }
 302
 303 void Chunk::Unlink() noexcept {
 304         for (int face = 0; face < Block::FACE_COUNT; ++face) {
 305                 if (neighbor[face]) {
 306                         neighbor[face]->neighbor[Block::Opposite(Block::Face(face))] = nullptr;
 307                         neighbor[face] = nullptr;
 308                 }
 309         }
 310 }
 311
 312
 313 void Chunk::SetLight(int index, int level) noexcept {
 314         if (light[index] != level) {
 315                 light[index] = level;
 316                 Invalidate();
 317         }
 318 }
 319
 320 int Chunk::GetLight(int index) const noexcept {
 321         return light[index];
 322 }
 323
 324 float Chunk::GetVertexLight(const Pos &pos, const BlockModel::Position &vtx, const EntityModel::Normal &norm) const noexcept {
 325         int index = ToIndex(pos);
 326         float light = GetLight(index);
 327
 328         Block::Face direct_face(Block::NormalFace(norm));
 329         // tis okay
 330         BlockLookup direct(const_cast<Chunk *>(this), pos, Block::NormalFace(norm));
 331         if (direct) {
 332                 float direct_light = direct.GetLight();
 333                 if (direct_light > light) {
 334                         light = direct_light;
 335                 }
 336         } else {
 337                 return light;
 338         }
 339
 340         if (Type(BlockAt(index)).luminosity > 0 || direct.GetType().block_light) {
 341                 return light;
 342         }
 343
 344         Block::Face edge[2];
 345         switch (Block::Axis(direct_face)) {
 346                 case 0: // X
 347                         edge[0] = (vtx.y - pos.y) > 0.5f ? Block::FACE_UP : Block::FACE_DOWN;
 348                         edge[1] = (vtx.z - pos.z) > 0.5f ? Block::FACE_FRONT : Block::FACE_BACK;
 349                         break;
 350                 case 1: // Y
 351                         edge[0] = (vtx.z - pos.z) > 0.5f ? Block::FACE_FRONT : Block::FACE_BACK;
 352                         edge[1] = (vtx.x - pos.x) > 0.5f ? Block::FACE_RIGHT : Block::FACE_LEFT;
 353                         break;
 354                 case 2: // Z
 355                         edge[0] = (vtx.x - pos.x) > 0.5f ? Block::FACE_RIGHT : Block::FACE_LEFT;
 356                         edge[1] = (vtx.y - pos.y) > 0.5f ? Block::FACE_UP : Block::FACE_DOWN;
 357                         break;
 358         }
 359
 360         int num = 1;
 361         int occlusion = 0;
 362
 363         BlockLookup next[2] = {
 364                 direct.Next(edge[0]),
 365                 direct.Next(edge[1]),
 366         };
 367
 368         if (next[0]) {
 369                 if (next[0].GetType().block_light) {
 370                         ++occlusion;
 371                 } else {
 372                         light += next[0].GetLight();
 373                         ++num;
 374                 }
 375         }
 376         if (next[1]) {
 377                 if (next[1].GetType().block_light) {
 378                         ++occlusion;
 379                 } else {
 380                         light += next[1].GetLight();
 381                         ++num;
 382                 }
 383         }
 384         if (occlusion < 2) {
 385                 if (next[0]) {
 386                         BlockLookup corner = next[0].Next(edge[1]);
 387                         if (corner) {
 388                                 if (corner.GetType().block_light) {
 389                                         ++occlusion;
 390                                 } else {
 391                                         light += corner.GetLight();
 392                                         ++num;
 393                                 }
 394                         }
 395                 } else if (next[1]) {
 396                         BlockLookup corner = next[1].Next(edge[0]);
 397                         if (corner) {
 398                                 if (corner.GetType().block_light) {
 399                                         ++occlusion;
 400                                 } else {
 401                                         light += corner.GetLight();
 402                                         ++num;
 403                                 }
 404                         }
 405                 }
 406         } else {
 407                 ++occlusion;
 408         }
 409
 410         return (light / num) - (occlusion * 0.8f);
 411 }
 412
 413
 414 bool Chunk::IsSurface(const Pos &pos) const noexcept {
 415         const Block &block = BlockAt(pos);
 416         if (!Type(block).visible) {
 417                 return false;
 418         }
 419         for (int face = 0; face < Block::FACE_COUNT; ++face) {
 420                 BlockLookup next = BlockLookup(const_cast<Chunk *>(this), pos, Block::Face(face));
 421                 if (!next || !next.GetType().visible) {
 422                         return true;
 423                 }
 424         }
 425         return false;
 426 }
 427
 428
 429 bool Chunk::Intersection(
 430         const Ray &ray,
 431         const glm::mat4 &M,
 432         WorldCollision &coll
 433 ) noexcept {
 434         int idx = 0;
 435         coll.chunk = this;
 436         coll.block = -1;
 437         coll.depth = std::numeric_limits<float>::infinity();
 438         for (int z = 0; z < depth; ++z) {
 439                 for (int y = 0; y < height; ++y) {
 440                         for (int x = 0; x < width; ++x, ++idx) {
 441                                 const BlockType &type = Type(idx);
 442                                 if (!type.visible) {
 443                                         continue;
 444                                 }
 445                                 float cur_dist;
 446                                 glm::vec3 cur_norm;
 447                                 if (type.shape->Intersects(ray, M * ToTransform(Pos(x, y, z), idx), cur_dist, cur_norm)) {
 448                                         if (cur_dist < coll.depth) {
 449                                                 coll.block = idx;
 450                                                 coll.depth = cur_dist;
 451                                                 coll.normal = cur_norm;
 452                                         }
 453                                 }
 454                         }
 455                 }
 456         }
 457
 458         if (coll.block < 0) {
 459                 return false;
 460         } else {
 461                 coll.normal = glm::vec3(BlockAt(coll.block).Transform() * glm::vec4(coll.normal, 0.0f));
 462                 return true;
 463         }
 464 }
 465
 466 bool Chunk::Intersection(
 467         const AABB &box,
 468         const glm::mat4 &Mbox,
 469         const glm::mat4 &Mchunk,
 470         std::vector<WorldCollision> &col
 471 ) noexcept {
 472         bool any = false;
 473         float penetration;
 474         glm::vec3 normal;
 475
 476         if (!blank::Intersection(box, Mbox, Bounds(), Mchunk, penetration, normal)) {
 477                 return false;
 478         }
 479         for (int idx = 0, z = 0; z < depth; ++z) {
 480                 for (int y = 0; y < height; ++y) {
 481                         for (int x = 0; x < width; ++x, ++idx) {
 482                                 const BlockType &type = Type(idx);
 483                                 if (!type.collision) {
 484                                         continue;
 485                                 }
 486                                 if (type.shape->Intersects(Mchunk * ToTransform(Pos(x, y, z), idx), box, Mbox, penetration, normal)) {
 487                                         col.emplace_back(this, idx, penetration, normal);
 488                                         any = true;
 489                                 }
 490                         }
 491                 }
 492         }
 493         return any;
 494 }
 495
 496
 497 namespace {
 498
 499 BlockModel::Buffer buf;
 500
 501 }
 502
 503 void Chunk::Update(BlockModel &model) noexcept {
 504         int vtx_count = 0, idx_count = 0;
 505         for (const auto &block : blocks) {
 506                 const Shape *shape = Type(block).shape;
 507                 vtx_count += shape->VertexCount();
 508                 idx_count += shape->VertexIndexCount();
 509         }
 510         buf.Clear();
 511         buf.Reserve(vtx_count, idx_count);
 512
 513         int idx = 0;
 514         BlockModel::Index vtx_counter = 0;
 515         for (size_t z = 0; z < depth; ++z) {
 516                 for (size_t y = 0; y < height; ++y) {
 517                         for (size_t x = 0; x < width; ++x, ++idx) {
 518                                 const BlockType &type = Type(BlockAt(idx));
 519                                 const Pos pos(x, y, z);
 520
 521                                 if (!type.visible || Obstructed(pos).All()) continue;
 522
 523                                 type.FillBlockModel(buf, ToTransform(pos, idx), vtx_counter);
 524                                 size_t vtx_begin = vtx_counter;
 525                                 vtx_counter += type.shape->VertexCount();
 526
 527                                 for (size_t vtx = vtx_begin; vtx < vtx_counter; ++vtx) {
 528                                         buf.lights.emplace_back(GetVertexLight(
 529                                                 pos,
 530                                                 buf.vertices[vtx],
 531                                                 type.shape->VertexNormal(vtx - vtx_begin, BlockAt(idx).Transform())
 532                                         ));
 533                                 }
 534                         }
 535                 }
 536         }
 537
 538         model.Update(buf);
 539         ClearModel();
 540 }
 541
 542 Block::FaceSet Chunk::Obstructed(const Pos &pos) const noexcept {
 543         Block::FaceSet result;
 544
 545         for (int f = 0; f < Block::FACE_COUNT; ++f) {
 546                 Block::Face face = Block::Face(f);
 547                 BlockLookup next(const_cast<Chunk *>(this), pos, face);
 548                 if (next && next.GetType().FaceFilled(next.GetBlock(), Block::Opposite(face))) {
 549                         result.Set(face);
 550                 }
 551         }
 552
 553         return result;
 554 }
 555
 556 glm::mat4 Chunk::ToTransform(const Pos &pos, int idx) const noexcept {
 557         return glm::translate(ToCoords(pos)) * BlockAt(idx).Transform();
 558 }
 559
 560
 561 BlockLookup::BlockLookup(Chunk *c, const Chunk::Pos &p) noexcept
 562 : chunk(c), pos(p) {
 563         while (pos.x >= Chunk::width) {
 564                 if (chunk->HasNeighbor(Block::FACE_RIGHT)) {
 565                         chunk = &chunk->GetNeighbor(Block::FACE_RIGHT);
 566                         pos.x -= Chunk::width;
 567                 } else {
 568                         chunk = nullptr;
 569                         return;
 570                 }
 571         }
 572         while (pos.x < 0) {
 573                 if (chunk->HasNeighbor(Block::FACE_LEFT)) {
 574                         chunk = &chunk->GetNeighbor(Block::FACE_LEFT);
 575                         pos.x += Chunk::width;
 576                 } else {
 577                         chunk = nullptr;
 578                         return;
 579                 }
 580         }
 581         while (pos.y >= Chunk::height) {
 582                 if (chunk->HasNeighbor(Block::FACE_UP)) {
 583                         chunk = &chunk->GetNeighbor(Block::FACE_UP);
 584                         pos.y -= Chunk::height;
 585                 } else {
 586                         chunk = nullptr;
 587                         return;
 588                 }
 589         }
 590         while (pos.y < 0) {
 591                 if (chunk->HasNeighbor(Block::FACE_DOWN)) {
 592                         chunk = &chunk->GetNeighbor(Block::FACE_DOWN);
 593                         pos.y += Chunk::height;
 594                 } else {
 595                         chunk = nullptr;
 596                         return;
 597                 }
 598         }
 599         while (pos.z >= Chunk::depth) {
 600                 if (chunk->HasNeighbor(Block::FACE_FRONT)) {
 601                         chunk = &chunk->GetNeighbor(Block::FACE_FRONT);
 602                         pos.z -= Chunk::depth;
 603                 } else {
 604                         chunk = nullptr;
 605                         return;
 606                 }
 607         }
 608         while (pos.z < 0) {
 609                 if (chunk->HasNeighbor(Block::FACE_BACK)) {
 610                         chunk = &chunk->GetNeighbor(Block::FACE_BACK);
 611                         pos.z += Chunk::depth;
 612                 } else {
 613                         chunk = nullptr;
 614                         return;
 615                 }
 616         }
 617 }
 618
 619 BlockLookup::BlockLookup(Chunk *c, const Chunk::Pos &p, Block::Face face) noexcept
 620 : chunk(c), pos(p) {
 621         pos += Block::FaceNormal(face);
 622         if (!Chunk::InBounds(pos)) {
 623                 pos -= Block::FaceNormal(face) * Chunk::Extent();
 624                 chunk = &chunk->GetNeighbor(face);
 625         }
 626 }
 627
 628
 629 ChunkLoader::ChunkLoader(
 630         ChunkStore &store,
 631         const Generator &gen,
 632         const WorldSave &save
 633 ) noexcept
 634 : store(store)
 635 , gen(gen)
 636 , save(save) {
 637
 638 }
 639
 640 void ChunkLoader::Update(int dt) {
 641         // check if there's chunks waiting to be loaded
 642         // load until one of load or generation limits was hit
 643         constexpr int max_load = 10;
 644         constexpr int max_gen = 1;
 645         int loaded = 0;
 646         int generated = 0;
 647         while (loaded < max_load && generated < max_gen && store.HasMissing()) {
 648                 if (LoadOne()) {
 649                         ++generated;
 650                 } else {
 651                         ++loaded;
 652                 }
 653         }
 654
 655         // store a few chunks as well
 656         constexpr int max_save = 10;
 657         int saved = 0;
 658         for (Chunk &chunk : store) {
 659                 if (chunk.ShouldUpdateSave()) {
 660                         save.Write(chunk);
 661                         ++saved;
 662                         if (saved >= max_save) {
 663                                 break;
 664                         }
 665                 }
 666         }
 667 }
 668
 669 int ChunkLoader::ToLoad() const noexcept {
 670         return store.EstimateMissing();
 671 }
 672
 673 bool ChunkLoader::LoadOne() {
 674         if (!store.HasMissing()) return false;
 675
 676         Chunk::Pos pos = store.NextMissing();
 677         Chunk *chunk = store.Allocate(pos);
 678         if (!chunk) {
 679                 // chunk store corrupted?
 680                 return false;
 681         }
 682
 683         if (save.Exists(pos)) {
 684                 save.Read(*chunk);
 685                 return false;
 686         } else {
 687                 gen(*chunk);
 688                 return true;
 689         }
 690 }
 691
 692 void ChunkLoader::LoadN(std::size_t n) {
 693         std::size_t end = std::min(n, std::size_t(ToLoad()));
 694         for (std::size_t i = 0; i < end && store.HasMissing(); ++i) {
 695                 LoadOne();
 696         }
 697 }
 698
 699
 700 ChunkRenderer::ChunkRenderer(ChunkIndex &index)
 701 : index(index)
 702 , models(index.TotalChunks())
 703 , block_tex()
 704 , fog_density(0.0f) {
 705
 706 }
 707
 708 ChunkRenderer::~ChunkRenderer() {
 709
 710 }
 711
 712 int ChunkRenderer::MissingChunks() const noexcept {
 713         return index.MissingChunks();
 714 }
 715
 716 void ChunkRenderer::LoadTextures(const AssetLoader &loader, const TextureIndex &tex_index) {
 717         block_tex.Bind();
 718         loader.LoadTextures(tex_index, block_tex);
 719         block_tex.FilterNearest();
 720 }
 721
 722 void ChunkRenderer::Update(int dt) {
 723         for (int i = 0, updates = 0; updates < dt && i < index.TotalChunks(); ++i) {
 724                 if (index[i] && index[i]->ShouldUpdateModel()) {
 725                         index[i]->Update(models[i]);
 726                         ++updates;
 727                 }
 728         }
 729 }
 730
 731 void ChunkRenderer::Render(Viewport &viewport) {
 732         BlockLighting &chunk_prog = viewport.ChunkProgram();
 733         chunk_prog.SetTexture(block_tex);
 734         chunk_prog.SetFogDensity(fog_density);
 735
 736         for (int i = 0; i < index.TotalChunks(); ++i) {
 737                 if (!index[i]) continue;
 738                 glm::mat4 m(index[i]->Transform(index.Base()));
 739                 glm::mat4 mvp(chunk_prog.GetVP() * m);
 740                 if (!CullTest(Chunk::Bounds(), mvp)) {
 741                         if (index[i]->ShouldUpdateModel()) {
 742                                 index[i]->Update(models[i]);
 743                         }
 744                         chunk_prog.SetM(m);
 745                         models[i].Draw();
 746                 }
 747         }
 748 }
 749
 750
 751 ChunkIndex::ChunkIndex(ChunkStore &store, const Chunk::Pos &base, int extent)
 752 : store(store)
 753 , base(base)
 754 , extent(extent)
 755 , side_length(2 * extent + 1)
 756 , total_length(side_length * side_length * side_length)
 757 , total_indexed(0)
 758 , last_missing(0)
 759 , stride(1, side_length, side_length * side_length)
 760 , chunks(total_length, nullptr) {
 761         Scan();
 762 }
 763
 764 ChunkIndex::~ChunkIndex() {
 765         Clear();
 766 }
 767
 768 bool ChunkIndex::InRange(const Chunk::Pos &pos) const noexcept {
 769         return manhattan_radius(pos - base) <= extent;
 770 }
 771
 772 int ChunkIndex::IndexOf(const Chunk::Pos &pos) const noexcept {
 773         Chunk::Pos mod_pos(
 774                 GetCol(pos.x),
 775                 GetCol(pos.y),
 776                 GetCol(pos.z)
 777         );
 778         return mod_pos.x * stride.x
 779                 +  mod_pos.y * stride.y
 780                 +  mod_pos.z * stride.z;
 781 }
 782
 783 Chunk::Pos ChunkIndex::PositionOf(int i) const noexcept {
 784         Chunk::Pos zero_pos(
 785                 (i / stride.x) % side_length,
 786                 (i / stride.y) % side_length,
 787                 (i / stride.z) % side_length
 788         );
 789         Chunk::Pos zero_base(
 790                 GetCol(base.x),
 791                 GetCol(base.y),
 792                 GetCol(base.z)
 793         );
 794         Chunk::Pos base_relative(zero_pos - zero_base);
 795         if (base_relative.x > extent) base_relative.x -= side_length;
 796         else if (base_relative.x < -extent) base_relative.x += side_length;
 797         if (base_relative.y > extent) base_relative.y -= side_length;
 798         else if (base_relative.y < -extent) base_relative.y += side_length;
 799         if (base_relative.z > extent) base_relative.z -= side_length;
 800         else if (base_relative.z < -extent) base_relative.z += side_length;
 801         return base + base_relative;
 802 }
 803
 804 Chunk *ChunkIndex::Get(const Chunk::Pos &pos) noexcept {
 805         if (InRange(pos)) {
 806                 return chunks[IndexOf(pos)];
 807         } else {
 808                 return nullptr;
 809         }
 810 }
 811
 812 const Chunk *ChunkIndex::Get(const Chunk::Pos &pos) const noexcept {
 813         if (InRange(pos)) {
 814                 return chunks[IndexOf(pos)];
 815         } else {
 816                 return nullptr;
 817         }
 818 }
 819
 820 void ChunkIndex::Rebase(const Chunk::Pos &new_base) {
 821         if (new_base == base) return;
 822
 823         Chunk::Pos diff(new_base - base);
 824
 825         if (manhattan_radius(diff) > extent) {
 826                 // that's more than half, so probably not worth shifting
 827                 base = new_base;
 828                 Clear();
 829                 Scan();
 830                 store.Clean();
 831                 return;
 832         }
 833
 834         while (diff.x > 0) {
 835                 Shift(Block::FACE_RIGHT);
 836                 --diff.x;
 837         }
 838         while (diff.x < 0) {
 839                 Shift(Block::FACE_LEFT);
 840                 ++diff.x;
 841         }
 842         while (diff.y > 0) {
 843                 Shift(Block::FACE_UP);
 844                 --diff.y;
 845         }
 846         while (diff.y < 0) {
 847                 Shift(Block::FACE_DOWN);
 848                 ++diff.y;
 849         }
 850         while (diff.z > 0) {
 851                 Shift(Block::FACE_FRONT);
 852                 --diff.z;
 853         }
 854         while (diff.z < 0) {
 855                 Shift(Block::FACE_BACK);
 856                 ++diff.z;
 857         }
 858         store.Clean();
 859 }
 860
 861 int ChunkIndex::GetCol(int c) const noexcept {
 862         c %= side_length;
 863         if (c < 0) c += side_length;
 864         return c;
 865 }
 866
 867 void ChunkIndex::Shift(Block::Face f) {
 868         int a_axis = Block::Axis(f);
 869         int b_axis = (a_axis + 1) % 3;
 870         int c_axis = (a_axis + 2) % 3;
 871         int dir = Block::Direction(f);
 872         base[a_axis] += dir;
 873         int a = GetCol(base[a_axis] + (extent * dir));
 874         int a_stride = a * stride[a_axis];
 875         for (int b = 0; b < side_length; ++b) {
 876                 int b_stride = b * stride[b_axis];
 877                 for (int c = 0; c < side_length; ++c) {
 878                         int bc_stride = b_stride + c * stride[c_axis];
 879                         int index = a_stride + bc_stride;
 880                         Unset(index);
 881                         int neighbor = ((a - dir + side_length) % side_length) * stride[a_axis] + bc_stride;
 882                         if (chunks[neighbor] && chunks[neighbor]->HasNeighbor(f)) {
 883                                 Set(index, chunks[neighbor]->GetNeighbor(f));
 884                         }
 885                 }
 886         }
 887 }
 888
 889 void ChunkIndex::Clear() noexcept {
 890         for (int i = 0; i < total_length && total_indexed > 0; ++i) {
 891                 Unset(i);
 892         }
 893 }
 894
 895 void ChunkIndex::Scan() noexcept {
 896         for (Chunk &chunk : store) {
 897                 Register(chunk);
 898         }
 899 }
 900
 901 void ChunkIndex::Register(Chunk &chunk) noexcept {
 902         if (InRange(chunk.Position())) {
 903                 Set(IndexOf(chunk.Position()), chunk);
 904         }
 905 }
 906
 907 void ChunkIndex::Set(int index, Chunk &chunk) noexcept {
 908         Unset(index);
 909         chunks[index] = &chunk;
 910         chunk.Ref();
 911         ++total_indexed;
 912 }
 913
 914 void ChunkIndex::Unset(int index) noexcept {
 915         if (chunks[index]) {
 916                 chunks[index]->UnRef();
 917                 chunks[index] = nullptr;
 918                 --total_indexed;
 919         }
 920 }
 921
 922 Chunk::Pos ChunkIndex::NextMissing() noexcept {
 923         if (MissingChunks() > 0) {
 924                 int roundtrip = last_missing;
 925                 last_missing = (last_missing + 1) % total_length;
 926                 while (chunks[last_missing]) {
 927                         last_missing = (last_missing + 1) % total_length;
 928                         if (last_missing == roundtrip) {
 929                                 break;
 930                         }
 931                 }
 932         }
 933         return PositionOf(last_missing);
 934 }
 935
 936
 937 ChunkStore::ChunkStore(const BlockTypeRegistry &types)
 938 : types(types)
 939 , loaded()
 940 , free()
 941 , indices() {
 942
 943 }
 944
 945 ChunkStore::~ChunkStore() {
 946
 947 }
 948
 949 ChunkIndex &ChunkStore::MakeIndex(const Chunk::Pos &pos, int extent) {
 950         indices.emplace_back(*this, pos, extent);
 951         return indices.back();
 952 }
 953
 954 void ChunkStore::UnregisterIndex(ChunkIndex &index) {
 955         for (auto i = indices.begin(), end = indices.end(); i != end; ++i) {
 956                 if (&*i == &index) {
 957                         indices.erase(i);
 958                         return;
 959                 } else {
 960                         ++i;
 961                 }
 962         }
 963 }
 964
 965 Chunk *ChunkStore::Get(const Chunk::Pos &pos) {
 966         for (ChunkIndex &index : indices) {
 967                 Chunk *chunk = index.Get(pos);
 968                 if (chunk) {
 969                         return chunk;
 970                 }
 971         }
 972         return nullptr;
 973 }
 974
 975 Chunk *ChunkStore::Allocate(const Chunk::Pos &pos) {
 976         Chunk *chunk = Get(pos);
 977         if (chunk) {
 978                 return chunk;
 979         }
 980         if (free.empty()) {
 981                 loaded.emplace(loaded.begin(), types);
 982         } else {
 983                 loaded.splice(loaded.begin(), free, free.begin());
 984                 loaded.front().Unlink();
 985         }
 986         chunk = &loaded.front();
 987         chunk->Position(pos);
 988         for (ChunkIndex &index : indices) {
 989                 if (index.InRange(pos)) {
 990                         index.Register(*chunk);
 991                 }
 992         }
 993         for (int i = 0; i < Block::FACE_COUNT; ++i) {
 994                 Block::Face face = Block::Face(i);
 995                 Chunk::Pos neighbor_pos(pos + Block::FaceNormal(face));
 996                 Chunk *neighbor = Get(neighbor_pos);
 997                 if (neighbor) {
 998                         chunk->SetNeighbor(face, *neighbor);
 999                 }
1000         }
1001         return chunk;
1002 }
1003
1004 bool ChunkStore::HasMissing() const noexcept {
1005         for (const ChunkIndex &index : indices) {
1006                 if (index.MissingChunks() > 0) {
1007                         return true;
1008                 }
1009         }
1010         return false;
1011 }
1012
1013 int ChunkStore::EstimateMissing() const noexcept {
1014         int missing = 0;
1015         for (const ChunkIndex &index : indices) {
1016                 missing += index.MissingChunks();
1017         }
1018         return missing;
1019 }
1020
1021 Chunk::Pos ChunkStore::NextMissing() noexcept {
1022         for (ChunkIndex &index : indices) {
1023                 if (index.MissingChunks()) {
1024                         return index.NextMissing();
1025                 }
1026         }
1027         return Chunk::Pos(0, 0, 0);
1028 }
1029
1030 void ChunkStore::Clean() {
1031         for (auto i = loaded.begin(), end = loaded.end(); i != end;) {
1032                 if (i->Referenced()) {
1033                         ++i;
1034                 } else {
1035                         auto chunk = i;
1036                         ++i;
1037                         free.splice(free.end(), loaded, chunk);
1038                         chunk->Unlink();
1039                         chunk->InvalidateModel();
1040                 }
1041         }
1042 }
1043
1044 }