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

Question

So I am building a voxel-based physics simulator in which voxels can be destroyed. Every voxelized object has a kind of "center voxel" to describe it, ill call it "peace A".
All voxels are simulated as one until they are separated from "peace A" or another voxel attached to it, then they(and/or other voxels connected to that voxel) get put into a new object with its own simulated physics. And here lies my problem, How Do I check if the voxel is still attached? in the most efficient way possible?

pathfinding sounds like it would slow down allot when I scale up but happy to try and figure that out if its the best option. and updating all voxels at once when one voxel is destroyed doesn't sound too good either. Any of you geniuses have any ideas?

here are some drawings for clarity(ps please excuse my bad mouse-handwriting)

first image, with voxels still connected:

second image, when the voxels separate:

Answer 1

Segmentation/labeling is the way (similar to raster A* and flood fill).

1. for each voxel add a flag variable/space

   this flag will be used to tell if voxel is used or not ... and can be used latter as a temp value...

2. clear all flags to zero and set actual object ID=1.

3. pick first voxel with flag=0

4. flood fill it with actual object ID

   so using 6 or 26 connectivity (analogy to 4 or 8 connectivity in 2D) flood fill the voxel flags with ID.

5. increment ID and goto #3

   stop when there are no more voxels with flag=0

After this the flag holds the sub object ID your original object is split into and ID holds the count of your new objects+1.

[edit1] C++/VCL/OpenGL example

//---------------------------------------------------------------------------
#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();
    }
//---------------------------------------------------------------------------

You can ignore the VCL stuff and also the OpenGL rendering The only important stuff is on the top of the code up to (including) function void recolor(); The map holds the individual voxels of our input map (hardcoded in my apps constructor with few objects). The flg array holds the id of object the corresponding voxel was labeled with (enumerated) and its used later for coloring each object with different color from the palette pal[]. To keep this as simple as I could I did not do any optimization (the fill and render are very slow because of that and can be optimized a lot).

Here preview (after calling the recolor()):

As you can see all the voxels connected share the same color which means they have the same id number in flg array (belong to same object) so the algo and code works as expected.

In case you want to use this the gl_simple.h is in here:

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

so you just need to port the VCL events into your environment style...

Answer 2

1. Pick a random, not connected, object
2. Recursively get the up/down/left/right object till there is no left (always checking if the object is already connected)
3. If there are no objects left in the scene that are not connected, stop
4. Go to Step 1