vtkConnectivityFilter.cxx 23.4 KB
Newer Older
Will Schroeder's avatar
Will Schroeder committed
1
2
/*=========================================================================

Ken Martin's avatar
Ken Martin committed
3
  Program:   Visualization Toolkit
Ken Martin's avatar
Ken Martin committed
4
  Module:    vtkConnectivityFilter.cxx
Will Schroeder's avatar
Will Schroeder committed
5

6
  Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
7
8
  All rights reserved.
  See Copyright.txt or http://www.kitware.com/Copyright.htm for details.
Ken Martin's avatar
Ken Martin committed
9

10
11
     This software is distributed WITHOUT ANY WARRANTY; without even
     the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
12
     PURPOSE.  See the above copyright notice for more information.
Will Schroeder's avatar
Will Schroeder committed
13
14

=========================================================================*/
Ken Martin's avatar
Ken Martin committed
15
#include "vtkConnectivityFilter.h"
16

17
18
#include "vtkCell.h"
#include "vtkCellData.h"
19
#include "vtkDataSet.h"
20
#include "vtkDemandDrivenPipeline.h"
21
22
#include "vtkFloatArray.h"
#include "vtkIdList.h"
23
24
#include "vtkInformation.h"
#include "vtkInformationVector.h"
25
#include "vtkMath.h"
26
#include "vtkObjectFactory.h"
27
28
#include "vtkPointData.h"
#include "vtkPointData.h"
29
#include "vtkPoints.h"
30
#include "vtkPolyData.h"
31
#include "vtkUnstructuredGrid.h"
32
#include "vtkIdTypeArray.h"
33

Cory Quammen's avatar
Cory Quammen committed
34
35
#include <map>

36
vtkObjectFactoryNewMacro(vtkConnectivityFilter);
37

Will Schroeder's avatar
Will Schroeder committed
38
// Construct with default extraction mode to extract largest regions.
Ken Martin's avatar
Ken Martin committed
39
vtkConnectivityFilter::vtkConnectivityFilter()
Will Schroeder's avatar
Will Schroeder committed
40
{
41
  this->RegionSizes = vtkIdTypeArray::New();
Will Schroeder's avatar
Will Schroeder committed
42
  this->ExtractionMode = VTK_EXTRACT_LARGEST_REGION;
Will Schroeder's avatar
Will Schroeder committed
43
  this->ColorRegions = 0;
Cory Quammen's avatar
Cory Quammen committed
44
  this->RegionIdAssignmentMode = UNSPECIFIED;
45
46
47
48

  this->ScalarConnectivity = 0;
  this->ScalarRange[0] = 0.0;
  this->ScalarRange[1] = 1.0;
Will Schroeder's avatar
Will Schroeder committed
49

50
51
  this->ClosestPoint[0] = this->ClosestPoint[1] = this->ClosestPoint[2] = 0.0;

52
  this->CellScalars = vtkFloatArray::New();
Will Schroeder's avatar
Will Schroeder committed
53
54
55
56
  this->CellScalars->Allocate(8);

  this->NeighborCellPointIds = vtkIdList::New();
  this->NeighborCellPointIds->Allocate(8);
57

58
59
  this->Seeds = vtkIdList::New();
  this->SpecifiedRegionIds = vtkIdList::New();
60

61
62
  this->NewScalars = nullptr;
  this->NewCellScalars = nullptr;
63
64

  this->OutputPointsPrecision = vtkAlgorithm::DEFAULT_PRECISION;
Will Schroeder's avatar
Will Schroeder committed
65
66
}

Charles Law's avatar
Charles Law committed
67
68
69
vtkConnectivityFilter::~vtkConnectivityFilter()
{
  this->RegionSizes->Delete();
Will Schroeder's avatar
Will Schroeder committed
70
71
  this->CellScalars->Delete();
  this->NeighborCellPointIds->Delete();
72
73
  this->Seeds->Delete();
  this->SpecifiedRegionIds->Delete();
Charles Law's avatar
Charles Law committed
74
75
}

76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
int vtkConnectivityFilter::RequestDataObject(vtkInformation* vtkNotUsed(request),
  vtkInformationVector** inputVector, vtkInformationVector* outputVector)
{
  vtkInformation* inInfo = inputVector[0]->GetInformationObject(0);
  if (!inInfo)
  {
      return 0;
  }

  vtkDataObject* input = inInfo->Get(vtkDataObject::DATA_OBJECT());
  if (input)
  {
    // for each output
    for (int i = 0; i < this->GetNumberOfOutputPorts(); ++i)
    {
      vtkInformation* info = outputVector->GetInformationObject(i);
      vtkDataObject* output = info->Get(vtkDataObject::DATA_OBJECT());

      if (!output || !output->IsA(input->GetClassName()))
      {
        vtkDataObject* newOutput = nullptr;
        if (input->IsA("vtkPolyData"))
        {
          newOutput = input->NewInstance();
        }
        else
        {
          newOutput = vtkUnstructuredGrid::New();
        }

        info->Set(vtkDataObject::DATA_OBJECT(), newOutput);
        newOutput->Delete();
        this->GetOutputPortInformation(0)->Set(
          vtkDataObject::DATA_EXTENT_TYPE(), newOutput->GetExtentType());
      }
    }
    return 1;
  }

  return 0;
}

