Revision: 56812
http://sourceforge.net/p/brlcad/code/56812
Author: r_weiss
Date: 2013-08-13 21:21:39 +0000 (Tue, 13 Aug 2013)
Log Message:
-----------
Changes to BOT-TIE to remove bit operations.
Modified Paths:
--------------
brlcad/trunk/include/tie.h
brlcad/trunk/src/librt/primitives/bot/tie.c
brlcad/trunk/src/librt/primitives/bot/tie_kdtree.c
brlcad/trunk/src/librt/primitives/bot/tieprivate.h
Modified: brlcad/trunk/include/tie.h
===================================================================
--- brlcad/trunk/include/tie.h 2013-08-13 21:20:26 UTC (rev 56811)
+++ brlcad/trunk/include/tie.h 2013-08-13 21:21:39 UTC (rev 56812)
@@ -107,13 +107,16 @@
*/
tfloat *v; /* 4-bytes or 8-bytes */
void *ptr; /* 4-bytes or 8-bytes */
- uint32_t b; /* 4-bytes (way more than we need, but helps
keep alignment) */
+ int8_t b;
};
struct tie_kdtree_s {
- float axis; /* 4-bytes, intentionally float */
- uint32_t b; /* 4-bytes, bit array to store data about the kdtree node */
- void *data; /* 4-bytes or 8-bytes */
+ struct tie_kdtree_s *left;
+ struct tie_kdtree_s *right;
+ fastf_t axis;
+ int8_t split;
+ int8_t has_children;
+ struct tie_geom_s *data;
};
Modified: brlcad/trunk/src/librt/primitives/bot/tie.c
===================================================================
--- brlcad/trunk/src/librt/primitives/bot/tie.c 2013-08-13 21:20:26 UTC (rev
56811)
+++ brlcad/trunk/src/librt/primitives/bot/tie.c 2013-08-13 21:21:39 UTC (rev
56812)
@@ -86,12 +86,15 @@
if (u.v[2] > u.v[1] && u.v[2] > u.v[0]) {
i1 = 0;
i2 = 1;
+ tri->b = 2;
} else if (u.v[1] > u.v[2] && u.v[1] > u.v[0]) {
i1 = 0;
i2 = 2;
+ tri->b = 1;
} else {
i1 = 1;
i2 = 2;
+ tri->b = 0;
}
/* compute u1, v2, u2, v2 */
@@ -100,12 +103,6 @@
tri->v[0] = v1.v[i2] - tri->data[0].v[i2];
tri->v[1] = v2.v[i2] - tri->data[0].v[i2];
- /* !!! what? no entiendo. */
- if (i1 == 0 && i2 == 1)
- tri->b = tri->b + 2;
- else if (i1 == 0)
- tri->b = tri->b + 1;
-
/* Compute DotVN */
VSCALE(v1.v, tri->data[0].v, -1.0);
tri->data[2].v[0] = VDOT( v1.v, tri->data[1].v);
@@ -236,7 +233,7 @@
}
/* Extracting value of splitting plane from the kdtree */
- split = tie->kdtree->b & (uint32_t)0x3L;
+ split = tie->kdtree->split;
/* Initialize ray segment */
if (ray->dir[split] < 0.0)
@@ -271,17 +268,22 @@
*
* Gordon Stoll's Mantra - Rays are Measured in Millions :-)
*/
- while (node && node->data && TIE_HAS_CHILDREN(node->b)) {
+ while (node->has_children) {
ray->kdtree_depth++;
/* Retrieve the splitting plane */
- split = node->b & (uint32_t)0x3L;
+ split = node->split;
/* Calculate the projected 1d distance to splitting axis */
dist = (node->axis - ray->pos[split]) * dirinv[split];
- temp[0] = &((struct tie_kdtree_s *)(node->data))[ab[split]];
- temp[1] = &((struct tie_kdtree_s *)(node->data))[1-ab[split]];
+ if (!ab[split]) {
+ temp[0] = node->left;
+ temp[1] = node->right;
+ } else {
+ temp[0] = node->right;
+ temp[1] = node->left;
+ }
i = near >= dist; /* Node B Only? */
node = temp[i];
@@ -338,8 +340,8 @@
/* Extract i1 and i2 indices from the 'b' field */
v = tri->v;
- i1 = TIE_TAB1[tri->b & (uint32_t)0x7L];
- i2 = TIE_TAB1[3 + (tri->b & (uint32_t)0x7L)];
+ i1 = TIE_TAB1[tri->b];
+ i2 = TIE_TAB1[3 + tri->b];
/* Compute U and V */
u0 = t.pos[i1] - tri->data[0].v[i1];
@@ -425,9 +427,9 @@
unsigned int i;
/* expand the tri buffer if needed */
- if (tnum + tie->tri_num > tie->tri_num_alloc) {
- tie->tri_list = (struct tie_tri_s *)bu_realloc( tie->tri_list,
sizeof(struct tie_tri_s) * (tie->tri_num + tnum), "tri_list during tie_push");
- tie->tri_num_alloc += tnum;
+ if (tie->tri_num + tnum > tie->tri_num_alloc) {
+ tie->tri_num_alloc = tie->tri_num + tnum;
+ tie->tri_list = (struct tie_tri_s *)bu_realloc(tie->tri_list,
tie->tri_num_alloc * sizeof(struct tie_tri_s), "tri_list during tie_push");
}
for (i = 0; i < tnum; i++) {
Modified: brlcad/trunk/src/librt/primitives/bot/tie_kdtree.c
===================================================================
--- brlcad/trunk/src/librt/primitives/bot/tie_kdtree.c 2013-08-13 21:20:26 UTC
(rev 56811)
+++ brlcad/trunk/src/librt/primitives/bot/tie_kdtree.c 2013-08-13 21:21:39 UTC
(rev 56812)
@@ -116,20 +116,24 @@
static void
tie_kdtree_free_node(struct tie_kdtree_s *node)
{
- if (node && TIE_HAS_CHILDREN(node->b)) {
+ if (node->has_children) {
/* Node Data is KDTREE Children, Recurse */
- tie_kdtree_free_node(&((struct tie_kdtree_s *)(node->data))[0]);
- tie_kdtree_free_node(&((struct tie_kdtree_s *)(node->data))[1]);
+ tie_kdtree_free_node(node->left);
+ tie_kdtree_free_node(node->right);
} else {
/* This node points to a geometry node, free it */
- struct tie_geom_s *tmp;
- tmp = (struct tie_geom_s *)node->data;
- if (tmp) {
- if (tmp->tri_num > 0) {
- bu_free(tmp->tri_list, "tri_list");
- }
- bu_free(tmp, "data");
+ if (node->left) {
+ bu_free(node->left, "node left");
}
+ if (node->right) {
+ bu_free(node->right, "node right");
+ }
+ if (node->data && node->data->tri_num > 0) {
+ bu_free(node->data->tri_list, "tri_list");
+ }
+ if (node->data) {
+ bu_free(node->data, "data");
+ }
}
}
@@ -584,6 +588,7 @@
/* Terminating criteria for KDTREE subdivision */
if (node_gd->tri_num <= TIE_KDTREE_NODE_MAX || depth > tie->max_depth) {
tie->stat += node_gd->tri_num;
+ node->has_children = 0;
return;
}
@@ -595,15 +600,14 @@
bu_bomb("Illegal tie kdtree method\n");
/* Allocate 2 children nodes for the parent node */
- node->data = bu_calloc(2, sizeof(struct tie_kdtree_s), __FUNCTION__);
- node->b = 0;
+ node->left = (struct tie_kdtree_s *)bu_calloc(1, sizeof(struct
tie_kdtree_s), "tie node left");
+ node->left->data = (struct tie_geom_s *)bu_calloc(1, sizeof(struct
tie_geom_s), "tie node left tie_geom_s");
+ node->right = (struct tie_kdtree_s *)bu_calloc(1, sizeof(struct
tie_kdtree_s), "tie node right");
+ node->right->data = (struct tie_geom_s *)bu_calloc(1, sizeof(struct
tie_geom_s), "tie node right tie_geom_s");
- BU_ALLOC(((struct tie_kdtree_s *)(node->data))[0].data, struct tie_geom_s);
- BU_ALLOC(((struct tie_kdtree_s *)(node->data))[1].data, struct tie_geom_s);
-
/* Initialize Triangle List */
- child[0] = ((struct tie_geom_s *)(((struct tie_kdtree_s
*)(node->data))[0].data));
- child[1] = ((struct tie_geom_s *)(((struct tie_kdtree_s
*)(node->data))[1].data));
+ child[0] = node->left->data;
+ child[1] = node->right->data;
child[0]->tri_list = (struct tie_tri_s **)bu_calloc(node_gd->tri_num,
sizeof(struct tie_tri_s *), "child[0]->tri_list");
child[0]->tri_num = 0;
@@ -677,13 +681,14 @@
VMOVE(lmin[1], cmin[1].v);
VMOVE(lmax[0], cmax[0].v);
VMOVE(lmax[1], cmax[1].v);
- tie_kdtree_build(tie, &((struct tie_kdtree_s *)(node->data))[0], depth+1,
lmin[0], lmax[0]);
- tie_kdtree_build(tie, &((struct tie_kdtree_s *)(node->data))[1], depth+1,
lmin[1], lmax[1]);
+ tie_kdtree_build(tie, node->left, depth+1, lmin[0], lmax[0]);
+ tie_kdtree_build(tie, node->right, depth+1, lmin[1], lmax[1]);
}
/* Assign the splitting dimension to the node */
/* If we've come this far then YES, this node DOES have child nodes, MARK
it as so. */
- node->b = TIE_SET_HAS_CHILDREN(node->b) + split;
+ node->split = split;
+ node->has_children = 1;
}
/*************************************************************
Modified: brlcad/trunk/src/librt/primitives/bot/tieprivate.h
===================================================================
--- brlcad/trunk/src/librt/primitives/bot/tieprivate.h 2013-08-13 21:20:26 UTC
(rev 56811)
+++ brlcad/trunk/src/librt/primitives/bot/tieprivate.h 2013-08-13 21:21:39 UTC
(rev 56812)
@@ -30,14 +30,6 @@
extern "C" {
#endif
-/* The last three bits of the 'b' field in the kdtree are used to
- * store data about the object. 0x4L marks if the node has children
- * (is set to 0 for a leaf), the last two are the encoding for the
- * splitting plane.
- */
-#define TIE_HAS_CHILDREN(bits) (bits & (uint32_t)0x4L)
-#define TIE_SET_HAS_CHILDREN(bits) (bits | (uint32_t)0x4L)
-
struct tie_geom_s {
struct tie_tri_s **tri_list; /* 4-bytes or 8-bytes */
uint32_t tri_num; /* 4-bytes */
This was sent by the SourceForge.net collaborative development platform, the
world's largest Open Source development site.
------------------------------------------------------------------------------
Get 100% visibility into Java/.NET code with AppDynamics Lite!
It's a free troubleshooting tool designed for production.
Get down to code-level detail for bottlenecks, with <2% overhead.
Download for free and get started troubleshooting in minutes.
http://pubads.g.doubleclick.net/gampad/clk?id=48897031&iu=/4140/ostg.clktrk
_______________________________________________
BRL-CAD Source Commits mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/brlcad-commits
