弧细分算法 [英] Arc subdivision algorithm

问题描述

我正在寻找从片段着色器中沿着圆弧的纹理中采样。这种排除了递归方法，如这。

我已经想出了几种不同的方法来实现这一点：两个似乎最合理的是（给定起始位置 p ，居中 c ，半径 r =长度（cp），角度（弧度范围） theta 弧度和 N 位置）：

<1>通过 theta / N ， N 次要的c关于c的计算：这需要构建一个将被重复使用的旋转矩阵：cost是两个trig函数， N 2×2矩阵相乘， N 左右的向量减法

2）找出一个段穿过一个扇区的和弦长度：它的长度是 2 * r * sin（theta / 2）。一旦我有了第一个向量，我就可以旋转它，并将它添加到前一个位置，以沿着我的弧线。这个方法的问题是，我仍然不知道表达式来获取我的长度 2 * r * sin（theta / 2）向量的方向。即使我做了我可能需要trig函数来构造它。我仍然需要旋转它，这可能需要我仍然建立一个旋转矩阵。啊。

有其他方法可以考虑吗？

解决方案

我认为一旦你开始使用圆和角度，你肯定会有一些trig调用。
鉴于此，第一种方法似乎确定。我只会注意到，我没有看到二维矩阵乘法的需要，因为如果这些点迭代操作。

  void f（float cx，float cy，float px，float py，float theta，int N）
 {
 float dx = px  -  cx; 
 float dy = py  -  cy; 
 float r2 = dx * dx + dy * dy; 
 float r = sqrt（r2）; 
 float ctheta = cos（theta /（N-1））; 
 float stheta = sin（theta /（N-1））; 
 std :: cout<< cx + dx<< ，<< cy + dy<<的std :: ENDL; 
 for（int i = 1; i！= N; ++ i）
 {
 float dxtemp = ctheta * dx  -  stheta * dy; 
 dy = stheta * dx + ctheta * dy; 
 dx = dxtemp; 
 std :: cout<< cx + dx<< ，<< cy + dy<<的std :: ENDL; 
 
 
  

给定大 N ，你可能会发现一些错误在这里累积。
给出一些假设，围绕 N 和 theta ，您可能可以对trig进行一些小角度近似。

总结：如果你想要指定数量的点并且正在使用弧，我看不出你真的会找到一种方法来做比计算少得多的计算接近选项1）。

I'm looking to sample from a texture along a circular arc in a fragment shader. That kind of rules out recursive methods such as this.

I have come up with a few different ways to accomplish this: Two that seem the most reasonable are (Given start position p, center c, radius r = length(c-p), angle (arc extent) theta in radians and N positions):

1) Rotate the vector p-c about c by theta/N, N times: This requires the construction of a rotation matrix which will be repeatedly used: cost is two trig functions, N 2x2 matrix multiplies, N or so vector subtractions

2) Find the chord length of one segment traversing a sector: Its length is 2*r*sin(theta/2). Once I have the first vector I can rotate it and add it to the previous position to "step along" my arc. The problem with this method is that I still don't know the expression to obtain the orientation of my length 2*r*sin(theta/2) vector. Even if I did I'd likely need trig functions to construct it. I still need to rotate it so that might require me to still build a rotation matrix. Ugh.

Are there other methods I could consider?

解决方案

I think that once you start using circles and angles you are bound to have a couple of trig calls. Given that, the first method seems OK. I'd only note that I do not see the need for 2D matrix multiplies as such if act iteratively on the points.

void f(float cx, float cy, float px, float py, float theta, int N)
{
    float dx = px - cx;
    float dy = py - cy;
    float r2 = dx * dx + dy * dy;
    float r = sqrt(r2);
    float ctheta = cos(theta/(N-1));
    float stheta = sin(theta/(N-1));
    std::cout << cx + dx << "," << cy + dy << std::endl;
    for(int i = 1; i != N; ++i)
    {
        float dxtemp = ctheta * dx - stheta * dy;
        dy = stheta * dx + ctheta * dy;
        dx = dxtemp;
        std::cout << cx + dx << "," << cy + dy << std::endl;
    }
}

Given large N, you might find that some errors accumulate here. Given some assumptions around N and theta you might be able to make some small angle approximations for the trig.

Summary: If you want the specified number of points and are using arcs, I cannot see that you are really going to find a way to do much less computation than something close to option 1).

这篇关于弧细分算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！