 | [TOC] Chapter 5: Managing Primitives & Intersections |  |
Managing primitives and intersections is crucial in rendering as it forms the foundation of how objects in a scene are represented and interact with light. Primitives, such as rays, spheres, or planes, are essential building blocks. Efficiently handling these primitives and calculating intersections - where rays of light meet these objects - is key to producing accurate and realistic images. Optimizing these processes ensures faster rendering by reducing unnecessary calculations, which is especially important in complex scenes with many objects.
| Interacting with Primitives | |
Primitives are the fundamental geometric shapes that make up the scene. These shapes can be spheres, triangles, planes, or any other geometric objects that rays can intersect. When rays are cast into the scene, the goal is to find which primitive(s) the ray intersects, if any, and at what points these intersections occur.
Ray-Primitive Intersection
The ray is usually represented by the parametric equation:
\[
\mathbf{R}(t) = \mathbf{O} + t \cdot \mathbf{D}
\]
Where:
- \(\mathbf{R}(t)\) is the ray at parameter \(t\),
- \(\mathbf{O}\) is the ray's origin,
- \(\mathbf{D}\) is the ray's direction,
- \(t\) is the distance along the ray.
Each primitive has its own intersection function, for example, for a sphere, the ray-sphere intersection can be found using:
\[
(\mathbf{R}(t) - \mathbf{C}) \cdot (\mathbf{R}(t) - \mathbf{C}) = r^2
\]
where:
\(\mathbf{C}\) is the center of the sphere,
\(r\) is the radius of the sphere.
Solving for \(t\) gives the intersection points.
Example: Ray-Sphere Intersection in JavaScript
class Sphere {
constructor(center, radius) {
this.center = center;
this.radius = radius;
}
intersect(ray) {
const oc = subtract(ray.origin, this.center);
const a = dot(ray.direction, ray.direction);
const b = 2.0 * dot(oc, ray.direction);
const c = dot(oc, oc) - this.radius * this.radius;
const discriminant = b * b - 4 * a * c;
if (discriminant > 0) {
const t1 = (-b - Math.sqrt(discriminant)) / (2.0 * a);
const t2 = (-b + Math.sqrt(discriminant)) / (2.0 * a);
return Math.min(t1, t2); // Return the nearest intersection point
}
return null; // No intersection
}
}
| Aggregates | |
In complex scenes, there are often a large number of primitives. Testing ray intersections with each individual primitive would be inefficient. An aggregate is a data structure that groups primitives together to accelerate intersection tests.
Aggregates aim to reduce the number of intersection tests required by organizing primitives into a spatial structure, such as bounding volume hierarchies (BVH) or kd-trees. Instead of testing all primitives, we first test against the bounding volumes or partitions, which helps to cull large portions of the scene where no intersection occurs.
Example: Simple Aggregate
class Aggregate {
constructor(primitives) {
this.primitives = primitives;
}
intersect(ray) {
let nearest = Infinity;
let hit = null;
for (let primitive of this.primitives) {
const t = primitive.intersect(ray);
if (t && t < nearest) {
nearest = t;
hit = primitive;
}
}
return hit;
}
}
| Bounding Volume Hierarchies (BVH) | |
A Bounding Volume Hierarchy (BVH) is a tree structure that organizes primitives using bounding volumes. Each node in the BVH contains a bounding box that encloses a set of primitives, and each child node contains a smaller subset of primitives. When testing for ray intersections, the ray is first tested against the bounding volumes, reducing the number of primitives tested.
Steps in BVH Construction1. Partition the primitives into two subsets.
2. Create a bounding box around each subset.
3. Recursively repeat for each subset, creating a hierarchy of bounding boxes.
BVH Ray Intersection Algorithm • Start at the root node.
• If the ray intersects the bounding box, recursively test the child nodes.
• If the ray intersects a primitive, return the closest intersection.
Example: BVH in JavaScript
class BVHNode {
constructor(primitives) {
if (primitives.length === 1) {
this.primitive = primitives[0];
this.boundingBox = this.primitive.getBoundingBox();
} else {
this.left = new BVHNode(primitives.slice(0, Math.floor(primitives.length / 2)));
this.right = new BVHNode(primitives.slice(Math.floor(primitives.length / 2)));
this.boundingBox = mergeBoundingBoxes(this.left.boundingBox, this.right.boundingBox);
}
}
intersect(ray) {
if (!this.boundingBox.intersect(ray)) return null;
if (this.primitive) {
return this.primitive.intersect(ray);
}
const leftHit = this.left.intersect(ray);
const rightHit = this.right.intersect(ray);
if (!leftHit) return rightHit;
if (!rightHit) return leftHit;
return Math.min(leftHit, rightHit); // Return the closer intersection
}
}
| Kd-Tree Accelerator | |
A kd-tree (k-dimensional tree) is another spatial data structure used to accelerate ray-primitive intersections. It recursively partitions the 3D space into two halves using planes that are aligned with the coordinate axes. Each node in the tree represents a region of space, and leaf nodes contain the primitives.
Kd-Tree Construction • Choose an axis-aligned plane to split the space.
• Partition the primitives into two sets based on the plane.
• Repeat recursively for each subset, creating a binary tree.
Kd-Tree Ray Traversal • At each node, check if the ray intersects the plane.
• If the ray intersects both regions, recursively test both child nodes.
• If the ray only intersects one region, traverse that child node.
• At leaf nodes, test the ray against the primitives.
Example: Kd-Tree Construction in JavaScript
class KdTreeNode {
constructor(primitives, depth = 0) {
if (primitives.length === 0) {
this.isLeaf = true;
this.primitives = [];
return;
}
if (primitives.length <= 2 || depth > MAX_DEPTH) {
this.isLeaf = true;
this.primitives = primitives;
return;
}
const axis = depth % 3; // Cycle through x, y, z axes
primitives.sort((a, b) => a.center[axis] - b.center[axis]);
const mid = Math.floor(primitives.length / 2);
this.left = new KdTreeNode(primitives.slice(0, mid), depth + 1);
this.right = new KdTreeNode(primitives.slice(mid), depth + 1);
this.isLeaf = false;
}
intersect(ray) {
if (this.isLeaf) {
let hit = null;
for (let primitive of this.primitives) {
const t = primitive.intersect(ray);
if (t && (!hit || t < hit)) hit = t;
}
return hit;
}
// Traverse left or right based on ray direction
const leftHit = this.left.intersect(ray);
const rightHit = this.right.intersect(ray);
if (!leftHit) return rightHit;
if (!rightHit) return leftHit;
return Math.min(leftHit, rightHit); // Return closer hit
}
}
| Key Differences: BVH vs. Kd-Tree | |
Bounding Volume Hierarchy (BVH) uses bounding boxes around sets of primitives and typically has a binary tree where each node corresponds to a bounding volume.
Kd-Tree splits space into axis-aligned partitions and has a binary tree where each node represents a spatial region, not a bounding box.
|
