所以我正在构建一个基于体素的物理模拟器，其中的体素可以被破坏。每个体素化的物体都有一种“中心体素”来描述它，我称之为“和平A”。
所有体素都被模拟为一个，直到它们与“和平A”或附加到它的另一个体素分开，然后它们(和/或连接到该体素的其他体素)被放入一个具有自己的模拟物理的新对象中。这就是我的问题，如何检查体素是否仍然附着？以尽可能最有效的方式？
当我扩大规模时，寻路听起来会减慢分配速度，但很高兴尝试找出它是否是最佳选择。当一个体素被破坏时立即更新所有体素听起来也不太好。各位大神有什么想法吗？
为了清楚起见，这里有一些图(请原谅我糟糕的鼠标手写)
第一张图片，体素仍然连接:
第二张图片，当体素分离时:
最佳答案
分割/标记是方法(类似于光栅 A* 和洪水填充)。
为每个体素添加一个标志变量/空间
此标志将用于判断是否使用了体素......并且可以在后者用作临时值......
将所有标志清零并设置实际对象
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 包含我们输入 map 的各个体素(硬编码在我的应用程序构造函数中，几乎没有对象)。 flg 数组保存对象的 id，相应的体素被标记为(枚举)，它稍后用于为每个对象着色来自调色板 pal[ 的不同颜色]。为了尽可能简单，我没有做任何优化(填充和渲染因此非常慢，可以很多优化)。
此处预览(调用 recolor() 后):
如您所见，所有连接的体素共享相同的颜色，这意味着它们在 flg 数组(属于同一对象)中具有相同的 id 编号，因此算法和代码按预期工作。
如果你想使用它，gl_simple.h 在这里:
所以你只需要将 VCL 事件移植到你的环境风格中......
关于algorithm - 检测体素或体素组是否仍连接到对象的其余部分，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/58676100/