118
119
120
121
int vtkConnectivityFilter::RequestData(
  vtkInformation *vtkNotUsed(request),
  vtkInformationVector **inputVector,
  vtkInformationVector *outputVector)
Will Schroeder's avatar
Will Schroeder committed
122
{
123
124
125
126
  // get the info objects
  vtkInformation *inInfo = inputVector[0]->GetInformationObject(0);
  vtkInformation *outInfo = outputVector->GetInformationObject(0);

127
  // get the input and output
128
129
  vtkDataSet *input = vtkDataSet::SafeDownCast(
    inInfo->Get(vtkDataObject::DATA_OBJECT()));
130
  vtkPointSet *output = vtkPointSet::SafeDownCast(
131
132
    outInfo->Get(vtkDataObject::DATA_OBJECT()));

133
134
135
  vtkPolyData* pdOutput = vtkPolyData::SafeDownCast(output);
  vtkUnstructuredGrid* ugOutput = vtkUnstructuredGrid::SafeDownCast(output);

136
  vtkIdType numPts, numCells, cellId, i, j, pt;
137
  vtkPoints *newPts;
138
139
140
  vtkIdType id;
  vtkIdType maxCellsInRegion;
  vtkIdType largestRegionId = 0;
141
142
  vtkPointData *pd=input->GetPointData(), *outputPD=output->GetPointData();
  vtkCellData *cd=input->GetCellData(), *outputCD=output->GetCellData();
143

Ken Martin's avatar
Ken Martin committed
144
  vtkDebugMacro(<<"Executing connectivity filter.");
145

Ken Martin's avatar
Ken Martin committed
146
147
  //  Check input/allocate storage
  //
148
149
  numCells=input->GetNumberOfCells();
  if ( (numPts=input->GetNumberOfPoints()) < 1 || numCells < 1 )
150
  {
Ken Martin's avatar
Ken Martin committed
151
    vtkDebugMacro(<<"No data to connect!");
152
    return 1;
153
  }
154
155
156
157
158
159
160
161
162

  if (pdOutput)
  {
    pdOutput->Allocate(numCells, numCells);
  }
  if (ugOutput)
  {
    ugOutput->Allocate(numCells, numCells);
  }
163

164
165
  // See whether to consider scalar connectivity
  //
166
  this->InScalars = input->GetPointData()->GetScalars();
167
  if ( !this->ScalarConnectivity )
168
  {
169
    this->InScalars = nullptr;
170
  }
171
  else
172
  {
173
    if ( this->ScalarRange[1] < this->ScalarRange[0] )
174
    {
175
176
      this->ScalarRange[1] = this->ScalarRange[0];
    }
177
  }
178

Ken Martin's avatar
Ken Martin committed
179
180
  // Initialize.  Keep track of points and cells visited.
  //
Charles Law's avatar
Charles Law committed
181
  this->RegionSizes->Reset();
Amy Squillacote's avatar
Amy Squillacote committed
182
  this->Visited = new vtkIdType[numCells];
Jim Miller's avatar
Style    
Jim Miller committed
183
  for ( i=0; i < numCells; i++ )
184
  {
185
    this->Visited[i] = -1;
186
  }
187
  this->PointMap = new vtkIdType[numPts];
Jim Miller's avatar
Style    
Jim Miller committed
188
  for ( i=0; i < numPts; i++ )
189
  {
190
    this->PointMap[i] = -1;
191
  }
Will Schroeder's avatar
Will Schroeder committed
192

193
  this->NewScalars = vtkIdTypeArray::New();
194
  this->NewScalars->SetName("RegionId");
195
  this->NewScalars->SetNumberOfTuples(numPts);
196
197
198
199
200

  this->NewCellScalars = vtkIdTypeArray::New();
  this->NewCellScalars->SetName("RegionId");
  this->NewCellScalars->SetNumberOfTuples(numCells);

201
  newPts = vtkPoints::New();
202
203
204

  // Set the desired precision for the points in the output.
  if(this->OutputPointsPrecision == vtkAlgorithm::DEFAULT_PRECISION)
205
  {
206
207
    vtkPointSet *inputPointSet = vtkPointSet::SafeDownCast(input);
    if(inputPointSet)
208
    {
209
      newPts->SetDataType(inputPointSet->GetPoints()->GetDataType());
210
    }
211
    else
212
    {
213
      newPts->SetDataType(VTK_FLOAT);
214
    }
215
  }
216
  else if(this->OutputPointsPrecision == vtkAlgorithm::SINGLE_PRECISION)
217
  {
218
    newPts->SetDataType(VTK_FLOAT);
219
  }
220
  else if(this->OutputPointsPrecision == vtkAlgorithm::DOUBLE_PRECISION)
221
  {
222
    newPts->SetDataType(VTK_DOUBLE);
223
  }
224

Will Schroeder's avatar
Will Schroeder committed
225
  newPts->Allocate(numPts);
226

Ken Martin's avatar
Ken Martin committed
227
  // Traverse all cells marking those visited.  Each new search
228
  // starts a new connected region. Connected region grows
229
  // using a connected wave propagation.
Ken Martin's avatar
Ken Martin committed
230
  //
231
232
233
234
  this->Wave = vtkIdList::New();
  this->Wave->Allocate(numPts/4+1,numPts);
  this->Wave2 = vtkIdList::New();
  this->Wave2->Allocate(numPts/4+1,numPts);
Will Schroeder's avatar
Will Schroeder committed
235

236
237
  this->PointNumber = 0;
  this->RegionNumber = 0;
Will Schroeder's avatar
Will Schroeder committed
238
  maxCellsInRegion = 0;
Will Schroeder's avatar
Will Schroeder committed
239

240
  this->CellIds = vtkIdList::New();
241
  this->CellIds->Allocate(8, VTK_CELL_SIZE);
242
  this->PointIds = vtkIdList::New();
243
  this->PointIds->Allocate(8, VTK_CELL_SIZE);
244

245
  if ( this->ExtractionMode != VTK_EXTRACT_POINT_SEEDED_REGIONS &&
246
  this->ExtractionMode != VTK_EXTRACT_CELL_SEEDED_REGIONS &&
247
  this->ExtractionMode != VTK_EXTRACT_CLOSEST_POINT_REGION )
248
  { //visit all cells marking with region number
Will Schroeder's avatar
Will Schroeder committed
249
    for (cellId=0; cellId < numCells; cellId++)
250
    {
251
      if ( cellId && !(cellId % 5000) )
252
      {
253
        this->UpdateProgress (0.1 + 0.8*cellId/numCells);
254
      }
255

256
      if ( this->Visited[cellId] < 0 )
257
      {
258
        this->NumCellsInRegion = 0;
259
        this->Wave->InsertNextId(cellId);
260
        this->TraverseAndMark (input);
Will Schroeder's avatar
Will Schroeder committed
261

262
        if ( this->NumCellsInRegion > maxCellsInRegion )
263
        {
264
265
          maxCellsInRegion = this->NumCellsInRegion;
          largestRegionId = this->RegionNumber;
266
        }
Will Schroeder's avatar
Will Schroeder committed
267

268
269
270
271
        this->RegionSizes->InsertValue(this->RegionNumber++,
                                       this->NumCellsInRegion);
        this->Wave->Reset();
        this->Wave2->Reset();
Will Schroeder's avatar
Will Schroeder committed
272
273
      }
    }
274
  }
Will Schroeder's avatar
Will Schroeder committed
275
  else // regions have been seeded, everything considered in same region
276
  {
277
    this->NumCellsInRegion = 0;
Will Schroeder's avatar
Will Schroeder committed
278

Will Schroeder's avatar
Will Schroeder committed
279
    if ( this->ExtractionMode == VTK_EXTRACT_POINT_SEEDED_REGIONS )
280
    {
281
      for (i=0; i < this->Seeds->GetNumberOfIds(); i++)
282
      {
283
        pt = this->Seeds->GetId(i);
284
        if ( pt >= 0 )
285
        {
286
          input->GetPointCells(pt,this->CellIds);
287
          for (j=0; j < this->CellIds->GetNumberOfIds(); j++)
288
          {
289
            this->Wave->InsertNextId(this->CellIds->GetId(j));
Will Schroeder's avatar
Will Schroeder committed
290
291
292
          }
        }
      }
293
    }
Will Schroeder's avatar
Will Schroeder committed
294
    else if ( this->ExtractionMode == VTK_EXTRACT_CELL_SEEDED_REGIONS )
295
    {
296
      for (i=0; i < this->Seeds->GetNumberOfIds(); i++)
297
      {
298
        cellId = this->Seeds->GetId(i);
Jim Miller's avatar
Style    
Jim Miller committed
299
        if ( cellId >= 0 )
300
        {
301
          this->Wave->InsertNextId(cellId);
Will Schroeder's avatar
Will Schroeder committed
302
303
        }
      }
304
    }
305
    else if ( this->ExtractionMode == VTK_EXTRACT_CLOSEST_POINT_REGION )
306
    {//loop over points, find closest one
Ken Martin's avatar
Ken Martin committed
307
      double minDist2, dist2, x[3];
Amy Squillacote's avatar
Amy Squillacote committed
308
      vtkIdType minId = 0;
Ken Martin's avatar
Ken Martin committed
309
      for (minDist2=VTK_DOUBLE_MAX, i=0; i<numPts; i++)
310
      {
311
312
313
        input->GetPoint(i,x);
        dist2 = vtkMath::Distance2BetweenPoints(x,this->ClosestPoint);
        if ( dist2 < minDist2 )
314
        {
315
          minId = i;
316
          minDist2 = dist2;
317
        }
318
      }
319
      input->GetPointCells(minId,this->CellIds);
320
      for (j=0; j < this->CellIds->GetNumberOfIds(); j++)
321
      {
322
        this->Wave->InsertNextId(this->CellIds->GetId(j));
323
      }
324
    }
325
    this->UpdateProgress (0.5);
Will Schroeder's avatar
Will Schroeder committed
326
327

    //mark all seeded regions
328
    this->TraverseAndMark (input);
329
    this->RegionSizes->InsertValue(this->RegionNumber,this->NumCellsInRegion);
330
    this->UpdateProgress (0.9);
331
  }
Will Schroeder's avatar
Will Schroeder committed
332

333
  vtkDebugMacro (<<"Extracted " << this->RegionNumber << " region(s)");
334
335
  this->Wave->Delete();
  this->Wave2->Delete();
Will Schroeder's avatar
Will Schroeder committed
336

337
338
339
  // Now that points and cells have been marked, traverse these lists pulling
  // everything that has been visited.
  //
Will Schroeder's avatar
Will Schroeder committed
340
  //Pass through point data that has been visited
Ken Martin's avatar
Ken Martin committed
341
  outputPD->CopyAllocate(pd);
342
  outputCD->CopyAllocate(cd);
Will Schroeder's avatar
Will Schroeder committed
343
344

  for (i=0; i < numPts; i++)
345
  {
346
    if ( this->PointMap[i] > -1 )
347
    {
348
349
      newPts->InsertPoint(this->PointMap[i],input->GetPoint(i));
      outputPD->CopyData(pd,i,this->PointMap[i]);
Will Schroeder's avatar
Will Schroeder committed
350
    }
351
  }
Will Schroeder's avatar
Will Schroeder committed
352
353

  // if coloring regions; send down new scalar data
Jim Miller's avatar
Style    
Jim Miller committed
354
  if ( this->ColorRegions )
355
  {
Cory Quammen's avatar
Cory Quammen committed
356
357
    this->OrderRegionIds(this->NewScalars, this->NewCellScalars);

358
359
    int idx = outputPD->AddArray(this->NewScalars);
    outputPD->SetActiveAttribute(idx, vtkDataSetAttributes::SCALARS);
360
361
    idx = outputCD->AddArray(this->NewCellScalars);
    outputCD->SetActiveAttribute(idx, vtkDataSetAttributes::SCALARS);
362
  }
363
  this->NewScalars->Delete();
364
  this->NewCellScalars->Delete();
Will Schroeder's avatar
Will Schroeder committed
365

Ken Martin's avatar
Ken Martin committed
366
  output->SetPoints(newPts);
Will Schroeder's avatar
Will Schroeder committed
367
  newPts->Delete();
368
369
370

  // Create output cells
  //
Will Schroeder's avatar
Will Schroeder committed
371
  if ( this->ExtractionMode == VTK_EXTRACT_POINT_SEEDED_REGIONS ||
372
  this->ExtractionMode == VTK_EXTRACT_CELL_SEEDED_REGIONS ||
373
  this->ExtractionMode == VTK_EXTRACT_CLOSEST_POINT_REGION ||
374
  this->ExtractionMode == VTK_EXTRACT_ALL_REGIONS)
375
  { // extract any cell that's been visited
Will Schroeder's avatar
Will Schroeder committed
376
    for (cellId=0; cellId < numCells; cellId++)
377
    {
378
      if ( this->Visited[cellId] >= 0 )
379
      {
380
381
382
        // special handling for polyhedron cells
        if (vtkUnstructuredGrid::SafeDownCast(input) &&
            input->GetCellType(cellId) == VTK_POLYHEDRON)
383
        {
384
385
          vtkUnstructuredGrid::SafeDownCast(input)->
            GetFaceStream(cellId, this->PointIds);
386
          vtkUnstructuredGrid::ConvertFaceStreamPointIds(this->PointIds,
387
                                                         this->PointMap);
388
        }
389
        else
390
        {
391
392
          input->GetCellPoints(cellId, this->PointIds);
          for (i=0; i < this->PointIds->GetNumberOfIds(); i++)
393
          {
394
395
            id = this->PointMap[this->PointIds->GetId(i)];
            this->PointIds->InsertId(i,id);
Will Schroeder's avatar
Will Schroeder committed
396
          }
397
        }
398
        vtkIdType newCellId = -1;
399
400
401
402
403
404
405
406
407
408
        if (pdOutput)
        {
          newCellId = pdOutput->InsertNextCell(input->GetCellType(cellId),
                                               this->PointIds);
        }
        else if (ugOutput)
        {
          newCellId = ugOutput->InsertNextCell(input->GetCellType(cellId),
                                               this->PointIds);
        }
409
410
411
412
        if (newCellId >= 0)
        {
          outputCD->CopyData(cd, cellId, newCellId);
        }
Will Schroeder's avatar
Will Schroeder committed
413
414
      }
    }
415
  }
Will Schroeder's avatar
Will Schroeder committed
416
  else if ( this->ExtractionMode == VTK_EXTRACT_SPECIFIED_REGIONS )
417
  {
Will Schroeder's avatar
Will Schroeder committed
418
    for (cellId=0; cellId < numCells; cellId++)
419
    {
Will Schroeder's avatar
Will Schroeder committed
420
      int inReg, regionId;
421
      if ( (regionId=this->Visited[cellId]) >= 0 )
422
      {
423
        for (inReg=0,i=0; i<this->SpecifiedRegionIds->GetNumberOfIds(); i++)
424
        {
425
          if ( regionId == this->SpecifiedRegionIds->GetId(i) )
426
          {
Will Schroeder's avatar
Will Schroeder committed
427
428
429
            inReg = 1;
            break;
          }
430
        }
Will Schroeder's avatar
Will Schroeder committed
431
        if ( inReg )
432
        {
433
434
435
          // special handling for polyhedron cells
          if (vtkUnstructuredGrid::SafeDownCast(input) &&
              input->GetCellType(cellId) == VTK_POLYHEDRON)
436
          {
437
438
            vtkUnstructuredGrid::SafeDownCast(input)->
              GetFaceStream(cellId, this->PointIds);
439
            vtkUnstructuredGrid::ConvertFaceStreamPointIds(this->PointIds,
440
                                                           this->PointMap);
441
          }
442
          else
443
          {
444
445
            input->GetCellPoints(cellId, this->PointIds);
            for (i=0; i < this->PointIds->GetNumberOfIds(); i++)
446
            {
447
448
              id = this->PointMap[this->PointIds->GetId(i)];
              this->PointIds->InsertId(i,id);
Will Schroeder's avatar
Will Schroeder committed
449
            }
450
          }
451
          vtkIdType newCellId = -1;
452
453
454
455
456
457
458
459
460
461
          if (pdOutput)
          {
            newCellId = pdOutput->InsertNextCell(input->GetCellType(cellId),
                                                 this->PointIds);
          }
          else if (ugOutput)
          {
            newCellId = ugOutput->InsertNextCell(input->GetCellType(cellId),
                                                 this->PointIds);
          }
462
463
464
465
          if (newCellId >= 0)
          {
            outputCD->CopyData(cd, cellId, newCellId);
          }
Will Schroeder's avatar
Will Schroeder committed
466
467
468
        }
      }
    }
469
  }
Will Schroeder's avatar
Will Schroeder committed
470
  else //extract largest region
471
  {
Will Schroeder's avatar
Will Schroeder committed
472
    for (cellId=0; cellId < numCells; cellId++)
473
    {
474
      if ( this->Visited[cellId] == largestRegionId )
475
      {
476
477
478
        // special handling for polyhedron cells
        if (vtkUnstructuredGrid::SafeDownCast(input) &&
            input->GetCellType(cellId) == VTK_POLYHEDRON)
479
        {
480
481
          vtkUnstructuredGrid::SafeDownCast(input)->
            GetFaceStream(cellId, this->PointIds);
482
          vtkUnstructuredGrid::ConvertFaceStreamPointIds(this->PointIds,
483
                                                         this->PointMap);
484
        }
485
        else
486
        {
487
488
          input->GetCellPoints(cellId, this->PointIds);
          for (i=0; i < this->PointIds->GetNumberOfIds(); i++)
489
          {
490
491
            id = this->PointMap[this->PointIds->GetId(i)];
            this->PointIds->InsertId(i,id);
Will Schroeder's avatar
Will Schroeder committed
492
          }
493
        }
494
        vtkIdType newCellId = -1;
495
496
497
498
499
500
501
502
503
504
        if (pdOutput)
        {
          newCellId = pdOutput->InsertNextCell(input->GetCellType(cellId),
                                               this->PointIds);
        }
        else if (ugOutput)
        {
          newCellId = ugOutput->InsertNextCell(input->GetCellType(cellId),
                                               this->PointIds);
        }
505
506
507
508
        if (newCellId >= 0)
        {
          outputCD->CopyData(cd, cellId, newCellId);
        }
Will Schroeder's avatar
Will Schroeder committed
509
      }
510
511
    }
  }
Will Schroeder's avatar
Will Schroeder committed
512

513
514
  delete [] this->Visited;
  delete [] this->PointMap;
515
516
  this->PointIds->Delete();
  this->CellIds->Delete();
Will Schroeder's avatar
Will Schroeder committed
517
  output->Squeeze();
518
  vtkDataArray* outScalars = nullptr;
Yves Starreveld's avatar
   
Yves Starreveld committed
519
  if (this->ColorRegions && (outScalars=output->GetPointData()->GetScalars()))
520
  {
521
    outScalars->Resize(output->GetNumberOfPoints());
522
  }
Will Schroeder's avatar
Will Schroeder committed
523

524
525
526
527
  int num = this->GetNumberOfExtractedRegions();
  int count = 0;

  for (int ii = 0; ii < num; ii++)
528
  {
529
    count += this->RegionSizes->GetValue (ii);
530
  }
531
  vtkDebugMacro (<< "Total # of cells accounted for: " << count);
532
  vtkDebugMacro (<< "Extracted " << output->GetNumberOfCells() << " cells");
Will Schroeder's avatar
Will Schroeder committed
533

534
  return 1;
Will Schroeder's avatar
Will Schroeder committed
535
536
}

