通过细分绘制多段线

• 下载源代码 - 1.56 MB

引言

这可以看作是第一篇文章《在OpenGL中绘制近乎完美的2D线段》的第二集。在2D图形应用程序中，仅仅绘制线段是不够的。我们需要多段线。

分析

为什么我们不通过一组线段来绘制多段线呢？
如果这样做，段之间的连接处会产生间隙和过度绘制。右图是两条50%透明度的灰色线段。有一个很大的间隙，并且变暗的部分被绘制了两次。任何粗于1.5像素的多段线都不会看起来很好。

为了避免间隙和过度绘制（假装这个词是名词），需要适当的连接点处理。在Cairo和大多数图形库中常见的3种连接点类型是：

• 斜接
  获取每条线段的“外”边界并找到交点。使用交点作为尖端。然而，当线之间夹角很小时，交点会位于无穷远处。作为一种备用方案，当夹角小于临界值时，切换到斜切类型。
  这不是一个完美的解决方案，因为如果多段线是可动画的，它会从尖锐突然变为斜切。
• 斜切
  取两条线的“外”角并将它们连接起来形成一个斜切。
• 圆角
  以公共顶点为圆心，以线宽的一半为半径绘制一个圆。听起来很容易，但如果绘制不小心，会导致严重的过度绘制。

以及常见的端点类型

• 平头
  红线是线段的骨架，平头端点始终位于其内部。
• 圆角
  在线段的端点处绘制一个半径为线宽一半的半圆形。
• 方头
  视觉上与平头端点相同。线段在一个“方头端点”处延伸，延伸长度等于线宽的一半。

我们的方法

任何多段线都可以分解成一组3点多段线（“^”或“v”），我们称之为锚点。换句话说，基于锚点绘制例程，我们可以轻松构建多段线绘制例程。

通过镶嵌绘制多段线的工作流程

1. 我们收到构成多段线的一系列点，以及颜色、粗细和附加样式，如连接类型和端点类型
2. 将多段线分解成一组锚点并发出anchor()调用
3. 根据粗细计算锚点的几何形状（轮廓）
4. 将几何形状分解成不重叠的三角形
5. 根据轮廓，为三角形的每个顶点赋予带alpha的颜色
6. 输出三角形列表并将其发送到渲染管线，最终进行光栅化。

我们现在将一步一步地介绍这些步骤，除了第6步，以使本文不那么专注于OpenGL。

输入

假设我们通过以下方式接收点和颜色的数组

struct Point
{
	double x,y;
	//constructors and operator overloadings...
};
struct Color
{
	float r,g,b,a;
};
void polyline( const Point* P, const Color* C, int size_of_P,
         double weight, char joint_type, char cap_type);

并且Point类有许多方法和重载运算符，允许我们执行类似Point mid_point = (P[0]+P[1])*0.5;的操作。
我们很快就会发现为什么我们会收到一个颜色数组。

将多段线分解为锚点

有许多可能的分解方式，最简单的是在每个线段的中点处分解

1. 找到多段线每个线段的中点。P[0]和P[1]之间的中点被称为mid[0]
2. 将mid[0]替换为P[0]，将mid[size_of_P-2]替换为P[size_of_P-1]
3. 对于i=1到size_of_P-2，
   创建带有点[mid[i-1],P[i],mid[i]]的锚点

第一个锚点的第一个端点和最后一个锚点的最后一个端点必须被绘制。其余锚点没有端点。这意味着anchor()函数必须允许我们选择绘制哪个端点。

那么anchor()的声明应该像这样

void anchor( const Point* P, const Color* C,
         double weight, char joint_type, char cap_type,
         bool cap_first, bool cap_last);

锚点度量

P[0],P[1],P[2]	构成锚点的3个点
T[0]	线段[P[0],P[1]]的垂直向量，从P[0]指向锚点的外边界
T[2]	线段[P[1],P[2]]的垂直向量，从P[2]指向锚点的外边界
aT[1]	与T[0]相同，但放置在P[1]上
bT[1]	与T[2]相同，但放置在P[1]上
vP[1]	一个从P[1]指向 线段 [T'[0],aT'[1]] 和 [T'[2],bT'[1]] 交点的向量， 其中4个向量放置在各自的点上，例如T'[0]=T[0]+P[0]

