d3/pt.h

   1 // Copyright 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
   7     and/or modify it under the terms of the GNU General Public License as
   8     published by the Free Software Foundation; either version 2 of the License,
   9     or (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/et.h: Represent 3D->2D projective transformations.
  23  */
  24
  25 #ifndef __pt_h__
  26 #define __pt_h__
  27
  28 #include "space.h"
  29 #include "et.h"
  30
  31 /*
  32  * Structure to describe a 3D->2D projective transformation.  3D information is
  33  * preserved by adding a depth element to the result.
  34  *
  35  * The following coordinate systems are considered:
  36  *
  37  *      P: projective
  38  *      C: local cartesian
  39  *      W: world
  40  */
  41
  42 struct pt {
  43 private:
  44         d2::transformation t;
  45         et euclidean;
  46         ale_real _view_angle;           /* XXX: should be ale_pos */
  47         ale_pos scale_factor;
  48         ale_pos diag_per_depth;
  49
  50 public:
  51
  52         /*
  53          * Constructor
  54          */
  55
  56         pt() {
  57                 _view_angle = M_PI / 4;
  58                 scale_factor = 1;
  59                 diag_per_depth = 0;
  60         }
  61
  62         pt(d2::transformation t, et e, ale_real va, ale_pos sf = 1) {
  63                 this->t = t;
  64                 euclidean = e;
  65                 _view_angle = va;
  66                 scale_factor = sf;
  67                 diag_per_depth = 0;
  68         }
  69
  70         /*
  71          * Get euclidean transformation reference.
  72          */
  73
  74         et &e() {
  75                 return euclidean;
  76         }
  77
  78         /*
  79          * Modify scale factor
  80          */
  81         void scale(ale_pos sf) {
  82                 scale_factor = sf;
  83         }
  84
  85         /*
  86          * Modify or get view angle
  87          */
  88         void view_angle(ale_pos va) {
  89                 diag_per_depth = 0;
  90                 _view_angle = va;
  91         }
  92
  93         ale_pos view_angle() {
  94                 return _view_angle;
  95         }
  96
  97         /*
  98          * Get the 2D scale factor
  99          */
 100         ale_pos scale_2d() const {
 101                 return t.scale();
 102         }
 103
 104         /*
 105          * Transform W to C.
 106          */
 107         point wc(point p) const {
 108                 return euclidean(p);
 109         }
 110
 111         /*
 112          * Transform C to P for given width and height.
 113          */
 114         point cp_generic(point p, ale_pos w, ale_pos h) const {
 115                 /*
 116                  * Divide x and y by negative z
 117                  */
 118
 119                 p[0] /= -p[2];
 120                 p[1] /= -p[2];
 121
 122                 /*
 123                  * Scale x and y
 124                  */
 125
 126                 ale_pos scaling_factor = sqrt(w*w + h*h) / (2 * tan(_view_angle / 2));
 127                 p[0] *= scaling_factor;
 128                 p[1] *= scaling_factor;
 129
 130                 /*
 131                  * Add an offset so that the upper-left corner is the origin.
 132                  */
 133
 134                 p[0] += h / 2;
 135                 p[1] += w / 2;
 136
 137                 return p;
 138         }
 139
 140         /*
 141          * Transform point p.
 142          */
 143         struct point wp_generic(struct point p, ale_pos w, ale_pos h) const {
 144                 return cp_generic(wc(p), w, h);
 145         }
 146
 147         /*
 148          * Width and height
 149          */
 150
 151         ale_pos scaled_width() const {
 152                 return t.scaled_width() * scale_factor;
 153         }
 154
 155         ale_pos scaled_height() const {
 156                 return t.scaled_height() * scale_factor;
 157         }
 158
 159         int scaled_in_bounds(point p) const {
 160                 return (p[0] >= 0 && p[0] <= scaled_height() - 1
 161                      && p[1] >= 0 && p[1] <= scaled_width() - 1);
 162         }
 163
 164         ale_pos unscaled_width() const {
 165                 return t.unscaled_width() * scale_factor;
 166         }
 167
 168         ale_pos unscaled_height() const {
 169                 return t.unscaled_height() * scale_factor;
 170         }
 171
 172         /*
 173          * Scaled transforms
 174          */
 175
 176         point cp_scaled(point p) const {
 177                 return cp_generic(p, scaled_width(), scaled_height());
 178         }
 179
 180         point wp_scaled(point p) const {
 181                 return wp_generic(p, scaled_width(), scaled_height());
 182         }
 183
 184         /*
 185          * Unscaled transforms
 186          */
 187
 188         point cp_unscaled(point p) const {
 189                 return cp_generic(p, unscaled_width(), unscaled_height());
 190         }
 191
 192         point wp_unscaled(point p) const {
 193                 return wp_generic(p, unscaled_width(), unscaled_height());
 194         }
 195
 196         /*
 197          * Transform P to C.
 198          */
 199         point pc_generic(point p, ale_pos w, ale_pos h) const {
 200                 /*
 201                  * Subtract offset
 202                  */
 203
 204                 p[0] -= h / 2;
 205                 p[1] -= w / 2;
 206
 207                 /*
 208                  * Scale x and y
 209                  */
 210
 211                 ale_pos scaling_factor = sqrt(w*w + h*h) / (2 * tan(_view_angle / 2));
 212                 p[0] /= scaling_factor;
 213                 p[1] /= scaling_factor;
 214
 215                 /*
 216                  * Multiply x and y by negative z
 217                  */
 218
 219                 p[0] *= -p[2];
 220                 p[1] *= -p[2];
 221
 222                 return p;
 223         }
 224
 225         /*
 226          * Transform C to W
 227          */
 228         point cw(point p) const {
 229                 return euclidean.inverse_transform(p);
 230         }
 231
 232         /*
 233          * Transform P to W
 234          */
 235         point pw_generic(point p, ale_pos w, ale_pos h) const {
 236                 return cw(pc_generic(p, w, h));
 237         }
 238
 239         /*
 240          * Inverse transforms for scaled points.
 241          */
 242
 243         point pc_scaled(point p) const {
 244                 return pc_generic(p, scaled_width(), scaled_height());
 245         }
 246
 247         point pw_scaled(point p) const {
 248                 return pw_generic(p, scaled_width(), scaled_height());
 249         }
 250
 251         /*
 252          * Inverse transforms for unscaled points.
 253          */
 254
 255         point pc_unscaled(point p) const {
 256                 return pc_generic(p, unscaled_width(), unscaled_height());
 257         }
 258
 259         point pw_unscaled(point p) const {
 260                 return pw_generic(p, unscaled_width(), unscaled_height());
 261         }
 262
 263         /*
 264          * Density calculation
 265          */
 266
 267         ale_pos c_density_scaled(point p) const {
 268                 ale_pos one_density = 1 / (pc_scaled(point(0, 0, -1)).lengthto(pc_scaled(point(0, 1, -1)))
 269                                          * pc_scaled(point(0, 0, -1)).lengthto(pc_scaled(point(1, 0, -1))));
 270
 271                 return one_density / (p[2] * p[2]);
 272         }
 273
 274         ale_pos w_density_scaled(point p) const {
 275                 return c_density_scaled(wc(p));
 276         }
 277
 278         ale_pos w_density_scaled_max(point w0, point w1, point w2) {
 279                 point c0 = wc(w0);
 280                 point c1 = wc(w1);
 281                 point c2 = wc(w2);
 282
 283                 /*
 284                  * Select the point closest to the camera.
 285                  */
 286
 287                 if (c0[2] > c1[2] && c0[2] > c2[2])
 288                         return c_density_scaled(c0);
 289                 else if (c1[2] > c2[2])
 290                         return c_density_scaled(c1);
 291                 else
 292                         return c_density_scaled(c2);
 293         }
 294
 295 private:
 296         void calculate_diag_per_depth() {
 297                 if (diag_per_depth != 0)
 298                         return;
 299                 ale_pos w = unscaled_width();
 300                 ale_pos h = unscaled_height();
 301
 302                 diag_per_depth = sqrt(2) * (2 * tan(_view_angle / 2)) / sqrt(w*w + h*h);
 303         }
 304
 305 public:
 306
 307         /*
 308          * Get a trilinear coordinate for a given position in the world and
 309          * a given 2D diagonal distance.
 310          */
 311         ale_pos trilinear_coordinate(point w, ale_pos diagonal) {
 312                 calculate_diag_per_depth();
 313
 314                 ale_pos depth = wc(w)[2];
 315
 316                 ale_pos coord = log(diagonal / (depth * diag_per_depth)) / log(2);
 317
 318                 return coord;
 319         }
 320
 321         /*
 322          * Get a trilinear coordinate for a given subspace.
 323          */
 324         ale_pos trilinear_coordinate(const space::traverse &st) {
 325                 point min = st.get_min();
 326                 point max = st.get_max();
 327                 point avg = (min + max) / (ale_pos) 2;
 328
 329                 ale_pos diagonal = min.lengthto(max) * sqrt(2) / sqrt(3);
 330
 331                 return trilinear_coordinate(avg, diagonal);
 332         }
 333
 334         /*
 335          * Get a diagonal distance for a given position in the world
 336          * and a given trilinear coordinate.
 337          */
 338         ale_pos diagonal_distance(point w, ale_pos coordinate) {
 339                 calculate_diag_per_depth();
 340
 341                 ale_pos depth = wc(w)[2];
 342                 ale_pos diagonal = pow(2, coordinate) * depth * diag_per_depth;
 343
 344                 return diagonal;
 345         }
 346
 347         /*
 348          * Get bounding box for projection of a subspace.
 349          */
 350
 351         void get_view_local_bb(const space::traverse &st, point bb[2]) {
 352
 353                 point min = point::posinf();
 354                 point max = point::neginf();
 355
 356                 point wbb[2] = { st.get_min(), st.get_max() };
 357
 358
 359                 for (int x = 0; x < 2; x++)
 360                 for (int y = 0; y < 2; y++)
 361                 for (int z = 0; z < 2; z++) {
 362                         point p = wp_scaled(point(wbb[x][0], wbb[y][1], wbb[z][2]));
 363
 364                         if (p[0] < min[0])
 365                                 min[0] = p[0];
 366                         if (p[0] > max[0])
 367                                 max[0] = p[0];
 368                         if (p[1] < min[1])
 369                                 min[1] = p[1];
 370                         if (p[1] > max[1])
 371                                 max[1] = p[1];
 372                         if (p[2] < min[2])
 373                                 min[2] = p[2];
 374                         if (p[2] > max[2])
 375                                 max[2] = p[2];
 376                 }
 377
 378                 /*
 379                  * Clip bounding box to image extents.
 380                  */
 381
 382                 if (min[0] < 0)
 383                         min[0] = 0;
 384                 if (min[1] < 0)
 385                         min[1] = 0;
 386                 if (max[0] > scaled_height() - 1)
 387                         max[0] = scaled_height() - 1;
 388                 if (max[1] > scaled_width() - 1)
 389                         max[1] = scaled_width() - 1;
 390
 391                 bb[0] = min;
 392                 bb[1] = max;
 393         }
 394
 395         /*
 396          * Get the in-bounds centroid for a subspace, if one exists.
 397          */
 398
 399         point centroid(const space::traverse &t) {
 400                 point bb[2];
 401
 402                 get_view_local_bb(t, bb);
 403
 404                 point min = bb[0];
 405                 point max = bb[1];
 406
 407                 for (int d = 0; d < 2; d++)
 408                 if (min[d] > max[d])
 409                         return point::undefined();
 410
 411                 if (min[2] > 0)
 412                         return point::undefined();
 413
 414                 return (bb[0] + bb[1]) / 2;
 415         }
 416
 417         /*
 418          * Get the local space origin in world space.
 419          */
 420
 421         point origin() {
 422                 return cw(point(0, 0, 0));
 423         }
 424
 425 };
 426
 427 #endif