537

Will Schroeder's avatar
Will Schroeder committed
538
539
540
// Mark current cell as visited and assign region number.  Note:
// traversal occurs across shared vertices.
//
541
void vtkConnectivityFilter::TraverseAndMark (vtkDataSet *input)
Will Schroeder's avatar
Will Schroeder committed
542
{
543
  vtkIdType i, j, k, cellId, numIds, ptId, numPts, numCells;
544
  vtkIdList *tmpWave;
Will Schroeder's avatar
Will Schroeder committed
545

546
  while ( (numIds=this->Wave->GetNumberOfIds()) > 0 )
547
  {
548
    for ( i=0; i < numIds; i++ )
549
    {
550
      cellId = this->Wave->GetId(i);
551
      if ( this->Visited[cellId] < 0 )
552
      {
553
        this->NewCellScalars->SetValue(cellId, this->RegionNumber);
554
555
556
557
558
        this->Visited[cellId] = this->RegionNumber;
        this->NumCellsInRegion++;
        input->GetCellPoints(cellId, this->PointIds);

        numPts = this->PointIds->GetNumberOfIds();
559
        for (j=0; j < numPts; j++)
560
        {
561
          if ( this->PointMap[ptId=this->PointIds->GetId(j)] < 0 )
562
          {
563
            this->PointMap[ptId] = this->PointNumber++;
564
565
            this->NewScalars->SetValue(this->PointMap[ptId],
                                       this->RegionNumber);
566
          }
Will Schroeder's avatar
Will Schroeder committed
567

568
          input->GetPointCells(ptId,this->CellIds);
Will Schroeder's avatar
Will Schroeder committed
569

570
571
572
          // check connectivity criterion (geometric + scalar)
          numCells = this->CellIds->GetNumberOfIds();
          for (k=0; k < numCells; k++)
573
          {
574
575
            cellId = this->CellIds->GetId(k);
            if ( this->InScalars )
576
            {
577
              int numScalars, ii;
Ken Martin's avatar
Ken Martin committed
578
              double s, range[2];
579
580

              input->GetCellPoints(cellId, this->NeighborCellPointIds);
581
582
583
              numScalars = this->NeighborCellPointIds->GetNumberOfIds();
              this->CellScalars->SetNumberOfComponents(this->InScalars->GetNumberOfComponents());
              this->CellScalars->SetNumberOfTuples(numScalars);
584
              this->InScalars->GetTuples(this->NeighborCellPointIds,
585
                                         this->CellScalars);
Ken Martin's avatar
Ken Martin committed
586
              range[0] = VTK_DOUBLE_MAX; range[1] = -VTK_DOUBLE_MAX;
587
              for (ii=0; ii < numScalars;  ii++)
588
              {
589
                s = this->CellScalars->GetComponent(ii,0);
590
                if ( s < range[0] )
591
                {
592
                  range[0] = s;
593
                }
594
                if ( s > range[1] )
595
                {
596
597
                  range[1] = s;
                }
598
              }
599
              if ( range[1] >= this->ScalarRange[0] &&
600
                   range[0] <= this->ScalarRange[1] )
601
              {
602
603
                this->Wave2->InsertNextId(cellId);
              }
604
            }
605
            else
606
            {
607
              this->Wave2->InsertNextId(cellId);
608
609
610
611
612
            }
          }//for all cells using this point
        }//for all points of this cell
      }//if cell not yet visited
    }//for all cells in this wave
613
614
615
616
617

    tmpWave = this->Wave;
    this->Wave = this->Wave2;
    this->Wave2 = tmpWave;
    tmpWave->Reset();
618
  } //while wave is not empty
Will Schroeder's avatar
Will Schroeder committed
619
620
}

