Tuesday merger of bf-blender into orange branch.
[blender-staging.git] / extern / bullet / Bullet / CollisionShapes / OptimizedBvh.h
1 /*
2  * Copyright (c) 2006 Erwin Coumans http://continuousphysics.com/Bullet/
3  *
4  * Permission to use, copy, modify, distribute and sell this software
5  * and its documentation for any purpose is hereby granted without fee,
6  * provided that the above copyright notice appear in all copies.
7  * Erwin Coumans makes no representations about the suitability 
8  * of this software for any purpose.  
9  * It is provided "as is" without express or implied warranty.
10 */
11
12 #ifndef OPTIMIZED_BVH_H
13 #define OPTIMIZED_BVH_H
14 #include "SimdVector3.h"
15 #include <vector>
16
17 class StridingMeshInterface;
18
19 /// OptimizedBvhNode contains both internal and leaf node information.
20 /// It hasn't been optimized yet for storage. Some obvious optimizations are:
21 /// Removal of the pointers (can already be done, they are not used for traversal)
22 /// and storing aabbmin/max as quantized integers.
23 /// 'subpart' doesn't need an integer either. It allows to re-use graphics triangle
24 /// meshes stored in a non-uniform way (like batches/subparts of triangle-fans
25 struct OptimizedBvhNode
26 {
27
28         SimdVector3     m_aabbMin;
29         SimdVector3     m_aabbMax;
30
31 //these 2 pointers are obsolete, the stackless traversal just uses the escape index
32         OptimizedBvhNode*       m_leftChild;
33         OptimizedBvhNode*       m_rightChild;
34
35         int     m_escapeIndex;
36
37         //for child nodes
38         int     m_subPart;
39         int     m_triangleIndex;
40
41 };
42
43 class NodeOverlapCallback
44 {
45 public:
46         virtual void ProcessNode(const OptimizedBvhNode* node) = 0;
47 };
48
49 typedef std::vector<OptimizedBvhNode>   NodeArray;
50
51
52 ///OptimizedBvh store an AABB tree that can be quickly traversed on CPU (and SPU,GPU in future)
53 class OptimizedBvh
54 {
55         OptimizedBvhNode*       m_rootNode1;
56         
57         OptimizedBvhNode*       m_contiguousNodes;
58         int                                     m_curNodeIndex;
59
60         int                                     m_numNodes;
61
62         NodeArray                       m_leafNodes;
63
64 public:
65         OptimizedBvh() :m_rootNode1(0), m_numNodes(0) { }
66         
67         void    Build(StridingMeshInterface* triangles);
68
69         OptimizedBvhNode*       BuildTree       (NodeArray&     leafNodes,int startIndex,int endIndex);
70
71         int     CalcSplittingAxis(NodeArray&    leafNodes,int startIndex,int endIndex);
72
73         int     SortAndCalcSplittingIndex(NodeArray&    leafNodes,int startIndex,int endIndex,int splitAxis);
74         
75         void    WalkTree(OptimizedBvhNode* rootNode,NodeOverlapCallback* nodeCallback,const SimdVector3& aabbMin,const SimdVector3& aabbMax) const;
76         
77         void    WalkStacklessTree(OptimizedBvhNode* rootNode,NodeOverlapCallback* nodeCallback,const SimdVector3& aabbMin,const SimdVector3& aabbMax) const;
78         
79
80         //OptimizedBvhNode*     GetRootNode() { return m_rootNode1;}
81
82         int                                     GetNumNodes() { return m_numNodes;}
83
84         void    ReportAabbOverlappingNodex(NodeOverlapCallback* nodeCallback,const SimdVector3& aabbMin,const SimdVector3& aabbMax) const;
85
86         void    ReportSphereOverlappingNodex(NodeOverlapCallback* nodeCallback,const SimdVector3& aabbMin,const SimdVector3& aabbMax) const;
87
88
89 };
90
91
92 #endif //OPTIMIZED_BVH_H