| // Copyright 2018 The Fuchsia Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include "src/ui/lib/escher/geometry/intersection.h" |
| |
| namespace escher { |
| |
| bool IntersectRayBox(const escher::ray4& ray, const escher::BoundingBox& box, |
| Interval* out_interval) { |
| // This algorithm is from "An Efficient and Robust Ray–Box Intersection |
| // Algorithm" by Amy Williams et al. 2004. Division by zero is handled via |
| // IEEE floating-point arithmetic. See paper for details. |
| // |
| // Fundamentally (leaving aside optimizations), the algorithm projects the box |
| // onto each coordinate axis and then computes the min/max parameters for the |
| // ray segment that has the same projection onto the same axis. If the |
| // intersection of these parameter ranges is empty, then the ray does not |
| // intersect the box. Otherwise, the minimum value of the intersected |
| // parameter ranges gives the intersection point. |
| const float idx = 1 / ray.direction.x; |
| const float idy = 1 / ray.direction.y; |
| const float idz = 1 / ray.direction.z; |
| |
| float t_min, t_max, ty_min, ty_max, tz_min, tz_max; |
| |
| // Bootstrap with x. Any coordinate axis would work just as well. |
| t_min = ((idx < 0 ? box.max() : box.min()).x - ray.origin.x) * idx; |
| t_max = ((idx < 0 ? box.min() : box.max()).x - ray.origin.x) * idx; |
| |
| ty_min = ((idy < 0 ? box.max() : box.min()).y - ray.origin.y) * idy; |
| ty_max = ((idy < 0 ? box.min() : box.max()).y - ray.origin.y) * idy; |
| |
| if (t_min > ty_max || ty_min > t_max) { |
| // The parameter ranges of the "x-axis projection" and "y-axis projection" |
| // ray segments are disjoint. Therefore the ray does not intersect the box. |
| return false; |
| } |
| |
| // Compute the intersection of the two parameter ranges. |
| if (ty_min > t_min) |
| t_min = ty_min; |
| if (ty_max < t_max) |
| t_max = ty_max; |
| |
| tz_min = ((idz < 0 ? box.max() : box.min()).z - ray.origin.z) * idz; |
| tz_max = ((idz < 0 ? box.min() : box.max()).z - ray.origin.z) * idz; |
| |
| if (t_min > tz_max || tz_min > t_max) |
| return false; |
| |
| if (tz_min > t_min) |
| t_min = tz_min; |
| if (tz_max < t_max) |
| t_max = tz_max; |
| |
| if (t_min < 0) { |
| if (t_max < 0) { |
| return false; |
| } |
| } |
| |
| // out_min and out_max values are only valid if there is a hit. |
| if (out_interval) { |
| *out_interval = Interval(glm::max(0.f, t_min), t_max); |
| } |
| |
| return true; |
| } |
| |
| // Use the "inside-out" test where the intersection point between the ray and the plane |
| // that contains the triangle is tested against each of the triangles edges. If the |
| // hit-point is inside all three edges then the ray has intersected the triangle. |
| bool IntersectRayTriangle(const escher::ray4& ray, const glm::vec3& v0, const glm::vec3& v1, |
| const glm::vec3& v2, float* out_distance) { |
| // Get ray components. |
| const glm::vec3 orig(ray.origin); |
| const glm::vec3 dir(ray.direction); |
| |
| // Get the normal vector for the triangle by computing the cross product |
| // of two of its edges, and normalizing the result. |
| glm::vec3 edge_1(v1 - v0); |
| glm::vec3 edge_2(v2 - v0); |
| glm::vec3 norm = glm::normalize(glm::cross(edge_1, edge_2)); |
| |
| // Find the intersection point between the ray and the triangle's plane. |
| // First check if the ray is parallel to the plane, in which case there |
| // is no intersection. Do this by computing the dot product of the ray direction |
| // with the normal. If it is 0, that indicates that the ray direction vector is |
| // 90 degrees from the normal, meaning it is parallel to the plane. |
| float dot_ray_norm = glm::dot(norm, dir); |
| if (fabs(dot_ray_norm) < kEpsilon) { |
| return false; |
| } |
| |
| // Check to see if the triangle is behind the ray origin by doing a ray-plane |
| // intersection test and seeing if the parameterized distance |t| is negative. |
| float t = glm::dot(v0 - orig, norm) / dot_ray_norm; |
| if (t < 0.f) { |
| return false; |
| } |
| |
| // Now we know that 1) the triangle is in front of the ray and 2) the ray intersections |
| // the plane. So we can grab the intersection point. |
| glm::vec3 point(ray.At(t)); |
| |
| // Now we perform the "inside out" test with P, to see if it lies on the inside of all |
| // three of the triangle's edges. This is a quick lambda function to do the edge testing |
| // so that we don't have to rewrite the same code three times. |
| auto IsInside = [&point, &norm](const glm::vec3& va, const glm::vec3& vb) { |
| glm::vec3 edge = vb - va; |
| glm::vec3 dist_p = point - va; |
| glm::vec3 perpendicular = glm::cross(edge, dist_p); |
| |
| // If the normal and the perpendicular vector are facing the same direction, the point |
| // is inside the edge. |
| return glm::dot(norm, perpendicular) >= 0.f; |
| }; |
| |
| // Check edge 0. |
| if (!IsInside(v0, v1)) { |
| return false; |
| } |
| |
| // Check edge 1. |
| if (!IsInside(v1, v2)) { |
| return false; |
| } |
| |
| // Check edge 2. |
| if (!IsInside(v2, v0)) { |
| return false; |
| } |
| |
| // The ray hit the triangle! Write out the distance before returning. |
| if (out_distance) { |
| *out_distance = t; |
| } |
| |
| return true; |
| } |
| |
| bool IntersectRayPlane(const escher::ray4& ray, const escher::plane3& plane, float* out_distance) { |
| float distance = IntersectLinePlane<vec3>(vec3(ray.origin), vec3(ray.direction), plane); |
| if (out_distance) { |
| *out_distance = distance; |
| } |
| return distance >= 0 && distance < FLT_MAX; |
| } |
| |
| } // namespace escher |