Cory Quammen's avatar
Cory Quammen committed
621
622
623
624
void vtkConnectivityFilter::OrderRegionIds(vtkIdTypeArray* pointRegionIds, vtkIdTypeArray* cellRegionIds)
{
  if (this->ColorRegions)
  {
625
626
    if (this->RegionIdAssignmentMode == CELL_COUNT_DESCENDING ||
        this->RegionIdAssignmentMode == CELL_COUNT_ASCENDING)
Cory Quammen's avatar
Cory Quammen committed
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
    {
      // Use a multimap to handle cases where more than one region has the same number of cells.
      std::multimap<vtkIdType, vtkIdType> cellCountToRegionId;
      typedef std::multimap<vtkIdType, vtkIdType>::value_type ValueType;
      vtkIdType numRegions = this->RegionSizes->GetNumberOfTuples();
      for (vtkIdType regionId = 0; regionId < numRegions; ++regionId)
      {
        ValueType value(this->RegionSizes->GetValue(regionId), regionId);
        cellCountToRegionId.insert(value);
      }

      // Now reverse iterate through the sorted multimap to process the RegionIds
      // from largest to smallest and create a map from the old RegionId to the new
      // RegionId
      std::map<vtkIdType, vtkIdType> oldToNew;
      vtkIdType counter = 0;
643
      if (this->RegionIdAssignmentMode == CELL_COUNT_ASCENDING)
Cory Quammen's avatar
Cory Quammen committed
644
      {
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
        for (auto iter = cellCountToRegionId.begin(); iter != cellCountToRegionId.end(); ++iter)
        {
          auto regionCount = iter->first;
          auto regionId = iter->second;

          // Re-order the region sizes based on the sorting
          this->RegionSizes->SetValue(counter, regionCount);

          // Create map from old to new RegionId
          oldToNew[regionId] = counter++;
        }
      }
      else // CELL_COUNT_DESCENDING
      {
        for (auto iter = cellCountToRegionId.rbegin(); iter != cellCountToRegionId.rend(); ++iter)
        {
          auto regionCount = iter->first;
          auto regionId = iter->second;
Cory Quammen's avatar
Cory Quammen committed
663

664
665
          // Re-order the region sizes based on the sorting
          this->RegionSizes->SetValue(counter, regionCount);
Cory Quammen's avatar
Cory Quammen committed
666

667
668
669
          // Create map from old to new RegionId
          oldToNew[regionId] = counter++;
        }
Cory Quammen's avatar
Cory Quammen committed
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
      }

      vtkIdType numPts = pointRegionIds->GetNumberOfTuples();
      for (vtkIdType i = 0; i < numPts; ++i)
      {
        vtkIdType oldValue = pointRegionIds->GetValue(i);
        pointRegionIds->SetValue(i, oldToNew[oldValue]);
      }

      vtkIdType numCells = cellRegionIds->GetNumberOfTuples();
      for (vtkIdType i = 0; i < numCells; ++i)
      {
        vtkIdType oldValue = cellRegionIds->GetValue(i);
        cellRegionIds->SetValue(i, oldToNew[oldValue]);
      }
    }
    // else UNSPECIFIED mode
  }
}