为了获得向外向量，将向量T[0]=P[1]-P[0]逆时针旋转90度。如果点P[0],P[1],P[2]按顺时针顺序排列，则不执行任何操作。否则，将向量T[0]指向相反方向。然后归一化T[0]并缩放到所需的粗细。

在伪C++代码中，

Point T[3];
T[0] = P[1]-P[0];          T[2] = P[2]-P[1];
T[0] = perpen(T[0]);       T[2] = perpen(T[2]);
if ( signed_area(P[0],P[1],P[2]) > 0)
{
	T[0] = -T[0];      T[2] = -T[2];
}
T[0] = normalize(T[0]);    T[2] = normalize(T[2]);
T[0] *= weight;            T[2] *= weight;

Point perpen(Point P) //perpendicular: anti-clockwise 90 degrees
{
	return Point(-P.y,P.x);
}
double signed_area(Point P1, Point P2, Point P3)
{
	return (P2.x-P1.x)*(P3.y-P1.y) - (P3.x-P1.x)*(P2.y-P1.y);
}

计算两条线交点的方法在此处解释。假设我们有这样的实现：

int intersect( Point P1, Point P2, //line 1
               Point P3, Point P4, //line 2
               Point& Pout);       //output point
{ //Determine the intersection point of two line segments
  //http://paulbourke.net/geometry/lineline2d/
	double mua,mub;
	double denom,numera,numerb;
	const double eps = 0.000000000001;

	denom  = (P4.y-P3.y) * (P2.x-P1.x) - (P4.x-P3.x) * (P2.y-P1.y);
	numera = (P4.x-P3.x) * (P1.y-P3.y) - (P4.y-P3.y) * (P1.x-P3.x);
	numerb = (P2.x-P1.x) * (P1.y-P3.y) - (P2.y-P1.y) * (P1.x-P3.x);

	if ( (-eps < numera && numera < eps) &&
             (-eps < numerb && numerb < eps) &&
             (-eps < denom  && denom  < eps) ) {
		Pout.x = (P1.x + P2.x) * 0.5;
		Pout.y = (P1.y + P2.y) * 0.5;
		return 2; //meaning the lines coincide
	}

	if (-eps < denom  && denom  < eps) {
		Pout.x = 0;
		Pout.y = 0;
		return 0; //meaning lines are parallel
	}

	mua = numera / denom;
	mub = numerb / denom;
	Pout.x = P1.x + mua * (P2.x - P1.x);
	Pout.y = P1.y + mua * (P2.y - P1.y);
	bool out1 = mua < 0 || mua > 1;
	bool out2 = mub < 0 || mub > 1;

	if ( out1 & out2) {
		return 5; //the intersection lies outside both segments
	} else if ( out1) {
		return 3; //the intersection lies outside segment 1
	} else if ( out2) {
		return 4; //the intersection lies outside segment 2
	} else {
		return 1; //the intersection lies inside both segments
	}
}

然后通过以下方式找到vP

Point interP, vP;
intersect( T[0]+P[0],T[0]+P[1], T[2]+P[2],T[2]+P[1], interP);
vP = interP - P[1];

有了这些度量，我们可以轻松地对斜接连接和斜切连接的锚点进行三角剖分，但圆角连接不行。

内弧

如前所述，为了避免过度绘制，我们不能简单地在圆角连接处绘制一个圆。我们应该只通过从aT到bT创建内弧来填充间隙。内弧是两个指定角度之间两个可能弧中较短的一个。

首先，让我们看看基本弧的代码

void basic_arc( Point P, //origin
         float r,      //radius
         float dangle, //angle for each step
         float angle1, float angle2)
{
	bool incremental=true;
	if ( angle1>angle2) {
		incremental = false; //means decremental
	}

	if ( incremental) {
		for ( float a=angle1; a < angle2; a+=dangle)
		{
			float x=cos(a);    float y=sin(a);
			Point q( P.x+x*r,P.y-y*r); //the current point on the arc
		}
	} else {
		for ( float a=angle1; a > angle2; a-=dangle)
		{
			float x=cos(a);    float y=sin(a);
			Point q( P.x+x*r,P.y-y*r);
		}
	}
}

第一次尝试填充两个向量之间的弧

