如何将粗的2D线渲染为多边形？ [英] How do I render thick 2D lines as polygons?
问题描述
我有一个由2D点列表组成的路径。我想把它们变成一个三角形的条纹，以便渲染具有指定厚度的纹理线条（以及其他类似的东西）。所以基本上，2D点的列表需要成为指定多边形轮廓的顶点列表，如果渲染将渲染线条。问题在于处理角连接，定位器，帽子等。由此产生的多边形需要在完全没有透支，干净连接等情况下完美，以便它可以被挤压或以其他方式玩弄。
是否有任何简单的资源可以提供算法洞察，代码或更多信息来有效地执行此操作？
我绝对不想要一个完整的2D矢量库（开罗，反锯齿，OpenVG等），包含曲线，弧线，破折号和所有的花里胡哨。我一直在为OpenVG实现和其他内容挖掘多个源代码树，以找到一些洞察力，但这一切都非常令人费解。
我肯定愿意自己编写代码，但是有很多退化的情况（小段+粗宽+尖角）造成各种连接问题。即使有一点帮助，也可以节省我几个小时的时间来处理这些问题。
编辑：下面是一个引起丑陋的退化案例之一，如果你只是为了从顶点到顶点。红色是最初的道路。橙色块是以指定宽度绘制的矩形，并以每个段为中心对齐。http://www.freeimagehosting.net/uploads/52dc639727.png
呵呵 - 我试图自己解决这个问题。我浪费了两个月试图解决零透支问题的解决方案。正如你已经发现你不能处理所有退化的案例，并同时零透支。
然而，你可以使用混合方法： p>
编写一个例程，检查连接是否可以由简单的几何体构造而不会出现问题。为此，您必须检查连接角度，线条宽度和连接线段的长度（比它们的宽度短的线段是PITA）。通过一些启发式方法，你应该能够理清所有微不足道的情况。
我不知道你的平均线数据是怎么样的，但在我的情况下， 90％的广告线没有退化的情况。
对于所有其他行：
可能已经发现，如果你容忍透支，生成几何图形要容易得多。这样做，并且让多边形CSG算法和镶嵌算法完成这项艰巨的工作。
我已经评估了大部分可用的tesselation软件包，并且我最终使用了GLU tesselator。它速度快，功能强大，从不崩溃（与大多数其他算法不同）。它是免费的，许可证允许我将它包含在商业程序中。 tesselation的质量和速度是可以的。你不会得到delaunay三角测量质量，但是因为你只需要渲染三角形，所以这不是问题。
由于我不喜欢tesselator API，因此我从免费的SGI OpenGL参考实现中提取了tesselation代码，重新编写了整个前端并添加了内存池以获取分配数量下。花了两天的时间来做到这一点，但它非常值得（如第五项性能改进）。这个解决方案在一个商业OpenVG实现中结束了：b）b）如果你在PC上使用OpenGL进行渲染，你可能想要移动tesselation / CSG-job从CPU到GPU并使用模板缓冲或z缓冲技巧来消除透支。这很容易，可能比CPU tesselation更快。
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?
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.
EDIT: 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.
http://www.freeimagehosting.net/uploads/52dc639727.png
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:
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.
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.
For all other lines:
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.
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.
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 :-)
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屋！
