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


/* ----------------------------------------------------------------------- *
 * This file is part of GEL, http://www.imm.dtu.dk/GEL
 * Copyright (C) the authors and DTU Informatics
 * For license and list of authors, see ../../doc/intro.pdf
 * ----------------------------------------------------------------------- */
 
/**
 * @file BSPTree.h
 * @brief Binary space partitioning tree.
 */
 
#ifndef __GEOMETRY_BSPTREE_H__
#define __GEOMETRY_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;
    size_t 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;
  };
 
    /** BSPTree class. Mostly used to accelerate ray casting. 
     */
  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 443	Rev 595
-		1	`/* ----------------------------------------------------------------------- *`
-		2	`* This file is part of GEL, http://www.imm.dtu.dk/GEL`
-		3	`* Copyright (C) the authors and DTU Informatics`
-		4	`* For license and list of authors, see ../../doc/intro.pdf`
-		5	`* ----------------------------------------------------------------------- */`
-		6
-		7	`/**`
-		8	`* @file BSPTree.h`
-		9	`* @brief Binary space partitioning tree.`
-		10	`*/`
-		11
1	`#ifndef __GEOMETRY_BSPTREE_H__`	12	`#ifndef __GEOMETRY_BSPTREE_H__`
2	`#define __GEOMETRY_BSPTREE_H__`	13	`#define __GEOMETRY_BSPTREE_H__`
3		14
4	`#include <vector>`	15	`#include <vector>`
5		16
6	`#include "CGLA/Mat4x4f.h"`	17	`#include "CGLA/Mat4x4f.h"`
7	`#include "Geometry/TriMesh.h"`	18	`#include "Geometry/TriMesh.h"`
8		19
9	`#include "BBox.h"`	20	`#include "BBox.h"`
10		21
11	`namespace Geometry`	22	`namespace Geometry`
12	`{`	23	`{`
13	`struct BSPNode;`	24	`struct BSPNode;`
14		25
15	`// Initialization structure`	26	`// Initialization structure`
16	`struct BSPNode`	27	`struct BSPNode`
17	`{`	28	`{`
18	`unsigned char axis_leaf; // 00 = axis 0, 01 = axis 1, 10 = axis 2, 11 = leaf`	29	`unsigned char axis_leaf; // 00 = axis 0, 01 = axis 1, 10 = axis 2, 11 = leaf`
19	`double plane;`	30	`double plane;`
20	`BSPNode left, right;`	31	`BSPNode left, right;`
21	`int id;`	32	`size_t id;`
22	`int count;`	33	`int count;`
23	`unsigned int ref;`	34	`unsigned int ref;`
24	`};`	35	`};`
25		36
26	`// Faster structure`	37	`// Faster structure`
27	`struct BSPLeaf {`	38	`struct BSPLeaf {`
28	`// bits 0..30 : offset to first son`	39	`// bits 0..30 : offset to first son`
29	`// bit 31 (sign) flag whether node is a leaf`	40	`// bit 31 (sign) flag whether node is a leaf`
30	`unsigned int flagAndOffset;`	41	`unsigned int flagAndOffset;`
31	`unsigned int count;`	42	`unsigned int count;`
32	`};`	43	`};`
33		44
34	`struct BSPInner {`	45	`struct BSPInner {`
35	`unsigned int flagAndOffset;`	46	`unsigned int flagAndOffset;`
36	`// bits 0..1 : splitting dimension`	47	`// bits 0..1 : splitting dimension`
37	`// bits 2..30: offset bits`	48	`// bits 2..30: offset bits`
38	`// bit 31 (sign) flag whether node is a leaf`	49	`// bit 31 (sign) flag whether node is a leaf`
39	`float splitCoordinate;`	50	`float splitCoordinate;`
40	`};`	51	`};`
41		52
42	`union FastBSPNode`	53	`union FastBSPNode`
43	`{`	54	`{`
44	`BSPLeaf leaf;`	55	`BSPLeaf leaf;`
45	`BSPInner inner;`	56	`BSPInner inner;`
46	`};`	57	`};`
47		58
-		59	`/** BSPTree class. Mostly used to accelerate ray casting.`
-		60	`*/`
48	`class BSPTree`	61	`class BSPTree`
49	`{`	62	`{`
50	`bool b_is_build;`	63	`bool b_is_build;`
51		64
52	`static int node_calls;`	65	`static int node_calls;`
53	`static int tri_calls;`	66	`static int tri_calls;`
54	`BSPNode* root;`	67	`BSPNode* root;`
55	`BBox bbox;`	68	`BBox bbox;`
56	`std::vector<const Geometry::TriMesh*> trimesh;`	69	`std::vector<const Geometry::TriMesh*> trimesh;`
57	`std::vector<CGLA::Mat4x4f> transforms;`	70	`std::vector<CGLA::Mat4x4f> transforms;`
58		71
59	`std::vector<ISectTri> isecttris;`	72	`std::vector<ISectTri> isecttris;`
60	`std::vector<TriAccel> triaccel;`	73	`std::vector<TriAccel> triaccel;`
61	`std::vector<ISectTri*> all_objects;`	74	`std::vector<ISectTri*> all_objects;`
62	`std::vector<TriAccel*> all_triaccel;`	75	`std::vector<TriAccel*> all_triaccel;`
63	`std::vector<FastBSPNode> fast_tree;`	76	`std::vector<FastBSPNode> fast_tree;`
64		77
65	`unsigned int max_objects;`	78	`unsigned int max_objects;`
66	`unsigned int max_level;`	79	`unsigned int max_level;`
67		80
68	`public:`	81	`public:`
69	`BSPTree();`	82	`BSPTree();`
70	`~BSPTree();`	83	`~BSPTree();`
71		84
72	`void init(std::vector<const Geometry::TriMesh*>& trimesh,`	85	`void init(std::vector<const Geometry::TriMesh*>& trimesh,`
73	`int max_objects, int max_level);`	86	`int max_objects, int max_level);`
74	`void init(std::vector<const Geometry::TriMesh*>& _trimesh,`	87	`void init(std::vector<const Geometry::TriMesh*>& _trimesh,`
75	`std::vector<CGLA::Mat4x4f>& _transforms,`	88	`std::vector<CGLA::Mat4x4f>& _transforms,`
76	`int _max_objects, int _max_level);`	89	`int _max_objects, int _max_level);`
77	`void init(const Geometry::TriMesh* mesh, CGLA::Mat4x4f transform,`	90	`void init(const Geometry::TriMesh* mesh, CGLA::Mat4x4f transform,`
78	`std::vector<int> &trilist,`	91	`std::vector<int> &trilist,`
79	`int _max_objects, int _max_level);`	92	`int _max_objects, int _max_level);`
80		93
81	`void build();`	94	`void build();`
82	`bool is_build();`	95	`bool is_build();`
83	`void clear();`	96	`void clear();`
84		97
85	`bool intersect(Ray &ray) const;`	98	`bool intersect(Ray &ray) const;`
86		99
87	`private:`	100	`private:`
88	`void delete_node(BSPNode *node);`	101	`void delete_node(BSPNode *node);`
89	`void subdivide_node(BSPNode &node, BBox &bbox,`	102	`void subdivide_node(BSPNode &node, BBox &bbox,`
90	`unsigned int level,`	103	`unsigned int level,`
91	`std::vector<ISectTri*>& objects,`	104	`std::vector<ISectTri*>& objects,`
92	`std::vector<TriAccel*>& tri_objects);`	105	`std::vector<TriAccel*>& tri_objects);`
93	`void init();`	106	`void init();`
94		107
95	`bool intersect_node(Ray &ray, const BSPNode &node,`	108	`bool intersect_node(Ray &ray, const BSPNode &node,`
96	`double t_min, double t_max) const;`	109	`double t_min, double t_max) const;`
97	`void print(BSPNode *node, int depth);`	110	`void print(BSPNode *node, int depth);`
98	`int size(BSPNode *node);`	111	`int size(BSPNode *node);`
99	`int size();`	112	`int size();`
100		113
101	`void make_fast_tree(BSPNode *node);`	114	`void make_fast_tree(BSPNode *node);`
102	`void push_fast_bsp_node(BSPNode *node, int id);`	115	`void push_fast_bsp_node(BSPNode *node, int id);`
103	`void intersect_fast_node(Ray &ray,`	116	`void intersect_fast_node(Ray &ray,`
104	`const FastBSPNode *node,`	117	`const FastBSPNode *node,`
105	`double t_min, double t_max) const;`	118	`double t_min, double t_max) const;`
106	`bool intersect(Ray &ray, const ISectTri &isecttri, double t_max) const;`	119	`bool intersect(Ray &ray, const ISectTri &isecttri, double t_max) const;`
107	`};`	120	`};`
108	`}`	121	`}`
109	`#endif`	122	`#endif`
110		123
111		124

Subversion Repositories gelsvn

(root)/trunk/src/Geometry/BSPTree.h/ – Rev 443 → 595