“极坐标”--“直角坐标”效率讨论
li kuan
如附件中的图片，一个雷达扫描图像可以看成是一条线围绕一个点旋转组成的圆。
本处假定圆的半径是500，现在采集到一条条半径线（知道角度，和线性排列的500个点），想用OPenGL纹理（一个数组，1000*1000）的方式画出来，需要将这条线上所有点（极坐标）解析到这个数组（直角坐标）中。
转换可以用cos/sin，也就是三角变换来做，但因为数据是高速传来，这样不能满足要求；
现有改进是查表，在程序启动时计算完毕，用空间换时间的思路，但因为仍然要逐点进行处理，效率还是不高。
请问有没有做过类似问题的TLers有更高效的方法，谢谢
qiaojie
li kuan
HaoPeiQiang
--
Tinyfool的开发日记 http://www.tinydust.net/dev/
代码中国网 http://www.codechina.org
myTwitter: http://twitter.com/tinyfool
li kuan
但是，点数不是这么算的，每条线是一个数据单元，一个个数据单元是顺序传过来，最终实现雷达扫描效果，由于“极坐标-直角坐标”转换关系，在圆的中心部位，很多点会重叠，因而重复更新
On 7/18/10, HaoPeiQiang <HaoPe...@gmail.com> wrote:
> 1024*768=786432
机械唯物主义 : linjunhalida
只更新那个扫描到的部分不行吗？
遇到这种问题，我都会想想，实际展示出来的信息量多少，（n kb/s）
然后看看能否有O(n)或者O(n*lgn)的方法来展示这些数据。
2010/7/18 HaoPeiQiang <HaoPe...@gmail.com>:
li kuan
> 只更新那个扫描到的部分不行吗？
现在是用Opengl作图，整个数组作为纹理贴图的，也就是说不管每次更新几条线，整个数组是同时贴上去的，也是想找一种部分更新的方法，但受限于开发环境，没有找到。
不知你是否有好的建议，多谢。
DaiZW
qiaojie
li kuan
> 显示器的刷新率只有60Hz，你每秒刷新纹理60次就可以了，没必要来了数据就刷新，那样当然没效率。每秒画1M点对现在的CPU/GPU来说简直就是大象踩蚂蚁，10年前的CPU就可以达到这个性能了。
刷新不是瓶颈，上面也一直没提刷新会有问题
问题是 坐标解算
附件贴图
li kuan
> 不能画线段吗?
呵呵，数据里没有直角坐标信息，只有这条线当前角度和这条线半径上所有点的颜色值，也就是说，每个点的直角坐标是要结算出来的，这100万次结算让人很头疼，如何能快速完成是重点
机械唯物主义 : linjunhalida
DaiZW
这样就不需要你来手动计算, 由OpenGL库来负责.
qiaojie
for(0...500)
li kuan
> 如果：那500个点的角度是一样的，区别只是一个一维的长度。
> 只要算一次sin和cos，然后乘法就好了。
恩，对的，谢谢回答，这样是会比所有点都cos，sin要快
但我们现在的改进方案是把所有角度，所有点的位置都在程序刚启动时计算完毕，组成一个大表，用空间换时间，来了数据后直接每个点查表即可，但就是这样每个点的查表还是搞得系统很狼狈（呵呵，不知这个词这么用是否合适），我在想有没有整块的算法，可思考很久，也没有合适的方法
li kuan
> 或许可以把整个圆面分割成很多小的三角形或者长方形, 然后每次更新对应切片上的贴图.
> 这样就不需要你来手动计算, 由OpenGL库来负责.
谢谢，这在Opengl中是可以实现的么（切片，只更新切片），如果可以，有没有demo/入门级资料，十分感谢
li kuan
> x = y = 0;
> dx = cos(a) * step
> dy = sin(a) * step
> for(0...500)
> {
> DrawPixel(x, y);
> x += dx;
> y += dy;
> }
谢谢，我们现在用的是查表法（程序刚开始运行时可能需要一点时间），不知是否会比这个更快一些
when startup
build two large tables Tx[ANGLE][DISTANCE] and Ty[ANGLE][DISTANCE];
for(i = 0...500)
{
x = Tx[a][i];
y = Ty[a][i];
DrawPixel(x,y);
}
DaiZW
我说的只更新切片意思并不是说利用OpenGL的库只更新贴图的某个部分, 而是说由你来建立一个长方形的"切片", 每次去更新这个切片的贴图, 而不是更新整个圆的贴图. 从用户的角度看上去是一个圆, 但是在程序的角度是一个不停旋转的长方形(或者是很多个依次更新的长方形, 跟具体实现有关).
另外这个方法不一定比你手动计算效率要高.
wang carl
赵帅
然后直接构造这条线上的其他点。
Milo Yip
http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm
function line(x0, x1, y0, y1, data)
int current = 0;
...
; change plot(x, y) to
if (x * x + y * y > data[current] * data[current])
plot(x, y)
current = current + 1;
if (current >= data.size)
return;
不過如同許多網友說，我也認為這個問題的瓶頸不會在畫點上。
另一個簡單方法是把500個點畫在一個1D texture上，再把該1D texture畫上GPU上的render
target。那麼反而可以省很多bandwidth，也可以利用硬件的filtering功能。
--
Milo Yip
Twitter @miloyip
http://www.cnblogs.com/miloyip/
http://miloyip.seezone.net/
dachuan lin
rockeet
+x]=color[i]，然后周期性地将virtual_screen put 到device上就可以了。
On Jul 18, 10:27 pm, qiaojie <qiao...@gmail.com> wrote:
> x = y = 0;
> dx = cos(a) * step
> dy = sin(a) * step
> for(0...500)
> {
> DrawPixel(x, y);
> x += dx;
> y += dy;
>
> }
>
> 2010/7/18 li kuan <zyl.lik...@gmail.com>
>
>
>
> > On 7/18/10, qiaojie <qiao...@gmail.com> :
>
> > 显示器的刷新率只有60Hz，你每秒刷新纹理60次就可以了，没必要来了数据就刷新，那样当然没效率。每秒画1M点对现在的CPU/GPU来说简直就是大象踩蚂 蚁，10年前的CPU就可以达到这个性能了。
li kuan
> 另一個簡單方法是把500個點畫在一個1D texture上，再把該1D texture畫上GPU上的render
> target。那麼反而可以省很多bandwidth，也可以利用硬件的filtering功能。
1D texture 是个不错的思路，谢谢
amao
原始数据是极坐标形式，也就是(rho, theta)这样的组合，要画出来的话，需要转成直角坐标(x, y)这样的形式。你们现在用的变换或者查
表，都是从极坐标转到直角坐标的变换，即已知一点的极坐标(rho, theta)求其直角坐标(x, y)。这样的算法在数学上没有任何问题，但在实
际应用中，有以下几个缺点：
1、计算量大。正如楼主所说，每条扫描线上有500个点，总共是4000+条扫描线，周期约2秒，要计算每一点的直角坐标，运算量是很大的。
2、圆心处重复计算，圆周附近又可能漏画某些点。由于一周有4000+条扫描线，后一个问题可能不明显。但是圆心处的重复计算问题，楼主应该注意到
了。
其实，要解决这两个问题，只需要反过来计算就可以了，也就是由屏幕点的直角坐标计算其极坐标。
原来的计算方式可以描述为：每一个雷达数据点，如果画在屏幕上，其直角坐标应该是什么？
后一种计算方式可以描述为：用于显示雷达数据的屏幕区域中的每一点所对应的雷达数据是哪一个？
这样的话，计算量只跟屏幕区域的尺寸有关，而且只要不平移、不缩放、不旋转的话，每个屏幕上的点所对应的雷达点是固定的，只需要计算一次，显示时，每次
刷新只需要查表即可（表是固定的）。
我不知道我讲清楚了没有？
On 7月18日, 下午10时28分, li kuan <zyl.lik...@gmail.com> wrote:
> On 7/18/10, 机械唯物主义 : linjunhalida <linjunhal...@gmail.com> :
>
> > 如果：那500个点的角度是一样的，区别只是一个一维的长度。
> > 只要算一次sin和cos，然后乘法就好了。
>
> 恩，对的，谢谢回答，这样是会比所有点都cos，sin要快
>
> 但我们现在的改进方案是把所有角度，所有点的位置都在程序刚启动时计算完毕，组成一个大表，用空间换时间，来了数据后直接每个点查表即可，但就是这样每个点的查 表还是搞得系统很狼狈（呵呵，不知这个词这么用是否合适），我在想有没有整块的算法，可思考很久，也没有合适的方法
liuxinyu
li kuan
> 我的理解：
> 原始数据是极坐标形式，也就是(rho, theta)这样的组合，要画出来的话，需要转成直角坐标(x, y)这样的形式。你们现在用的变换或者查
> 表，都是从极坐标转到直角坐标的变换，即已知一点的极坐标(rho, theta)求其直角坐标(x, y)。这样的算法在数学上没有任何问题，但在实
> 际应用中，有以下几个缺点：
> 1、计算量大。正如楼主所说，每条扫描线上有500个点，总共是4000+条扫描线，周期约2秒，要计算每一点的直角坐标，运算量是很大的。
> 2、圆心处重复计算，圆周附近又可能漏画某些点。由于一周有4000+条扫描线，后一个问题可能不明显。但是圆心处的重复计算问题，楼主应该注意到
> 了。
>
> 其实，要解决这两个问题，只需要反过来计算就可以了，也就是由屏幕点的直角坐标计算其极坐标。
> 原来的计算方式可以描述为：每一个雷达数据点，如果画在屏幕上，其直角坐标应该是什么？
> 后一种计算方式可以描述为：用于显示雷达数据的屏幕区域中的每一点所对应的雷达数据是哪一个？
> 这样的话，计算量只跟屏幕区域的尺寸有关，而且只要不平移、不缩放、不旋转的话，每个屏幕上的点所对应的雷达点是固定的，只需要计算一次，显示时，每次
> 刷新只需要查表即可（表是固定的）。
>
> 我不知道我讲清楚了没有？
受教了，谢谢你仔细的回复，恩，对，反过来思考能节省大量的计算
oldherl
因为有些(rho, theta)并不能映射到整数像素上，或者说，一个屏幕像素可能对应着很多个(rho, theta)，如果只取其中的一个，则其
他点就无法显示。
比如在离圆心很近的一个圆周上，可能只有几十个像素，然而theta有上百种取值，就没办法画了。
也许可以对于每个像素点，算出它附近1像素范围内的区域里面对应着哪些(rho,theta)，然后把这些一起考虑，不过这样的效率和直接正向画不一定
有区别了。
On Jul 21, 1:12 pm, amao <maoziy...@gmail.com> wrote:
