1 /**************************************************************************
3 * Copyright 2013-2014 RAD Game Tools and Valve Software
4 * Copyright 2010-2014 Rich Geldreich and Tenacious Software LLC
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:
14 * The above copyright notice and this permission notice shall be included in
15 * all copies or substantial portions of the Software.
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
25 **************************************************************************/
27 // File: vogl_intersect.h
30 #include "vogl_core.h"
32 #include "vogl_plane.h"
36 namespace intersection
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)
54 cNumDim = vector_type::num_elements,
61 int quadrant[cNumDim];
62 scalar_type candidate_plane[cNumDim];
64 for (int i = 0; i < cNumDim; i++)
66 if (ray.get_origin()[i] < box[0][i])
69 candidate_plane[i] = box[0][i];
72 else if (ray.get_origin()[i] > box[1][i])
75 candidate_plane[i] = box[1][i];
80 quadrant[i] = cMiddle;
86 coord = ray.get_origin();
91 scalar_type max_t[cNumDim];
92 for (int i = 0; i < cNumDim; i++)
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];
101 for (int i = 1; i < cNumDim; i++)
102 if (max_t[which_plane] < max_t[i])
105 if (max_t[which_plane] < 0.0f)
108 for (int i = 0; i < cNumDim; i++)
110 if (i != which_plane)
112 coord[i] = ray.get_origin()[i] + max_t[which_plane] * ray.get_direction()[i];
114 if ((coord[i] < box[0][i]) || (coord[i] > box[1][i]))
119 coord[i] = candidate_plane[i];
122 VOGL_ASSERT(coord[i] >= box[0][i] && coord[i] <= box[1][i]);
125 t = max_t[which_plane];
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)
132 if (!box.contains(ray.get_origin()))
134 started_within = false;
135 return ray_aabb(coord, t, ray, box);
138 started_within = true;
140 float diag_dist = box.diagonal_length() * 1.5f;
141 ray_type outside_ray(ray.eval(diag_dist), -ray.get_direction());
143 result res(ray_aabb(coord, t, outside_ray, box));
147 t = math::maximum(0.0f, diag_dist - t);
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)
154 const scalar_type dir_dot = the_ray.get_direction()[plane_axis];
155 if (fabs(dir_dot) <= epsilon)
161 const scalar_type pos_dot = the_ray.get_origin()[plane_axis];
163 scalar_type dist = positive_plane_dist - pos_dot;
165 if ((front_only) && (dist > 0.0f))
171 result = dist / dir_dot;
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)
178 const scalar_type dir_dot = the_plane.get_normal() * the_ray.get_direction();
179 if (fabs(dir_dot) <= epsilon)
185 const scalar_type pos_dot = the_plane.get_normal() * the_ray.get_origin();
187 scalar_type dist = the_plane.get_distance() - pos_dot;
189 if ((front_only) && (dist > 0.0f))
195 result = dist / dir_dot;
199 inline result plane2D_plane2D(vec2F &p, const plane2D &x, const plane2D &y, float epsilon = 1e-8f)
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)
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));
212 inline result plane2D_x_plane(vec2F &p, const plane2D &a, float pos_x_dist, float epsilon = 1e-8f)
214 const double v = a.m_normal[1];
215 if (fabs(v) <= epsilon)
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));
225 inline result plane2D_y_plane(vec2F &p, const plane2D &a, float pos_y_dist, float epsilon = 1e-8f)
227 const double v = -a.m_normal[0];
228 if (fabs(v) <= epsilon)
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));