HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
TS_Octree.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: Octree (C++)
7  *
8  * COMMENTS:
9  *
10  */
11 
12 
13 #ifndef __TS_Octree_H__
14 #define __TS_Octree_H__
15 
16 #include "TS_API.h"
17 #include <UT/UT_Array.h>
18 #include <UT/UT_BoundingBox.h>
19 #include "TS_Expression.h"
20 #include "TS_Primitive.h"
21 
22 #define TS_OCTREE_INITIALIZED 1 // Normal octree intersect
23 #define TS_OCTREE_DOFAST 2 // For small octrees (1 deep)
24 
25 //
26 // Here's the class for a voxel. Each voxel contains a list of primitives
27 // as well as a bounding box and a split direction. Each voxel can
28 // be split into two children (creating a binary tree).
29 //
31 {
32 public:
34  ~TS_OctreeVoxel();
35 
36  /// Compute memory usage
37  int64 getMemoryUsage(bool inclusive) const;
38 
39  TS_OctreeVoxel *myKids[2]; // Left and right
40  TS_ExpressionList myList; // List of objects in this voxel
41  unsigned myAxis; // My split direction (axis)
42  float myAvg; // The split distance
43  UT_BoundingBox myBBox; // Bounding box
44 
45  float xmin() const { return myBBox(0, 0); }
46  float xmax() const { return myBBox(0, 1); }
47  float ymin() const { return myBBox(1, 0); }
48  float ymax() const { return myBBox(1, 1); }
49  float zmin() const { return myBBox(2, 0); }
50  float zmax() const { return myBBox(2, 1); }
51  TS_OctreeVoxel *left() { return myKids[0]; }
52  TS_OctreeVoxel *right() { return myKids[1]; }
53 
54  void addThing(TS_MetaPrimitive *object);
55 
56  void subdivide(const TS_ExpressionList &nodes,
57  unsigned maxEntries, unsigned level);
58 private:
59  void bestSplit(unsigned maxEntries,
60  const TS_ExpressionList &nodes);
61  void getKids(TS_ExpressionList &kids,
62  const TS_ExpressionList &nodes,
63  int left = 1);
64 };
65 
66 //
67 // This class is used in octree traversal. This maintains a stack
68 // of where we are in the octree...
69 //
71 {
72 public:
74  float myMin, myMax;
75 
77  {
78  myVoxel = d.myVoxel;
79  myMin = d.myMin;
80  myMax = d.myMax;
81  return *this;
82  }
83  unsigned operator==(const TS_OctreeStack &) const
84  {
85  return 0;
86  }
87 };
88 
89 //
90 // Here is the real octree class.
91 //
93 {
94 public:
95  TS_Octree();
96  TS_Octree(const TS_MetaExpression *e);
97  ~TS_Octree();
98 
99  void setSweepList(const TS_Ray &ray, TS_SweepList &sweep,
100  fpreal tmin=0, fpreal tmax=1e20);
101  TS_OctreeVoxel *findVoxel(const UT_Vector3 &P) const;
102 
103  /// Compute memory usage
104  int64 getMemoryUsage(bool inclusive) const;
105 
106 private:
107  int buildMe(); // Other people may have to do things
108 
109 private:
110  TS_OctreeVoxel *myHead; // My BSP tree
111  unsigned myMaxLevel;
112 
113  UT_Array<TS_OctreeStack> myStack; // used for intersect
114  const TS_MetaExpression *myOwner;
115  unsigned myStackPtr;
116 };
117 
118 #endif
#define TS_API
Definition: TS_API.h:10
unsigned myAxis
Definition: TS_Octree.h:41
TS_ExpressionList myList
Definition: TS_Octree.h:40
float xmin() const
Definition: TS_Octree.h:45
float xmax() const
Definition: TS_Octree.h:46
TS_OctreeVoxel * myVoxel
Definition: TS_Octree.h:73
GLint left
Definition: glcorearb.h:2004
GLint level
Definition: glcorearb.h:107
float ymax() const
Definition: TS_Octree.h:48
TS_OctreeVoxel * left()
Definition: TS_Octree.h:51
long long int64
Definition: SYS_Types.h:106
Definition: TS_Ray.h:21
TS_OctreeVoxel * right()
Definition: TS_Octree.h:52
float ymin() const
Definition: TS_Octree.h:47
double fpreal
Definition: SYS_Types.h:269
float zmax() const
Definition: TS_Octree.h:50
UT_BoundingBox myBBox
Definition: TS_Octree.h:43
unsigned operator==(const TS_OctreeStack &) const
Definition: TS_Octree.h:83
float zmin() const
Definition: TS_Octree.h:49
TS_OctreeStack & operator=(const TS_OctreeStack &d)
Definition: TS_Octree.h:76