git.cworth.org Git - vogl/blob - src/voglcore/vogl_plane.h

   1 /**************************************************************************
   2  *
   3  * Copyright 2013-2014 RAD Game Tools and Valve Software
   4  * Copyright 2010-2014 Rich Geldreich and Tenacious Software LLC
   5  * All Rights Reserved.
   6  *
   7  * Permission is hereby granted, free of charge, to any person obtaining a copy
   8  * of this software and associated documentation files (the "Software"), to deal
   9  * in the Software without restriction, including without limitation the rights
  10  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  11  * copies of the Software, and to permit persons to whom the Software is
  12  * furnished to do so, subject to the following conditions:
  13  *
  14  * The above copyright notice and this permission notice shall be included in
  15  * all copies or substantial portions of the Software.
  16  *
  17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  18  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  20  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  21  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  22  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  23  * THE SOFTWARE.
  24  *
  25  **************************************************************************/
  26
  27 // File: vogl_plane.h
  28 #pragma once
  29
  30 #include "vogl_core.h"
  31 #include "vogl_matrix.h"
  32
  33 namespace vogl
  34 {
  35     class oriented_plane;
  36
  37     class plane
  38     {
  39     public:
  40         float m_dist;
  41         vec3F m_normal;
  42
  43         inline plane()
  44         {
  45         }
  46
  47         inline plane(const vec3F &norm, float dist)
  48             : m_dist(dist), m_normal(norm)
  49         {
  50         }
  51
  52         inline plane(const vec4F &norm, float dist)
  53             : m_dist(dist), m_normal(norm)
  54         {
  55         }
  56
  57         inline plane(float nx, float ny, float nz, float dist)
  58             : m_dist(dist), m_normal(nx, ny, nz)
  59         {
  60         }
  61
  62         inline plane(const vec3F &norm, const vec3F &org)
  63             : m_dist(norm.dot(org)), m_normal(norm)
  64         {
  65         }
  66
  67         inline plane(const vec3F &p, const vec3F &q, const vec3F &r)
  68         {
  69             init(p, q, r);
  70         }
  71
  72         inline plane(const vec4F &equation)
  73             : m_dist(-equation[3]), m_normal(equation)
  74         {
  75         }
  76
  77         inline plane(const oriented_plane &op)
  78         {
  79             init(op);
  80         }
  81
  82         inline bool is_valid() const
  83         {
  84             return (m_normal[0] != 0.0f) || (m_normal[1] != 0.0f) || (m_normal[2] != 0.0f);
  85         }
  86
  87         inline plane &clear()
  88         {
  89             m_normal.clear();
  90             m_dist = 0;
  91             return *this;
  92         }
  93
  94         inline const vec3F &get_normal() const
  95         {
  96             return m_normal;
  97         }
  98
  99         inline vec3F &get_normal()
 100         {
 101             return m_normal;
 102         }
 103
 104         inline const float &get_distance() const
 105         {
 106             return m_dist;
 107         }
 108
 109         inline float &get_distance()
 110         {
 111             return m_dist;
 112         }
 113
 114         inline vec4F get_equation() const
 115         {
 116             return vec4F(m_normal[0], m_normal[1], m_normal[2], -m_dist);
 117         }
 118
 119         inline vec3F get_point_on_plane() const
 120         {
 121             return m_normal * m_dist;
 122         }
 123
 124         inline const plane &init(float nx, float ny, float nz, float dist)
 125         {
 126             m_normal.set(nx, ny, nz);
 127             m_dist = dist;
 128             return *this;
 129         }
 130
 131         inline const plane &init(const vec4F &eq)
 132         {
 133             m_normal = eq;
 134             m_dist = -eq[3];
 135             return *this;
 136         }
 137
 138         inline bool init(const vec3F &p, const vec3F &q, const vec3F &r, float epsilon = 1e-6f)
 139         {
 140             m_normal = vec3F::cross3((r - q), (p - q));
 141
 142             double normal_len2 = m_normal.norm();
 143             if (normal_len2 <= epsilon)
 144             {
 145                 clear();
 146                 return false;
 147             }
 148
 149             m_normal *= static_cast<float>(1.0f / sqrt(normal_len2));
 150             m_dist = m_normal.dot(q);
 151             return true;
 152         }
 153
 154         inline void init_denormalized(const vec3F &p, const vec3F &q, const vec3F &r)
 155         {
 156             m_normal = vec3F::cross3(r - q, p - q);
 157             m_dist = m_normal.dot(q);
 158         }
 159
 160         inline plane &init(const vec3F &norm, const vec3F &point_on_plane)
 161         {
 162             m_normal = norm;
 163             m_dist = norm.dot(point_on_plane);
 164             return *this;
 165         }
 166
 167         inline plane &init(const oriented_plane &op);
 168
 169         inline plane &normalize_in_place()
 170         {
 171             double normal_len = m_normal.length();
 172             if (normal_len == 0.0f)
 173                 clear();
 174             else
 175             {
 176                 double one_over_normal_len = 1.0f / normal_len;
 177                 m_normal *= static_cast<float>(one_over_normal_len);
 178                 m_dist *= static_cast<float>(one_over_normal_len);
 179             }
 180             return *this;
 181         }
 182
 183         inline bool operator==(const plane &rhs) const
 184         {
 185             return (m_normal == rhs.m_normal) && (m_dist == rhs.m_dist);
 186         }
 187
 188         inline bool operator!=(const plane &rhs) const
 189         {
 190             return !(*this == rhs);
 191         }
 192
 193         inline float get_distance(const vec3F &p) const
 194         {
 195             return p.dot(m_normal) - m_dist;
 196         }
 197
 198         inline plane get_flipped() const
 199         {
 200             return plane(-m_normal, -m_dist);
 201         }
 202
 203         // computes how much solve_axis changes with movement along exclusively movement_axis
 204         inline float get_gradient(uint solve_axis, uint movement_axis, float epsilon = 1e-6f) const
 205         {
 206             const float dA = -m_normal[movement_axis];
 207             const float dB = m_normal[solve_axis];
 208             if (fabs(dB) <= epsilon)
 209             {
 210                 VOGL_ASSERT(0.0f);
 211                 return 0.0f;
 212             }
 213             return dA / dB;
 214         }
 215
 216         inline plane get_transformed(const matrix44F &m)
 217         {
 218             matrix44F m_inverted;
 219             if (!m.invert(m_inverted))
 220             {
 221                 VOGL_ASSERT_ALWAYS;
 222             }
 223
 224             plane result;
 225             result.m_normal = matrix44F::transform_vector_transposed(m_normal, m_inverted).normalize_in_place();
 226             result.m_dist = matrix44F::transform_point(get_point_on_plane(), m).dot3(result.m_normal);
 227             return result;
 228         }
 229
 230         inline plane get_transformed_ortho(const matrix44F &m)
 231         {
 232             plane result;
 233             result.m_normal = matrix44F::transform_vector(m_normal, m);
 234             result.m_dist = m_dist + vec3F(m[3]).dot(result.m_normal);
 235             return result;
 236         }
 237
 238         inline vec3F project_to_plane(const vec3F &p) const
 239         {
 240             return p - m_normal * get_distance(p);
 241         }
 242
 243         // computes z given xy
 244         inline float solve_for_z(float x, float y) const
 245         {
 246             return m_normal[2] ? ((m_dist - x * m_normal[0] - y * m_normal[1]) / m_normal[2]) : 0.0f;
 247         }
 248
 249         // generalized for any axis
 250         inline float solve_for_axis(const vec3F &p, uint axis) const
 251         {
 252             VOGL_ASSERT(axis < 3);
 253             static const uint8 axis2[] = { 1, 0, 0 };
 254             static const uint8 axis3[] = { 2, 2, 1 };
 255             return m_normal[axis] ? ((m_dist - p[axis2[axis]] * m_normal[axis2[axis]] - p[axis3[axis]] * m_normal[axis3[axis]]) / m_normal[axis]) : 0.0f;
 256         }
 257     };
 258
 259     class oriented_plane
 260     {
 261     public:
 262         vec3F m_u, m_v;
 263         vec3F m_origin;
 264
 265         inline oriented_plane()
 266         {
 267         }
 268
 269         inline oriented_plane(const plane &p)
 270         {
 271             init(p);
 272         }
 273
 274         inline oriented_plane(const vec3F &origon, const vec3F &u_axis, const vec3F &v_axis)
 275             : m_u(u_axis), m_v(v_axis), m_origin(origon)
 276         {
 277         }
 278
 279         inline oriented_plane(const vec3F &origon, const vec3F &norm)
 280         {
 281             init(origon, norm);
 282         }
 283
 284         inline void clear()
 285         {
 286             m_origin.clear();
 287             m_u.clear();
 288             m_v.clear();
 289         }
 290
 291         inline const vec3F &get_origin() const
 292         {
 293             return m_origin;
 294         }
 295         inline vec3F &get_origin()
 296         {
 297             return m_origin;
 298         }
 299
 300         inline const vec3F &get_u() const
 301         {
 302             return m_u;
 303         }
 304         inline vec3F &get_u()
 305         {
 306             return m_u;
 307         }
 308
 309         inline const vec3F &get_v() const
 310         {
 311             return m_v;
 312         }
 313         inline vec3F &get_v()
 314         {
 315             return m_v;
 316         }
 317
 318         inline oriented_plane &init(const vec3F &origon, const vec3F &u_axis, const vec3F &v_axis)
 319         {
 320             m_origin = origon;
 321             m_u = u_axis;
 322             m_v = v_axis;
 323             return *this;
 324         }
 325
 326         inline oriented_plane &init(const plane &p)
 327         {
 328             m_origin = p.get_point_on_plane();
 329             m_u = vec3F::make_axis(p.m_normal.get_minor_axis()).remove_unit_direction(p.m_normal).normalize_in_place();
 330             m_v = vec3F::cross3(p.m_normal, m_u).normalize_in_place();
 331             return *this;
 332         }
 333
 334         inline oriented_plane &init(const vec3F &origon, const vec3F &norm)
 335         {
 336             m_origin = origon;
 337             m_u = vec3F::make_axis(norm.get_minor_axis()).remove_unit_direction(norm).normalize_in_place();
 338             m_v = vec3F::cross3(norm, m_u).normalize_in_place();
 339             return *this;
 340         }
 341
 342         inline vec2F get_projected(const vec3F &p) const
 343         {
 344             vec3F rel(p - m_origin);
 345             return vec2F(m_u.dot(rel), m_v.dot(rel));
 346         }
 347
 348         inline vec3F get_point(const vec2F &p) const
 349         {
 350             return m_u * p[0] + m_v * p[1] + m_origin;
 351         }
 352
 353         inline vec3F get_normal() const
 354         {
 355             return vec3F::cross3(m_u, m_v).normalize_in_place();
 356         }
 357
 358         inline oriented_plane &normalize_in_place()
 359         {
 360             m_u.normalize();
 361             m_v.normalize();
 362             return *this;
 363         }
 364
 365         inline oriented_plane &init_planar_projection(const plane &p)
 366         {
 367             const uint major_axis = p.get_normal().get_major_axis();
 368             uint axis0 = math::next_wrap<uint>(major_axis, 3U);
 369             uint axis1 = math::next_wrap<uint>(axis0, 3U);
 370             if (p.get_normal()[major_axis] > 0.0f)
 371                 std::swap(axis0, axis1);
 372             return init(vec3F(0), vec3F::make_axis(axis0), vec3F::make_axis(axis1));
 373         }
 374     };
 375
 376     inline plane &plane::init(const oriented_plane &op)
 377     {
 378         m_normal = op.get_normal();
 379         m_dist = op.get_origin().dot(op.get_normal());
 380         return *this;
 381     }
 382
 383     inline void clip_convex_polygon_against_plane(vogl::vector<vec3F> &result, const vogl::vector<vec3F> &src_poly, const plane &p)
 384     {
 385         result.resize(0);
 386         if (!src_poly.size())
 387             return;
 388
 389         uint prev_index = src_poly.size() - 1;
 390         float prev_dist = p.get_distance(src_poly[prev_index]);
 391         for (uint cur_index = 0; cur_index < src_poly.size(); ++cur_index)
 392         {
 393             if (prev_dist >= 0.0f)
 394                 result.push_back(src_poly[prev_index]);
 395
 396             float cur_dist = p.get_distance(src_poly[cur_index]);
 397             if (((prev_dist < 0.0f) && (cur_dist > 0.0f)) || ((prev_dist > 0.0f) && (cur_dist < 0.0f)))
 398                 result.push_back(vec3F::lerp(src_poly[prev_index], src_poly[cur_index], prev_dist / (prev_dist - cur_dist)));
 399
 400             prev_index = cur_index;
 401             prev_dist = cur_dist;
 402         }
 403     }
 404
 405     // This stuff was derived from the plane equation for a 3D triangle, with XY in screenspace and Z the component to interpolate:
 406     //compute denormalized plane normal/distance:
 407     //m_normal = vec3F::cross3(r - q, p - q);
 408     //m_dist = m_normal * q;
 409     //return vec<3, T>(a[1] * b[2] - a[2] * b[1], a[2] * b[0] - a[0] * b[2], a[0] * b[1] - a[1] * b[0]);
 410     struct tri_gradient_common
 411     {
 412         double m_qx, m_qy;
 413         double m_ax, m_ay, m_bx, m_by;
 414
 415         double m_norm_z;
 416         double m_one_over_norm_z;
 417
 418         inline void clear()
 419         {
 420             utils::zero_object(*this);
 421         }
 422
 423         // q is treated as the origin
 424         // vector_type must be at least 2 dimension, xy can be in screenspace (for example), component to be interpolated is treated as z axis.
 425         template <typename vector_type>
 426         inline void init(const vector_type &p, const vector_type &q, const vector_type &r)
 427         {
 428             m_qx = q[0];
 429             m_qy = q[1];
 430
 431             m_ax = r[0] - q[0];
 432             m_ay = r[1] - q[1];
 433
 434             m_bx = p[0] - q[0];
 435             m_by = p[1] - q[1];
 436
 437             m_norm_z = m_ax * m_by - m_ay * m_bx;
 438             m_one_over_norm_z = m_norm_z ? (1.0 / m_norm_z) : 0.0;
 439         }
 440     };
 441
 442     template <typename scalar_type>
 443     struct tri_gradient_component
 444     {
 445         scalar_type m_qz;
 446         scalar_type m_norm_x, m_norm_y;
 447         scalar_type m_dist;
 448
 449         inline void clear()
 450         {
 451             utils::zero_object(*this);
 452         }
 453
 454         void init(const tri_gradient_common &common, float pz, float qz, float rz)
 455         {
 456             m_qz = qz;
 457
 458             double az = rz - qz;
 459             double bz = pz - qz;
 460
 461             m_norm_x = static_cast<scalar_type>(common.m_ay * bz - az * common.m_by);
 462             m_norm_y = static_cast<scalar_type>(az * common.m_bx - common.m_ax * bz);
 463
 464             m_dist = static_cast<scalar_type>(m_norm_x * common.m_qx + m_norm_y * common.m_qy + common.m_norm_z * m_qz);
 465         }
 466
 467         // returns denormalized plane
 468         inline plane get_plane(const tri_gradient_common &common) const
 469         {
 470             return plane(static_cast<float>(m_norm_x), static_cast<float>(m_norm_y), static_cast<float>(common.m_norm_z), static_cast<float>(m_dist));
 471         }
 472
 473         // not accurate at float precision
 474         inline double solve_for_z(const tri_gradient_common &common, float x, float y) const
 475         {
 476             return (m_dist - x * m_norm_x - y * m_norm_y) * common.m_one_over_norm_z;
 477         }
 478
 479         // more accurate at float precision
 480         inline double solve_for_z_alt(const tri_gradient_common &common, float x, float y) const
 481         {
 482             double dz_dx = get_dz_over_dx_gradient(common);
 483             double dz_dy = get_dz_over_dy_gradient(common);
 484             return m_qz + (x - common.m_qx) * dz_dx + (y - common.m_qy) * dz_dy;
 485         }
 486
 487         inline double get_dz_over_dx_gradient(const tri_gradient_common &common) const
 488         {
 489             return -m_norm_x * common.m_one_over_norm_z;
 490         }
 491
 492         inline double get_dz_over_dy_gradient(const tri_gradient_common &common) const
 493         {
 494             return -m_norm_y * common.m_one_over_norm_z;
 495         }
 496     };
 497
 498     class plane2D
 499     {
 500     public:
 501         float m_dist;
 502         vec2F m_normal;
 503
 504         inline plane2D()
 505         {
 506         }
 507
 508         inline plane2D(const vec2F &norm, float dist)
 509             : m_dist(dist), m_normal(norm)
 510         {
 511         }
 512
 513         inline plane2D(float nx, float ny, float dist)
 514             : m_dist(dist), m_normal(nx, ny)
 515         {
 516         }
 517
 518         inline plane2D(const vec2F &p, const vec2F &q, float epsilon = 1e-6f)
 519         {
 520             init(p, q, epsilon);
 521         }
 522
 523         inline plane2D(const vec3F &equation)
 524             : m_dist(-equation[2]), m_normal(equation)
 525         {
 526         }
 527
 528         inline bool is_valid() const
 529         {
 530             return (m_normal[0] != 0.0f) || (m_normal[1] != 0.0f);
 531         }
 532
 533         inline plane2D &clear()
 534         {
 535             m_normal.clear();
 536             m_dist = 0;
 537             return *this;
 538         }
 539
 540         inline const vec2F &get_normal() const
 541         {
 542             return m_normal;
 543         }
 544
 545         inline vec2F &get_normal()
 546         {
 547             return m_normal;
 548         }
 549
 550         inline const float &get_distance() const
 551         {
 552             return m_dist;
 553         }
 554
 555         inline float &get_distance()
 556         {
 557             return m_dist;
 558         }
 559
 560         inline vec3F get_equation() const
 561         {
 562             return vec3F(m_normal[0], m_normal[1], -m_dist);
 563         }
 564
 565         inline vec2F get_point_on_plane() const
 566         {
 567             return m_normal * m_dist;
 568         }
 569
 570         inline const plane2D &init(float nx, float ny, float dist)
 571         {
 572             m_normal.set(nx, ny);
 573             m_dist = dist;
 574             return *this;
 575         }
 576
 577         inline const plane2D &init(const vec3F &eq)
 578         {
 579             m_normal = eq;
 580             m_dist = -eq[2];
 581             return *this;
 582         }
 583
 584         inline bool init(const vec2F &p, const vec2F &q, float epsilon = 1e-6f)
 585         {
 586             m_normal = (p - q).perp();
 587
 588             double normal_len2 = m_normal.norm();
 589             if (normal_len2 <= epsilon)
 590             {
 591                 clear();
 592                 return false;
 593             }
 594
 595             m_normal *= static_cast<float>(1.0f / sqrt(normal_len2));
 596             m_dist = m_normal.dot(q);
 597             return true;
 598         }
 599
 600         inline void init_denormalized(const vec2F &p, const vec2F &q)
 601         {
 602             m_normal = (p - q).perp();
 603             m_dist = m_normal.dot(q);
 604         }
 605
 606         inline plane2D &init_from_normal_point(const vec2F &norm, const vec2F &point_on_plane)
 607         {
 608             m_normal = norm;
 609             m_dist = norm.dot(point_on_plane);
 610             return *this;
 611         }
 612
 613         inline plane2D &normalize_in_place()
 614         {
 615             double normal_len = m_normal.length();
 616             if (normal_len == 0.0f)
 617                 clear();
 618             else
 619             {
 620                 double one_over_normal_len = 1.0f / normal_len;
 621                 m_normal *= static_cast<float>(one_over_normal_len);
 622                 m_dist *= static_cast<float>(one_over_normal_len);
 623             }
 624             return *this;
 625         }
 626
 627         inline bool operator==(const plane2D &rhs) const
 628         {
 629             return (m_normal == rhs.m_normal) && (m_dist == rhs.m_dist);
 630         }
 631
 632         inline bool operator!=(const plane2D &rhs) const
 633         {
 634             return !(*this == rhs);
 635         }
 636
 637         inline float get_distance(const vec2F &p) const
 638         {
 639             return p.dot(m_normal) - m_dist;
 640         }
 641
 642         inline plane2D get_flipped() const
 643         {
 644             return plane2D(-m_normal, -m_dist);
 645         }
 646
 647         // computes how much solve_axis changes with movement along exclusively movement_axis
 648         inline float get_gradient(uint solve_axis, uint movement_axis, float epsilon = 1e-6f) const
 649         {
 650             const float dA = -m_normal[movement_axis];
 651             const float dB = m_normal[solve_axis];
 652             if (fabs(dB) <= epsilon)
 653             {
 654                 VOGL_ASSERT(0.0f);
 655                 return 0.0f;
 656             }
 657             return dA / dB;
 658         }
 659
 660         inline plane2D get_transformed(const matrix33F &m)
 661         {
 662             matrix33F m_inverted;
 663             if (!m.invert(m_inverted))
 664             {
 665                 VOGL_ASSERT_ALWAYS;
 666             }
 667
 668             plane2D result;
 669             result.m_normal = matrix33F::transform_vector_transposed(m_normal, m_inverted).normalize_in_place();
 670             result.m_dist = matrix33F::transform_point(get_point_on_plane(), m).dot2(result.m_normal);
 671             return result;
 672         }
 673
 674         inline plane2D get_transformed_ortho(const matrix33F &m)
 675         {
 676             plane2D result;
 677             result.m_normal = matrix33F::transform_vector(m_normal, m);
 678             result.m_dist = m_dist + vec2F(m[2]).dot(result.m_normal);
 679             return result;
 680         }
 681
 682         inline vec2F project_to_plane(const vec2F &p) const
 683         {
 684             return p - m_normal * get_distance(p);
 685         }
 686
 687         inline float solve_for_axis(const vec2F &p, uint axis) const
 688         {
 689             return m_normal[axis] ? ((m_dist - p[axis ^ 1] * m_normal[axis ^ 1]) / m_normal[axis]) : 0.0f;
 690         }
 691
 692         inline float solve_for_x(float y) const
 693         {
 694             return m_normal[0] ? ((m_dist - y * m_normal[1]) / m_normal[0]) : 0.0f;
 695         }
 696
 697         inline float solve_for_y(float x) const
 698         {
 699             return m_normal[1] ? ((m_dist - x * m_normal[0]) / m_normal[1]) : 0.0f;
 700         }
 701     };
 702
 703 } // namespace vogl