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