Find Different Independent Parts Of An Object

A 3D model may be composed of a few different parts. We want to find all the independent parts. In the following code snippet, the interface GetConnectedCellIds can help us to find all the parts, DrawCells will mark a part which is represented by some cell ids red color.

#include <iostream>
#include <vtkSmartPointer.h>
#include <vtkSphereSource.h>
#include <vtkActor.h>
#include <vtkConeSource.h>
#include <vtkRenderer.h>
#include <vtkRenderWindow.h>
#include <vtkPolyDataMapper.h>
#include <vtkRenderWindowInteractor.h>
#include <vtkCellData.h>
#include <vtkNamedColors.h>
#include <vtkColorTransferFunction.h>
#include <vtkTriangleFilter.h>
#include <vtkXMLPolyDataReader.h>
#include <vtkCharArray.h>

#define vtkSPtr vtkSmartPointer
#define vtkSPtrNew(Var, Type) vtkSPtr<Type> Var = vtkSPtr<Type>::New();

using namespace std;

struct Edge
{
    vtkIdType cellId;
    vtkIdType edgePt1;
    vtkIdType edgePt2;
};

void DrawCells( vtkSPtr<vtkPolyData> pd,
                vtkSPtr<vtkPolyDataMapper> mapper,
                vtkSPtr<vtkIdList> visitedCellIds )
{
    vtkNew<vtkCharArray> cellTypes;
    cellTypes->SetNumberOfComponents( 1 );
    for( int i = 0; i < pd->GetNumberOfCells(); ++i )
    {
        cellTypes->InsertNextValue( 0 );
    }
    for( int i = 0; i < visitedCellIds->GetNumberOfIds(); ++i )
    {
        auto cellId = visitedCellIds->GetId( i );
        cellTypes->InsertValue( cellId, 1 );
    }

    pd->GetCellData()->SetScalars( cellTypes );
    pd->GetCellData()->Modified();

    mapper->SetScalarModeToUseCellData();
    mapper->SetColorModeToMapScalars();

    vtkNew<vtkColorTransferFunction> lut;
    lut->AddRGBPoint( 0, 1, 1, 1 );
    lut->AddRGBPoint( 1, 0.8, 0, 0 );
    mapper->SetLookupTable( lut );
}

vtkSPtr<vtkIdList> GetConnectedCellIds( vtkPolyData *pd, vtkIdType seedCellId )
{
    vtkIdType nPts;
    vtkIdType *pts;
    pd->GetCellPoints( seedCellId, nPts, pts );
    std::vector<Edge> currrentEdges;
    for( int i = 0; i < 3; ++i )
    {
        Edge edge;
        edge.cellId = seedCellId;
        edge.edgePt1 = pts[i];
        edge.edgePt2 = pts[ (i+1) % 3 ];
        currrentEdges.push_back( edge );
    }
    vtkNew<vtkIdList> visitedCellIds;
    visitedCellIds->InsertNextId( seedCellId );
    std::vector<Edge> nextEdges;
    while ( currrentEdges.size() > 0 )
    {
        for( int i = 0; i < currrentEdges.size(); ++i )
        {
            Edge edge = currrentEdges[i];
            vtkNew<vtkIdList> neighborCellIds;
            pd->GetCellEdgeNeighbors( edge.cellId, edge.edgePt1, edge.edgePt2, neighborCellIds );
            for( int j = 0; j < neighborCellIds->GetNumberOfIds(); ++j )
            {
                auto neiCellId = neighborCellIds->GetId( j );
                if( -1 != visitedCellIds->IsId( neiCellId ) )
                {
                    continue;
                }
                pd->GetCellPoints( neiCellId, nPts, pts );
                vtkIdType thirdPt = -1;
                for( int k = 0; k < 3; ++k )
                {
                    if( pts[k] != edge.edgePt1 && pts[k] != edge.edgePt2 )
                    {
                        thirdPt = pts[k];
                        break;
                    }
                }
                if( -1 == thirdPt )
                {
                    continue;
                }

                Edge edge1;
                edge1.cellId = neiCellId;
                edge1.edgePt1 = edge.edgePt1;
                edge1.edgePt2 = thirdPt;

                Edge edge2;
                edge2.cellId = neiCellId;
                edge2.edgePt1 = edge.edgePt2;
                edge2.edgePt2 = thirdPt;

                nextEdges.push_back( edge1 );
                nextEdges.push_back( edge2 );
                visitedCellIds->InsertNextId( neiCellId );
            }
        }
        currrentEdges.swap( nextEdges );
        nextEdges.clear();
    }

    return visitedCellIds;
}

int main()
{
    vtkSPtrNew( reader, vtkXMLPolyDataReader );
    reader->SetFileName( "/Users/weiyang/Desktop/test.vtp" );
    reader->Update();

    auto *polyData = reader->GetOutput();

    vtkSPtrNew( triangleFilter, vtkTriangleFilter );
    triangleFilter->SetInputData( polyData );
    triangleFilter->PassLinesOff();
    triangleFilter->PassVertsOff();
    triangleFilter->Update();

    polyData = triangleFilter->GetOutput();

    vtkSPtrNew( mapper, vtkPolyDataMapper );
    mapper->SetInputData( polyData );

    vtkSPtrNew( actor, vtkActor );
    actor->SetMapper( mapper );

    // ============== start to split =================
    polyData->BuildCells();
    polyData->BuildLinks();

    vtkIdType pdCellCount = polyData->GetNumberOfCells();
    vtkIdType visCellCount = 0;
    std::vector<bool> markCellIds;
    std::vector< vtkSPtr<vtkIdList> > visCellIdsList;
    for( int i = 0; i < pdCellCount; ++i )
    {
        markCellIds.push_back( false );
    }
    while ( visCellCount != pdCellCount )
    {
        vtkIdType seedCellId = -1;
        for( int i = 0; i < pdCellCount; ++i )
        {
            if( !markCellIds[i] )
            {
                seedCellId = i;
            }
        }
        if( -1 == seedCellId )
        {
            break;
        }
        vtkSPtr<vtkIdList> visitedCells = GetConnectedCellIds( polyData, seedCellId );
        visCellCount += visitedCells->GetNumberOfIds();
        visCellIdsList.push_back( visitedCells );
        for( int i = 0; i < visitedCells->GetNumberOfIds(); ++i )
        {
            auto id = visitedCells->GetId( i );
            markCellIds[id] = true;
        }
    }

    cout << visCellIdsList.size() << endl;
    DrawCells( polyData, mapper, visCellIdsList[1] );
    // ============== finish: split =================

    vtkSPtrNew( renderer, vtkRenderer );
    renderer->AddActor(actor);
    renderer->SetBackground( 0, 0, 0 );

    vtkSPtrNew( renderWindow, vtkRenderWindow );
    renderWindow->AddRenderer( renderer );

    vtkSPtrNew( renderWindowInteractor, vtkRenderWindowInteractor );
    renderWindowInteractor->SetRenderWindow( renderWindow );

    renderer->ResetCamera();
    renderWindow->Render();
    renderWindowInteractor->Start();
    return 0;
}