---

写在前面

在先前的画光系列中，实现实体几何、反射、折射等效果，但是最大的一个缺陷是复杂度太高。当采样是1024时，渲染时间直线上升（用4线程），以至好几个小时才能完成一副作品，实现太慢。然而，当我看到这篇文章时，我有了一些思路。

我想到了系列文章中的思路，对啊，何必用SDF去慢慢逼近呢？用现成的解析几何算法去做不是更快吗？

过了一番摸索，终于有了题图。

要注意的地方

检测圆与直线相交的算法，我从抄来：

intersect : function(ray) {        var v = ray.origin.subtract(this.center);        var a0 = v.sqrLength() - this.sqrRadius;        var DdotV = ray.direction.dot(v);        if (DdotV <= 0) {            var discr = DdotV * DdotV - a0;            if (discr >= 0) {                var result = new IntersectResult();                result.geometry = this;                result.distance = -DdotV - Math.sqrt(discr);                result.position = ray.getPoint(result.distance);                result.normal = result.position.subtract(this.center).normalize();                return result;            }        }        return IntersectResult.noHit;    }

但这里有所不同：3D中的光线追踪是有视角的，也就是说，光线来自同一个点，即摄像机的位置，因此，光线的起点不会在几何图形内部！！而2D中，我们的渲染方式有所不同，光线来自2D区域中的每一个点上，因此，光线起点可能在图形内部。

所以修改后的代码是这样：

