1 // Copyright (c) 2017-2021, Lawrence Livermore National Security, LLC and
2 // other Axom Project Developers. See the top-level LICENSE file for details.
3 //
4 // SPDX-License-Identifier: (BSD-3-Clause)
5
6 #include "gtest/gtest.h"
7
8 #include "axom/spin/OctreeBase.hpp"
9
10 #include "axom/slic/interface/slic.hpp"
11
12 //------------------------------------------------------------------------------
TEST(spin_octree,topological_octree_parent_child)13 TEST(spin_octree, topological_octree_parent_child)
14 {
15 SLIC_INFO(
16 "*** This test exercises the parent/child relation in spin::OctreeBase");
17
18 static const int DIM = 2;
19 using CoordType = int;
20 using LeafNodeType = axom::spin::BlockData;
21
22 using OctreeType = axom::spin::OctreeBase<DIM, LeafNodeType>;
23 using GridPt = OctreeType::GridPt;
24 using BlockIndex = OctreeType::BlockIndex;
25 using OctreeChildIndexSet = BlockIndex::ChildIndexSet;
26
27 OctreeType octree;
28
29 BlockIndex rootBlock = octree.root();
30 EXPECT_EQ(rootBlock.pt(), GridPt());
31 EXPECT_EQ(rootBlock.level(), 0);
32
33 OctreeChildIndexSet childIndexSet;
34 int numChildren = childIndexSet.size();
35 for(int i = 0; i < numChildren; ++i)
36 {
37 // Root's children are at level one and have coordinates that are either
38 // zero or one
39 BlockIndex childBlock = octree.child(rootBlock, childIndexSet[i]);
40 EXPECT_EQ(childBlock.level(), 1);
41 EXPECT_EQ(childBlock.level(), rootBlock.childLevel());
42
43 int recombineIndex = 0;
44 for(int dim = 0; dim < DIM; ++dim)
45 {
46 CoordType coordVal = childBlock.pt()[dim];
47 EXPECT_TRUE(coordVal == 0 || coordVal == 1);
48
49 bool expBit = (childIndexSet[i] & 1 << dim) > 0;
50 EXPECT_EQ(coordVal, expBit ? 1 : 0);
51
52 recombineIndex += (coordVal << dim);
53 }
54 EXPECT_EQ(childIndexSet[i], recombineIndex);
55
56 // Parent of child is self
57 EXPECT_EQ(octree.parent(childBlock), rootBlock);
58 }
59 }
60
61 //------------------------------------------------------------------------------
TEST(spin_octree,topological_octree_refine)62 TEST(spin_octree, topological_octree_refine)
63 {
64 SLIC_INFO("*** This test exercises the block refinement in spin::OctreeBase"
65 << "\nSpecifically, that refining the root block adds "
66 << "all its children to the octree.");
67
68 static const int DIM = 3;
69 using LeafNodeType = axom::spin::BlockData;
70
71 using OctreeType = axom::spin::OctreeBase<DIM, LeafNodeType>;
72 using BlockIndex = OctreeType::BlockIndex;
73
74 OctreeType octree;
75
76 BlockIndex rootBlock = octree.root();
77
78 EXPECT_TRUE(octree.hasBlock(rootBlock));
79 EXPECT_TRUE(octree.isLeaf(rootBlock));
80 EXPECT_FALSE(octree.isInternal(rootBlock));
81
82 int numChildren = BlockIndex::numChildren();
83 for(int i = 0; i < numChildren; ++i)
84 {
85 EXPECT_FALSE(octree.hasBlock(octree.child(rootBlock, i)));
86 }
87
88 octree.refineLeaf(rootBlock);
89
90 EXPECT_TRUE(octree.hasBlock(rootBlock));
91 EXPECT_FALSE(octree.isLeaf(rootBlock));
92 EXPECT_TRUE(octree.isInternal(rootBlock));
93
94 for(int i = 0; i < numChildren; ++i)
95 {
96 EXPECT_TRUE(octree.hasBlock(octree.child(rootBlock, i)));
97 EXPECT_TRUE(octree.isLeaf(octree.child(rootBlock, i)));
98 }
99 }
100
101 //------------------------------------------------------------------------------
TEST(spin_octree,octree_coveringLeafBlocks)102 TEST(spin_octree, octree_coveringLeafBlocks)
103 {
104 SLIC_INFO(
105 "*** This test exercises the coveringLeafBlock function of OctreeBase");
106
107 static const int DIM = 2;
108 using LeafNodeType = axom::spin::BlockData;
109 using OctreeType = axom::spin::OctreeBase<DIM, LeafNodeType>;
110 using BlockIndex = OctreeType::BlockIndex;
111 using GridPt = OctreeType::GridPt;
112
113 OctreeType octree;
114
115 BlockIndex rootBlock = octree.root();
116 SLIC_INFO("Root block of octree is " << rootBlock);
117 EXPECT_EQ(rootBlock, octree.coveringLeafBlock(rootBlock));
118
119 EXPECT_EQ(2 * DIM, rootBlock.numFaceNeighbors());
120
121 // All children blocks of a leaf block have the leaf as their covering block
122 int numChildren = BlockIndex::numChildren();
123 for(int i = 0; i < numChildren; ++i)
124 {
125 BlockIndex blk = octree.child(rootBlock, i);
126
127 EXPECT_EQ(rootBlock, octree.coveringLeafBlock(blk));
128 }
129
130 // All neighbors of the root block are invalid
131 for(int i = 0; i < rootBlock.numFaceNeighbors(); ++i)
132 {
133 BlockIndex neighborBlk = rootBlock.faceNeighbor(i);
134
135 SLIC_INFO(" Face neighbor " << i << " is " << neighborBlk);
136
137 // The root has no valid neighbors at the same level
138 EXPECT_EQ(BlockIndex::invalid_index(), octree.coveringLeafBlock(neighborBlk));
139 }
140
141 octree.refineLeaf(rootBlock);
142
143 // No leaf covers a block after it is refined
144 EXPECT_EQ(BlockIndex::invalid_index(), octree.coveringLeafBlock(rootBlock));
145
146 // Check neighbors of the root's children
147 for(int i = 0; i < numChildren; ++i)
148 {
149 BlockIndex blk = octree.child(rootBlock, i);
150
151 EXPECT_EQ(blk, octree.coveringLeafBlock(blk));
152
153 // Each child or the root has two valid face neighbors
154 int validNeighborCount = 0;
155 for(int j = 0; j < blk.numFaceNeighbors(); ++j)
156 {
157 BlockIndex neighborBlk = blk.faceNeighbor(j);
158
159 SLIC_INFO(" Face neighbor " << j << " is " << neighborBlk);
160
161 if(octree.coveringLeafBlock(neighborBlk) != BlockIndex::invalid_index())
162 validNeighborCount++;
163 }
164 EXPECT_EQ(2, validNeighborCount);
165 }
166
167 octree.refineLeaf(octree.child(rootBlock, 0));
168
169 // Iterate through level 2 blocks and find face-neighbors
170 int lev = 2;
171 for(int i = 0; i < (1 << lev); ++i)
172 {
173 for(int j = 0; j < (1 << lev); ++j)
174 {
175 GridPt pt = GridPt::make_point(i, j);
176 BlockIndex blk(pt, lev);
177
178 BlockIndex coveringBlock = octree.coveringLeafBlock(blk);
179
180 SLIC_INFO("Covering block of " << blk << " is " << coveringBlock);
181
182 // Every blk has a valid covering block
183 EXPECT_NE(BlockIndex::invalid_index(), coveringBlock);
184
185 // .. at a coarser level
186 EXPECT_GE(blk.level(), coveringBlock.level());
187
188 for(int k = 0; k < blk.numFaceNeighbors(); ++k)
189 {
190 BlockIndex neighborBlk = blk.faceNeighbor(k);
191 BlockIndex coveringBlk = octree.coveringLeafBlock(neighborBlk);
192
193 SLIC_INFO(
194 "\tFace neighbor "
195 << k << " is " << neighborBlk << " -- Covering block is " << coveringBlk
196 << (coveringBlk == BlockIndex::invalid_index() ? " -- invalid_index"
197 : ""));
198
199 if(octree.coveringLeafBlock(neighborBlk) != BlockIndex::invalid_index())
200 {
201 EXPECT_GE(blk.level(), neighborBlk.level());
202 }
203 }
204 }
205 }
206 }
207
208 //------------------------------------------------------------------------------
TEST(spin_octree,octree_block_is_descendant)209 TEST(spin_octree, octree_block_is_descendant)
210 {
211 SLIC_INFO(
212 "*** This test exercises the isDescendantOf() function of "
213 "OctreeBase::BlockIndex");
214
215 static const int DIM = 2;
216 using LeafNodeType = axom::spin::BlockData;
217 using OctreeType = axom::spin::OctreeBase<DIM, LeafNodeType>;
218 using BlockIndex = OctreeType::BlockIndex;
219
220 OctreeType octree;
221
222 BlockIndex rootBlock = octree.root();
223 SLIC_INFO("Root block of octree is " << rootBlock);
224
225 EXPECT_TRUE(rootBlock.isDescendantOf(rootBlock));
226 EXPECT_FALSE(rootBlock.isDescendantOf(BlockIndex::invalid_index()));
227 EXPECT_FALSE(BlockIndex::invalid_index().isDescendantOf(rootBlock));
228
229 SLIC_INFO("-- checking children of root");
230 octree.refineLeaf(rootBlock);
231 int numChildren = BlockIndex::numChildren();
232 for(int i = 0; i < numChildren; ++i)
233 {
234 BlockIndex blk = octree.child(rootBlock, i);
235
236 EXPECT_TRUE(blk.isDescendantOf(rootBlock));
237 EXPECT_FALSE(rootBlock.isDescendantOf(blk));
238
239 EXPECT_FALSE(
240 blk.isDescendantOf(octree.child(rootBlock, (i + 1) % numChildren)));
241 }
242
243 BlockIndex child3 = octree.child(rootBlock, 3);
244 octree.refineLeaf(child3);
245
246 for(int i = 0; i < numChildren; ++i)
247 {
248 BlockIndex grandchild = child3.child(i);
249 EXPECT_TRUE(grandchild.isDescendantOf(grandchild));
250 EXPECT_TRUE(grandchild.isDescendantOf(child3));
251 EXPECT_TRUE(grandchild.isDescendantOf(rootBlock));
252
253 if(i != 3)
254 {
255 EXPECT_FALSE(grandchild.isDescendantOf(rootBlock.child(i)));
256 }
257
258 EXPECT_FALSE(grandchild.isDescendantOf(BlockIndex::invalid_index()));
259 EXPECT_FALSE(BlockIndex::invalid_index().isDescendantOf(grandchild));
260 }
261 }
262
TEST(spin_octree,count_octree_blocks)263 TEST(spin_octree, count_octree_blocks)
264 {
265 static const int DIM = 2;
266 using LeafNodeType = axom::spin::BlockData;
267 using OctreeType = axom::spin::OctreeBase<DIM, LeafNodeType>;
268
269 OctreeType octree;
270
271 // A default initialized octree should have a single leaf block -- the root
272 SLIC_INFO("Check number of blocks in empty octree");
273 EXPECT_EQ(1, octree.getOctreeLevel(0).numBlocks());
274 EXPECT_EQ(0, octree.getOctreeLevel(0).numInternalBlocks());
275 EXPECT_EQ(1, octree.getOctreeLevel(0).numLeafBlocks());
276
277 for(int lev = 1; lev < octree.maxLeafLevel(); ++lev)
278 {
279 EXPECT_EQ(0, octree.getOctreeLevel(lev).numBlocks());
280 EXPECT_EQ(0, octree.getOctreeLevel(lev).numInternalBlocks());
281 EXPECT_EQ(0, octree.getOctreeLevel(lev).numLeafBlocks());
282 }
283
284 SLIC_INFO("Refine the root and check number of blocks in first three levels");
285 octree.refineLeaf(octree.root());
286 EXPECT_EQ(1, octree.getOctreeLevel(0).numBlocks());
287 EXPECT_EQ(1, octree.getOctreeLevel(0).numInternalBlocks());
288 EXPECT_EQ(0, octree.getOctreeLevel(0).numLeafBlocks());
289
290 EXPECT_EQ(4, octree.getOctreeLevel(1).numBlocks());
291 EXPECT_EQ(0, octree.getOctreeLevel(1).numInternalBlocks());
292 EXPECT_EQ(4, octree.getOctreeLevel(1).numLeafBlocks());
293
294 EXPECT_EQ(0, octree.getOctreeLevel(2).numBlocks());
295 EXPECT_EQ(0, octree.getOctreeLevel(2).numInternalBlocks());
296 EXPECT_EQ(0, octree.getOctreeLevel(2).numLeafBlocks());
297
298 SLIC_INFO("Refine a child of the root and check blocks in first few levels");
299 octree.refineLeaf(octree.root().child(3));
300 EXPECT_EQ(1, octree.getOctreeLevel(0).numBlocks());
301 EXPECT_EQ(1, octree.getOctreeLevel(0).numInternalBlocks());
302 EXPECT_EQ(0, octree.getOctreeLevel(0).numLeafBlocks());
303
304 EXPECT_EQ(4, octree.getOctreeLevel(1).numBlocks());
305 EXPECT_EQ(1, octree.getOctreeLevel(1).numInternalBlocks());
306 EXPECT_EQ(3, octree.getOctreeLevel(1).numLeafBlocks());
307
308 EXPECT_EQ(4, octree.getOctreeLevel(2).numBlocks());
309 EXPECT_EQ(0, octree.getOctreeLevel(2).numInternalBlocks());
310 EXPECT_EQ(4, octree.getOctreeLevel(2).numLeafBlocks());
311
312 SLIC_INFO(
313 "Refine another child of the root and check blocks in first few levels");
314 octree.refineLeaf(octree.root().child(2));
315 EXPECT_EQ(4, octree.getOctreeLevel(1).numBlocks());
316 EXPECT_EQ(2, octree.getOctreeLevel(1).numInternalBlocks());
317 EXPECT_EQ(2, octree.getOctreeLevel(1).numLeafBlocks());
318
319 EXPECT_EQ(8, octree.getOctreeLevel(2).numBlocks());
320 EXPECT_EQ(0, octree.getOctreeLevel(2).numInternalBlocks());
321 EXPECT_EQ(8, octree.getOctreeLevel(2).numLeafBlocks());
322
323 SLIC_INFO(
324 "Refine a grandchild of the root and check blocks in first few levels");
325 octree.refineLeaf(octree.root().child(2).child(1));
326 EXPECT_EQ(4, octree.getOctreeLevel(1).numBlocks());
327 EXPECT_EQ(2, octree.getOctreeLevel(1).numInternalBlocks());
328 EXPECT_EQ(2, octree.getOctreeLevel(1).numLeafBlocks());
329
330 EXPECT_EQ(8, octree.getOctreeLevel(2).numBlocks());
331 EXPECT_EQ(1, octree.getOctreeLevel(2).numInternalBlocks());
332 EXPECT_EQ(7, octree.getOctreeLevel(2).numLeafBlocks());
333
334 EXPECT_EQ(4, octree.getOctreeLevel(3).numBlocks());
335 EXPECT_EQ(0, octree.getOctreeLevel(3).numInternalBlocks());
336 EXPECT_EQ(4, octree.getOctreeLevel(3).numLeafBlocks());
337 }
338
339 //----------------------------------------------------------------------
340 //----------------------------------------------------------------------
341 #include "axom/slic/core/SimpleLogger.hpp"
342 using axom::slic::SimpleLogger;
343
main(int argc,char * argv[])344 int main(int argc, char* argv[])
345 {
346 int result = 0;
347
348 ::testing::InitGoogleTest(&argc, argv);
349
350 SimpleLogger logger; // create & initialize test logger,
351
352 // finalized when exiting main scope
353
354 result = RUN_ALL_TESTS();
355
356 return result;
357 }
358