# initialize_aabbtree

## `initialize_aabbtree(V, F=None, vmin=None, vmax=None)`

Axis-Aligned Bounding Box hierarchy for efficient computation

Computes an AABB tree by recursively dividing cells along the biggest dimension. May be called for any dimension and simplex size

Parameters:

Name Type Description Default
`V` `numpy double array`

Matrix of mesh vertex coordinates

required
`F` `numpy int array, optional (default None)`

Matrix of element indices into V (if None, treated as point cloud)

`None`

Returns:

Name Type Description
`C` `numpy double array `

Matrix of box centers

`W` `numpy double array `

Matrix of box widths

`CH` `numpy int array`

Matrix of child indeces (-1 if leaf node)

`PAR` `numpy int array `

Vector of immediate parent indeces (to traverse upwards)

`D` `numpy int array`

Vector of tree depths

`tri_indices` `numpy int array`

Vector of element indices (-1 if not leaf node)

#### Notes

This code is purposefully not optimized beyond asymptotics for simplicity in understanding its functionality and translating it to other programming languages beyond prototyping.

Examples:

``````from gpytoolbox import initialize_aabbtree
P = np.array([[0,0,0],[0.1,0,0],[0,0,0],[0.02,0.1,0],[1,1,0.9],[1,1,1]])
F = np.array([[0,1],[2,3],[4,5]],dtype=int)
C,W,CH,PAR,D,tri_ind = gpytoolbox.initialize_aabbtree(P,F)
``````
Source code in `src/gpytoolbox/initialize_aabbtree.py`
 ``` 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101``` ``````def initialize_aabbtree(V,F=None,vmin=None,vmax=None): """Axis-Aligned Bounding Box hierarchy for efficient computation Computes an AABB tree by recursively dividing cells along the biggest dimension. May be called for any dimension and simplex size Parameters ---------- V : numpy double array Matrix of mesh vertex coordinates F : numpy int array, optional (default None) Matrix of element indices into V (if None, treated as point cloud) Returns ------- C : numpy double array Matrix of box centers W : numpy double array Matrix of box widths CH : numpy int array Matrix of child indeces (-1 if leaf node) PAR : numpy int array Vector of immediate parent indeces (to traverse upwards) D : numpy int array Vector of tree depths tri_indices : numpy int array Vector of element indices (-1 if *not* leaf node) See Also -------- traverse_aabbtree, initialize_quadtree. Notes ----- This code is *purposefully* not optimized beyond asymptotics for simplicity in understanding its functionality and translating it to other programming languages beyond prototyping. Examples -------- ```python from gpytoolbox import initialize_aabbtree P = np.array([[0,0,0],[0.1,0,0],[0,0,0],[0.02,0.1,0],[1,1,0.9],[1,1,1]]) F = np.array([[0,1],[2,3],[4,5]],dtype=int) C,W,CH,PAR,D,tri_ind = gpytoolbox.initialize_aabbtree(P,F) ``` """ if (F is None): F = np.linspace(0,V.shape[0]-1,V.shape[0],dtype=int)[:,None] # We start with a bounding box dim = V.shape[1] simplex_size = F.shape[1] num_s = F.shape[0] if (vmin is None): vmin = np.amin(V,axis=0) if (vmax is None): vmax = np.amax(V,axis=0) C = (vmin + vmax)/2.0 C = C[None,:] #print(C) # We need to compute this once, we'll need it for the subdivision: vmin_big = 10000*np.ones((num_s,dim)) vmax_big = -10000*np.ones((num_s,dim)) for j in range(dim): for i in range(simplex_size): vmax_big[:,j] = np.amax(np.hstack((V[F[:,i],j][:,None],vmax_big[:,j][:,None])),axis=1)[:] vmin_big[:,j] = np.amin(np.hstack((V[F[:,i],j][:,None],vmin_big[:,j][:,None])),axis=1)[:] W = np.reshape(vmax-vmin,(1,dim)) CH = np.tile(np.array([[-1]],dtype=int),(1,2)) # for now it's leaf node D = np.array([1],dtype=int) PAR = np.array([-1],dtype=int) # supreme Neanderthal ancestral node tri_indices = np.array([-1]) # this will have the index in leaf nodes (at least temporarily) tri_index_list = [ list(range(F.shape[0])) ] # Now, we will loop box_ind = -1 while True: box_ind = box_ind + 1 if box_ind>=C.shape[0]: break is_child = (CH[box_ind,1]==-1) assert(is_child) # This check should be superfluous I think #tris_in_box = is_in_box(V,F,C[box_ind,:],W[box_ind,:]) tris_in_box = tri_index_list[box_ind] # print(box_ind) # print(tris_in_box) # print(tri_indices) # print(tris_in_box) num_tris_in_box = len(tris_in_box) # print(num_tris_in_box) assert(num_tris_in_box>0) # There can't be a node with zero triangles... if (is_child and num_tris_in_box>=2): # Does this quad contain more than one triangle? Then subdivide it C,W,CH,PAR,D,tri_indices,tri_index_list = subdivide_box(box_ind,V,F,tris_in_box,C,W,CH,PAR,D,tri_indices,tri_index_list,vmin_big,vmax_big) if (is_child and num_tris_in_box==1): tri_indices[box_ind] = tris_in_box[0] # Check this?? return C,W,CH,PAR,D,tri_indices ``````