Will Schroeder's avatar
Will Schroeder committed
690
// Obtain the number of connected regions.
Ken Martin's avatar
Ken Martin committed
691
int vtkConnectivityFilter::GetNumberOfExtractedRegions()
Will Schroeder's avatar
Will Schroeder committed
692
{
Charles Law's avatar
Charles Law committed
693
  return this->RegionSizes->GetMaxId() + 1;
Will Schroeder's avatar
Will Schroeder committed
694
695
}

696
697
698
699
700
701
702
703
704
705
706
707
int vtkConnectivityFilter::ProcessRequest(vtkInformation* request,
  vtkInformationVector** inputVector, vtkInformationVector* outputVector)
{
  if (request->Has(vtkDemandDrivenPipeline::REQUEST_DATA_OBJECT()))
  {
    return this->RequestDataObject(request, inputVector, outputVector);
  }

  return this->Superclass::ProcessRequest(request, inputVector, outputVector);
}


Will Schroeder's avatar
Will Schroeder committed
708
// Initialize list of point ids/cell ids used to seed regions.
Ken Martin's avatar
Ken Martin committed
709
void vtkConnectivityFilter::InitializeSeedList()
Will Schroeder's avatar
Will Schroeder committed
710
711
{
  this->Modified();
712
  this->Seeds->Reset();
Will Schroeder's avatar
Will Schroeder committed
713
714
}

