d3/space.h

   1 // Copyright 2003, 2004, 2005 David Hilvert <dhilvert@auricle.dyndns.org>,
   2 //                                          <dhilvert@ugcs.caltech.edu>
   3
   4 /*  This file is part of the Anti-Lamenessing Engine.
   5
   6     The Anti-Lamenessing Engine is free software; you can redistribute it and/or modify
   7     it under the terms of the GNU General Public License as published by
   8     the Free Software Foundation; either version 3 of the License, or
   9     (at your option) any later version.
  10
  11     The Anti-Lamenessing Engine is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with the Anti-Lamenessing Engine; if not, write to the Free Software
  18     Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  19 */
  20
  21 /*
  22  * d3/space.h: Representation of 3D space.
  23  */
  24
  25 #ifndef __space_h__
  26 #define __space_h__
  27
  28 #include "point.h"
  29
  30 class space {
  31 public:
  32
  33         /*
  34          * Structure to hold a subdivisible region of space.
  35          */
  36         struct node {
  37                 struct node *positive;
  38                 struct node *negative;
  39
  40                 node() {
  41                         positive = NULL;
  42                         negative = NULL;
  43                 }
  44         };
  45
  46 private:
  47         /*
  48          * Space root pointer
  49          */
  50         static node *root_node;
  51
  52 public:
  53
  54         static void init_root() {
  55                 root_node = new node;
  56         }
  57
  58         /*
  59          * Space traversal and navigation class.
  60          */
  61
  62         class traverse {
  63                 node *current;
  64                 point bounds[2];
  65
  66         public:
  67
  68                 static int get_next_split(point min, point max) {
  69                         assert(min[0] < max[0]);
  70                         assert(min[1] < max[1]);
  71                         assert(min[2] < max[2]);
  72
  73                         /*
  74                          * Double-infinite case.
  75                          */
  76
  77                         for (int d = 0; d < 3; d++)
  78                         if (isinf(max[d]) && isinf(min[d]))
  79                                 return d;
  80
  81                         /*
  82                          * Finite or single-infinite case
  83                          */
  84
  85                         if (max[0] - min[0] >= max[1] - min[1]
  86                          && (max[0] >= max[1] || !isinf(min[1]))
  87                          && (min[0] <= min[1] || !isinf(max[1]))
  88                          && max[0] - min[0] >= max[2] - min[2]
  89                          && (max[0] >= max[2] || !isinf(min[2]))
  90                          && (min[0] <= min[2] || !isinf(max[2])))
  91                                 return 0;
  92
  93                         if (max[1] - min[1] > max[2] - min[2]
  94                          && (max[1] >= max[2] || !isinf(min[2]))
  95                          && (min[1] <= min[2] || !isinf(max[2])))
  96                                 return 1;
  97
  98                         return 2;
  99                 }
 100
 101                 static ale_pos split_coordinate(int d, point min, point max) {
 102                         if (isinf(max[d]) && isinf(min[d]))
 103                                 return 0;
 104
 105                         if (isinf(max[d]))
 106                                 return tan((atan(min[d]) + M_PI/2) / 2);
 107
 108                         if (isinf(min[d]))
 109                                 return tan((atan(max[d]) - M_PI/2) / 2);
 110
 111                         return (min[d] + max[d]) / 2;
 112                 }
 113
 114                 static int get_next_cells(int d, point min, point max, point cells[2][2]) {
 115                         cells[0][0] = min;
 116                         cells[0][1] = max;
 117                         cells[1][0] = min;
 118                         cells[1][1] = max;
 119
 120                         ale_pos split_point = split_coordinate(d, min, max);
 121
 122                         if (split_point == min[d]
 123                          || split_point == max[d]
 124                          || !finite(split_point))
 125                                 return 0;
 126
 127                         cells[0][1][d] = split_point;
 128                         cells[1][0][d] = split_point;
 129
 130                         return 1;
 131                 }
 132
 133                 int get_next_split() {
 134                         return get_next_split(bounds[0], bounds[1]);
 135                 }
 136
 137                 ale_pos split_coordinate(int d) {
 138                         return split_coordinate(d, bounds[0], bounds[1]);
 139                 }
 140
 141                 ale_pos split_coordinate() {
 142                         int next_split = get_next_split();
 143                         return split_coordinate(next_split);
 144                 }
 145
 146                 static traverse root() {
 147
 148                         traverse result;
 149
 150                         result.current = root_node;
 151                         result.bounds[0] = point::neginf();
 152                         result.bounds[1] = point::posinf();
 153
 154                         assert(result.current);
 155
 156                         return result;
 157                 }
 158
 159                 int precision_wall() {
 160                         int next_split = get_next_split();
 161                         ale_pos split_point = split_coordinate(next_split);
 162
 163                         point &min = bounds[0];
 164                         point &max = bounds[1];
 165
 166                         assert(split_point <= max[next_split]);
 167                         assert(split_point >= min[next_split]);
 168
 169                         if (split_point == min[next_split] || split_point == max[next_split])
 170                                 return 1;
 171
 172                         return 0;
 173                 }
 174
 175                 traverse positive() {
 176
 177                         assert(current);
 178
 179                         int next_split = get_next_split();
 180
 181                         if (current->positive == NULL) {
 182                                 current->positive = new node;
 183                         }
 184
 185                         traverse result;
 186
 187                         result.current = current->positive;
 188                         result.bounds[0] = bounds[0];
 189                         result.bounds[1] = bounds[1];
 190
 191                         result.bounds[0][next_split] = split_coordinate(next_split);
 192
 193                         assert(result.current);
 194
 195                         return result;
 196                 }
 197
 198                 traverse negative() {
 199
 200                         assert(current);
 201
 202                         int next_split = get_next_split();
 203
 204                         if (current->negative == NULL) {
 205                                 current->negative = new node;
 206                         }
 207
 208                         traverse result;
 209
 210                         result.current = current->negative;
 211                         result.bounds[0] = bounds[0];
 212                         result.bounds[1] = bounds[1];
 213
 214                         result.bounds[1][next_split] = split_coordinate(next_split);
 215
 216                         assert(result.current);
 217
 218                         return result;
 219                 }
 220
 221                 point get_min() const {
 222                         return bounds[0];
 223                 }
 224
 225                 point get_max() const {
 226                         return bounds[1];
 227                 }
 228
 229                 const point *get_bounds() const {
 230                         return bounds;
 231                 }
 232
 233                 point get_centroid() const {
 234                         return (bounds[0] + bounds[1]) / 2;
 235                 }
 236
 237                 int includes(point p) {
 238
 239                         for (int d = 0; d < 3; d++) {
 240                                 if (p[d] > bounds[1][d])
 241                                         return 0;
 242                                 if (p[d] < bounds[0][d])
 243                                         return 0;
 244                                 if (isnan(p[d]))
 245                                         return 0;
 246                         }
 247
 248                         return 1;
 249                 }
 250
 251                 node *get_node() {
 252                         assert(current);
 253                         return current;
 254                 }
 255
 256         };
 257
 258         /*
 259          * Class to iterate through subspaces based on proximity to a camera.
 260          */
 261
 262         class iterate {
 263                 std::stack<traverse> node_stack;
 264                 point camera_origin;
 265
 266         public:
 267                 iterate(point co, traverse top = traverse::root()) {
 268                         camera_origin = co;
 269                         node_stack.push(top);
 270                 }
 271
 272                 int next() {
 273                         if (node_stack.empty())
 274                                 return 0;
 275
 276                         traverse st = node_stack.top();
 277
 278                         int d = st.get_next_split();
 279
 280                         ale_pos split_coordinate = st.split_coordinate();
 281
 282                         node *n = st.get_node()->negative;
 283                         node *p = st.get_node()->positive;
 284
 285                         if (camera_origin[d] > split_coordinate) {
 286                                 if (n) {
 287                                         node_stack.top() = st.negative();
 288                                         if (p)
 289                                                 node_stack.push(st.positive());
 290                                 } else {
 291                                         if (p)
 292                                                 node_stack.top() = st.positive();
 293                                         else
 294                                                 node_stack.pop();
 295                                 }
 296                         } else {
 297                                 if (p) {
 298                                         node_stack.top() = st.positive();
 299                                         if (n)
 300                                                 node_stack.push(st.negative());
 301                                 } else {
 302                                         if (n)
 303                                                 node_stack.top() = st.negative();
 304                                         else
 305                                                 node_stack.pop();
 306                                 }
 307                         }
 308
 309                         return (!node_stack.empty());
 310                 }
 311
 312                 iterate cleave() {
 313                         assert (!node_stack.empty());
 314
 315                         iterate result(camera_origin, node_stack.top());
 316
 317                         node_stack.pop();
 318
 319                         return result;
 320                 }
 321
 322                 int done() {
 323                         return node_stack.empty();
 324                 }
 325
 326                 traverse get() {
 327                         assert (!node_stack.empty());
 328                         return node_stack.top();
 329                 }
 330         };
 331 };
 332
 333 #endif