WebSVN – gelsvn – Diff – /trunk/src/Geometry/BSPTree.h


#ifndef __BSPTREE_H__
#define __BSPTREE_H__
 
#include <vector>
 
#include "CGLA/Mat4x4f.h"
#include "Geometry/TriMesh.h"
 
#include "BBox.h"
 
namespace Geometry 
{
  struct BSPNode;
 
  // Initialization structure
  struct BSPNode 
  {
    unsigned char axis_leaf; // 00 = axis 0, 01 = axis 1, 10 = axis 2, 11 = leaf
    double plane;
    BSPNode *left, *right;
    int id;
    int count;
    unsigned int ref;
  };
 
  // Faster structure
  struct BSPLeaf {
    // bits 0..30 : offset to first son
    // bit 31 (sign) flag whether node is a leaf
    unsigned int flagAndOffset;
    unsigned int count;
  };
 
  struct BSPInner {
    unsigned int flagAndOffset;
    // bits 0..1 : splitting dimension
    // bits 2..30: offset bits
    // bit 31 (sign) flag whether node is a leaf
    float splitCoordinate;
  };
 
  union FastBSPNode
  {
    BSPLeaf leaf;
    BSPInner inner;
  };
 
  class BSPTree 
  {
    bool b_is_build;
 
	  static int node_calls;
    static int tri_calls;
    BSPNode* root;
    BBox bbox;
    std::vector<const Geometry::TriMesh*> trimesh;
    std::vector<CGLA::Mat4x4f> transforms;
    
    std::vector<ISectTri> isecttris;
    std::vector<TriAccel> triaccel;
    std::vector<ISectTri*> all_objects;
    std::vector<TriAccel*> all_triaccel;
    std::vector<FastBSPNode> fast_tree;
    
    unsigned int max_objects;
    unsigned int max_level;
	
  public:
    BSPTree();
    ~BSPTree();
 
    void init(std::vector<const Geometry::TriMesh*>& trimesh, 
              int max_objects, int max_level);
    void init(std::vector<const Geometry::TriMesh*>& _trimesh, 
              std::vector<CGLA::Mat4x4f>& _transforms, 
              int _max_objects, int _max_level);
    void init(const Geometry::TriMesh* mesh, CGLA::Mat4x4f transform, 
              std::vector<int> &trilist, 
              int _max_objects, int _max_level);
 
    void build();
    bool is_build();
    void clear();
 
    bool intersect(Ray &ray) const;
	
  private:
    void delete_node(BSPNode *node);
 
    void subdivide_node(BSPNode &node, BBox &bbox, 
                        unsigned int level, 
                        std::vector<ISectTri*>& objects, 
                        std::vector<TriAccel*>& tri_objects);
    void init();
 
    bool intersect_node(Ray &ray, const BSPNode &node, 
                        double t_min, double t_max) const;
    void print(BSPNode *node, int depth);
    int size(BSPNode *node);
    int size();
 
    void make_fast_tree(BSPNode *node);
    void push_fast_bsp_node(BSPNode *node, int id);
    void intersect_fast_node(Ray &ray, 
                             const FastBSPNode *node, 
                             double t_min, double t_max) const;
    bool intersect(Ray &ray, const ISectTri &isecttri, double t_max) const;
  };
}
#endif
 
 

