git.cworth.org Git - vogl/blob - src/voglcore/vogl_intersect.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_intersect.h
  28 #pragma once
  29
  30 #include "vogl_core.h"
  31 #include "vogl_ray.h"
  32 #include "vogl_plane.h"
  33
  34 namespace vogl
  35 {
  36     namespace intersection
  37     {
  38         enum result
  39         {
  40             cBackfacing = -1,
  41             cFailure = 0,
  42             cSuccess,
  43             cParallel,
  44             cInside,
  45         };
  46
  47         // Returns cInside, cSuccess, or cFailure.
  48         // Algorithm: Graphics Gems 1
  49         template <typename vector_type, typename scalar_type, typename ray_type, typename aabb_type>
  50         inline result ray_aabb(vector_type &coord, scalar_type &t, const ray_type &ray, const aabb_type &box)
  51         {
  52             enum
  53             {
  54                 cNumDim = vector_type::num_elements,
  55                 cRight = 0,
  56                 cLeft = 1,
  57                 cMiddle = 2
  58             };
  59
  60             bool inside = true;
  61             int quadrant[cNumDim];
  62             scalar_type candidate_plane[cNumDim];
  63
  64             for (int i = 0; i < cNumDim; i++)
  65             {
  66                 if (ray.get_origin()[i] < box[0][i])
  67                 {
  68                     quadrant[i] = cLeft;
  69                     candidate_plane[i] = box[0][i];
  70                     inside = false;
  71                 }
  72                 else if (ray.get_origin()[i] > box[1][i])
  73                 {
  74                     quadrant[i] = cRight;
  75                     candidate_plane[i] = box[1][i];
  76                     inside = false;
  77                 }
  78                 else
  79                 {
  80                     quadrant[i] = cMiddle;
  81                 }
  82             }
  83
  84             if (inside)
  85             {
  86                 coord = ray.get_origin();
  87                 t = 0.0f;
  88                 return cInside;
  89             }
  90
  91             scalar_type max_t[cNumDim];
  92             for (int i = 0; i < cNumDim; i++)
  93             {
  94                 if ((quadrant[i] != cMiddle) && (ray.get_direction()[i] != 0.0f))
  95                     max_t[i] = (candidate_plane[i] - ray.get_origin()[i]) / ray.get_direction()[i];
  96                 else
  97                     max_t[i] = -1.0f;
  98             }
  99
 100             int which_plane = 0;
 101             for (int i = 1; i < cNumDim; i++)
 102                 if (max_t[which_plane] < max_t[i])
 103                     which_plane = i;
 104
 105             if (max_t[which_plane] < 0.0f)
 106                 return cFailure;
 107
 108             for (int i = 0; i < cNumDim; i++)
 109             {
 110                 if (i != which_plane)
 111                 {
 112                     coord[i] = ray.get_origin()[i] + max_t[which_plane] * ray.get_direction()[i];
 113
 114                     if ((coord[i] < box[0][i]) || (coord[i] > box[1][i]))
 115                         return cFailure;
 116                 }
 117                 else
 118                 {
 119                     coord[i] = candidate_plane[i];
 120                 }
 121
 122                 VOGL_ASSERT(coord[i] >= box[0][i] && coord[i] <= box[1][i]);
 123             }
 124
 125             t = max_t[which_plane];
 126             return cSuccess;
 127         }
 128
 129         template <typename vector_type, typename scalar_type, typename ray_type, typename aabb_type>
 130         inline result ray_aabb(bool &started_within, vector_type &coord, scalar_type &t, const ray_type &ray, const aabb_type &box)
 131         {
 132             if (!box.contains(ray.get_origin()))
 133             {
 134                 started_within = false;
 135                 return ray_aabb(coord, t, ray, box);
 136             }
 137
 138             started_within = true;
 139
 140             float diag_dist = box.diagonal_length() * 1.5f;
 141             ray_type outside_ray(ray.eval(diag_dist), -ray.get_direction());
 142
 143             result res(ray_aabb(coord, t, outside_ray, box));
 144             if (res != cSuccess)
 145                 return res;
 146
 147             t = math::maximum(0.0f, diag_dist - t);
 148             return cSuccess;
 149         }
 150
 151         template <typename ray_type, typename scalar_type>
 152         inline result ray_plane(scalar_type &result, uint plane_axis, scalar_type positive_plane_dist, const ray_type &the_ray, bool front_only, scalar_type epsilon = 1e-6f)
 153         {
 154             const scalar_type dir_dot = the_ray.get_direction()[plane_axis];
 155             if (fabs(dir_dot) <= epsilon)
 156             {
 157                 result = 0;
 158                 return cParallel;
 159             }
 160
 161             const scalar_type pos_dot = the_ray.get_origin()[plane_axis];
 162
 163             scalar_type dist = positive_plane_dist - pos_dot;
 164
 165             if ((front_only) && (dist > 0.0f))
 166             {
 167                 result = 0;
 168                 return cFailure;
 169             }
 170
 171             result = dist / dir_dot;
 172             return cSuccess;
 173         }
 174
 175         template <typename plane_type, typename ray_type, typename scalar_type>
 176         inline result ray_plane(scalar_type &result, const plane_type &the_plane, const ray_type &the_ray, bool front_only, scalar_type epsilon = 1e-6f)
 177         {
 178             const scalar_type dir_dot = the_plane.get_normal() * the_ray.get_direction();
 179             if (fabs(dir_dot) <= epsilon)
 180             {
 181                 result = 0;
 182                 return cParallel;
 183             }
 184
 185             const scalar_type pos_dot = the_plane.get_normal() * the_ray.get_origin();
 186
 187             scalar_type dist = the_plane.get_distance() - pos_dot;
 188
 189             if ((front_only) && (dist > 0.0f))
 190             {
 191                 result = 0;
 192                 return cFailure;
 193             }
 194
 195             result = dist / dir_dot;
 196             return cSuccess;
 197         }
 198
 199         inline result plane2D_plane2D(vec2F &p, const plane2D &x, const plane2D &y, float epsilon = 1e-8f)
 200         {
 201             const double v = y.m_normal[0] * x.m_normal[1] - y.m_normal[1] * x.m_normal[0];
 202             if (fabs(v) <= epsilon)
 203             {
 204                 p.clear();
 205                 return cParallel;
 206             }
 207             double one_over_v = 1.0 / v;
 208             p.set(static_cast<float>((y.m_dist * x.m_normal[1] - y.m_normal[1] * x.m_dist) * one_over_v), static_cast<float>((y.m_normal[0] * x.m_dist - y.m_dist * x.m_normal[0]) * one_over_v));
 209             return cSuccess;
 210         }
 211
 212         inline result plane2D_x_plane(vec2F &p, const plane2D &a, float pos_x_dist, float epsilon = 1e-8f)
 213         {
 214             const double v = a.m_normal[1];
 215             if (fabs(v) <= epsilon)
 216             {
 217                 p.clear();
 218                 return cParallel;
 219             }
 220             double one_over_v = 1.0 / v;
 221             p.set(static_cast<float>((pos_x_dist * a.m_normal[1]) * one_over_v), static_cast<float>((a.m_dist - pos_x_dist * a.m_normal[0]) * one_over_v));
 222             return cSuccess;
 223         }
 224
 225         inline result plane2D_y_plane(vec2F &p, const plane2D &a, float pos_y_dist, float epsilon = 1e-8f)
 226         {
 227             const double v = -a.m_normal[0];
 228             if (fabs(v) <= epsilon)
 229             {
 230                 p.clear();
 231                 return cParallel;
 232             }
 233             double one_over_v = 1.0 / v;
 234             p.set(static_cast<float>((pos_y_dist * a.m_normal[1] - a.m_dist) * one_over_v), static_cast<float>((-pos_y_dist * a.m_normal[0]) * one_over_v));
 235             return cSuccess;
 236         }
 237
 238     } // intersection
 239
 240 } // namespace vogl