如何将粗 2D 线渲染为多边形? [英] How do I render thick 2D lines as polygons?

问题描述

我有一个由二维点列表组成的路径.我想将它们变成一条三角形，以便渲染具有指定厚度(以及其他此类东西)的纹理线.所以本质上，二维点列表需要成为一个顶点列表，指定多边形的轮廓，如果渲染将渲染线.问题是处理角连接、斜接、帽等.生成的多边形需要是完美的"多边形.在没有透支、干净的连接等的意义上，它可以被挤压或以其他方式被玩弄.

I have a path made up of a list of 2D points. I want to turn these into a strip of triangles in order to render a textured line with a specified thickness (and other such things). So essentially the list of 2D points need to become a list of vertices specifying the outline of a polygon that if rendered would render the line. The problem is handling the corner joins, miters, caps etc. The resulting polygon needs to be "perfect" in the sense of no overdraw, clean joins, etc. so that it could feasibly be extruded or otherwise toyed with.

是否有任何简单资源可以提供算法洞察、代码或有关有效执行此操作的更多信息?

Are there any simple resources around that can provide algorithm insight, code or any more information on doing this efficiently?

我绝对不想要一个完整的 2D 矢量库(cairo、antigrain、OpenVG 等)，包括曲线、弧线、破折号和所有花里胡哨的东西.我一直在为 OpenVG 实现和其他东西挖掘多个源代码树，以找到一些见解，但这一切都非常复杂.

I absolutely DO NOT want a full fledged 2D vector library (cairo, antigrain, OpenVG, etc.) with curves, arcs, dashes and all the bells and whistles. I've been digging in multiple source trees for OpenVG implementations and other things to find some insight, but it's all terribly convoluted.

我绝对愿意自己编写代码，但是有许多退化情况(小段 + 粗宽度 + 尖角)会产生各种连接问题.即使是一点点帮助，我也可以节省数小时的时间来处理它们.

I'm definitely willing to code it myself, but there are many degenerate cases (small segments + thick widths + sharp corners) that create all kinds of join issues. Even a little help would save me hours of trying to deal with them all.

这里有一个例子，说明如果你只是从一个顶点到另一个顶点，就会导致丑陋.红色是原始路径.橙色块是以指定宽度绘制的矩形，对齐并居中在每个线段上.

Here's an example of one of those degenerate cases that causes ugliness if you were simply to go from vertex to vertex. Red is the original path. The orange blocks are rectangles drawn at a specified width aligned and centered on each segment.

推荐答案

好吧 - 我已经尝试自己解决这个问题.我在试图解决零透支问题的解决方案上浪费了两个月.正如您已经发现的那样，您无法同时处理所有退化情况并实现零透支.

Oh well - I've tried to solve that problem myself. I wasted two month on a solution that tried to solve the zero overdraw problem. As you've already found out you can't deal with all degenerated cases and have zero overdraw at the same time.

然而，您可以使用混合方法:

You can however use a hybrid approach:

自己编写一个例程，检查连接是否可以从简单的几何图形中毫无问题地构造出来.为此，您必须检查连接角度、线的宽度和连接的线段的长度(比其宽度短的线段是 PITA).通过一些启发式方法，您应该能够解决所有琐碎的情况.

Write yourself a routine that checks if the joins can be constructed from simple geometry without problems. To do so you have to check the join-angle, the width of the line and the length of the joined line-segments (line-segments that are shorter than their width are a PITA). With some heuristics you should be able to sort out all the trivial cases.

我不知道你的平均线数据是什么样的，但在我的例子中，超过 90% 的宽线没有退化的情况.

I don't know how your average line-data looks like, but in my case more than 90% of the wide lines had no degenerated cases.

对于所有其他行:

您很可能已经发现，如果您容忍过度绘制，则生成几何图形会容易得多.这样做，让多边形 CSG 算法和曲面细分算法来完成这项艰巨的工作.

You've most probably already found out that if you tolerate overdraw, generating the geometry is a lot easier. Do so, and let a polygon CSG algorithm and a tesselation algorithm do the hard job.

我已经评估了大部分可用的曲面细分包，最后我使用了 GLU 曲面细分器.它快速、健壮、永不崩溃(与大多数其他算法不同).它是免费的，许可证允许我将其包含在商业程序中.镶嵌的质量和速度还可以.您不会获得 delaunay 三角剖分质量，但由于您只需要三角形进行渲染，这不是问题.

I've evaluated most of the available tesselation packages, and I ended up with the GLU tesselator. It was fast, robust, never crashed (unlike most other algorithms). It was free and the license allowed me to include it in a commercial program. The quality and speed of the tesselation is okay. You will not get delaunay triangulation quality, but since you just need the triangles for rendering that's not a problem.

由于我不喜欢 tesselator API，我从免费的 SGI OpenGL 参考实现中提取了 tesselation 代码，重写了整个前端并添加了内存池以减少分配的数量.这样做花了两天时间，但这是非常值得的(比如因子 5 的性能改进).该解决方案最终以商业 OpenVG 实现 btw :-)

Since I disliked the tesselator API I lifted the tesselation code from the free SGI OpenGL reference implementation, rewrote the entire front-end and added memory pools to get the number of allocations down. It took two days to do this, but it was well worth it (like factor five performance improvement). The solution ended up in a commercial OpenVG implementation btw :-)

如果您在 PC 上使用 OpenGL 进行渲染，您可能希望将曲面细分/CSG 作业从 CPU 移动到 GPU，并使用模板缓冲区或 z 缓冲区技巧来消除过度绘制.这比 CPU 细分要容易得多，甚至可能更快.

If you're rendering with OpenGL on a PC, you may want to move the tesselation/CSG-job from the CPU to the GPU and use stencil-buffer or z-buffer tricks to remove the overdraw. That's a lot easier and may be even faster than CPU tesselation.

这篇关于如何将粗 2D 线渲染为多边形?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！