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