MantisBT - VTK
View Issue Details
IDProjectCategoryView StatusDate SubmittedLast Update
0009000VTK(No Category)public2009-05-11 12:172016-08-12 09:55
ReporterAndy Turner 
Assigned ToKitware Robot 
PrioritynormalSeveritymajorReproducibilityalways
StatusclosedResolutionmoved 
PlatformOSOS Version
Product Version 
Target VersionFixed in Version 
Project
Type
Summary0009000: vtkQuadricDecimation filter produces bad geometry in output
DescriptionvtkQuadricDecimation filter can introduce non-manifold faces and isolated vertices (i.e. unused vertices which have not been removed by edge collapsing process).

The problem arises when decimating particular polydata meshes. I do not have one small enough to upload, but it happens consistently.
Steps To Reproduce
Additional InformationThe problem arises because of removing a particular configuration of edges. Say that you've got three triangles with vertex indices:-

(0,1,3), (1,2,3), (0,3,2)

There are 6 choices of edge to collapse; if edges (0,2) is collapsed, faces (0,1,3) and (1,2,3) become faces (0,1,3) and (1,3,0), i.e. they are back-to-back. One of these faces is subsequently removed, leaving a non-manifold triangle. (I'm not sure how this also leads to isolated vertices, but it seems to).

This problem can be avoided by checking for such configurations of edges/faces prior to collapsing the edges. If the configuration is found, the edge is pushed back into the priority queue.

The check for this is:-

* For each of the cells using edge E, the edge to be collapsed:-
  * (Call these cells the "base" cells)
  * Get all of the neighbouring cells
  * Get all of the "far" vertices of these neighbouring cells (i.e. the vertices which are not in common with the "base" cell)
  * If any of the far vertex indices appear in more than one of the neighbouring cells (i.e. cell A's far vertex = cell B's far vertex), edge E must not be collapsed.

Please find attached a quick and dirty patch to perform this check.
TagsNo tags attached.
Relationships
Attached Filespatch vtkQuadricDecimation.patch (11,665) 2009-05-11 12:17
https://www.vtk.org/Bug/file/7230/vtkQuadricDecimation.patch
patch vtkQuadricDecimation.2.patch (5,122) 2009-05-14 10:51
https://www.vtk.org/Bug/file/7245/vtkQuadricDecimation.2.patch
? example_vtkQuadricDecimation_fails_target_reduction_0.85.vtk (27,540) 2009-05-26 12:16
https://www.vtk.org/Bug/file/7271/example_vtkQuadricDecimation_fails_target_reduction_0.85.vtk
Issue History
Date ModifiedUsernameFieldChange
2009-05-11 12:17Andy TurnerNew Issue
2009-05-11 12:17Andy TurnerFile Added: vtkQuadricDecimation.patch
2009-05-11 12:23Andy TurnerNote Added: 0016375
2009-05-14 06:00dbarbierNote Added: 0016422
2009-05-14 06:46Andy TurnerNote Added: 0016423
2009-05-14 06:47Andy TurnerNote Edited: 0016423
2009-05-14 09:51dbarbierNote Added: 0016430
2009-05-14 10:51Andy TurnerFile Added: vtkQuadricDecimation.2.patch
2009-05-14 10:53Andy TurnerNote Added: 0016439
2009-05-26 12:16Bryn LloydFile Added: example_vtkQuadricDecimation_fails_target_reduction_0.85.vtk
2009-05-26 12:22Bryn LloydNote Added: 0016567
2011-06-16 13:11Zack GalbreathCategory => (No Category)
2016-08-12 09:55Kitware RobotNote Added: 0037075
2016-08-12 09:55Kitware RobotStatusexpired => closed
2016-08-12 09:55Kitware RobotResolutionopen => moved
2016-08-12 09:55Kitware RobotAssigned To => Kitware Robot

Notes
(0016375)
Andy Turner   
2009-05-11 12:23   
The same bad geometry problem occurs with vtkDecimatePro.

The suggested patch could perhaps be adapted to make the same checks before collapsing edges in vtkDecimatePro.
(0016422)
dbarbier   
2009-05-14 06:00   
This is discussed in http://www.cs.duke.edu/~edels/Meshes/MeshAssoc.pdf [^]
(0016423)
Andy Turner   
2009-05-14 06:46   
(edited on: 2009-05-14 06:47)
dbarbier, I'm unsure about whether your comment is in support of or against my suggested fix.

Please could you clarify what in particular is discussed in that paper?

* That this issue exists (TTIE) in mesh decimation
* TTIE, and the above fixes all possible problems
* TTIE, and the above fixes only some of the problems
* TTIE, and the above introduces more problems than it fixes!

Thanks in advance.
(0016430)
dbarbier   
2009-05-14 09:51   
Sorry if I was unclear. This issue does exist, but your patch does not fix all possible problems, it will reliably only work for manifold meshes without boundaries. Moreover comments in your patch are misleading, e.g. isPyramid may be true even with 2D planar meshes.
You may add checks to deal with boundary and non-manifold meshes, but it will be hard to know whether all cases are fixed, IMHO it would be better to write a topological check based on this paper to catch all cases.
Of course your patch is still an improvement over the current situation.
(0016439)
Andy Turner   
2009-05-14 10:53   
Uploaded a new version of the patch which only affects parts of the class that were intentionally changed, not others by, e.g. retabbing, inserting extra new lines etc.
(0016567)
Bryn Lloyd   
2009-05-26 12:22   
Uploaded an example where decimation fails (produces non-manifold meshes) for a target reduction of 0.85 or higher.

The patch worked for all examples I could find or create. I created the examples by re-meshing a surface using the contour filter (marching cubes) on an inside/outside image at different resolutions.
(0037075)
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.