mirror of
https://github.com/copyrighttxt/watrbx-game-engine.git
synced 2026-09-04 20:57:49 +00:00
322 lines
9.6 KiB
C++
322 lines
9.6 KiB
C++
/* Copyright 2003-2011 ROBLOX Corporation, All Rights Reserved */
|
|
#include "stdafx.h"
|
|
|
|
#include "V8World/TerrainPartition.h"
|
|
|
|
#include "V8DataModel/MegaCluster.h"
|
|
#include "V8World/Primitive.h"
|
|
#include "Voxel/Grid.h"
|
|
|
|
#include "voxel2/Grid.h"
|
|
|
|
LOGGROUP(TerrainCellListener)
|
|
|
|
namespace RBX {
|
|
|
|
TerrainPartitionMega::TerrainPartitionMega(Voxel::Grid* voxelGrid)
|
|
: voxelGrid(voxelGrid)
|
|
{
|
|
voxelGrid->connectListener(this);
|
|
}
|
|
|
|
TerrainPartitionMega::~TerrainPartitionMega()
|
|
{
|
|
voxelGrid->disconnectListener(this);
|
|
}
|
|
|
|
void TerrainPartitionMega::findCellsTouchingExtents(const Extents& extents, std::vector<Vector3int16>* found) const
|
|
{
|
|
Extents clampedExtents = extents;
|
|
|
|
if (!clampedExtents.clampToOverlap(Voxel::getTerrainExtents()))
|
|
{
|
|
return;
|
|
}
|
|
|
|
Vector3int16 minPos = Voxel::worldToCell_floor(clampedExtents.min());
|
|
Vector3int16 maxPos = Voxel::worldToCell_floor(clampedExtents.max());
|
|
|
|
SpatialRegion::Id minRegion = SpatialRegion::regionContainingVoxel(minPos);
|
|
SpatialRegion::Id maxRegion = SpatialRegion::regionContainingVoxel(maxPos);
|
|
|
|
for (int y = minRegion.value().y; y <= maxRegion.value().y; ++y)
|
|
{
|
|
for (int z = minRegion.value().z; z <= maxRegion.value().z; ++z)
|
|
{
|
|
for (int x = minRegion.value().x; x <= maxRegion.value().x; ++x)
|
|
{
|
|
SpatialRegion::Id region(x, y, z);
|
|
|
|
if (const ChunkData* chunk = chunks.find(region))
|
|
{
|
|
Region3int16 regionExtents = SpatialRegion::inclusiveVoxelExtentsOfRegion(region);
|
|
|
|
Vector3int16 minOffset = SpatialRegion::voxelCoordinateRelativeToEnclosingRegion(regionExtents.getMinPos().max(minPos));
|
|
Vector3int16 maxOffset = SpatialRegion::voxelCoordinateRelativeToEnclosingRegion(regionExtents.getMaxPos().min(maxPos));
|
|
|
|
findCellsInRegion(region, *chunk, minOffset, maxOffset, found);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
inline unsigned int lsb(unsigned int value)
|
|
{
|
|
#ifdef _WIN32
|
|
unsigned long bitPosition;
|
|
_BitScanForward(&bitPosition, value);
|
|
return bitPosition;
|
|
#else
|
|
return ffs(value) - 1;
|
|
#endif
|
|
}
|
|
|
|
void TerrainPartitionMega::findCellsInRegion(const SpatialRegion::Id& region, const ChunkData& chunk, const Vector3int16& minOffset, const Vector3int16& maxOffset, std::vector<Vector3int16>* found) const
|
|
{
|
|
Vector3int16 minSubOffset = minOffset >> Vector3int16(2, 1, 2);
|
|
Vector3int16 maxSubOffset = maxOffset >> Vector3int16(2, 1, 2);
|
|
|
|
Region3int16 offsetExtents(minOffset, maxOffset);
|
|
|
|
for (int y = minSubOffset.y; y <= maxSubOffset.y; ++y)
|
|
{
|
|
for (int z = minSubOffset.z; z <= maxSubOffset.z; ++z)
|
|
{
|
|
for (int x = minSubOffset.x; x <= maxSubOffset.x; ++x)
|
|
{
|
|
unsigned int group = chunk.filled[y][z][x];
|
|
|
|
// this group has certain bits set; let's just iterate through all of them
|
|
while (group)
|
|
{
|
|
unsigned int bit = lsb(group);
|
|
|
|
Vector3int16 pos((x << 2) | (bit & 3), (y << 1) | (bit >> 4), (z << 2) | ((bit >> 2) & 3));
|
|
|
|
if (offsetExtents.contains(pos))
|
|
{
|
|
found->push_back(SpatialRegion::globalVoxelCoordinateFromRegionAndRelativeCoordinate(region, pos));
|
|
}
|
|
|
|
group &= ~(1 << bit);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
void TerrainPartitionMega::terrainCellChanged(const Voxel::CellChangeInfo& info)
|
|
{
|
|
bool beforeNotSolid = info.beforeCell.solid.getBlock() == Voxel::CELL_BLOCK_Empty;
|
|
bool afterNotSolid = info.afterCell.solid.getBlock() == Voxel::CELL_BLOCK_Empty;
|
|
|
|
if (beforeNotSolid != afterNotSolid)
|
|
{
|
|
SpatialRegion::Id region = SpatialRegion::regionContainingVoxel(info.position);
|
|
ChunkData& chunk = chunks.insert(region);
|
|
|
|
Vector3int16 localPos = SpatialRegion::voxelCoordinateRelativeToEnclosingRegion(info.position);
|
|
|
|
unsigned int bitPos = (localPos.x & 3) | ((localPos.z & 3) << 2) | ((localPos.y & 1) << 4);
|
|
unsigned int bitMask = 1 << bitPos;
|
|
|
|
if (beforeNotSolid)
|
|
{
|
|
RBXASSERT((chunk.filled[localPos.y >> 1][localPos.z >> 2][localPos.x >> 2] & bitMask) == 0);
|
|
|
|
chunk.filled[localPos.y >> 1][localPos.z >> 2][localPos.x >> 2] |= bitMask;
|
|
chunk.count++;
|
|
}
|
|
else
|
|
{
|
|
RBXASSERT((chunk.filled[localPos.y >> 1][localPos.z >> 2][localPos.x >> 2] & bitMask) != 0);
|
|
|
|
chunk.filled[localPos.y >> 1][localPos.z >> 2][localPos.x >> 2] &= ~bitMask;
|
|
chunk.count--;
|
|
|
|
if (chunk.count == 0)
|
|
{
|
|
// last cell in the chunk, we don't need it any more
|
|
chunks.erase(region);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
TerrainPartitionSmooth::TerrainPartitionSmooth(Voxel2::Grid* grid)
|
|
: grid(grid)
|
|
{
|
|
for (int min = 0; min < kChunkSize; ++min)
|
|
for (int max = 0; max < kChunkSize; ++max)
|
|
{
|
|
uint64_t hor = 0;
|
|
|
|
for (int z = min; z <= max; ++z)
|
|
for (int x = 0; x < kChunkSize; ++x)
|
|
hor |= 1ull << (z * kChunkSize + x);
|
|
|
|
uint64_t ver = 0;
|
|
|
|
for (int z = 0; z < kChunkSize; ++z)
|
|
for (int x = min; x <= max; ++x)
|
|
ver |= 1ull << (z * kChunkSize + x);
|
|
|
|
masksHor[min][max] = hor;
|
|
masksVer[min][max] = ver;
|
|
}
|
|
}
|
|
|
|
TerrainPartitionSmooth::~TerrainPartitionSmooth()
|
|
{
|
|
}
|
|
|
|
void TerrainPartitionSmooth::findChunksTouchingExtents(const Extents& extents, std::vector<ChunkResult>* found) const
|
|
{
|
|
Voxel2::Region region = Voxel2::Region::fromExtents(extents.min(), extents.max());
|
|
|
|
if (region.empty())
|
|
return;
|
|
|
|
Vector3int32 margin = Vector3int32::one();
|
|
|
|
Vector3int32 minPos = region.begin();
|
|
Vector3int32 maxPos = region.end() - Vector3int32::one();
|
|
|
|
Vector3int32 minChunk = (minPos - margin) >> kChunkSizeLog2;
|
|
Vector3int32 maxChunk = (maxPos + margin) >> kChunkSizeLog2;
|
|
|
|
for (int cy = minChunk.y; cy <= maxChunk.y; ++cy)
|
|
for (int cz = minChunk.z; cz <= maxChunk.z; ++cz)
|
|
for (int cx = minChunk.x; cx <= maxChunk.x; ++cx)
|
|
{
|
|
ChunkMap::const_iterator it = chunks.find(Vector3int32(cx, cy, cz));
|
|
|
|
if (it != chunks.end())
|
|
fillChunkIfTouchingExtents(it->first, it->second, minPos, maxPos, found);
|
|
}
|
|
}
|
|
|
|
template <int Size> static void dilate(uint32_t (&data)[Size][Size])
|
|
{
|
|
// Dilate along X
|
|
for (int y = 0; y < Size; ++y)
|
|
for (int z = 0; z < Size; ++z)
|
|
data[y][z] = (data[y][z] << 1) | data[y][z] | (data[y][z] >> 1);
|
|
|
|
// Dilate along Z
|
|
uint32_t temp[Size][Size];
|
|
|
|
for (int y = 0; y < Size; ++y)
|
|
for (int z = 1; z < Size - 1; ++z)
|
|
temp[y][z] = data[y][z - 1] | data[y][z] | data[y][z + 1];
|
|
|
|
// Dilate along Y
|
|
for (int y = 1; y < Size - 1; ++y)
|
|
for (int z = 0; z < Size; ++z)
|
|
data[y][z] = temp[y - 1][z] | temp[y][z] | temp[y + 1][z];
|
|
}
|
|
|
|
void TerrainPartitionSmooth::updateChunk(const Vector3int32& id)
|
|
{
|
|
Voxel2::Region region = Voxel2::Region::fromChunk(id, kChunkSizeLog2).expand(1);
|
|
Voxel2::Box box = grid->read(region);
|
|
|
|
if (box.isEmpty())
|
|
{
|
|
chunks.erase(id);
|
|
return;
|
|
}
|
|
|
|
ChunkData& chunk = chunks[id];
|
|
|
|
static const int size = (1 << kChunkSizeLog2) + 2;
|
|
|
|
// we pack two bitmasks in 1 32-bit register
|
|
BOOST_STATIC_ASSERT(size < 16);
|
|
|
|
RBXASSERT(box.getSizeX() == size && box.getSizeY() == size && box.getSizeZ() == size);
|
|
|
|
// Low 16 bits are solid, high 16 bits are water; we only use 10/16 bits
|
|
uint32_t bits[size][size];
|
|
|
|
// Fill bitmasks
|
|
for (int y = 0; y < size; ++y)
|
|
{
|
|
for (int z = 0; z < size; ++z)
|
|
{
|
|
uint32_t solidRow = 0;
|
|
uint32_t waterRow = 0;
|
|
|
|
const Voxel2::Cell* row = box.readRow(0, y, z);
|
|
|
|
for (int x = 0; x < size; ++x)
|
|
{
|
|
unsigned char material = row[x].getMaterial();
|
|
|
|
solidRow |= (material > Voxel2::Cell::Material_Water) << x;
|
|
waterRow |= (material == Voxel2::Cell::Material_Water) << x;
|
|
}
|
|
|
|
bits[y][z] = solidRow | (waterRow << 16);
|
|
}
|
|
}
|
|
|
|
// Dilate along X/Y/Z; output border bits are not defined but we won't use them
|
|
dilate(bits);
|
|
|
|
// Fill slices
|
|
for (int y = 0; y < kChunkSize; ++y)
|
|
{
|
|
uint64_t solid = 0;
|
|
uint64_t water = 0;
|
|
|
|
for (int z = 0; z < kChunkSize; ++z)
|
|
{
|
|
unsigned char solidRow = bits[y + 1][z + 1] >> 1;
|
|
unsigned char waterRow = bits[y + 1][z + 1] >> 17;
|
|
|
|
solid |= uint64_t(solidRow) << (z * kChunkSize);
|
|
water |= uint64_t(waterRow) << (z * kChunkSize);
|
|
}
|
|
|
|
chunk.slices[y].solid = solid;
|
|
chunk.slices[y].water = water;
|
|
}
|
|
}
|
|
|
|
void TerrainPartitionSmooth::fillChunkIfTouchingExtents(const Vector3int32& chunkId, const ChunkData& chunkData, const Vector3int32& minPos, const Vector3int32& maxPos, std::vector<ChunkResult>* found) const
|
|
{
|
|
Vector3int32 chunkOffset = chunkId << kChunkSizeLog2;
|
|
|
|
Vector3int32 regionMin = (minPos - chunkOffset).max(Vector3int32(0, 0, 0)).min(Vector3int32(kChunkSize - 1, kChunkSize - 1, kChunkSize - 1));
|
|
Vector3int32 regionMax = (maxPos - chunkOffset).max(Vector3int32(0, 0, 0)).min(Vector3int32(kChunkSize - 1, kChunkSize - 1, kChunkSize - 1));
|
|
|
|
RBXASSERT(regionMin.x <= regionMax.x && regionMin.y <= regionMax.y && regionMin.z <= regionMax.z);
|
|
|
|
uint64_t mask = masksVer[regionMin.x][regionMax.x] & masksHor[regionMin.z][regionMax.z];
|
|
|
|
bool touchesSolid = false;
|
|
bool touchesWater = false;
|
|
|
|
for (int y = regionMin.y; y <= regionMax.y; ++y)
|
|
{
|
|
if (chunkData.slices[y].solid & mask)
|
|
touchesSolid = true;
|
|
|
|
if (chunkData.slices[y].water & mask)
|
|
touchesWater = true;
|
|
|
|
if (touchesSolid & touchesWater)
|
|
break;
|
|
}
|
|
|
|
if (touchesSolid | touchesWater)
|
|
{
|
|
ChunkResult result = { chunkId, touchesSolid, touchesWater };
|
|
found->push_back(result);
|
|
}
|
|
}
|
|
|
|
} // namespace
|