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

Support
1

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！

2

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

2 Likes
3

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
4

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
5

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;
}
6

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