2 // This code written in 2010 by Forest Hale (lordhavoc ghdigital com), and placed into public domain.
8 static int BIH_BuildNode(bih_t *bih, int numchildren, int *leaflist)
25 return -1-leaflist[0];
26 // if we run out of nodes it's the caller's fault, but don't crash
27 if (bih->numnodes == bih->maxnodes)
30 bih->error = BIHERROR_OUT_OF_NODES;
31 return -1-leaflist[0];
33 nodenum = bih->numnodes++;
34 node = bih->nodes + nodenum;
35 // calculate bounds of children
36 child = bih->leafs + leaflist[0];
37 mins[0] = child->mins[0];
38 mins[1] = child->mins[1];
39 mins[2] = child->mins[2];
40 maxs[0] = child->maxs[0];
41 maxs[1] = child->maxs[1];
42 maxs[2] = child->maxs[2];
43 for (i = 1;i < numchildren;i++)
45 child = bih->leafs + leaflist[i];
46 if (mins[0] > child->mins[0]) mins[0] = child->mins[0];
47 if (mins[1] > child->mins[1]) mins[1] = child->mins[1];
48 if (mins[2] > child->mins[2]) mins[2] = child->mins[2];
49 if (maxs[0] < child->maxs[0]) maxs[0] = child->maxs[0];
50 if (maxs[1] < child->maxs[1]) maxs[1] = child->maxs[1];
51 if (maxs[2] < child->maxs[2]) maxs[2] = child->maxs[2];
53 size[0] = maxs[0] - mins[0];
54 size[1] = maxs[1] - mins[1];
55 size[2] = maxs[2] - mins[2];
56 // store bounds for node
57 node->mins[0] = mins[0];
58 node->mins[1] = mins[1];
59 node->mins[2] = mins[2];
60 node->maxs[0] = maxs[0];
61 node->maxs[1] = maxs[1];
62 node->maxs[2] = maxs[2];
65 if (size[0] < size[1]) longestaxis = 1;
66 if (size[longestaxis] < size[2]) longestaxis = 2;
67 // iterate possible split axis choices:
68 // longest (best raytracing performance)
69 // x (longest had identical children, try X axis)
70 // y (longest and X axis had identical children, try Y axis)
71 // z (longest and X and Y axes had identical children, try Z axis)
72 // arbitrary (all children have same bounds, divide the list)
75 // if longest axis fails, we try each one until something works
76 // (this also can fail, see below)
80 case 0: axis = longestaxis;break;
81 case 1: axis = (longestaxis + 1) % 3;break;
82 case 2: axis = (longestaxis + 2) % 3;break;
84 // sort children into front and back lists
85 node->type = BIH_SPLITX + axis;
86 splitdist = (node->mins[axis] + node->maxs[axis]) * 0.5f;
89 for (i = 0;i < numchildren;i++)
91 child = bih->leafs + leaflist[i];
92 d = (child->mins[axis] + child->maxs[axis]) * 0.5f;
94 bih->leafsortscratch[back++] = leaflist[i];
96 leaflist[front++] = leaflist[i];
98 // now copy the back ones into the space made in the leaflist for them
100 memcpy(leaflist + front, bih->leafsortscratch, back*sizeof(leaflist[0]));
101 // if both sides have some children, it's good enough for us.
107 // the almost impossible case happened; all children have identical
108 // bounds, so just divide them arbitrarily into two lists.
109 node->type = BIH_SPLITX;
110 back = numchildren >> 1;
111 front = numchildren - back;
114 // we now have front and back children divided in leaflist...
115 node->children[0] = BIH_BuildNode(bih, front, leaflist);
116 node->children[1] = BIH_BuildNode(bih, back, leaflist + front);
120 int BIH_Build(bih_t *bih, int numleafs, bih_leaf_t *leafs, int maxnodes, bih_node_t *nodes, int *temp_leafsort, int *temp_leafsortscratch)
124 memset(bih, 0, sizeof(*bih));
125 bih->numleafs = numleafs;
127 bih->leafsort = temp_leafsort;
128 bih->leafsortscratch = temp_leafsortscratch;
130 bih->maxnodes = maxnodes;
133 // clear things we intend to rebuild
134 memset(bih->nodes, 0, sizeof(bih->nodes[0]) * bih->maxnodes);
135 for (i = 0;i < bih->numleafs;i++)
136 bih->leafsort[i] = i;
138 BIH_BuildNode(bih, bih->numleafs, bih->leafsort);