14956332093

Committed 11 May 2025 01:34PM UTC coverage: 74.477% (-0.1%) from 74.578%

Build # 14956332093

Build Type

push

github

Committed by

Razakhel

Commit Message

[Data/Grid3] Added a type for a 3-dimensional grid

Run Details

13 of 31 new or added lines in 2 files covered. (41.94%)

1 existing line in 1 file now uncovered.

8220 of 11037 relevant lines covered (74.48%)

1785.81 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

99.07

/src/RaZ/Utils/Ray.cpp

#include "RaZ/Utils/FloatUtils.hpp"
#include "RaZ/Utils/Ray.hpp"
#include "RaZ/Utils/Shape.hpp"

namespace Raz {

namespace {

constexpr bool solveQuadratic(float a, float b, float c, float& firstHitDist, float& secondHitDist) {
  const float discriminant = b * b - 4.f * a * c;

  if (discriminant < 0.f) {
    return false;
  } else if (discriminant > 0.f) {
    const float q = -0.5f * ((b > 0) ? b + std::sqrt(discriminant) : b - std::sqrt(discriminant));

    firstHitDist  = q / a;
    secondHitDist = c / q;
  } else { // discriminant == 0
    const float hitDist = -0.5f * b / a;

    firstHitDist  = hitDist;
    secondHitDist = hitDist;
  }

  if (firstHitDist > secondHitDist)
    std::swap(firstHitDist, secondHitDist);

  return true;
}

} // namespace

bool Ray::intersects(const Vec3f& point, RayHit* hit) const {
  if (point == m_origin) {
    if (hit) {
      hit->position = point;
      hit->distance = 0.f;
    }

    return true;
  }

  const Vec3f pointDir       = point - m_origin;
  const Vec3f normedPointDir = pointDir.normalize();

  if (!FloatUtils::areNearlyEqual(normedPointDir.dot(m_direction), 1.f))
    return false;

  if (hit) {
    hit->position = point;
    hit->normal   = -normedPointDir;
    hit->distance = pointDir.computeLength();
  }

  return true;
}

bool Ray::intersects(const Plane& plane, RayHit* hit) const {
  const float dirAngle = m_direction.dot(plane.getNormal());

  if (dirAngle >= 0.f) // The plane is facing in the same direction as the ray
    return false;

  const float origAngle = m_origin.dot(plane.getNormal());
  const float hitDist   = (plane.getDistance() - origAngle) / dirAngle;

  if (hitDist <= 0.f) // The plane is behind the ray
    return false;

  if (hit) {
    hit->position = m_origin + m_direction * hitDist;
    hit->normal   = plane.getNormal();
    hit->distance = hitDist;
  }

  return true;
}

bool Ray::intersects(const Sphere& sphere, RayHit* hit) const {
  const Vec3f sphereDir = m_origin - sphere.getCenter();

  const float raySqLength = m_direction.dot(m_direction);
  const float rayDiff     = 2.f * m_direction.dot(sphereDir);
  const float sphereDiff  = sphereDir.computeSquaredLength() - sphere.getRadius() * sphere.getRadius();

  float firstHitDist {};
  float secondHitDist {};

  if (!solveQuadratic(raySqLength, rayDiff, sphereDiff, firstHitDist, secondHitDist))
    return false;

  // If the hit distances are negative, we've hit a sphere located behind the ray's origin
  if (firstHitDist < 0.f) {
    firstHitDist = secondHitDist;

    if (firstHitDist < 0.f)
      return false;
  }

  if (hit) {
    const Vec3f hitPos = m_origin + m_direction * firstHitDist;

    hit->position = hitPos;
    hit->normal   = (hitPos - sphere.getCenter()).normalize();
    hit->distance = firstHitDist;
  }

  return true;
}

bool Ray::intersects(const Triangle& triangle, RayHit* hit) const {
  const Vec3f firstEdge   = triangle.getSecondPos() - triangle.getFirstPos();
  const Vec3f secondEdge  = triangle.getThirdPos() - triangle.getFirstPos();
  const Vec3f pVec        = m_direction.cross(secondEdge);
  const float determinant = firstEdge.dot(pVec);

  if (FloatUtils::areNearlyEqual(std::abs(determinant), 0.f))
    return false;

  const float invDeterm = 1.f / determinant;

  const Vec3f invPlaneDir    = m_origin - triangle.getFirstPos();
  const float firstBaryCoord = invPlaneDir.dot(pVec) * invDeterm;

  if (firstBaryCoord < 0.f || firstBaryCoord > 1.f)
    return false;

  const Vec3f qVec = invPlaneDir.cross(firstEdge);
  const float secondBaryCoord = qVec.dot(m_direction) * invDeterm;

  if (secondBaryCoord < 0.f || firstBaryCoord + secondBaryCoord > 1.f)
    return false;

  const float hitDist = secondEdge.dot(qVec) * invDeterm;

  if (hitDist <= 0.f)
    return false;

  if (hit) {
    hit->position = m_origin + m_direction * hitDist;
    hit->normal   = firstEdge.cross(secondEdge).normalize(); // Directly computing the normal using the already calculated triangle's edges
    hit->distance = hitDist;
  }

  return true;
}

bool Ray::intersects(const AABB& aabb, RayHit* hit) const {
  // Branchless algorithm based on Tavianator's:
  //  - https://tavianator.com/fast-branchless-raybounding-box-intersections/
  //  - https://tavianator.com/cgit/dimension.git/tree/libdimension/bvh/bvh.c#n196

  const Vec3f minDist = (aabb.getMinPosition() - m_origin) * m_invDirection;
  const Vec3f maxDist = (aabb.getMaxPosition() - m_origin) * m_invDirection;

  const float minDistX = std::min(minDist.x(), maxDist.x());
  const float maxDistX = std::max(minDist.x(), maxDist.x());

  const float minDistY = std::min(minDist.y(), maxDist.y());
  const float maxDistY = std::max(minDist.y(), maxDist.y());

  const float minDistZ = std::min(minDist.z(), maxDist.z());
  const float maxDistZ = std::max(minDist.z(), maxDist.z());

  const float minHitDist = std::max(minDistX, std::max(minDistY, minDistZ));
  const float maxHitDist = std::min(maxDistX, std::min(maxDistY, maxDistZ));

  if (maxHitDist < std::max(minHitDist, 0.f))
    return false;

  // If reaching here with a negative distance (minHitDist < 0), this means that the ray's origin is inside the box
  // Currently, in this case, the computed hit position represents the intersection behind the ray

  if (hit) {
    hit->position = m_origin + m_direction * minHitDist;

    // Normal computing method based on John Novak's: https://blog.johnnovak.net/2016/10/22/the-nim-ray-tracer-project-part-4-calculating-box-normals/
    const Vec3f hitDir = (hit->position - aabb.computeCentroid()) / aabb.computeHalfExtents();
    hit->normal = Vec3f(std::trunc(hitDir.x()), std::trunc(hitDir.y()), std::trunc(hitDir.z())).normalize();

    hit->distance = minHitDist;
  }

  return true;
}

Vec3f Ray::computeProjection(const Vec3f& point) const {
  const float pointDist = m_direction.dot(point - m_origin);
  return (m_origin + m_direction * std::max(pointDist, 0.f));
}

} // namespace Raz

