如何将二维粗线渲染为多边形？
我有一条由二维点列表组成的路径。 我想将它们变成一条三角形，以便渲染具有指定厚度的纹理线（以及其他类似的东西）。 因此，本质上，二维点列表需要成为指定多边形轮廓的顶点列表，如果渲染该多边形，则将渲染该线。 问题是处理角连接、斜接、帽等。生成的多边形需要“完美”，没有过度绘制、干净的连接等，以便可以进行挤压或以其他方式进行操作。
是否有任何简单资源可以提供算法见解、代码或有关有效执行此操作的更多信息？
我绝对不想要一个完整的 2D 矢量库（cairo、antigrain、OpenVG 等），其中包含曲线、弧线、破折号和所有花哨的功能。 我一直在挖掘 OpenVG 实现的多个源代码树和其他东西来寻找一些见解，但这一切都非常复杂。
我绝对愿意自己编写代码，但是有许多退化的情况（小段+厚宽度+尖角）会产生各种连接问题。 即使是一点点的帮助也会节省我处理所有这些问题的时间。
编辑：这是一个退化案例的例子，如果你只是从一个顶点到另一个顶点，就会导致丑陋。 红色是原来的路径。 橙色块是以指定宽度绘制的矩形，在每个线段上对齐并居中。
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（9）
哦，好吧 - 我已经尝试自己解决这个问题了。 我在一个试图解决零透支问题的解决方案上浪费了两个月的时间。 正如您已经发现的，您无法处理所有退化情况并同时实现零透支。
但是，您可以使用混合方法：
自己编写一个例程，检查是否可以从简单的几何体毫无问题地构建连接。 为此，您必须检查连接角度、线的宽度和连接的线段的长度（比宽度短的线段是 PITA）。 通过一些启发式方法，您应该能够解决所有琐碎的情况。
我不知道你的平均线数据是什么样的，但在我的例子中，超过 90% 的宽线没有退化的情况。
对于所有其他线条：
您很可能已经发现，如果您容忍过度绘制，则生成几何图形会容易得多。 这样做，并让多边形 CSG 算法和曲面细分算法来完成这项艰巨的工作。
我已经评估了大多数可用的曲面细分包，最终选择了 GLU 曲面细分器。 它快速、强大、从未崩溃（与大多数其他算法不同）。 它是免费的，并且许可证允许我将其包含在商业程序中。 曲面细分的质量和速度都还不错。 您不会获得 delaunay 三角测量质量，但由于您只需要三角形进行渲染，所以这不是问题。
由于我不喜欢 tesselator API，因此我从免费的 SGI OpenGL 参考实现中提取了 tesselation 代码，重写了整个前端并添加了内存池以减少分配数量。 花了两天时间才完成此操作，但这是非常值得的（就像第五因子性能改进一样）。 该解决方案最终以商业 OpenVG 实现告终 :-)
如果您在 PC 上使用 OpenGL 进行渲染，您可能希望将曲面细分/CSG 作业从 CPU 移动到 GPU 并使用模板缓冲区或 z 缓冲区消除透支的技巧。 这比 CPU 曲面细分要容易得多，甚至可能更快。
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.
我刚刚发现了这个令人惊叹的作品：
http://www.codeproject.com/ Articles/226569/Drawing-polylines-by-tessellation
它似乎完全符合您的要求，并且其许可证甚至允许在商业应用程序中使用它。 另外，作者在详细说明他的方法方面做得非常出色。 我可能会在某个时候尝试一下，以取代我自己的不太完美的实现。
I just found this amazing work:
http://www.codeproject.com/Articles/226569/Drawing-polylines-by-tessellation
It seems to do exactly what you want, and its licence allows to use it even in commercial applications. Plus, the author did a truly great job to detail his method. I'll probably give it a shot at some point to replace my own not-nearly-as-perfect implementation.
我想到了一个简单的方法。
将每个 2d 顶点的角度一分为二，这将创建一条漂亮的斜接线。 然后沿着该线向内和向外移动“厚度”的量（或厚度除以二？），现在您有了内部和外部多边形点。 移动到下一个点，重复相同的过程，沿途构建新的多边形点。 然后应用三角剖分以获得可渲染的顶点。
A simple method off the top of my head.
Bisect the angle of each 2d Vertex, this will create a nice miter line. Then move along that line, both inward and outward, the amount of your "thickness" (or thickness divided by two?), you now have your inner and outer polygon points. Move to the next point, repeat the same process, building your new polygon points along the way. Then apply a triangualtion to get your render-ready vertexes.
我最终不得不亲自动手编写一个小ribbonizer来解决类似的问题。
对我来说，问题是我想要 OpenGL 中的粗线条，而不会出现我在 iPhone 上使用 OpenGL 时看到的那种伪影。 在查看了各种解决方案后； 贝塞尔曲线等 - 我认为制作自己的曲线可能是最简单的。 有几种不同的方法。
一种方法是找到两个线段之间的交叉角度，然后沿着该交叉线移动距离表面一定距离，并将其视为带状顶点。 我尝试了一下，但看起来并不直观； 色带宽度会有所不同。
另一种方法是实际计算线段表面的法线，并使用它来计算该线段的理想带状边缘，并在带状线段之间进行实际的相交测试。 这种方法效果很好，只是对于尖角，带状线段交叉点距离太远（如果段间角度接近 180'）。
我用两种方法解决了锐角问题。 Paul Bourke 线相交算法（我以未优化的方式使用）建议检测相交是否位于线段内部。 由于两个段是相同的，我只需要测试其中一个段的交叉点。 然后我可以仲裁如何解决这个问题； 要么通过捏造两端之间的最佳点，要么通过放置端盖 - 两种方法看起来都不错 - 端盖方法可能会破坏 opengl 的多边形正面/背面顺序。
请参阅 http://paulbourke.net/geometry/lineline2d/
在此处查看我的源代码：https://gist.github.com/1474156
I ended up having to get my hands dirty and write a small ribbonizer to solve a similar problem.
For me the issue was that I wanted fat lines in OpenGL that did not have the kinds of artifacts that I was seeing with OpenGL on the iPhone. After looking at various solutions; bezier curves and the like - I decided it was probably easiest to just make my own. There are a couple of different approaches.
One approach is to find the angle of intersection between two segments and then move along that intersection line a certain distance away from the surface and treat that as a ribbon vertex. I tried that and it did not look intuitive; the ribbon width would vary.
Another approach is to actually compute a normal to the surface of the line segments and use that to compute the ideal ribbon edge for that segment and to do actual intersection tests between ribbon segments. This worked well except that for sharp corners the ribbon line segment intersections were too far away ( if the inter-segment angle approached 180' ).
I worked around the sharp angle issue with two approaches. The Paul Bourke line intersection algorithm ( which I used in an unoptimized way ) suggested detecting if the intersection was inside of the segments. Since both segments are identical I only needed to test one of the segments for intersection. I could then arbitrate how to resolve this; either by fudging a best point between the two ends or by putting on an end cap - both approaches look good - the end cap approach may throw off the polygon front/back facing ordering for opengl.
See http://paulbourke.net/geometry/lineline2d/
See my source code here : https://gist.github.com/1474156
我对此也很感兴趣，因为我想完善我的地图应用程序 (Kosmos) 绘图道路。 我使用的一种解决方法是绘制折线两次，一次使用较粗的线，一次使用较细的线，并使用不同的颜色。 但这并不是真正的多边形，它只是模拟多边形的一种快速方法。 请参阅此处的一些示例：http://wiki.openstreetmap.org/wiki/Kosmos_Rendering_Help#Rendering_Options
我不确定这是否是您所需要的。
I'm interested in this too, since I want to perfect my mapping application's (Kosmos) drawing of roads. One workaround I used is to draw the polyline twice, once with a thicker line and once with a thinner, with a different color. But this is not really a polygon, it's just a quick way of simulating one. See some samples here: http://wiki.openstreetmap.org/wiki/Kosmos_Rendering_Help#Rendering_Options
I'm not sure if this is what you need.
我想我会采用曲面细分算法。 确实，在大多数情况下，使用这些的目的是减少顶点数量以优化渲染，但在您的情况下，您可以参数化以保留所有细节 - 并且优化的可能性可能会很有用。
网络上有许多曲面细分算法和代码 - 几年前，我将纯 C 封装在 DLL 中，以便与 Delphi 景观渲染器一起使用，并且它们对于高级图形编码教程等来说并不是一个不常见的主题。
I think I'd reach for a tessellation algorithm. It's true that in most case where these are used the aim is to reduce the number of vertexes to optimise rendering, but in your case you could parameterise to retain all the detail - and the possibility of optimising may come in useful.
There are numerous tessellation algorithms and code around on the web - I wrapped up a pure C on in a DLL a few years back for use with a Delphi landscape renderer, and they are not an uncommon subject for advanced graphics coding tutorials and the like.
看看Delaunay 三角测量是否有帮助。
See if Delaunay triangulation can help.
就我而言，我可以透支。 我只是在折线的每个顶点上绘制半径=宽度/2 的圆。
工件以这种方式被掩盖，并且如果您可以忍受“圆”角和一些过度绘制，那么它很容易实现。
In my case I could afford to overdraw. I just drow circles with radius = width/2 centered on each of the polyline's vertices.
Artifacts are masked this way, and it is very easy to implement, if you can live with "rounded" corners and some overdrawing.
从您的图像看来，您正在使用“填充”并使用橙色围绕线段绘制框。 这样做肯定会造成严重的透支。 因此，首先要做的就是不渲染黑色边框，并且填充颜色可以是不透明的。
为什么你不能使用 GL_LINES 原语来做你想做的事？ 您可以指定宽度、过滤、平滑度、纹理等任何内容。 您可以使用 glDrawArrays() 渲染所有顶点。 我知道这不是您想要的，但由于您专注于 2D 绘图，这可能是更简单的方法。 （搜索纹理线等）
From your image it looks like that you are drawing box around line segments with FILL on and using orange color. Doing so is going to create bad overdraws for sure. So first thing to do would be not render black border and fill color can be opaque.
Why can't you use GL_LINES primitive to do what you intent to do? You can specify width, filtering, smoothness, texture anything. You can render all vertices using glDrawArrays(). I know this is not something you have in mind but as you are focusing on 2D drawing, this might be easier approach. (search for Textured lines etc.)