写在前面
在先前的画光系列中，实现实体几何、反射、折射等效果，但是最大的一个缺陷是复杂度太高。当采样是1024时，渲染时间直线上升（用4线程），以至好几个小时才能完成一副作品，实现太慢。然而，当我看到用C++画光（一）这篇文章时，我有了一些思路。
我想到了【游戏框架系列】简单的图形学（一）系列文章中的思路，对啊，何必用SDF去慢慢逼近呢？用现成的解析几何算法去做不是更快吗？
过了一番摸索，终于有了题图。
要注意的地方
检测圆与直线相交的算法，我从用JavaScript玩转计算机图形学(一)光线追踪入门 - Milo Yip - 博客园抄来：
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，即不断迭代，最终逼近相交点。这种方法的问题就是迭代的次数太多，每次迭代都进行了同样的计算。
优化之后，计算相交点，我们直接用解析法，一个方程就能搞定，更棒的是，我们可以求出相交的最近点和最远点（这很重要！）。
方法的不同影响了渲染时间的多少。
怎样安排代码
我们先来看顶层调用（https://github.com/bajdcc/GameFramework/blob/master/CCGameFramework/base/pe2d/Render2DScene2.cpp#L72）：
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串联起来。
当然，后面还可以用重载让代码更简洁。
直线与圆相交算法在https://github.com/bajdcc/GameFramework/blob/master/CCGameFramework/base/pe2d/Geometries2D.cpp#L163中，上面已贴过。
如何实现两个图形的交、并、差？
这里才是本文重点，而实现这功能用了很多时间。
并：
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)即白色。
本文重点即两圆之间的交集、差集的解析法实现，还有直线与圆的相交算法。
程序下载：bajdcc/GameFramework