Geo2DResult Geo2DCircle::sample(vector2 ori, vector2 dir) const{    // 圆上点x满足： || 点x - 圆心center || = 圆半径radius    // 光线方程 r(t) = o + t.d (t>=0)    // 代入得 || o + t.d - c || = r    // 令 v = o - c，则 || v + t.d || = r    // 化简求 t = - d.v - sqrt( (d.v)^2 + (v^2 - r^2) )  (求最近点)    // 令 v = origin - center    auto v = ori - center;    // a0 = (v^2 - r^2)    auto a0 = SquareMagnitude(v) - rsq;    // DdotV = d.v    auto DdotV = DotProduct(dir, v);    //if (DdotV <= 0)    {        // 点乘测试相交，为负则同方向        auto discr = (DdotV * DdotV) - a0; // 平方根中的算式        if (discr >= 0)        {            // 非负则方程有解，相交成立            // r(t) = o + t.d            auto distance = -DdotV - sqrtf(discr); // 得出t，即摄影机发出的光线到其与圆的交点距离            auto distance2 = -DdotV + sqrtf(discr);            auto position = ori + dir * distance; // 代入直线方程，得出交点位置            auto normal = Normalize(position - center); // 法向量 = 光线终点(球面交点) - 球心坐标            if (a0 <= 0 || distance >= 0)// 这里不一样！！                return Geo2DResult(this, a0 <= 0, distance, distance2, position, normal);        }    }    return Geo2DResult(); // 失败，不相交}

相交算法实质上是用参数方程代入求解，得出参数t，其实就是距离。有一种情况是无效的，需要注意，就是当距离为负且光线起点不在图形内部时，这样一种解是无效的，因为我们的线是射线。

为什么渲染速度变快了

原来的方法是SDF，即不断迭代，最终逼近相交点。这种方法的问题就是迭代的次数太多，每次迭代都进行了同样的计算。

优化之后，计算相交点，我们直接用解析法，一个方程就能搞定，更棒的是，我们可以求出相交的最近点和最远点（这很重要！）。

方法的不同影响了渲染时间的多少。

怎样安排代码

我们先来看顶层调用（）：

root = Geo2DFactory:: or (	Geo2DFactory:: and (		Geo2DFactory::new_circle(1.3f, 0.5f, 0.4f, color(2.0f, 1.0f, 1.0f)),		Geo2DFactory::new_circle(1.7f, 0.5f, 0.4f, color(2.0f, 1.0f, 1.0f))),	Geo2DFactory:: sub (		Geo2DFactory::new_circle(0.5f, 0.5f, 0.4f, color(1.0f, 1.0f, 2.0f)),		Geo2DFactory::new_circle(0.9f, 0.5f, 0.4f, color(1.0f, 1.0f, 2.0f))));

结果就是题图，代码定义了两个图形，一个是两圆相交and，一个是两圆sub，两个图形用or串联起来。

当然，后面还可以用重载让代码更简洁。

直线与圆相交算法在中，上面已贴过。

如何实现两个图形的交、并、差？

这里才是本文重点，而实现这功能用了很多时间。

并：

if (op == t_union){    const auto r1 = obj1->sample(ori, dst);    const auto r2 = obj2->sample(ori, dst);    return r1.distance < r2.distance ? r1 : r2;}

很好解释，直线扫到两个图形上，如果没交点，那么distance就是无穷大，如果有交点，就取距离较近的图形。

---

交：

if (op == t_intersect){    const auto r1 = obj1->sample(ori, dst);    if (r1.body)    {        const auto r2 = obj2->sample(ori, dst);        if (r2.body)        {            const auto rd = ((r1.inside ? 1 : 0) << 1) | (r2.inside ? 1 : 0);            switch (rd)            {            case 0: // not(A or B)                if (r1.distance < r2.distance)                {                    if (r2.distance2 > r1.distance && r2.distance > r1.distance2)                        break;                    return r2;                }                if (r2.distance < r1.distance)                {                    if (r1.distance2 > r2.distance && r1.distance > r2.distance2)                        break;                    return r1;                }                break;            case 1: // B                if (r1.distance < r2.distance2)                    return r1;                break;            case 2: // A                if (r2.distance < r1.distance2)                    return r2;                break;            case 3: // A and B                return r1.distance > r2.distance ? r1 : r2;            default:                break;            }        }    }}

代码中distance是最近交点（较小根），distance2是最远交点（较大根）。

交就复杂得多，首先，光线必须与两个图形都有交点，其次，分四种情况（我喜欢这样写两个bool的分类讨论。。），讨论光线起点与两个图形的位置关系。

第一，讨论光线起点不在两圆中。

交集的情况

分六种情况(C{2,4}=6)，其中两种情况为不相交，剩下四种情况为相交，代码中就是这个思路。

第二，讨论光线起点在B中，显而易见，交点就是A的边界

第三，讨论光线起点在A中，显而易见，交点就是B的边界

第四，讨论光线起点在A交B中，这里必相交

---

差：

if (op == t_subtract){    const auto r1 = obj1->sample(ori, dst);    const auto r2 = obj2->sample(ori, dst);    const auto rd = ((r1.body ? 1 : 0) << 1) | (r2.body ? 1 : 0);    switch (rd)    {    case 0: // not(A or B)        break;    case 1: // B        break;    case 2: // A        return r1;    case 3: // A and B        if (r2.inside)        {            if (r1.distance2 > r2.distance2)            {                auto r(r2);                r.body = r1.body;                r.inside = false;                r.distance = r.distance2;                return r;            }            break;        }        if (r1.inside)        {            return r1;        }        if (r2.distance < r1.distance)        {            if (r1.distance2 < r2.distance2)            {                break;            }            auto r(r2);            r.body = r1.body;            r.inside = false;            r.distance = r.distance2;            return r;        }        return r1;    default:        break;    }}

差的实现也不简单，讨论射线与两圆的相交情况：

第一：射线与两圆都不相交，那射线与A-B也不相交

第二：射线与B相交，与A不相交，那射线与A-B也不相交

第三：射线与A相交，与B不相交，射线必定与A-B相交

第四：射线与A交B相交，这时情况复杂了

差集的情况

只考虑两种不相交的情况，如图。反映在代码中就是两个break。

小结

渲染的结果有所不同，发光图形本身的颜色是白色的，这是因为定义时的颜色是RGB(2.0f,1.0f,1.0f)，最终采样经平均后呈现时还是RGB(2.0f,1.0f,1.0f)，做了一个截断之后就是RGB(1.0f,1.0f,1.0f)即白色。

本文重点即两圆之间的交集、差集的解析法实现，还有直线与圆的相交算法。

程序下载：

由备份。