1	#include "RaZ/Utils/FloatUtils.hpp"
2	#include "RaZ/Utils/Ray.hpp"
3	#include "RaZ/Utils/Shape.hpp"
4
5	namespace Raz {
6
7	namespace {
8
9	constexpr bool solveQuadratic(float a, float b, float c, float& firstHitDist, float& secondHitDist) {	14✔
10	const float discriminant = b * b - 4.f * a * c;	14✔
11
12	if (discriminant < 0.f) {	14✔
13	return false;	3✔
14	} else if (discriminant > 0.f) {	11✔
15	const float q = -0.5f * ((b > 0) ? b + std::sqrt(discriminant) : b - std::sqrt(discriminant));	10✔
16
17	firstHitDist = q / a;	10✔
18	secondHitDist = c / q;	10✔
19	} else { // discriminant == 0
20	const float hitDist = -0.5f * b / a;	1✔
21
22	firstHitDist = hitDist;	1✔
23	secondHitDist = hitDist;	1✔
24	}
25
26	if (firstHitDist > secondHitDist)	11✔
27	std::swap(firstHitDist, secondHitDist);	8✔
28
29	return true;	11✔
30	}
31
32	} // namespace
33
34	bool Ray::intersects(const Vec3f& point, RayHit* hit) const {	9✔
35	if (point == m_origin) {	9✔
36	if (hit) {	1✔
37	hit->position = point;	1✔
38	hit->distance = 0.f;	1✔
39	}
40
41	return true;	1✔
42	}
43
44	const Vec3f pointDir = point - m_origin;	8✔
45	const Vec3f normedPointDir = pointDir.normalize();	8✔
46
47	if (!FloatUtils::areNearlyEqual(normedPointDir.dot(m_direction), 1.f))	8✔
48	return false;	6✔
49
50	if (hit) {	2✔
51	hit->position = point;	2✔
52	hit->normal = -normedPointDir;	2✔
53	hit->distance = pointDir.computeLength();	2✔
54	}
55
56	return true;	2✔
57	}
58
59	bool Ray::intersects(const Plane& plane, RayHit* hit) const {	16✔
60	const float dirAngle = m_direction.dot(plane.getNormal());	16✔
61
62	if (dirAngle >= 0.f) // The plane is facing in the same direction as the ray	16✔
63	return false;	9✔
64
65	const float origAngle = m_origin.dot(plane.getNormal());	7✔
66	const float hitDist = (plane.getDistance() - origAngle) / dirAngle;	7✔
67
68	if (hitDist <= 0.f) // The plane is behind the ray	7✔
69	return false;	2✔
70
71	if (hit) {	5✔
72	hit->position = m_origin + m_direction * hitDist;	2✔
73	hit->normal = plane.getNormal();	2✔
74	hit->distance = hitDist;	2✔
75	}
76
77	return true;	5✔
78	}
79
80	bool Ray::intersects(const Sphere& sphere, RayHit* hit) const {	14✔
81	const Vec3f sphereDir = m_origin - sphere.getCenter();	14✔
82
83	const float raySqLength = m_direction.dot(m_direction);	14✔
84	const float rayDiff = 2.f * m_direction.dot(sphereDir);	14✔
85	const float sphereDiff = sphereDir.computeSquaredLength() - sphere.getRadius() * sphere.getRadius();	14✔
86
87	float firstHitDist {};	14✔
88	float secondHitDist {};	14✔
89
90	if (!solveQuadratic(raySqLength, rayDiff, sphereDiff, firstHitDist, secondHitDist))	14✔
91	return false;	3✔
92
93	// If the hit distances are negative, we've hit a sphere located behind the ray's origin
94	if (firstHitDist < 0.f) {	11✔
95	firstHitDist = secondHitDist;	6✔
96
97	if (firstHitDist < 0.f)	6✔
98	return false;	2✔
99	}
100
101	if (hit) {	9✔
102	const Vec3f hitPos = m_origin + m_direction * firstHitDist;	8✔
103
104	hit->position = hitPos;	8✔
105	hit->normal = (hitPos - sphere.getCenter()).normalize();	8✔
106	hit->distance = firstHitDist;	8✔
107	}
108
109	return true;	9✔
110	}
111
112	bool Ray::intersects(const Triangle& triangle, RayHit* hit) const {	234,005✔
113	const Vec3f firstEdge = triangle.getSecondPos() - triangle.getFirstPos();	234,005✔
114	const Vec3f secondEdge = triangle.getThirdPos() - triangle.getFirstPos();	234,708✔
115	const Vec3f pVec = m_direction.cross(secondEdge);	235,533✔
116	const float determinant = firstEdge.dot(pVec);	235,719✔
117
118	if (FloatUtils::areNearlyEqual(std::abs(determinant), 0.f))	236,313✔
119	return false;	3,055✔
120
121	const float invDeterm = 1.f / determinant;	231,232✔
122
123	const Vec3f invPlaneDir = m_origin - triangle.getFirstPos();	231,232✔
124	const float firstBaryCoord = invPlaneDir.dot(pVec) * invDeterm;	232,119✔
125
126	if (firstBaryCoord < 0.f \|\| firstBaryCoord > 1.f)	233,071✔
127	return false;	134,888✔
128
129	const Vec3f qVec = invPlaneDir.cross(firstEdge);	98,183✔
130	const float secondBaryCoord = qVec.dot(m_direction) * invDeterm;	98,159✔
131
132	if (secondBaryCoord < 0.f \|\| firstBaryCoord + secondBaryCoord > 1.f)	98,384✔
133	return false;	53,167✔
134
135	const float hitDist = secondEdge.dot(qVec) * invDeterm;	45,217✔
136
137	if (hitDist <= 0.f)	45,242✔
138	return false;	24,841✔
139
140	if (hit) {	20,401✔
141	hit->position = m_origin + m_direction * hitDist;	20,422✔
142	hit->normal = firstEdge.cross(secondEdge).normalize(); // Directly computing the normal using the already calculated triangle's edges	20,426✔
143	hit->distance = hitDist;	20,438✔
144	}
145
146	return true;	20,417✔
147	}
148
149	bool Ray::intersects(const AABB& aabb, RayHit* hit) const {	266,708✔
150	// Branchless algorithm based on Tavianator's:
151	// - https://tavianator.com/fast-branchless-raybounding-box-intersections/
152	// - https://tavianator.com/cgit/dimension.git/tree/libdimension/bvh/bvh.c#n196
153
154	const Vec3f minDist = (aabb.getMinPosition() - m_origin) * m_invDirection;	266,708✔
155	const Vec3f maxDist = (aabb.getMaxPosition() - m_origin) * m_invDirection;	269,460✔
156
157	const float minDistX = std::min(minDist.x(), maxDist.x());	269,843✔
158	const float maxDistX = std::max(minDist.x(), maxDist.x());	268,012✔
159
160	const float minDistY = std::min(minDist.y(), maxDist.y());	266,991✔
161	const float maxDistY = std::max(minDist.y(), maxDist.y());	266,961✔
162
163	const float minDistZ = std::min(minDist.z(), maxDist.z());	268,015✔
164	const float maxDistZ = std::max(minDist.z(), maxDist.z());	268,166✔
165
166	const float minHitDist = std::max(minDistX, std::max(minDistY, minDistZ));	266,503✔
167	const float maxHitDist = std::min(maxDistX, std::min(maxDistY, maxDistZ));	267,910✔
168
169	if (maxHitDist < std::max(minHitDist, 0.f))	266,406✔
170	return false;	55,181✔
171
172	// If reaching here with a negative distance (minHitDist < 0), this means that the ray's origin is inside the box
173	// Currently, in this case, the computed hit position represents the intersection behind the ray
174
175	if (hit) {	213,148✔
176	hit->position = m_origin + m_direction * minHitDist;	12✔
177
178	// Normal computing method based on John Novak's: https://blog.johnnovak.net/2016/10/22/the-nim-ray-tracer-project-part-4-calculating-box-normals/
179	const Vec3f hitDir = (hit->position - aabb.computeCentroid()) / aabb.computeHalfExtents();	12✔
180	hit->normal = Vec3f(std::trunc(hitDir.x()), std::trunc(hitDir.y()), std::trunc(hitDir.z())).normalize();	12✔
181
UNCOV 182	hit->distance = minHitDist;	×
183	}
184
185	return true;	212,897✔
186	}
187
188	Vec3f Ray::computeProjection(const Vec3f& point) const {	7✔
189	const float pointDist = m_direction.dot(point - m_origin);	7✔
190	return (m_origin + m_direction * std::max(pointDist, 0.f));	7✔
191	}
192
193	} // namespace Raz

Razakhel / RaZ / 14956332093

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous