00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023 #ifndef LUX_UNSAFEKDTREEACCEL_H
00024 #define LUX_UNSAFEKDTREEACCEL_H
00025
00026
00027 #include "lux.h"
00028 #include "primitive.h"
00029 #include "memory.h"
00030
00031 namespace lux {
00032
00033
00034
00035 struct MailboxPrim {
00036 MailboxPrim(boost::shared_ptr<Primitive> p) {
00037 primitive = p;
00038 lastMailboxId = -1;
00039 }
00040 boost::shared_ptr<Primitive> primitive;
00041 int lastMailboxId;
00042 };
00043
00044 struct UnsafeKdAccelNode {
00045
00046 void initLeaf(int *primNums, int np,
00047 MailboxPrim *mailboxPrims, MemoryArena &arena) {
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057 nPrims = np << 2;
00058 flags |= 3;
00059
00060 if (np == 0)
00061 onePrimitive = NULL;
00062 else if (np == 1)
00063 onePrimitive = &mailboxPrims[primNums[0]];
00064 else {
00065 primitives = (MailboxPrim **)arena.Alloc(np *
00066 sizeof(MailboxPrim *));
00067 for (int i = 0; i < np; ++i)
00068 primitives[i] = &mailboxPrims[primNums[i]];
00069 }
00070 }
00071 void initInterior(int axis, float s) {
00072
00073
00074 split = s;
00075 flags &= ~3;
00076 flags |= axis;
00077 }
00078 float SplitPos() const { return split; }
00079 int nPrimitives() const { return nPrims >> 2; }
00080 int SplitAxis() const { return flags & 3; }
00081 bool IsLeaf() const { return (flags & 3) == 3; }
00082
00083
00084
00085 u_int flags;
00086 union {
00087
00088 float split;
00089 u_int nPrims;
00090 };
00091 union {
00092 u_int aboveChild;
00093 MailboxPrim *onePrimitive;
00094 MailboxPrim **primitives;
00095 };
00096 };
00097
00098 struct UnsafeBoundEdge {
00099
00100 UnsafeBoundEdge() { }
00101 UnsafeBoundEdge(float tt, int pn, bool starting) {
00102 t = tt;
00103 primNum = pn;
00104 type = starting ? START : END;
00105 }
00106 bool operator<(const UnsafeBoundEdge &e) const {
00107 if (t == e.t)
00108 return (int)type < (int)e.type;
00109 else return t < e.t;
00110 }
00111 float t;
00112 int primNum;
00113 enum { START, END } type;
00114 };
00115
00116
00117 struct UnsafeKdAccelNode;
00118 class UnsafeKdTreeAccel : public Aggregate {
00119 public:
00120
00121 UnsafeKdTreeAccel(const vector<boost::shared_ptr<Primitive> > &p,
00122 int icost, int scost,
00123 float ebonus, int maxp, int maxDepth);
00124 virtual BBox WorldBound() const { return bounds; }
00125 virtual bool CanIntersect() const { return true; }
00126 virtual ~UnsafeKdTreeAccel();
00127 virtual bool Intersect(const Ray &ray, Intersection *isect) const;
00128 virtual bool IntersectP(const Ray &ray) const;
00129
00130 virtual void GetPrimitives(vector<boost::shared_ptr<Primitive> > &prims);
00131
00132 static Aggregate *CreateAccelerator(const vector<boost::shared_ptr<Primitive> > &prims, const ParamSet &ps);
00133
00134 private:
00135 void buildTree(int nodeNum, const BBox &bounds,
00136 const vector<BBox> &primBounds,
00137 int *primNums, int nprims, int depth,
00138 UnsafeBoundEdge *edges[3],
00139 int *prims0, int *prims1, int badRefines = 0);
00140
00141 BBox bounds;
00142 int isectCost, traversalCost, maxPrims;
00143 float emptyBonus;
00144 u_int nMailboxes;
00145 MailboxPrim *mailboxPrims;
00146 mutable int curMailboxId;
00147 UnsafeKdAccelNode *nodes;
00148 int nAllocedNodes, nextFreeNode;
00149
00150 MemoryArena arena;
00151 };
00152
00153 struct KdToDo {
00154 const UnsafeKdAccelNode *node;
00155 float tmin, tmax;
00156 };
00157
00158 }
00159
00160 #endif
00161