building bvh for mesh

mesh的bvh的用处很多， 在raytrace中很重要，在collision detection也常用。建立方法不是很难，方法也很多，要做到非常优秀的结果是比较难的。常见的方法：

1：octree（这个在场景管理中也比较常见，用来建立mesh的bvh也可以）

2： bvh（这里是狭义的bvh，基于二分法，可选择不同策略）

法一 ：我用在了场景管理中，所以没有采用它生成mesh的bvh，其实使用过程中也发现octree比较适合松散的物体，而对于一个mesh，它的三角面一般比较集中。另外，octree是基于空间等分的，对于三角面而言，边缘交叉的概率不较大，会导致树的效果不理想。

法二：也是我最后采用的方法，即每次选取一个最佳plane（axis-assigned），将颗粒跟配到两个不同的set中。然后递归下去。在plane的选取上，试了三种策略spatial median， mean-variance，sah。树的节点结构：

class AABBNode : public AllocObject
{
	friend class AABBTree;
public:
	AABBNode();
	~AABBNode();
	
	bool isLeaf() const { return m_nodeType == LEAF;};

private:
	SplittingAxis	m_nodeType;
	int		m_splitVlaue;	// split plane 
	// 24bytes
	AABB		m_boundingBox;
	// 8bytes
	AABBNode*	m_left;		// left child
	AABBNode*	m_right;	// right child
	// 4bytes
	int		m_key;		// not used now, for future
	primitiveList	m_primitives;	// not used
};

spatial median：基于空间中值的拆分，以当前空间的中心作为下次split的基准。

mean variance：基于均值的拆分，以方差为基准。（参考bullet开源物理引擎）

sah： surface area heuristics， 基于表面积贪心算法。

经过测试sah的效果最佳,在等同的深度下，生成的树最优，节点数最少。

spatial median：

mean variance：

sah：

sah的结果最优，不过其建立过程较之前两种比较耗时。经过部分优化（最佳值区间估计），将每次split选取最佳顶点的计算次数限制在了常数级上，速度基本可以接受了。

sah策略不同深度的测试结果：

 

以上只是显示叶节点，下为包含所有节点：

最近在看opencl， 打算看看bvh怎样并行生成。

HG repository: https://bitbucket.org/AdamWu/veritasengine/overview