光线追踪：球体相交检测实现 - 图形学每日挑战

每日编程挑战：光线与球体相交检测可视化

今天完成了光线追踪中的基础计算——光线与球体相交检测。这是光线追踪算法中最核心的几何计算之一，通过检测光线与球体的交点，为后续的材质、光照和阴影计算奠定基础。

项目概述

实现语言：C++ (C++11标准)
算法核心：光线-球体相交的几何计算
输出格式：400×300像素PNG图像
场景内容：单个球体，多方向光线可视化

核心算法：光线-球体相交

光线与球体的交点计算是光线追踪的基础问题。使用几何方法可以高效地计算交点。

数学公式推导

设：

光线：R(t) = O + t·d（O为原点，d为方向向量，t为参数）
球体：中心C，半径r，满足 ||P - C||² = r²

将光线方程代入球体方程：
||O + t·d - C||² = r²

展开得：
(O - C + t·d) · (O - C + t·d) = r²

令 OC = O - C，则：
(OC + t·d) · (OC + t·d) = r²
OC·OC + 2t(OC·d) + t²(d·d) = r²

整理得到一元二次方程：
a·t² + b·t + c = 0

其中：

a = d·d（方向向量的点积）
b = 2(OC·d)（OC与方向向量的点积的两倍）
c = OC·OC - r²（OC的点积减去半径平方）

交点判定

通过判别式 Δ = b² - 4ac 判断相交情况：

Δ < 0：无交点
Δ = 0：相切（一个交点）
Δ > 0：相交（两个交点）

代码实现

1. 向量类实现

struct Vec3 {
    float x, y, z;
    
    Vec3 operator+(const Vec3& v) const { return Vec3(x + v.x, y + v.y, z + v.z); }
    Vec3 operator-(const Vec3& v) const { return Vec3(x - v.x, y - v.y, z - v.z); }
    Vec3 operator*(float s) const { return Vec3(x * s, y * s, z * s); }
    Vec3 operator/(float s) const { return Vec3(x / s, y / s, z / s); }
    
    float dot(const Vec3& v) const { return x * v.x + y * v.y + z * v.z; }
    float length() const { return sqrt(x * x + y * y + z * z); }
    Vec3 normalize() const { return (*this) / length(); }
};

2. 相交检测函数

bool raySphereIntersect(const Ray& ray, const Sphere& sphere, float& t) {
    Vec3 oc = ray.origin - sphere.center;
    float a = ray.direction.dot(ray.direction);
    float b = 2.0f * oc.dot(ray.direction);
    float c = oc.dot(oc) - sphere.radius * sphere.radius;
    
    float discriminant = b * b - 4 * a * c;
    
    if (discriminant < 0) {
        return false; // 没有交点
    }
    
    float sqrtDisc = sqrt(discriminant);
    float t1 = (-b - sqrtDisc) / (2.0f * a);
    float t2 = (-b + sqrtDisc) / (2.0f * a);
    
    // 选择最近的正值交点
    if (t1 > 0 && t2 > 0) {
        t = (t1 < t2) ? t1 : t2;
        return true;
    } else if (t1 > 0) {
        t = t1;
        return true;
    } else if (t2 > 0) {
        t = t2;
        return true;
    }
    
    return false;
}

3. 光线生成与追踪

// 球体定义
Sphere sphere(Vec3(0, 0, 0), 1.0f);

// 多方向光线测试
for (int i = 0; i < numRays; ++i) {
    float phi = (i * 2.0f * M_PI) / numRays;
    Ray ray(Vec3(2.0f, 0, 0), 
            Vec3(cos(phi), sin(phi), 0).normalize());
    
    float t;
    if (raySphereIntersect(ray, sphere, t)) {
        // 计算交点位置
        Vec3 hitPoint = ray.origin + ray.direction * t;
        // 计算表面法线
        Vec3 normal = (hitPoint - sphere.center).normalize();
        // 简单着色
        float intensity = fabs(normal.dot(ray.direction));
        Vec3 color = Vec3(0.5, 0.7, 1.0) * intensity;
        
        // 记录结果
        colors.push_back(color);
    } else {
        // 没有相交，使用背景色
        colors.push_back(Vec3(0.1, 0.1, 0.1));
    }
}

可视化效果

输出图像展示了多个方向的光线与球体的相交情况：

相交区域：蓝色区域表示光线与球体相交
未相交区域：深灰色表示光线未命中球体
强度渐变：根据交点的法线方向产生亮度变化

图像中可以看到：

中心区域：光线与球体正面相交，颜色较亮
边缘区域：光线与球体侧面相交，颜色较暗
外围区域：光线完全错过球体，颜色最深

数学细节探讨

交点选择策略

当存在两个交点时（$t_1$和$t_2$），选择策略很重要：

最近交点：选择较小的$t$值（$t_1$）
外部进入：$t > 0$表示光线从外部进入球体
内部出发：$t < 0$表示光线从球体内部出发

数值稳定性优化

实际实现中需要考虑数值稳定性：

// 避免除零错误
if (fabs(a) < EPSILON) {
    // 处理特殊情况
}

// 使用双精度计算避免精度丢失
double a_d = static_cast<double>(a);
double b_d = static_cast<double>(b);
double c_d = static_cast<double>(c);

快速拒绝测试

对于复杂的场景，可以进行快速拒绝测试：

包围盒测试：先检测光线与球体包围盒的相交
距离阈值：预先排除过远的物体
方向过滤：排除方向错误的光线

性能分析

时间复杂度：O(1) 每光线-球体对
空间复杂度：O(1) 基本计算
浮点运算：约20次乘加运算
分支预测：1个主要分支（判别式判断）

优化后的近似计算：

// 优化形式1：避免重复计算
Vec3 oc = ray.origin - sphere.center;
float b = oc.dot(ray.direction);
float c = oc.dot(oc) - sphere.radius * sphere.radius;
float discriminant = b * b - c;  // 当a=1时

// 优化形式2：预计算信息
float radiusSq = sphere.radius * sphere.radius;  // 预计算平方

实际应用场景

光线-球体相交计算在实际中有广泛应用：

游戏引擎：碰撞检测、拾取操作
物理模拟：粒子系统、刚体碰撞
医学成像：CT/MRI数据球体标记
机器人学：传感器距离计算

扩展应用：多球体场景

std::vector<Sphere> spheres = {
    Sphere(Vec3(-1.5, 0, 0), 0.5),
    Sphere(Vec3(0, 0, 0), 1.0),
    Sphere(Vec3(1.5, 0, 0), 0.7)
};

for (const auto& sphere : spheres) {
    float t;
    if (raySphereIntersect(ray, sphere, t)) {
        hits.emplace_back(t, &sphere);
    }
}

// 选择最近的交点
std::sort(hits.begin(), hits.end());
if (!hits.empty()) {
    // 处理最近交点
}