MantisBT - VTK
View Issue Details
IDProjectCategoryView StatusDate SubmittedLast Update
0013708VTK(No Category)public2012-12-06 09:012016-08-12 09:55
ReporterAndriy Fedorov 
Assigned ToCory Quammen 
PriorityhighSeverityminorReproducibilityhave not tried
StatusclosedResolutionmoved 
PlatformOSOS Version
Product Version 
Target VersionFixed in Version 
ProjectTBD
Typeincorrect functionality
Summary0013708: vtkBooleanOperationPolyDataFilterproduces incorrect result
DescriptionI am trying to subtract two relatively simple shapes, and the result does not seem to be correct. Attached screenshots are:

1) input 1 (triangulated parallelepiped)
2) input 2 (a set of narrow parallelepipeds, triangulated)
3) visualized together
4) result of boolean difference operator

Tested with today's build of master (git 8202e05d26faf89d04c69c8b93a0db989d8c3f9e)
Steps To Reproduce
Additional Information
TagsNo tags attached.
Relationships
Attached Filespng Screen shot 2012-12-06 at 8.58.59 .png (13,243) 2012-12-06 09:02
https://www.vtk.org/Bug/file/9353/Screen%20shot%202012-12-06%20at%208.58.59%20.png
png

png Screen shot 2012-12-06 at 8.59.07 .png (17,529) 2012-12-06 09:02
https://www.vtk.org/Bug/file/9354/Screen%20shot%202012-12-06%20at%208.59.07%20.png
png

png Screen shot 2012-12-06 at 8.59.15 .png (20,022) 2012-12-06 09:02
https://www.vtk.org/Bug/file/9355/Screen%20shot%202012-12-06%20at%208.59.15%20.png
png

png Screen shot 2012-12-06 at 8.59.25 .png (16,678) 2012-12-06 09:02
https://www.vtk.org/Bug/file/9356/Screen%20shot%202012-12-06%20at%208.59.25%20.png
png

? cube.stl (1,926) 2012-12-06 09:03
https://www.vtk.org/Bug/file/9357/cube.stl
? grooves.stl (20,922) 2012-12-06 09:04
https://www.vtk.org/Bug/file/9358/grooves.stl
? diff_new.stl (58,592) 2012-12-06 09:04
https://www.vtk.org/Bug/file/9359/diff_new.stl
? test_delaunay_input.vtk (917) 2014-01-02 14:06
https://www.vtk.org/Bug/file/9585/test_delaunay_input.vtk
? delaunay_output.vtk (967) 2014-01-02 14:06
https://www.vtk.org/Bug/file/9586/delaunay_output.vtk
txt CMakeLists.txt (261) 2014-01-02 14:10
https://www.vtk.org/Bug/file/9587/CMakeLists.txt
cxx Delaunay2DTest.cxx (1,038) 2014-01-02 14:11
https://www.vtk.org/Bug/file/9588/Delaunay2DTest.cxx
png SubdivisionResults.png (10,998) 2014-01-03 12:02
https://www.vtk.org/Bug/file/9592/SubdivisionResults.png
png
Issue History
Date ModifiedUsernameFieldChange
2012-12-06 09:01Andriy FedorovNew Issue
2012-12-06 09:02Andriy FedorovFile Added: Screen shot 2012-12-06 at 8.58.59 .png
2012-12-06 09:02Andriy FedorovFile Added: Screen shot 2012-12-06 at 8.59.07 .png
2012-12-06 09:02Andriy FedorovFile Added: Screen shot 2012-12-06 at 8.59.15 .png
2012-12-06 09:02Andriy FedorovFile Added: Screen shot 2012-12-06 at 8.59.25 .png
2012-12-06 09:03Andriy FedorovNote Added: 0029833
2012-12-06 09:03Andriy FedorovFile Added: cube.stl
2012-12-06 09:04Andriy FedorovFile Added: grooves.stl
2012-12-06 09:04Andriy FedorovFile Added: diff_new.stl
2013-12-16 13:50Dave DeMarleNote Added: 0031949
2013-12-16 13:50Dave DeMarleAssigned To => Cory Quammen
2013-12-16 13:50Dave DeMarleStatusbacklog => tabled
2013-12-23 15:57Cory QuammenNote Added: 0032048
2013-12-27 21:46Dave DeMarleStatustabled => backlog
2013-12-27 21:46Dave DeMarleStatusbacklog => active development
2014-01-02 14:04Cory QuammenNote Added: 0032112
2014-01-02 14:06Cory QuammenFile Added: test_delaunay_input.vtk
2014-01-02 14:06Cory QuammenFile Added: delaunay_output.vtk
2014-01-02 14:10Cory QuammenFile Added: CMakeLists.txt
2014-01-02 14:11Cory QuammenFile Added: Delaunay2DTest.cxx
2014-01-02 14:13Cory QuammenNote Added: 0032114
2014-01-02 17:13Cory QuammenNote Added: 0032118
2014-01-03 12:02Cory QuammenFile Added: SubdivisionResults.png
2014-01-03 12:03Cory QuammenNote Added: 0032128
2014-09-19 09:02Cory QuammenStatusactive development => backlog
2016-07-06 16:48Berk GeveciStatusbacklog => expired
2016-07-06 16:48Berk GeveciNote Added: 0036275
2016-08-12 09:55Kitware RobotNote Added: 0037296
2016-08-12 09:55Kitware RobotStatusexpired => closed
2016-08-12 09:55Kitware RobotResolutionopen => moved

