1 /*=========================================================================
2
3 Program: Visualization Toolkit
4 Module: vtkMarchingSquares.cxx
5
6 Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
7 All rights reserved.
8 See Copyright.txt or http://www.kitware.com/Copyright.htm for details.
9
10 This software is distributed WITHOUT ANY WARRANTY; without even
11 the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
12 PURPOSE. See the above copyright notice for more information.
13
14 =========================================================================*/
15 #include "vtkMarchingSquares.h"
16
17 #include "vtkCellArray.h"
18 #include "vtkCharArray.h"
19 #include "vtkDoubleArray.h"
20 #include "vtkFloatArray.h"
21 #include "vtkInformation.h"
22 #include "vtkInformationVector.h"
23 #include "vtkIntArray.h"
24 #include "vtkLongArray.h"
25 #include "vtkMarchingSquaresLineCases.h"
26 #include "vtkMergePoints.h"
27 #include "vtkObjectFactory.h"
28 #include "vtkPointData.h"
29 #include "vtkPolyData.h"
30 #include "vtkShortArray.h"
31 #include "vtkStructuredPoints.h"
32 #include "vtkUnsignedCharArray.h"
33 #include "vtkUnsignedIntArray.h"
34 #include "vtkUnsignedLongArray.h"
35 #include "vtkUnsignedShortArray.h"
36 #include "vtkIncrementalPointLocator.h"
37
38 #include <math.h>
39
40 vtkStandardNewMacro(vtkMarchingSquares);
41
42 // Description:
43 // Construct object with initial scalar range (0,1) and single contour value
44 // of 0.0. The ImageRange are set to extract the first k-plane.
vtkMarchingSquares()45 vtkMarchingSquares::vtkMarchingSquares()
46 {
47 this->ContourValues = vtkContourValues::New();
48
49 this->ImageRange[0] = 0; this->ImageRange[1] = VTK_INT_MAX;
50 this->ImageRange[2] = 0; this->ImageRange[3] = VTK_INT_MAX;
51 this->ImageRange[4] = 0; this->ImageRange[5] = 0;
52
53 this->Locator = NULL;
54 }
55
~vtkMarchingSquares()56 vtkMarchingSquares::~vtkMarchingSquares()
57 {
58 this->ContourValues->Delete();
59 if ( this->Locator )
60 {
61 this->Locator->UnRegister(this);
62 this->Locator = NULL;
63 }
64 }
65
SetImageRange(int imin,int imax,int jmin,int jmax,int kmin,int kmax)66 void vtkMarchingSquares::SetImageRange(int imin, int imax, int jmin, int jmax,
67 int kmin, int kmax)
68 {
69 int dim[6];
70
71 dim[0] = imin;
72 dim[1] = imax;
73 dim[2] = jmin;
74 dim[3] = jmax;
75 dim[4] = kmin;
76 dim[5] = kmax;
77
78 this->SetImageRange(dim);
79 }
80
81 // Description:
82 // Overload standard modified time function. If contour values are modified,
83 // then this object is modified as well.
GetMTime()84 unsigned long vtkMarchingSquares::GetMTime()
85 {
86 unsigned long mTime=this->Superclass::GetMTime();
87 unsigned long mTime2=this->ContourValues->GetMTime();
88
89 mTime = ( mTime2 > mTime ? mTime2 : mTime );
90 if (this->Locator)
91 {
92 mTime2=this->Locator->GetMTime();
93 mTime = ( mTime2 > mTime ? mTime2 : mTime );
94 }
95
96 return mTime;
97 }
98
99 //
100 // Contouring filter specialized for images
101 //
102 template <class T>
vtkContourImage(T * scalars,vtkDataArray * newScalars,int roi[6],int dir[3],int start[2],int end[2],int offset[3],double ar[3],double origin[3],double * values,int numValues,vtkIncrementalPointLocator * p,vtkCellArray * lines)103 void vtkContourImage(T *scalars, vtkDataArray *newScalars, int roi[6], int dir[3],
104 int start[2], int end[2], int offset[3], double ar[3],
105 double origin[3], double *values, int numValues,
106 vtkIncrementalPointLocator *p, vtkCellArray *lines)
107 {
108 int i, j;
109 vtkIdType ptIds[2];
110 double t, *x1, *x2, x[3], xp, yp;
111 double pts[4][3], min, max;
112 int contNum, jOffset, idx, ii, jj, index, *vert;
113 static int CASE_MASK[4] = {1,2,8,4};
114 vtkMarchingSquaresLineCases *lineCase, *lineCases;
115 static int edges[4][2] = { {0,1}, {1,3}, {2,3}, {0,2} };
116 EDGE_LIST *edge;
117 double value, s[4];
118
119 lineCases = vtkMarchingSquaresLineCases::GetCases();
120 //
121 // Get min/max contour values
122 //
123 if ( numValues < 1 )
124 {
125 return;
126 }
127 for ( min=max=values[0], i=1; i < numValues; i++)
128 {
129 if ( values[i] < min )
130 {
131 min = values[i];
132 }
133 if ( values[i] > max )
134 {
135 max = values[i];
136 }
137 }
138
139 //assign coordinate value to non-varying coordinate direction
140 x[dir[2]] = origin[dir[2]] + roi[dir[2]*2]*ar[dir[2]];
141
142 // Traverse all pixel cells, generating line segements using marching squares.
143 for ( j=roi[start[1]]; j < roi[end[1]]; j++ )
144 {
145
146 jOffset = j * offset[1];
147 pts[0][dir[1]] = origin[dir[1]] + j*ar[dir[1]];
148 yp = origin[dir[1]] + (j+1)*ar[dir[1]];
149
150 for ( i=roi[start[0]]; i < roi[end[0]]; i++)
151 {
152 //get scalar values
153 idx = i * offset[0] + jOffset + offset[2];
154 s[0] = scalars[idx];
155 s[1] = scalars[idx+offset[0]];
156 s[2] = scalars[idx + offset[1]];
157 s[3] = scalars[idx+offset[0] + offset[1]];
158
159 if ( (s[0] < min && s[1] < min && s[2] < min && s[3] < min) ||
160 (s[0] > max && s[1] > max && s[2] > max && s[3] > max) )
161 {
162 continue; // no contours possible
163 }
164
165 //create pixel points
166 pts[0][dir[0]] = origin[dir[0]] + i*ar[dir[0]];
167 xp = origin[dir[0]] + (i+1)*ar[dir[0]];
168
169 pts[1][dir[0]] = xp;
170 pts[1][dir[1]] = pts[0][dir[1]];
171
172 pts[2][dir[0]] = pts[0][dir[0]];
173 pts[2][dir[1]] = yp;
174
175 pts[3][dir[0]] = xp;
176 pts[3][dir[1]] = yp;
177
178 // Loop over contours in this pixel
179 for (contNum=0; contNum < numValues; contNum++)
180 {
181 value = values[contNum];
182
183 // Build the case table
184 for ( ii=0, index = 0; ii < 4; ii++)
185 {
186 if ( s[ii] >= value )
187 {
188 index |= CASE_MASK[ii];
189 }
190 }
191 if ( index == 0 || index == 15 )
192 {
193 continue; //no lines
194 }
195
196 lineCase = lineCases + index;
197 edge = lineCase->edges;
198
199 for ( ; edge[0] > -1; edge += 2 )
200 {
201 for (ii=0; ii<2; ii++) //insert line
202 {
203 vert = edges[edge[ii]];
204 t = (value - s[vert[0]]) / (s[vert[1]] - s[vert[0]]);
205 x1 = pts[vert[0]];
206 x2 = pts[vert[1]];
207 for (jj=0; jj<2; jj++) //only need to interpolate two values
208 {
209 x[dir[jj]] = x1[dir[jj]] + t * (x2[dir[jj]] - x1[dir[jj]]);
210 }
211 if ( p->InsertUniquePoint(x, ptIds[ii]) )
212 {
213 newScalars->InsertComponent(ptIds[ii],0,value);
214 }
215 }
216
217 if ( ptIds[0] != ptIds[1] ) //check for degenerate line
218 {
219 lines->InsertNextCell(2,ptIds);
220 }
221
222 }//for each line
223 }//for all contours
224 }//for i
225 }//for j
226 }
227
228 //
229 // Contouring filter specialized for images (or slices from images)
230 //
RequestData(vtkInformation * vtkNotUsed (request),vtkInformationVector ** inputVector,vtkInformationVector * outputVector)231 int vtkMarchingSquares::RequestData(
232 vtkInformation *vtkNotUsed(request),
233 vtkInformationVector **inputVector,
234 vtkInformationVector *outputVector)
235 {
236 // get the info objects
237 vtkInformation *inInfo = inputVector[0]->GetInformationObject(0);
238 vtkInformation *outInfo = outputVector->GetInformationObject(0);
239
240 // get the input and output
241 vtkImageData *input = vtkImageData::SafeDownCast(
242 inInfo->Get(vtkDataObject::DATA_OBJECT()));
243 vtkPolyData *output = vtkPolyData::SafeDownCast(
244 outInfo->Get(vtkDataObject::DATA_OBJECT()));
245
246 vtkPointData *pd;
247 vtkPoints *newPts;
248 vtkCellArray *newLines;
249 vtkDataArray *inScalars;
250 vtkDataArray *newScalars = NULL;
251 int i, dims[3], roi[6], dataSize, dim, plane=0;
252 int *ext;
253 double origin[3], ar[3];
254 int start[2], end[2], offset[3], dir[3], estimatedSize;
255 int numContours=this->ContourValues->GetNumberOfContours();
256 double *values=this->ContourValues->GetValues();
257
258 vtkDebugMacro(<< "Executing marching squares");
259 //
260 // Initialize and check input
261 //
262 pd=input->GetPointData();
263 if (pd ==NULL)
264 {
265 vtkErrorMacro(<<"PointData is NULL");
266 return 1;
267 }
268 inScalars=pd->GetScalars();
269 if ( inScalars == NULL )
270 {
271 vtkErrorMacro(<<"Scalars must be defined for contouring");
272 return 1;
273 }
274 //
275 // Check dimensionality of data and get appropriate form
276 //
277 input->GetDimensions(dims);
278 ext = input->GetExtent();
279 input->GetOrigin(origin);
280 input->GetSpacing(ar);
281 dataSize = dims[0] * dims[1] * dims[2];
282
283 if ( input->GetDataDimension() != 2 )
284 {
285 for (i=0; i < 6; i++)
286 {
287 roi[i] = this->ImageRange[i];
288 }
289 }
290 else
291 {
292 input->GetExtent(roi);
293 }
294
295 // check the final region of interest to make sure its acceptable
296 for ( dim=0, i=0; i < 3; i++ )
297 {
298 if ( roi[2*i+1] > ext[2*i+1] )
299 {
300 roi[2*i+1] = ext[2*i+1];
301 }
302 else if ( roi[2*i+1] < ext[2*i] )
303 {
304 roi[2*i+1] = ext[2*i];
305 }
306
307 if ( roi[2*i] > roi[2*i+1] )
308 {
309 roi[2*i] = roi[2*i+1];
310 }
311 else if ( roi[2*i] < ext[2*i] )
312 {
313 roi[2*i] = ext[2*i];
314 }
315
316 if ( (roi[2*i+1]-roi[2*i]) > 0 )
317 {
318 dim++;
319 }
320 else
321 {
322 plane = i;
323 }
324 }
325
326 if ( dim != 2 )
327 {
328 vtkErrorMacro(<<"Marching squares requires 2D data");
329 return 1;
330 }
331 //
332 // Setup indices and offsets (since can have x-y or z-plane)
333 //
334 if ( plane == 0 ) //x-plane
335 {
336 start[0] = 2; end[0] = 3;
337 start[1] = 4; end[1] = 5;
338 offset[0] = dims[0];
339 offset[1] = dims[0]*dims[1];
340 offset[2] = (roi[0]-ext[0]);
341 dir[0] = 1; dir[1] = 2; dir[2] = 0;
342 }
343 else if ( plane == 1 ) //y-plane
344 {
345 start[0] = 0; end[0] = 1;
346 start[1] = 4; end[1] = 5;
347 offset[0] = 1;
348 offset[1] = dims[0]*dims[1];
349 offset[2] = (roi[2]-ext[2])*dims[0];
350 dir[0] = 0; dir[1] = 2; dir[2] = 1;
351 }
352 else //z-plane
353 {
354 start[0] = 0; end[0] = 1;
355 start[1] = 2; end[1] = 3;
356 offset[0] = 1;
357 offset[1] = dims[0];
358 offset[2] = (roi[4]-ext[4])*dims[0]*dims[1];
359 dir[0] = 0; dir[1] = 1; dir[2] = 2;
360 }
361 //
362 // Allocate necessary objects
363 //
364 estimatedSize = (int) (numContours * sqrt((double)dims[0]*dims[1]));
365 estimatedSize = estimatedSize / 1024 * 1024; //multiple of 1024
366 if (estimatedSize < 1024)
367 {
368 estimatedSize = 1024;
369 }
370
371 newPts = vtkPoints::New();
372 newPts->Allocate(estimatedSize,estimatedSize);
373 newLines = vtkCellArray::New();
374 newLines->Allocate(newLines->EstimateSize(estimatedSize,2));
375
376 // locator used to merge potentially duplicate points
377 if ( this->Locator == NULL )
378 {
379 this->CreateDefaultLocator();
380 }
381 this->Locator->InitPointInsertion (newPts, input->GetBounds());
382 //
383 // Check data type and execute appropriate function
384 //
385 if (inScalars->GetNumberOfComponents() == 1 )
386 {
387 void* scalars = inScalars->GetVoidPointer(0);
388 newScalars = inScalars->NewInstance();
389 newScalars->Allocate(5000, 25000);
390 switch (inScalars->GetDataType())
391 {
392 vtkTemplateMacro(
393 vtkContourImage(static_cast<VTK_TT*>(scalars),newScalars,
394 roi,dir,start,end,offset,ar,origin,
395 values,numContours,this->Locator,newLines)
396 );
397 }//switch
398 }
399
400 else //multiple components - have to convert
401 {
402 vtkDoubleArray *image = vtkDoubleArray::New();
403 image->SetNumberOfComponents(inScalars->GetNumberOfComponents());
404 image->SetNumberOfTuples(dataSize);
405 inScalars->GetTuples(0,dataSize,image);
406 newScalars = vtkFloatArray::New();
407 newScalars->Allocate(5000,25000);
408 double *scalars = image->GetPointer(0);
409 vtkContourImage(scalars,newScalars,roi,dir,start,end,offset,ar,origin,
410 values,numContours,this->Locator,newLines);
411 image->Delete();
412 }
413
414 vtkDebugMacro(<<"Created: "
415 << newPts->GetNumberOfPoints() << " points, "
416 << newLines->GetNumberOfCells() << " lines");
417 //
418 // Update ourselves. Because we don't know up front how many lines
419 // we've created, take care to reclaim memory.
420 //
421 output->SetPoints(newPts);
422 newPts->Delete();
423
424 output->SetLines(newLines);
425 newLines->Delete();
426
427 int idx = output->GetPointData()->AddArray(newScalars);
428 output->GetPointData()->SetActiveAttribute(idx, vtkDataSetAttributes::SCALARS);
429 newScalars->Delete();
430
431 this->Locator->Initialize();
432 output->Squeeze();
433
434 return 1;
435 }
436
437 // Description:
438 // Specify a spatial locator for merging points. By default,
439 // an instance of vtkMergePoints is used.
SetLocator(vtkIncrementalPointLocator * locator)440 void vtkMarchingSquares::SetLocator(vtkIncrementalPointLocator *locator)
441 {
442 if ( this->Locator == locator)
443 {
444 return;
445 }
446
447 if ( this->Locator )
448 {
449 this->Locator->UnRegister(this);
450 this->Locator = NULL;
451 }
452
453 if ( locator )
454 {
455 locator->Register(this);
456 }
457
458 this->Locator = locator;
459 this->Modified();
460 }
461
CreateDefaultLocator()462 void vtkMarchingSquares::CreateDefaultLocator()
463 {
464 if ( this->Locator == NULL)
465 {
466 this->Locator = vtkMergePoints::New();
467 }
468 }
469
FillInputPortInformation(int,vtkInformation * info)470 int vtkMarchingSquares::FillInputPortInformation(int, vtkInformation *info)
471 {
472 info->Set(vtkAlgorithm::INPUT_REQUIRED_DATA_TYPE(), "vtkImageData");
473 return 1;
474 }
475
PrintSelf(ostream & os,vtkIndent indent)476 void vtkMarchingSquares::PrintSelf(ostream& os, vtkIndent indent)
477 {
478 this->Superclass::PrintSelf(os,indent);
479
480 this->ContourValues->PrintSelf(os,indent.GetNextIndent());
481
482 os << indent << "Image Range: ( "
483 << this->ImageRange[0] << ", "
484 << this->ImageRange[1] << ", "
485 << this->ImageRange[2] << ", "
486 << this->ImageRange[3] << ", "
487 << this->ImageRange[4] << ", "
488 << this->ImageRange[5] << " )\n";
489
490 if ( this->Locator )
491 {
492 os << indent << "Locator: " << this->Locator << "\n";
493 }
494 else
495 {
496 os << indent << "Locator: (none)\n";
497 }
498 }
499