1 /*=========================================================================
2
3 Program: Visualization Toolkit
4 Module: vtkBSplineTransform.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 "vtkBSplineTransform.h"
16
17 #include "vtkImageData.h"
18 #include "vtkMath.h"
19 #include "vtkObjectFactory.h"
20 #include "vtkStreamingDemandDrivenPipeline.h"
21 #include "vtkTrivialProducer.h"
22
23 #include <cmath>
24
25 vtkStandardNewMacro(vtkBSplineTransform);
26
27 class vtkBSplineTransformConnectionHolder : public vtkAlgorithm
28 {
29 public:
30 static vtkBSplineTransformConnectionHolder* New();
31 vtkTypeMacro(vtkBSplineTransformConnectionHolder, vtkAlgorithm);
32
vtkBSplineTransformConnectionHolder()33 vtkBSplineTransformConnectionHolder() { this->SetNumberOfInputPorts(1); }
34 };
35
36 vtkStandardNewMacro(vtkBSplineTransformConnectionHolder);
37
38 namespace
39 {
40
41 //-------------------------------------------------------------
42 // The b-spline provides continuity of the first and second
43 // derivatives with a piecewise cubic polynomial. The polynomial
44 // does not pass through the knots.
vtkBSplineTransformWeights(double F[4],double G[4],double f)45 inline void vtkBSplineTransformWeights(double F[4], double G[4], double f)
46 {
47 const double sixth = 1.0 / 6.0;
48 const double half = 0.5;
49
50 double f2 = f * f;
51
52 F[3] = f2 * f * sixth;
53 F[0] = (f2 - f) * half - F[3] + sixth;
54 F[2] = f + F[0] - F[3] * 2;
55 F[1] = 1 - F[0] - F[2] - F[3];
56
57 // weights for derivative
58 G[3] = f2 * half;
59 G[0] = f - half - G[3];
60 G[2] = 1 + G[0] - G[3] * 2;
61 G[1] = -G[0] - G[2] - G[3];
62 }
63
64 //-------------------------------------------------------------
65 // if the support region for the b-spline is not fully within
66 // the bounds, take action here according to the BorderMode
vtkBSplineTransformBorder(int gridId0[3],int gridId1[3],int gridId2[3],int gridId3[3],double * ff[3],double * gg[3],int ext[3],int borderMode)67 int vtkBSplineTransformBorder(int gridId0[3], int gridId1[3], int gridId2[3], int gridId3[3],
68 double* ff[3], double* gg[3], int ext[3], int borderMode)
69 {
70 int pointIsInvalid = 0;
71
72 switch (borderMode)
73 {
74 case VTK_BSPLINE_EDGE:
75 // coefficient at edge continues infinitely past edge
76 // (this is continuous and smooth)
77 break;
78
79 case VTK_BSPLINE_ZERO:
80 // coefficients past edge are all zero
81 // (this is continuous and smooth)
82 for (int i = 0; i < 3; i++)
83 {
84 // note: "ext" is just the size subtract one
85 if (ext[i] != 0)
86 {
87 if (gridId1[i] == 0)
88 {
89 ff[i][0] = 0.0;
90 gg[i][0] = 0.0;
91 }
92 else if (gridId2[i] == 0)
93 {
94 ff[i][0] = 0.0;
95 ff[i][1] = 0.0;
96 gg[i][0] = 0.0;
97 gg[i][1] = 0.0;
98 }
99 else if (gridId3[i] == 0)
100 {
101 ff[i][0] = 0.0;
102 ff[i][1] = 0.0;
103 ff[i][2] = 0.0;
104 gg[i][0] = 0.0;
105 gg[i][1] = 0.0;
106 gg[i][2] = 0.0;
107 }
108 else if (gridId3[i] < 0)
109 {
110 pointIsInvalid = 1;
111 }
112
113 if (gridId2[i] == ext[i])
114 {
115 ff[i][3] = 0.0;
116 gg[i][3] = 0.0;
117 }
118 else if (gridId1[i] == ext[i])
119 {
120 ff[i][2] = 0.0;
121 ff[i][3] = 0.0;
122 gg[i][2] = 0.0;
123 gg[i][3] = 0.0;
124 }
125 else if (gridId0[i] == ext[i])
126 {
127 ff[i][1] = 0.0;
128 ff[i][2] = 0.0;
129 ff[i][3] = 0.0;
130 gg[i][1] = 0.0;
131 gg[i][2] = 0.0;
132 gg[i][3] = 0.0;
133 }
134 else if (gridId0[i] > ext[i])
135 {
136 pointIsInvalid = 1;
137 }
138 }
139 }
140 break;
141
142 case VTK_BSPLINE_ZERO_AT_BORDER:
143 // adjust weights to achieve zero displacement at one
144 // grid-spacing past the bounds of the grid
145 // (this is continuous but not smooth)
146 for (int j = 0; j < 3; j++)
147 {
148 // note: "ext" is just the size subtract one
149 if (ext[j] != 0)
150 {
151 if (gridId1[j] == 0)
152 {
153 ff[j][0] = 0.0;
154 if (gg[j])
155 {
156 gg[j][0] = 0.0;
157 }
158 }
159 else if (gridId2[j] == 0)
160 {
161 ff[j][2] -= ff[j][0];
162 ff[j][0] = 0.0;
163 ff[j][1] = 0.0;
164 gg[j][2] -= gg[j][0];
165 gg[j][0] = 0.0;
166 gg[j][1] = 0.0;
167 }
168 else if (gridId2[j] < 0)
169 {
170 pointIsInvalid = 1;
171 }
172
173 if (gridId2[j] == ext[j])
174 {
175 ff[j][3] = 0.0;
176 gg[j][3] = 0.0;
177 }
178 else if (gridId1[j] == ext[j])
179 {
180 ff[j][1] -= ff[j][3];
181 ff[j][2] = 0.0;
182 ff[j][3] = 0.0;
183 gg[j][1] -= gg[j][3];
184 gg[j][2] = 0.0;
185 gg[j][3] = 0.0;
186 }
187 else if (gridId1[j] > ext[j])
188 {
189 pointIsInvalid = 1;
190 }
191 }
192 }
193 break;
194 }
195
196 for (int k = 0; k < 3; k++)
197 {
198 // clamp to the boundary limits
199 int emax = ext[k];
200 if (gridId0[k] < 0)
201 {
202 gridId0[k] = 0;
203 }
204 if (gridId0[k] > emax)
205 {
206 gridId0[k] = emax;
207 }
208 if (gridId1[k] < 0)
209 {
210 gridId1[k] = 0;
211 }
212 if (gridId1[k] > emax)
213 {
214 gridId1[k] = emax;
215 }
216 if (gridId2[k] < 0)
217 {
218 gridId2[k] = 0;
219 }
220 if (gridId2[k] > emax)
221 {
222 gridId2[k] = emax;
223 }
224 if (gridId3[k] < 0)
225 {
226 gridId3[k] = 0;
227 }
228 if (gridId3[k] > emax)
229 {
230 gridId3[k] = emax;
231 }
232 }
233
234 return pointIsInvalid;
235 }
236
237 //-------------------------------------------------------------
238 template <class T>
239 class vtkBSplineTransformFunction
240 {
241 public:
242 static void Cubic(const double point[3], double displacement[3], double derivatives[3][3],
243 void* gridPtrVoid, int gridExt[6], vtkIdType gridInc[3], int borderMode);
244 };
245
246 template <class T>
Cubic(const double point[3],double displacement[3],double derivatives[3][3],void * gridPtrVoid,int gridExt[6],vtkIdType gridInc[3],int borderMode)247 void vtkBSplineTransformFunction<T>::Cubic(const double point[3], double displacement[3],
248 double derivatives[3][3], void* gridPtrVoid, int gridExt[6], vtkIdType gridInc[3], int borderMode)
249 {
250 // the interpolation weights
251 double fX[4] = { 0, 1, 0, 0 };
252 double fY[4] = { 0, 1, 0, 0 };
253 double fZ[4] = { 0, 1, 0, 0 };
254 double gX[4] = { 0, 0, 0, 0 };
255 double gY[4] = { 0, 0, 0, 0 };
256 double gZ[4] = { 0, 0, 0, 0 };
257
258 double* ff[3];
259 double* gg[3];
260
261 ff[0] = fX;
262 ff[1] = fY;
263 ff[2] = fZ;
264
265 gg[0] = gX;
266 gg[1] = gY;
267 gg[2] = gZ;
268
269 // initialize the knot positions
270 int gridId0[3] = { 0, 0, 0 };
271 int gridId1[3] = { 0, 0, 0 };
272 int gridId2[3] = { 0, 0, 0 };
273 int gridId3[3] = { 0, 0, 0 };
274
275 // "ext" is the size subtract one
276 int ext[3];
277
278 // compute the weights
279 for (int i = 0; i < 3; i++)
280 {
281 ext[i] = gridExt[2 * i + 1] - gridExt[2 * i];
282
283 if (ext[i] != 0)
284 {
285 // change point into integer plus fraction
286 int idx = vtkMath::Floor(point[i]);
287 double f = point[i] - idx;
288 idx -= gridExt[2 * i];
289 idx--;
290 gridId0[i] = idx++;
291 gridId1[i] = idx++;
292 gridId2[i] = idx++;
293 gridId3[i] = idx++;
294
295 vtkBSplineTransformWeights(ff[i], gg[i], f);
296 }
297 }
298
299 // do bounds check, most points will be inside so optimize for that
300 int pointIsInvalid = 0;
301
302 if ((gridId0[0] | (ext[0] - gridId3[0]) | gridId0[1] | (ext[1] - gridId3[1]) | gridId0[2] |
303 (ext[2] - gridId3[2])) < 0)
304 {
305 pointIsInvalid =
306 vtkBSplineTransformBorder(gridId0, gridId1, gridId2, gridId3, ff, gg, ext, borderMode);
307 }
308
309 // Compute the indices into the data
310 vtkIdType factX[4], factY[4], factZ[4];
311
312 factX[0] = gridId0[0] * gridInc[0];
313 factX[1] = gridId1[0] * gridInc[0];
314 factX[2] = gridId2[0] * gridInc[0];
315 factX[3] = gridId3[0] * gridInc[0];
316
317 factY[0] = gridId0[1] * gridInc[1];
318 factY[1] = gridId1[1] * gridInc[1];
319 factY[2] = gridId2[1] * gridInc[1];
320 factY[3] = gridId3[1] * gridInc[1];
321
322 factZ[0] = gridId0[2] * gridInc[2];
323 factZ[1] = gridId1[2] * gridInc[2];
324 factZ[2] = gridId2[2] * gridInc[2];
325 factZ[3] = gridId3[2] * gridInc[2];
326
327 // initialize displacement and derivatives to zero
328 displacement[0] = 0.0;
329 displacement[1] = 0.0;
330 displacement[2] = 0.0;
331
332 if (derivatives)
333 {
334 for (int i = 0; i < 3; i++)
335 {
336 derivatives[i][0] = 0.0;
337 derivatives[i][1] = 0.0;
338 derivatives[i][2] = 0.0;
339 }
340 }
341
342 // if point is valid, do the interpolation
343 if (!pointIsInvalid)
344 {
345 T* gridPtr = static_cast<T*>(gridPtrVoid);
346
347 // shortcut for 1D and 2D images (ext is size subtract 1)
348 int singleZ = (ext[2] == 0);
349 int jl = singleZ;
350 int jm = 4 - 2 * singleZ;
351 int singleY = (ext[1] == 0);
352 int kl = singleY;
353 int km = 4 - 2 * singleY;
354
355 // here is the tricubic interpolation
356 double vY[3], vZ[3];
357 displacement[0] = 0;
358 displacement[1] = 0;
359 displacement[2] = 0;
360 for (int j = jl; j < jm; j++)
361 {
362 T* gridPtr1 = gridPtr + factZ[j];
363 vZ[0] = 0;
364 vZ[1] = 0;
365 vZ[2] = 0;
366 for (int k = kl; k < km; k++)
367 {
368 T* gridPtr2 = gridPtr1 + factY[k];
369 vY[0] = 0;
370 vY[1] = 0;
371 vY[2] = 0;
372 if (!derivatives)
373 {
374 for (int l = 0; l < 4; l++)
375 {
376 T* gridPtr3 = gridPtr2 + factX[l];
377 double f = fX[l];
378 vY[0] += gridPtr3[0] * f;
379 vY[1] += gridPtr3[1] * f;
380 vY[2] += gridPtr3[2] * f;
381 }
382 }
383 else
384 {
385 for (int l = 0; l < 4; l++)
386 {
387 T* gridPtr3 = gridPtr2 + factX[l];
388 double f = fX[l];
389 double gff = gX[l] * fY[k] * fZ[j];
390 double fgf = fX[l] * gY[k] * fZ[j];
391 double ffg = fX[l] * fY[k] * gZ[j];
392 double inVal = gridPtr3[0];
393 vY[0] += inVal * f;
394 derivatives[0][0] += inVal * gff;
395 derivatives[0][1] += inVal * fgf;
396 derivatives[0][2] += inVal * ffg;
397 inVal = gridPtr3[1];
398 vY[1] += inVal * f;
399 derivatives[1][0] += inVal * gff;
400 derivatives[1][1] += inVal * fgf;
401 derivatives[1][2] += inVal * ffg;
402 inVal = gridPtr3[2];
403 vY[2] += inVal * f;
404 derivatives[2][0] += inVal * gff;
405 derivatives[2][1] += inVal * fgf;
406 derivatives[2][2] += inVal * ffg;
407 }
408 }
409 vZ[0] += vY[0] * fY[k];
410 vZ[1] += vY[1] * fY[k];
411 vZ[2] += vY[2] * fY[k];
412 }
413 displacement[0] += vZ[0] * fZ[j];
414 displacement[1] += vZ[1] * fZ[j];
415 displacement[2] += vZ[2] * fZ[j];
416 }
417 }
418 }
419
420 } // end anonymous namespace
421
422 //------------------------------------------------------------------------------
vtkBSplineTransform()423 vtkBSplineTransform::vtkBSplineTransform()
424 {
425 this->ConnectionHolder = vtkBSplineTransformConnectionHolder::New();
426 this->BorderMode = VTK_BSPLINE_EDGE;
427 this->InverseTolerance = 1e-6;
428 this->DisplacementScale = 1.0;
429 this->CalculateSpline = nullptr;
430 this->GridPointer = nullptr;
431 }
432
433 //------------------------------------------------------------------------------
~vtkBSplineTransform()434 vtkBSplineTransform::~vtkBSplineTransform()
435 {
436 this->ConnectionHolder->Delete();
437 this->ConnectionHolder = nullptr;
438 }
439
440 //------------------------------------------------------------------------------
PrintSelf(ostream & os,vtkIndent indent)441 void vtkBSplineTransform::PrintSelf(ostream& os, vtkIndent indent)
442 {
443 this->Superclass::PrintSelf(os, indent);
444
445 os << indent << "BorderMode: " << this->GetBorderModeAsString() << "\n";
446 os << indent << "DisplacementScale: " << this->DisplacementScale << "\n";
447 }
448
449 //------------------------------------------------------------------------------
GetBorderModeAsString()450 const char* vtkBSplineTransform::GetBorderModeAsString()
451 {
452 switch (this->BorderMode)
453 {
454 case VTK_BSPLINE_EDGE:
455 return "Edge";
456 case VTK_BSPLINE_ZERO:
457 return "Zero";
458 case VTK_BSPLINE_ZERO_AT_BORDER:
459 return "ZeroAtBorder";
460 default:
461 break;
462 }
463
464 return "Unknown";
465 }
466
467 //------------------------------------------------------------------------------
468 // need to check the input image data to determine MTime
GetMTime()469 vtkMTimeType vtkBSplineTransform::GetMTime()
470 {
471 vtkMTimeType mtime, result;
472 result = vtkWarpTransform::GetMTime();
473 if (this->GetCoefficientData())
474 {
475 vtkAlgorithm* inputAlgorithm = this->ConnectionHolder->GetInputAlgorithm(0, 0);
476 inputAlgorithm->UpdateInformation();
477
478 vtkStreamingDemandDrivenPipeline* sddp =
479 vtkStreamingDemandDrivenPipeline::SafeDownCast(inputAlgorithm->GetExecutive());
480 mtime = sddp->GetPipelineMTime();
481 result = (mtime > result ? mtime : result);
482 }
483
484 return result;
485 }
486
487 //------------------------------------------------------------------------------
ForwardTransformPoint(const double inPoint[3],double outPoint[3])488 void vtkBSplineTransform::ForwardTransformPoint(const double inPoint[3], double outPoint[3])
489 {
490 if (!this->GridPointer || !this->CalculateSpline)
491 {
492 outPoint[0] = inPoint[0];
493 outPoint[1] = inPoint[1];
494 outPoint[2] = inPoint[2];
495 return;
496 }
497
498 void* gridPtr = this->GridPointer;
499 double* spacing = this->GridSpacing;
500 double* origin = this->GridOrigin;
501 int* extent = this->GridExtent;
502 vtkIdType* increments = this->GridIncrements;
503
504 double scale = this->DisplacementScale;
505
506 double point[3];
507 double displacement[3];
508
509 displacement[0] = 0.0;
510 displacement[1] = 0.0;
511 displacement[2] = 0.0;
512
513 // Convert the inPoint to i,j,k indices into the deformation grid
514 // plus fractions
515 point[0] = (inPoint[0] - origin[0]) / spacing[0];
516 point[1] = (inPoint[1] - origin[1]) / spacing[1];
517 point[2] = (inPoint[2] - origin[2]) / spacing[2];
518
519 this->CalculateSpline(
520 point, displacement, nullptr, gridPtr, extent, increments, this->BorderMode);
521
522 outPoint[0] = inPoint[0] + displacement[0] * scale;
523 outPoint[1] = inPoint[1] + displacement[1] * scale;
524 outPoint[2] = inPoint[2] + displacement[2] * scale;
525 }
526
527 //------------------------------------------------------------------------------
528 // convert float to double, transform, and back again
ForwardTransformPoint(const float point[3],float output[3])529 void vtkBSplineTransform::ForwardTransformPoint(const float point[3], float output[3])
530 {
531 double fpoint[3];
532 fpoint[0] = point[0];
533 fpoint[1] = point[1];
534 fpoint[2] = point[2];
535
536 this->ForwardTransformPoint(fpoint, fpoint);
537
538 output[0] = static_cast<float>(fpoint[0]);
539 output[1] = static_cast<float>(fpoint[1]);
540 output[2] = static_cast<float>(fpoint[2]);
541 }
542
543 //------------------------------------------------------------------------------
544 // calculate the derivative of the transform
ForwardTransformDerivative(const double inPoint[3],double outPoint[3],double derivative[3][3])545 void vtkBSplineTransform::ForwardTransformDerivative(
546 const double inPoint[3], double outPoint[3], double derivative[3][3])
547 {
548 if (!this->GridPointer || !this->CalculateSpline)
549 {
550 outPoint[0] = inPoint[0];
551 outPoint[1] = inPoint[1];
552 outPoint[2] = inPoint[2];
553 vtkMath::Identity3x3(derivative);
554 return;
555 }
556
557 void* gridPtr = this->GridPointer;
558 double* spacing = this->GridSpacing;
559 double* origin = this->GridOrigin;
560 int* extent = this->GridExtent;
561 vtkIdType* increments = this->GridIncrements;
562
563 double scale = this->DisplacementScale;
564
565 double point[3];
566 double displacement[3];
567
568 // convert the inPoint to i,j,k indices plus fractions
569 point[0] = (inPoint[0] - origin[0]) / spacing[0];
570 point[1] = (inPoint[1] - origin[1]) / spacing[1];
571 point[2] = (inPoint[2] - origin[2]) / spacing[2];
572
573 this->CalculateSpline(
574 point, displacement, derivative, gridPtr, extent, increments, this->BorderMode);
575
576 for (int i = 0; i < 3; i++)
577 {
578 derivative[i][0] = derivative[i][0] * scale / spacing[0];
579 derivative[i][1] = derivative[i][1] * scale / spacing[1];
580 derivative[i][2] = derivative[i][2] * scale / spacing[2];
581 derivative[i][i] += 1.0;
582 }
583
584 outPoint[0] = inPoint[0] + displacement[0] * scale;
585 outPoint[1] = inPoint[1] + displacement[1] * scale;
586 outPoint[2] = inPoint[2] + displacement[2] * scale;
587 }
588
589 //------------------------------------------------------------------------------
590 // convert double to double
ForwardTransformDerivative(const float point[3],float output[3],float derivative[3][3])591 void vtkBSplineTransform::ForwardTransformDerivative(
592 const float point[3], float output[3], float derivative[3][3])
593 {
594 double fpoint[3];
595 double fderivative[3][3];
596 fpoint[0] = point[0];
597 fpoint[1] = point[1];
598 fpoint[2] = point[2];
599
600 this->ForwardTransformDerivative(fpoint, fpoint, fderivative);
601
602 for (int i = 0; i < 3; i++)
603 {
604 derivative[i][0] = static_cast<float>(fderivative[i][0]);
605 derivative[i][1] = static_cast<float>(fderivative[i][1]);
606 derivative[i][2] = static_cast<float>(fderivative[i][2]);
607 output[i] = static_cast<float>(fpoint[i]);
608 }
609 }
610
611 //------------------------------------------------------------------------------
612 // We use Newton's method to iteratively invert the transformation.
613 // This is actually quite robust as long as the Jacobian matrix is never
614 // singular.
615 // Note that this is similar to vtkWarpTransform::InverseTransformPoint()
616 // but has been optimized specifically for uniform grid transforms.
InverseTransformDerivative(const double inPoint[3],double outPoint[3],double derivative[3][3])617 void vtkBSplineTransform::InverseTransformDerivative(
618 const double inPoint[3], double outPoint[3], double derivative[3][3])
619 {
620 if (!this->GridPointer || !this->CalculateSpline)
621 {
622 outPoint[0] = inPoint[0];
623 outPoint[1] = inPoint[1];
624 outPoint[2] = inPoint[2];
625 return;
626 }
627
628 void* gridPtr = this->GridPointer;
629 double* spacing = this->GridSpacing;
630 double* origin = this->GridOrigin;
631 int* extent = this->GridExtent;
632 vtkIdType* increments = this->GridIncrements;
633
634 double invSpacing[3];
635 invSpacing[0] = 1.0 / spacing[0];
636 invSpacing[1] = 1.0 / spacing[1];
637 invSpacing[2] = 1.0 / spacing[2];
638
639 double scale = this->DisplacementScale;
640
641 double point[3], inverse[3], lastInverse[3];
642 double deltaP[3], deltaI[3];
643
644 double functionValue = 0;
645 double functionDerivative = 0;
646 double lastFunctionValue = VTK_DOUBLE_MAX;
647
648 double errorSquared = 0.0;
649 double toleranceSquared = this->InverseTolerance;
650 toleranceSquared *= toleranceSquared;
651
652 double f = 1.0;
653 double a;
654
655 // convert the inPoint to i,j,k indices plus fractions
656 point[0] = (inPoint[0] - origin[0]) * invSpacing[0];
657 point[1] = (inPoint[1] - origin[1]) * invSpacing[1];
658 point[2] = (inPoint[2] - origin[2]) * invSpacing[2];
659
660 // first guess at inverse point, just subtract displacement
661 // (the inverse point is given in i,j,k indices plus fractions)
662 this->CalculateSpline(point, deltaP, nullptr, gridPtr, extent, increments, this->BorderMode);
663
664 inverse[0] = point[0] - deltaP[0] * scale * invSpacing[0];
665 inverse[1] = point[1] - deltaP[1] * scale * invSpacing[1];
666 inverse[2] = point[2] - deltaP[2] * scale * invSpacing[2];
667 lastInverse[0] = inverse[0];
668 lastInverse[1] = inverse[1];
669 lastInverse[2] = inverse[2];
670
671 // do a maximum 500 iterations, usually less than 10 are required
672 int n = this->InverseIterations;
673 int i, j;
674
675 for (i = 0; i < n; i++)
676 {
677 this->CalculateSpline(
678 inverse, deltaP, derivative, gridPtr, extent, increments, this->BorderMode);
679
680 // convert displacement
681 deltaP[0] = (inverse[0] - point[0]) * spacing[0] + deltaP[0] * scale;
682 deltaP[1] = (inverse[1] - point[1]) * spacing[1] + deltaP[1] * scale;
683 deltaP[2] = (inverse[2] - point[2]) * spacing[2] + deltaP[2] * scale;
684
685 // convert derivative
686 for (j = 0; j < 3; j++)
687 {
688 derivative[j][0] = derivative[j][0] * scale * invSpacing[0];
689 derivative[j][1] = derivative[j][1] * scale * invSpacing[1];
690 derivative[j][2] = derivative[j][2] * scale * invSpacing[2];
691 derivative[j][j] += 1.0;
692 }
693
694 // get the current function value
695 functionValue = (deltaP[0] * deltaP[0] + deltaP[1] * deltaP[1] + deltaP[2] * deltaP[2]);
696
697 // if the function value is decreasing, do next Newton step
698 if (i == 0 || functionValue < lastFunctionValue)
699 {
700 // here is the critical step in Newton's method
701 vtkMath::LinearSolve3x3(derivative, deltaP, deltaI);
702
703 // get the error value in the output coord space
704 errorSquared = (deltaI[0] * deltaI[0] + deltaI[1] * deltaI[1] + deltaI[2] * deltaI[2]);
705
706 // break if less than tolerance in both coordinate systems
707 if (errorSquared < toleranceSquared && functionValue < toleranceSquared)
708 {
709 break;
710 }
711
712 // save the last inverse point
713 lastInverse[0] = inverse[0];
714 lastInverse[1] = inverse[1];
715 lastInverse[2] = inverse[2];
716
717 // save error at last inverse point
718 lastFunctionValue = functionValue;
719
720 // derivative of functionValue at last inverse point
721 functionDerivative =
722 (deltaP[0] * derivative[0][0] * deltaI[0] + deltaP[1] * derivative[1][1] * deltaI[1] +
723 deltaP[2] * derivative[2][2] * deltaI[2]) *
724 2;
725
726 // calculate new inverse point
727 inverse[0] -= deltaI[0] * invSpacing[0];
728 inverse[1] -= deltaI[1] * invSpacing[1];
729 inverse[2] -= deltaI[2] * invSpacing[2];
730
731 // reset f to 1.0
732 f = 1.0;
733
734 continue;
735 }
736
737 // the error is increasing, so take a partial step
738 // (see Numerical Recipes 9.7 for rationale, this code
739 // is a simplification of the algorithm provided there)
740
741 // quadratic approximation to find best fractional distance
742 a = -functionDerivative / (2 * (functionValue - lastFunctionValue - functionDerivative));
743
744 // clamp to range [0.1,0.5]
745 f *= (a < 0.1 ? 0.1 : (a > 0.5 ? 0.5 : a));
746
747 // re-calculate inverse using fractional distance
748 inverse[0] = lastInverse[0] - f * deltaI[0] * invSpacing[0];
749 inverse[1] = lastInverse[1] - f * deltaI[1] * invSpacing[1];
750 inverse[2] = lastInverse[2] - f * deltaI[2] * invSpacing[2];
751 }
752
753 if (i >= n)
754 {
755 // didn't converge: back up to last good result
756 inverse[0] = lastInverse[0];
757 inverse[1] = lastInverse[1];
758 inverse[2] = lastInverse[2];
759
760 vtkWarningMacro("InverseTransformPoint: no convergence ("
761 << inPoint[0] << ", " << inPoint[1] << ", " << inPoint[2]
762 << ") error = " << sqrt(errorSquared) << " after " << i << " iterations.");
763 }
764
765 // convert point
766 outPoint[0] = inverse[0] * spacing[0] + origin[0];
767 outPoint[1] = inverse[1] * spacing[1] + origin[1];
768 outPoint[2] = inverse[2] * spacing[2] + origin[2];
769 }
770
771 //------------------------------------------------------------------------------
772 // convert double to double and back again
InverseTransformDerivative(const float point[3],float output[3],float derivative[3][3])773 void vtkBSplineTransform::InverseTransformDerivative(
774 const float point[3], float output[3], float derivative[3][3])
775 {
776 double fpoint[3];
777 double fderivative[3][3];
778 fpoint[0] = point[0];
779 fpoint[1] = point[1];
780 fpoint[2] = point[2];
781
782 this->InverseTransformDerivative(fpoint, fpoint, fderivative);
783
784 for (int i = 0; i < 3; i++)
785 {
786 output[i] = static_cast<float>(fpoint[i]);
787 derivative[i][0] = static_cast<float>(fderivative[i][0]);
788 derivative[i][1] = static_cast<float>(fderivative[i][1]);
789 derivative[i][2] = static_cast<float>(fderivative[i][2]);
790 }
791 }
792
793 //------------------------------------------------------------------------------
InverseTransformPoint(const double point[3],double output[3])794 void vtkBSplineTransform::InverseTransformPoint(const double point[3], double output[3])
795 {
796 // the derivative won't be used, but it is required for Newton's method
797 double derivative[3][3];
798 this->InverseTransformDerivative(point, output, derivative);
799 }
800
801 //------------------------------------------------------------------------------
802 // convert double to double and back again
InverseTransformPoint(const float point[3],float output[3])803 void vtkBSplineTransform::InverseTransformPoint(const float point[3], float output[3])
804 {
805 double fpoint[3];
806 double fderivative[3][3];
807 fpoint[0] = point[0];
808 fpoint[1] = point[1];
809 fpoint[2] = point[2];
810
811 this->InverseTransformDerivative(fpoint, fpoint, fderivative);
812
813 output[0] = static_cast<float>(fpoint[0]);
814 output[1] = static_cast<float>(fpoint[1]);
815 output[2] = static_cast<float>(fpoint[2]);
816 }
817
818 //------------------------------------------------------------------------------
InternalDeepCopy(vtkAbstractTransform * transform)819 void vtkBSplineTransform::InternalDeepCopy(vtkAbstractTransform* transform)
820 {
821 vtkBSplineTransform* gridTransform = (vtkBSplineTransform*)transform;
822
823 this->SetInverseTolerance(gridTransform->InverseTolerance);
824 this->SetInverseIterations(gridTransform->InverseIterations);
825 this->CalculateSpline = gridTransform->CalculateSpline;
826 this->ConnectionHolder->SetInputConnection(0,
827 gridTransform->ConnectionHolder->GetNumberOfInputConnections(0)
828 ? gridTransform->ConnectionHolder->GetInputConnection(0, 0)
829 : nullptr);
830 this->SetDisplacementScale(gridTransform->DisplacementScale);
831 this->SetBorderMode(gridTransform->BorderMode);
832
833 if (this->InverseFlag != gridTransform->InverseFlag)
834 {
835 this->InverseFlag = gridTransform->InverseFlag;
836 this->Modified();
837 }
838 }
839
840 //------------------------------------------------------------------------------
InternalUpdate()841 void vtkBSplineTransform::InternalUpdate()
842 {
843 vtkImageData* grid = this->GetCoefficientData();
844 this->GridPointer = nullptr;
845
846 if (grid == nullptr)
847 {
848 return;
849 }
850
851 vtkAlgorithm* inputAlgorithm = this->ConnectionHolder->GetInputAlgorithm(0, 0);
852 inputAlgorithm->Update();
853
854 // In case output changed.
855 grid = this->GetCoefficientData();
856
857 if (grid->GetNumberOfScalarComponents() != 3)
858 {
859 vtkErrorMacro(<< "TransformPoint: displacement grid must have 3 components");
860 return;
861 }
862
863 // get the correct spline calculation function according to the grid type
864 switch (grid->GetScalarType())
865 {
866 case VTK_FLOAT:
867 this->CalculateSpline = &(vtkBSplineTransformFunction<float>::Cubic);
868 break;
869 case VTK_DOUBLE:
870 this->CalculateSpline = &(vtkBSplineTransformFunction<double>::Cubic);
871 break;
872 default:
873 this->CalculateSpline = nullptr;
874 vtkErrorMacro("InternalUpdate: grid type must be float or double");
875 break;
876 }
877
878 this->GridPointer = grid->GetScalarPointer();
879 grid->GetSpacing(this->GridSpacing);
880 grid->GetOrigin(this->GridOrigin);
881 grid->GetExtent(this->GridExtent);
882 grid->GetIncrements(this->GridIncrements);
883 }
884
885 //------------------------------------------------------------------------------
MakeTransform()886 vtkAbstractTransform* vtkBSplineTransform::MakeTransform()
887 {
888 return vtkBSplineTransform::New();
889 }
890
891 //------------------------------------------------------------------------------
SetCoefficientConnection(vtkAlgorithmOutput * output)892 void vtkBSplineTransform::SetCoefficientConnection(vtkAlgorithmOutput* output)
893 {
894 this->ConnectionHolder->SetInputConnection(output);
895 }
896
897 //------------------------------------------------------------------------------
SetCoefficientData(vtkImageData * grid)898 void vtkBSplineTransform::SetCoefficientData(vtkImageData* grid)
899 {
900 vtkTrivialProducer* tp = vtkTrivialProducer::New();
901 tp->SetOutput(grid);
902 this->SetCoefficientConnection(tp->GetOutputPort());
903 tp->Delete();
904 }
905
906 //------------------------------------------------------------------------------
GetCoefficientData()907 vtkImageData* vtkBSplineTransform::GetCoefficientData()
908 {
909 return vtkImageData::SafeDownCast(this->ConnectionHolder->GetInputDataObject(0, 0));
910 }
911