View Issue Details [ Jump to Notes ] [ Print ]
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 
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)
TagsNo tags attached.
ProjectTBD
Typeincorrect functionality
Attached Filespng file icon Screen shot 2012-12-06 at 8.58.59 .png [^] (13,243 bytes) 2012-12-06 09:02


png file icon Screen shot 2012-12-06 at 8.59.07 .png [^] (17,529 bytes) 2012-12-06 09:02


png file icon Screen shot 2012-12-06 at 8.59.15 .png [^] (20,022 bytes) 2012-12-06 09:02


png file icon Screen shot 2012-12-06 at 8.59.25 .png [^] (16,678 bytes) 2012-12-06 09:02


? file icon cube.stl [^] (1,926 bytes) 2012-12-06 09:03
? file icon grooves.stl [^] (20,922 bytes) 2012-12-06 09:04
? file icon diff_new.stl [^] (58,592 bytes) 2012-12-06 09:04
? file icon test_delaunay_input.vtk [^] (917 bytes) 2014-01-02 14:06
? file icon delaunay_output.vtk [^] (967 bytes) 2014-01-02 14:06
txt file icon CMakeLists.txt [^] (261 bytes) 2014-01-02 14:10 [Show Content]
cxx file icon Delaunay2DTest.cxx [^] (1,038 bytes) 2014-01-02 14:11
png file icon SubdivisionResults.png [^] (10,998 bytes) 2014-01-03 12:02

 Relationships

  Notes
(0029833)
Andriy Fedorov (reporter)
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 (administrator)
2013-12-16 13:50

 Cory, can you investigate and see what the problem might be?
(0032048)
Cory Quammen (developer)
2013-12-23 15:57

 I am able to reproduce this error. Investigating.
(0032112)
Cory Quammen (developer)
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 (developer)
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 (developer)
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 (developer)
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 (administrator)
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 (administrator)
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.

 Issue History
Date Modified Username Field Change
2012-12-06 09:01 Andriy Fedorov New Issue
2012-12-06 09:02 Andriy Fedorov File Added: Screen shot 2012-12-06 at 8.58.59 .png
2012-12-06 09:02 Andriy Fedorov File Added: Screen shot 2012-12-06 at 8.59.07 .png
2012-12-06 09:02 Andriy Fedorov File Added: Screen shot 2012-12-06 at 8.59.15 .png
2012-12-06 09:02 Andriy Fedorov File Added: Screen shot 2012-12-06 at 8.59.25 .png
2012-12-06 09:03 Andriy Fedorov Note Added: 0029833
2012-12-06 09:03 Andriy Fedorov File Added: cube.stl
2012-12-06 09:04 Andriy Fedorov File Added: grooves.stl
2012-12-06 09:04 Andriy Fedorov File Added: diff_new.stl
2013-12-16 13:50 Dave DeMarle Note Added: 0031949
2013-12-16 13:50 Dave DeMarle Assigned To => Cory Quammen
2013-12-16 13:50 Dave DeMarle Status backlog => tabled
2013-12-23 15:57 Cory Quammen Note Added: 0032048
2013-12-27 21:46 Dave DeMarle Status tabled => backlog
2013-12-27 21:46 Dave DeMarle Status backlog => active development
2014-01-02 14:04 Cory Quammen Note Added: 0032112
2014-01-02 14:06 Cory Quammen File Added: test_delaunay_input.vtk
2014-01-02 14:06 Cory Quammen File Added: delaunay_output.vtk
2014-01-02 14:10 Cory Quammen File Added: CMakeLists.txt
2014-01-02 14:11 Cory Quammen File Added: Delaunay2DTest.cxx
2014-01-02 14:13 Cory Quammen Note Added: 0032114
2014-01-02 17:13 Cory Quammen Note Added: 0032118
2014-01-03 12:02 Cory Quammen File Added: SubdivisionResults.png
2014-01-03 12:03 Cory Quammen Note Added: 0032128
2014-09-19 09:02 Cory Quammen Status active development => backlog
2016-07-06 16:48 Berk Geveci Status backlog => expired
2016-07-06 16:48 Berk Geveci Note Added: 0036275
2016-08-12 09:55 Kitware Robot Note Added: 0037296
2016-08-12 09:55 Kitware Robot Status expired => closed
2016-08-12 09:55 Kitware Robot Resolution open => moved

Copyright © 2000 - 2018 MantisBT Team