Will Schroeder's avatar
Will Schroeder committed
715
// Add a seed id (point or cell id). Note: ids are 0-offset.
Amy Squillacote's avatar
Amy Squillacote committed
716
void vtkConnectivityFilter::AddSeed(vtkIdType id)
Will Schroeder's avatar
Will Schroeder committed
717
718
{
  this->Modified();
719
  this->Seeds->InsertNextId(id);
Will Schroeder's avatar
Will Schroeder committed
720
721
}

Will Schroeder's avatar
Will Schroeder committed
722
// Delete a seed id (point or cell id). Note: ids are 0-offset.
Amy Squillacote's avatar
Amy Squillacote committed
723
void vtkConnectivityFilter::DeleteSeed(vtkIdType id)
Will Schroeder's avatar
Will Schroeder committed
724
725
{
  this->Modified();
726
  this->Seeds->DeleteId(id);
Will Schroeder's avatar
Will Schroeder committed
727
728
}

Will Schroeder's avatar
Will Schroeder committed
729
// Initialize list of region ids to extract.
Ken Martin's avatar
Ken Martin committed
730
void vtkConnectivityFilter::InitializeSpecifiedRegionList()
Will Schroeder's avatar
Will Schroeder committed
731
732
{
  this->Modified();
733
  this->SpecifiedRegionIds->Reset();
Will Schroeder's avatar
Will Schroeder committed
734
735
}

