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