Subversion Repositories gelsvn

Rev

Rev 595 | Details | Compare with Previous | Last modification | View Log | RSS feed

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