检测体素或体素组是否仍连接到对象的其余部分

Question

所以我正在构建一个基于体素的物理模拟器，其中的体素可以被破坏。每个体素化对象都有一种"center voxel"来描述它，我称之为"peace A"。
所有体素都被模拟为一个，直到它们与"peace A"或附加的另一个体素分开到它，然后他们（and/or 连接到该体素的其他体素）被放入一个具有自己的模拟物理的新对象中。这就是我的问题，如何检查体素是否仍然附着？以尽可能最有效的方式？

寻路听起来好像在我扩大规模时会减慢分配速度，但很乐意尝试找出它是否是最佳选择。当一个体素被破坏时立即更新所有体素听起来也不太好。各位大神有什么想法吗？

为了清楚起见，这里有一些图纸（ps请原谅我糟糕的鼠标手写）

第一张图像，体素仍然连接：

第二张图片，当体素分离时：

Answer 1

随机选择一个未连接的对象
递归获取up/down/left/right对象直到没有剩余（总是检查对象是否已经连接）
如果场景中没有留下未连接的对象，则停止
转到步骤 1

Answer 2

Segmentation/labeling 是方式（类似于光栅 A* 和洪水填充）。

为每个体素添加一个标志variable/space

此标志将用于判断是否使用了体素...并且可以在后者用作临时值...
将所有标志清零并设置实际对象 ID=1.
用flag=0
选择第一个体素
用实际对象填充ID

所以使用 6 或 26 连接（类似于 2D 中的 4 或 8 连接）用 ID 填充体素标志。
增加 ID 并转到 #3

当没有体素时停止 flag=0

在此之后，标志包含您的原始对象被拆分成的子对象 ID，ID 包含您的新对象的数量 +1。

[edit1] C++/VCL/OpenGL 示例

//---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop
#include "Unit1.h"
#include "gl_simple.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
const int n=16;     // voxel map resolution
bool map[n][n][n];  // voxel map
int  flg[n][n][n];  // (flag)
int pal[]=          // 0xAABBGGRR
    {
    0x007F0000,
    0x00007F00,
    0x0000007F,
    0x00007F7F,
    0x007F007F,
    0x007F7F00,
    0x00FF0000,
    0x0000FF00,
    0x000000FF,
    0x0000FFFF,
    0x00FF00FF,
    0x00FFFF00,
    };
const int pals=sizeof(pal)/sizeof(pals);
//---------------------------------------------------------------------------
void fill(int x,int y,int z,int id)
    {
    // inside map check
    if ((x<0)||(x>=n)) return;
    if ((y<0)||(y>=n)) return;
    if ((z<0)||(z>=n)) return;
    // is it active voxel?
    if (!map[x][y][z]) return;
    // already filled with the same id?
    if (flg[x][y][z]==id) return;
    // set flag
    flg[x][y][z]=id;
    // fill neighbors
    fill(x-1,y,z,id);
    fill(x+1,y,z,id);
    fill(x,y-1,z,id);
    fill(x,y+1,z,id);
    fill(x,y,z-1,id);
    fill(x,y,z+1,id);
    fill(x-1,y-1,z,id);
    fill(x-1,y+1,z,id);
    fill(x+1,y-1,z,id);
    fill(x+1,y+1,z,id);
    fill(x-1,y,z-1,id);
    fill(x-1,y,z+1,id);
    fill(x+1,y,z-1,id);
    fill(x+1,y,z+1,id);
    fill(x,y-1,z-1,id);
    fill(x,y-1,z+1,id);
    fill(x,y+1,z-1,id);
    fill(x,y+1,z+1,id);
    fill(x-1,y-1,z-1,id);
    fill(x-1,y-1,z+1,id);
    fill(x-1,y+1,z-1,id);
    fill(x-1,y+1,z+1,id);
    fill(x+1,y-1,z-1,id);
    fill(x+1,y-1,z+1,id);
    fill(x+1,y+1,z-1,id);
    fill(x+1,y+1,z+1,id);
    }
//---------------------------------------------------------------------------
void recolor()
    {
    int x,y,z,id;
    // clear all flags to zero and set actual object ID=1
    id=1;
    for (x=0;x<n;x++)
     for (y=0;y<n;y++)
      for (z=0;z<n;z++)
       flg[x][y][z]=0;
    // pick first voxel with flag=0
    for (x=0;x<n;x++)
     for (y=0;y<n;y++)
      for (z=0;z<n;z++)
       if (map[x][y][z])
        if (flg[x][y][z]==0)
            {
            // flood fill it with actual object ID
            fill(x,y,z,id);
            // increment ID and goto #3
            id++;
            }
    }
