写在前面
在先前的画光系列中，实现实体几何、反射、折射等效果，但是最大的一个缺陷是复杂度太高。当采样是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