diff options
Diffstat (limited to 'chroma/bvh/grid.py')
| -rw-r--r-- | chroma/bvh/grid.py | 50 |
1 files changed, 34 insertions, 16 deletions
diff --git a/chroma/bvh/grid.py b/chroma/bvh/grid.py index 9ac0306..6fcb3dd 100644 --- a/chroma/bvh/grid.py +++ b/chroma/bvh/grid.py @@ -5,7 +5,9 @@ from chroma.gpu.bvh import create_leaf_nodes, merge_nodes_detailed, concatenate_ MAX_CHILD = 2**(32 - CHILD_BITS) - 1 -@profile +def count_unique_in_sorted(a): + return (np.ediff1d(a) > 0).sum() + 1 + def make_recursive_grid_bvh(mesh, target_degree=3): '''Returns a BVH created using a 'recursive grid' method. @@ -24,7 +26,7 @@ def make_recursive_grid_bvh(mesh, target_degree=3): argsort = morton_codes.argsort() leaf_nodes = leaf_nodes[argsort] morton_codes = morton_codes[argsort] - + morton_codes >>= 12 # Create parent layers layers = [leaf_nodes] while len(layers[0]) > 1: @@ -33,27 +35,43 @@ def make_recursive_grid_bvh(mesh, target_degree=3): # Figure out how many bits to shift in morton code to achieve desired # degree nnodes = len(top_layer) - nunique = len(np.unique(morton_codes)) - while nnodes / float(nunique) < target_degree and nunique > 1: - morton_codes >>= 1 - nunique = len(np.unique(morton_codes)) + + #nunique = count_unique_in_sorted(morton_codes) + #while nnodes / float(nunique) < target_degree and nunique > 1: + # morton_codes >>= 1 + # nunique = count_unique_in_sorted(morton_codes) + morton_codes >>= 3 + nunique = count_unique_in_sorted(morton_codes) # Determine the grouping of child nodes into parents parent_morton_codes, first_child = np.unique(morton_codes, return_index=True) + #assert (np.sort(parent_morton_codes) == parent_morton_codes).all() first_child = first_child.astype(np.int32) nchild = np.ediff1d(first_child, to_end=nnodes - first_child[-1]) # Expand groups that have too many children - print 'Expanding %d parent nodes' % (np.count_nonzero(nchild > MAX_CHILD)) - while nchild.max() > MAX_CHILD: - index = nchild.argmax() - new_first = np.arange(first_child[index], first_child[index]+nchild[index], MAX_CHILD) - first_child = np.concatenate([first_child[:index], - new_first, - first_child[index+1:]]) - parent_morton_codes = np.concatenate([parent_morton_codes[:index], - np.repeat(parent_morton_codes[index], len(new_first)), - parent_morton_codes[index+1:]]) + excess_children = np.argwhere(nchild > MAX_CHILD) + if len(excess_children) > 0: + print 'Expanding %d parent nodes' % len(excess_children) + parent_morton_parts = np.split(parent_morton_codes, excess_children) + first_child_parts = np.split(first_child, excess_children) + nchild_parts = np.split(nchild, excess_children) + + new_parent_morton_parts = parent_morton_parts[:1] + new_first_child_parts = first_child_parts[:1] + + for morton_part, first_part, nchild_part in zip(parent_morton_parts[1:], + first_child_parts[1:], + nchild_parts[1:]): + extra_first = np.arange(first_part[0], + first_part[0]+nchild_part[0], + MAX_CHILD) + new_first_child_parts.extend([extra_first, first_part[1:]]) + new_parent_morton_parts.extend([np.repeat(parent_morton_codes[0], + len(extra_first)), morton_part[1:]]) + + parent_morton_codes = np.concatenate(new_parent_morton_parts) + first_child = np.concatenate(new_first_child_parts) nchild = np.ediff1d(first_child, to_end=nnodes - first_child[-1]) if nunique > 1: # Yes, I'm pedantic |