在尺寸n的3D阵列中有效检查相邻的体素

Question

我的体素系统使用一个在运行时动态分配的平面3D阵列，但是每块生成数百万个立方体是不可行的。

>

我打算实现的第一个优化当然是不为遮挡的体素生成网格数据，这是一个好主意，但我不知道该怎么做。

我所有的尝试都遇到了难以调试的记忆分配问题，因此，我不得不把毛巾扔进去，问更多知识渊博的人。

我目前的化身就是这样

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 %dn", 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）是我实现的骇客，以免生成块时（否则它在生成块时都会违反内存访问的情况[chunksize] [chunksize] [chunksize] [chunksize] [Chunksize]，这不是很好好的。无意中的黑客骇客确保所有立方体都是生成的，但同样令人着迷。

这里的简洁问题如下：我的逻辑的哪一部分被打破了？（大概是所有的），如何以快速的方式正确检查相邻块，而不会导致界限出现错误？（我尝试通过手动编码例外情况，但事实证明这是无与伦比的，并且速度较慢且容易出现segfaulting）

Answer 1

我会使用以下内容：

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);
    }
};

如果您将主张留在并访问通过封锁仪，则不应永远不会seg fault

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);
}

Answer 2

您不显示B_Blocks变量是如何声明或初始化的，但是鉴于您遇到了细分错误，因此您可能将其声明为尺寸小于chunk_size。