]> git.xonotic.org Git - xonotic/darkplaces.git/blob - bih.c
Q1BSP: fix misaligned memory access
[xonotic/darkplaces.git] / bih.c
1
2 // This code written in 2010 by Ashley Rose Hale (LadyHavoc) (darkplacesengine gmail com), and placed into public domain.
3
4 #include <stdlib.h>
5 #include <string.h>
6 #include "bih.h"
7
8 static int BIH_BuildNode(bih_t *bih, int numchildren, int *leaflist, float *totalmins, float *totalmaxs)
9 {
10         int i;
11         int j;
12         int longestaxis;
13         int axis = 0;
14         int nodenum;
15         int front = 0;
16         int back = 0;
17         bih_node_t *node;
18         bih_leaf_t *child;
19         float splitdist;
20         float d;
21         float mins[3];
22         float maxs[3];
23         float size[3];
24         float frontmins[3];
25         float frontmaxs[3];
26         float backmins[3];
27         float backmaxs[3];
28         // calculate bounds of children
29         child = bih->leafs + leaflist[0];
30         mins[0] = child->mins[0];
31         mins[1] = child->mins[1];
32         mins[2] = child->mins[2];
33         maxs[0] = child->maxs[0];
34         maxs[1] = child->maxs[1];
35         maxs[2] = child->maxs[2];
36         for (i = 1;i < numchildren;i++)
37         {
38                 child = bih->leafs + leaflist[i];
39                 if (mins[0] > child->mins[0]) mins[0] = child->mins[0];
40                 if (mins[1] > child->mins[1]) mins[1] = child->mins[1];
41                 if (mins[2] > child->mins[2]) mins[2] = child->mins[2];
42                 if (maxs[0] < child->maxs[0]) maxs[0] = child->maxs[0];
43                 if (maxs[1] < child->maxs[1]) maxs[1] = child->maxs[1];
44                 if (maxs[2] < child->maxs[2]) maxs[2] = child->maxs[2];
45         }
46         size[0] = maxs[0] - mins[0];
47         size[1] = maxs[1] - mins[1];
48         size[2] = maxs[2] - mins[2];
49         // provide bounds to caller
50         totalmins[0] = mins[0];
51         totalmins[1] = mins[1];
52         totalmins[2] = mins[2];
53         totalmaxs[0] = maxs[0];
54         totalmaxs[1] = maxs[1];
55         totalmaxs[2] = maxs[2];
56         // if we run out of nodes it's the caller's fault, but don't crash
57         if (bih->numnodes == bih->maxnodes)
58         {
59                 if (!bih->error)
60                         bih->error = BIHERROR_OUT_OF_NODES;
61                 return 0;
62         }
63         nodenum = bih->numnodes++;
64         node = bih->nodes + nodenum;
65         // store bounds for node
66         node->mins[0] = mins[0];
67         node->mins[1] = mins[1];
68         node->mins[2] = mins[2];
69         node->maxs[0] = maxs[0];
70         node->maxs[1] = maxs[1];
71         node->maxs[2] = maxs[2];
72         node->front = 0;
73         node->back = 0;
74         node->frontmin = 0;
75         node->backmax = 0;
76         memset(node->children, -1, sizeof(node->children));
77         // check if there are few enough children to store an unordered node
78         if (numchildren <= BIH_MAXUNORDEREDCHILDREN)
79         {
80                 node->type = BIH_UNORDERED;
81                 for (j = 0;j < numchildren;j++)
82                         node->children[j] = leaflist[j];
83                 return nodenum;
84         }
85         // pick longest axis
86         longestaxis = 0;
87         if (size[0] < size[1]) longestaxis = 1;
88         if (size[longestaxis] < size[2]) longestaxis = 2;
89         // iterate possible split axis choices, starting with the longest axis, if
90         // all fail it means all children have the same bounds and we simply split
91         // the list in half because each node can only have two children.
92         for (j = 0;j < 3;j++)
93         {
94                 // pick an axis
95                 axis = (longestaxis + j) % 3;
96                 // sort children into front and back lists
97                 splitdist = (node->mins[axis] + node->maxs[axis]) * 0.5f;
98                 front = 0;
99                 back = 0;
100                 for (i = 0;i < numchildren;i++)
101                 {
102                         child = bih->leafs + leaflist[i];
103                         d = (child->mins[axis] + child->maxs[axis]) * 0.5f;
104                         if (d < splitdist)
105                                 bih->leafsortscratch[back++] = leaflist[i];
106                         else
107                                 leaflist[front++] = leaflist[i];
108                 }
109                 // now copy the back ones into the space made in the leaflist for them
110                 if (back)
111                         memcpy(leaflist + front, bih->leafsortscratch, back*sizeof(leaflist[0]));
112                 // if both sides have some children, it's good enough for us.
113                 if (front && back)
114                         break;
115         }
116         if (j == 3)
117         {
118                 // somewhat common case: no good choice, divide children arbitrarily
119                 axis = 0;
120                 back = numchildren >> 1;
121                 front = numchildren - back;
122         }
123
124         // we now have front and back children divided in leaflist...
125         node->type = (bih_nodetype_t)((int)BIH_SPLITX + axis);
126         node->front = BIH_BuildNode(bih, front, leaflist, frontmins, frontmaxs);
127         node->frontmin = frontmins[axis];
128         node->back = BIH_BuildNode(bih, back, leaflist + front, backmins, backmaxs);
129         node->backmax = backmaxs[axis];
130         return nodenum;
131 }
132
133 int BIH_Build(bih_t *bih, int numleafs, bih_leaf_t *leafs, int maxnodes, bih_node_t *nodes, int *temp_leafsort, int *temp_leafsortscratch)
134 {
135         int i;
136
137         memset(bih, 0, sizeof(*bih));
138         bih->numleafs = numleafs;
139         bih->leafs = leafs;
140         bih->leafsort = temp_leafsort;
141         bih->leafsortscratch = temp_leafsortscratch;
142         bih->numnodes = 0;
143         bih->maxnodes = maxnodes;
144         bih->nodes = nodes;
145
146         // clear things we intend to rebuild
147         memset(bih->nodes, 0, sizeof(bih->nodes[0]) * bih->maxnodes);
148         for (i = 0;i < bih->numleafs;i++)
149                 bih->leafsort[i] = i;
150
151         bih->rootnode = BIH_BuildNode(bih, bih->numleafs, bih->leafsort, bih->mins, bih->maxs);
152         return bih->error;
153 }
154
155 static void BIH_GetTriangleListForBox_Node(const bih_t *bih, int nodenum, int maxtriangles, int *trianglelist_idx, int *trianglelist_surf, int *numtrianglespointer, const float *mins, const float *maxs)
156 {
157         int axis;
158         bih_node_t *node;
159         bih_leaf_t *leaf;
160         for(;;)
161         {
162                 node = bih->nodes + nodenum;
163                 // check if this is an unordered node (which holds an array of leaf numbers)
164                 if (node->type == BIH_UNORDERED)
165                 {
166                         for (axis = 0;axis < BIH_MAXUNORDEREDCHILDREN && node->children[axis] >= 0;axis++)
167                         {
168                                 leaf = bih->leafs + node->children[axis];
169                                 if (mins[0] > leaf->maxs[0] || maxs[0] < leaf->mins[0]
170                                  || mins[1] > leaf->maxs[1] || maxs[1] < leaf->mins[1]
171                                  || mins[2] > leaf->maxs[2] || maxs[2] < leaf->mins[2])
172                                         continue;
173                                 switch(leaf->type)
174                                 {
175                                 case BIH_RENDERTRIANGLE:
176                                         if (*numtrianglespointer >= maxtriangles)
177                                         {
178                                                 ++*numtrianglespointer; // so the caller can detect overflow
179                                                 break;
180                                         }
181                                         if(trianglelist_surf)
182                                                 trianglelist_surf[*numtrianglespointer] = leaf->surfaceindex;
183                                         trianglelist_idx[*numtrianglespointer] = leaf->itemindex;
184                                         ++*numtrianglespointer;
185                                         break;
186                                 default:
187                                         break;
188                                 }
189                         }
190                         return;
191                 }
192                 // splitting node
193                 axis = node->type - BIH_SPLITX;
194                 if (mins[axis] < node->backmax)
195                 {
196                         if (maxs[axis] > node->frontmin)
197                                 BIH_GetTriangleListForBox_Node(bih, node->front, maxtriangles, trianglelist_idx, trianglelist_surf, numtrianglespointer, mins, maxs);
198                         nodenum = node->back;
199                         continue;
200                 }
201                 if (maxs[axis] > node->frontmin)
202                 {
203                         nodenum = node->front;
204                         continue;
205                 }
206                 // fell between the child groups, nothing here
207                 return;
208         }
209 }
210
211 int BIH_GetTriangleListForBox(const bih_t *bih, int maxtriangles, int *trianglelist_idx, int *trianglelist_surf, const float *mins, const float *maxs)
212 {
213         int numtriangles = 0;
214         BIH_GetTriangleListForBox_Node(bih, bih->rootnode, maxtriangles, trianglelist_idx, trianglelist_surf, &numtriangles, mins, maxs);
215         return numtriangles;
216 }