quadTreeTracer.cpp

Public Functions

calcInterceptNone(F32 , F32 , F32 )

calcInterceptV(F32 vStart, F32 invDeltaV, F32 intercept)

  1
  2//-----------------------------------------------------------------------------
  3// Copyright (c) 2012 GarageGames, LLC
  4//
  5// Permission is hereby granted, free of charge, to any person obtaining a copy
  6// of this software and associated documentation files (the "Software"), to
  7// deal in the Software without restriction, including without limitation the
  8// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
  9// sell copies of the Software, and to permit persons to whom the Software is
 10// furnished to do so, subject to the following conditions:
 11//
 12// The above copyright notice and this permission notice shall be included in
 13// all copies or substantial portions of the Software.
 14//
 15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 18// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 21// IN THE SOFTWARE.
 22//-----------------------------------------------------------------------------
 23
 24#include "util/quadTreeTracer.h"
 25#include "platform/profiler.h"
 26#include "core/frameAllocator.h"
 27
 28static F32 calcInterceptV(F32 vStart, F32 invDeltaV, F32 intercept)
 29{
 30   return (intercept - vStart) * invDeltaV;
 31}
 32
 33static F32 calcInterceptNone(F32, F32, F32)
 34{
 35   return F32_MAX;
 36}
 37
 38static F32 (*calcInterceptX)(F32, F32, F32);
 39static F32 (*calcInterceptY)(F32, F32, F32);
 40
 41bool QuadTreeTracer::castRay(const Point3F &start, const Point3F &end, RayInfo *info)
 42{
 43   PROFILE_START(QuadTreeTracer_castRay);
 44
 45   // Do some precalculations we'll use for the rest of this routine.
 46   // Set up our intercept calculation methods.
 47   F32 invDeltaX;
 48   if(end.x == start.x)
 49   {
 50      calcInterceptX = calcInterceptNone;
 51      invDeltaX = 0;
 52   }
 53   else
 54   {
 55      invDeltaX = 1.f / (end.x - start.x);
 56      calcInterceptX = calcInterceptV;
 57   }
 58
 59   F32 invDeltaY;
 60   if(end.y == start.y)
 61   {
 62      calcInterceptY = calcInterceptNone;
 63      invDeltaY = 0;
 64   }
 65   else
 66   {
 67      invDeltaY = 1.f / (end.y - start.y);
 68      calcInterceptY = calcInterceptV;
 69   }
 70
 71   // Subdivide our space based on the size of the lowest level of the tree...
 72   const F32 invSize   = 1.f / F32(BIT(mTreeDepth-1));
 73
 74   // Grab this off the frame allocator, we don't want to do a proper alloc
 75   // on every ray!
 76   FrameAllocatorMarker stackAlloc;
 77   RayStackNode *stack = (RayStackNode*)stackAlloc.alloc(sizeof(RayStackNode) * (mTreeDepth * 3 + 1));
 78
 79   U32 stackSize = 1;
 80
 81   // Kick off the stack with the root node.
 82   stack[0].startT   = 0;
 83   stack[0].endT     = 1;
 84   stack[0].squarePos.set(0,0);
 85   stack[0].level    = mTreeDepth - 1;
 86
 87   //Con::printf("QuadTreeTracer::castRay(%x)", this);
 88
 89   // Aright, now let's do some raycasting!
 90   while(stackSize--)
 91   {
 92      // Get the current node for easy access...
 93      RayStackNode *sn = stack + stackSize;
 94
 95      const U32 level         = sn->level;
 96      const F32 startT        = sn->startT;
 97      const F32 endT          = sn->endT;
 98      const Point2I squarePos = sn->squarePos;
 99
100      AssertFatal((startT >= 0.f) && (startT <= 1.f),  "QuadTreeTracer::castRay - out of range startT on stack!");
101      AssertFatal((endT >= 0.f) && (endT <= 1.f),     "QuadTreeTracer::castRay - out of range endT   on stack!");
102
103      //Con::printf(" -- node(%d, %d @ %d), sT=%f, eT=%f", squarePos.x, squarePos.y, level, startT, endT);
104
105      // Figure our start and end Z.
106      const F32 startZ = startT * (end.z - start.z) + start.z;
107      const F32 endZ   = endT   * (end.z - start.z) + start.z;
108
109      // Ok, now let's see if we hit the lower bound
110      const F32 squareMin = getSquareMin(level, squarePos);
111
112      if(startZ < squareMin && endZ < squareMin)
113         continue; //Nope, skip out.
114
115      // Hmm, let's check the upper bound.
116      const F32 squareMax = getSquareMax(level, squarePos);
117
118      if(startZ > squareMax && endZ > squareMax)
119         continue; //Nope, skip out.
120
121      // We might be intersecting something... If we've hit
122      // the tree depth let's deal with the leaf intersection.
123      if(level == 0)
124      {
125         //Con::printf(" ++ check node(%d, %d @ %d), sT=%f, eT=%f", squarePos.x, squarePos.y, level, startT, endT);
126
127         if(castLeafRay(squarePos, start, end, startT, endT, info))
128         {
129            PROFILE_END();
130            return true; // We hit, tell 'em so!
131         }
132         continue; // Otherwise, keep looking.
133      }
134      else
135      {
136         // Ok, we have to push our children as we're an inner node.
137
138         // First, figure out some widths...
139         U32 subSqSize  = BIT(level - 1);
140
141         // Now, calculate intercepts so we know how to deal with this
142         // situation... (intercept = position, int = t value for that pos)
143
144         const F32 xIntercept = (squarePos.x + subSqSize) * invSize;
145         F32 xInt = calcInterceptX(start.x, invDeltaX, xIntercept);
146
147         const F32 yIntercept = (squarePos.y + subSqSize) * invSize;
148         F32 yInt = calcInterceptY(start.y, invDeltaY, yIntercept);
149
150         // Our starting position for this subray...
151         const F32 startX = startT * (end.x - start.x) + start.x;
152         const F32 startY = startT * (end.y - start.y) + start.y;
153
154         // Deal with squares that might be "behind" the ray.
155         if(xInt < startT) xInt = F32_MAX;
156         if(yInt < startT) yInt = F32_MAX;
157
158         // Do a little magic to calculate our next checks...
159         const U32 x0 = (startX > xIntercept) * subSqSize;
160         const U32 y0 = (startY > yIntercept) * subSqSize;
161
162         const U32 x1 = subSqSize - x0;
163         const U32 y1 = subSqSize - y0;
164
165         const U32 nextLevel = level - 1;
166
167         // Ok, now let's figure out what nodes, in what order, need to go
168         // on the stack. We push things on in reverse order of processing.
169         if(xInt > endT && yInt > endT)
170         {
171            stack[stackSize].squarePos.set(squarePos.x + x0, squarePos.y + y0);
172            stack[stackSize].level = nextLevel;
173            stackSize++;
174         }
175         else if(xInt < yInt)
176         {
177            F32 nextIntersect = endT;
178
179            if(yInt <= endT)
180            {
181               stack[stackSize].squarePos.set(squarePos.x + x1, squarePos.y + y1);
182               stack[stackSize].startT = yInt;
183               stack[stackSize].endT   = endT;
184               stack[stackSize].level  = nextLevel;
185               nextIntersect = yInt;
186               stackSize++;
187            }
188
189            // Do middle two, order doesn't matter.
190            stack[stackSize].squarePos.set(squarePos.x + x1, squarePos.y + y0);
191            stack[stackSize].startT = xInt;
192            stack[stackSize].endT   = nextIntersect;
193            stack[stackSize].level  = nextLevel;
194
195            stack[stackSize+1].squarePos.set(squarePos.x + x0, squarePos.y + y0);
196            stack[stackSize+1].startT = startT;
197            stack[stackSize+1].endT   = xInt;
198            stack[stackSize+1].level  = nextLevel;
199            stackSize += 2;
200         }
201         else if(yInt < xInt)
202         {
203            F32 nextIntersect = endT;
204            if(xInt <= endT)
205            {
206               stack[stackSize].squarePos.set(squarePos.x + x1, squarePos.y + y1);
207               stack[stackSize].startT = xInt;
208               stack[stackSize].endT   = endT;
209               stack[stackSize].level  = nextLevel;
210               nextIntersect = xInt;
211               stackSize++;
212            }
213            stack[stackSize].squarePos.set(squarePos.x + x0, squarePos.y + y1);
214            stack[stackSize].startT  = yInt;
215            stack[stackSize].endT    = nextIntersect;
216            stack[stackSize].level   = nextLevel;
217
218            stack[stackSize+1].squarePos.set(squarePos.x + x0, squarePos.y + y0);
219            stack[stackSize+1].startT = startT;
220            stack[stackSize+1].endT   = yInt;
221            stack[stackSize+1].level  = nextLevel;
222            stackSize += 2;
223         }
224         else
225         {
226            stack[stackSize].squarePos.set(squarePos.x + x1, squarePos.y + y1);
227            stack[stackSize].startT = xInt;
228            stack[stackSize].endT   = endT;
229            stack[stackSize].level  = nextLevel;
230
231            stack[stackSize+1].squarePos.set(squarePos.x + x0, squarePos.y + y0);
232            stack[stackSize+1].startT = startT;
233            stack[stackSize+1].endT   = xInt;
234            stack[stackSize+1].level  = nextLevel;
235            stackSize += 2;
236         }
237      }
238   }
239
240   // Nothing found, so give up.
241   PROFILE_END();
242   return false;
243}
244