岁月流转,往昔空明

C++博客 首页 新随笔 联系 聚合 管理
  118 Posts :: 3 Stories :: 413 Comments :: 0 Trackbacks
一个在常数时间内确定一个点在Octree中所在的叶节点的路径,很猛的一个算法,比log n的普通判定算法要强的多。。。

如果我们有一个点(x, y, z),先把它们Normalize到[1, 2]区间里面;
紧接着提取出每个浮点后的23bit(底数部分,不明白的请参见IEEE标准);
将每个浮点的23bit按照zyx的方式逐bit排列,共有69bit;截取其中的64bit,作为叶节点的ID,其中每三个比特一组作为叶节点的路径。

ps,此文已经是第五手了。。。偶师父sama正在找源头的paper,等他找到了再说吧。

posted on 2007-10-26 17:41 空明流转 阅读(1026) 评论(2)  编辑 收藏 引用

评论

# re: Octree中点坐标所在的叶节点的快速求法[未登录] 2007-10-26 19:05 flyman
Normalize 是NDC转化?
如果是的话,区间好像有问题。  回复  更多评论
  

# re: Octree中点坐标所在的叶节点的快速求法 2007-10-26 21:52 Corner Zhang
嗯,hash法  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理