View Issue Details Jump to Notes ] Print ]
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 
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.
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.
Project
Type
Attached Filespatch file icon vtkQuadricDecimation.patch [^] (11,665 bytes) 2009-05-11 12:17 [Show Content]
patch file icon vtkQuadricDecimation.2.patch [^] (5,122 bytes) 2009-05-14 10:51 [Show Content]
? file icon example_vtkQuadricDecimation_fails_target_reduction_0.85.vtk [^] (27,540 bytes) 2009-05-26 12:16

 Relationships

  Notes
(0016375)
Andy Turner (reporter)
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 (reporter)
2009-05-14 06:00

This is discussed in http://www.cs.duke.edu/~edels/Meshes/MeshAssoc.pdf [^]
(0016423)
Andy Turner (reporter)
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 (reporter)
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 (reporter)
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 (reporter)
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 (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
2009-05-11 12:17 Andy Turner New Issue
2009-05-11 12:17 Andy Turner File Added: vtkQuadricDecimation.patch
2009-05-11 12:23 Andy Turner Note Added: 0016375
2009-05-14 06:00 dbarbier Note Added: 0016422
2009-05-14 06:46 Andy Turner Note Added: 0016423
2009-05-14 06:47 Andy Turner Note Edited: 0016423
2009-05-14 09:51 dbarbier Note Added: 0016430
2009-05-14 10:51 Andy Turner File Added: vtkQuadricDecimation.2.patch
2009-05-14 10:53 Andy Turner Note Added: 0016439
2009-05-26 12:16 Bryn Lloyd File Added: example_vtkQuadricDecimation_fails_target_reduction_0.85.vtk
2009-05-26 12:22 Bryn Lloyd Note Added: 0016567
2011-06-16 13:11 Zack Galbreath Category => (No Category)
2016-08-12 09:55 Kitware Robot Note Added: 0037075
2016-08-12 09:55 Kitware Robot Status expired => closed
2016-08-12 09:55 Kitware Robot Resolution open => moved
2016-08-12 09:55 Kitware Robot Assigned To => Kitware Robot


Copyright © 2000 - 2018 MantisBT Team