1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
|
// SPDX-FileCopyrightText: Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
// SPDX-License-Identifier: BSD-3-Clause
#ifndef vtkCellGridSidesCache_h
#define vtkCellGridSidesCache_h
#include "vtkObject.h"
#include "vtkCommonDataModelModule.h" // For export macro.
#include "vtkHashCombiner.h" // For templated AddSide() method.
#include "vtkStringToken.h" // For API.
#include <functional>
#include <map>
#include <set>
#include <unordered_map>
#include <vector>
VTK_ABI_NAMESPACE_BEGIN
class vtkIdTypeArray;
/**
* @class vtkCellGridSidesCache
* @brief Hold a map from hash-ids (representing sides of cells of multiple types)
* to details on the cells that claim the corresponding side.
*
* This class is created by filters such as vtkCellGridComputeSides and
* vtkCellGridExtractCrinkle; it can be reused by the same filter and
* any others that process the same input (since it is stored in a
* cache available to them).
*/
class VTKCOMMONDATAMODEL_EXPORT vtkCellGridSidesCache : public vtkObject
{
public:
static vtkCellGridSidesCache* New();
vtkTypeMacro(vtkCellGridSidesCache, vtkObject);
void PrintSelf(ostream& os, vtkIndent indent) override;
/// Records held by a hash-entry that represent the side of one cell.
///
/// All instances of Side owned by a single hash-entry have the same
/// hash but correspond to distinct sides of different cells.
struct Side
{
/// The type of cell whose side is hashed.
vtkStringToken CellType;
/// The shape of the side being hashed.
vtkStringToken SideShape;
/// The degree of freedom starting the hash sequence.
vtkIdType DOF;
/// The ID of the side being hashed.
int SideId;
/// Compare side-hashes to allow set insertion.
bool operator<(const Side& other) const
{
return (this->CellType < other.CellType) ||
(this->CellType == other.CellType &&
((this->DOF < other.DOF) || (this->DOF == other.DOF && this->SideId < other.SideId)));
}
};
/// Each hash entry corresponds to one or more sides of one or more cells.
struct Entry
{
std::set<Side> Sides;
};
/// Return the map of hashed side information.
std::unordered_map<std::size_t, Entry>& GetHashes() { return this->Hashes; }
/// Compute the hash of a side (but do not insert a side into the map).
template <typename C, typename T = typename C::value_type>
std::size_t HashSide(vtkStringToken shape, const C& conn)
{
std::size_t ss = 0;
std::size_t NN = conn.size();
if (NN == 0)
{
return 0;
}
T smin = conn[0];
for (std::size_t jj = 1; jj < NN; ++jj)
{
if (conn[jj] < smin)
{
smin = conn[jj];
ss = jj;
}
}
bool forward = conn[(ss + 1) % NN] > conn[(ss + NN - 1) % NN];
std::size_t hashedValue = std::hash<std::size_t>{}(NN);
vtkHashCombiner()(hashedValue, shape.GetId());
// std::cout << "Hash(" << (forward ? "F" : "R") << ")";
if (forward)
{
for (std::size_t ii = 0; ii < NN; ++ii)
{
std::size_t hashedToken = std::hash<T>{}(conn[(ss + ii) % NN]);
vtkHashCombiner()(hashedValue, hashedToken);
// std::cout << " " << conn[(ss + ii) % NN];
}
}
else // backward
{
for (std::size_t ii = 0; ii < NN; ++ii)
{
std::size_t hashedToken = std::hash<T>{}(conn[(ss + NN - ii) % NN]);
// hashedValue = hashedValue ^ (hashedToken << (ii + 1));
vtkHashCombiner()(hashedValue, hashedToken);
// std::cout << " " << conn[(ss + NN - ii) % NN];
}
}
// std::cout << " = " << std::hex << hashedValue << std::dec << "\n";
return hashedValue;
}
/// Add a \a side with the given \a shape and connectivity to the request's state.
///
/// The \a shape, \a conn size, and \a conn entries are hashed together into a key
/// which is mapped to a set of all the matching sides.
/// The \a cellType and \a cell ID are also stored with each matching side; these
/// are used during Finalize() to generate the output map-of-maps returned
/// by GetSides() so that the sides are reported by cell type, cell ID, and then side ID.
///
/// Note that the \a conn entries are hashed in a particular canonical order so
/// that the same hash is generated for sides with point IDs that have been shifted
/// and/or reversed.
/// The hash always starts at the smallest entry of \a conn and goes
/// in the direction that has the largest next entry.
/// Examples:
/// (3, 2, 0, 1) → starts at index 2 (0) and hashes backwards: (0, 2, 3, 1)
/// (4, 5, 6, 7) → starts at index 0 (4) and hashes backwards: (4, 7, 6, 5)
/// (7, 3, 6, 2) → starts at index 3 (2) and hashes forwards: (2, 7, 3, 6)
//
/// By storing the \a cellType, we avoid requiring a global-to-local cell numbering
/// in vtkCellGrid instances (as vtkPolyData incurs) which may hold multiple types of cells.
//@{
template <typename C, typename T = typename C::value_type>
void AddSide(
vtkStringToken cellType, vtkIdType cell, int side, vtkStringToken shape, const C& conn)
{
auto hashedValue = this->HashSide(shape, conn);
this->Hashes[hashedValue].Sides.insert(Side{ cellType, shape, cell, side });
}
//@}
/// Empty the cache of all hashes.
void Initialize();
protected:
vtkCellGridSidesCache() = default;
~vtkCellGridSidesCache() override = default;
std::unordered_map<std::size_t, Entry> Hashes;
private:
vtkCellGridSidesCache(const vtkCellGridSidesCache&) = delete;
void operator=(const vtkCellGridSidesCache&) = delete;
};
VTK_ABI_NAMESPACE_END
#endif // vtkCellGridSidesCache_h
|