void basic_vectors_arc( Point P, //origin
         Point A, Point B,
         float r) //radius
{
	A = normalize(A);          B = normalize(B);
	float angle1=acos(A.x);    float angle2=acos(B.x); //A dot x-axis = A.x

	basic_arc( P,r,PI/18, angle1,angle2);
}

只有当 A 和 B 都向上时，它才能给出正确的结果。当其中任何一个向下时，都是错误的，请参阅交互式演示。一个原因是反余弦只返回 0 到 PI，即 0 到 180 度。要将范围扩展到 0 到 2*PI，在获取 acos() 值后执行此操作

if ( A.y>0){ angle1=2*PI-angle1;}
if ( B.y>0){ angle2=2*PI-angle2;}

内弧总是短于或等于半圆周。如果 angle2-angle1 大于 PI，则将 angle2 减去 2*PI。
考虑左边的图像。假设 angle1=120° 和 angle2=330°。如果弧线从 angle1 到 angle2 递增计算，它将是外弧。由于 angle2-angle1=210° > 180°，所以将 angle2 减去 360°，变为 -30°。根据 basic_arc 的定义，弧线现在从 angle2 到 angle1 递增计算，这是一条内弧。当 angle1 > angle2 时，也类似处理。

示例代码在同一位置。

然后，我们可以为圆角连接和圆角端点生成一个在aT和bT之间的三角形扇。左侧的三角剖分选择-vP作为扇形的表观中心。无论如何，如果锚点上的颜色都相同，三角剖分的形式无关紧要。否则，三角剖分确实会影响颜色插值。

应用颜色

我们收到一个颜色数组是因为我们想要进行逐顶点着色。着色有许多配置文件，就像孩子可以用蜡笔给汽车着色一样多。这里我们只给每个顶点它最近的输入顶点的颜色。

面对失败案例

上述镶嵌方法在大多数情况下都能正确绘制锚点。但当两条线段形成非常小的角度，重叠并开始退化成一条线段时则不行。在退化情况下，交点 vP 将位于无穷远处。我们现在有一组略有不同的度量。

为了识别退化，将绿色线段[T[2]+P[2], -T[2]+P[2]]与红色线段[-T[0]+P[1], -T[0]+P[0]]相交。如果交点TP位于两个线段内部，则发生退化。

再考虑一下点的顺序颠倒的情况。

幸运的是，接头不受影响。

渐隐多边形

为了使用第一篇文章中提到的“渐隐多边形技术”实现抗锯齿，或者只是为了使其更复杂，我们还可以渲染锚点的渐隐多边形。数学原理相同，所以这里不再赘述。

一个附加功能是我们可以任意缩放渐隐多边形的厚度以实现羽化效果。效果如何？非常酷！

右图：在OpenGL中实现带有圆角连接、圆角端点和羽化效果的anchor()。

介绍Vase Renderer

所有上述关于渲染多段线的想法都被实现为一个名为Vase Renderer的库。它是开源的。它还很年轻，所以它唯一的功能是polyline()。

Vase Renderer 旨在以不同的基础在 OpenGL 中创建高质量的 2D 图形。我们不考虑像素，而是考虑三角形。它试图打破 2D 图形库的历史限制。例如，Cairo、SVG 没有逐顶点颜色。它们不允许沿多段线变化颜色。并非他们想不到这个功能（我相信），只是支持可变颜色需要考虑太多，他们最好从头开始重新设计库。2D 计算机图形仍然需要进化。

手动镶嵌每个三角形的好处是您可以控制每个顶点的颜色、每个三角形的形式和整体拓扑。然后我们可以创建优雅的颜色混合。此外，虽然实现过程很艰难，但一旦完成，结果就会很好并且速度很快。

Using the Code

有关 Vase Renderer 的最新源代码、用法和问题，请访问当前文档页面。

限制

每个锚点都是单独处理的，彼此独立。在退化时，会发生过度绘制。如果多段线有颜色，这种伪影尤其明显。在当前的Vase Renderer实现中，当多段线的一个线段短于其自身的宽度时，结果将“失控”。这意味着实际上我们不能使用polyline()来绘制点密集的曲线。

无论如何，这些限制可以通过仔细（和痛苦的）检查来克服，就像本文中所有技术都是这样开发出来的一样。

希望本文的下一次更新将提供这些问题的解决方案。