Эффективно проверяйте соседние воксели в трехмерном массиве размера n
Моя система вокселей использует плоский трехмерный массив, динамически выделяемый во время выполнения для каждого чанка, однако генерирование миллионов кубов в чанке невозможно, поэтому мне нужно оптимизировать.
Первая оптимизация, которую я собираюсь реализовать, — это, конечно, не генерировать данные сетки для окклюдированных вокселей, это хорошая идея на бумаге, но я не знаю, как это сделать.
Все мои попытки закончились трудными отладками проблем с выделением памяти, и поэтому я должен был бросить полотенце и попросить более знающих людей, так как я в растерянности.
Мое текущее воплощение этого как такового
int8_t x = 0, y= 0, z = 0;
const int MAX = CHUNKSIZE-1;
const int MIN = 0;int8_t sPosX = (x - 1 < MIN) ? x : x-1;
int8_t sPosY = (y - 1 < MIN) ? y : y-1;
int8_t sPosZ = (z - 1 < MIN) ? z : z-1;
int8_t ePosX = (x + 1 > MAX) ? x : x+1;
int8_t ePosY = (y + 1 > MAX) ? y : y+1;
int8_t ePosZ = (z + 1 > MAX) ? z : z+1;
int8_t a=sPosX, b=sPosY, c=sPosZ;
int8_t add = 0;BlockType BT = BT_grass;
scene::SMesh* mesh = new scene::SMesh();
for(x = 0; x <= MAX; x++)
{
for(y = 0; y <= MAX; y++)
{
for(z = 0; z <= MAX; z++)
{
cm = b_blocks[x][y][z].material;
//b_blocks[x][y][z].setFlags(0xFE, BT);
if( !b_blocks[x][x][z].isActive() )
{
continue;
}
else
{
if(sPosX == MIN)
{
createCube(x,y,z,c,mesh,cm);
}
else
{
if(a<=ePosX)
{
if(b<=ePosY)
{
if(c<=ePosZ)
{
printf("x %d, y %d, z %d\n", x, y, z);
if(!b_blocks[x][y][z].isActive())
{
add = 1;
}
}
}
}
if(add == 1)
{
createCube(x,y,z,c,mesh,cm);
add = 0;
}
}
}
}
}
}
If (sPosX == MIN) — это хак, который я реализовал, чтобы не вызывать segfault при генерации чанка (в противном случае он приводит к нарушению доступа к памяти при генерировании блока [CHUNKSIZE] [CHUNKSIZE] [CHUNKSIZE], что не очень приятно.
Этот хак непреднамеренно гарантирует, что все кубы сгенерированы, и является столь же непривлекательным.
Краткие вопросы здесь следующие:
Какая часть моей логики нарушена? (по-видимому, все это) и как правильно проверить соседние блоки быстрым способом, который не вызывает ошибку «вне границ»? (Я пытался вручную кодировать исключения для каждого последнего углового случая, но это оказалось неприемлемым и было на несколько порядков медленнее и склонно к сегагфингу)
Решение
Я бы использовал что-то вроде:
class BlockChunk final
{
public:
static constexpr int sizeXShift = 4, sizeYshift = 8, sizeZshift = 4;
static constexpr int sizeX = 1 << sizeXShift; // 2 ** sizeXShift
static constexpr int sizeY = 1 << sizeYShift;
static constexpr int sizeZ = 1 << sizeZShift;
static constexpr int sizeXRelativeMask = sizeX - 1; // mask to get position mod sizeX (faster than % because negative inputs to % return negative answers which need more adjusting whereas masking always returns the positive answer)
static constexpr int sizeYRelativeMask = sizeY - 1;
static constexpr int sizeZRelativeMask = sizeZ - 1;
static constexpr int sizeXChunkBaseMask = ~sizeXRelativeMask; // mask to get position - relativePosition (aka chunk base position)
static constexpr int sizeYChunkBaseMask = ~sizeYRelativeMask;
static constexpr int sizeZChunkBaseMask = ~sizeZRelativeMask;
private:
Block blocks[sizeX][sizeY][sizeZ];
public:
const PositionI basePosition;
BlockChunk(PositionI basePosition)
: basePosition(basePosition)
{
}
Block &at(PositionI relative)
{
assert(relative.x >= 0 && relative.x < sizeX);
assert(relative.y >= 0 && relative.y < sizeY);
assert(relative.z >= 0 && relative.z < sizeZ); // these asserts are important for finding out-of-bounds bugs
return blocks[relative.x][relative.y][relative.z];
}
static PositionI getRelativePosition(PositionI p)
{
p.x &= sizeXRelativeMask;
p.y &= sizeYRelativeMask;
p.z &= sizeZRelativeMask;
return p;
}
static PositionI getChunkBasePosition(PositionI p)
{
p.x &= sizeXChunkBaseMask;
p.y &= sizeYChunkBaseMask;
p.z &= sizeZChunkBaseMask;
return p;
}
};
class BlockIterator;
class BlockWorldBase
{
friend class BlockIterator;
private:
std::unordered_map<PositionI, std::shared_ptr<BlockChunk>> chunks;
BlockChunk *getOrMakeChunk(PositionI chunkBasePosition)
{
std::shared_ptr<BlockChunk> &chunk = chunks[chunkBasePosition];
if(chunk == nullptr)
chunk = std::make_shared<BlockChunk>(chunkBasePosition);
return chunk.get();
}
};
class BlockWorld;
class BlockIterator final
{
friend class BlockWorld;
private:
BlockChunk *chunk;
BlockWorldBase *world;
PositionI chunkBasePosition, relativePosition;
void updateChunk()
{
chunk = world->getOrMakeChunk(chunkBasePosition);
}
BlockIterator(BlockWorldBase *world, PositionI position)
: chunk(),
world(world),
chunkBasePosition(BlockChunk::getChunkBasePosition(position)),
relativePosition(BlockChunk::getRelativePosition(position))
{
updateChunk();
}
public:
PositionI getPosition() const
{
return relativePosition + chunkBasePosition;
}
Block &get()
{
return chunk->at(relativePosition);
}
BlockIterator &operator +=(PositionI deltaPosition) // move to point to a new block
{
PositionI newRelativePosition = relativePosition + deltaPosition;
if(BlockChunk::getRelativePosition(newRelativePosition) != newRelativePosition) // if the new position is outside of this chunk
{
relativePosition = BlockChunk::getRelativePosition(newRelativePosition);
chunkBasePosition += BlockChunk::getChunkBasePosition(newRelativePosition);
updateChunk();
}
else
{
relativePosition = newRelativePosition;
}
}
friend BlockIterator operator +(PositionI p, BlockIterator bi)
{
bi += p;
return bi;
}
friend BlockIterator operator +(BlockIterator bi, PositionI p)
{
bi += p;
return bi;
}
};
class BlockWorld final : public BlockWorldBase
{
public:
BlockIterator getIterator(PositionI p)
{
return BlockIterator(this, p);
}
};
Если вы оставляете утверждения и получаете доступ через BlockIterator, вы никогда не должны испытывать ошибки
void drawBlock(Renderer &renderer, BlockIterator bi)
{
BlockIterator nxBlockIterator = bi + PositionI(-1, 0, 0);
BlockIterator pxBlockIterator = bi + PositionI(1, 0, 0);
BlockIterator nyBlockIterator = bi + PositionI(0, -1, 0);
BlockIterator pyBlockIterator = bi + PositionI(0, 1, 0);
BlockIterator nzBlockIterator = bi + PositionI(0, 0, -1);
BlockIterator pzBlockIterator = bi + PositionI(0, 0, 1);
if(nxBlockIterator.get().isPXFaceBlocked())
bi.get().renderNXFace(renderer, bi);
if(pxBlockIterator.get().isNXFaceBlocked())
bi.get().renderPXFace(renderer, bi);
if(nyBlockIterator.get().isPYFaceBlocked())
bi.get().renderNYFace(renderer, bi);
if(pyBlockIterator.get().isNYFaceBlocked())
bi.get().renderPYFace(renderer, bi);
if(nzBlockIterator.get().isPZFaceBlocked())
bi.get().renderNZFace(renderer, bi);
if(pzBlockIterator.get().isNZFaceBlocked())
bi.get().renderPZFace(renderer, bi);
bi.get().renderCenter(renderer, bi);
}
Другие решения
Вы не показываете, как переменная b_blocks объявляется или инициализируется, но, учитывая, что вы получаете ошибку сегментации, скорее всего, вы объявили ее меньшим размером, чем ваш CHUNK_SIZE.