1 //============================================================================
2 //  Copyright (c) Kitware, Inc.
3 //  All rights reserved.
4 //  See LICENSE.txt for details.
5 //
6 //  This software is distributed WITHOUT ANY WARRANTY; without even
7 //  the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
8 //  PURPOSE.  See the above copyright notice for more information.
9 //============================================================================
10 #ifndef vtk_m_cont_internal_ReverseConnectivityBuilder_h
11 #define vtk_m_cont_internal_ReverseConnectivityBuilder_h
12 
13 #include <vtkm/cont/Algorithm.h>
14 #include <vtkm/cont/ArrayHandle.h>
15 #include <vtkm/cont/ArrayHandleCast.h>
16 #include <vtkm/cont/ArrayHandleConstant.h>
17 
18 #include <vtkm/cont/AtomicArray.h>
19 #include <vtkm/exec/FunctorBase.h>
20 
21 #include <utility>
22 
23 namespace vtkm
24 {
25 namespace cont
26 {
27 namespace internal
28 {
29 
30 namespace rcb
31 {
32 
33 template <typename AtomicHistogram, typename ConnInPortal, typename RConnToConnIdxCalc>
34 struct BuildHistogram : public vtkm::exec::FunctorBase
35 {
36   AtomicHistogram Histo;
37   ConnInPortal Conn;
38   RConnToConnIdxCalc IdxCalc;
39 
40   VTKM_CONT
BuildHistogramBuildHistogram41   BuildHistogram(const AtomicHistogram& histo,
42                  const ConnInPortal& conn,
43                  const RConnToConnIdxCalc& idxCalc)
44     : Histo(histo)
45     , Conn(conn)
46     , IdxCalc(idxCalc)
47   {
48   }
49 
50   VTKM_EXEC
operatorBuildHistogram51   void operator()(vtkm::Id rconnIdx) const
52   {
53     // Compute the connectivity array index (skipping cell length entries)
54     const vtkm::Id connIdx = this->IdxCalc(rconnIdx);
55     const vtkm::Id ptId = this->Conn.Get(connIdx);
56     this->Histo.Add(ptId, 1);
57   }
58 };
59 
60 template <typename AtomicHistogram,
61           typename ConnInPortal,
62           typename ROffsetInPortal,
63           typename RConnOutPortal,
64           typename RConnToConnIdxCalc,
65           typename ConnIdxToCellIdxCalc>
66 struct GenerateRConn : public vtkm::exec::FunctorBase
67 {
68   AtomicHistogram Histo;
69   ConnInPortal Conn;
70   ROffsetInPortal ROffsets;
71   RConnOutPortal RConn;
72   RConnToConnIdxCalc IdxCalc;
73   ConnIdxToCellIdxCalc CellIdCalc;
74 
75   VTKM_CONT
GenerateRConnGenerateRConn76   GenerateRConn(const AtomicHistogram& histo,
77                 const ConnInPortal& conn,
78                 const ROffsetInPortal& rOffsets,
79                 const RConnOutPortal& rconn,
80                 const RConnToConnIdxCalc& idxCalc,
81                 const ConnIdxToCellIdxCalc& cellIdCalc)
82     : Histo(histo)
83     , Conn(conn)
84     , ROffsets(rOffsets)
85     , RConn(rconn)
86     , IdxCalc(idxCalc)
87     , CellIdCalc(cellIdCalc)
88   {
89   }
90 
91   VTKM_EXEC
operatorGenerateRConn92   void operator()(vtkm::Id inputIdx) const
93   {
94     // Compute the connectivity array index (skipping cell length entries)
95     const vtkm::Id connIdx = this->IdxCalc(inputIdx);
96     const vtkm::Id ptId = this->Conn.Get(connIdx);
97 
98     // Compute the cell id:
99     const vtkm::Id cellId = this->CellIdCalc(connIdx);
100 
101     // Find the base offset for this point id:
102     const vtkm::Id baseOffset = this->ROffsets.Get(ptId);
103 
104     // Find the next unused index for this point id
105     const vtkm::Id nextAvailable = this->Histo.Add(ptId, 1);
106 
107     // Update the final location in the RConn table with the cellId
108     const vtkm::Id rconnIdx = baseOffset + nextAvailable;
109     this->RConn.Set(rconnIdx, cellId);
110   }
111 };
112 }
113 /// Takes a connectivity array handle (conn) and constructs a reverse
114 /// connectivity table suitable for use by VTK-m (rconn).
115 ///
116 /// This code is generalized for use by VTK and VTK-m.
117 ///
118 /// The Run(...) method is the main entry point. The template parameters are:
119 /// @param RConnToConnIdxCalc defines `vtkm::Id operator()(vtkm::Id in) const`
120 /// which computes the index of the in'th point id in conn. This is necessary
121 /// for VTK-style cell arrays that need to skip the cell length entries. In
122 /// vtk-m, this is a no-op passthrough.
123 /// @param ConnIdxToCellIdxCalc Functor that computes the cell id from an
124 /// index into conn.
125 /// @param ConnTag is the StorageTag for the input connectivity array.
126 ///
127 /// See usages in vtkmCellSetExplicit and vtkmCellSetSingleType for examples.
128 class ReverseConnectivityBuilder
129 {
130 public:
131   VTKM_CONT
132   template <typename ConnArray,
133             typename RConnArray,
134             typename ROffsetsArray,
135             typename RConnToConnIdxCalc,
136             typename ConnIdxToCellIdxCalc>
Run(const ConnArray & conn,RConnArray & rConn,ROffsetsArray & rOffsets,const RConnToConnIdxCalc & rConnToConnCalc,const ConnIdxToCellIdxCalc & cellIdCalc,vtkm::Id numberOfPoints,vtkm::Id rConnSize,vtkm::cont::DeviceAdapterId device)137   inline void Run(const ConnArray& conn,
138                   RConnArray& rConn,
139                   ROffsetsArray& rOffsets,
140                   const RConnToConnIdxCalc& rConnToConnCalc,
141                   const ConnIdxToCellIdxCalc& cellIdCalc,
142                   vtkm::Id numberOfPoints,
143                   vtkm::Id rConnSize,
144                   vtkm::cont::DeviceAdapterId device)
145   {
146     vtkm::cont::Token connToken;
147     auto connPortal = conn.PrepareForInput(device, connToken);
148     auto zeros = vtkm::cont::make_ArrayHandleConstant(vtkm::IdComponent{ 0 }, numberOfPoints);
149 
150     // Compute RConn offsets by atomically building a histogram and doing an
151     // extended scan.
152     //
153     // Example:
154     // (in)  Conn:  | 3  0  1  2  |  3  0  1  3  |  3  0  3  4  |  3  3  4  5  |
155     // (out) RNumIndices:  3  2  1  3  2  1
156     // (out) RIdxOffsets:  0  3  5  6  9 11 12
157     vtkm::cont::ArrayHandle<vtkm::IdComponent> rNumIndices;
158     { // allocate and zero the numIndices array:
159       vtkm::cont::Algorithm::Copy(device, zeros, rNumIndices);
160     }
161 
162     { // Build histogram:
163       vtkm::cont::AtomicArray<vtkm::IdComponent> atomicCounter{ rNumIndices };
164       vtkm::cont::Token token;
165       auto ac = atomicCounter.PrepareForExecution(device, token);
166       using BuildHisto =
167         rcb::BuildHistogram<decltype(ac), decltype(connPortal), RConnToConnIdxCalc>;
168       BuildHisto histoGen{ ac, connPortal, rConnToConnCalc };
169 
170       vtkm::cont::Algorithm::Schedule(device, histoGen, rConnSize);
171     }
172 
173     { // Compute offsets:
174       vtkm::cont::Algorithm::ScanExtended(
175         device, vtkm::cont::make_ArrayHandleCast<vtkm::Id>(rNumIndices), rOffsets);
176     }
177 
178     { // Reset the numIndices array to 0's:
179       vtkm::cont::Algorithm::Copy(device, zeros, rNumIndices);
180     }
181 
182     // Fill the connectivity table:
183     // 1) Lookup each point idx base offset.
184     // 2) Use the atomic histogram to find the next available slot for this
185     //    pt id in RConn.
186     // 3) Compute the cell id from the connectivity index
187     // 4) Update RConn[nextSlot] = cellId
188     //
189     // Example:
190     // (in)    Conn:  | 3  0  1  2  |  3  0  1  3  |  3  0  3  4  |  3  3  4  5  |
191     // (inout) RNumIndices:  0  0  0  0  0  0  (Initial)
192     // (inout) RNumIndices:  3  2  1  3  2  1  (Final)
193     // (in)    RIdxOffsets:  0  3  5  6  9  11
194     // (out)   RConn: | 0  1  2  |  0  1  |  0  |  1  2  3  |  2  3  |  3  |
195     {
196       vtkm::cont::AtomicArray<vtkm::IdComponent> atomicCounter{ rNumIndices };
197       vtkm::cont::Token token;
198       auto ac = atomicCounter.PrepareForExecution(device, token);
199       auto rOffsetPortal = rOffsets.PrepareForInput(device, token);
200       auto rConnPortal = rConn.PrepareForOutput(rConnSize, device, token);
201 
202       using GenRConnT = rcb::GenerateRConn<decltype(ac),
203                                            decltype(connPortal),
204                                            decltype(rOffsetPortal),
205                                            decltype(rConnPortal),
206                                            RConnToConnIdxCalc,
207                                            ConnIdxToCellIdxCalc>;
208       GenRConnT rConnGen{ ac, connPortal, rOffsetPortal, rConnPortal, rConnToConnCalc, cellIdCalc };
209 
210       vtkm::cont::Algorithm::Schedule(device, rConnGen, rConnSize);
211     }
212   }
213 };
214 }
215 }
216 } // end namespace vtkm::cont::internal
217 
218 #endif // ReverseConnectivityBuilder_h
219