1 |
|
|
/* |
2 |
|
|
Teem: Tools to process and visualize scientific data and images . |
3 |
|
|
Copyright (C) 2013, 2012, 2011, 2010, 2009 University of Chicago |
4 |
|
|
Copyright (C) 2008, 2007, 2006, 2005 Gordon Kindlmann |
5 |
|
|
Copyright (C) 2004, 2003, 2002, 2001, 2000, 1999, 1998 University of Utah |
6 |
|
|
|
7 |
|
|
This library is free software; you can redistribute it and/or |
8 |
|
|
modify it under the terms of the GNU Lesser General Public License |
9 |
|
|
(LGPL) as published by the Free Software Foundation; either |
10 |
|
|
version 2.1 of the License, or (at your option) any later version. |
11 |
|
|
The terms of redistributing and/or modifying this software also |
12 |
|
|
include exceptions to the LGPL that facilitate static linking. |
13 |
|
|
|
14 |
|
|
This library is distributed in the hope that it will be useful, |
15 |
|
|
but WITHOUT ANY WARRANTY; without even the implied warranty of |
16 |
|
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
17 |
|
|
Lesser General Public License for more details. |
18 |
|
|
|
19 |
|
|
You should have received a copy of the GNU Lesser General Public License |
20 |
|
|
along with this library; if not, write to Free Software Foundation, Inc., |
21 |
|
|
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA |
22 |
|
|
*/ |
23 |
|
|
|
24 |
|
|
#include "echo.h" |
25 |
|
|
#include "privateEcho.h" |
26 |
|
|
|
27 |
|
|
void |
28 |
|
|
echoListAdd(echoObject *list, echoObject *child) { |
29 |
|
|
int idx; |
30 |
|
|
|
31 |
|
|
if (!( list && child && |
32 |
|
|
(echoTypeList == list->type || |
33 |
|
|
echoTypeAABBox == list->type) )) |
34 |
|
|
return; |
35 |
|
|
|
36 |
|
|
idx = airArrayLenIncr(LIST(list)->objArr, 1); |
37 |
|
|
LIST(list)->obj[idx] = child; |
38 |
|
|
|
39 |
|
|
return; |
40 |
|
|
} |
41 |
|
|
|
42 |
|
|
int |
43 |
|
|
_echoPosCompare(double *A, double *B) { |
44 |
|
|
|
45 |
|
|
return *A < *B ? -1 : (*A > *B ? 1 : 0); |
46 |
|
|
} |
47 |
|
|
|
48 |
|
|
/* |
49 |
|
|
******** echoListSplit() |
50 |
|
|
** |
51 |
|
|
** returns a echoObjectSplit to point to the same things as pointed |
52 |
|
|
** to by the given echoObjectList |
53 |
|
|
*/ |
54 |
|
|
echoObject * |
55 |
|
|
echoListSplit(echoScene *scene, echoObject *list, int axis) { |
56 |
|
|
echoPos_t lo[3], hi[3], loest0[3], hiest0[3], |
57 |
|
|
loest1[3], hiest1[3]; |
58 |
|
|
double *mids; |
59 |
|
|
echoObject *o, *split, *list0, *list1; |
60 |
|
|
int i, splitIdx, len; |
61 |
|
|
|
62 |
|
|
if (!( echoTypeList == list->type || |
63 |
|
|
echoTypeAABBox == list->type )) { |
64 |
|
|
return list; |
65 |
|
|
} |
66 |
|
|
|
67 |
|
|
len = LIST(list)->objArr->len; |
68 |
|
|
if (len <= ECHO_LEN_SMALL_ENOUGH) { |
69 |
|
|
/* there is nothing or only one object */ |
70 |
|
|
return list; |
71 |
|
|
} |
72 |
|
|
|
73 |
|
|
split = echoObjectNew(scene, echoTypeSplit); |
74 |
|
|
list0 = echoObjectNew(scene, echoTypeList); |
75 |
|
|
list1 = echoObjectNew(scene, echoTypeList); |
76 |
|
|
SPLIT(split)->axis = axis; |
77 |
|
|
SPLIT(split)->obj0 = list0; |
78 |
|
|
SPLIT(split)->obj1 = list1; |
79 |
|
|
|
80 |
|
|
mids = (double *)malloc(2 * len * sizeof(double)); |
81 |
|
|
for (i=0; i<len; i++) { |
82 |
|
|
o = LIST(list)->obj[i]; |
83 |
|
|
echoBoundsGet(lo, hi, o); |
84 |
|
|
mids[0 + 2*i] = (lo[axis] + hi[axis])/2; |
85 |
|
|
*((unsigned int *)(mids + 1 + 2*i)) = i; |
86 |
|
|
} |
87 |
|
|
/* overkill, I know, I know */ |
88 |
|
|
qsort(mids, len, 2*sizeof(double), |
89 |
|
|
(int (*)(const void *, const void *))_echoPosCompare); |
90 |
|
|
/* |
91 |
|
|
for (i=0; i<len; i++) { |
92 |
|
|
printf("%d -> %g\n", i, mids[0 + 2*i]); |
93 |
|
|
} |
94 |
|
|
*/ |
95 |
|
|
|
96 |
|
|
splitIdx = len/2; |
97 |
|
|
/* printf("splitIdx = %d\n", splitIdx); */ |
98 |
|
|
ELL_3V_SET(loest0, ECHO_POS_MAX, ECHO_POS_MAX, ECHO_POS_MAX); |
99 |
|
|
ELL_3V_SET(loest1, ECHO_POS_MAX, ECHO_POS_MAX, ECHO_POS_MAX); |
100 |
|
|
ELL_3V_SET(hiest0, ECHO_POS_MIN, ECHO_POS_MIN, ECHO_POS_MIN); |
101 |
|
|
ELL_3V_SET(hiest1, ECHO_POS_MIN, ECHO_POS_MIN, ECHO_POS_MIN); |
102 |
|
|
airArrayLenSet(LIST(list0)->objArr, splitIdx); |
103 |
|
|
for (i=0; i<splitIdx; i++) { |
104 |
|
|
o = LIST(list)->obj[*((unsigned int *)(mids + 1 + 2*i))]; |
105 |
|
|
LIST(list0)->obj[i] = o; |
106 |
|
|
echoBoundsGet(lo, hi, o); |
107 |
|
|
/* |
108 |
|
|
printf("000 lo = (%g,%g,%g), hi = (%g,%g,%g)\n", |
109 |
|
|
lo[0], lo[1], lo[2], hi[0], hi[1], hi[2]); |
110 |
|
|
*/ |
111 |
|
|
ELL_3V_MIN(loest0, loest0, lo); |
112 |
|
|
ELL_3V_MAX(hiest0, hiest0, hi); |
113 |
|
|
} |
114 |
|
|
airArrayLenSet(LIST(list1)->objArr, len-splitIdx); |
115 |
|
|
for (i=splitIdx; i<len; i++) { |
116 |
|
|
o = LIST(list)->obj[*((unsigned int *)(mids + 1 + 2*i))]; |
117 |
|
|
LIST(list1)->obj[i-splitIdx] = o; |
118 |
|
|
echoBoundsGet(lo, hi, o); |
119 |
|
|
/* |
120 |
|
|
printf("111 lo = (%g,%g,%g), hi = (%g,%g,%g)\n", |
121 |
|
|
lo[0], lo[1], lo[2], hi[0], hi[1], hi[2]); |
122 |
|
|
*/ |
123 |
|
|
ELL_3V_MIN(loest1, loest1, lo); |
124 |
|
|
ELL_3V_MAX(hiest1, hiest1, hi); |
125 |
|
|
} |
126 |
|
|
/* |
127 |
|
|
printf("0: loest = (%g,%g,%g); hiest = (%g,%g,%g)\n", |
128 |
|
|
loest0[0], loest0[1], loest0[2], |
129 |
|
|
hiest0[0], hiest0[1], hiest0[2]); |
130 |
|
|
printf("1: loest = (%g,%g,%g); hiest = (%g,%g,%g)\n", |
131 |
|
|
loest1[0], loest1[1], loest1[2], |
132 |
|
|
hiest1[0], hiest1[1], hiest1[2]); |
133 |
|
|
*/ |
134 |
|
|
ELL_3V_COPY(SPLIT(split)->min0, loest0); |
135 |
|
|
ELL_3V_COPY(SPLIT(split)->max0, hiest0); |
136 |
|
|
ELL_3V_COPY(SPLIT(split)->min1, loest1); |
137 |
|
|
ELL_3V_COPY(SPLIT(split)->max1, hiest1); |
138 |
|
|
|
139 |
|
|
/* we can't delete the list object here, we just gut it so |
140 |
|
|
that there's nothing substantial left of it */ |
141 |
|
|
airArrayLenSet(LIST(list)->objArr, 0); |
142 |
|
|
mids = (double *)airFree(mids); |
143 |
|
|
return split; |
144 |
|
|
} |
145 |
|
|
|
146 |
|
|
echoObject * |
147 |
|
|
echoListSplit3(echoScene *scene, echoObject *list, int depth) { |
148 |
|
|
echoObject *ret, *tmp0, *tmp1; |
149 |
|
|
|
150 |
|
|
if (!( echoTypeList == list->type || |
151 |
|
|
echoTypeAABBox == list->type )) |
152 |
|
|
return NULL; |
153 |
|
|
|
154 |
|
|
if (!depth) |
155 |
|
|
return list; |
156 |
|
|
|
157 |
|
|
ret = echoListSplit(scene, list, 0); |
158 |
|
|
|
159 |
|
|
#define DOIT(obj, ax) ((obj) = echoListSplit(scene, (obj), (ax))) |
160 |
|
|
#define MORE(obj) echoTypeSplit == (obj)->type |
161 |
|
|
|
162 |
|
|
if (MORE(ret)) { |
163 |
|
|
tmp0 = DOIT(SPLIT(ret)->obj0, 1); |
164 |
|
|
if (MORE(tmp0)) { |
165 |
|
|
tmp1 = DOIT(SPLIT(tmp0)->obj0, 2); |
166 |
|
|
if (MORE(tmp1)) { |
167 |
|
|
SPLIT(tmp1)->obj0 = echoListSplit3(scene, SPLIT(tmp1)->obj0, depth-1); |
168 |
|
|
SPLIT(tmp1)->obj1 = echoListSplit3(scene, SPLIT(tmp1)->obj1, depth-1); |
169 |
|
|
} |
170 |
|
|
tmp1 = DOIT(SPLIT(tmp0)->obj1, 2); |
171 |
|
|
if (MORE(tmp1)) { |
172 |
|
|
SPLIT(tmp1)->obj0 = echoListSplit3(scene, SPLIT(tmp1)->obj0, depth-1); |
173 |
|
|
SPLIT(tmp1)->obj1 = echoListSplit3(scene, SPLIT(tmp1)->obj1, depth-1); |
174 |
|
|
} |
175 |
|
|
} |
176 |
|
|
tmp0 = DOIT(SPLIT(ret)->obj1, 1); |
177 |
|
|
if (MORE(tmp0)) { |
178 |
|
|
tmp1 = DOIT(SPLIT(tmp0)->obj0, 2); |
179 |
|
|
if (MORE(tmp1)) { |
180 |
|
|
SPLIT(tmp1)->obj0 = echoListSplit3(scene, SPLIT(tmp1)->obj0, depth-1); |
181 |
|
|
SPLIT(tmp1)->obj1 = echoListSplit3(scene, SPLIT(tmp1)->obj1, depth-1); |
182 |
|
|
} |
183 |
|
|
tmp1 = DOIT(SPLIT(tmp0)->obj1, 2); |
184 |
|
|
if (MORE(tmp1)) { |
185 |
|
|
SPLIT(tmp1)->obj0 = echoListSplit3(scene, SPLIT(tmp1)->obj0, depth-1); |
186 |
|
|
SPLIT(tmp1)->obj1 = echoListSplit3(scene, SPLIT(tmp1)->obj1, depth-1); |
187 |
|
|
} |
188 |
|
|
} |
189 |
|
|
} |
190 |
|
|
return ret; |
191 |
|
|
} |
192 |
|
|
|