1 /*=========================================================================
2
3 Program: Visualization Toolkit
4 Module: vtkQuadraticLinearQuad.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 "vtkQuadraticLinearQuad.h"
20
21 #include "vtkDoubleArray.h"
22 #include "vtkLine.h"
23 #include "vtkMath.h"
24 #include "vtkObjectFactory.h"
25 #include "vtkPoints.h"
26 #include "vtkQuad.h"
27 #include "vtkQuadraticEdge.h"
28
29 vtkStandardNewMacro(vtkQuadraticLinearQuad);
30
31 //------------------------------------------------------------------------------
32 // Construct the quadratic linear quad with six points.
vtkQuadraticLinearQuad()33 vtkQuadraticLinearQuad::vtkQuadraticLinearQuad()
34 {
35 this->Edge = vtkQuadraticEdge::New();
36 this->LinEdge = vtkLine::New();
37 this->Quad = vtkQuad::New();
38 this->Scalars = vtkDoubleArray::New();
39 this->Scalars->SetNumberOfTuples(4); // vertices of a linear quad
40 this->Points->SetNumberOfPoints(6);
41 this->PointIds->SetNumberOfIds(6);
42 for (int i = 0; i < 6; i++)
43 {
44 this->Points->SetPoint(i, 0.0, 0.0, 0.0);
45 this->PointIds->SetId(i, 0);
46 }
47 }
48
49 //------------------------------------------------------------------------------
~vtkQuadraticLinearQuad()50 vtkQuadraticLinearQuad::~vtkQuadraticLinearQuad()
51 {
52 this->Edge->Delete();
53 this->LinEdge->Delete();
54 this->Quad->Delete();
55 this->Scalars->Delete();
56 }
57
58 //------------------------------------------------------------------------------
59 static int LinearQuads[2][4] = {
60 { 0, 4, 5, 3 },
61 { 4, 1, 2, 5 },
62 };
63
64 static int LinearQuadEdges[4][3] = {
65 { 0, 1, 4 },
66 { 1, 2, -1 },
67 { 2, 3, 5 },
68 { 3, 0, -1 },
69 };
70
71 //------------------------------------------------------------------------------
GetEdgeArray(vtkIdType edgeId)72 int* vtkQuadraticLinearQuad::GetEdgeArray(vtkIdType edgeId)
73 {
74 return LinearQuadEdges[edgeId];
75 }
76
77 //------------------------------------------------------------------------------
GetEdge(int edgeId)78 vtkCell* vtkQuadraticLinearQuad::GetEdge(int edgeId)
79 {
80 edgeId = (edgeId < 0 ? 0 : (edgeId > 3 ? 3 : edgeId));
81
82 // We have 2 linear edges
83 if (edgeId == 1 || edgeId == 3)
84 {
85 this->LinEdge->PointIds->SetId(0, this->PointIds->GetId(LinearQuadEdges[edgeId][0]));
86 this->LinEdge->PointIds->SetId(1, this->PointIds->GetId(LinearQuadEdges[edgeId][1]));
87
88 this->LinEdge->Points->SetPoint(0, this->Points->GetPoint(LinearQuadEdges[edgeId][0]));
89 this->LinEdge->Points->SetPoint(1, this->Points->GetPoint(LinearQuadEdges[edgeId][1]));
90
91 return this->LinEdge;
92 }
93 // and two quadratic edges
94 else // (edgeId == 0 || edgeId == 2)
95 {
96 this->Edge->PointIds->SetId(0, this->PointIds->GetId(LinearQuadEdges[edgeId][0]));
97 this->Edge->PointIds->SetId(1, this->PointIds->GetId(LinearQuadEdges[edgeId][1]));
98 this->Edge->PointIds->SetId(2, this->PointIds->GetId(LinearQuadEdges[edgeId][2]));
99
100 this->Edge->Points->SetPoint(0, this->Points->GetPoint(LinearQuadEdges[edgeId][0]));
101 this->Edge->Points->SetPoint(1, this->Points->GetPoint(LinearQuadEdges[edgeId][1]));
102 this->Edge->Points->SetPoint(2, this->Points->GetPoint(LinearQuadEdges[edgeId][2]));
103
104 return this->Edge;
105 }
106 }
107
108 //------------------------------------------------------------------------------
EvaluatePosition(const double x[3],double * closestPoint,int & subId,double pcoords[3],double & minDist2,double * weights)109 int vtkQuadraticLinearQuad::EvaluatePosition(const double x[3], double* closestPoint, int& subId,
110 double pcoords[3], double& minDist2, double* weights)
111 {
112 double pc[3], dist2;
113 int ignoreId, i, returnStatus = 0, status;
114 double tempWeights[4];
115 double closest[3];
116
117 // two linear quads are used
118 for (minDist2 = VTK_DOUBLE_MAX, i = 0; i < 2; i++)
119 {
120 this->Quad->Points->SetPoint(0, this->Points->GetPoint(LinearQuads[i][0]));
121 this->Quad->Points->SetPoint(1, this->Points->GetPoint(LinearQuads[i][1]));
122 this->Quad->Points->SetPoint(2, this->Points->GetPoint(LinearQuads[i][2]));
123 this->Quad->Points->SetPoint(3, this->Points->GetPoint(LinearQuads[i][3]));
124
125 status = this->Quad->EvaluatePosition(x, closest, ignoreId, pc, dist2, tempWeights);
126 if (status != -1 && dist2 < minDist2)
127 {
128 returnStatus = status;
129 minDist2 = dist2;
130 subId = i;
131 pcoords[0] = pc[0];
132 pcoords[1] = pc[1];
133 }
134 }
135
136 // adjust parametric coordinates
137 if (returnStatus != -1)
138 {
139 if (subId == 0)
140 {
141 pcoords[0] /= 2.0;
142 }
143 else if (subId == 1)
144 {
145 pcoords[0] = 0.5 + (pcoords[0] / 2.0);
146 }
147 pcoords[2] = 0.0;
148 if (closestPoint != nullptr)
149 {
150 // Compute both closestPoint and weights
151 this->EvaluateLocation(subId, pcoords, closestPoint, weights);
152 }
153 else
154 {
155 // Compute weights only
156 vtkQuadraticLinearQuad::InterpolationFunctions(pcoords, weights);
157 }
158 }
159
160 return returnStatus;
161 }
162
163 //------------------------------------------------------------------------------
EvaluateLocation(int & vtkNotUsed (subId),const double pcoords[3],double x[3],double * weights)164 void vtkQuadraticLinearQuad::EvaluateLocation(
165 int& vtkNotUsed(subId), const double pcoords[3], double x[3], double* weights)
166 {
167 int i, j;
168 double pt[3];
169
170 vtkQuadraticLinearQuad::InterpolationFunctions(pcoords, weights);
171
172 x[0] = x[1] = x[2] = 0.0;
173 for (i = 0; i < 6; i++)
174 {
175 this->Points->GetPoint(i, pt);
176 for (j = 0; j < 3; j++)
177 {
178 x[j] += pt[j] * weights[i];
179 }
180 }
181 }
182
183 //------------------------------------------------------------------------------
CellBoundary(int subId,const double pcoords[3],vtkIdList * pts)184 int vtkQuadraticLinearQuad::CellBoundary(int subId, const double pcoords[3], vtkIdList* pts)
185 {
186 return this->Quad->CellBoundary(subId, pcoords, pts);
187 }
188
189 //------------------------------------------------------------------------------
Contour(double value,vtkDataArray * cellScalars,vtkIncrementalPointLocator * locator,vtkCellArray * verts,vtkCellArray * lines,vtkCellArray * polys,vtkPointData * inPd,vtkPointData * outPd,vtkCellData * inCd,vtkIdType cellId,vtkCellData * outCd)190 void vtkQuadraticLinearQuad::Contour(double value, vtkDataArray* cellScalars,
191 vtkIncrementalPointLocator* locator, vtkCellArray* verts, vtkCellArray* lines,
192 vtkCellArray* polys, vtkPointData* inPd, vtkPointData* outPd, vtkCellData* inCd, vtkIdType cellId,
193 vtkCellData* outCd)
194 {
195 for (int i = 0; i < 2; i++)
196 {
197 for (int j = 0; j < 4; j++)
198 {
199 this->Quad->Points->SetPoint(j, this->Points->GetPoint(LinearQuads[i][j]));
200 this->Quad->PointIds->SetId(j, this->PointIds->GetId(LinearQuads[i][j]));
201 this->Scalars->SetValue(j, cellScalars->GetTuple1(LinearQuads[i][j]));
202 }
203 this->Quad->Contour(
204 value, this->Scalars, locator, verts, lines, polys, inPd, outPd, inCd, cellId, outCd);
205 }
206 }
207
208 //------------------------------------------------------------------------------
209 // Clip this quadratic quad using scalar value provided. Like contouring,
210 // 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)211 void vtkQuadraticLinearQuad::Clip(double value, vtkDataArray* cellScalars,
212 vtkIncrementalPointLocator* locator, vtkCellArray* polys, vtkPointData* inPd, vtkPointData* outPd,
213 vtkCellData* inCd, vtkIdType cellId, vtkCellData* outCd, int insideOut)
214 {
215 for (int i = 0; i < 2; i++)
216 {
217 for (int j = 0; j < 4; j++) // for each of the four vertices of the linear quad
218 {
219 this->Quad->Points->SetPoint(j, this->Points->GetPoint(LinearQuads[i][j]));
220 this->Quad->PointIds->SetId(j, this->PointIds->GetId(LinearQuads[i][j]));
221 this->Scalars->SetTuple(j, cellScalars->GetTuple(LinearQuads[i][j]));
222 }
223 this->Quad->Clip(
224 value, this->Scalars, locator, polys, inPd, outPd, inCd, cellId, outCd, insideOut);
225 }
226 }
227
228 //------------------------------------------------------------------------------
229 // Line-line intersection. Intersection has to occur within [0,1] parametric
230 // coordinates and with specified tolerance.
IntersectWithLine(const double * p1,const double * p2,double tol,double & t,double * x,double * pcoords,int & subId)231 int vtkQuadraticLinearQuad::IntersectWithLine(
232 const double* p1, const double* p2, double tol, double& t, double* x, double* pcoords, int& subId)
233 {
234 int subTest, i;
235 subId = 0;
236
237 // intersect the two linear quads
238 for (i = 0; i < 2; i++)
239 {
240 this->Quad->Points->SetPoint(0, this->Points->GetPoint(LinearQuads[i][0]));
241 this->Quad->Points->SetPoint(1, this->Points->GetPoint(LinearQuads[i][1]));
242 this->Quad->Points->SetPoint(2, this->Points->GetPoint(LinearQuads[i][2]));
243 this->Quad->Points->SetPoint(3, this->Points->GetPoint(LinearQuads[i][3]));
244
245 if (this->Quad->IntersectWithLine(p1, p2, tol, t, x, pcoords, subTest))
246 {
247 return 1;
248 }
249 }
250
251 return 0;
252 }
253
254 //------------------------------------------------------------------------------
Triangulate(int vtkNotUsed (index),vtkIdList * ptIds,vtkPoints * pts)255 int vtkQuadraticLinearQuad::Triangulate(int vtkNotUsed(index), vtkIdList* ptIds, vtkPoints* pts)
256 {
257 pts->Reset();
258 ptIds->Reset();
259
260 // Create four linear triangles:
261 // Choose the triangulation that minimizes the edge length
262 // across the cell.
263 double x0[3], x1[3], x2[3], x3[3], x4[3], x5[3];
264 this->Points->GetPoint(0, x0);
265 this->Points->GetPoint(1, x1);
266 this->Points->GetPoint(2, x2);
267 this->Points->GetPoint(3, x3);
268 this->Points->GetPoint(4, x4);
269 this->Points->GetPoint(5, x5);
270
271 if (vtkMath::Distance2BetweenPoints(x0, x5) <= vtkMath::Distance2BetweenPoints(x3, x4))
272 {
273 ptIds->InsertId(0, this->PointIds->GetId(0));
274 ptIds->InsertId(1, this->PointIds->GetId(4));
275 ptIds->InsertId(2, this->PointIds->GetId(5));
276 pts->InsertPoint(0, this->Points->GetPoint(0));
277 pts->InsertPoint(1, this->Points->GetPoint(4));
278 pts->InsertPoint(2, this->Points->GetPoint(5));
279
280 ptIds->InsertId(3, this->PointIds->GetId(0));
281 ptIds->InsertId(4, this->PointIds->GetId(5));
282 ptIds->InsertId(5, this->PointIds->GetId(3));
283 pts->InsertPoint(3, this->Points->GetPoint(0));
284 pts->InsertPoint(4, this->Points->GetPoint(5));
285 pts->InsertPoint(5, this->Points->GetPoint(3));
286 }
287 else
288 {
289 ptIds->InsertId(0, this->PointIds->GetId(0));
290 ptIds->InsertId(1, this->PointIds->GetId(4));
291 ptIds->InsertId(2, this->PointIds->GetId(3));
292 pts->InsertPoint(0, this->Points->GetPoint(0));
293 pts->InsertPoint(1, this->Points->GetPoint(4));
294 pts->InsertPoint(2, this->Points->GetPoint(3));
295
296 ptIds->InsertId(3, this->PointIds->GetId(4));
297 ptIds->InsertId(4, this->PointIds->GetId(5));
298 ptIds->InsertId(5, this->PointIds->GetId(3));
299 pts->InsertPoint(3, this->Points->GetPoint(4));
300 pts->InsertPoint(4, this->Points->GetPoint(5));
301 pts->InsertPoint(5, this->Points->GetPoint(3));
302 }
303
304 if (vtkMath::Distance2BetweenPoints(x4, x2) <= vtkMath::Distance2BetweenPoints(x5, x1))
305 {
306 ptIds->InsertId(6, this->PointIds->GetId(4));
307 ptIds->InsertId(7, this->PointIds->GetId(1));
308 ptIds->InsertId(8, this->PointIds->GetId(2));
309 pts->InsertPoint(6, this->Points->GetPoint(4));
310 pts->InsertPoint(7, this->Points->GetPoint(1));
311 pts->InsertPoint(8, this->Points->GetPoint(2));
312
313 ptIds->InsertId(9, this->PointIds->GetId(4));
314 ptIds->InsertId(10, this->PointIds->GetId(2));
315 ptIds->InsertId(11, this->PointIds->GetId(5));
316 pts->InsertPoint(9, this->Points->GetPoint(4));
317 pts->InsertPoint(10, this->Points->GetPoint(2));
318 pts->InsertPoint(11, this->Points->GetPoint(5));
319 }
320 else
321 {
322 ptIds->InsertId(6, this->PointIds->GetId(4));
323 ptIds->InsertId(7, this->PointIds->GetId(1));
324 ptIds->InsertId(8, this->PointIds->GetId(5));
325 pts->InsertPoint(6, this->Points->GetPoint(4));
326 pts->InsertPoint(7, this->Points->GetPoint(1));
327 pts->InsertPoint(8, this->Points->GetPoint(5));
328
329 ptIds->InsertId(9, this->PointIds->GetId(1));
330 ptIds->InsertId(10, this->PointIds->GetId(2));
331 ptIds->InsertId(11, this->PointIds->GetId(5));
332 pts->InsertPoint(9, this->Points->GetPoint(1));
333 pts->InsertPoint(10, this->Points->GetPoint(2));
334 pts->InsertPoint(11, this->Points->GetPoint(5));
335 }
336
337 return 1;
338 }
339
340 //------------------------------------------------------------------------------
Derivatives(int vtkNotUsed (subId),const double pcoords[3],const double * values,int dim,double * derivs)341 void vtkQuadraticLinearQuad::Derivatives(
342 int vtkNotUsed(subId), const double pcoords[3], const double* values, int dim, double* derivs)
343 {
344 double x0[3], x1[3], x2[3], deltaX[3], weights[6];
345 int i, j;
346 double functionDerivs[12];
347
348 this->Points->GetPoint(0, x0);
349 this->Points->GetPoint(1, x1);
350 this->Points->GetPoint(2, x2);
351
352 vtkQuadraticLinearQuad::InterpolationFunctions(pcoords, weights);
353 vtkQuadraticLinearQuad::InterpolationDerivs(pcoords, functionDerivs);
354
355 for (i = 0; i < 3; i++)
356 {
357 deltaX[i] = x1[i] - x0[i] - x2[i];
358 }
359 for (i = 0; i < dim; i++)
360 {
361 for (j = 0; j < 3; j++)
362 {
363 if (deltaX[j] != 0)
364 {
365 derivs[3 * i + j] = (values[2 * i + 1] - values[2 * i]) / deltaX[j];
366 }
367 else
368 {
369 derivs[3 * i + j] = 0;
370 }
371 }
372 }
373 }
374
375 //------------------------------------------------------------------------------
376 // Compute interpolation functions. The first four nodes are the corner
377 // vertices; the others are mid-edge nodes.
InterpolationFunctions(const double pcoords[3],double weights[6])378 void vtkQuadraticLinearQuad::InterpolationFunctions(const double pcoords[3], double weights[6])
379 {
380 double x = pcoords[0];
381 double y = pcoords[1];
382
383 // corners
384 weights[0] = -1.0 * (2.0 * x - 1.0) * (x - 1.0) * (y - 1.0);
385 weights[1] = -1.0 * (2.0 * x - 1.0) * (x) * (y - 1.0);
386 weights[2] = (2.0 * x - 1.0) * (x) * (y);
387 weights[3] = (2.0 * x - 1.0) * (x - 1.0) * (y);
388
389 // Edge middle nodes
390 weights[4] = 4.0 * (x) * (1.0 - x) * (1.0 - y);
391 weights[5] = 4.0 * (x) * (1.0 - x) * (y);
392 }
393
394 //------------------------------------------------------------------------------
395 // Derivatives in parametric space.
InterpolationDerivs(const double pcoords[3],double derivs[12])396 void vtkQuadraticLinearQuad::InterpolationDerivs(const double pcoords[3], double derivs[12])
397 {
398 double x = pcoords[0];
399 double y = pcoords[1];
400
401 // Derivatives in the x-direction
402 // corners
403 derivs[0] = -1.0 * (4.0 * x - 3.0) * (y - 1.0);
404 derivs[1] = -1.0 * (4.0 * x - 1.0) * (y - 1.0);
405 derivs[2] = (4.0 * x - 1.0) * (y);
406 derivs[3] = (4.0 * x - 3.0) * (y);
407 // Edge middle nodes
408 derivs[4] = 4.0 * (1.0 - 2.0 * x) * (1.0 - y);
409 derivs[5] = 4.0 * (1.0 - 2.0 * x) * (y);
410
411 // Derivatives in the y-direction
412 // corners
413 derivs[6] = -1.0 * (2.0 * x - 1.0) * (x - 1.0);
414 derivs[7] = -1.0 * (2.0 * x - 1.0) * (x);
415 derivs[8] = (2.0 * x - 1.0) * (x);
416 derivs[9] = (2.0 * x - 1.0) * (x - 1.0);
417 // Edge middle nodes
418 derivs[10] = -4.0 * (x) * (1.0 - x);
419 derivs[11] = 4.0 * (x) * (1.0 - x);
420 }
421
422 //------------------------------------------------------------------------------
423 static double vtkQLinQuadCellPCoords[18] = {
424 0.0, 0.0, 0.0, //
425 1.0, 0.0, 0.0, //
426 1.0, 1.0, 0.0, //
427 0.0, 1.0, 0.0, //
428 0.5, 0.0, 0.0, //
429 0.5, 1.0, 0.0 //
430 };
431
GetParametricCoords()432 double* vtkQuadraticLinearQuad::GetParametricCoords()
433 {
434 return vtkQLinQuadCellPCoords;
435 }
436
437 //------------------------------------------------------------------------------
PrintSelf(ostream & os,vtkIndent indent)438 void vtkQuadraticLinearQuad::PrintSelf(ostream& os, vtkIndent indent)
439 {
440 this->Superclass::PrintSelf(os, indent);
441
442 os << indent << "Edge:\n";
443 this->Edge->PrintSelf(os, indent.GetNextIndent());
444 os << indent << "Quad:\n";
445 this->Quad->PrintSelf(os, indent.GetNextIndent());
446 os << indent << "Scalars:\n";
447 this->Scalars->PrintSelf(os, indent.GetNextIndent());
448 }
449