1 //============================================================================
2 // Copyright (c) Kitware, Inc.
3 // All rights reserved.
4 // See LICENSE.txt for details.
5 // This software is distributed WITHOUT ANY WARRANTY; without even
6 // the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
7 // PURPOSE. See the above copyright notice for more information.
8 //
9 // Copyright 2015 Sandia Corporation.
10 // Copyright 2015 UT-Battelle, LLC.
11 // Copyright 2015 Los Alamos National Security.
12 //
13 // Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
14 // the U.S. Government retains certain rights in this software.
15 //
16 // Under the terms of Contract DE-AC52-06NA25396 with Los Alamos National
17 // Laboratory (LANL), the U.S. Government retains certain rights in
18 // this software.
19 //============================================================================
20
21 #include "vtkmlib/Storage.h"
22 #include "vtkmCellSetExplicit.h"
23 #include "vtkmConnectivityExec.h"
24
25 #include <vtkm/cont/ArrayHandleImplicit.h>
26 #include <vtkm/cont/internal/ReverseConnectivityBuilder.h>
27 #include <vtkm/worklet/WorkletMapField.h>
28 #include <vtkm/worklet/DispatcherMapField.h>
29
30 #include <utility>
31
32 namespace
33 {
34
35 // Converts [0, rconnSize) to [0, connSize), skipping cell length entries.
36 template <typename Device>
37 struct ExplicitRConnToConn
38 {
39 using OffsetsArray = vtkm::cont::ArrayHandle<vtkm::Id, tovtkm::vtkAOSArrayContainerTag>;
40 using OffsetsPortal = decltype(std::declval<OffsetsArray>().PrepareForInput(Device()));
41
42 // Functor that modifies the offsets array so we can compute point id indices
43 // Output is:
44 // modOffset[i] = offsets[i] - i
45 struct OffsetsModifier
46 {
47 OffsetsPortal Offsets;
48
49 VTKM_SUPPRESS_EXEC_WARNINGS
50 VTKM_EXEC_CONT
OffsetsModifier__anon99f76a4f0111::ExplicitRConnToConn::OffsetsModifier51 OffsetsModifier(const OffsetsPortal& offsets = OffsetsPortal{})
52 : Offsets(offsets)
53 {
54 }
55
56 VTKM_EXEC
operator ()__anon99f76a4f0111::ExplicitRConnToConn::OffsetsModifier57 vtkm::Id operator()(vtkm::Id inIdx) const
58 {
59 return this->Offsets.Get(inIdx) - inIdx;
60 }
61 };
62
63 using ModOffsetsArray = vtkm::cont::ArrayHandleImplicit<OffsetsModifier>;
64 using ModOffsetsPortal = decltype(std::declval<ModOffsetsArray>().PrepareForInput(Device()));
65
66 VTKM_CONT
ExplicitRConnToConn__anon99f76a4f0111::ExplicitRConnToConn67 ExplicitRConnToConn(const ModOffsetsPortal& offsets)
68 : Offsets(offsets)
69 {
70 }
71
72 VTKM_EXEC
operator ()__anon99f76a4f0111::ExplicitRConnToConn73 vtkm::Id operator()(vtkm::Id rConnIdx) const
74 {
75 // Compute the connectivity array index (skipping cell length entries)
76 // The number of cell length entries can be found by taking the index of
77 // the upper bound of inIdx in Offsets and adding it to inIdx.
78 //
79 // Example:
80 // Conn: | 3 X X X | 4 X X X X | 3 X X X | 2 X X |
81 // Idx: | 0 1 2 3 | 4 5 6 7 8 | 9 10 11 12 | 13 14 15 |
82 // InIdx: 0 1 2 3 4 5 6 | 7 8 9 10 11
83 //
84 // ModOffset[i] = Offsets[i] - i:
85 // Offsets: 0 4 9 13 (16)
86 // ModOffsets: 0 3 7 10 (12)
87 //
88 // Define UB(x) to return the index of the upper bound of x in ModOffsets,
89 // the i'th point index's location in Conn is computed as:
90 // OutId = UB(InIdx) + InIdx
91 //
92 // This gives us the expected out indices:
93 // InIdx: 0 1 2 3 4 5 6 7 8 9 10 11
94 // UB(InIdx): 1 1 1 2 2 2 2 3 3 3 4 4
95 // OutIdx: 1 2 3 5 6 7 8 10 11 12 14 15
96 const vtkm::Id uBIdx = this->UpperBoundIdx(rConnIdx);
97 const vtkm::Id connIdx = rConnIdx + uBIdx;
98 return connIdx;
99 }
100
101 private:
102
103 ModOffsetsPortal Offsets;
104
105 VTKM_EXEC
UpperBoundIdx__anon99f76a4f0111::ExplicitRConnToConn106 vtkm::Id UpperBoundIdx(vtkm::Id inIdx) const
107 {
108 vtkm::Id first = 0;
109 vtkm::Id length = this->Offsets.GetNumberOfValues();
110
111 while (length > 0)
112 {
113 vtkm::Id half = length / 2;
114 vtkm::Id pos = first + half;
115 vtkm::Id val = this->Offsets.Get(pos);
116 if (val <= inIdx)
117 {
118 first = pos + 1;
119 length -= half + 1;
120 }
121 else
122 {
123 length = half;
124 }
125 }
126
127 return first;
128 }
129 };
130
131 // Converts a connectivity index to a cell id:
132 template <typename Device>
133 struct ExplicitCellIdCalc
134 {
135 using OffsetsArray = vtkm::cont::ArrayHandle<vtkm::Id, tovtkm::vtkAOSArrayContainerTag>;
136 using OffsetsPortal = decltype(std::declval<OffsetsArray>().PrepareForInput(Device()));
137
138 vtkm::Id ConnSize;
139 OffsetsPortal Offsets;
140
141 VTKM_CONT
ExplicitCellIdCalc__anon99f76a4f0111::ExplicitCellIdCalc142 ExplicitCellIdCalc(vtkm::Id connSize, const OffsetsPortal& offsets)
143 : ConnSize(connSize)
144 , Offsets(offsets)
145 {
146 }
147
148 // Computes the cellid of the connectivity index i.
149 //
150 // For a mixed-cell connectivity, the offset table is used to compute
151 // the cell id.
152 //
153 // Example:
154 // Conn: | 3 X X X | 4 X X X X | 3 X X X | 2 X X |
155 // Idx: | 1 2 3 | 5 6 7 8 | 10 11 12 | 14 15 |
156 //
157 // Offsets: 0 4 9 13
158 // ModOffsets: 4 9 13 16
159 //
160 // Computing the index of the lower bound in ModOffsets for each Idx gives
161 // the expected cell id values:
162 // CellId: | 0 0 0 | 1 1 1 1 | 2 2 2 | 3 3 |
163 VTKM_EXEC
operator ()__anon99f76a4f0111::ExplicitCellIdCalc164 vtkm::Id operator()(vtkm::Id i) const
165 {
166 return this->LowerBound(i);
167 }
168
169 private:
170 /// Returns the i+1 offset, or the full size of the connectivity if at end.
171 VTKM_EXEC
GetModifiedOffset__anon99f76a4f0111::ExplicitCellIdCalc172 vtkm::Id GetModifiedOffset(vtkm::Id i) const
173 {
174 ++i;
175 return (i >= this->Offsets.GetNumberOfValues()) ? this->ConnSize
176 : this->Offsets.Get(i);
177 }
178
179 VTKM_EXEC
LowerBound__anon99f76a4f0111::ExplicitCellIdCalc180 vtkm::Id LowerBound(vtkm::Id inVal) const
181 {
182 vtkm::Id first = 0;
183 vtkm::Id length = this->Offsets.GetNumberOfValues();
184
185 while (length > 0)
186 {
187 vtkm::Id half = length / 2;
188 vtkm::Id pos = first + half;
189 vtkm::Id val = this->GetModifiedOffset(pos);
190 if (val < inVal)
191 {
192 first = pos + 1;
193 length -= half + 1;
194 }
195 else
196 {
197 length = half;
198 }
199 }
200
201 return first;
202
203 }
204 };
205
206 } // end anon namespace
207
208 namespace vtkm {
209 namespace cont {
210
211 //------------------------------------------------------------------------------
Fill(vtkm::Id numberOfPoints,const vtkm::cont::ArrayHandle<vtkm::UInt8,tovtkm::vtkAOSArrayContainerTag> & cellTypes,const vtkm::cont::ArrayHandle<vtkm::Id,tovtkm::vtkCellArrayContainerTag> & connectivity,const vtkm::cont::ArrayHandle<vtkm::Id,tovtkm::vtkAOSArrayContainerTag> & offsets)212 void vtkmCellSetExplicitAOS::Fill(
213 vtkm::Id numberOfPoints,
214 const vtkm::cont::ArrayHandle<vtkm::UInt8, tovtkm::vtkAOSArrayContainerTag>&
215 cellTypes,
216 const vtkm::cont::ArrayHandle<vtkm::Id, tovtkm::vtkCellArrayContainerTag>&
217 connectivity,
218 const vtkm::cont::ArrayHandle<vtkm::Id, tovtkm::vtkAOSArrayContainerTag>&
219 offsets)
220 {
221 this->Shapes = cellTypes;
222 this->Connectivity = connectivity;
223 this->IndexOffsets = offsets;
224 this->NumberOfPoints = numberOfPoints;
225 }
226
227 //------------------------------------------------------------------------------
PrintSummary(std::ostream & out) const228 void vtkmCellSetExplicitAOS::PrintSummary(std::ostream& out) const
229 {
230 out << " vtkmCellSetExplicitAOS: " << this->Name << std::endl;
231 out << " Shapes: " << std::endl;
232 vtkm::cont::printSummary_ArrayHandle(this->Shapes, out);
233 out << " Connectivity: " << std::endl;
234 vtkm::cont::printSummary_ArrayHandle(this->Connectivity, out);
235 out << " IndexOffsets: " << std::endl;
236 vtkm::cont::printSummary_ArrayHandle(this->IndexOffsets, out);
237 }
238
239 //------------------------------------------------------------------------------
240 template <typename Device>
241 typename vtkm::exec::ConnectivityVTKAOS<Device>
PrepareForInput(Device,vtkm::TopologyElementTagPoint,vtkm::TopologyElementTagCell) const242 vtkmCellSetExplicitAOS::PrepareForInput(Device,
243 vtkm::TopologyElementTagPoint,
244 vtkm::TopologyElementTagCell) const
245 {
246 return vtkm::exec::ConnectivityVTKAOS<Device>(
247 this->Shapes.PrepareForInput(Device()),
248 this->Connectivity.PrepareForInput(Device()),
249 this->IndexOffsets.PrepareForInput(Device()));
250 }
251
252 //------------------------------------------------------------------------------
253 template <typename Device>
254 typename vtkm::exec::ReverseConnectivityVTK<Device>
PrepareForInput(Device,vtkm::TopologyElementTagCell,vtkm::TopologyElementTagPoint) const255 vtkmCellSetExplicitAOS::PrepareForInput(Device,
256 vtkm::TopologyElementTagCell,
257 vtkm::TopologyElementTagPoint) const
258 {
259 //One of the biggest questions when computing the reverse connectivity
260 //is how are we going to layout the results.
261 //We have two options:
262 // 1. The layout mirrors that of the point->cell where the connectivity array
263 // is VTK with the counts interlaced inside the array
264 // 2. We go with a VTK-m approach where we keep a separate array.
265 //
266 //While #1 has the strength of being easily mapped to VTK, we are going with
267 //#2 as it easier to construct
268 if(!this->ReverseConnectivityBuilt)
269 {
270 const vtkm::Id numberOfPoints = this->GetNumberOfPoints();
271 const vtkm::Id connectivityLength = this->Connectivity.GetNumberOfValues();
272 const vtkm::Id rconnSize = connectivityLength - this->IndexOffsets.GetNumberOfValues();
273
274 auto offsetsPortal = this->IndexOffsets.PrepareForInput(Device());
275 typename ExplicitRConnToConn<Device>::OffsetsModifier offsetModifier{offsetsPortal};
276 auto modOffsets = vtkm::cont::make_ArrayHandleImplicit(offsetModifier,
277 this->IndexOffsets.GetNumberOfValues());
278
279 const ExplicitRConnToConn<Device> rconnToConnCalc{modOffsets.PrepareForInput(Device())};
280 const ExplicitCellIdCalc<Device> cellIdCalc{this->Connectivity.GetNumberOfValues(),
281 this->IndexOffsets.PrepareForInput(Device())};
282
283 vtkm::cont::internal::ReverseConnectivityBuilder builder;
284
285 builder.Run(this->Connectivity,
286 this->RConn,
287 this->RNumIndices,
288 this->RIndexOffsets,
289 rconnToConnCalc,
290 cellIdCalc,
291 numberOfPoints,
292 rconnSize,
293 Device{});
294
295 this->NumberOfPoints = this->RIndexOffsets.GetNumberOfValues();
296 this->ReverseConnectivityBuilt = true;
297 }
298
299 //no need to have a reverse shapes array, as everything has the shape type
300 //of vertex
301 return vtkm::exec::ReverseConnectivityVTK<Device>(
302 this->RConn.PrepareForInput(Device()),
303 this->RNumIndices.PrepareForInput(Device()),
304 this->RIndexOffsets.PrepareForInput(Device()));
305 }
306
307 // template methods we want to compile only once
308 template VTKACCELERATORSVTKM_EXPORT
309 vtkm::exec::ConnectivityVTKAOS<vtkm::cont::DeviceAdapterTagSerial>
310 vtkmCellSetExplicitAOS::PrepareForInput(vtkm::cont::DeviceAdapterTagSerial,
311 vtkm::TopologyElementTagPoint, vtkm::TopologyElementTagCell) const;
312
313 template VTKACCELERATORSVTKM_EXPORT
314 vtkm::exec::ReverseConnectivityVTK<vtkm::cont::DeviceAdapterTagSerial>
315 vtkmCellSetExplicitAOS::PrepareForInput(vtkm::cont::DeviceAdapterTagSerial,
316 vtkm::TopologyElementTagCell, vtkm::TopologyElementTagPoint) const;
317
318 #ifdef VTKM_ENABLE_TBB
319 template VTKACCELERATORSVTKM_EXPORT
320 vtkm::exec::ConnectivityVTKAOS<vtkm::cont::DeviceAdapterTagTBB>
321 vtkmCellSetExplicitAOS::PrepareForInput(vtkm::cont::DeviceAdapterTagTBB,
322 vtkm::TopologyElementTagPoint, vtkm::TopologyElementTagCell) const;
323
324 template VTKACCELERATORSVTKM_EXPORT
325 vtkm::exec::ReverseConnectivityVTK<vtkm::cont::DeviceAdapterTagTBB>
326 vtkmCellSetExplicitAOS::PrepareForInput(vtkm::cont::DeviceAdapterTagTBB,
327 vtkm::TopologyElementTagCell, vtkm::TopologyElementTagPoint) const;
328 #endif
329
330 #ifdef VTKM_ENABLE_OPENMP
331 template VTKACCELERATORSVTKM_EXPORT
332 vtkm::exec::ConnectivityVTKAOS<vtkm::cont::DeviceAdapterTagOpenMP>
333 vtkmCellSetExplicitAOS::PrepareForInput(vtkm::cont::DeviceAdapterTagOpenMP,
334 vtkm::TopologyElementTagPoint, vtkm::TopologyElementTagCell) const;
335
336 template VTKACCELERATORSVTKM_EXPORT
337 vtkm::exec::ReverseConnectivityVTK<vtkm::cont::DeviceAdapterTagOpenMP>
338 vtkmCellSetExplicitAOS::PrepareForInput(vtkm::cont::DeviceAdapterTagOpenMP,
339 vtkm::TopologyElementTagCell, vtkm::TopologyElementTagPoint) const;
340 #endif
341
342 }
343 }
344