Attached Files | vtkQuadricDecimation.patch [^] (11,665 bytes) 2009-05-11 12:17 [Show Content] [Hide Content]Index: vtkQuadricDecimation.cxx
===================================================================
RCS file: /cvsroot/VTK/VTK/Graphics/vtkQuadricDecimation.cxx,v
retrieving revision 1.39.50.1
diff -u -r1.39.50.1 vtkQuadricDecimation.cxx
--- vtkQuadricDecimation.cxx 17 Jul 2008 20:29:18 -0000 1.39.50.1
+++ vtkQuadricDecimation.cxx 11 May 2009 15:42:15 -0000
@@ -12,7 +12,7 @@
PURPOSE. See the above copyright notice for more information.
=========================================================================*/
-// Comments from Brad---
+// Comments from Brad->-
// FIXME: I do not have a very good method for detecting the stability of a
// matrix
@@ -59,7 +59,7 @@
vtkStandardNewMacro(vtkQuadricDecimation);
-//----------------------------------------------------------------------------
+//->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->
vtkQuadricDecimation::vtkQuadricDecimation()
{
this->Edges = vtkEdgeTable::New();
@@ -68,7 +68,7 @@
this->EndPoint2List = vtkIdList::New();
this->ErrorQuadrics = NULL;
this->TargetPoints = vtkDoubleArray::New();
-
+
this->TargetReduction = 0.9;
this->NumberOfEdgeCollapses = 0;
this->NumberOfComponents = 0;
@@ -89,7 +89,7 @@
this->ActualReduction = 0.0;
}
-//----------------------------------------------------------------------------
+//->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->
vtkQuadricDecimation::~vtkQuadricDecimation()
{
this->Edges->Delete();
@@ -170,7 +170,7 @@
}
}
-//----------------------------------------------------------------------------
+//->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->
int vtkQuadricDecimation::RequestData(
vtkInformation *vtkNotUsed(request),
vtkInformationVector **inputVector,
@@ -337,6 +337,18 @@
continue;
}
+ // check for a non-collapsible edges -- AWT
+ if ( !this->IsEdgeCollapsible( endPtIds[0], endPtIds[1] ) )
+ {
+ vtkDebugMacro(<<"Pyramid detected " << edgeId << " " << cost);
+ // return the point to the queue but with the max cost so that
+ // when it is recomputed it will be reconsidered
+ this->EdgeCosts->Insert(VTK_DOUBLE_MAX, edgeId);
+
+ edgeId = this->EdgeCosts->Pop(0, cost);
+ continue;
+ }
+
this->NumberOfEdgeCollapses++;
// Set the new coordinates of point0.
@@ -371,7 +383,7 @@
delete [] this->TempB;
delete [] this->TempA;
delete [] this->TempData;
-
+
// copy the simplified mesh from the working mesh to the output mesh
for (i = 0; i < this->Mesh->GetNumberOfCells(); i++)
{
@@ -406,7 +418,86 @@
return 1;
}
-//----------------------------------------------------------------------------
+int vtkQuadricDecimation::IsEdgeCollapsible( vtkIdType pt0Id, vtkIdType pt1Id )
+{
+ bool isPyramid = false;
+
+ vtkIdType i, j, k, m;
+ vtkIdType npts, *pts;
+
+ vtkIdList* uniqueVertices = vtkIdList::New( );
+ vtkIdList* neighbourCells = vtkIdList::New( );
+
+ // Look for the cells which use this edge
+ this->Mesh->GetPointCells(pt0Id, this->CollapseCellIds);
+ for (i = 0; i < this->CollapseCellIds->GetNumberOfIds(); i++)
+ {
+ const vtkIdType cellId = this->CollapseCellIds->GetId(i);
+ this->Mesh->GetCellPoints(cellId, npts, pts);
+ for (j = 0; j < 3 && !isPyramid; j++)
+ {
+ if (pts[j] == pt1Id)
+ {
+ vtkIdType thisTriangleVerts[] = { pt0Id, pt1Id,
+ GetThirdVertexId( cellId, pt0Id, pt1Id ) };
+
+ uniqueVertices->SetNumberOfIds( 0 );
+ uniqueVertices->Allocate( neighbourCells->GetNumberOfIds( ) );
+
+ for ( k = 0; k < 3; ++k )
+ {
+ this->Mesh->GetCellEdgeNeighbors( cellId, thisTriangleVerts[k], thisTriangleVerts[(k+1)%3], neighbourCells );
+
+ for ( m = 0; m < neighbourCells->GetNumberOfIds( ); ++m )
+ {
+ vtkIdType farVertex = GetThirdVertexId( neighbourCells->GetId( m ), thisTriangleVerts[k], thisTriangleVerts[(k+1)%3] );
+
+ if ( farVertex == VTK_INT_MAX )
+ continue;
+
+ if ( -1 == uniqueVertices->IsId( farVertex ) )
+ {
+ uniqueVertices->InsertNextId( farVertex );
+ }
+ else
+ {
+ isPyramid = true;
+ }
+ }
+ }
+ }
+ }
+ }
+
+ uniqueVertices->Delete( );
+ neighbourCells->Delete( );
+
+ return ( isPyramid ) ? 0 : 1;
+}
+
+int vtkQuadricDecimation::GetThirdVertexId( vtkIdType cellId, vtkIdType pt0Id, vtkIdType pt1Id )
+{
+ // Should only be 3 at most... because there is a check to make
+ // sure only done only done on triangle meshes
+ vtkIdList* pts = vtkIdList::New( );
+
+ this->Mesh->GetCellPoints( cellId, pts );
+
+ for ( int i = 0; i < 3; ++i )
+ {
+ const int id = pts->GetId( i );
+ if ( id != pt0Id && id != pt1Id )
+ {
+ pts->Delete( );
+ return id;
+ }
+ }
+
+ pts->Delete( );
+ return VTK_INT_MAX;
+}
+
+//->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->
void vtkQuadricDecimation::InitializeQuadrics(vtkIdType numPts)
{
vtkPolyData *input = this->Mesh;
@@ -651,7 +742,7 @@
delete [] QEM;
}
-//----------------------------------------------------------------------------
+//->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->
void vtkQuadricDecimation::AddQuadric(vtkIdType oldPtId, vtkIdType newPtId)
{
int i;
@@ -663,7 +754,7 @@
}
}
-//----------------------------------------------------------------------------
+//->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->
void vtkQuadricDecimation::FindAffectedEdges(vtkIdType p1Id, vtkIdType p2Id,
vtkIdList *edges)
{
@@ -788,7 +879,7 @@
return;
}
-//----------------------------------------------------------------------------
+//->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->
double vtkQuadricDecimation::ComputeCost(vtkIdType edgeId, double *x)
{
static const double errorNumber = 1e-10;
@@ -887,7 +978,7 @@
}
-//----------------------------------------------------------------------------
+//->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->
double vtkQuadricDecimation::ComputeCost2(vtkIdType edgeId, double *x)
{
// this function is so ugly because the functionality of converting an QEM
@@ -1086,53 +1177,52 @@
return cost;
}
-
int vtkQuadricDecimation::CollapseEdge(vtkIdType pt0Id, vtkIdType pt1Id)
{
- int j, numDeleted=0;
- vtkIdType i, npts, *pts, cellId;
+ int j, numDeleted=0;
+ vtkIdType i, npts, *pts, cellId;
- this->Mesh->GetPointCells(pt0Id, this->CollapseCellIds);
- for (i = 0; i < this->CollapseCellIds->GetNumberOfIds(); i++)
- {
- cellId = this->CollapseCellIds->GetId(i);
- this->Mesh->GetCellPoints(cellId, npts, pts);
- for (j = 0; j < 3; j++)
- {
- if (pts[j] == pt1Id)
- {
- this->Mesh->RemoveCellReference(cellId);
- this->Mesh->DeleteCell(cellId);
- numDeleted++;
- }
- }
- }
-
- this->Mesh->GetPointCells(pt1Id, this->CollapseCellIds);
- this->Mesh->ResizeCellList(pt0Id, this->CollapseCellIds->GetNumberOfIds());
- for (i=0; i < this->CollapseCellIds->GetNumberOfIds(); i++)
- {
- cellId = this->CollapseCellIds->GetId(i);
- this->Mesh->GetCellPoints(cellId, npts, pts);
- // making sure we don't already have the triangle we're about to
- // change this one to
- if ((pts[0] == pt1Id && this->Mesh->IsTriangle(pt0Id, pts[1], pts[2])) ||
- (pts[1] == pt1Id && this->Mesh->IsTriangle(pts[0], pt0Id, pts[2])) ||
- (pts[2] == pt1Id && this->Mesh->IsTriangle(pts[0], pts[1], pt0Id)))
- {
- this->Mesh->RemoveCellReference(cellId);
- this->Mesh->DeleteCell(cellId);
- numDeleted++;
+ this->Mesh->GetPointCells(pt0Id, this->CollapseCellIds);
+ for (i = 0; i < this->CollapseCellIds->GetNumberOfIds(); i++)
+ {
+ cellId = this->CollapseCellIds->GetId(i);
+ this->Mesh->GetCellPoints(cellId, npts, pts);
+ for (j = 0; j < 3; j++)
+ {
+ if (pts[j] == pt1Id)
+ {
+ this->Mesh->RemoveCellReference(cellId);
+ this->Mesh->DeleteCell(cellId);
+ numDeleted++;
+ }
+ }
+ }
+
+ this->Mesh->GetPointCells(pt1Id, this->CollapseCellIds);
+ this->Mesh->ResizeCellList(pt0Id, this->CollapseCellIds->GetNumberOfIds());
+ for (i=0; i < this->CollapseCellIds->GetNumberOfIds(); i++)
+ {
+ cellId = this->CollapseCellIds->GetId(i);
+ this->Mesh->GetCellPoints(cellId, npts, pts);
+ // making sure we don't already have the triangle we're about to
+ // change this one to
+ if ((pts[0] == pt1Id && this->Mesh->IsTriangle(pt0Id, pts[1], pts[2])) ||
+ (pts[1] == pt1Id && this->Mesh->IsTriangle(pts[0], pt0Id, pts[2])) ||
+ (pts[2] == pt1Id && this->Mesh->IsTriangle(pts[0], pts[1], pt0Id)))
+ {
+ this->Mesh->RemoveCellReference(cellId);
+ this->Mesh->DeleteCell(cellId);
+ numDeleted++;
}
- else
+ else
{
- this->Mesh->AddReferenceToCell(pt0Id, cellId);
- this->Mesh->ReplaceCellPoint(cellId, pt1Id, pt0Id);
+ this->Mesh->AddReferenceToCell(pt0Id, cellId);
+ this->Mesh->ReplaceCellPoint(cellId, pt1Id, pt0Id);
}
- }
- this->Mesh->DeletePoint(pt1Id);
-
- return numDeleted;
+ }
+ this->Mesh->DeletePoint(pt1Id);
+
+ return numDeleted;
}
@@ -1293,7 +1383,7 @@
}
this->AttributeComponents[1] = this->NumberOfComponents;
- // Normals attributes -- normals are assumed normalized
+ // Normals attributes -> normals are assumed normalized
if (pd->GetNormals() != NULL && this->NormalsAttribute)
{
this->NumberOfComponents += 3;
@@ -1348,7 +1438,7 @@
vtkDebugMacro("Number of components: " << this->NumberOfComponents);
}
-//----------------------------------------------------------------------------
+//->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->->
void vtkQuadricDecimation::PrintSelf(ostream& os, vtkIndent indent)
{
this->Superclass::PrintSelf(os,indent);
Index: vtkQuadricDecimation.h
===================================================================
RCS file: /cvsroot/VTK/VTK/Graphics/vtkQuadricDecimation.h,v
retrieving revision 1.22
diff -u -r1.22 vtkQuadricDecimation.h
--- vtkQuadricDecimation.h 29 Nov 2004 18:41:29 -0000 1.22
+++ vtkQuadricDecimation.h 11 May 2009 15:42:01 -0000
@@ -169,6 +169,9 @@
vtkIdType GetEdgeCellId(vtkIdType p1Id, vtkIdType p2Id);
int IsGoodPlacement(vtkIdType pt0Id, vtkIdType pt1Id, const double *x);
+ int IsEdgeCollapsible( vtkIdType pt0Id, vtkIdType pt1Id );
+ int GetThirdVertexId( vtkIdType cellId, vtkIdType pt0Id, vtkIdType pt1Id );
+
int TrianglePlaneCheck(const double t0[3], const double t1[3],
const double t2[3], const double *x);
void ComputeNumberOfComponents(void);
vtkQuadricDecimation.2.patch [^] (5,122 bytes) 2009-05-14 10:51 [Show Content] [Hide Content]Index: vtkQuadricDecimation.cxx
===================================================================
RCS file: /cvsroot/VTK/VTK/Graphics/vtkQuadricDecimation.cxx,v
retrieving revision 1.39.50.1
diff -u -r1.39.50.1 vtkQuadricDecimation.cxx
--- vtkQuadricDecimation.cxx 17 Jul 2008 20:29:18 -0000 1.39.50.1
+++ vtkQuadricDecimation.cxx 12 May 2009 10:54:30 -0000
@@ -337,6 +337,18 @@
continue;
}
+ // check for a non-collapsible edges -- AWT
+ if ( !this->IsEdgeCollapsible( endPtIds[0], endPtIds[1] ) )
+ {
+ vtkDebugMacro(<<"Non-collapsible edge detected " << edgeId << " " << cost);
+ // return the point to the queue but with the max cost so that
+ // when it is recomputed it will be reconsidered
+ this->EdgeCosts->Insert(VTK_DOUBLE_MAX, edgeId);
+
+ edgeId = this->EdgeCosts->Pop(0, cost);
+ continue;
+ }
+
this->NumberOfEdgeCollapses++;
// Set the new coordinates of point0.
@@ -407,6 +419,96 @@
}
//----------------------------------------------------------------------------
+int vtkQuadricDecimation::IsEdgeCollapsible( vtkIdType pt0Id, vtkIdType pt1Id )
+{
+ bool isCollapsible = true;
+
+ vtkIdType i, j, k, m, vv;
+ vtkIdType npts, *pts;
+
+ vtkIdList* uniqueVertices = vtkIdList::New( );
+ vtkIdList* neighbourCells = vtkIdList::New( );
+ vtkIdList* thirdVertexList = vtkIdList::New( );
+
+ // Look for the cells which use this edge
+ this->Mesh->GetPointCells(pt0Id, this->CollapseCellIds);
+ for (i = 0; i < this->CollapseCellIds->GetNumberOfIds() && isCollapsible; i++)
+ {
+ const vtkIdType cellId = this->CollapseCellIds->GetId(i);
+ this->Mesh->GetCellPoints(cellId, npts, pts);
+ for (j = 0; j < 3 && isCollapsible; j++)
+ {
+ if (pts[j] == pt1Id)
+ {
+ // Cell cellId uses this edge. Now to look and see how many
+ // unique vertices are used by its neighbours
+
+ vtkIdType thisTriangleVerts[] = { pt0Id, pt1Id, VTK_INT_MAX };
+
+ // Work out which is the vertex of cell cellId not in the edge
+ this->Mesh->GetCellPoints( cellId, thirdVertexList );
+ for ( vv = 0; vv < 3; ++vv )
+ {
+ thisTriangleVerts[2] = thirdVertexList->GetId( vv );
+
+ if ( thisTriangleVerts[2] != thisTriangleVerts[0] && thisTriangleVerts[2] != thisTriangleVerts[0] )
+ break;
+ }
+
+ // Don't know why this should happen, but it shows there's
+ // something weird afoot
+ if ( vv == 3 )
+ continue;
+
+ // Going to build a list of vertices used
+ uniqueVertices->SetNumberOfIds( 0 );
+ uniqueVertices->Allocate( neighbourCells->GetNumberOfIds( ) );
+
+ for ( k = 0; k < 3 && isCollapsible; ++k )
+ {
+ this->Mesh->GetCellEdgeNeighbors( cellId, thisTriangleVerts[k], thisTriangleVerts[(k+1)%3], neighbourCells );
+
+ for ( m = 0; m < neighbourCells->GetNumberOfIds( ) && isCollapsible; ++m )
+ {
+ // Look for the vertex which isn't on the shared edge
+ vtkIdType farVertex = VTK_INT_MAX;
+
+ this->Mesh->GetCellPoints( cellId, thirdVertexList );
+ for ( vv = 0; vv < 3; ++vv )
+ {
+ farVertex = thirdVertexList->GetId( vv );
+
+ if ( farVertex != thisTriangleVerts[k] && farVertex != thisTriangleVerts[(k+1)%3] )
+ break;
+ }
+
+ if ( vv == 3 )
+ continue;
+
+ if ( -1 == uniqueVertices->IsId( farVertex ) )
+ {
+ uniqueVertices->InsertNextId( farVertex );
+ }
+ else
+ {
+ // We've seen this vertex before - this means we've found a
+ // non-collapsible combination
+ isCollapsible = false;
+ }
+ }
+ }
+ }
+ }
+ }
+
+ thirdVertexList->Delete( );
+ uniqueVertices->Delete( );
+ neighbourCells->Delete( );
+
+ return ( isCollapsible ) ? 1 : 0;
+}
+
+//----------------------------------------------------------------------------
void vtkQuadricDecimation::InitializeQuadrics(vtkIdType numPts)
{
vtkPolyData *input = this->Mesh;
Index: vtkQuadricDecimation.h
===================================================================
RCS file: /cvsroot/VTK/VTK/Graphics/vtkQuadricDecimation.h,v
retrieving revision 1.22
diff -u -r1.22 vtkQuadricDecimation.h
--- vtkQuadricDecimation.h 29 Nov 2004 18:41:29 -0000 1.22
+++ vtkQuadricDecimation.h 12 May 2009 09:58:02 -0000
@@ -169,6 +169,8 @@
vtkIdType GetEdgeCellId(vtkIdType p1Id, vtkIdType p2Id);
int IsGoodPlacement(vtkIdType pt0Id, vtkIdType pt1Id, const double *x);
+ int IsEdgeCollapsible( vtkIdType pt0Id, vtkIdType pt1Id );
+
int TrianglePlaneCheck(const double t0[3], const double t1[3],
const double t2[3], const double *x);
void ComputeNumberOfComponents(void);
example_vtkQuadricDecimation_fails_target_reduction_0.85.vtk [^] (27,540 bytes) 2009-05-26 12:16 |