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