Will Schroeder's avatar
Will Schroeder committed
736
// Add a region id to extract. Note: ids are 0-offset.
Ken Martin's avatar
Ken Martin committed
737
void vtkConnectivityFilter::AddSpecifiedRegion(int id)
Will Schroeder's avatar
Will Schroeder committed
738
739
{
  this->Modified();
740
  this->SpecifiedRegionIds->InsertNextId(id);
Will Schroeder's avatar
Will Schroeder committed
741
742
}

Will Schroeder's avatar
Will Schroeder committed
743
// Delete a region id to extract. Note: ids are 0-offset.
Ken Martin's avatar
Ken Martin committed
744
void vtkConnectivityFilter::DeleteSpecifiedRegion(int id)
Will Schroeder's avatar
Will Schroeder committed
745
746
{
  this->Modified();
747
  this->SpecifiedRegionIds->DeleteId(id);
Will Schroeder's avatar
Will Schroeder committed
748
749
}

750
751
752
753
754
755
int vtkConnectivityFilter::FillInputPortInformation(int, vtkInformation *info)
{
  info->Set(vtkAlgorithm::INPUT_REQUIRED_DATA_TYPE(), "vtkDataSet");
  return 1;
}

756
757
758
759
760
761
int vtkConnectivityFilter::FillOutputPortInformation(int vtkNotUsed(port), vtkInformation* info)
{
  info->Set(vtkDataObject::DATA_TYPE_NAME(), "vtkDataSet");
  return 1;
}

