# 平民程序 - linghuye's blog

## Horizon Occlusion Culling

NND,图形学怎么有这么多的算法!一个接着一个,没完没了.一堆的论文要看,越学越难,越学越无知.看着国外的好书只能流口水,怎么赶得上人家的水平啊,做人的差距,咋就这么大呐,灰心寽.

1. How to walk through the elements in the scene in front-to-back ordering?
2. How to representation for the visibility occlusion horizon?
3. How give out a simplified representation of scene objects to be used for calculating occlusions with the horizon, ie, to test if the element is under the horizon?
4. How to add the visible elements' affection into horizon line?

Reference:
http://rivit.cs.byu.edu//a3dg/publications/horizonCullingVISFinal.pdf
http://www.cs.tau.ac.il/~dcor/online_papers/papers/visibility-survey-ieee.pdf

http://www.cs.lth.se/home/Tomas_Akenine_Moller/pubs/i3d2001.pdf
http://graphics.stanford.edu/courses/cs248-05/real-time-programming/moller-cs248-01-lecture.pdf

12.23

posted on 2005-11-29 00:31 linghuye 阅读(2937) 评论(22)  编辑 收藏 引用 所属分类: 3D图形学研究我的3D引擎 －DestinyMatrix

## #re: Horizon Occlusion Culling  回复更多评论

13391050336@133sh.com
2005-12-23 13:21 | superzeng

## #re: Horizon Occlusion Culling  回复更多评论

en,我的算法代码已经融进场景图结构,而且糅合了其他的LOD算法,再加上底层的数据结构,很难再抽出单独的算法代码了.基本按游戏编程4的思路来,原代码的
ClipLine的计算code_b的有严重错误,
Horizon::insert,Horizon::test中的y2 -= (right-x2) * dy;应该是y2 -= (right-x2) * dydx;

http://linghuye.nease.net/Tools/HorizonSomeCode.TXT
2005-12-23 15:13 | 平民程序

## #re: Horizon Occlusion Culling  回复更多评论

2005-12-23 17:02 | superzeng

## #re: Horizon Occlusion Culling  回复更多评论

2005-12-23 18:10 | superzeng

## #re: Horizon Occlusion Culling  回复更多评论

1.Horizon::test和Horizon::insert里的 y2 -= (right-x2) * dy;应该是y2 -= (right-x2) * dydx;

2.Bounding Node判断错误,我发现是有两个原因,第一个作者也说了:
// look at figure 4 again, and notice that min/max planes are not vertically
// aligned above each other in screen space because the perspective transform
// skews them horizontally - this is bad! the extra line checks below are
// therefore required to ensure proper bounding of the node samples.

if(x2 < 0 || x1 > width-1) { return BELOW; }

3.由近至远的裁减,我开始时抛弃了作者的做法,gamedev上有一篇讲8叉树的做法,4叉树类似,即:
int nFirstNode = ((camera.m_vPos.x < (m_vMin.x + m_vMax.x) * 0.5f)? 0 : 1) | ((camera.m_vPos.z < (m_vMin.z + m_vMax.z) * 0.5f)? 0 : 2);
m_pChildNodes[nFirstNode].CalculateVisibility(camera, horizon);
m_pChildNodes[nFirstNode^1].CalculateVisibility(camera, horizon);
m_pChildNodes[nFirstNode^2].CalculateVisibility(camera, horizon);
m_pChildNodes[nFirstNode^3].CalculateVisibility(camera, horizon);

3 4

2005-12-23 18:27 | 平民程序

## #re: Horizon Occlusion Culling  回复更多评论

2005-12-23 19:30 | superzeng

## #re: Horizon Occlusion Culling  回复更多评论

2005-12-23 19:48 | 平民程序

## #re: Horizon Occlusion Culling  回复更多评论

[ x , y , z , 1 ]经过投影的变换以后变为[ A, B, (z - zn ) * zf / (zf - zn), z ] ,w 保留的是z的值,当(z - zn ) * zf / (zf - zn) < 0 的时候, z < zn , 所以当z < zn 的时候,该点就位于近平面的后面.我看书上的代码这样写坐标变换: project * view ; 但是坐标投影的变换不是先经过view变换,再经过project的变换吗?是不是应该是 point * view * project = Screenpoint.
2005-12-23 22:43 | superzeng

## #re: Horizon Occlusion Culling  回复更多评论

(备忘)我推导了一下OpenGL(zf > zn > 0)中是得到的是:
[A, B, -z * (zf +zn)/(zf-zn) - 2*zf*zn/(zf-zn), -z]

=> z > -zn, => z > zn'(n' = -n,n'才是近平面值)

2005-12-24 11:29 | 平民程序

## #re: Horizon Occlusion Culling  回复更多评论

OGRE的思想是把地表取样,从眼睛点到目标tile连接线段,进行射线检测,你认为这样可行吗?速度会快吗?
2005-12-26 15:48 | superzeng

## #re: Horizon Occlusion Culling  回复更多评论

2005-12-26 20:19 | 平民程序

## #re: Horizon Occlusion Culling  回复更多评论

"DX的我有点怀疑他不做除 w 就判断<0为近平面外, 难道w恒正? 如果w为负,那么z就应该是 < 0 才能使得Normaiize device coordinate(NDC) > 0 "

2005-12-30 11:46 | pannan

## #re: Horizon Occlusion Culling  回复更多评论

2005-12-30 13:45 | 平民程序

## #re: Horizon Occlusion Culling  回复更多评论

2005-12-30 17:29 | pannan

## #re: Horizon Occlusion Culling  回复更多评论

"而由于在视点空间已用z=0来clip"

2005-12-30 17:41 | 平民程序

## #re: Horizon Occlusion Culling  回复更多评论

2005-12-31 01:55 | pannan

## #re: Horizon Occlusion Culling  回复更多评论

2006-03-17 16:00 | 0000

## #re: Horizon Occlusion Culling  回复更多评论

2006-03-20 17:29 | 0000

## #re: Horizon Occlusion Culling  回复更多评论

2007-04-10 16:40 | CDDB

## #re: Horizon Occlusion Culling回复更多评论

PS:my email is cddb.zhang@gmail.com
2007-04-10 16:45 | CDDB