R·ex / Zeng


音游狗、安全狗、攻城狮、业余设计师、段子手、苦学日语的少年。

从前端组件库引出的计算几何问题

注意:本文发布于 1571 天前,文章中的一些内容可能已经过时。

是的,又是那个组件库。由于脚手架搭的比较好,大家开发的效率超出了预期。然而总有些不顺利的事情出现,于是就有了这次要说的事情。

一个容易解决的问题

我们的 <Icon> 组件跟 Ant design 比较类似,底层用的是 SVG,这样可以通过按需引入以减小空间。由于 SVG 是设计师用 Illustrator 画的,里面必定会带有各种无关紧要的信息,因此同事在构建脚本中用 svgo 去掉了几乎所有用不到的数据。然而,我们发现不能去掉 fill 属性(通常 SVG 图标内部不能带有具体颜色的 fill,而是要指定 fill: currentColor 来保证页面可以为其设置“字体颜色”),否则有些图标会变成一个黑色方块。

经过审查元素我发现,所有变成了黑色方块的图标,都带有一个 <path d="M0 0H24V24H0Z" /> 的标签,这条路径很明显是一个占满了整张图像的正方形(我们的图标都是 24x24 的),似乎是 svgo 为了减少几个字节,将一个 <rect x="0" y="0" width="24" height="24" /> 转换而成的。当我们去掉了 fill 之后,默认的 fill 就是 #000000,自然就成了黑色方框。

我们去找了设计师,发现设计师为了方便设计,为每个图标都加了一个 24x24 的白色方框,将其删除就可以了。

盲生你发现了华点

虽然问题解决了,但一个疑问随之而来:既然设计师给每个图标都加了方框,为什么只有一部分图标会出问题呢?于是我又看向了之前那些没有问题的 SVG,发现 <path> 里面的路径是 M0 0H24V24H0M0 0H24V24H0M0 0H24V24H0M0 0H24V24H0Z,如果说之前那条路径是从左上角开始顺时针画了一个正方形,那这条路径就是额外又绕了三圈。这可能是 svgo 转换的问题,暂且不谈,只是想知道,为什么多绕了三圈之后反而没有问题了呢?

两种不同的填充规则

经过几次控制变量法之后,我们发现是一个叫 fill-rule 的属性在作怪。去 MDN 上面搜了一下,发现 中文版本 落后英文版本实在太远,于是顺手帮忙完整的翻译了一下。简单来说(为了方便起见,下文中所有的“线段”、“路径段”可能是直的,也可能是弯的,“多边形”则代指由任意多的“路径段”组成的一个封闭图形):

如何判断一个路径组成的多边形的内部区域,从而给它上色,对于一个简单的、没有交错的路径来说,是很显然的;然而,对于一个更为复杂的路径,比如一条与自身相交的路径,或者是这条路径上的其中一段将另一段包围着,要解释什么是“内部”,就不再这么显然了。

很显然我们那个绕了四圈的路径,就是绘制了一个复杂多边形。

两种绘制模式分别是 non-zeroevenodd,其中 non-zero 的原理是:

从该点向任意方向的无限远处绘制射线,然后检测形状与射线相交的位置。从 0 开始统计,路径上每一条从左到右(顺时针)跨过射线的线段都会让结果加 1,每条从右向左(逆时针)跨过射线的线段都会让结果减 1。当统计结束后,如果结果为 0,则点在外部;如果结果不为 0,则点在内部。

evenodd 的原理则是:

从该点向任意方向无限远处绘制射线,并统计这个形状所有的路径段中,与射线相交的路径段的数量。如果有奇数个路径段与射线相交,则点在内部;如果有偶数个,则点在外部。

设计师给的 SVG 的 fill-ruleevenodd,如果我从 (12, 12)(图标正中心)往正右方引射线,那么对于有问题的 SVG,射线只会与 1(奇数)条边相交;对于没问题的 SVG,射线会与 4(偶数)条边相交。因此前者的中心区域会被填充,而后者的中心区域不会。

那么该取哪个点、往哪个方向引射线呢?万一射线刚好穿过某个顶点,或者跟某条边重合了呢?鉴于 MDN 上面没有明确的结论,我又去翻 W3C,发现了这个:

The above descriptions do not specify what to do if a path segment coincides with or is tangent to the ray. Since any ray will do, one may simply choose a different ray that does not have such problem intersections.

通俗来讲就是:如果发生了路径段与射线相切(路径段可能是条曲线)或重合的情况,就换一条射线,总有射线不会出现这种情况。

计算几何中的解法

记得高中竞赛时期曾经做过一些计算几何相关的东西,其中一类算法就是判断一个点在多边形内还是外(还是边上),记得当时我比较熟悉的做法是:

从某一顶点开始沿着边行走,按顺序枚举多边形上的每个顶点,从该点往这些顶点依次引射线,将所有“前一条射线与当前射线的夹角”(逆时针为正,顺时针为负)求和,如果是 0 则表示点在多边形外部,不为 0(可能是 [math]2 \pi[/math] 或 [math]-2 \pi[/math] 的整数倍)则表示点在多边形内部。

这种做法只需要一个循环和一个夹角公式(可以由向量的点积公式得出),不需要复杂的判断,也无需考虑边是直线还是曲线,比之前的两种算法要简单的多,为什么 SVG 没有用这样的方法呢?我认为,可能是因为无法避免用到反三角函数(acos)和除法,对精度要求较高,运算速度也较慢。之前的两种做法无论是判断顺逆时针还是判断相交,都可以通过一些方式避免三角函数和除法,因此速度会更快一些。

还有一些其它算法,这篇文章 已经写的很好了,里面还附了代码,这儿就不再重复了。

番外:OpenGL 中的 Winding Rules / Numbers

在查资料的过程中,我发现 OpenGL 对于 non-zero 的支持更加完善,这篇文章 的最后一小节举了几个例子,分别是:

GLU_TESS_WINDING_ODD:如果结果是奇数则被填充,这是 OpenGL 的默认配置
GLU_TESS_WINDING_NONZERO:跟 SVG 的 non-zero 相同
GLU_TESS_WINDING_POSITIVE:如果结果是正数则被填充
GLU_TESS_WINDING_NEGATIVE:如果结果是负数则被填充
GLU_TESS_WINDING_ABS_GEQ_TWO:如果结果大于等于 2 则被填充

然而,想要在 OpenGL 中实现 evenodd,需要花一点功夫:先用 glStencilOpSeparate 先设置 Buffer,将所有 GL_FRONT(顺时针元素)所在区域加一,GL_BACK(逆时针元素)所在区域减一,然后使用 glStencilFunc 告诉 OpenGL 只绘制 Buffer 中为 1 的区域,也就变相的达到了 evenodd 的效果。

这并不是一个完美的解决方案,首先这只适用于多个闭合子路径的情况,不适合单一的、边与边相交的路径;此外必须指定路径的顺时针与逆时针。(由于我对 OpenGL 不熟悉,这一自然段不保证正确性,如果有错还请大佬们指出。)

我找到了一段使用了这个方法的 Python 示例,里面的图形是这个:

Odd-even fill rule using the stencil buffer

绘制的代码在 这里,可以在最下方看到作者通过变量 P 指定了每个顶点的坐标,变量 I 指定了三个正方形的顶点顺序。如果把第二行的顺时针改为逆时针,就无法得到上面的图像了,取而代之的是一个完整的灰色正方形。

参考资料

Disqus 加载中……如未能加载,请将 disqus.com 和 disquscdn.com 加入白名单。

这是我们共同度过的

第 3040 天