1 /*=========================================================================
2
3 Program: Visualization Toolkit
4 Module: vtkBiQuadraticQuad.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
16 // Thanks to Soeren Gebbert who developed this class and
17 // integrated it into VTK 5.0.
18
19 #include "vtkBiQuadraticQuad.h"
20
21 #include "vtkDoubleArray.h"
22 #include "vtkMath.h"
23 #include "vtkObjectFactory.h"
24 #include "vtkPointData.h"
25 #include "vtkPoints.h"
26 #include "vtkQuad.h"
27 #include "vtkQuadraticEdge.h"
28
29 vtkStandardNewMacro(vtkBiQuadraticQuad);
30
31 //------------------------------------------------------------------------------
32 // Construct the quad with nine points.
vtkBiQuadraticQuad()33 vtkBiQuadraticQuad::vtkBiQuadraticQuad()
34 {
35 this->Edge = vtkQuadraticEdge::New();
36 this->Quad = vtkQuad::New();
37 this->Points->SetNumberOfPoints(9);
38 this->PointIds->SetNumberOfIds(9);
39 for (int i = 0; i < 9; i++)
40 {
41 this->Points->SetPoint(i, 0.0, 0.0, 0.0);
42 this->PointIds->SetId(i, 0);
43 }
44 this->Scalars = vtkDoubleArray::New();
45 this->Scalars->SetNumberOfTuples(4);
46 }
47
48 //------------------------------------------------------------------------------
~vtkBiQuadraticQuad()49 vtkBiQuadraticQuad::~vtkBiQuadraticQuad()
50 {
51 this->Edge->Delete();
52 this->Quad->Delete();
53
54 this->Scalars->Delete();
55 }
56
57 //------------------------------------------------------------------------------
GetEdge(int edgeId)58 vtkCell* vtkBiQuadraticQuad::GetEdge(int edgeId)
59 {
60 edgeId = (edgeId < 0 ? 0 : (edgeId > 3 ? 3 : edgeId));
61 int p = (edgeId + 1) % 4;
62
63 // load point id's
64 this->Edge->PointIds->SetId(0, this->PointIds->GetId(edgeId));
65 this->Edge->PointIds->SetId(1, this->PointIds->GetId(p));
66 this->Edge->PointIds->SetId(2, this->PointIds->GetId(edgeId + 4));
67
68 // load coordinates
69 this->Edge->Points->SetPoint(0, this->Points->GetPoint(edgeId));
70 this->Edge->Points->SetPoint(1, this->Points->GetPoint(p));
71 this->Edge->Points->SetPoint(2, this->Points->GetPoint(edgeId + 4));
72
73 return this->Edge;
74 }
75
76 //------------------------------------------------------------------------------
77 static int LinearQuads[4][4] = { { 0, 4, 8, 7 }, { 4, 1, 5, 8 }, { 8, 5, 2, 6 }, { 7, 8, 6, 3 } };
78
79 //------------------------------------------------------------------------------
EvaluatePosition(const double x[3],double * closestPoint,int & subId,double pcoords[3],double & minDist2,double * weights)80 int vtkBiQuadraticQuad::EvaluatePosition(const double x[3], double* closestPoint, int& subId,
81 double pcoords[3], double& minDist2, double* weights)
82 {
83 double pc[3], dist2;
84 int ignoreId, i, returnStatus = 0, status;
85 double tempWeights[4];
86 double closest[3];
87
88 // four linear quads are used
89 for (minDist2 = VTK_DOUBLE_MAX, i = 0; i < 4; i++)
90 {
91 this->Quad->Points->SetPoint(0, this->Points->GetPoint(LinearQuads[i][0]));
92 this->Quad->Points->SetPoint(1, this->Points->GetPoint(LinearQuads[i][1]));
93 this->Quad->Points->SetPoint(2, this->Points->GetPoint(LinearQuads[i][2]));
94 this->Quad->Points->SetPoint(3, this->Points->GetPoint(LinearQuads[i][3]));
95
96 status = this->Quad->EvaluatePosition(x, closest, ignoreId, pc, dist2, tempWeights);
97 if (status != -1 && dist2 < minDist2)
98 {
99 returnStatus = status;
100 minDist2 = dist2;
101 subId = i;
102 pcoords[0] = pc[0];
103 pcoords[1] = pc[1];
104 }
105 }
106
107 // adjust parametric coordinates
108 if (returnStatus != -1)
109 {
110 if (subId == 0)
111 {
112 pcoords[0] /= 2.0;
113 pcoords[1] /= 2.0;
114 }
115 else if (subId == 1)
116 {
117 pcoords[0] = 0.5 + (pcoords[0] / 2.0);
118 pcoords[1] /= 2.0;
119 }
120 else if (subId == 2)
121 {
122 pcoords[0] = 0.5 + (pcoords[0] / 2.0);
123 pcoords[1] = 0.5 + (pcoords[1] / 2.0);
124 }
125 else
126 {
127 pcoords[0] /= 2.0;
128 pcoords[1] = 0.5 + (pcoords[1] / 2.0);
129 }
130 pcoords[2] = 0.0;
131 if (closestPoint != nullptr)
132 {
133 // Compute both closestPoint and weights
134 this->EvaluateLocation(subId, pcoords, closestPoint, weights);
135 }
136 else
137 {
138 // Compute weights only
139 vtkBiQuadraticQuad::InterpolationFunctionsPrivate(pcoords, weights);
140 }
141 }
142
143 return returnStatus;
144 }
145
146 //------------------------------------------------------------------------------
EvaluateLocation(int & vtkNotUsed (subId),const double pcoords[3],double x[3],double * weights)147 void vtkBiQuadraticQuad::EvaluateLocation(
148 int& vtkNotUsed(subId), const double pcoords[3], double x[3], double* weights)
149 {
150 int i, j;
151 double pt[3];
152
153 vtkBiQuadraticQuad::InterpolationFunctionsPrivate(pcoords, weights);
154
155 x[0] = x[1] = x[2] = 0.0;
156 for (i = 0; i < 9; i++)
157 {
158 this->Points->GetPoint(i, pt);
159 for (j = 0; j < 3; j++)
160 {
161 x[j] += pt[j] * weights[i];
162 }
163 }
164 }
165
166 //------------------------------------------------------------------------------
CellBoundary(int subId,const double pcoords[3],vtkIdList * pts)167 int vtkBiQuadraticQuad::CellBoundary(int subId, const double pcoords[3], vtkIdList* pts)
168 {
169 return this->Quad->CellBoundary(subId, pcoords, pts);
170 }
171
172 //------------------------------------------------------------------------------
Contour(double value,vtkDataArray * cellScalars,vtkIncrementalPointLocator * locator,vtkCellArray * verts,vtkCellArray * lines,vtkCellArray * polys,vtkPointData * inPd,vtkPointData * outPd,vtkCellData * inCd,vtkIdType cellId,vtkCellData * outCd)173 void vtkBiQuadraticQuad::Contour(double value, vtkDataArray* cellScalars,
174 vtkIncrementalPointLocator* locator, vtkCellArray* verts, vtkCellArray* lines,
175 vtkCellArray* polys, vtkPointData* inPd, vtkPointData* outPd, vtkCellData* inCd, vtkIdType cellId,
176 vtkCellData* outCd)
177 {
178 // contour each linear quad separately
179 for (int i = 0; i < 4; i++)
180 {
181 for (int j = 0; j < 4; j++)
182 {
183 this->Quad->Points->SetPoint(j, this->Points->GetPoint(LinearQuads[i][j]));
184 this->Quad->PointIds->SetId(j, this->PointIds->GetId(LinearQuads[i][j]));
185 this->Scalars->SetValue(j, cellScalars->GetTuple1(LinearQuads[i][j]));
186 }
187
188 this->Quad->Contour(
189 value, this->Scalars, locator, verts, lines, polys, inPd, outPd, inCd, cellId, outCd);
190 }
191 }
192
193 //------------------------------------------------------------------------------
194 // Clip this quadratic quad using scalar value provided. Like contouring,
195 // except that it cuts the quad to produce other quads and triangles.
Clip(double value,vtkDataArray * cellScalars,vtkIncrementalPointLocator * locator,vtkCellArray * polys,vtkPointData * inPd,vtkPointData * outPd,vtkCellData * inCd,vtkIdType cellId,vtkCellData * outCd,int insideOut)196 void vtkBiQuadraticQuad::Clip(double value, vtkDataArray* cellScalars,
197 vtkIncrementalPointLocator* locator, vtkCellArray* polys, vtkPointData* inPd, vtkPointData* outPd,
198 vtkCellData* inCd, vtkIdType cellId, vtkCellData* outCd, int insideOut)
199 {
200 // contour each linear quad separately
201 for (int i = 0; i < 4; i++)
202 {
203 for (int j = 0; j < 4; j++) // for each of the four vertices of the linear quad
204 {
205 this->Quad->Points->SetPoint(j, this->Points->GetPoint(LinearQuads[i][j]));
206 this->Quad->PointIds->SetId(j, this->PointIds->GetId(LinearQuads[i][j]));
207 this->Scalars->SetValue(j, cellScalars->GetTuple1(LinearQuads[i][j]));
208 }
209
210 this->Quad->Clip(
211 value, this->Scalars, locator, polys, inPd, outPd, inCd, cellId, outCd, insideOut);
212 }
213 }
214
215 //------------------------------------------------------------------------------
216 // Line-line intersection. Intersection has to occur within [0,1] parametric
217 // coordinates and with specified tolerance.
IntersectWithLine(const double * p1,const double * p2,double tol,double & t,double * x,double * pcoords,int & subId)218 int vtkBiQuadraticQuad::IntersectWithLine(
219 const double* p1, const double* p2, double tol, double& t, double* x, double* pcoords, int& subId)
220 {
221 int subTest, i;
222 subId = 0;
223
224 // intersect the four linear quads
225 for (i = 0; i < 4; i++)
226 {
227 this->Quad->Points->SetPoint(0, this->Points->GetPoint(LinearQuads[i][0]));
228 this->Quad->Points->SetPoint(1, this->Points->GetPoint(LinearQuads[i][1]));
229 this->Quad->Points->SetPoint(2, this->Points->GetPoint(LinearQuads[i][2]));
230 this->Quad->Points->SetPoint(3, this->Points->GetPoint(LinearQuads[i][3]));
231
232 if (this->Quad->IntersectWithLine(p1, p2, tol, t, x, pcoords, subTest))
233 {
234 return 1;
235 }
236 }
237
238 return 0;
239 }
240
241 //------------------------------------------------------------------------------
Triangulate(int vtkNotUsed (index),vtkIdList * ptIds,vtkPoints * pts)242 int vtkBiQuadraticQuad::Triangulate(int vtkNotUsed(index), vtkIdList* ptIds, vtkPoints* pts)
243 {
244 pts->SetNumberOfPoints(24);
245 ptIds->SetNumberOfIds(24);
246
247 // First the corner vertices
248 ptIds->SetId(0, this->PointIds->GetId(0));
249 ptIds->SetId(1, this->PointIds->GetId(4));
250 ptIds->SetId(2, this->PointIds->GetId(7));
251 pts->SetPoint(0, this->Points->GetPoint(0));
252 pts->SetPoint(1, this->Points->GetPoint(4));
253 pts->SetPoint(2, this->Points->GetPoint(7));
254
255 ptIds->SetId(3, this->PointIds->GetId(4));
256 ptIds->SetId(4, this->PointIds->GetId(1));
257 ptIds->SetId(5, this->PointIds->GetId(5));
258 pts->SetPoint(3, this->Points->GetPoint(4));
259 pts->SetPoint(4, this->Points->GetPoint(1));
260 pts->SetPoint(5, this->Points->GetPoint(5));
261
262 ptIds->SetId(6, this->PointIds->GetId(5));
263 ptIds->SetId(7, this->PointIds->GetId(2));
264 ptIds->SetId(8, this->PointIds->GetId(6));
265 pts->SetPoint(6, this->Points->GetPoint(5));
266 pts->SetPoint(7, this->Points->GetPoint(2));
267 pts->SetPoint(8, this->Points->GetPoint(6));
268
269 ptIds->SetId(9, this->PointIds->GetId(6));
270 ptIds->SetId(10, this->PointIds->GetId(3));
271 ptIds->SetId(11, this->PointIds->GetId(7));
272 pts->SetPoint(9, this->Points->GetPoint(6));
273 pts->SetPoint(10, this->Points->GetPoint(3));
274 pts->SetPoint(11, this->Points->GetPoint(7));
275
276 // Now the triangles in the middle
277 ptIds->SetId(12, this->PointIds->GetId(4));
278 ptIds->SetId(13, this->PointIds->GetId(8));
279 ptIds->SetId(14, this->PointIds->GetId(7));
280 pts->SetPoint(12, this->Points->GetPoint(4));
281 pts->SetPoint(13, this->Points->GetPoint(8));
282 pts->SetPoint(14, this->Points->GetPoint(7));
283
284 ptIds->SetId(15, this->PointIds->GetId(4));
285 ptIds->SetId(16, this->PointIds->GetId(5));
286 ptIds->SetId(17, this->PointIds->GetId(8));
287 pts->SetPoint(15, this->Points->GetPoint(4));
288 pts->SetPoint(16, this->Points->GetPoint(5));
289 pts->SetPoint(17, this->Points->GetPoint(8));
290
291 ptIds->SetId(18, this->PointIds->GetId(5));
292 ptIds->SetId(19, this->PointIds->GetId(6));
293 ptIds->SetId(20, this->PointIds->GetId(8));
294 pts->SetPoint(18, this->Points->GetPoint(5));
295 pts->SetPoint(19, this->Points->GetPoint(6));
296 pts->SetPoint(20, this->Points->GetPoint(8));
297
298 ptIds->SetId(21, this->PointIds->GetId(6));
299 ptIds->SetId(22, this->PointIds->GetId(7));
300 ptIds->SetId(23, this->PointIds->GetId(8));
301 pts->SetPoint(21, this->Points->GetPoint(6));
302 pts->SetPoint(22, this->Points->GetPoint(7));
303 pts->SetPoint(23, this->Points->GetPoint(8));
304
305 return 1;
306 }
307
308 //------------------------------------------------------------------------------
Derivatives(int vtkNotUsed (subId),const double pcoords[3],const double * values,int dim,double * derivs)309 void vtkBiQuadraticQuad::Derivatives(
310 int vtkNotUsed(subId), const double pcoords[3], const double* values, int dim, double* derivs)
311 {
312 double sum[2], p[3], weights[9];
313 double functionDerivs[18];
314 double *J[3], J0[3], J1[3], J2[3];
315 double *JI[3], JI0[3], JI1[3], JI2[3];
316
317 vtkBiQuadraticQuad::InterpolationFunctionsPrivate(pcoords, weights);
318 vtkBiQuadraticQuad::InterpolationDerivsPrivate(pcoords, functionDerivs);
319
320 // Compute transposed Jacobian and inverse Jacobian
321 J[0] = J0;
322 J[1] = J1;
323 J[2] = J2;
324 JI[0] = JI0;
325 JI[1] = JI1;
326 JI[2] = JI2;
327 for (int k = 0; k < 3; k++)
328 {
329 J0[k] = J1[k] = 0.0;
330 }
331
332 for (int i = 0; i < 9; i++)
333 {
334 this->Points->GetPoint(i, p);
335 for (int j = 0; j < 2; j++)
336 {
337 for (int k = 0; k < 3; k++)
338 {
339 J[j][k] += p[k] * functionDerivs[j * 9 + i];
340 }
341 }
342 }
343
344 // Compute third row vector in transposed Jacobian and normalize it, so that Jacobian determinant
345 // stays the same.
346 vtkMath::Cross(J0, J1, J2);
347 if (vtkMath::Normalize(J2) == 0.0 || !vtkMath::InvertMatrix(J, JI, 3)) // degenerate
348 {
349 for (int j = 0; j < dim; j++)
350 {
351 for (int i = 0; i < 3; i++)
352 {
353 derivs[j * dim + i] = 0.0;
354 }
355 }
356 return;
357 }
358
359 // Loop over "dim" derivative values. For each set of values,
360 // compute derivatives
361 // in local system and then transform into modelling system.
362 // First compute derivatives in local x'-y' coordinate system
363 for (int j = 0; j < dim; j++)
364 {
365 sum[0] = sum[1] = 0.0;
366 for (int i = 0; i < 9; i++) // loop over interp. function derivatives
367 {
368 sum[0] += functionDerivs[i] * values[dim * i + j];
369 sum[1] += functionDerivs[9 + i] * values[dim * i + j];
370 }
371 // dBydx = sum[0]*JI[0][0] + sum[1]*JI[0][1];
372 // dBydy = sum[0]*JI[1][0] + sum[1]*JI[1][1];
373
374 // Transform into global system (dot product with global axes)
375 derivs[3 * j] = sum[0] * JI[0][0] + sum[1] * JI[0][1];
376 derivs[3 * j + 1] = sum[0] * JI[1][0] + sum[1] * JI[1][1];
377 derivs[3 * j + 2] = sum[0] * JI[2][0] + sum[1] * JI[2][1];
378 }
379 }
380
381 //------------------------------------------------------------------------------
382 // Compute interpolation functions. The first four nodes are the corner
383 // vertices; the others are mid-edge nodes, the last one is the mid-center
384 // node.
InterpolationFunctionsPrivate(const double pcoords[3],double weights[9])385 void vtkBiQuadraticQuad::InterpolationFunctionsPrivate(const double pcoords[3], double weights[9])
386 {
387 // Normally these coordinates are named r and s, but I chose x and y,
388 // because you can easily mark and paste these functions to the
389 // gnuplot splot function. :D
390 double x = pcoords[0];
391 double y = pcoords[1];
392
393 // midedge weights
394 weights[0] = 4.0 * (1.0 - x) * (x - 0.5) * (1.0 - y) * (y - 0.5);
395 weights[1] = -4.0 * (x) * (x - 0.5) * (1.0 - y) * (y - 0.5);
396 weights[2] = 4.0 * (x) * (x - 0.5) * (y) * (y - 0.5);
397 weights[3] = -4.0 * (1.0 - x) * (x - 0.5) * (y) * (y - 0.5);
398 // corner weights
399 weights[4] = 8.0 * (x) * (1.0 - x) * (1.0 - y) * (0.5 - y);
400 weights[5] = -8.0 * (x) * (0.5 - x) * (1.0 - y) * (y);
401 weights[6] = -8.0 * (x) * (1.0 - x) * (y) * (0.5 - y);
402 weights[7] = 8.0 * (1.0 - x) * (0.5 - x) * (1.0 - y) * (y);
403 // surface center weight
404 weights[8] = 16.0 * (x) * (1.0 - x) * (1.0 - y) * (y);
405 }
406
407 //------------------------------------------------------------------------------
408 // Derivatives in parametric space.
InterpolationDerivsPrivate(const double pcoords[3],double derivs[18])409 void vtkBiQuadraticQuad::InterpolationDerivsPrivate(const double pcoords[3], double derivs[18])
410 {
411 // Coordinate conversion
412 double x = pcoords[0];
413 double y = pcoords[1];
414
415 // Derivatives in the x-direction
416 // edge
417 derivs[0] = 4.0 * (1.5 - 2.0 * x) * (1.0 - y) * (y - 0.5);
418 derivs[1] = -4.0 * (2.0 * x - 0.5) * (1.0 - y) * (y - 0.5);
419 derivs[2] = 4.0 * (2.0 * x - 0.5) * (y) * (y - 0.5);
420 derivs[3] = -4.0 * (1.5 - 2.0 * x) * (y) * (y - 0.5);
421 // midedge
422 derivs[4] = 8.0 * (1.0 - 2.0 * x) * (1.0 - y) * (0.5 - y);
423 derivs[5] = -8.0 * (0.5 - 2.0 * x) * (1.0 - y) * (y);
424 derivs[6] = -8.0 * (1.0 - 2.0 * x) * (y) * (0.5 - y);
425 derivs[7] = 8.0 * (2.0 * x - 1.5) * (1.0 - y) * (y);
426 // center
427 derivs[8] = 16.0 * (1.0 - 2.0 * x) * (1.0 - y) * (y);
428
429 // Derivatives in the y-direction
430 // edge
431 derivs[9] = 4.0 * (1.0 - x) * (x - 0.5) * (1.5 - 2.0 * y);
432 derivs[10] = -4.0 * (x) * (x - 0.5) * (1.5 - 2.0 * y);
433 derivs[11] = 4.0 * (x) * (x - 0.5) * (2.0 * y - 0.5);
434 derivs[12] = -4.0 * (1.0 - x) * (x - 0.5) * (2.0 * y - 0.5);
435 // midedge
436 derivs[13] = 8.0 * (x) * (1.0 - x) * (2.0 * y - 1.5);
437 derivs[14] = -8.0 * (x) * (0.5 - x) * (1.0 - 2.0 * y);
438 derivs[15] = -8.0 * (x) * (1.0 - x) * (0.5 - 2.0 * y);
439 derivs[16] = 8.0 * (1.0 - x) * (0.5 - x) * (1.0 - 2.0 * y);
440 // center
441 derivs[17] = 16.0 * (x) * (1.0 - x) * (1.0 - 2.0 * y);
442 }
443
444 //------------------------------------------------------------------------------
445 static double vtkQQuadCellPCoords[27] = { 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 1.0, 1.0, 0.0, 0.0, 1.0,
446 0.0, 0.5, 0.0, 0.0, 1.0, 0.5, 0.0, 0.5, 1.0, 0.0, 0.0, 0.5, 0.0, 0.5, 0.5, 0.0 };
447
GetParametricCoords()448 double* vtkBiQuadraticQuad::GetParametricCoords()
449 {
450 return vtkQQuadCellPCoords;
451 }
452
453 //------------------------------------------------------------------------------
PrintSelf(ostream & os,vtkIndent indent)454 void vtkBiQuadraticQuad::PrintSelf(ostream& os, vtkIndent indent)
455 {
456 this->Superclass::PrintSelf(os, indent);
457
458 os << indent << "Edge:\n";
459 this->Edge->PrintSelf(os, indent.GetNextIndent());
460 os << indent << "Quad:\n";
461 this->Quad->PrintSelf(os, indent.GetNextIndent());
462 os << indent << "Scalars:\n";
463 this->Scalars->PrintSelf(os, indent.GetNextIndent());
464 }
465