Rev 349	Rev 428
1	`#ifndef __BSPTREE_H__`	1	`#ifndef __BSPTREE_H__`
2	`#define __BSPTREE_H__`	2	`#define __BSPTREE_H__`
3		3
4	`#include <vector>`	4	`#include <vector>`
5		5
6	`#include "CGLA/Mat4x4f.h"`	6	`#include "CGLA/Mat4x4f.h"`
7	`#include "Geometry/TriMesh.h"`	7	`#include "Geometry/TriMesh.h"`
8		8
9	`#include "BBox.h"`	9	`#include "BBox.h"`
10		10
11	`namespace Geometry`	11	`namespace Geometry`
12	`{`	12	`{`
13	`struct BSPNode;`	13	`struct BSPNode;`
14		14
15	`// Initialization structure`	15	`// Initialization structure`
16	`struct BSPNode`	16	`struct BSPNode`
17	`{`	17	`{`
18	`unsigned char axis_leaf; // 00 = axis 0, 01 = axis 1, 10 = axis 2, 11 = leaf`	18	`unsigned char axis_leaf; // 00 = axis 0, 01 = axis 1, 10 = axis 2, 11 = leaf`
19	`double plane;`	19	`double plane;`
20	`BSPNode left, right;`	20	`BSPNode left, right;`
21	`int id;`	21	`int id;`
22	`int count;`	22	`int count;`
23	`unsigned int ref;`	23	`unsigned int ref;`
24	`};`	24	`};`
25		25
26	`// Faster structure`	26	`// Faster structure`
27	`struct BSPLeaf {`	27	`struct BSPLeaf {`
28	`// bits 0..30 : offset to first son`	28	`// bits 0..30 : offset to first son`
29	`// bit 31 (sign) flag whether node is a leaf`	29	`// bit 31 (sign) flag whether node is a leaf`
30	`unsigned int flagAndOffset;`	30	`unsigned int flagAndOffset;`
31	`unsigned int count;`	31	`unsigned int count;`
32	`};`	32	`};`
33		33
34	`struct BSPInner {`	34	`struct BSPInner {`
35	`unsigned int flagAndOffset;`	35	`unsigned int flagAndOffset;`
36	`// bits 0..1 : splitting dimension`	36	`// bits 0..1 : splitting dimension`
37	`// bits 2..30: offset bits`	37	`// bits 2..30: offset bits`
38	`// bit 31 (sign) flag whether node is a leaf`	38	`// bit 31 (sign) flag whether node is a leaf`
39	`float splitCoordinate;`	39	`float splitCoordinate;`
40	`};`	40	`};`
41		41
42	`union FastBSPNode`	42	`union FastBSPNode`
43	`{`	43	`{`
44	`BSPLeaf leaf;`	44	`BSPLeaf leaf;`
45	`BSPInner inner;`	45	`BSPInner inner;`
46	`};`	46	`};`
47		47
48	`class BSPTree`	48	`class BSPTree`
49	`{`	49	`{`
50	`bool b_is_build;`	50	`bool b_is_build;`
51		51
52	`static int node_calls;`	52	`static int node_calls;`
53	`static int tri_calls;`	53	`static int tri_calls;`
54	`BSPNode* root;`	54	`BSPNode* root;`
55	`BBox bbox;`	55	`BBox bbox;`
56	`std::vector<const Geometry::TriMesh*> trimesh;`	56	`std::vector<const Geometry::TriMesh*> trimesh;`
57	`std::vector<CGLA::Mat4x4f> transforms;`	57	`std::vector<CGLA::Mat4x4f> transforms;`
58		58
59	`std::vector<ISectTri> isecttris;`	59	`std::vector<ISectTri> isecttris;`
60	`std::vector<TriAccel> triaccel;`	60	`std::vector<TriAccel> triaccel;`
61	`std::vector<ISectTri*> all_objects;`	61	`std::vector<ISectTri*> all_objects;`
62	`std::vector<TriAccel*> all_triaccel;`	62	`std::vector<TriAccel*> all_triaccel;`
63	`std::vector<FastBSPNode> fast_tree;`	63	`std::vector<FastBSPNode> fast_tree;`
64		64
65	`unsigned int max_objects;`	65	`unsigned int max_objects;`
66	`unsigned int max_level;`	66	`unsigned int max_level;`
67		67
68	`public:`	68	`public:`
69	`BSPTree();`	69	`BSPTree();`
70	`~BSPTree();`	70	`~BSPTree();`
71		71
72	`void init(std::vector<const Geometry::TriMesh*>& trimesh,`	72	`void init(std::vector<const Geometry::TriMesh*>& trimesh,`
73	`int max_objects, int max_level);`	73	`int max_objects, int max_level);`
74	`void init(std::vector<const Geometry::TriMesh*>& _trimesh,`	74	`void init(std::vector<const Geometry::TriMesh*>& _trimesh,`
75	`std::vector<CGLA::Mat4x4f>& _transforms,`	75	`std::vector<CGLA::Mat4x4f>& _transforms,`
76	`int _max_objects, int _max_level);`	76	`int _max_objects, int _max_level);`
77	`void init(const Geometry::TriMesh* mesh, CGLA::Mat4x4f transform,`	77	`void init(const Geometry::TriMesh* mesh, CGLA::Mat4x4f transform,`
78	`std::vector<int> &trilist,`	78	`std::vector<int> &trilist,`
79	`int _max_objects, int _max_level);`	79	`int _max_objects, int _max_level);`
80		80
81	`void build();`	81	`void build();`
82	`bool is_build();`	82	`bool is_build();`
83	`void clear();`	83	`void clear();`
84		84
85	`bool intersect(Ray &ray) const;`	85	`bool intersect(Ray &ray) const;`
86		86
87	`private:`	87	`private:`
88	`void delete_node(BSPNode *node);`	88	`void delete_node(BSPNode *node);`
89	`// bool intersect2(BRender::Ray &ray, const TriAccel &acc, double t_max) const;`	-
90	`void subdivide_node(BSPNode &node, BBox &bbox,`	89	`void subdivide_node(BSPNode &node, BBox &bbox,`
91	`unsigned int level,`	90	`unsigned int level,`
92	`std::vector<ISectTri*>& objects,`	91	`std::vector<ISectTri*>& objects,`
93	`std::vector<TriAccel*>& tri_objects);`	92	`std::vector<TriAccel*>& tri_objects);`
94	`void init();`	93	`void init();`
95		94
96	`bool intersect_node(Ray &ray, const BSPNode &node,`	95	`bool intersect_node(Ray &ray, const BSPNode &node,`
97	`double t_min, double t_max) const;`	96	`double t_min, double t_max) const;`
98	`void print(BSPNode *node, int depth);`	97	`void print(BSPNode *node, int depth);`
99	`int size(BSPNode *node);`	98	`int size(BSPNode *node);`
100	`int size();`	99	`int size();`
101		100
102	`void make_fast_tree(BSPNode *node);`	101	`void make_fast_tree(BSPNode *node);`
103	`void push_fast_bsp_node(BSPNode *node, int id);`	102	`void push_fast_bsp_node(BSPNode *node, int id);`
104	`void intersect_fast_node(Ray &ray,`	103	`void intersect_fast_node(Ray &ray,`
105	`const FastBSPNode *node,`	104	`const FastBSPNode *node,`
106	`double t_min, double t_max) const;`	105	`double t_min, double t_max) const;`
107	`bool intersect(Ray &ray, const ISectTri &isecttri, double t_max) const;`	106	`bool intersect(Ray &ray, const ISectTri &isecttri, double t_max) const;`
108	`};`	107	`};`
109	`}`	108	`}`
110	`#endif`	109	`#endif`
111		110
112		111

Subversion Repositories gelsvn

(root)/trunk/src/Geometry/BSPTree.h – Rev 349 → 428