/* Last edited on 2021-07-14 16:44:16 by jstolfi */ size_t kdtom_node_size(ppv_dim_t d); /* Returns the size in bytes of a {kdtom_t} record for a {d}-dimensional k-d-tree, including the {size} vector but not including any additional fields specific to each variant. */ size_t kdtom_node_size(ppv_dim_t d) { size_t fix_bytes = sizeof(kdtom_t); /* Fixed fields, incl. {size} pointer. */ size_t szv_bytes = d * sizeof(ppv_size_t); /* The {size} vector eleements. */ size_t tot_bytes = roundup(fix_bytes + szv_bytes, 8); return tot_bytes; } kdtom_kind_TRANS, /* The voxel block is shifted and padded. */ kdtom_kind_IXMAP /* The voxel indices are permuted and/or reversed */ case kdtom_kind_TRANS: return kdtom_trans_get_sample((kdtom_trans_t *)T, ix); case kdtom_kind_IXMAP: return kdtom_ixmap_get_sample((kdtom_ixmap_t *)T, ix); case kdtom_kind_TRANS: return kdtom_trans_bytesize((kdtom_trans_t *)T, total); case kdtom_kind_IXMAP: return kdtom_ixmap_bytesize((kdtom_ixmap_t *)T, total); /* Replace any shared-element arrays by deep copies:*/ if (T0->kind == kdtom_kind_ARRAY) { T0 = (kdtom_t *)copied_array_node(B0); } if (T1->kind == kdtom_kind_ARRAY) { T1 = (kdtom_t *)copied_array_node(B1); } if (T->kind == kdtom_kind_split) { /* Remove the storage sharing from the descendant nodes: */ kdtom_split_t *Ts = (kdtom_split_t)T; if (Ts.sub[0]->kind == kdtom_kind_ARRAY) { Ts.sub[0] = (kdtom_t *)copied_array_node(B0); } if (Ts.sub[1]->kind == kdtom_kind_ARRAY) { Ts.sub[1] = (kdtom_t *)copied_array_node(B1); } } auto kdtom_array_t *copied_array_node(ppv_array_t *B); /* Returns a {kdtom_array_t} node that has the same size as {B} but a a newly alocated sample storage area, after copying into it the sample values of the voxels of {B}. */ kdtom_array_t *copied_array_node(ppv_array_t *B) { ppv_array_t *C = ppv_array_new(d, B->size, B->maxsmp); ppv_array_assign(C, B); kdtom_array_t *Ta = kdtom_array_make(C); return Ta; } void tkdc_test_clip(kdtom_const_t *T, sign_t loclip, sign_t hiclip) { fprintf(stderr, "Testing {kdtom_clip} loclip = %+d hiclip =%+d ...\n", loclip, hiclip); ppv_dim_t d = T->h.d; kdtom_test_show_box(stderr, d, "original box = [ ", T->h.ixlo, T->h.size, " ]\n"); ppv_index_t ixlo_box[d]; /* {ixlo} value of clip box. */ ppv_size_t size_box[d]; /* Size vector of clip box. */ ppv_index_t ixlo_new[d]; /* Expected {T.h.ixlo} after clipping. */ ppv_size_t size_new[d]; /* Expected {T.h.size} after clipping. */ for (ppv_axis_t ax = 0; ax < d; ax++) { /* Get current core index range {ixlok_old..ixhik_old} on axis {ax}: */ ppv_index_t ixlok_old = T->h.ixlo[ax]; ppv_index_t ixhik_old = ixlok_old + T->h.size[ax] - 1; /* Select the clipping box index range {ixlok_box..ixhik_box} on axis {ax}: */ ppv_index_t ixa[5] = { ixlok_old - 2, ixlok_old, ixlok_old + 1, ixhik_old, ixhik_old + 1}; ppv_index_t ixb[5] = { ixlok_old - 1, ixlok_old, ixhik_old - 1, ixhik_old, ixhik_old + 2}; ppv_index_t ixlok_box = ixa[loclip+2]; ppv_index_t ixhik_box = ixb[hiclip+2]; bool_t empty_box = (ixlok_box > ixhik_box); if (empty_box) { ixlok_box = 0; ixhik_box = -1; } ixlo_box[ax] = ixlok_box; size_box[ax] = ixhik_box - ixlok_box + 1; /* Set index range along other axes as non-clipping: */ for (ppv_axis_t k = 0; k < d; k++) { if (k != ax) { ixlo_box[k] = (empty_box ? 0 : T->h.ixlo[k] - 1); size_box[k] = (empty_box ? 0 : T->h.size[k] + 2); } } kdtom_test_show_box(stderr, d, "clipping box = [ ", ixlo_box, size_box, " ]\n"); /* Compute the expected clipped core box {ixlo_new[ax],size_new[ax]}: */ kdtom_intersect_boxes(d, T->h.ixlo, T->h.size, ixlo_box, size_box, ixlo_new, size_new); kdtom_test_show_box(stderr, d, "expected box = [ ", ixlo_new, size_new, " ]\n"); kdtom_t *S = kdtom_clip((kdtom_t *)T, ixlo_box, size_box); kdtom_test_show_box(stderr, d, "clipped box = [ ", S->ixlo, S->size, " ]\n"); demand(S->d == T->h.d, "{kdtom_clip} bug: {S.d}"); demand(S->maxsmp == T->h.maxsmp, "{kdtom_clip} bug: {S.maxsmp}"); demand(S->fill == T->h.fill, "{kdtom_clip} bug: {S.fill}"); for (ppv_axis_t k = 0; k < d; k++) { demand(S->ixlo[k] == ixlo_new[k], "{kdtom_clip} bug: {S.ixlo}"); demand(S->size[k] == size_new[k], "{kdtom_clip} bug: {S.size}"); } demand(S->kind == kdtom_kind_CONST, "{kdtom_clip} bug: {S.kind}"); tkdc_test_get_sample((kdtom_const_t *)S, ixlo_new, size_new); fprintf(stderr, "\n"); } } void kdtom_node_init(kdtom_t *T, ppv_dim_t d, char **pendP) { char *pend = (*pendP); /* Set the {d} field: */ T->d = d; /* Alocate the {size} vector: */ size_t sizv_bytes = d * sizeof(ppv_size_t); /* Bytesize of the {size} vector. */ T->size = (ppv_size_t *)pend; pend += sizv_bytes; /* Update free pointer: */ (*pendP) = pend; return T; } /* ----------------------------------------------------------------------*/ /* kdtom_split_simplify: */ bool_t sub1_has_no_core = kdtom_box_is_empty(d, sub1->size); bool_t sub1_is_all_core = kdtom_boxes_are_equal(d, sub1->ixlo, sub1->size, ixlo, size); bool_t sub0_has_no_core = kdtom_box_is_empty(d, sub0->size); bool_t sub0_is_all_core = kdtom_boxes_are_equal(d, sub0->ixlo, sub0->size, ixlo, size); /* See if the split can be simplified: */ if (sub0_has_no_core && (sub0->fill == fill)) { /* We don't need {sub0}: */ if (sub1_is_all-core || (sub1->fill == fill)) { /* We can let {T} be just {sub1} shifted by {ixlo1}: */ T = sub1; kdtom_translate(T, ixlo1); } else { /* We need a split node to clip {sub1}: */ sub0 = NULL; } } ?? if (sub1_has_no_core && (sub0->fill == fill)) { /* We can return just {sub0}: */ T = sub0; } else { /* Try to join them info a single node: */ T = kdtom_join_nodes(size, ax, sub0, size0, sub1, size1); if (T == NULL) { /* Must create a real {kdtom_split_t} node: */ } } /* ---------------------------------------------------------------------- */