[yt-svn] commit/yt: MatthewTurk: Merged in charlie_watson/yt (pull request #2240)
commits-noreply at bitbucket.org
commits-noreply at bitbucket.org
Tue Jun 28 08:29:57 PDT 2016
1 new commit in yt:
https://bitbucket.org/yt_analysis/yt/commits/3ca8a739e529/
Changeset: 3ca8a739e529
Branch: yt
User: MatthewTurk
Date: 2016-06-28 15:29:48+00:00
Summary: Merged in charlie_watson/yt (pull request #2240)
Changing amr_kdtree functions to be Node class methods
Affected #: 5 files
diff -r d48c4a143f6e3c69c9a1016725d8328f8ea3af53 -r 3ca8a739e5296422ea7954ce8d2717908be25dd6 yt/utilities/amr_kdtree/amr_kdtree.py
--- a/yt/utilities/amr_kdtree/amr_kdtree.py
+++ b/yt/utilities/amr_kdtree/amr_kdtree.py
@@ -23,19 +23,7 @@
receive_and_reduce, \
send_to_parent, \
scatter_image
-from yt.utilities.lib.amr_kdtools import \
- Node, \
- add_grids, \
- find_node, \
- kd_is_leaf, \
- set_dirty, \
- depth_traverse, \
- depth_first_touch, \
- kd_traverse, \
- get_left_edge, \
- get_right_edge, \
- kd_sum_volume, \
- kd_node_check
+from yt.utilities.lib.amr_kdtools import Node
from yt.utilities.parallel_tools.parallel_analysis_interface import \
ParallelAnalysisInterface
from yt.utilities.lib.grid_traversal import PartitionedGrid
@@ -95,7 +83,7 @@
gles = np.array([g.LeftEdge for g in grids])
gres = np.array([g.RightEdge for g in grids])
gids = np.array([g.id for g in grids], dtype="int64")
- add_grids(self.trunk, gids.size, gles, gres, gids,
+ self.trunk.add_grids(gids.size, gles, gres, gids,
self.comm_rank, self.comm_size)
del gles, gres, gids, grids
@@ -108,14 +96,14 @@
self.add_grids(grids)
def check_tree(self):
- for node in depth_traverse(self.trunk):
+ for node in self.trunk.depth_traverse():
if node.grid == -1:
continue
grid = self.ds.index.grids[node.grid - self._id_offset]
dds = grid.dds
gle = grid.LeftEdge
- nle = self.ds.arr(get_left_edge(node), input_units="code_length")
- nre = self.ds.arr(get_right_edge(node), input_units="code_length")
+ nle = self.ds.arr(node.get_left_edge(), input_units="code_length")
+ nre = self.ds.arr(node.get_right_edge(), input_units="code_length")
li = np.rint((nle-gle)/dds).astype('int32')
ri = np.rint((nre-gle)/dds).astype('int32')
dims = (ri - li).astype('int32')
@@ -125,22 +113,22 @@
# print grid, dims, li, ri
# Calculate the Volume
- vol = kd_sum_volume(self.trunk)
+ vol = self.trunk.kd_sum_volume()
mylog.debug('AMRKDTree volume = %e' % vol)
- kd_node_check(self.trunk)
+ self.trunk.kd_node_check()
def sum_cells(self, all_cells=False):
cells = 0
- for node in depth_traverse(self.trunk):
+ for node in self.trunk.depth_traverse():
if node.grid == -1:
continue
- if not all_cells and not kd_is_leaf(node):
+ if not all_cells and not node.kd_is_leaf():
continue
grid = self.ds.index.grids[node.grid - self._id_offset]
dds = grid.dds
gle = grid.LeftEdge
- nle = self.ds.arr(get_left_edge(node), input_units="code_length")
- nre = self.ds.arr(get_right_edge(node), input_units="code_length")
+ nle = self.ds.arr(node.get_left_edge(), input_units="code_length")
+ nre = self.ds.arr(node.get_right_edge(), input_units="code_length")
li = np.rint((nle-gle)/dds).astype('int32')
ri = np.rint((nre-gle)/dds).astype('int32')
dims = (ri - li).astype('int32')
@@ -186,7 +174,7 @@
regenerate_data = self.fields is None or \
len(self.fields) != len(new_fields) or \
self.fields != new_fields or force
- set_dirty(self.tree.trunk, regenerate_data)
+ self.tree.trunk.set_dirty(regenerate_data)
self.fields = new_fields
if self.log_fields is not None and not regenerate_data:
@@ -214,18 +202,18 @@
self.set_fields(fields, log_fields, no_ghost)
def traverse(self, viewpoint=None):
- for node in kd_traverse(self.tree.trunk, viewpoint=viewpoint):
+ for node in self.tree.trunk.kd_traverse(viewpoint=viewpoint):
yield self.get_brick_data(node)
def slice_traverse(self, viewpoint = None):
if not hasattr(self.ds.index, "grid"):
raise NotImplementedError
- for node in kd_traverse(self.tree.trunk, viewpoint=viewpoint):
+ for node in self.tree.trunk.kd_traverse(viewpoint=viewpoint):
grid = self.ds.index.grids[node.grid - self._id_offset]
dds = grid.dds
gle = grid.LeftEdge.in_units("code_length").ndarray_view()
- nle = get_left_edge(node)
- nre = get_right_edge(node)
+ nle = node.get_left_edge()
+ nre = node.get_right_edge()
li = np.rint((nle-gle)/dds).astype('int32')
ri = np.rint((nre-gle)/dds).astype('int32')
dims = (ri - li).astype('int32')
@@ -248,7 +236,7 @@
return temp
def locate_node(self, pos):
- return find_node(self.tree.trunk, pos)
+ return self.tree.trunk.find_node(pos)
def get_reduce_owners(self):
owners = {}
@@ -290,8 +278,8 @@
grid = self.ds.index.grids[node.grid - self._id_offset]
dds = grid.dds.ndarray_view()
gle = grid.LeftEdge.ndarray_view()
- nle = get_left_edge(node)
- nre = get_right_edge(node)
+ nle = node.get_left_edge()
+ nre = node.get_right_edge()
li = np.rint((nle-gle)/dds).astype('int32')
ri = np.rint((nre-gle)/dds).astype('int32')
dims = (ri - li).astype('int32')
@@ -434,7 +422,7 @@
if self.comm.rank != 0:
self.comm.recv_array(self.comm.rank-1, tag=self.comm.rank-1)
f = h5py.File(fn,'w')
- for node in depth_traverse(self.tree):
+ for node in self.tree.depth_traverse():
i = node.node_id
if node.data is not None:
for fi,field in enumerate(self.fields):
@@ -455,7 +443,7 @@
self.comm.recv_array(self.comm.rank-1, tag=self.comm.rank-1)
try:
f = h5py.File(fn,"a")
- for node in depth_traverse(self.tree):
+ for node in self.tree.depth_traverse():
i = node.node_id
if node.grid != -1:
data = [f["brick_%s_%s" %
@@ -506,7 +494,7 @@
gridids = []
splitdims = []
splitposs = []
- for node in depth_first_touch(self.tree.trunk):
+ for node in self.tree.trunk.depth_first_touch():
nids.append(node.node_id)
les.append(node.get_left_edge())
res.append(node.get_right_edge())
@@ -562,11 +550,11 @@
if splitdims[i] != -1:
n.create_split(splitdims[i], splitposs[i])
- mylog.info('AMRKDTree rebuilt, Final Volume: %e' % kd_sum_volume(self.tree.trunk))
+ mylog.info('AMRKDTree rebuilt, Final Volume: %e' % self.tree.trunk.kd_sum_volume())
return self.tree.trunk
def count_volume(self):
- return kd_sum_volume(self.tree.trunk)
+ return self.tree.trunk.kd_sum_volume()
def count_cells(self):
return self.tree.sum_cells()
@@ -581,6 +569,6 @@
hv = AMRKDTree(ds)
t2 = time()
- print(kd_sum_volume(hv.tree.trunk))
- print(kd_node_check(hv.tree.trunk))
+ print(hv.tree.trunk.kd_sum_volume())
+ print(hv.tree.trunk.kd_node_check())
print('Time: %e seconds' % (t2-t1))
diff -r d48c4a143f6e3c69c9a1016725d8328f8ea3af53 -r 3ca8a739e5296422ea7954ce8d2717908be25dd6 yt/utilities/lib/amr_kdtools.pxd
--- a/yt/utilities/lib/amr_kdtools.pxd
+++ b/yt/utilities/lib/amr_kdtools.pxd
@@ -19,8 +19,6 @@
int dim
np.float64_t pos
-cdef class Node
-
cdef class Node:
cdef public Node left
cdef public Node right
@@ -34,7 +32,51 @@
cdef public data
cdef Split * split
cdef int level
-
-cdef int point_in_node(Node node, np.float64_t[:] point)
-cdef Node _find_node(Node node, np.float64_t[:] point)
-cdef int _kd_is_leaf(Node node)
+ cdef int point_in_node(self, np.float64_t[:] point)
+ cdef Node _find_node(self, np.float64_t[:] point)
+ cdef int _kd_is_leaf(self)
+ cdef add_grid(self, np.float64_t[:] gle, np.float64_t[:] gre,
+ int gid,
+ int rank,
+ int size)
+ cdef insert_grid(self,
+ np.float64_t[:] gle,
+ np.float64_t[:] gre,
+ int grid_id,
+ int rank,
+ int size)
+ cpdef add_grids(self,
+ int ngrids,
+ np.float64_t[:,:] gles,
+ np.float64_t[:,:] gres,
+ np.int64_t[:] gids,
+ int rank,
+ int size)
+ cdef int should_i_split(self, int rank, int size)
+ cdef void insert_grids(self,
+ int ngrids,
+ np.float64_t[:,:] gles,
+ np.float64_t[:,:] gres,
+ np.int64_t[:] gids,
+ int rank,
+ int size)
+ cdef split_grid(self,
+ np.float64_t[:] gle,
+ np.float64_t[:] gre,
+ int gid,
+ int rank,
+ int size)
+ cdef int split_grids(self,
+ int ngrids,
+ np.float64_t[:,:] gles,
+ np.float64_t[:,:] gres,
+ np.int64_t[:] gids,
+ int rank,
+ int size)
+ cdef geo_split(self,
+ np.float64_t[:] gle,
+ np.float64_t[:] gre,
+ int grid_id,
+ int rank,
+ int size)
+ cdef void divide(self, Split * split)
diff -r d48c4a143f6e3c69c9a1016725d8328f8ea3af53 -r 3ca8a739e5296422ea7954ce8d2717908be25dd6 yt/utilities/lib/amr_kdtools.pyx
--- a/yt/utilities/lib/amr_kdtools.pyx
+++ b/yt/utilities/lib/amr_kdtools.pyx
@@ -67,12 +67,6 @@
else:
return np.nan
- def get_left_edge(self):
- return get_left_edge(self)
-
- def get_right_edge(self):
- return get_right_edge(self)
-
def set_left_edge(self, np.float64_t[:] left_edge):
cdef int i
for i in range(3):
@@ -92,17 +86,571 @@
def __dealloc__(self):
if self.split != NULL: free(self.split)
-def get_left_edge(Node node):
- le = np.empty(3, dtype='float64')
- for i in range(3):
- le[i] = node.left_edge[i]
- return le
+ # Begin input of converted methods
-def get_right_edge(Node node):
- re = np.empty(3, dtype='float64')
- for i in range(3):
- re[i] = node.right_edge[i]
- return re
+ def get_left_edge(self):
+ le = np.empty(3, dtype='float64')
+ for i in range(3):
+ le[i] = self.left_edge[i]
+ return le
+
+ def get_right_edge(self):
+ re = np.empty(3, dtype='float64')
+ for i in range(3):
+ re[i] = self.right_edge[i]
+ return re
+
+ def set_dirty(self, bint state):
+ cdef Node node
+ for node in self.depth_traverse():
+ node.dirty = state
+
+ def kd_traverse(self, viewpoint=None):
+ cdef Node node
+ if viewpoint is None:
+ for node in self.depth_traverse():
+ if node._kd_is_leaf() == 1 and node.grid != -1:
+ yield node
+ else:
+ for node in self.viewpoint_traverse(viewpoint):
+ if node._kd_is_leaf() == 1 and node.grid != -1:
+ yield node
+
+ def add_pygrid(self,
+ np.float64_t[:] gle,
+ np.float64_t[:] gre,
+ int gid,
+ int rank,
+ int size):
+
+ """
+ The entire purpose of this function is to move everything from ndarrays
+ to internal C pointers.
+ """
+ cdef np.float64_t[:] pgles = cvarray(format="d", shape=(3,), itemsize=sizeof(np.float64_t))
+ cdef np.float64_t[:] pgres = cvarray(format="d", shape=(3,), itemsize=sizeof(np.float64_t))
+ cdef int j
+ for j in range(3):
+ pgles[j] = gle[j]
+ pgres[j] = gre[j]
+
+ self.add_grid(pgles, pgres, gid, rank, size)
+
+ @cython.boundscheck(False)
+ @cython.wraparound(False)
+ @cython.cdivision(True)
+ cdef add_grid(self,
+ np.float64_t[:] gle,
+ np.float64_t[:] gre,
+ int gid,
+ int rank,
+ int size):
+
+ if not should_i_build(self, rank, size):
+ return
+
+ if self._kd_is_leaf() == 1:
+ self.insert_grid(gle, gre, gid, rank, size)
+ else:
+ less_id = gle[self.split.dim] < self.split.pos
+ if less_id:
+ self.left.add_grid(gle, gre,
+ gid, rank, size)
+
+ greater_id = gre[self.split.dim] > self.split.pos
+ if greater_id:
+ self.right.add_grid(gle, gre,
+ gid, rank, size)
+ return
+
+
+
+ @cython.boundscheck(False)
+ @cython.wraparound(False)
+ @cython.cdivision(True)
+ cdef insert_grid(self,
+ np.float64_t[:] gle,
+ np.float64_t[:] gre,
+ int grid_id,
+ int rank,
+ int size):
+ if not should_i_build(self, rank, size):
+ return
+
+ # If we should continue to split based on parallelism, do so!
+ if self.should_i_split(rank, size):
+ self.geo_split(gle, gre, grid_id, rank, size)
+ return
+
+ cdef int contained = 1
+ for i in range(3):
+ if gle[i] > self.left_edge[i] or\
+ gre[i] < self.right_edge[i]:
+ contained *= 0
+
+ if contained == 1:
+ self.grid = grid_id
+ assert(self.grid != -1)
+ return
+
+ # Split the grid
+ cdef int check = self.split_grid(gle, gre, grid_id, rank, size)
+ # If check is -1, then we have found a place where there are no choices.
+ # Exit out and set the node to None.
+ if check == -1:
+ self.grid = -1
+ return
+
+ @cython.boundscheck(False)
+ @cython.wraparound(False)
+ @cython.cdivision(True)
+ cpdef add_grids(self,
+ int ngrids,
+ np.float64_t[:,:] gles,
+ np.float64_t[:,:] gres,
+ np.int64_t[:] gids,
+ int rank,
+ int size):
+ cdef int i, j, nless, ngreater, index
+ cdef np.float64_t[:,:] less_gles, less_gres, greater_gles, greater_gres
+ cdef np.int64_t[:] l_ids, g_ids
+ if not should_i_build(self, rank, size):
+ return
+
+ if self._kd_is_leaf() == 1:
+ self.insert_grids(ngrids, gles, gres, gids, rank, size)
+ return
+
+ less_ids = cvarray(format="q", shape=(ngrids,), itemsize=sizeof(np.int64_t))
+ greater_ids = cvarray(format="q", shape=(ngrids,), itemsize=sizeof(np.int64_t))
+
+ nless = 0
+ ngreater = 0
+ for i in range(ngrids):
+ if gles[i, self.split.dim] < self.split.pos:
+ less_ids[nless] = i
+ nless += 1
+
+ if gres[i, self.split.dim] > self.split.pos:
+ greater_ids[ngreater] = i
+ ngreater += 1
+
+ #print 'nless: %i' % nless
+ #print 'ngreater: %i' % ngreater
+
+ if nless > 0:
+ less_gles = cvarray(format="d", shape=(nless,3), itemsize=sizeof(np.float64_t))
+ less_gres = cvarray(format="d", shape=(nless,3), itemsize=sizeof(np.float64_t))
+ l_ids = cvarray(format="q", shape=(nless,), itemsize=sizeof(np.int64_t))
+
+ for i in range(nless):
+ index = less_ids[i]
+ l_ids[i] = gids[index]
+ for j in range(3):
+ less_gles[i,j] = gles[index,j]
+ less_gres[i,j] = gres[index,j]
+
+ self.left.add_grids(nless, less_gles, less_gres,
+ l_ids, rank, size)
+
+ if ngreater > 0:
+ greater_gles = cvarray(format="d", shape=(ngreater,3), itemsize=sizeof(np.float64_t))
+ greater_gres = cvarray(format="d", shape=(ngreater,3), itemsize=sizeof(np.float64_t))
+ g_ids = cvarray(format="q", shape=(ngreater,), itemsize=sizeof(np.int64_t))
+
+ for i in range(ngreater):
+ index = greater_ids[i]
+ g_ids[i] = gids[index]
+ for j in range(3):
+ greater_gles[i,j] = gles[index,j]
+ greater_gres[i,j] = gres[index,j]
+
+ self.right.add_grids(ngreater, greater_gles, greater_gres,
+ g_ids, rank, size)
+
+ return
+
+ @cython.boundscheck(False)
+ @cython.wraparound(False)
+ @cython.cdivision(True)
+ cdef int should_i_split(self, int rank, int size):
+ if self.node_id < size and self.node_id > 0:
+ return 1
+ return 0
+
+ @cython.boundscheck(False)
+ @cython.wraparound(False)
+ @cython.cdivision(True)
+ cdef void insert_grids(self,
+ int ngrids,
+ np.float64_t[:,:] gles,
+ np.float64_t[:,:] gres,
+ np.int64_t[:] gids,
+ int rank,
+ int size):
+
+ if not should_i_build(self, rank, size) or ngrids == 0:
+ return
+ cdef int contained = 1
+ cdef int check
+
+ if ngrids == 1:
+ # If we should continue to split based on parallelism, do so!
+ if self.should_i_split(rank, size):
+ self.geo_split(gles[0,:], gres[0,:], gids[0], rank, size)
+ return
+
+ for i in range(3):
+ contained *= gles[0,i] <= self.left_edge[i]
+ contained *= gres[0,i] >= self.right_edge[i]
+
+ if contained == 1:
+ # print 'Node fully contained, setting to grid: %i' % gids[0]
+ self.grid = gids[0]
+ assert(self.grid != -1)
+ return
+
+ # Split the grids
+ check = self.split_grids(ngrids, gles, gres, gids, rank, size)
+ # If check is -1, then we have found a place where there are no choices.
+ # Exit out and set the node to None.
+ if check == -1:
+ self.grid = -1
+ return
+
+ @cython.boundscheck(False)
+ @cython.wraparound(False)
+ @cython.cdivision(True)
+ cdef split_grid(self,
+ np.float64_t[:] gle,
+ np.float64_t[:] gre,
+ int gid,
+ int rank,
+ int size):
+
+ cdef int j
+ cdef np.uint8_t[:] less_ids, greater_ids
+ data = cvarray(format="d", shape=(1,2,3), itemsize=sizeof(np.float64_t))
+ for j in range(3):
+ data[0,0,j] = gle[j]
+ data[0,1,j] = gre[j]
+
+ less_ids = cvarray(format="B", shape=(1,), itemsize=sizeof(np.uint8_t))
+ greater_ids = cvarray(format="B", shape=(1,), itemsize=sizeof(np.uint8_t))
+
+ best_dim, split_pos, nless, ngreater = \
+ kdtree_get_choices(1, data, self.left_edge, self.right_edge,
+ less_ids, greater_ids)
+
+ # If best_dim is -1, then we have found a place where there are no choices.
+ # Exit out and set the node to None.
+ if best_dim == -1:
+ return -1
+
+
+ split = <Split *> malloc(sizeof(Split))
+ split.dim = best_dim
+ split.pos = split_pos
+
+ # Create a Split
+ self.divide(split)
+
+ # Populate Left Node
+ #print 'Inserting left node', self.left_edge, self.right_edge
+ if nless == 1:
+ self.left.insert_grid(gle, gre,
+ gid, rank, size)
+
+ # Populate Right Node
+ #print 'Inserting right node', self.left_edge, self.right_edge
+ if ngreater == 1:
+ self.right.insert_grid(gle, gre,
+ gid, rank, size)
+
+ return 0
+
+ #@cython.boundscheck(False)
+ #@cython.wraparound(False)
+ #@cython.cdivision(True)
+ cdef int split_grids(self,
+ int ngrids,
+ np.float64_t[:,:] gles,
+ np.float64_t[:,:] gres,
+ np.int64_t[:] gids,
+ int rank,
+ int size):
+ # Find a Split
+ cdef int i, j, index
+ cdef np.float64_t[:,:] less_gles, less_gres, greater_gles, greater_gres
+ cdef np.int64_t[:] l_ids, g_ids
+ if ngrids == 0: return 0
+
+ data = cvarray(format="d", shape=(ngrids,2,3), itemsize=sizeof(np.float64_t))
+
+ for i in range(ngrids):
+ for j in range(3):
+ data[i,0,j] = gles[i,j]
+ data[i,1,j] = gres[i,j]
+
+ less_ids = cvarray(format="B", shape=(ngrids,), itemsize=sizeof(np.uint8_t))
+ greater_ids = cvarray(format="B", shape=(ngrids,), itemsize=sizeof(np.uint8_t))
+
+ best_dim, split_pos, nless, ngreater = \
+ kdtree_get_choices(ngrids, data, self.left_edge, self.right_edge,
+ less_ids, greater_ids)
+
+
+ # If best_dim is -1, then we have found a place where there are no choices.
+ # Exit out and set the node to None.
+ if best_dim == -1:
+ print 'Failed to split grids.'
+ return -1
+
+ split = <Split *> malloc(sizeof(Split))
+ split.dim = best_dim
+ split.pos = split_pos
+
+ # Create a Split
+ self.divide(split)
+
+ less_index = cvarray(format="q", shape=(ngrids,), itemsize=sizeof(np.int64_t))
+ greater_index = cvarray(format="q", shape=(ngrids,), itemsize=sizeof(np.int64_t))
+
+ nless = 0
+ ngreater = 0
+ for i in range(ngrids):
+ if less_ids[i] == 1:
+ less_index[nless] = i
+ nless += 1
+
+ if greater_ids[i] == 1:
+ greater_index[ngreater] = i
+ ngreater += 1
+
+ if nless > 0:
+ less_gles = cvarray(format="d", shape=(nless,3), itemsize=sizeof(np.float64_t))
+ less_gres = cvarray(format="d", shape=(nless,3), itemsize=sizeof(np.float64_t))
+ l_ids = cvarray(format="q", shape=(nless,), itemsize=sizeof(np.int64_t))
+
+ for i in range(nless):
+ index = less_index[i]
+ l_ids[i] = gids[index]
+ for j in range(3):
+ less_gles[i,j] = gles[index,j]
+ less_gres[i,j] = gres[index,j]
+
+ # Populate Left Node
+ #print 'Inserting left node', self.left_edge, self.right_edge
+ self.left.insert_grids(nless, less_gles, less_gres,
+ l_ids, rank, size)
+
+ if ngreater > 0:
+ greater_gles = cvarray(format="d", shape=(ngreater,3), itemsize=sizeof(np.float64_t))
+ greater_gres = cvarray(format="d", shape=(ngreater,3), itemsize=sizeof(np.float64_t))
+ g_ids = cvarray(format="q", shape=(ngreater,), itemsize=sizeof(np.int64_t))
+
+ for i in range(ngreater):
+ index = greater_index[i]
+ g_ids[i] = gids[index]
+ for j in range(3):
+ greater_gles[i,j] = gles[index,j]
+ greater_gres[i,j] = gres[index,j]
+
+ # Populate Right Node
+ #print 'Inserting right node', self.left_edge, self.right_edge
+ self.right.insert_grids(ngreater, greater_gles, greater_gres,
+ g_ids, rank, size)
+
+ return 0
+
+ cdef geo_split(self,
+ np.float64_t[:] gle,
+ np.float64_t[:] gre,
+ int grid_id,
+ int rank,
+ int size):
+ cdef int big_dim = 0
+ cdef int i
+ cdef np.float64_t v, my_max = 0.0
+
+ for i in range(3):
+ v = gre[i] - gle[i]
+ if v > my_max:
+ my_max = v
+ big_dim = i
+
+ new_pos = (gre[big_dim] + gle[big_dim])/2.
+
+ lnew_gle = cvarray(format="d", shape=(3,), itemsize=sizeof(np.float64_t))
+ lnew_gre = cvarray(format="d", shape=(3,), itemsize=sizeof(np.float64_t))
+ rnew_gle = cvarray(format="d", shape=(3,), itemsize=sizeof(np.float64_t))
+ rnew_gre = cvarray(format="d", shape=(3,), itemsize=sizeof(np.float64_t))
+
+ for j in range(3):
+ lnew_gle[j] = gle[j]
+ lnew_gre[j] = gre[j]
+ rnew_gle[j] = gle[j]
+ rnew_gre[j] = gre[j]
+
+ split = <Split *> malloc(sizeof(Split))
+ split.dim = big_dim
+ split.pos = new_pos
+
+ # Create a Split
+ self.divide(split)
+
+ #lnew_gre[big_dim] = new_pos
+ # Populate Left Node
+ #print 'Inserting left node', self.left_edge, self.right_edge
+ self.left.insert_grid(lnew_gle, lnew_gre,
+ grid_id, rank, size)
+
+ #rnew_gle[big_dim] = new_pos
+ # Populate Right Node
+ #print 'Inserting right node', self.left_edge, self.right_edge
+ self.right.insert_grid(rnew_gle, rnew_gre,
+ grid_id, rank, size)
+ return
+
+ cdef void divide(self, Split * split):
+ # Create a Split
+ self.split = split
+
+ cdef np.float64_t[:] le = np.empty(3, dtype='float64')
+ cdef np.float64_t[:] re = np.empty(3, dtype='float64')
+
+ cdef int i
+ for i in range(3):
+ le[i] = self.left_edge[i]
+ re[i] = self.right_edge[i]
+ re[split.dim] = split.pos
+
+ self.left = Node(self, None, None,
+ le, re, self.grid,
+ _lchild_id(self.node_id))
+
+ re[split.dim] = self.right_edge[split.dim]
+ le[split.dim] = split.pos
+ self.right = Node(self, None, None,
+ le, re, self.grid,
+ _rchild_id(self.node_id))
+
+ return
+ #
+ def kd_sum_volume(self):
+ cdef np.float64_t vol = 1.0
+ if (self.left is None) and (self.right is None):
+ if self.grid == -1:
+ return 0.0
+ for i in range(3):
+ vol *= self.right_edge[i] - self.left_edge[i]
+ return vol
+ else:
+ return self.left.kd_sum_volume() + self.right.kd_sum_volume()
+
+ def kd_node_check(self):
+ assert (self.left is None) == (self.right is None)
+ if (self.left is None) and (self.right is None):
+ if self.grid != -1:
+ return np.prod(self.right_edge - self.left_edge)
+ else: return 0.0
+ else:
+ return self.left.kd_node_check()+self.right.kd_node_check()
+
+ def kd_is_leaf(self):
+ cdef int has_l_child = self.left == None
+ cdef int has_r_child = self.right == None
+ assert has_l_child == has_r_child
+ return has_l_child
+
+ cdef int _kd_is_leaf(self):
+ if self.left is None or self.right is None:
+ return 1
+ return 0
+
+ def depth_traverse(self, max_node=None):
+ '''
+ Yields a depth-first traversal of the kd tree always going to
+ the left child before the right.
+ '''
+ current = self
+ previous = None
+ if max_node is None:
+ max_node = np.inf
+ while current is not None:
+ yield current
+ current, previous = step_depth(current, previous)
+ if current is None: break
+ if current.node_id >= max_node:
+ current = current.parent
+ previous = current.right
+
+ def depth_first_touch(self, max_node=None):
+ '''
+ Yields a depth-first traversal of the kd tree always going to
+ the left child before the right.
+ '''
+ current = self
+ previous = None
+ if max_node is None:
+ max_node = np.inf
+ while current is not None:
+ if previous is None or previous.parent != current:
+ yield current
+ current, previous = step_depth(current, previous)
+ if current is None: break
+ if current.node_id >= max_node:
+ current = current.parent
+ previous = current.right
+
+ def breadth_traverse(self):
+ '''
+ Yields a breadth-first traversal of the kd tree always going to
+ the left child before the right.
+ '''
+ current = self
+ previous = None
+ while current is not None:
+ yield current
+ current, previous = step_depth(current, previous)
+
+
+ def viewpoint_traverse(self, viewpoint):
+ '''
+ Yields a viewpoint dependent traversal of the kd-tree. Starts
+ with nodes furthest away from viewpoint.
+ '''
+
+ current = self
+ previous = None
+ while current is not None:
+ yield current
+ current, previous = step_viewpoint(current, previous, viewpoint)
+
+ cdef int point_in_node(self,
+ np.float64_t[:] point):
+ cdef int i
+ cdef int inside = 1
+ for i in range(3):
+ inside *= self.left_edge[i] <= point[i]
+ inside *= self.right_edge[i] > point[i]
+ return inside
+
+ cdef Node _find_node(self, np.float64_t[:] point):
+ while self._kd_is_leaf() == 0:
+ if point[self.split.dim] < self.split.pos:
+ self = self.left
+ else:
+ self = self.right
+ return self
+
+ def find_node(self,
+ np.float64_t[:] point):
+ """
+ Find the AMRKDTree node enclosing a position
+ """
+ assert(self.point_in_node(point))
+ return self._find_node(point)
@cython.boundscheck(False)
@cython.wraparound(False)
@@ -133,270 +681,84 @@
else:
return 0
-def set_dirty(Node trunk, bint state):
- for node in depth_traverse(trunk):
- node.dirty = state
+def step_depth(Node current, Node previous):
+ '''
+ Takes a single step in the depth-first traversal
+ '''
+ if current._kd_is_leaf() == 1: # At a leaf, move back up
+ previous = current
+ current = current.parent
-def kd_traverse(Node trunk, viewpoint=None):
- if viewpoint is None:
- for node in depth_traverse(trunk):
- if _kd_is_leaf(node) == 1 and node.grid != -1:
- yield node
- else:
- for node in viewpoint_traverse(trunk, viewpoint):
- if _kd_is_leaf(node) == 1 and node.grid != -1:
- yield node
+ elif current.parent is previous: # Moving down, go left first
+ previous = current
+ if current.left is not None:
+ current = current.left
+ elif current.right is not None:
+ current = current.right
+ else:
+ current = current.parent
- at cython.boundscheck(False)
- at cython.wraparound(False)
- at cython.cdivision(True)
-cdef add_grid(Node node,
- np.float64_t[:] gle,
- np.float64_t[:] gre,
- int gid,
- int rank,
- int size):
+ elif current.left is previous: # Moving up from left, go right
+ previous = current
+ if current.right is not None:
+ current = current.right
+ else:
+ current = current.parent
- if not should_i_build(node, rank, size):
- return
+ elif current.right is previous: # Moving up from right child, move up
+ previous = current
+ current = current.parent
- if _kd_is_leaf(node) == 1:
- insert_grid(node, gle, gre, gid, rank, size)
- else:
- less_id = gle[node.split.dim] < node.split.pos
- if less_id:
- add_grid(node.left, gle, gre,
- gid, rank, size)
+ return current, previous
- greater_id = gre[node.split.dim] > node.split.pos
- if greater_id:
- add_grid(node.right, gle, gre,
- gid, rank, size)
- return
+def step_viewpoint(Node current,
+ Node previous,
+ viewpoint):
+ '''
+ Takes a single step in the viewpoint based traversal. Always
+ goes to the node furthest away from viewpoint first.
+ '''
+ if current._kd_is_leaf() == 1: # At a leaf, move back up
+ previous = current
+ current = current.parent
+ elif current.split.dim is None: # This is a dead node
+ previous = current
+ current = current.parent
-def add_pygrid(Node node,
- np.float64_t[:] gle,
- np.float64_t[:] gre,
- int gid,
- int rank,
- int size):
+ elif current.parent is previous: # Moving down
+ previous = current
+ if viewpoint[current.split.dim] <= current.split.pos:
+ if current.right is not None:
+ current = current.right
+ else:
+ previous = current.right
+ else:
+ if current.left is not None:
+ current = current.left
+ else:
+ previous = current.left
- """
- The entire purpose of this function is to move everything from ndarrays
- to internal C pointers.
- """
- cdef np.float64_t[:] pgles = cvarray(format="d", shape=(3,), itemsize=sizeof(np.float64_t))
- cdef np.float64_t[:] pgres = cvarray(format="d", shape=(3,), itemsize=sizeof(np.float64_t))
- cdef int j
- for j in range(3):
- pgles[j] = gle[j]
- pgres[j] = gre[j]
+ elif current.right is previous: # Moving up from right
+ previous = current
+ if viewpoint[current.split.dim] <= current.split.pos:
+ if current.left is not None:
+ current = current.left
+ else:
+ current = current.parent
+ else:
+ current = current.parent
- add_grid(node, pgles, pgres, gid, rank, size)
+ elif current.left is previous: # Moving up from left child
+ previous = current
+ if viewpoint[current.split.dim] > current.split.pos:
+ if current.right is not None:
+ current = current.right
+ else:
+ current = current.parent
+ else:
+ current = current.parent
- at cython.boundscheck(False)
- at cython.wraparound(False)
- at cython.cdivision(True)
-cdef insert_grid(Node node,
- np.float64_t[:] gle,
- np.float64_t[:] gre,
- int grid_id,
- int rank,
- int size):
- if not should_i_build(node, rank, size):
- return
-
- # If we should continue to split based on parallelism, do so!
- if should_i_split(node, rank, size):
- geo_split(node, gle, gre, grid_id, rank, size)
- return
-
- cdef int contained = 1
- for i in range(3):
- if gle[i] > node.left_edge[i] or\
- gre[i] < node.right_edge[i]:
- contained *= 0
-
- if contained == 1:
- node.grid = grid_id
- assert(node.grid != -1)
- return
-
- # Split the grid
- cdef int check = split_grid(node, gle, gre, grid_id, rank, size)
- # If check is -1, then we have found a place where there are no choices.
- # Exit out and set the node to None.
- if check == -1:
- node.grid = -1
- return
-
- at cython.boundscheck(False)
- at cython.wraparound(False)
- at cython.cdivision(True)
-cpdef add_grids(Node node,
- int ngrids,
- np.float64_t[:,:] gles,
- np.float64_t[:,:] gres,
- np.int64_t[:] gids,
- int rank,
- int size):
- cdef int i, j, nless, ngreater, index
- cdef np.float64_t[:,:] less_gles, less_gres, greater_gles, greater_gres
- cdef np.int64_t[:] l_ids, g_ids
- if not should_i_build(node, rank, size):
- return
-
- if _kd_is_leaf(node) == 1:
- insert_grids(node, ngrids, gles, gres, gids, rank, size)
- return
-
- less_ids = cvarray(format="q", shape=(ngrids,), itemsize=sizeof(np.int64_t))
- greater_ids = cvarray(format="q", shape=(ngrids,), itemsize=sizeof(np.int64_t))
-
- nless = 0
- ngreater = 0
- for i in range(ngrids):
- if gles[i, node.split.dim] < node.split.pos:
- less_ids[nless] = i
- nless += 1
-
- if gres[i, node.split.dim] > node.split.pos:
- greater_ids[ngreater] = i
- ngreater += 1
-
- #print 'nless: %i' % nless
- #print 'ngreater: %i' % ngreater
-
- if nless > 0:
- less_gles = cvarray(format="d", shape=(nless,3), itemsize=sizeof(np.float64_t))
- less_gres = cvarray(format="d", shape=(nless,3), itemsize=sizeof(np.float64_t))
- l_ids = cvarray(format="q", shape=(nless,), itemsize=sizeof(np.int64_t))
-
- for i in range(nless):
- index = less_ids[i]
- l_ids[i] = gids[index]
- for j in range(3):
- less_gles[i,j] = gles[index,j]
- less_gres[i,j] = gres[index,j]
-
- add_grids(node.left, nless, less_gles, less_gres,
- l_ids, rank, size)
-
- if ngreater > 0:
- greater_gles = cvarray(format="d", shape=(ngreater,3), itemsize=sizeof(np.float64_t))
- greater_gres = cvarray(format="d", shape=(ngreater,3), itemsize=sizeof(np.float64_t))
- g_ids = cvarray(format="q", shape=(ngreater,), itemsize=sizeof(np.int64_t))
-
- for i in range(ngreater):
- index = greater_ids[i]
- g_ids[i] = gids[index]
- for j in range(3):
- greater_gles[i,j] = gles[index,j]
- greater_gres[i,j] = gres[index,j]
-
- add_grids(node.right, ngreater, greater_gles, greater_gres,
- g_ids, rank, size)
-
- return
-
- at cython.boundscheck(False)
- at cython.wraparound(False)
- at cython.cdivision(True)
-cdef int should_i_split(Node node, int rank, int size):
- if node.node_id < size and node.node_id > 0:
- return 1
- return 0
-
- at cython.boundscheck(False)
- at cython.wraparound(False)
- at cython.cdivision(True)
-cdef void insert_grids(Node node,
- int ngrids,
- np.float64_t[:,:] gles,
- np.float64_t[:,:] gres,
- np.int64_t[:] gids,
- int rank,
- int size):
-
- if not should_i_build(node, rank, size) or ngrids == 0:
- return
- cdef int contained = 1
- cdef int check
-
- if ngrids == 1:
- # If we should continue to split based on parallelism, do so!
- if should_i_split(node, rank, size):
- geo_split(node, gles[0,:], gres[0,:], gids[0], rank, size)
- return
-
- for i in range(3):
- contained *= gles[0,i] <= node.left_edge[i]
- contained *= gres[0,i] >= node.right_edge[i]
-
- if contained == 1:
- # print 'Node fully contained, setting to grid: %i' % gids[0]
- node.grid = gids[0]
- assert(node.grid != -1)
- return
-
- # Split the grids
- check = split_grids(node, ngrids, gles, gres, gids, rank, size)
- # If check is -1, then we have found a place where there are no choices.
- # Exit out and set the node to None.
- if check == -1:
- node.grid = -1
- return
-
- at cython.boundscheck(False)
- at cython.wraparound(False)
- at cython.cdivision(True)
-cdef split_grid(Node node,
- np.float64_t[:] gle,
- np.float64_t[:] gre,
- int gid,
- int rank,
- int size):
-
- cdef int j
- cdef np.uint8_t[:] less_ids, greater_ids
- data = cvarray(format="d", shape=(1,2,3), itemsize=sizeof(np.float64_t))
- for j in range(3):
- data[0,0,j] = gle[j]
- data[0,1,j] = gre[j]
-
- less_ids = cvarray(format="B", shape=(1,), itemsize=sizeof(np.uint8_t))
- greater_ids = cvarray(format="B", shape=(1,), itemsize=sizeof(np.uint8_t))
-
- best_dim, split_pos, nless, ngreater = \
- kdtree_get_choices(1, data, node.left_edge, node.right_edge,
- less_ids, greater_ids)
-
- # If best_dim is -1, then we have found a place where there are no choices.
- # Exit out and set the node to None.
- if best_dim == -1:
- return -1
-
-
- split = <Split *> malloc(sizeof(Split))
- split.dim = best_dim
- split.pos = split_pos
-
- # Create a Split
- divide(node, split)
-
- # Populate Left Node
- #print 'Inserting left node', node.left_edge, node.right_edge
- if nless == 1:
- insert_grid(node.left, gle, gre,
- gid, rank, size)
-
- # Populate Right Node
- #print 'Inserting right node', node.left_edge, node.right_edge
- if ngreater == 1:
- insert_grid(node.right, gle, gre,
- gid, rank, size)
-
- return 0
+ return current, previous
@cython.boundscheck(False)
@cython.wraparound(False)
@@ -465,366 +827,3 @@
# Return out unique values
return best_dim, split, nless, ngreater
-
-#@cython.boundscheck(False)
-#@cython.wraparound(False)
-#@cython.cdivision(True)
-cdef int split_grids(Node node,
- int ngrids,
- np.float64_t[:,:] gles,
- np.float64_t[:,:] gres,
- np.int64_t[:] gids,
- int rank,
- int size):
- # Find a Split
- cdef int i, j, index
- cdef np.float64_t[:,:] less_gles, less_gres, greater_gles, greater_gres
- cdef np.int64_t[:] l_ids, g_ids
- if ngrids == 0: return 0
-
- data = cvarray(format="d", shape=(ngrids,2,3), itemsize=sizeof(np.float64_t))
-
- for i in range(ngrids):
- for j in range(3):
- data[i,0,j] = gles[i,j]
- data[i,1,j] = gres[i,j]
-
- less_ids = cvarray(format="B", shape=(ngrids,), itemsize=sizeof(np.uint8_t))
- greater_ids = cvarray(format="B", shape=(ngrids,), itemsize=sizeof(np.uint8_t))
-
- best_dim, split_pos, nless, ngreater = \
- kdtree_get_choices(ngrids, data, node.left_edge, node.right_edge,
- less_ids, greater_ids)
-
-
- # If best_dim is -1, then we have found a place where there are no choices.
- # Exit out and set the node to None.
- if best_dim == -1:
- print 'Failed to split grids.'
- return -1
-
- split = <Split *> malloc(sizeof(Split))
- split.dim = best_dim
- split.pos = split_pos
-
- # Create a Split
- divide(node, split)
-
- less_index = cvarray(format="q", shape=(ngrids,), itemsize=sizeof(np.int64_t))
- greater_index = cvarray(format="q", shape=(ngrids,), itemsize=sizeof(np.int64_t))
-
- nless = 0
- ngreater = 0
- for i in range(ngrids):
- if less_ids[i] == 1:
- less_index[nless] = i
- nless += 1
-
- if greater_ids[i] == 1:
- greater_index[ngreater] = i
- ngreater += 1
-
- if nless > 0:
- less_gles = cvarray(format="d", shape=(nless,3), itemsize=sizeof(np.float64_t))
- less_gres = cvarray(format="d", shape=(nless,3), itemsize=sizeof(np.float64_t))
- l_ids = cvarray(format="q", shape=(nless,), itemsize=sizeof(np.int64_t))
-
- for i in range(nless):
- index = less_index[i]
- l_ids[i] = gids[index]
- for j in range(3):
- less_gles[i,j] = gles[index,j]
- less_gres[i,j] = gres[index,j]
-
- # Populate Left Node
- #print 'Inserting left node', node.left_edge, node.right_edge
- insert_grids(node.left, nless, less_gles, less_gres,
- l_ids, rank, size)
-
- if ngreater > 0:
- greater_gles = cvarray(format="d", shape=(ngreater,3), itemsize=sizeof(np.float64_t))
- greater_gres = cvarray(format="d", shape=(ngreater,3), itemsize=sizeof(np.float64_t))
- g_ids = cvarray(format="q", shape=(ngreater,), itemsize=sizeof(np.int64_t))
-
- for i in range(ngreater):
- index = greater_index[i]
- g_ids[i] = gids[index]
- for j in range(3):
- greater_gles[i,j] = gles[index,j]
- greater_gres[i,j] = gres[index,j]
-
- # Populate Right Node
- #print 'Inserting right node', node.left_edge, node.right_edge
- insert_grids(node.right, ngreater, greater_gles, greater_gres,
- g_ids, rank, size)
-
- return 0
-
-cdef geo_split(Node node,
- np.float64_t[:] gle,
- np.float64_t[:] gre,
- int grid_id,
- int rank,
- int size):
- cdef int big_dim = 0
- cdef int i
- cdef np.float64_t v, my_max = 0.0
-
- for i in range(3):
- v = gre[i] - gle[i]
- if v > my_max:
- my_max = v
- big_dim = i
-
- new_pos = (gre[big_dim] + gle[big_dim])/2.
-
- lnew_gle = cvarray(format="d", shape=(3,), itemsize=sizeof(np.float64_t))
- lnew_gre = cvarray(format="d", shape=(3,), itemsize=sizeof(np.float64_t))
- rnew_gle = cvarray(format="d", shape=(3,), itemsize=sizeof(np.float64_t))
- rnew_gre = cvarray(format="d", shape=(3,), itemsize=sizeof(np.float64_t))
-
- for j in range(3):
- lnew_gle[j] = gle[j]
- lnew_gre[j] = gre[j]
- rnew_gle[j] = gle[j]
- rnew_gre[j] = gre[j]
-
- split = <Split *> malloc(sizeof(Split))
- split.dim = big_dim
- split.pos = new_pos
-
- # Create a Split
- divide(node, split)
-
- #lnew_gre[big_dim] = new_pos
- # Populate Left Node
- #print 'Inserting left node', node.left_edge, node.right_edge
- insert_grid(node.left, lnew_gle, lnew_gre,
- grid_id, rank, size)
-
- #rnew_gle[big_dim] = new_pos
- # Populate Right Node
- #print 'Inserting right node', node.left_edge, node.right_edge
- insert_grid(node.right, rnew_gle, rnew_gre,
- grid_id, rank, size)
- return
-
-cdef void divide(Node node, Split * split):
- # Create a Split
- node.split = split
-
- cdef np.float64_t[:] le = np.empty(3, dtype='float64')
- cdef np.float64_t[:] re = np.empty(3, dtype='float64')
-
- cdef int i
- for i in range(3):
- le[i] = node.left_edge[i]
- re[i] = node.right_edge[i]
- re[split.dim] = split.pos
-
- node.left = Node(node, None, None,
- le, re, node.grid,
- _lchild_id(node.node_id))
-
- re[split.dim] = node.right_edge[split.dim]
- le[split.dim] = split.pos
- node.right = Node(node, None, None,
- le, re, node.grid,
- _rchild_id(node.node_id))
-
- return
-#
-def kd_sum_volume(Node node):
- cdef np.float64_t vol = 1.0
- if (node.left is None) and (node.right is None):
- if node.grid == -1:
- return 0.0
- for i in range(3):
- vol *= node.right_edge[i] - node.left_edge[i]
- return vol
- else:
- return kd_sum_volume(node.left) + kd_sum_volume(node.right)
-
-def kd_node_check(Node node):
- assert (node.left is None) == (node.right is None)
- if (node.left is None) and (node.right is None):
- if node.grid != -1:
- return np.prod(node.right_edge - node.left_edge)
- else: return 0.0
- else:
- return kd_node_check(node.left)+kd_node_check(node.right)
-
-def kd_is_leaf(Node node):
- cdef int has_l_child = node.left == None
- cdef int has_r_child = node.right == None
- assert has_l_child == has_r_child
- return has_l_child
-
-cdef int _kd_is_leaf(Node node):
- if node.left is None or node.right is None:
- return 1
- return 0
-
-def step_depth(Node current, Node previous):
- '''
- Takes a single step in the depth-first traversal
- '''
- if _kd_is_leaf(current) == 1: # At a leaf, move back up
- previous = current
- current = current.parent
-
- elif current.parent is previous: # Moving down, go left first
- previous = current
- if current.left is not None:
- current = current.left
- elif current.right is not None:
- current = current.right
- else:
- current = current.parent
-
- elif current.left is previous: # Moving up from left, go right
- previous = current
- if current.right is not None:
- current = current.right
- else:
- current = current.parent
-
- elif current.right is previous: # Moving up from right child, move up
- previous = current
- current = current.parent
-
- return current, previous
-
-def depth_traverse(Node trunk, max_node=None):
- '''
- Yields a depth-first traversal of the kd tree always going to
- the left child before the right.
- '''
- current = trunk
- previous = None
- if max_node is None:
- max_node = np.inf
- while current is not None:
- yield current
- current, previous = step_depth(current, previous)
- if current is None: break
- if current.node_id >= max_node:
- current = current.parent
- previous = current.right
-
-def depth_first_touch(Node tree, max_node=None):
- '''
- Yields a depth-first traversal of the kd tree always going to
- the left child before the right.
- '''
- current = tree
- previous = None
- if max_node is None:
- max_node = np.inf
- while current is not None:
- if previous is None or previous.parent != current:
- yield current
- current, previous = step_depth(current, previous)
- if current is None: break
- if current.node_id >= max_node:
- current = current.parent
- previous = current.right
-
-def breadth_traverse(Node tree):
- '''
- Yields a breadth-first traversal of the kd tree always going to
- the left child before the right.
- '''
- current = tree
- previous = None
- while current is not None:
- yield current
- current, previous = step_depth(current, previous)
-
-
-def viewpoint_traverse(Node tree, viewpoint):
- '''
- Yields a viewpoint dependent traversal of the kd-tree. Starts
- with nodes furthest away from viewpoint.
- '''
-
- current = tree
- previous = None
- while current is not None:
- yield current
- current, previous = step_viewpoint(current, previous, viewpoint)
-
-def step_viewpoint(Node current,
- Node previous,
- viewpoint):
- '''
- Takes a single step in the viewpoint based traversal. Always
- goes to the node furthest away from viewpoint first.
- '''
- if _kd_is_leaf(current) == 1: # At a leaf, move back up
- previous = current
- current = current.parent
- elif current.split.dim is None: # This is a dead node
- previous = current
- current = current.parent
-
- elif current.parent is previous: # Moving down
- previous = current
- if viewpoint[current.split.dim] <= current.split.pos:
- if current.right is not None:
- current = current.right
- else:
- previous = current.right
- else:
- if current.left is not None:
- current = current.left
- else:
- previous = current.left
-
- elif current.right is previous: # Moving up from right
- previous = current
- if viewpoint[current.split.dim] <= current.split.pos:
- if current.left is not None:
- current = current.left
- else:
- current = current.parent
- else:
- current = current.parent
-
- elif current.left is previous: # Moving up from left child
- previous = current
- if viewpoint[current.split.dim] > current.split.pos:
- if current.right is not None:
- current = current.right
- else:
- current = current.parent
- else:
- current = current.parent
-
- return current, previous
-
-cdef int point_in_node(Node node,
- np.float64_t[:] point):
- cdef int i
- cdef int inside = 1
- for i in range(3):
- inside *= node.left_edge[i] <= point[i]
- inside *= node.right_edge[i] > point[i]
- return inside
-
-cdef Node _find_node(Node node, np.float64_t[:] point):
- while _kd_is_leaf(node) == 0:
- if point[node.split.dim] < node.split.pos:
- node = node.left
- else:
- node = node.right
- return node
-
-def find_node(Node node,
- np.float64_t[:] point):
- """
- Find the AMRKDTree node enclosing a position
- """
- assert(point_in_node(node, point))
- return _find_node(node, point)
-
diff -r d48c4a143f6e3c69c9a1016725d8328f8ea3af53 -r 3ca8a739e5296422ea7954ce8d2717908be25dd6 yt/utilities/lib/contour_finding.pyx
--- a/yt/utilities/lib/contour_finding.pyx
+++ b/yt/utilities/lib/contour_finding.pyx
@@ -25,7 +25,7 @@
OctreeContainer, OctInfo
from yt.geometry.oct_visitors cimport \
Oct
-from .amr_kdtools cimport _find_node, Node
+from .amr_kdtools cimport Node
from .grid_traversal cimport VolumeContainer, PartitionedGrid, \
vc_index, vc_pos_index
import sys
@@ -446,7 +446,7 @@
pos[ax] = vc0.dims[ax]
my_pos[ax] = vc0.dims[ax]-1
get_spos(vc0, pos[0], pos[1], pos[2], ax, spos)
- adj_node = _find_node(trunk, spos)
+ adj_node = trunk._find_node(spos)
vc1 = vcs[adj_node.node_ind]
if spos_contained(vc1, spos):
index = vc_index(vc0, my_pos[0],
diff -r d48c4a143f6e3c69c9a1016725d8328f8ea3af53 -r 3ca8a739e5296422ea7954ce8d2717908be25dd6 yt/utilities/tests/test_amr_kdtree.py
--- a/yt/utilities/tests/test_amr_kdtree.py
+++ b/yt/utilities/tests/test_amr_kdtree.py
@@ -14,8 +14,6 @@
#-----------------------------------------------------------------------------
from yt.utilities.amr_kdtree.api import AMRKDTree
-from yt.utilities.lib.amr_kdtools import depth_traverse, \
- get_left_edge, get_right_edge
import yt.utilities.initial_conditions as ic
import yt.utilities.flagging_methods as fm
from yt.frontends.stream.api import load_uniform_grid, refine_amr
@@ -46,14 +44,14 @@
# This largely reproduces the AMRKDTree.tree.check_tree() functionality
tree_ok = True
- for node in depth_traverse(kd.tree.trunk):
+ for node in kd.tree.trunk.depth_traverse():
if node.grid is None:
continue
grid = ds.index.grids[node.grid - kd._id_offset]
dds = grid.dds
gle = grid.LeftEdge
- nle = get_left_edge(node)
- nre = get_right_edge(node)
+ nle = node.get_left_edge()
+ nre = node.get_right_edge()
li = np.rint((nle-gle)/dds).astype('int32')
ri = np.rint((nre-gle)/dds).astype('int32')
dims = (ri - li).astype('int32')
Repository URL: https://bitbucket.org/yt_analysis/yt/
--
This is a commit notification from bitbucket.org. You are receiving
this because you have the service enabled, addressing the recipient of
this email.
More information about the yt-svn
mailing list