[vtkusers] vtk3.2beta available
johnny carroll norris
jnorris at csar.uiuc.edu
Wed Jan 3 15:46:37 EST 2001
Once upon a time, Will Schroeder wrote:
> Hi Folks-
>
> vtk3.2beta is available at ftp://public.kitware.com/pub/vtk/vtk3.2/
>
> We'd appreciate any feedback or suggestions for improvement.
>
> Will
VTK (and 3.2 in particular) is a wonderful package! Thanks a bunch! I have
a contribution I'd like to make.
I'm working on a visualization package for the researchers here at CSAR, and
recently ran into a problem with large datasets. One researcher has an
unstructured grid with 847,361 tetrahedrons and 155,932 points. Rendering
the surface (via vtkGeometryFilter) took over 16 minutes on a Sun Ultra 2
with a Creator graphics card. I browsed the code, searching for a way to
speed this up. I found that vtkGeometryFilter uses the method
GetCellNeighbors() to determine whether a cell face is on the surface or not.
If there are neighbors, the filter checks the first neighbor in the list to
see if it's visible or not. Any other neighbors that may have been returned
are ignored. Since the filter is only interested in the first neighbor
found, I added a new method, GetFirstCellNeighbor(), to vtkUnstructuredGrid.
I then modified vtkGeometryFilter::UnstructuredGridExecute() to use this
method instead of GetCellNeighbors(). After recompiling, rendering the
surface of the afore-mentioned dataset took about 12 minutes.
Unfortunately, I don't know how much time is being spent executing
vtkGeometryFilter (my crude attempts to get timing info failed miserably),
but I didn't change anything else in the visualization pipeline. The
big-O complexity is still the same; I've merely reduced the constant.
I'm attaching a diff of vtkUnstructuredGrid.h, vtkUnstructuredGrid.cxx, and
vtkGeometryFilter.cxx. I believe that the other classes derived from
vtkDataSet could also benefit from a GetFirstCellNeighbor() method, but
since I'm only working with unstructured grids, I haven't really looked into
it. I'd be more than happy to write and test them if there's an interest
in incorporating them into the VTK library.
One more note: the only place GetCellNeighbors() is called outside of
vtkGeometryFilter is in vtkPointSet. Again, only the first neighbor is
used.
Hope someone finds this useful,
John
--
John Norris
Research Programmer
Center for Simulation of Advanced Rockets
http://www.uiuc.edu/ph/www/jnorris
-------------- next part --------------
*** common/vtkUnstructuredGrid.h.orig Wed Jan 3 11:09:55 2001
--- common/vtkUnstructuredGrid.h Wed Jan 3 11:44:29 2001
***************
*** 117,120 ****
--- 117,127 ----
// Description:
+ // Topological inquiry to get first cell using list of points exclusive of
+ // cell specified (e.g., cellId).
+ // THIS METHOD IS THREAD SAFE IF FIRST CALLED FROM A SINGLE THREAD AND
+ // THE DATASET IS NOT MODIFIED
+ virtual int GetFirstCellNeighbor(int cellId, vtkIdList *ptIds);
+
+ // Description:
// For streaming. User/next filter specifies which piece the want updated.
// The source of this poly data has to return exactly this piece.
*** common/vtkUnstructuredGrid.cxx.orig Wed Jan 3 11:10:02 2001
--- common/vtkUnstructuredGrid.cxx Wed Jan 3 11:44:43 2001
***************
*** 764,765 ****
--- 764,833 ----
}//for all candidate cells attached to point
}
+
+ // Determine neighbor as follows. Find the (shortest) list of cells that
+ // uses one of the points in ptIds. For each cell, in the list, see whether
+ // it contains the other points in the ptIds list. If so, it's a neighbor.
+ //
+ int vtkUnstructuredGrid::GetFirstCellNeighbor(int cellId, vtkIdList *ptIds)
+ {
+ int i, j, k;
+ int numPts, minNumCells, *minCells, numCells, *pts;
+ int match, minPtId;
+ int npts, *cellPts;
+
+ if ( ! this->Links )
+ {
+ this->BuildLinks();
+ }
+
+ //Find the point used by the fewest number of cells
+ //
+ numPts = ptIds->GetNumberOfIds();
+ pts = ptIds->GetPointer(0);
+
+ minNumCells = this->Links->GetNcells(pts[0]);
+ minCells = this->Links->GetCells(pts[0]);
+ minPtId = pts[0];
+
+ for (i=1; i<numPts; i++)
+ {
+ numCells = this->Links->GetNcells(pts[i]);
+ if ( numCells < minNumCells )
+ {
+ minNumCells = numCells;
+ minCells = this->Links->GetCells(pts[i]);
+ minPtId = pts[i];
+ }
+ }
+
+ //Now for each cell, see if it contains all the points
+ //in the ptIds list.
+ for (i=0; i<minNumCells; i++)
+ {
+ if ( minCells[i] != cellId ) //don't include current cell
+ {
+ this->GetCellPoints(minCells[i],npts,cellPts);
+ for (match=1, j=0; j<numPts && match; j++) //for all pts in input cell
+ {
+ if ( pts[j] != minPtId ) //of course minPtId is contained by cell
+ {
+ for (match=k=0; k<npts; k++) //for all points in candidate cell
+ {
+ if ( pts[j] == cellPts[k] )
+ {
+ match = 1; //a match was found
+ break;
+ }
+ }//for all points in current cell
+ }//if not guaranteed match
+ }//for all points in input cell
+ if ( match )
+ {
+ return minCells[i];
+ }
+ }//if not the reference cell
+ }//for all candidate cells attached to point
+
+ // there are no neighbors
+ return -1;
+ }
*** graphics/vtkGeometryFilter.cxx.orig Mon Dec 11 14:19:45 2000
--- graphics/vtkGeometryFilter.cxx Wed Jan 3 14:20:17 2001
***************
*** 563,567 ****
vtkCellArray *Connectivity = input->GetCells();
if (Connectivity == NULL) {return;}
! int i, cellId;
int allVisible;
int npts, *pts;
--- 563,567 ----
vtkCellArray *Connectivity = input->GetCells();
if (Connectivity == NULL) {return;}
! int i, cellId, neighborId;
int allVisible;
int npts, *pts;
***************
*** 574,578 ****
vtkCellData *outputCD = output->GetCellData();
vtkCellArray *Verts, *Lines, *Polys, *Strips;
! vtkIdList *cellIds, *faceIds;
char *cellVis;
int newCellId, faceId, *faceVerts, numFacePts;
--- 574,578 ----
vtkCellData *outputCD = output->GetCellData();
vtkCellArray *Verts, *Lines, *Polys, *Strips;
! vtkIdList *faceIds;
char *cellVis;
int newCellId, faceId, *faceVerts, numFacePts;
***************
*** 610,614 ****
// Determine nature of what we have to do
- cellIds = vtkIdList::New();
faceIds = vtkIdList::New();
if ( (!this->CellClipping) && (!this->PointClipping) &&
--- 610,613 ----
***************
*** 730,736 ****
faceIds->InsertNextId(pts[faceVerts[2]]);
numFacePts = 3;
! input->GetCellNeighbors(cellId, faceIds, cellIds);
! if ( cellIds->GetNumberOfIds() <= 0 ||
! (!allVisible && !cellVis[cellIds->GetId(0)]) )
{
newCellId = Polys->InsertNextCell(numFacePts);
--- 729,735 ----
faceIds->InsertNextId(pts[faceVerts[2]]);
numFacePts = 3;
! neighborId = input->GetFirstCellNeighbor(cellId, faceIds);
! if ( neighborId == -1 ||
! (!allVisible && !cellVis[neighborId]) )
{
newCellId = Polys->InsertNextCell(numFacePts);
***************
*** 754,760 ****
faceIds->InsertNextId(pts[faceVerts[3]]);
numFacePts = 4;
! input->GetCellNeighbors(cellId, faceIds, cellIds);
! if ( cellIds->GetNumberOfIds() <= 0 ||
! (!allVisible && !cellVis[cellIds->GetId(0)]) )
{
newCellId = Polys->InsertNextCell(numFacePts);
--- 753,759 ----
faceIds->InsertNextId(pts[faceVerts[3]]);
numFacePts = 4;
! neighborId = input->GetFirstCellNeighbor(cellId, faceIds);
! if ( neighborId == -1 ||
! (!allVisible && !cellVis[neighborId]) )
{
newCellId = Polys->InsertNextCell(numFacePts);
***************
*** 778,784 ****
faceIds->InsertNextId(pts[faceVerts[3]]);
numFacePts = 4;
! input->GetCellNeighbors(cellId, faceIds, cellIds);
! if ( cellIds->GetNumberOfIds() <= 0 ||
! (!allVisible && !cellVis[cellIds->GetId(0)]) )
{
newCellId = Polys->InsertNextCell(numFacePts);
--- 777,783 ----
faceIds->InsertNextId(pts[faceVerts[3]]);
numFacePts = 4;
! neighborId = input->GetFirstCellNeighbor(cellId, faceIds);
! if ( neighborId == -1 ||
! (!allVisible && !cellVis[neighborId]) )
{
newCellId = Polys->InsertNextCell(numFacePts);
***************
*** 806,812 ****
numFacePts = 4;
}
! input->GetCellNeighbors(cellId, faceIds, cellIds);
! if ( cellIds->GetNumberOfIds() <= 0 ||
! (!allVisible && !cellVis[cellIds->GetId(0)]) )
{
newCellId = Polys->InsertNextCell(numFacePts);
--- 805,811 ----
numFacePts = 4;
}
! neighborId = input->GetFirstCellNeighbor(cellId, faceIds);
! if ( neighborId == -1 ||
! (!allVisible && !cellVis[neighborId]) )
{
newCellId = Polys->InsertNextCell(numFacePts);
***************
*** 834,840 ****
numFacePts = 4;
}
! input->GetCellNeighbors(cellId, faceIds, cellIds);
! if ( cellIds->GetNumberOfIds() <= 0 ||
! (!allVisible && !cellVis[cellIds->GetId(0)]) )
{
newCellId = Polys->InsertNextCell(numFacePts);
--- 833,839 ----
numFacePts = 4;
}
! neighborId = input->GetFirstCellNeighbor(cellId, faceIds);
! if ( neighborId == -1 ||
! (!allVisible && !cellVis[neighborId]) )
{
newCellId = Polys->InsertNextCell(numFacePts);
***************
*** 867,871 ****
<< output->GetNumberOfCells() << " cells.");
- cellIds->Delete();
faceIds->Delete();
if ( cellVis )
--- 866,869 ----
More information about the vtkusers
mailing list