762
void vtkConnectivityFilter::PrintSelf(ostream& os, vtkIndent indent)
Will Schroeder's avatar
Will Schroeder committed
763
{
Brad King's avatar
Brad King committed
764
  this->Superclass::PrintSelf(os,indent);
Will Schroeder's avatar
Will Schroeder committed
765

766
  os << indent << "Extraction Mode: ";
767
768
  os << this->GetExtractionModeAsString() << "\n";

769
  os << indent << "Closest Point: (" << this->ClosestPoint[0] << ", "
770
     << this->ClosestPoint[1] << ", " << this->ClosestPoint[2] << ")\n";
Will Schroeder's avatar
Will Schroeder committed
771

772
773
  os << indent << "Color Regions: " << (this->ColorRegions ? "On\n" : "Off\n");

774
  os << indent << "Scalar Connectivity: "
775
776
     << (this->ScalarConnectivity ? "On\n" : "Off\n");

Ken Martin's avatar
Ken Martin committed
777
  double *range = this->GetScalarRange();
778
  os << indent << "Scalar Range: (" << range[0] << ", " << range[1] << ")\n";
779
780
  os << indent << "Output Points Precision: " << this->OutputPointsPrecision
     << "\n";
Will Schroeder's avatar
Will Schroeder committed
781
}