随笔 - 85  文章 - 47  trackbacks - 0

常用链接

随笔分类

随笔档案

搜索

  •  

最新评论

Jack Ritter, "An Efficient Bounding Sphere" in Graphic Gems (1990)

1. 在三维点集S中找到较远的两点,构成一个初始包围球估计B0。该球可以如是求:遍历S,求出其中x坐标最大/最小、y最大/最小及z最大/最小的3对点,然后取其中距离最大的一对,以其二点连线中点为球心C0,距离的一半为初始半径R0
2. 然后再次遍历S,逐一测试S中其他点是否处于B中;
3. 如果点Pk处于Bk中,则继续测试下一个点Pk+1
4. 如果Pk不处于Bk中,则:作Bk的球心Ck与Pk的连线矢量(Ck,Pk),并反向延长至与Bk相交,交点为Qk,以连线(Qk,Pk)的中点为新的球心Ck+1,其距离的一半为新的球半径Rk+1,构成新的包围球Bk+1,不难发现,Bk与Bk+1相切于Qk
5. 上述过程迭代至所有S中的P点遍历完为止。以上近似算法可扩展到n维空间。
6. 该算法特点:快速,且包围球几乎最小,虽不能保证绝对最小,但绝对优于基于包围盒算出来的解



According to Jack Ritter a near-optimal sphere can be created by:
1) Finding the minimal and maximal vertices along each axis (x,y,z).
2) For those three pairs chose the one pair which has the largest distance.
3) The center of the sphere is the midpoint between those two vertices and its radius is half the distance between them.
4) Go through all vertices again, if you find a vertex whose distance (d) is greater than the radius (r), move the sphere towards this vertex by (d-r)/2 and then set the new sphere radius to (d+r)/2.

posted on 2008-05-05 02:32 w2001 阅读(889) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理