算法背景
光线追踪（Ray Tracing）是计算机图形学中最逼真的渲染技术之一。与光栅化渲染不同，光线追踪通过模拟光线在场景中的传播路径——包括反射、折射和阴影计算——来生成图像。该方法自Whitted于1980年提出以来，已成为电影特效、建筑可视化和现代实时游戏渲染的核心技术。
核心思想
光线追踪的基本思路是从相机位置向每个像素发射一条光线，计算光线与场景中物体的交点，然后根据材质属性决定光线是反射、折射还是吸收，并递归追踪后续光线，最终累积颜色值。
光线与球体求交
光线方程为 P(t) = O + t*D，其中 O 为原点，D 为方向向量，t > 0。球体方程为 |P - C|^2 = r^2。联立后得到关于 t 的一元二次方程：
|D|^2 * t^2 + 2*D*(O-C)*t + |O-C|^2 - r^2 = 0
通过判别式判断交点情况：
– Δ > 0：两个交点，取最小正根
– Δ = 0：相切
– Δ < 0：无交点
加速结构：BVH树
对于复杂场景，逐物体求交效率极低。包围体层次结构（Bounding Volume Hierarchy, BVH）通过递归地将场景分割为轴对齐包围盒（AABB），大幅减少求交次数。
Java完整实现
import java.util.*;
/**
* 光线追踪渲染器：递归光线投射与BVH加速
*/
public class RayTracer {
// 三维向量
public static class Vec3 {
public double x, y, z;
public Vec3(double x, double y, double z) {
this.x = x; this.y = y; this.z = z;
}
public Vec3 add(Vec3 v) { return new Vec3(x + v.x, y + v.y, z + v.z); }
public Vec3 sub(Vec3 v) { return new Vec3(x - v.x, y - v.y, z - v.z); }
public Vec3 multiply(double s) { return new Vec3(x * s, y * s, z * s); }
public Vec3 multiply(Vec3 v) { return new Vec3(x * v.x, y * v.y, z * v.z); }
public double dot(Vec3 v) { return x * v.x + y * v.y + z * v.z; }
public Vec3 cross(Vec3 v) {
return new Vec3(y * v.z - z * v.y, z * v.x - x * v.z, x * v.y - y * v.x);
}
public double length() { return Math.sqrt(dot(this)); }
public Vec3 normalize() {
double len = length();
return len > 0 ? multiply(1.0 / len) : new Vec3(0, 0, 0);
}
public Vec3 reflect(Vec3 n) {
return sub(n.multiply(2.0 * dot(n)));
}
@Override
public String toString() {
return String.format("(%.2f, %.2f, %.2f)", x, y, z);
}
}
// 光线
public static class Ray {
public Vec3 origin, direction;
public Ray(Vec3 origin, Vec3 direction) {
this.origin = origin;
this.direction = direction.normalize();
}
public Vec3 at(double t) {
return origin.add(direction.multiply(t));
}
}
// 材质类型
public enum MaterialType { DIFFUSE, METAL, GLASS }
// 材质
public static class Material {
public Vec3 albedo; // 基础颜色
public MaterialType type;
public double fuzz; // 金属模糊度
public double refractionIndex; // 折射率
public Material(Vec3 albedo, MaterialType type) {
this.albedo = albedo;
this.type = type;
this.fuzz = 0.0;
this.refractionIndex = 1.0;
}
}
// 命中记录
public static class HitRecord {
public double t;
public Vec3 point;
public Vec3 normal;
public Material material;
public boolean frontFace;
public void setFaceNormal(Ray ray, Vec3 outwardNormal) {
frontFace = ray.direction.dot(outwardNormal) < 0;
normal = frontFace ? outwardNormal : outwardNormal.multiply(-1.0);
}
}
// 可求交物体接口
public interface Hittable {
boolean hit(Ray ray, double tMin, double tMax, HitRecord rec);
Vec3 getMinBounds();
Vec3 getMaxBounds();
}
// 球体
public static class Sphere implements Hittable {
public Vec3 center;
public double radius;
public Material material;
public Sphere(Vec3 center, double radius, Material material) {
this.center = center;
this.radius = radius;
this.material = material;
}
@Override
public boolean hit(Ray ray, double tMin, double tMax, HitRecord rec) {
Vec3 oc = ray.origin.sub(center);
double a = ray.direction.dot(ray.direction);
double halfB = oc.dot(ray.direction);
double c = oc.dot(oc) - radius * radius;
double discriminant = halfB * halfB - a * c;
if (discriminant < 0) return false;
double sqrtd = Math.sqrt(discriminant);
double root = (-halfB - sqrtd) / a;
if (root < tMin || root > tMax) {
root = (-halfB + sqrtd) / a;
if (root < tMin || root > tMax) return false;
}
rec.t = root;
rec.point = ray.at(root);
Vec3 outwardNormal = rec.point.sub(center).multiply(1.0 / radius);
rec.setFaceNormal(ray, outwardNormal);
rec.material = material;
return true;
}
@Override
public Vec3 getMinBounds() {
return new Vec3(center.x - radius, center.y - radius, center.z - radius);
}
@Override
public Vec3 getMaxBounds() {
return new Vec3(center.x + radius, center.y + radius, center.z + radius);
}
}
// BVH节点
public static class BVHNode implements Hittable {
public Hittable left, right;
public Vec3 boxMin, boxMax;
public BVHNode(List<Hittable> objects, int start, int end) {
int axis = new Random().nextInt(3); // 随机选择分割轴
objects.subList(start, end).sort((a, b) -> {
double aMin = axis == 0 ? a.getMinBounds().x :
(axis == 1 ? a.getMinBounds().y : a.getMinBounds().z);
double bMin = axis == 0 ? b.getMinBounds().x :
(axis == 1 ? b.getMinBounds().y : b.getMinBounds().z);
return Double.compare(aMin, bMin);
});
int span = end - start;
if (span == 1) {
left = right = objects.get(start);
} else if (span == 2) {
left = objects.get(start);
right = objects.get(start + 1);
} else {
int mid = start + span / 2;
left = new BVHNode(objects, start, mid);
right = new BVHNode(objects, mid, end);
}
boxMin = new Vec3(
Math.min(left.getMinBounds().x, right.getMinBounds().x),
Math.min(left.getMinBounds().y, right.getMinBounds().y),
Math.min(left.getMinBounds().z, right.getMinBounds().z)
);
boxMax = new Vec3(
Math.max(left.getMaxBounds().x, right.getMaxBounds().x),
Math.max(left.getMaxBounds().y, right.getMaxBounds().y),
Math.max(left.getMaxBounds().z, right.getMaxBounds().z)
);
}
@Override
public boolean hit(Ray ray, double tMin, double tMax, HitRecord rec) {
if (!hitAABB(ray, tMin, tMax)) return false;
boolean hitLeft = left.hit(ray, tMin, tMax, rec);
boolean hitRight = right.hit(ray, tMin, hitLeft ? rec.t : tMax, rec);
return hitLeft || hitRight;
}
// AABB包围盒求交
private boolean hitAABB(Ray ray, double tMin, double tMax) {
for (int a = 0; a < 3; a++) {
double invD = 1.0 / (a == 0 ? ray.direction.x :
(a == 1 ? ray.direction.y : ray.direction.z));
double t0 = ((a == 0 ? boxMin.x : (a == 1 ? boxMin.y : boxMin.z))
- (a == 0 ? ray.origin.x : (a == 1 ? ray.origin.y : ray.origin.z))) * invD;
double t1 = ((a == 0 ? boxMax.x : (a == 1 ? boxMax.y : boxMax.z))
- (a == 0 ? ray.origin.x : (a == 1 ? ray.origin.y : ray.origin.z))) * invD;
if (invD < 0) { double tmp = t0; t0 = t1; t1 = tmp; }
tMin = Math.max(t0, tMin);
tMax = Math.min(t1, tMax);
if (tMax <= tMin) return false;
}
return true;
}
@Override
public Vec3 getMinBounds() { return boxMin; }
@Override
public Vec3 getMaxBounds() { return boxMax; }
}
// 折射计算（斯涅尔定律）
public static Vec3 refract(Vec3 uv, Vec3 n, double etaiOverEtat) {
double cosTheta = Math.min(uv.multiply(-1.0).dot(n), 1.0);
Vec3 rOutPerp = uv.add(n.multiply(cosTheta)).multiply(etaiOverEtat);
Vec3 rOutParallel = n.multiply(-Math.sqrt(Math.abs(1.0 - rOutPerp.dot(rOutPerp))));
return rOutPerp.add(rOutParallel);
}
// 递归光线颜色计算
public static Vec3 rayColor(Ray ray, Hittable world, int depth) {
if (depth <= 0) return new Vec3(0, 0, 0);
HitRecord rec = new HitRecord();
if (!world.hit(ray, 0.001, Double.POSITIVE_INFINITY, rec)) {
// 背景：天蓝色渐变
double t = 0.5 * (ray.direction.normalize().y + 1.0);
return new Vec3(1.0, 1.0, 1.0).multiply(1.0 - t)
.add(new Vec3(0.5, 0.7, 1.0).multiply(t));
}
Vec3 attenuation = new Vec3(0, 0, 0);
Vec3 scatteredDir = new Vec3(0, 0, 0);
Random rand = new Random();
switch (rec.material.type) {
case DIFFUSE:
// 漫反射：随机散射
Vec3 target = rec.point.add(rec.normal)
.add(randomUnitVector(rand));
scatteredDir = target.sub(rec.point);
attenuation = rec.material.albedo;
break;
case METAL:
// 金属反射 + 模糊
Vec3 reflected = ray.direction.normalize().reflect(rec.normal);
scatteredDir = reflected.add(randomUnitVector(rand).multiply(rec.material.fuzz));
attenuation = rec.material.albedo;
if (scatteredDir.dot(rec.normal) <= 0)
return new Vec3(0, 0, 0);
break;
case GLASS:
// 玻璃：折射或反射
attenuation = new Vec3(1.0, 1.0, 1.0);
double refractionRatio = rec.frontFace ?
(1.0 / rec.material.refractionIndex) : rec.material.refractionIndex;
Vec3 unitDir = ray.direction.normalize();
double cosTheta = Math.min(unitDir.multiply(-1.0).dot(rec.normal), 1.0);
double sinTheta = Math.sqrt(1.0 - cosTheta * cosTheta);
boolean cannotRefract = refractionRatio * sinTheta > 1.0;
if (cannotRefract || reflectance(cosTheta, refractionRatio) > rand.nextDouble()) {
scatteredDir = unitDir.reflect(rec.normal);
} else {
scatteredDir = refract(unitDir, rec.normal, refractionRatio);
}
break;
}
Ray scattered = new Ray(rec.point, scatteredDir);
Vec3 color = rayColor(scattered, world, depth - 1);
return new Vec3(attenuation.x * color.x,
attenuation.y * color.y,
attenuation.z * color.z);
}
// 生成单位球内随机向量
public static Vec3 randomUnitVector(Random rand) {
while (true) {
Vec3 v = new Vec3(rand.nextDouble() * 2 - 1,
rand.nextDouble() * 2 - 1,
rand.nextDouble() * 2 - 1);
if (v.dot(v) < 1.0) return v.normalize();
}
}
// 菲涅尔反射近似
public static double reflectance(double cosine, double refIdx) {
double r0 = (1.0 - refIdx) / (1.0 + refIdx);
r0 = r0 * r0;
return r0 + (1.0 - r0) * Math.pow(1.0 - cosine, 5);
}
// 渲染场景（简化版，输出ASCII艺术）
public static void renderAscii(Hittable world, int width, int height) {
Vec3 cameraPos = new Vec3(0, 0, 0);
double viewportHeight = 2.0;
double viewportWidth = viewportHeight * ((double) width / height);
double focalLength = 1.0;
Vec3 horizontal = new Vec3(viewportWidth, 0, 0);
Vec3 vertical = new Vec3(0, viewportHeight, 0);
Vec3 lowerLeftCorner = cameraPos.sub(horizontal.multiply(0.5))
.sub(vertical.multiply(0.5))
.sub(new Vec3(0, 0, focalLength));
String[] shades = {" ", ".", ":", "-", "=", "+", "*", "#", "%", "@"};
System.out.println("光线追踪渲染结果（ASCII）：");
for (int j = height - 1; j >= 0; j--) {
StringBuilder line = new StringBuilder();
for (int i = 0; i < width; i++) {
double u = (double) i / (width - 1);
double v = (double) j / (height - 1);
Ray ray = new Ray(cameraPos,
lowerLeftCorner.add(horizontal.multiply(u))
.add(vertical.multiply(v))
.sub(cameraPos));
Vec3 color = rayColor(ray, world, 10);
// 伽马校正
double intensity = Math.sqrt(color.x) * 0.3 +
Math.sqrt(color.y) * 0.59 +
Math.sqrt(color.z) * 0.11;
int shadeIdx = (int) Math.min(intensity * shades.length, shades.length - 1);
line.append(shades[shadeIdx]);
}
System.out.println(line);
}
}
public static void main(String[] args) {
// 构建场景
List<Hittable> objects = new ArrayList<>();
// 地面
objects.add(new Sphere(new Vec3(0, -100.5, -1), 100.0,
new Material(new Vec3(0.8, 0.8, 0.0), MaterialType.DIFFUSE)));
// 中心球（玻璃）
Material glass = new Material(new Vec3(1.0, 1.0, 1.0), MaterialType.GLASS);
glass.refractionIndex = 1.5;
objects.add(new Sphere(new Vec3(0, 0, -1), 0.5, glass));
// 左侧球（漫反射）
objects.add(new Sphere(new Vec3(-1.0, 0, -1), 0.5,
new Material(new Vec3(0.7, 0.3, 0.3), MaterialType.DIFFUSE)));
// 右侧球（金属）
Material metal = new Material(new Vec3(0.8, 0.8, 0.8), MaterialType.METAL);
metal.fuzz = 0.3;
objects.add(new Sphere(new Vec3(1.0, 0, -1), 0.5, metal));
// 构建BVH加速结构
Hittable world = new BVHNode(objects, 0, objects.size());
// 渲染
renderAscii(world, 60, 30);
}
}
复杂度分析
| 场景 | 无加速 | BVH加速 |
|---|---|---|
| 时间复杂度（求交） | O(n) | O(log n) |
| 空间复杂度 | O(n) | O(n) |
| 构建开销 | 无 | O(n log n) |
对于包含1000个物体的场景，BVH可将单像素求交次数从平均500次降低到约10次，加速比可达50倍以上。
关键技术点
- 递归深度控制：防止无限递归，通常限制在10-50层
- 浮点精度处理：使用
t > 0.001避免自相交问题 - 伽马校正：将线性颜色空间转换为感知均匀空间
- 抗锯齿：每像素发射多条随机偏移光线取平均
扩展方向
- 路径追踪：蒙特卡洛积分实现全局光照
- HDR环境贴图：IBL实现真实环境反射
- 纹理映射：UV坐标采样位图纹理
- 运动模糊：时间维度采样实现动态模糊效果
总结
光线追踪通过物理模拟光线的传播行为，实现了照片级的渲染质量。BVH加速结构将求交复杂度从线性降低到对数级，使光线追踪在大规模场景中变得实用。掌握光线追踪原理，是理解现代GPU光追管线（如NVIDIA RTX）的基础。
