00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025 #include "lux.h"
00026 #include "primitive.h"
00027
00028 #include <xmmintrin.h>
00029 #include <boost/cstdint.hpp>
00030 using boost::int32_t;
00031
00032 namespace lux
00033 {
00034
00035
00036
00045 #define NB_BINS 8
00046
00050 class QBVHNode {
00051 public:
00052
00053
00054
00055
00056
00057
00058
00059 static const int32_t emptyLeafNode = 0xffffffff;
00060
00065 __m128 bboxes[2][3];
00066
00074 int32_t children[4];
00075
00079 int32_t axisMain, axisSubLeft, axisSubRight;
00080
00082 int32_t parentNodeIndex;
00083
00088 inline QBVHNode() : axisMain(0), axisSubLeft(0), axisSubRight(0),
00089 parentNodeIndex(-1) {
00090 for (int i = 0; i < 3; ++i) {
00091 bboxes[0][i] = _mm_set1_ps(INFINITY);
00092 bboxes[1][i] = _mm_set1_ps(-INFINITY);
00093 }
00094
00095
00096 for (int i = 0; i < 4; ++i)
00097 children[i] = emptyLeafNode;
00098 }
00099
00105 inline bool ChildIsLeaf(int i) const {
00106 return (children[i] < 0);
00107 }
00108
00113 inline static bool IsLeaf(int32_t index) {
00114 return (index < 0);
00115 }
00116
00121 inline bool LeafIsEmpty(int i) const {
00122 return (children[i] == emptyLeafNode);
00123 }
00124
00129 inline static bool IsEmpty(int32_t index) {
00130 return (index == emptyLeafNode);
00131 }
00132
00139 inline u_int NbQuadsInLeaf(int i) const {
00140 return (((children[i] >> 27) & 15)) + 1;
00141 }
00142
00147 inline static u_int NbQuadPrimitives(int32_t index) {
00148 return ((index >> 27) & 15) + 1;
00149 }
00150
00157 inline u_int NbPrimitivesInLeaf(int i) const {
00158 return NbQuadsInLeaf(i) * 4;
00159 }
00160
00167 inline u_int FirstQuadIndexForLeaf(int i) const {
00168 return children[i] & 0x07ffffff;
00169 }
00170
00175 inline static u_int FirstQuadIndex(int32_t index) {
00176 return index & 0x07ffffff;
00177 }
00178
00185 inline void InitializeLeaf(int i, u_int nbQuads, u_int firstQuadIndex) {
00186
00187 if (nbQuads == 0) {
00188 children[i] = emptyLeafNode;
00189 } else {
00190
00191 children[i] = 0x80000000;
00192
00193 children[i] |= ((nbQuads - 1) & 0xff) << 27;
00194
00195 children[i] |= firstQuadIndex & 0x07ffffff;
00196 }
00197 }
00198
00204 inline void SetBBox(int i, const BBox &bbox) {
00205 for (int axis = 0; axis < 3; ++axis) {
00206 ((float *)&(bboxes[0][axis]))[i] = bbox.pMin[axis];
00207 ((float *)&(bboxes[1][axis]))[i] = bbox.pMax[axis];
00208 }
00209 }
00210
00211
00225 int32_t BBoxIntersect(__m128 sseOrig[3], __m128 sseInvDir[3],
00226 const __m128 &sseTMin, const __m128 &sseTMax,
00227 const int sign[3]) const;
00228
00229
00230 };
00231
00232
00233
00234 class QBVHAccel : public Aggregate {
00235 public:
00243 QBVHAccel(const vector<boost::shared_ptr<Primitive> > &p, int mp, float fst, int sf);
00244
00248 virtual ~QBVHAccel();
00249
00254 virtual BBox WorldBound() const;
00255
00263 virtual bool Intersect(const Ray &ray, Intersection *isect) const;
00264
00270 virtual bool IntersectP(const Ray &ray) const;
00271
00276 virtual void GetPrimitives(vector<boost::shared_ptr<Primitive> > &prims);
00277
00283 static Aggregate *CreateAccelerator(const vector<boost::shared_ptr<Primitive> > &prims, const ParamSet &ps);
00284
00285 private:
00301 void BuildTree(u_int start, u_int end, u_int *primsIndexes, BBox *primsBboxes,
00302 Point *primsCentroids, const BBox &nodeBbox,
00303 const BBox ¢roidsBbox, int32_t parentIndex, int32_t childIndex,
00304 int depth);
00305
00314 void CreateTempLeaf(int32_t parentIndex, int32_t childIndex, u_int start, u_int end,
00315 const BBox &nodeBbox);
00316
00323 inline int32_t CreateIntermediateNode(int32_t parentIndex, int32_t childIndex,
00324 const BBox &nodeBbox) {
00325 int32_t index = nNodes++;
00326 if (nNodes >= maxNodes) {
00327 QBVHNode *newNodes = AllocAligned<QBVHNode>(2 * maxNodes);
00328 memcpy(newNodes, nodes, sizeof(QBVHNode) * maxNodes);
00329 for (u_int i = 0; i < maxNodes; ++i)
00330 newNodes[maxNodes + i] = QBVHNode();
00331 FreeAligned(nodes);
00332 nodes = newNodes;
00333 maxNodes *= 2;
00334 }
00335 nodes[index].parentNodeIndex = parentIndex;
00336 if (parentIndex >= 0) {
00337 nodes[parentIndex].children[childIndex] = index;
00338 nodes[parentIndex].SetBBox(childIndex, nodeBbox);
00339 }
00340 return index;
00341 }
00342
00350 void PreSwizzle(int32_t nodeIndex, u_int *primsIndexes,
00351 const vector<boost::shared_ptr<Primitive> > &vPrims);
00352
00362 void CreateSwizzledLeaf(int32_t parentIndex, int32_t childIndex,
00363 u_int *primsIndexes, const vector<boost::shared_ptr<Primitive> > &vPrims);
00364
00368 u_int nQuads;
00369
00377 boost::shared_ptr<Primitive> *prims;
00378
00382 u_int nPrims;
00383
00387 QBVHNode *nodes;
00388
00392 u_int nNodes, maxNodes;
00393
00397 BBox worldBound;
00398
00403 u_int fullSweepThreshold;
00404
00408 u_int skipFactor;
00409
00413 u_int maxPrimsPerLeaf;
00414
00415
00416
00417
00418
00419
00420
00421
00422
00423
00424
00425
00426
00427
00428
00429
00430
00431
00432 static const boost::int16_t pathTable[128];
00433 };
00434
00435 }