平民程序 - linghuye's blog

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

请问可以把你的算法共享一下?快要崩溃了.谢谢
13391050336@133sh.com

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

en,我的算法代码已经融进场景图结构,而且糅合了其他的LOD算法,再加上底层的数据结构,很难再抽出单独的算法代码了.基本按游戏编程4的思路来,原代码的
ClipLine的计算code_b的有严重错误,
Horizon::insert,Horizon::test中的y2 -= (right-x2) * dy;应该是y2 -= (right-x2) * dydx;
而且Demo故意不让镜头进入Bounding Node中,一旦进入,水平线test函数测试结果是错误的.
这是我的关键的代码段,是按OpenGL的剪裁方式计算的,DX的剪裁不能这么算. 咳,这种问题讲是讲不清楚的,还得靠自己理解.
http://linghuye.nease.net/Tools/HorizonSomeCode.TXT

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

不管看的懂还是看不懂,先谢谢了.
我用的是DX
最小二次方平面是按照书上求出的,但是我的裁减不正确
我的code_b也是改过的,他主要的意思是用z=0平面来裁减线段,最后都会使z<o的点变换到z=0的平面上
我的主要问题也是镜头进入Bounding Node中,判断出该Bounding Node投影到屏幕上的结果是错误的,还有就是由近到远的裁减也是有问题.不知道你的代码有提到吗?
谢谢.

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

还有请问一下,你的camera的m_pos是眼睛位置吗?还是通过眼睛点沿下方向得到的位置,因为就是这个问题使我从前往后遍力出现了问题.如果用眼睛的点,那么从天空往地面看的话就会有问题,因为眼睛点有可能处于屏幕的中心位置.一定是沿下方向得到的点吧,是不是?

# 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.
就是说需要完整判断8条bounding线段.
另一个错误,是当镜头在Bounding Node中且向下俯视小块区域时,不但最大平面在近平面之外,而且另外附加判断的4个bounding线段虽然在近平面之内,但是都落在了屏幕的左右外围,被horizon::test简单的返回false了,导致整个根节点被视为不可见.
if(x2 < 0 || x1 > width-1) { return BELOW; }
我的做法是:在这里将horizon::test返回true可见,但是在整个的外围做了一次镜头裁减BoxInFrustrum,因为通过了镜头裁减,则必有可见处,所以直接返回true.

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);
我是以x,z为平面,y为高度的,m_pChildNodes必须预先按 1 2 的Z型排列,m_vPos是眼睛位置.
3 4
作者的代码不同,遍历思路似乎是一样的,虽然不保证真正意义上的由近至远遍历,但能保证在每个x处总是近处的地平线先测试.即可能0->x/2先由近至远,再x/2->x由近至远,对算法而言是正确的.
原代码用一个frustum.base,屏幕NDC空间中镜头下方的1500单位点对应的世界空间点,我觉得简直莫名其妙,我是直接使用镜头位置,然后解决了2的向下俯视的问题.

我现在的结果是,水平裁减基本正确,但有一些没裁掉,由于算法是近似的,所以可以容忍.另外镜头不能落到地面以下,不能俯视超过90度,即不能倒着看世界(最大最小平面完全倒置了),否则算法会出现问题,这些也是符合实际的.

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

有一点看不懂,你的clipline是怎么想的?怎么使用z和w进行比较?

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

与DX不同,我使用的OpenGL的z映射到[-1,1],而不是DX的[0,1],而且按OpenGL Spec标准z裁减范围在 -w(近) <= z <= w(远)之间(实际的计算结果证明z确实是在这个之间),
而DX的我有点怀疑他不做除 w 就判断<0为近平面外, 难道w恒正? 如果w为负,那么z就应该是 < 0 才能使得Normaiize device coordinate(NDC) > 0

# 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.

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

书上(或者是研究3D图形学的惯例)说得是OpenGL式数学矩阵的思维方式M * v,而不是DX的v * M,所以书上的意思是: project * view * v,确实是先作view变换,再作projection变换,到DX那就变成了v * view * project.

经过DX的project的确是[A, B, (z - zn ) * zf / (zf - zn), z],这里的z是镜头坐标系空间的,z < zn的确成立.
(备忘)我推导了一下OpenGL(zf > zn > 0)中是得到的是:
[A, B, -z * (zf +zn)/(zf-zn) - 2*zf*zn/(zf-zn), -z]
推导不等式Vz < -Vw为: -z * (zf + zn) / (zf - zn) - 2 * zf * zn / (zf - zn) < -(-z)
=> z > -zn, => z > zn'(n' = -n,n'才是近平面值)
由于OpenGL的z指向观察者,即z正轴指向近平面外,因此z > zn'表明z在近平面外.

嘿嘿,大部分研究论文都依照OpenGL矩阵方式描述,用DX的同学们脑子有的转了.

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

请问你看过OGRE的水平线裁减吗?
OGRE的思想是把地表取样,从眼睛点到目标tile连接线段,进行射线检测,你认为这样可行吗?速度会快吗?

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

没看过,有时间再研究了.

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

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

他在视点空间已经用z = 0来clip，所以w肯定>=0,所以不存在你说的问题。

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

嘿嘿,W恒正吗?按DX标准:
如上所述的 w 是刚做完point * view * project 计算的结果w值,其值等于point * view结果的z值, 要知道我们做的是手动计算,而非DX管线,即*此时*我们*尚未*进行Clip操作,所以point * view的z值会<0,即w是会<0.
正因为w会<0, 我们才需要进一步进行手动计算近平面裁减,所以才会有这个问题.

实际上,不能使用除w得到的值做判断(你会发现除w的结果值不是一个连续的值域),应该使用上述superzeng的推导公式得出z < zn.

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

对啊，既然“结果w值,其值等于point * view结果的z值”，而由于在视点空间已用z=0来clip,则z >= 0,则最后w >= 0，怎么会有w < 0的情况呢 ?

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

"而由于在视点空间已用z=0来clip"
是谁自动执行的Clip计算? 哪一步进行的Clip? 是DX吗, modelview矩阵吗? 投影矩阵会吗?
此时Clip尚未发生,得自己计算.不信你弄个镜头正背后1000单位点,乘以view*project,看看w是正的不是,咳,很罗嗦.

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

我说的是game gems 4上的原代码,你可能误会我说dx了:(

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

请问你 wowmodelview 你编译通过了马？
少一个wx，下载了几个都不合适。

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

请问你 wowmodelview 你编译通过了马？
少一个wx，下载了几个都不合适。

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

呵呵 还有书上贴代码？
我现在正在根据paper实现算法。
一开始是以为蛮简单的算法，结果在结合四叉树扫描遍历场景上遇到了麻烦。
第一，是扫描的顺序，想起来容易，扫描扫描，呵呵。现在做的是结合四叉树的，用一个有限队列来排列有限处理的节点，层次的往下选择。
第二,效率。由于相机会运动，如果结合树的方式进行层次裁剪，那么树的节点都要一层层的进行视点变换，然后投影到z=-1平面，判断，然后决定是否继续往下走。想想都觉得恐怖，这些视点变化和投影的矩阵操作实在是会消耗很多时间。

请问平民，如何解决扫描顺序和扫描效率的？

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

PS:my email is cddb.zhang@gmail.com