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

Question

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

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

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

第一张图片，体素仍然连接:

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

Answer 1

分割/标记是方法(类似于光栅 A* 和洪水填充)。

1. 为每个体素添加一个标志变量/空间

   此标志将用于判断是否使用了体素......并且可以在后者用作临时值......

2. 将所有标志清零并设置实际对象 ID=1。

3. 使用 flag=0 选取第一个体素

4. 用实际对象 ID 大量填充它

   因此使用 6 或 26 连接(类似于 2D 中的 4 或 8 连接)用 ID 填充体素标志。

5. 增加 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 包含我们输入 map 的各个体素(硬编码在我的应用程序构造函数中，几乎没有对象)。 flg 数组保存对象的 id，相应的体素被标记为(枚举)，它稍后用于为每个对象着色来自调色板 pal[ 的不同颜色]。为了尽可能简单，我没有做任何优化(填充和渲染因此非常慢，可以很多优化)。

此处预览(调用 recolor() 后):

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

如果你想使用它，gl_simple.h 在这里:

• complete GL+GLSL+VAO/VBO C++ example

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