[场景管理]关于八叉树的困惑

cty41

花了两周慢慢吞吞吧随机迷宫给做了，其中一周多把框架改了。。。本来是那种半过程半对象式的，后来看了Jim Adams的书给全改成引擎的样子，视锥裁剪也写了，现在在看八叉树，看的迷迷糊糊的，我想请问大家些关于八叉树的的问题：

1.八叉树是用来划分场景，我想问的是存储的是物体的坐标么

2.数据是存在最底层的节点里么？（像哈夫曼树一样？）

我也看了些代码，但总是迷迷糊糊的...就是感觉八叉树我能理解但是就不知道该怎么用。。。


还有一个话外题，怎么判定做出来的demo性能可以呢？
如目前我做的这个随机3d迷宫，只做了一个地面和墙壁， 地面是用4个顶点缓冲画的，墙壁也是（不过2个方向都画了，为了防止到另一面就看不到墙壁），迷宫大小是50×50（想像成二维数组），墙壁就一个，只是放到世界坐标系的不同地方然后循环渲染，大概是有2600面墙就是5200×2= 10400个三角形（两面都画了所以×2），优化上只做了视锥裁剪，库页没有任何优化，直接用的DirectX库，现在的帧速大概稳定在33左右，这速度是不是很烂？？

希望大家能不能提点我下，现在又觉得许多自己都不会了。先谢谢各位了。


                               看八叉树不会看人物骨骼动画还是不明白人敬上                                

cty41

/*第一章图是在迷宫里的，最上面的值是fps下面是渲染了多少面墙（总共大概2600面）
第二幅图是俯视图。。。帧率掉的吓人*/
图不会贴。。上面的话就先注释掉好了。。

忘记说了。。我的电脑cpu是赛扬M360 1.4ghz， 1G内存， 集成烂显卡。。。。

zyfu0000

LZ看的什么书？

sjinny

没用八叉树做过渲染……
其实八叉树是对空间的分割，不管这个空间里有没有物体、物体在什么位置、物体有多大……
然后要把一个物体放进去的时候，需要在八叉树的所有层次里面找到一个合适的格子，使这个格子能够完全包裹住要放入的物体，如果有多个格子都合适，就应该用尺寸最小的那个格子。
然后使用的时候就是指定一个空间范围，然后让八叉树把这个空间范围内的对象告诉调用者。这个空间范围可能是个视锥（用于可视裁减），也可能是某个物体所占用的空间（用于碰撞检测），也可能是某个玩家的视野范围（用于在服务器端查询某个人能够看到哪些对象）。

cty41

zyfu0000: Re:[场景管理]关于八叉树的困惑

LZ看的什么书？

看的很乱额。。。现在在看的是《DirectX角色扮演游戏编程(原书第2版)》的英文版。。。中文的没得卖了。。
而且从图书馆把Game Programming Gems1，2，4的中文版借回来了，1里面也讲了八叉树没明白。。。阻塞裁剪那也没看明白。。

cty41

sjinny: Re:[场景管理]关于八叉树的困惑

没用八叉树做过渲染……
其实八叉树是对空间的分割，不管这个空间里有没有物体、物体在什么位置、物体有多...

有点开窍了，我再想想，过两天试着自己写写看，感觉学完基础到这一下子变难了许多。。真的多谢你的提示了，感觉明白好多，感激啊～～

能再问下关于我的帧速的问题么？是不是我写的太烂了，现在才33帧左右，窗口大小是640×480，别的数据如我上面所说的

sjinny

呃……不懂客户端……再说性能优化是要靠测量的，实际测量一下各个地方的耗时吧……不测量，再怎么猜测也不靠普……

我的印象里，场景管理主要是两种做法：
一种是对空间进行划分，比如四叉树/八叉树、打格子，各个节点的含义与空间中的物体无关，仅仅与被表达的空间本身有关
另一种是对空间中的物体进行划分，比如二叉树，递归逐维分组（GPG2  2.7），球形树（GPG2  4.3），这些节点所对应的空间范围其实是取决于空间中的物体分布的

前一种你把GPG1里的4.6、4.10、4.11和GPG2里的4.5看看，后一种只有GPG2里的2.7值得看，球形树那个讲得不是很详细，我没看懂 = =!

做空间划分，多画画图，特别是要利用一样东西：地砖……因为地砖一般是方形的网格，没有地砖就看看天花板上有没有格子…… = =!
有足够大的地砖的话，可以把自己当作物体，站在特定的位置然后看这时该怎么处理……




恩，想起来了，好像在哪看到过一个说法，说现代显卡处理三角形的能力都很高，所以很多时候应该以物体为基本单位进行管理，而不是以三角形为单位，因为后者可能会把本来连续的三角形带/扇给打乱，这个你可以搜一下……

cty41

刚考完四级～～恩，万分感谢～～～～彻底明白了～～下周虽然一堆考试，不过一定得做掉哈，哟活活～～