Notes
(0029833)
Andriy Fedorov   
2012-12-06 09:03   
Attached are the models that together with the script below allow to reproduce the problem:

import vtk, sys

r1 = vtk.vtkSTLReader()
r1.SetFileName(sys.argv[1])
r1.Update()

r2 = vtk.vtkSTLReader()
r2.SetFileName(sys.argv[2])
r2.Update()

inter = vtk.vtkBooleanOperationPolyDataFilter()
inter.SetOperationToDifference()
inter.SetInputConnection(0, r1.GetOutputPort())
inter.SetInputConnection(1, r2.GetOutputPort())
inter.Update()

w = vtk.vtkSTLWriter()
w.SetInputConnection(inter.GetOutputPort())
w.SetFileName(sys.argv[3])
w.Update()
(0031949)
Dave DeMarle   
2013-12-16 13:50   
Cory, can you investigate and see what the problem might be?
(0032048)
Cory Quammen   
2013-12-23 15:57   
I am able to reproduce this error. Investigating.
(0032112)
Cory Quammen   
2014-01-02 14:04   
I have tracked the problem down to the vtkDelaunay2D filter. This filter is supposed to treat line cells in the input set via SetSourceConnection() as edges that must appear in the output of the Delaunay triangulation, making the output in this case not necessarily a true Delaunay triangulation but a constrained Delaunay triangulation instead. In some cases, not all required edges are present in the output of the Delaunay triangulation. I'm investigating why.
(0032114)
Cory Quammen   
2014-01-02 14:13   
Also, I have attached an input file (test_delaunay_input.vtk) containing a polydata with points and line segments derived from the original test file from Andriy. This file causes the constrained Delaunay triangulation within vtkDelaunay2D filter to fail (output in delaunay_output.vtk). The test program that produced the output is attached. When compiled, one can run it with

./Delaunay2DTest test_delaunay_input.vtk delaunay_output.vtk

to get the attached output file.
(0032118)
Cory Quammen   
2014-01-02 17:13   
vtkDelaunay2D is bailing out on restoring the constraint edges when failing to find a neighboring cell in the neighborhood of a constraint edge. This is likely because the triangles produced by the Delaunay triangulation are not wound in a consistent ordering in the test input I posted, which seems like a bug.
(0032128)
Cory Quammen   
2014-01-03 12:03   
I think the underlying problem is that the Delaunay triangulation for the box geometry results in very long and thing triangles, which is known to cause problems with the Delaunay algorithm. A solution is to insert new points into the geometry to make the output triangles not quite as thin.

As a workaround, I recommend subdividing at least the cube.stl geometry using the vtkLinearSubdivisionFilter. By setting the NumberOfSubdivisions in the vtkLinearSubdivisionFilter to 2, I can get good results. See the image file SubdivisionResults.png I posted.
(0036275)
Berk Geveci   
2016-07-06 16:48   
Setting to status of bugs that have not been updated in the last year to expired. Please re-open if still important.
(0037296)
Kitware Robot   
2016-08-12 09:55   
Resolving issue as `moved`.

This issue tracker is no longer used. Further discussion of this issue may take place in the current VTK Issues page linked in the banner at the top of this page.