//---------------------------------------------------------------------------
void TForm1::draw()
    {
    glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
    glEnable(GL_CULL_FACE);
    glEnable(GL_DEPTH_TEST);
    glEnable(GL_LIGHTING);
    glEnable(GL_LIGHT0);
    glEnable(GL_COLOR_MATERIAL);

    // center the view around map[][][]
    glMatrixMode(GL_MODELVIEW);
    glLoadIdentity();
    glTranslatef(0.0,0.0,-80.0);
    glRotatef( 15.0,1.0,0.0,0.0);
    glTranslatef(-n,-n,-n);

    // render map[][][] as cubes (very slow old api version for simplicity)
    int x,y,z,i;
    for (x=0;x<n;x++)
     for (y=0;y<n;y++)
      for (z=0;z<n;z++)
       if (map[x][y][z])
        {
        glPushMatrix();
        glTranslatef(x+x,y+y,z+z);
        glColor4ubv((BYTE*)&(pal[flg[x][y][z]%pals]));
        glBegin(GL_QUADS);
        for (i=0;i<3*24;i+=3)
            {
            glNormal3fv(vao_nor+i);
            glVertex3fv(vao_pos+i);
            }
        glEnd();
        glPopMatrix();
        }

    glFlush();
    SwapBuffers(hdc);
    }
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner):TForm(Owner)
    {
    gl_init(Handle);

    // init map[][][]
    int x,y,z,i0=2,i1=n-i0-1,xx,yy,zz;
    for (x=0;x<n;x++)
     for (y=0;y<n;y++)
      for (z=0;z<n;z++)
        {
        // clear map
        map[x][y][z]=false;
        // cube edges
        if (((x>=i0)&&(x<=i1))&&((y==i0)||(y==i1))&&((z==i0)||(z==i1))) map[x][y][z]=true;
        if (((y>=i0)&&(y<=i1))&&((x==i0)||(x==i1))&&((z==i0)||(z==i1))) map[x][y][z]=true;
        if (((z>=i0)&&(z<=i1))&&((x==i0)||(x==i1))&&((y==i0)||(y==i1))) map[x][y][z]=true;
        // ball
        xx=x-8; xx*=xx;
        yy=y-8; yy*=yy;
        zz=z-8; zz*=zz;
        if (xx+yy+zz<=16) map[x][y][z]=true;
        // X
        if ((y==i0)&&(x==  z  )&&(x>=4)&&(x<12)) map[x][y][z]=true;
        if ((y==i0)&&(x==n-z-1)&&(x>=4)&&(x<12)) map[x][y][z]=true;
        }
     recolor();
    }
//---------------------------------------------------------------------------
void __fastcall TForm1::FormDestroy(TObject *Sender)
    {
    gl_exit();
    }
//---------------------------------------------------------------------------
void __fastcall TForm1::FormResize(TObject *Sender)
    {
    gl_resize(ClientWidth,ClientHeight);
    draw();
    }
//---------------------------------------------------------------------------
void __fastcall TForm1::FormPaint(TObject *Sender)
    {
    draw();
    }
//---------------------------------------------------------------------------
void __fastcall TForm1::Timer1Timer(TObject *Sender)
    {
    draw();
    }
//---------------------------------------------------------------------------

你可以忽略 VCL 和 OpenGL 渲染唯一重要的东西在代码的顶部直到 (包括）函数 void recolor(); map 保存我们输入地图的各个体素（硬编码在我的应用程序构造函数中，几乎没有对象）。 flg 数组保存对象的 id，对应的体素被标记（枚举），稍后用于使用调色板 pal[] 中的不同颜色为每个对象着色。为了尽可能简单，我没有做任何优化（因此填充和渲染非常慢，可以优化很多）。

这里预览（调用recolor()后）：

如您所见，所有连接的体素共享相同的颜色，这意味着它们在 flg 数组（属于同一对象）中具有相同的 id 数字，因此算法和代码按预期工作.

如果您想使用它，gl_simple.h 在这里：

所以您只需要将 VCL 事件移植到您的环境风格中...

检测体素或体素组是否仍连接到对象的其余部分

Detecting if Voxel or voxel group is still connected to rest of object

algorithm

unity3d

path

physics

voxel