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         int unscaled_in_bounds(point p) const {
 165                 return (p[0] >= 0 && p[0] <= unscaled_height() - 1
 166                      && p[1] >= 0 && p[1] <= unscaled_width() - 1);
 167         }
 168
 169         ale_pos unscaled_width() const {
 170                 return t.unscaled_width() * scale_factor;
 171         }
 172
 173         ale_pos unscaled_height() const {
 174                 return t.unscaled_height() * scale_factor;
 175         }
 176
 177         /*
 178          * Scaled transforms
 179          */
 180
 181         point cp_scaled(point p) const {
 182                 return cp_generic(p, scaled_width(), scaled_height());
 183         }
 184
 185         point wp_scaled(point p) const {
 186                 return wp_generic(p, scaled_width(), scaled_height());
 187         }
 188
 189         /*
 190          * Unscaled transforms
 191          */
 192
 193         point cp_unscaled(point p) const {
 194                 return cp_generic(p, unscaled_width(), unscaled_height());
 195         }
 196
 197         point wp_unscaled(point p) const {
 198                 return wp_generic(p, unscaled_width(), unscaled_height());
 199         }
 200
 201         /*
 202          * Transform P to C.
 203          */
 204         point pc_generic(point p, ale_pos w, ale_pos h) const {
 205                 /*
 206                  * Subtract offset
 207                  */
 208
 209                 p[0] -= h / 2;
 210                 p[1] -= w / 2;
 211
 212                 /*
 213                  * Scale x and y
 214                  */
 215
 216                 ale_pos scaling_factor = sqrt(w*w + h*h) / (2 * tan(_view_angle / 2));
 217                 p[0] /= scaling_factor;
 218                 p[1] /= scaling_factor;
 219
 220                 /*
 221                  * Multiply x and y by negative z
 222                  */
 223
 224                 p[0] *= -p[2];
 225                 p[1] *= -p[2];
 226
 227                 return p;
 228         }
 229
 230         /*
 231          * Transform C to W
 232          */
 233         point cw(point p) const {
 234                 return euclidean.inverse_transform(p);
 235         }
 236
 237         /*
 238          * Transform P to W
 239          */
 240         point pw_generic(point p, ale_pos w, ale_pos h) const {
 241                 return cw(pc_generic(p, w, h));
 242         }
 243
 244         /*
 245          * Inverse transforms for scaled points.
 246          */
 247
 248         point pc_scaled(point p) const {
 249                 return pc_generic(p, scaled_width(), scaled_height());
 250         }
 251
 252         point pw_scaled(point p) const {
 253                 return pw_generic(p, scaled_width(), scaled_height());
 254         }
 255
 256         /*
 257          * Inverse transforms for unscaled points.
 258          */
 259
 260         point pc_unscaled(point p) const {
 261                 return pc_generic(p, unscaled_width(), unscaled_height());
 262         }
 263
 264         point pw_unscaled(point p) const {
 265                 return pw_generic(p, unscaled_width(), unscaled_height());
 266         }
 267
 268         /*
 269          * Density calculation
 270          */
 271
 272         ale_pos c_density_scaled(point p) const {
 273                 ale_pos one_density = 1 / (pc_scaled(point(0, 0, -1)).lengthto(pc_scaled(point(0, 1, -1)))
 274                                          * pc_scaled(point(0, 0, -1)).lengthto(pc_scaled(point(1, 0, -1))));
 275
 276                 return one_density / (p[2] * p[2]);
 277         }
 278
 279         ale_pos w_density_scaled(point p) const {
 280                 return c_density_scaled(wc(p));
 281         }
 282
 283         ale_pos w_density_scaled_max(point w0, point w1, point w2) {
 284                 point c0 = wc(w0);
 285                 point c1 = wc(w1);
 286                 point c2 = wc(w2);
 287
 288                 /*
 289                  * Select the point closest to the camera.
 290                  */
 291
 292                 if (c0[2] > c1[2] && c0[2] > c2[2])
 293                         return c_density_scaled(c0);
 294                 else if (c1[2] > c2[2])
 295                         return c_density_scaled(c1);
 296                 else
 297                         return c_density_scaled(c2);
 298         }
 299
 300 private:
 301         void calculate_diag_per_depth() {
 302                 if (diag_per_depth != 0)
 303                         return;
 304                 ale_pos w = unscaled_width();
 305                 ale_pos h = unscaled_height();
 306
 307                 diag_per_depth = sqrt(2) * (2 * tan(_view_angle / 2)) / sqrt(w*w + h*h);
 308         }
 309
 310 public:
 311
 312         /*
 313          * Get a trilinear coordinate for a given position in the world and
 314          * a given 2D diagonal distance.
 315          */
 316         ale_pos trilinear_coordinate(point w, ale_pos diagonal) {
 317                 calculate_diag_per_depth();
 318
 319                 ale_pos depth = fabs(wc(w)[2]);
 320
 321                 ale_pos coord = log(diagonal / (depth * diag_per_depth)) / log(2);
 322
 323                 return coord;
 324         }
 325
 326         /*
 327          * Get a trilinear coordinate for a given subspace.
 328          */
 329         ale_pos trilinear_coordinate(const space::traverse &st) {
 330                 point min = st.get_min();
 331                 point max = st.get_max();
 332                 point avg = (min + max) / (ale_pos) 2;
 333
 334                 ale_pos diagonal = min.lengthto(max) * sqrt(2) / sqrt(3);
 335
 336                 return trilinear_coordinate(avg, diagonal);
 337         }
 338
 339         /*
 340          * Get a diagonal distance for a given position in the world
 341          * and a given trilinear coordinate.
 342          */
 343         ale_pos diagonal_distance(point w, ale_pos coordinate) {
 344                 calculate_diag_per_depth();
 345
 346                 ale_pos depth = fabs(wc(w)[2]);
 347                 ale_pos diagonal = pow(2, coordinate) * depth * diag_per_depth;
 348
 349                 return diagonal;
 350         }
 351
 352         /*
 353          * Get the 3D diagonal for a given depth and trilinear coordinate.
 354          */
 355         ale_pos diagonal_distance_3d(ale_pos depth, ale_pos coordinate) {
 356                 return pow(2, coordinate) * fabs(depth) * diag_per_depth * sqrt(3) / sqrt(2);
 357         }
 358
 359         /*
 360          * Get bounding box for projection of a subspace.
 361          */
 362
 363         void get_view_local_bb(const space::traverse &st, point bb[2]) {
 364
 365                 point min = point::posinf();
 366                 point max = point::neginf();
 367
 368                 point wbb[2] = { st.get_min(), st.get_max() };
 369
 370
 371                 for (int x = 0; x < 2; x++)
 372                 for (int y = 0; y < 2; y++)
 373                 for (int z = 0; z < 2; z++) {
 374                         point p = wp_scaled(point(wbb[x][0], wbb[y][1], wbb[z][2]));
 375
 376                         if (p[0] < min[0])
 377                                 min[0] = p[0];
 378                         if (p[0] > max[0])
 379                                 max[0] = p[0];
 380                         if (p[1] < min[1])
 381                                 min[1] = p[1];
 382                         if (p[1] > max[1])
 383                                 max[1] = p[1];
 384                         if (p[2] < min[2])
 385                                 min[2] = p[2];
 386                         if (p[2] > max[2])
 387                                 max[2] = p[2];
 388                 }
 389
 390                 /*
 391                  * Clip bounding box to image extents.
 392                  */
 393
 394                 if (min[0] < 0)
 395                         min[0] = 0;
 396                 if (min[1] < 0)
 397                         min[1] = 0;
 398                 if (max[0] > scaled_height() - 1)
 399                         max[0] = scaled_height() - 1;
 400                 if (max[1] > scaled_width() - 1)
 401                         max[1] = scaled_width() - 1;
 402
 403                 bb[0] = min;
 404                 bb[1] = max;
 405         }
 406
 407         /*
 408          * Get the in-bounds centroid for a subspace, if one exists.
 409          */
 410
 411         point centroid(point min, point max) {
 412                 for (int d = 0; d < 2; d++)
 413                 if (min[d] > max[d])
 414                         return point::undefined();
 415
 416                 if (min[2] > 0)
 417                         return point::undefined();
 418
 419                 return (bb[0] + bb[1]) / 2;
 420         }
 421
 422         point centroid(const space::traverse &t) {
 423                 point bb[2];
 424
 425                 get_view_local_bb(t, bb);
 426
 427                 return centroid(bb[0], bb[1]);
 428         }
 429
 430         /*
 431          * Get the local space origin in world space.
 432          */
 433
 434         point origin() {
 435                 return cw(point(0, 0, 0));
 436         }
 437
 438 };
 439
 440 #endif