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