绘制锯齿状、像素完美的 1px 样条曲线(特别是 Catmull-Rom) [英] Drawing aliased, pixel-perfect 1px splines (Catmull-Rom, specifically)

问题描述

简要背景:我正在开发一个基于 Web 的绘图应用程序，需要绘制 1px 粗的样条线以通过其控制点.

A brief background: I'm working on a web-based drawing application and need to draw 1px thick splines that pass through their control points.

我遇到的问题是，我需要像使用 1px 铅笔工具一样绘制 p1 和 p2 之间的每个像素.所以，没有抗锯齿，一次一个像素.这需要在不使用任何线/曲线库代码的情况下手动完成，因为我的画笔系统依赖于将画笔笔尖应用到画布的像素坐标.

The issue I'm struggling with is that I need to draw each of the pixels between p1 and p2 as if I were using a 1px pencil tool. So, no anti-aliasing and one pixel at a time. This needs to be done manually without the use of any line/curve library code as my brush system depends upon having a pixel coordinate to apply the brush tip to the canvas.

本质上，我需要将来自 Bresenham 算法之类的单像素步进与 Catmull-Rom 方程返回的坐标相结合.我遇到了麻烦，因为 Catmull-Rom 点不是均匀分布的(所以我不能只说曲线中应该有 100 个像素并运行方程 100 次).我尝试使用 X 和 Y 增量的最大值的估计起始值并用 Bresenham 填补空白，但由于四舍五入，我仍然得到一些脏"部分(即，线显然向上移动到是的，但我仍然得到两个具有相同 Y 分量的像素，从而导致线条的胖"部分).

Essentially, I need to combine the one pixel stepping from something like the Bresenham algorithm with the coordinates returned by the Catmull-Rom equation. I'm having trouble because the Catmull-Rom points are not uniformly distributed (so I can't just say there should be 100 pixels in the curve and run the equation 100 times). I tried using an estimated starting value of the maximum of the X and Y deltas and filling in the gaps with Bresenham, but due to rounding I still end up with some "dirty" sections (ie. the line is clearly moving up and to the right but I still get two pixels with the same Y component, resulting in a "fat" section of the line).

我确信这已经解决了，因为几乎每个绘制样条的图形程序都必须支持我所追求的干净的像素曲线.然而，经过相当多的数学研究，我有点困惑，仍然没有解决方案.有什么建议吗?

I'm positive this has been solved because nearly every graphics program that draws splines has to support the clean pixel curves that I'm after. After quite a bit of math research, though, I'm a bit confused and still without a solution. Any advice?

这是我可能需要渲染的曲线示例:

Here's an example of a curve that I might have to render:

可能有如下所示的预期结果(请注意，这是估计值):

Which might have an expected result looking like this (note that this is an estimate):

使用 Catmull-Rom 样条方程，我们需要四个点来创建线段.P0 和 P3 用作 P1->P2 段的传入和传出方向的切线.使用 Catmull-Rom 样条，当 t 从 0 移动到 1 时，蓝色部分是全部插值的.可以复制 P0 和 P3 以确保绿色部分得到渲染，所以这对我来说不是问题.

Using the Catmull-Rom spline equation, we need four points to create a segment. P0 and P3 are used as tangents for incoming and outgoing direction from the P1->P2 segment. With a Catmull-Rom spline, the blue section is all that gets interpolated as t moves from 0 to 1. P0 and P3 can be duplicated to ensure that the green portion gets rendered, so that is not an issue for me.

为简单起见，我需要在 P1 和 P2 之间的曲线上渲染像素，因为我有 P0 和 P3 形式的切线.我不一定需要使用 Catmull-Rom 样条，但它们似乎是这项工作的正确工具，因为必须通过控制点.插值点的非均匀分布让我陷入了循环.

For simplicity's sake, I need to render the pixels on the curve between P1 and P2, given that I have tangents in the form of P0 and P3. I don't necessarily need to use Catmull-Rom splines, but they seem to be the right tool for this job being that control points must be passed through. The non-uniform distribution of interpolation points is what's throwing me for a loop.

这是我说我的结果曲线很脏时我的意思的一个例子:

Here's an example of what I mean when I say my resulting curve is dirty:

红色箭头指出了一些不应有像素的位置.这是因为计算出的坐标的 X 和 Y 分量不会以相同的速率变化.因此，当每个分量都被四舍五入时(所以我有一个精确的像素位置)，可能是 X 或 Y 没有被提升，因为计算出的坐标是(42.4999, 50.98).将圆形换成地板或天花板并不能解决问题，因为它只是改变了发生的位置.

The red arrows point out a few locations where there should not be a pixel. This is occurring because the X and Y components of the coordinate that get calculated do not change at the same rate. So, when each of the components gets rounded (so I have an exact pixel location) it can be the case that either X or Y doesn't get bumped up because the calculated coordinate is, say, (42.4999, 50.98). Swapping the round for a floor or ceil doesn't solve the problem, as it just changes where it occurs.

推荐答案

这里有 一篇描述样条重新参数化方法的论文，以便在曲线长度上获得等距的点.我认为这可以解决你的问题，如果你能适应 Catmull-Rom 曲线(我猜应该不会太难)

Here you have a paper describing method for the re-parametrization of splines in order to get equally spaced points along the curve length. I think this can solve your problem if you can adapt it to Catmull-Rom curves (shouldn't be too difficult, I guess)

这篇关于绘制锯齿状、像素完美的 1px 样条曲线(特别是 Catmull-Rom)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！