How to find convex hull of a set of 3D points?

How to find the convex hull of a set of 3D points? I did not find a method in the VTK class. Similar functions are vtkHull and vtkPointsProjectedHull, but from the description it is not a way to obtain a set of 3D point convex hulls.
For 2D points, just use vtkConvex2D. For 3D points, maybe there is no vtkConvex3D method?
Thank you very much!

You can get convex hull of a 3D pointset using vtkDelaunay3D.

2 Likes

Hello, Wang,

Complementing Andras’ answer, here’s an example with a full pipeline to extract the triangulated hull from the tetra tesselation generated by vtkDelaunay3D: https://vtk.org/Wiki/VTK/Examples/Boneyard/Cxx/PolyData/ConvexHullDelaunay3D

cheers,

Paulo

1 Like

Thank you all, I will try the classes and examples you gave. The example website you gave is very useful. I did not find the example searched on https://lorensen.github.io/VTKExamples/site/Cxx/. It may be because they have different categories.
Thanks again!

1 Like

output output.vtp (2.4 KB) points.vtp (3.5 KB)
Hello, Paulo

When I used this method, I found that the convex hull generated seemed inconsistent with the definition of convex hull I thought.
I used a point set generated from 100 random points to find the convex hull, but found that some of the triangular faces are concave. Is there a problem with my parameter settings?

cheers,

Wang

#include <vtkPoints.h>
#include <vtkPolyData.h>
#include <vtkDelaunay3D.h>
#include <vtkUnstructuredGrid.h>
#include <vtkSmartPointer.h>
#include <vtkXMLPolyDataWriter.h>
#include <vtkXMLUnstructuredGridWriter.h>
#include <vtkCellArray.h>
#include <vtkDataSetSurfaceFilter.h>
#include <vtkActor.h>
#include <vtkPolyDataMapper.h>
#include <vtkRenderer.h>
#include <vtkRenderWindow.h>
#include <vtkRenderWindowInteractor.h>
#include <vtkInteractorStyleTrackballCamera.h>

int main(int, char* [])
{
//Create some random points

vtkSmartPointer<vtkPoints> points =
    vtkSmartPointer< vtkPoints >::New();

for (int index = 0; index < 100; ++index)
{
    points->InsertNextPoint(std::rand(), std::rand(), std::rand());
}
vtkSmartPointer< vtkPolyData> polydata =
    vtkSmartPointer<vtkPolyData>::New();
polydata->SetPoints(points);

vtkSmartPointer<vtkXMLPolyDataWriter> pointsWriter =
    vtkSmartPointer<vtkXMLPolyDataWriter>::New();
pointsWriter->SetFileName("points.vtp");
pointsWriter->SetInputData(polydata);
pointsWriter->Write();

// Create the convex hull of the pointcloud
vtkSmartPointer<vtkDelaunay3D> delaunay =
    vtkSmartPointer< vtkDelaunay3D >::New();
delaunay->SetInputData(polydata);
delaunay->Update();

vtkSmartPointer<vtkDataSetSurfaceFilter> surfaceFilter =
    vtkSmartPointer<vtkDataSetSurfaceFilter>::New();
surfaceFilter->SetInputConnection(delaunay->GetOutputPort());
surfaceFilter->Update();

vtkSmartPointer<vtkXMLUnstructuredGridWriter> ugWriter =
    vtkSmartPointer<vtkXMLUnstructuredGridWriter>::New();
ugWriter->SetInputConnection(delaunay->GetOutputPort());
ugWriter->SetFileName("delaunay.vtu");
ugWriter->Write();

vtkSmartPointer<vtkPolyDataMapper> surfaceMapper = vtkSmartPointer<vtkPolyDataMapper>::New();
surfaceMapper->SetInputConnection(surfaceFilter->GetOutputPort());
vtkSmartPointer<vtkActor> surfaceActor = vtkSmartPointer<vtkActor>::New();
surfaceActor->SetMapper(surfaceMapper);

vtkSmartPointer<vtkRenderer> renderer =
    vtkSmartPointer<vtkRenderer>::New();
renderer->AddActor(surfaceActor);
vtkSmartPointer<vtkRenderWindow> renderWindow =
    vtkSmartPointer<vtkRenderWindow>::New();
renderWindow->AddRenderer(renderer);
vtkSmartPointer<vtkRenderWindowInteractor> renderWindowInteractor =
    vtkSmartPointer<vtkRenderWindowInteractor>::New();
renderWindowInteractor->SetRenderWindow(renderWindow);
vtkSmartPointer<vtkInteractorStyleTrackballCamera> InteractorStyleTrackballCamera = vtkSmartPointer<vtkInteractorStyleTrackballCamera>::New();
renderWindowInteractor->SetInteractorStyle(InteractorStyleTrackballCamera);
renderWindow->Render();
renderWindowInteractor->Start();


return EXIT_SUCCESS;
}

Hello, Wang,

First, sorry for the late response.

By definition, a Delaunay tesselation’s outer boundary is convex, but we know theory is not always exactly the same as implementation. Take a look at the vtkDelaunay3D's documentation: https://vtk.org/doc/nightly/html/classvtkDelaunay3D.html:

The output of the Delaunay triangulation is supposedly a convex hull. In certain cases this implementation may not generate the convex hull. This behavior can be controlled by the Offset instance variable. Offset is a multiplier used to control the size of the initial triangulation. The larger the offset value, the more likely you will generate a convex hull; and the more likely you are to see numerical problems.

(emphasis added)

So I guess you need to play a bit with said parameter to get satisfactory results.

regards,

Paulo

1 Like