VTK – Delete Cells And Create Model Without Invalid Points

We have a 3D model mace like the above image.
Let’s delete the cells that are in the negative X-axis space, there are some invalid points in the model after the operation.

    vtkSPtrNew( reader, vtkSTLReader );
    reader->SetFileName( "/Users/weiyang/Desktop/mace.stl" );
    reader->Update();

    vtkSPtrNew( data, vtkPolyData );
    data->DeepCopy( reader->GetOutput() );

    vtkSPtrNew( cutPlane, vtkPlane );
    cutPlane->SetNormal( 1, 0, 0 );
    cutPlane->SetOrigin( 0, 0, 0 );

    // =============== delete some cells, clip by cutPlane ====================
    cout << "point count: " << data->GetNumberOfPoints() << endl;
    for( int i = 0; i < data->GetNumberOfCells(); ++i )
    {
        vtkCell *cell = data->GetCell( i );
        Point center( 0, 0, 0 );
        for( int j = 0; j < cell->GetNumberOfPoints(); j++ )
        {
            Point pt( data->GetPoint( cell->GetPointId( j ) ) );
            center = center + pt;
        }
        center /= 3;
        if ( cutPlane->EvaluateFunction( center.point ) < 0 )
        {
            data->DeleteCell( i );
        }
    }
    data->RemoveDeletedCells();
    cout << "point count: " << data->GetNumberOfPoints() << endl;
    // ===================== end! ===================

Here is a interesting truth about storing the data. The class vtkXMLPolyDataWriter will write all points to file but vtkSTLWriter writes only points which are used by cells.

    // vtkXMLPolyDataWriter will write all points to file
    vtkSPtrNew( xmlWriter, vtkXMLPolyDataWriter );
    xmlWriter->SetInputData( data );
    xmlWriter->SetFileName( "/Users/weiyang/Desktop/clipped.vtp" );
    xmlWriter->Update();

    // vtkSTLWriter write only points which are used by cells
    vtkSPtrNew( stlWriter, vtkSTLWriter );
    stlWriter->SetInputData( data );
    stlWriter->SetFileName( "/Users/weiyang/Desktop/clipped.stl" );
    stlWriter->Update();

Generate a new polyData which has not invalid point. We have to colloct the points that are used by cells and update the point ids in the cell lists. I used binary search algorithm to speed up the process.

int binary_Find( std::vector<int> array, int value )
{
    int l = 0;
    int r = array.size() - 1;
    int mid = -1;
    while( l <= r )
    {
        mid = (l + r) / 2;
        if( array[mid] == value )
        {
            return mid;
        }
        else if( array[mid] < value )
        {
            l = mid+1;
        }
        else {
            r = mid-1;
        }
    }
    return -1;
}

int main()
{
//...
    // ================ generate a new polyData without invalid points ===============
    std::vector<bool> validPts;
    for( int i = 0; i < data->GetNumberOfPoints(); ++i )
    {
        validPts.push_back( false );
    }
    for( int i = 0; i < data->GetNumberOfCells(); ++i )
    {
        vtkIdType npts;
        const vtkIdType *pts;
        data->GetCellPoints( i, npts, pts );
        for( int j = 0; j < npts; ++j )
        {
            validPts[ pts[j] ] = true;
        }
    }

    vtkSPtrNew( newData, vtkPolyData );
    vtkSPtrNew( newPoints, vtkPoints );
    vtkSPtrNew( newCells, vtkCellArray);
    std::vector<int> newPtIds;
    for( int i = 0; i < data->GetNumberOfPoints(); ++i )
    {
        if( validPts[i] )
        {
            newPoints->InsertNextPoint( data->GetPoint( i ) );
            newPtIds.push_back( i );
        }
    }
    for( int i = 0; i < data->GetNumberOfCells(); ++i )
    {
        vtkIdType npts;
        const vtkIdType *pts;
        data->GetCellPoints( i, npts, pts );
        vtkSPtrNew( list, vtkIdList );
        for( int j = 0; j < npts; ++j )
        {
            int index = binary_Find( newPtIds, pts[j] );
            list->InsertNextId( index );
        }
        newCells->InsertNextCell( list );
    }
    newData->SetPoints( newPoints );
    newData->SetPolys( newCells );
    newData->Modified();

We can find that the number of points of the original model is 700 and the new result is 394.