1 /*=========================================================================
2
3 Program: Visualization Toolkit
4 Module: vtkCellCenterDepthSort.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 /*
17 * Copyright 2003 Sandia Corporation.
18 * Under the terms of Contract DE-AC04-94AL85000, there is a non-exclusive
19 * license for use of this work by or on behalf of the
20 * U.S. Government. Redistribution and use in source and binary forms, with
21 * or without modification, are permitted provided that this Notice and any
22 * statement of authorship are reproduced on all copies.
23 */
24 #include "vtkCellCenterDepthSort.h"
25
26 #include "vtkCamera.h"
27 #include "vtkCell.h"
28 #include "vtkDataSet.h"
29 #include "vtkFloatArray.h"
30 #include "vtkIdTypeArray.h"
31 #include "vtkMath.h"
32 #include "vtkMatrix4x4.h"
33 #include "vtkObjectFactory.h"
34 #include "vtkSortDataArray.h"
35
36 #include <algorithm>
37 #include <stack>
38 #include <utility>
39
40 //------------------------------------------------------------------------------
41
42 typedef std::pair<vtkIdType, vtkIdType> vtkIdPair;
43
44 class vtkCellCenterDepthSortStack
45 {
46 public:
47 std::stack<vtkIdPair> Stack;
48 };
49
50 //------------------------------------------------------------------------------
51
52 vtkStandardNewMacro(vtkCellCenterDepthSort);
53
vtkCellCenterDepthSort()54 vtkCellCenterDepthSort::vtkCellCenterDepthSort()
55 {
56 this->SortedCells = vtkIdTypeArray::New();
57 this->SortedCells->SetNumberOfComponents(1);
58 this->SortedCellPartition = vtkIdTypeArray::New();
59 this->SortedCells->SetNumberOfComponents(1);
60
61 this->CellCenters = vtkFloatArray::New();
62 this->CellCenters->SetNumberOfComponents(3);
63 this->CellDepths = vtkFloatArray::New();
64 this->CellDepths->SetNumberOfComponents(1);
65 this->CellPartitionDepths = vtkFloatArray::New();
66 this->CellPartitionDepths->SetNumberOfComponents(1);
67
68 this->ToSort = new vtkCellCenterDepthSortStack;
69 }
70
~vtkCellCenterDepthSort()71 vtkCellCenterDepthSort::~vtkCellCenterDepthSort()
72 {
73 this->SortedCells->Delete();
74 this->SortedCellPartition->Delete();
75 this->CellCenters->Delete();
76 this->CellDepths->Delete();
77 this->CellPartitionDepths->Delete();
78
79 delete this->ToSort;
80 }
81
PrintSelf(ostream & os,vtkIndent indent)82 void vtkCellCenterDepthSort::PrintSelf(ostream& os, vtkIndent indent)
83 {
84 this->Superclass::PrintSelf(os, indent);
85 }
86
ComputeProjectionVector()87 float* vtkCellCenterDepthSort::ComputeProjectionVector()
88 {
89 vtkDebugMacro("ComputeProjectionVector");
90
91 if (this->Camera == nullptr)
92 {
93 vtkErrorMacro("Must set camera before sorting cells.");
94 static float v[3] = { 0.0, 0.0, 0.0 };
95 return v;
96 }
97
98 double focalPoint[4];
99 double position[4];
100
101 this->Camera->GetFocalPoint(focalPoint);
102 focalPoint[3] = 1.0;
103 this->Camera->GetPosition(position);
104 position[3] = 1.0;
105
106 this->InverseModelTransform->MultiplyPoint(focalPoint, focalPoint);
107 this->InverseModelTransform->MultiplyPoint(position, position);
108
109 static float vector[3];
110 if (this->Direction == vtkVisibilitySort::BACK_TO_FRONT)
111 {
112 // Sort back to front.
113 vector[0] = position[0] - focalPoint[0];
114 vector[1] = position[1] - focalPoint[1];
115 vector[2] = position[2] - focalPoint[2];
116 }
117 else
118 {
119 // Sort front to back.
120 vector[0] = focalPoint[0] - position[0];
121 vector[1] = focalPoint[1] - position[1];
122 vector[2] = focalPoint[2] - position[2];
123 }
124
125 vtkDebugMacro("Returning: " << vector[0] << ", " << vector[1] << ", " << vector[2]);
126
127 return vector;
128 }
129
ComputeCellCenters()130 void vtkCellCenterDepthSort::ComputeCellCenters()
131 {
132 vtkIdType numcells = this->Input->GetNumberOfCells();
133 this->CellCenters->SetNumberOfTuples(numcells);
134
135 float* center = this->CellCenters->GetPointer(0);
136 double dcenter[3];
137 double* weights = new double[this->Input->GetMaxCellSize()]; // Dummy array.
138
139 for (vtkIdType i = 0; i < numcells; i++)
140 {
141 vtkCell* cell = this->Input->GetCell(i);
142 double pcenter[3];
143 int subId;
144 subId = cell->GetParametricCenter(pcenter);
145 cell->EvaluateLocation(subId, pcenter, dcenter, weights);
146 center[0] = dcenter[0];
147 center[1] = dcenter[1];
148 center[2] = dcenter[2];
149 center += 3;
150 }
151
152 delete[] weights;
153 }
154
ComputeDepths()155 void vtkCellCenterDepthSort::ComputeDepths()
156 {
157 float* vector = this->ComputeProjectionVector();
158 vtkIdType numcells = this->Input->GetNumberOfCells();
159
160 float* center = this->CellCenters->GetPointer(0);
161 float* depth = this->CellDepths->GetPointer(0);
162 for (vtkIdType i = 0; i < numcells; i++)
163 {
164 *(depth++) = vtkMath::Dot(center, vector);
165 center += 3;
166 }
167 }
168
InitTraversal()169 void vtkCellCenterDepthSort::InitTraversal()
170 {
171 vtkDebugMacro("InitTraversal");
172
173 vtkIdType numcells = this->Input->GetNumberOfCells();
174
175 if ((this->LastSortTime < this->Input->GetMTime()) || (this->LastSortTime < this->MTime))
176 {
177 vtkDebugMacro("Building cell centers array.");
178
179 // Data may have changed. Recompute cell centers.
180 this->ComputeCellCenters();
181 this->CellDepths->SetNumberOfTuples(numcells);
182 this->SortedCells->SetNumberOfTuples(numcells);
183 }
184
185 vtkDebugMacro("Filling SortedCells to initial values.");
186 vtkIdType* id = this->SortedCells->GetPointer(0);
187 for (vtkIdType i = 0; i < numcells; i++)
188 {
189 *(id++) = i;
190 }
191
192 vtkDebugMacro("Calculating depths.");
193 this->ComputeDepths();
194
195 while (!this->ToSort->Stack.empty())
196 this->ToSort->Stack.pop();
197 this->ToSort->Stack.push(vtkIdPair(0, numcells));
198
199 this->LastSortTime.Modified();
200 }
201
GetNextCells()202 vtkIdTypeArray* vtkCellCenterDepthSort::GetNextCells()
203 {
204 if (this->ToSort->Stack.empty())
205 {
206 // Already sorted and returned everything.
207 return nullptr;
208 }
209
210 vtkIdType* cellIds = this->SortedCells->GetPointer(0);
211 float* cellDepths = this->CellDepths->GetPointer(0);
212 vtkIdPair partition;
213
214 partition = this->ToSort->Stack.top();
215 this->ToSort->Stack.pop();
216 while (partition.second - partition.first > this->MaxCellsReturned)
217 {
218 vtkIdType left = partition.first;
219 vtkIdType right = partition.second - 1;
220 float pivot = cellDepths[static_cast<vtkIdType>(vtkMath::Random(left, right))];
221 while (left <= right)
222 {
223 while ((left <= right) && (cellDepths[left] < pivot))
224 left++;
225 while ((left <= right) && (cellDepths[right] > pivot))
226 right--;
227
228 if (left > right)
229 break;
230
231 std::swap(cellIds[left], cellIds[right]);
232 std::swap(cellDepths[left], cellDepths[right]);
233
234 left++;
235 right--;
236 }
237
238 this->ToSort->Stack.push(vtkIdPair(left, partition.second));
239 partition.second = left;
240 }
241
242 if (partition.second <= partition.first)
243 {
244 // Got a partition of zero size. Just recurse to get the next one.
245 return this->GetNextCells();
246 }
247
248 vtkIdType firstcell = partition.first;
249 vtkIdType numcells = partition.second - partition.first;
250
251 this->SortedCellPartition->SetArray(cellIds + firstcell, numcells, 1);
252 this->SortedCellPartition->SetNumberOfTuples(numcells);
253 this->CellPartitionDepths->SetArray(cellDepths + firstcell, numcells, 1);
254 this->CellPartitionDepths->SetNumberOfTuples(numcells);
255
256 vtkSortDataArray::Sort(this->CellPartitionDepths, this->SortedCellPartition);
257 return this->SortedCellPartition;
258 }
259