 | [TOC] Chapter 3: Rays, Geometry & Shapes |  |
Geometric objects are at the core of rendering scenes. Rays intersect with these shapes to compute color, light reflection, shadows, and more. Different geometric shapes require different methods for calculating ray intersections. We'll explore several common shapes used in ray-tracing, including spheres, cylinders, disks, quadrics, triangle meshes, curves, subdivision surfaces, and handling rounding errors.
| Spheres | |
Spheres are one of the simplest shapes to work with in ray-tracing. The equation for a sphere with center \( C \) and radius \( r \) is:
\[
(x - C_x)^2 + (y - C_y)^2 + (z - C_z)^2 = r^2
\]
To find whether a ray intersects a sphere, we need to solve for \( t \) in the ray equation:
\[
\mathbf{P}(t) = \mathbf{O} + t \mathbf{D}
\]
where:
\( \mathbf{O} \) is the ray's origin.
\( \mathbf{D} \) is the ray's direction.
\( \mathbf{P}(t) \) is a point along the ray.
Sphere-Ray Intersection Equation
The intersection equation for a ray with a sphere can be derived by plugging the ray equation into the sphere's equation:
\[
(\mathbf{O} + t \mathbf{D} - C) \cdot (\mathbf{O} + t \mathbf{D} - C) = r^2
\]
This simplifies to:
\[
(\mathbf{D} \cdot \mathbf{D})t^2 + 2\mathbf{D} \cdot (\mathbf{O} - C)t + (\mathbf{O} - C) \cdot (\mathbf{O} - C) - r^2 = 0
\]
This is a quadratic equation in \( t \). Solving for \( t \) gives the points where the ray intersects the sphere.
Example: Sphere-Ray Intersection in JavaScript
function intersectSphere(rayOrigin, rayDirection, sphereCenter, sphereRadius) {
let oc = subtract(rayOrigin, sphereCenter);
let a = dot(rayDirection, rayDirection);
let b = 2.0 * dot(oc, rayDirection);
let c = dot(oc, oc) - sphereRadius * sphereRadius;
let discriminant = b * b - 4 * a * c;
if (discriminant < 0) {
return null; // No intersection
} else {
let t1 = (-b - Math.sqrt(discriminant)) / (2.0 * a);
let t2 = (-b + Math.sqrt(discriminant)) / (2.0 * a);
return Math.min(t1, t2); // Return the closer intersection point
}
}
Here, the function computes the intersection of a ray with a sphere and returns the distance \( t \) to the intersection.
| Cylinders | |
The equation for a cylinder is more complex than for spheres. A cylinder along the \( z \)-axis with radius \( r \) is defined as:
\[
x^2 + y^2 = r^2 \quad \text{for} \quad z_1 \leq z \leq z_2
\]
Ray-Cylinder Intersection
For ray-cylinder intersections, we insert the ray equation into the cylinder's equation:
\[
(x_0 + t d_x)^2 + (y_0 + t d_y)^2 = r^2
\]
This simplifies to a quadratic equation in \( t \):
\[
a t^2 + b t + c = 0
\]
where:
\( a = d_x^2 + d_y^2 \)
\( b = 2(x_0 d_x + y_0 d_y) \)
\( c = x_0^2 + y_0^2 - r^2 \)
We solve this quadratic to find the intersection points, and then check whether they are within the cylinder's height limits.
Example: Cylinder-Ray Intersection in JavaScript
function intersectCylinder(rayOrigin, rayDirection, radius, zMin, zMax) {
let a = rayDirection.x * rayDirection.x + rayDirection.y * rayDirection.y;
let b = 2.0 * (rayOrigin.x * rayDirection.x + rayOrigin.y * rayDirection.y);
let c = rayOrigin.x * rayOrigin.x + rayOrigin.y * rayOrigin.y - radius * radius;
let discriminant = b * b - 4 * a * c;
if (discriminant < 0) {
return null; // No intersection
}
let t1 = (-b - Math.sqrt(discriminant)) / (2.0 * a);
let t2 = (-b + Math.sqrt(discriminant)) / (2.0 * a);
let z1 = rayOrigin.z + t1 * rayDirection.z;
let z2 = rayOrigin.z + t2 * rayDirection.z;
if (z1 < zMin || z1 > zMax) t1 = null;
if (z2 < zMin || z2 > zMax) t2 = null;
return t1 !== null ? t1 : t2;
}
This checks for ray-cylinder intersection and ensures that the intersection points lie within the cylinder's height limits.
| Disks | |
A disk is a flat circular object with a defined center, normal, and radius. The intersection of a ray with a disk requires first checking if the ray intersects the plane of the disk and then verifying if the point lies within the disk's radius.
Ray-Disk Intersection
1. First, compute the intersection with the plane using the plane equation \( \mathbf{N} \cdot (\mathbf{P} - \mathbf{P_0}) = 0 \).
2. Once we have the intersection point, check if it lies within the disk's radius.
Example: Disk-Ray Intersection in JavaScript
function intersectDisk(rayOrigin, rayDirection, diskCenter, diskNormal, diskRadius) {
let denom = dot(diskNormal, rayDirection);
if (Math.abs(denom) < 1e-6) return null; // Ray is parallel to disk
let t = dot(subtract(diskCenter, rayOrigin), diskNormal) / denom;
if (t < 0) return null; // Intersection is behind the ray origin
let hitPoint = add(rayOrigin, scale(rayDirection, t));
if (length(subtract(hitPoint, diskCenter)) <= diskRadius) {
return t; // Intersection point is inside the disk
}
return null; // Outside the disk
}
This function first checks for the ray-plane intersection and then ensures the intersection point lies within the disk.
| Other Quadrics | |
Quadrics represent a general class of shapes including spheres, ellipsoids, paraboloids, and hyperboloids. These shapes can all be described by a second-degree polynomial equation of the form:
\[
Ax^2 + By^2 + Cz^2 + Dxy + Exz + Fyz + Gx + Hy + Iz + J = 0
\]
The ray intersection with quadrics generally involves solving this polynomial equation for \( t \), similar to the methods we used for spheres and cylinders.
Example: Ray-Quadric Intersection (General Case)
function intersectQuadric(rayOrigin, rayDirection, quadricCoeffs) {
let A = quadricCoeffs.A;
let B = quadricCoeffs.B;
let C = quadricCoeffs.C;
let G = quadricCoeffs.G;
let H = quadricCoeffs.H;
let I = quadricCoeffs.I;
let J = quadricCoeffs.J;
// Form the quadratic equation as done with spheres and cylinders
// This will require solving for t using the general polynomial form
// Example of solving for t based on the quadratic form
}
This is a placeholder for the general intersection code, as the specific quadratic coefficients depend on the type of quadric.
| Triangle Meshes | |
Triangle meshes consist of a collection of triangles that approximate a surface. The ray-triangle intersection test is fundamental in many ray-tracers because meshes can represent complex models.
Ray-Triangle Intersection
For a triangle defined by vertices \( v_0, v_1, v_2 \), the ray-triangle intersection test involves solving the Muller-Trumbore intersection algorithm, which checks whether the ray intersects the plane containing the triangle and whether the intersection point is inside the triangle.
Example: Ray-Triangle Intersection in JavaScript
function intersectTriangle(rayOrigin, rayDirection, v0, v1, v2) {
let edge1 = subtract(v1, v0);
let edge2 = subtract(v2, v0);
let h = cross(rayDirection, edge2);
let a = dot(edge1, h);
if (Math.abs(a) < 1e-6) return null; // Ray is parallel to the triangle
let f = 1.0 / a;
let s = subtract(rayOrigin, v0);
let u = f * dot(s, h);
if (u < 0.0 || u > 1.0) return null;
let q = cross(s, edge1);
let v = f * dot
(rayDirection, q);
if (v < 0.0 || u + v > 1.0) return null;
let t = f * dot(edge2, q);
if (t > 1e-6) return t; // Intersection with the triangle
return null;
}
This is the standard Muller-Trumbore algorithm for detecting ray-triangle intersections.
| Curves in Ray-Tracing | |
Curves, such as Bezier curves, splines, and NURBS (Non-Uniform Rational B-Splines), are essential for modeling smooth and flexible shapes in 3D space. In ray-tracing, curves are more challenging to intersect than simple primitives like spheres or triangles because they require either precise mathematical methods or approximations to check ray intersections.
Types of Curves
1. Parametric Curves: Defined by a parametric equation that describes the position of a point along the curve as a function of a parameter \( t \), where \( t \in [0, 1] \).
- Bezier Curves: These are defined by a set of control points, and the curve is formed by a weighted average of these points.
- B-splines: Basis splines are a generalization of Bezier curves, providing better control over the curve's shape by introducing multiple control points over sections.
2. Implicit Curves: These are defined by an implicit equation, \( f(x, y, z) = 0 \), where the surface consists of all points that satisfy the equation.
Bezier Curves
The Bezier curve is defined by a set of control points \( P_0, P_1, \ldots, P_n \). For a cubic Bzier curve (the most common type), the parametric equation is:
\[
\mathbf{P}(t) = (1 - t)^3 P_0 + 3(1 - t)^2 t P_1 + 3(1 - t) t^2 P_2 + t^3 P_3
\]
Where \( t \in [0, 1] \) is the parameter that interpolates between the control points. The curve starts at \( P_0 \) when \( t = 0 \) and ends at \( P_3 \) when \( t = 1 \).
Ray-Curve Intersection
For ray-tracing curves, such as Bezier or B-splines, we typically either:
1. Approximate the curve with line segments or triangles, and then perform standard ray-line or ray-triangle intersection tests.
2. Solve the parametric equation for \( t \), which requires finding the points of intersection analytically or numerically (e.g., through iterative methods).
Example: Ray-Bzier Curve Intersection (Approximation)
One approach is to sample points along the Bezier curve by discretizing the parameter \( t \) and then performing ray-line intersection checks for the sampled points. This converts the continuous curve into a set of straight-line segments.
function evaluateBezier(t, p0, p1, p2, p3) {
let u = 1 - t;
return add(
scale(p0, u * u * u),
add(
scale(p1, 3 * u * u * t),
add(scale(p2, 3 * u * t * t), scale(p3, t * t * t))
)
);
}
function intersectRayWithBezier(rayOrigin, rayDirection, p0, p1, p2, p3, numSamples) {
let prevPoint = p0;
let tStep = 1.0 / numSamples;
for (let i = 1; i <= numSamples; i++) {
let t = i * tStep;
let pointOnCurve = evaluateBezier(t, p0, p1, p2, p3);
let intersection = intersectRayWithLine(rayOrigin, rayDirection, prevPoint, pointOnCurve);
if (intersection) {
return intersection; // Return the intersection point
}
prevPoint = pointOnCurve; // Move to the next segment
}
return null; // No intersection
}
In this code, we sample points along the Bezier curve and check each line segment for intersections with the ray. This method approximates the curve with straight-line segments.
| Subdivision Surfaces in Ray-Tracing | |
Subdivision surfaces are a powerful method for generating smooth surfaces from a coarse mesh. They work by iteratively refining a mesh, splitting its polygons into smaller polygons and adjusting the vertex positions to create a smooth limit surface.
Popular Subdivision Schemes
1. Catmull-Clark Subdivision: This is one of the most widely used subdivision methods, which works on polygonal meshes, especially quads. The algorithm:
- Splits each quad into four smaller quads.
- Averages vertex positions by computing new face points, edge points, and adjusting the old vertices.
- Repeats this process recursively, generating smoother and finer surfaces at each step.
2. Loop Subdivision: Similar to Catmull-Clark but operates on triangle meshes instead of quad meshes. It refines each triangle into four smaller triangles.
Subdivision Surface Ray-Tracing
Ray-tracing a subdivision surface is computationally expensive. Two common approaches are:
1. Precomputing the Refined Mesh: Precompute a high-resolution mesh from the coarse base mesh using a few iterations of the subdivision algorithm. Ray intersections can then be performed with the resulting triangle mesh.
2. Direct Subdivision on-the-fly: Subdivide surfaces dynamically during ray intersection tests. This requires refining only the areas where the ray might intersect, avoiding the need to compute the entire subdivided surface.
Catmull-Clark Subdivision Algorithm
The Catmull-Clark algorithm splits each face into smaller faces, computes new vertex positions based on edge and face points, and moves the original vertices to new positions according to the average of neighboring faces.
For a given face in the mesh:
- Face Point \( F \): The average of all vertices of the face.
- Edge Point \( E \): The average of the two adjacent face points and the two vertices forming the edge.
- Vertex Point \( V \): Adjusted based on neighboring edges and faces.
Example: Subdivision Surface Algorithm
ript
function subdivideCatmullClark(mesh) {
let newVertices = [];
let newFaces = [];
// 1. Compute face points
let facePoints = mesh.faces.map(face => {
return average(face.vertices);
});
// 2. Compute edge points
let edgePoints = computeEdgePoints(mesh, facePoints);
// 3. Compute new vertex positions
let newVertexPositions = computeVertexPoints(mesh, edgePoints, facePoints);
// 4. Create new faces by connecting face points, edge points, and new vertices
mesh.faces.forEach((face, i) => {
let fp = facePoints[i]; // Face point for the current face
face.edges.forEach(edge => {
let ep1 = edgePoints[edge]; // Edge point for the first vertex
let ep2 = edgePoints[edge.next]; // Edge point for the second vertex
let vp = newVertexPositions[edge.vertex]; // Adjusted vertex point
// Create new faces with these points (fp, ep1, ep2, vp)
newFaces.push(new Face(fp, ep1, vp, ep2));
});
});
return new Mesh(newVertices, newFaces);
}
This algorithm performs one iteration of Catmull-Clark subdivision, computing new face, edge, and vertex points and creating a finer mesh.
Ray-Subdivision Surface Intersection
For ray-subdivision surface intersections, we can:
1. Precompute the mesh: Subdivide the surface a few times and then perform ray-triangle intersection tests as usual.
2. Adaptive subdivision: Refine only the triangles the ray intersects dynamically to avoid unnecessary subdivisions.
Adaptive Subdivision Algorithm
For dynamic ray-tracing, adaptive subdivision involves recursively subdividing triangles only when the ray is near. This requires a bounding volume hierarchy (BVH) or a similar spatial acceleration structure to limit subdivision to relevant areas.
| Managing Rounding Error | |
In numerical ray-tracing, rounding errors are common due to finite precision. Methods for managing rounding error include:
• Epsilon values: Introduce a small threshold \( \epsilon \) when comparing floating-point numbers.
• Double precision: Use double-precision floats for calculations that require higher accuracy.
• Robust geometric predicates: Use algorithms that minimize the impact of floating-point errors.
Example: Handling Epsilon in JavaScript
const EPSILON = 1e-6;
function isZero(value) {
return Math.abs(value) < EPSILON;
}
This small utility function helps manage numerical precision errors when comparing floating-point numbers in intersection calculations.
|
