eic-opticks/CSG/csg_postorder.h

0001 /*
0002  * Copyright (c) 2019 Opticks Team. All Rights Reserved.
0003  *
0004  * This file is part of Opticks
0005  * (see https://bitbucket.org/simoncblyth/opticks).
0006  *
0007  * Licensed under the Apache License, Version 2.0 (the "License");
0008  * you may not use this file except in compliance with the License.
0009  * You may obtain a copy of the License at
0010  *
0011  *   http://www.apache.org/licenses/LICENSE-2.0
0012  *
0013  * Unless required by applicable law or agreed to in writing, software
0014  * distributed under the License is distributed on an "AS IS" BASIS,
0015  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0016  * See the License for the specific language governing permissions and
0017  * limitations under the License.
0018  */
0019
0020 #pragma once
0021 /*
0022
0023 1-based indexing of complete binary tree
0024 -------------------------------------------
0025
0026 Exhibits a very regular pattern of the bits::
0027
0028                                                      depth     elevation
0029
0030                          1                               0           3
0031
0032               10                   11                    1           2
0033
0034          100       101        110        111             2           1
0035
0036      1000 1001  1010 1011  1100 1101  1110  1111         3           0
0037
0038
0039 This has several advantages:
0040
0041 * child/parent indices can be computed (not stored) so no tree overheads
0042 * postorder traverse can be computed by bit twiddling
0043
0044 ::
0045
0046     parent(i)         = i/2
0047     leftchild(i)      = 2*i + 1
0048     rightchild(i)     = 2*i + 2
0049
0050     leftmost(height)  =  1 << height
0051     postorder_next(i) =  i & 1   ?   i >> 1   :   (i << elevation) + (1 << elevation)
0052
0053
0054 */
0055
0056 #ifdef __CUDACC__
0057 #define POSTORDER_DEPTH(currIdx) ( 32 - __clz((currIdx)) - 1 )
0058 #define TREE_HEIGHT(numNodes) ( __ffs((numNodes) + 1) - 2)
0059 #define TREE_DEPTH(nodeIdx) ( 32 - __clz((nodeIdx)) - 1 )
0060 #else
0061 #define POSTORDER_DEPTH(currIdx) ( 32 - std::__clz((currIdx)) - 1 )
0062 #define TREE_HEIGHT(numNodes) ( ffs((numNodes) + 1) - 2)
0063 //#define TREE_DEPTH(nodeIdx) ( 32 - std::__clz((nodeIdx)) - 1 )
0064 #define TREE_DEPTH(nodeIdx) ( 32 - __builtin_clz((nodeIdx)) - 1 )
0065 #endif
0066
0067 // see dev/csg/postorder.py
0068 #define POSTORDER_NEXT(currIdx, elevation )( ((currIdx) & 1) ? (currIdx) >> 1 :  ((currIdx) << (elevation)) + (1 << (elevation)) )
0069
0070 // perfect binary tree assumptions,   2^(h+1) - 1
0071 #define TREE_NODES(height) ( (0x1 << (1+(height))) - 1 )
0072
0073