Text archives Help

---

Author: sparker
Date: Wed Mar 14 15:09:21 2007
New Revision: 1302

Added:
   trunk/Engine/ImageTraversers/DeadlineImageTraverser.cc
   trunk/Engine/ImageTraversers/DeadlineImageTraverser.h
Modified:
   trunk/Engine/ImageTraversers/CMakeLists.txt
Log:
Add first iteration of a progressive refinement mechanism


Modified: trunk/Engine/ImageTraversers/CMakeLists.txt
==============================================================================
--- trunk/Engine/ImageTraversers/CMakeLists.txt (original)
+++ trunk/Engine/ImageTraversers/CMakeLists.txt Wed Mar 14 15:09:21 2007
@@ -1,5 +1,7 @@
 
 SET (Manta_ImageTraversers_SRCS
+     ImageTraversers/DeadlineImageTraverser.cc
+     ImageTraversers/DeadlineImageTraverser.h
      ImageTraversers/DissolveImageTraverser.cc
      ImageTraversers/DissolveImageTraverser.h
      ImageTraversers/DissolveTiledImageTraverser.cc

Added: trunk/Engine/ImageTraversers/DeadlineImageTraverser.cc
==============================================================================
--- (empty file)
+++ trunk/Engine/ImageTraversers/DeadlineImageTraverser.cc      Wed Mar 14 
15:09:21 2007
@@ -0,0 +1,418 @@
+// TODO
+// Profile/optimize
+// Better criteria
+// Spatial criteria (1 iteration of lcong)
+// Error criteria
+// Should do pixel centers - directly to renderer, or alternate interface??
+// Avoid false sharing in tiles - pad or make per-processor tile arrays?
+
+/*
+  For more information, please see: http://software.sci.utah.edu
+
+  The MIT License
+
+  Copyright (c) 2005
+  Scientific Computing and Imaging Institute, University of Utah
+
+  License for the specific language governing rights and limitations under
+  Permission is hereby granted, free of charge, to any person obtaining a
+  copy of this software and associated documentation files (the "Software"),
+  to deal in the Software without restriction, including without limitation
+  the rights to use, copy, modify, merge, publish, distribute, sublicense,
+  and/or sell copies of the Software, and to permit persons to whom the
+  Software is furnished to do so, subject to the following conditions:
+
+  The above copyright notice and this permission notice shall be included
+  in all copies or substantial portions of the Software.
+
+  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+  OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+  THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+  FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+  DEALINGS IN THE SOFTWARE.
+*/
+
+#include <Engine/ImageTraversers/DeadlineImageTraverser.h>
+#include <Core/Exceptions/IllegalArgument.h>
+#include <Core/Math/MinMax.h>
+#include <Core/Math/Expon.h>
+#include <Core/Thread/Time.h>
+#include <Core/Thread/Mutex.h>
+#include <Core/Util/Args.h>
+#include <Core/Util/NotFinished.h>
+#include <Interface/Context.h>
+#include <Interface/Fragment.h>
+#include <Interface/Image.h>
+#include <Interface/LoadBalancer.h>
+#include <Interface/PixelSampler.h>
+#include <Engine/PixelSamplers/SingleSampler.h>
+#include <Interface/RayPacket.h> // for maxsize
+#include <MantaSSE.h>
+#include <set>
+
+using namespace Manta;
+using SCIRun::Time;
+
+ImageTraverser* DeadlineImageTraverser::create(const vector<string>& args)
+{
+  return new DeadlineImageTraverser(args);
+}
+
+DeadlineImageTraverser::DeadlineImageTraverser(const vector<string>& args)
+  : qlock("DeadlineImageTraverser queue lock")
+{
+  float frameRate = 15;
+  ypacketsize = 1;
+  while(ypacketsize * ypacketsize * 2 < Fragment::MaxSize)
+    ypacketsize *= 2;
+  xpacketsize = Fragment::MaxSize / ypacketsize;
+  xcoarsepixelsize = 8;
+  ycoarsepixelsize = 8;
+  xrefinementRatio = 2;
+  yrefinementRatio = 2;
+  priority = LuminanceVariance;
+  int argc = static_cast<int>(args.size());
+  for(int i = 0; i<argc;i++){
+    string arg = args[i];
+    if(arg == "-packetsize"){
+      if(!getResolutionArg(i, args, xpacketsize, ypacketsize))
+        throw IllegalArgument("DeadlineImageTraverser -packetsize", i, args);
+      if(xpacketsize * ypacketsize > Fragment::MaxSize)
+        throw IllegalArgument("DeadlineImageTraverser -packetsize too 
large", i, args);
+    } else if(arg == "-framerate"){
+      if(!getArg(i, args, frameRate))
+        throw IllegalArgument("DeadlineImageTraverser -framerate", i, args);
+    } else if(arg == "-magnification"){
+      if(!getResolutionArg(i, args, xcoarsepixelsize, ycoarsepixelsize))
+        throw IllegalArgument("DeadlineImageTraverser -magnification", i, 
args);
+    } else if(arg == "-priority"){
+      string priorityString;
+      if(!getArg(i, args, priorityString))
+        throw IllegalArgument("DeadlineImageTraverser -priority", i, args);
+      if(priorityString == "FIFO")
+        priority = FIFO;
+      else if(priorityString == "luminancevariance")
+        priority = LuminanceVariance;
+      else
+        throw IllegalArgument("DeadlineImageTraverser -priority, bad 
priority", i, args);
+    } else if("-refinmentRatio"){
+      if(!getResolutionArg(i, args, xrefinementRatio, yrefinementRatio))
+        throw IllegalArgument("DeadlineImageTraverser -refinement", i, args);
+    } else {
+      throw IllegalArgument("DeadlineImageTraverser", i, args);
+    }
+  }
+  frameTime = 1./frameRate;
+  tiles = 0;
+  queue = 0;
+  total_tiles = 0;
+  qsize = 0;
+  singleSampler = new SingleSampler(vector<string>());
+}
+
+DeadlineImageTraverser::~DeadlineImageTraverser()
+{
+}
+
+void DeadlineImageTraverser::setupBegin(SetupContext& context, int 
numChannels)
+{
+  singleSampler->setupBegin(context, numChannels);
+  context.loadBalancer->setupBegin(context, numChannels);
+  context.pixelSampler->setupBegin(context, numChannels);
+  if(total_tiles){
+    delete[] tiles;
+    delete[] queue;
+  }
+  total_tiles = 0;
+  top_tiles = 0;
+}
+
+void DeadlineImageTraverser::setupDisplayChannel(SetupContext& context)
+{
+  // Determine the resolution.
+  bool stereo;
+  int xres, yres;
+  context.getResolution(stereo, xres, yres);
+
+  // Determine how many coarse tiles are needed.
+  int coarse_xres = (xres + xcoarsepixelsize-1)/xcoarsepixelsize;
+  int coarse_yres = (yres + ycoarsepixelsize-1)/ycoarsepixelsize;
+
+  int xtiles = (coarse_xres + xpacketsize-1)/xpacketsize;
+  int ytiles = (coarse_yres + ypacketsize-1)/ypacketsize;
+
+  // Tell the load balancer how much work to assign.
+  int numAssignments = xtiles * ytiles;
+  context.loadBalancer->setupDisplayChannel(context, numAssignments);
+
+  // Continue setting up the rendering stack.
+  context.pixelSampler->setupDisplayChannel(context);
+
+  int cur = 1;
+  int ntotal = 0;
+  int x = xcoarsepixelsize;
+  int y = ycoarsepixelsize;
+  while(x > 1 && y > 1){
+    ntotal += cur;
+    cur *= xrefinementRatio * yrefinementRatio;
+    x /= xrefinementRatio;
+    y /= yrefinementRatio;
+  }
+  if(total_tiles){
+    delete[] tiles;
+    delete[] queue;
+  }
+  if(numAssignments > top_tiles)
+    top_tiles = numAssignments;
+  total_tiles += ntotal * xtiles * ytiles;
+  tiles = new Tile[total_tiles];
+  queue = new Tile*[total_tiles];
+
+  singleSampler->setupDisplayChannel(context);
+}
+
+void DeadlineImageTraverser::setupFrame(const RenderContext& context)
+{
+  context.loadBalancer->setupFrame(context);
+  context.pixelSampler->setupFrame(context);
+  qsize = 0;
+  next_tile = top_tiles;
+
+  singleSampler->setupFrame(context);
+  // Determine how long we should render this frame.
+  frameEnd = Time::currentSeconds() + frameTime;
+}
+
+void DeadlineImageTraverser::insertIntoQueue(Tile* tiles, int numtiles)
+{
+  qlock.lock();
+
+  for(int i=0;i<numtiles;i++){
+    Tile* tile = &tiles[i];
+
+    // Heap insert
+    queue[qsize] = tile;
+    int p = qsize++;
+    while(p){
+      int parent = (p-1)>>1;
+      if(queue[p]->priority > queue[parent]->priority){
+        // Swap
+        Tile* tmp = queue[p];
+        queue[p] = queue[parent];
+        queue[parent] = tmp;
+      } else {
+        break;
+      }
+      p = parent;
+    }
+  }
+  qlock.unlock();
+}
+
+DeadlineImageTraverser::Tile* DeadlineImageTraverser::popFromQueue(Tile*& 
childtiles)
+{
+  int numtiles = xrefinementRatio * yrefinementRatio;
+  qlock.lock();
+  if(qsize == 0){
+    qlock.unlock();
+    return 0;
+  }
+
+  // Create space for the children of this tile
+  childtiles = &tiles[next_tile];
+  next_tile += numtiles;
+
+  // Get the next tile and update the queue
+  Tile* tile = queue[0];
+  tile->priority = -1;
+
+  int p = 0;
+  while((p<<1)+2 < qsize){
+    int c1 = (p<<1)+1;
+    int c2 = (p<<1)+2;
+    int c;
+    if(queue[c1]->priority > queue[c2]->priority)
+      c = c1;
+    else
+      c = c2;
+    queue[p] = queue[c];
+    p = c;
+  }
+  if((p<<1)+2 == qsize){
+    int c = (p<<1)+1;
+    queue[p] = queue[c];
+    p = c;
+  } else {
+    queue[p] = queue[qsize-1];
+    while(p){
+      int parent = (p-1)>>1;
+      if(queue[p]->priority > queue[parent]->priority){
+        // Swap
+        Tile* tmp = queue[p];
+        queue[p] = queue[parent];
+        queue[parent] = tmp;
+      } else {
+        break;
+      }
+      p = parent;
+    }
+  }
+  qsize--;
+  qlock.unlock();
+  return tile;
+}
+
+void DeadlineImageTraverser::renderImage(const RenderContext& context, 
Image* image)
+{
+  double bt = Time::currentSeconds();
+  // Determine number of coarse level
+  bool stereo;
+  int xres, yres;
+  image->getResolution(stereo, xres, yres);
+  int numEyes = stereo?2:1;
+
+  int coarse_xres = (xres + xcoarsepixelsize - 1) / xcoarsepixelsize;
+  int coarse_yres = (yres + ycoarsepixelsize - 1) / ycoarsepixelsize;
+
+  int xtiles = (coarse_xres + xpacketsize-1)/xpacketsize;
+  int ytiles = (coarse_yres + ypacketsize-1)/ypacketsize;
+  int xcoarsetilesize = xpacketsize * xcoarsepixelsize;
+  int ycoarsetilesize = ypacketsize * ycoarsepixelsize;
+
+  // First pass - do all of the coarse level tiles with the normal load 
balancer
+  int s,e;
+  while(context.loadBalancer->getNextAssignment(context, s, e)){
+    for(int assignment = s; assignment < e; assignment++){
+      int xtile = assignment/ytiles;
+      int ytile = assignment%ytiles;
+      int xstart = xtile * xcoarsetilesize;
+      int xend = (xtile+1) * xcoarsetilesize;
+
+      if(xend > xres)
+        xend = xres;
+
+      int ystart = ytile * ycoarsetilesize;
+      int yend = (ytile+1) * ycoarsetilesize;
+
+      if(yend > yres)
+        yend = yres;
+
+      Fragment frag(Fragment::SquareShape, Fragment::ConstantEye);
+      frag.setPixelSize(xcoarsepixelsize, ycoarsepixelsize);
+
+      for(int eye = 0; eye < numEyes; eye++){
+        int idx = 0;
+        for (int j = ystart; j < yend; j += ycoarsepixelsize) {
+          for (int i = xstart; i < xend; i += xcoarsepixelsize) {
+            frag.pixel[0][idx] = i;
+            frag.pixel[1][idx] = j;
+            frag.whichEye[idx] = eye;
+            idx++;
+          }
+        }
+        frag.setSize(idx);
+        if((xcoarsepixelsize | ycoarsepixelsize) > 1){
+          singleSampler->renderFragment(context, frag);
+          Tile* tile = &tiles[assignment];
+          tile->xstart = xstart;
+          tile->ystart = ystart;
+          tile->xend = xend;
+          tile->yend = yend;
+          tile->xmag = xcoarsepixelsize;
+          tile->ymag = ycoarsepixelsize;
+          computePriority(tile, frag);
+          insertIntoQueue(tile, 1);
+        } else {
+          context.pixelSampler->renderFragment(context, frag);
+        }
+        image->set(frag);
+      }
+    }
+  }
+
+  while(Time::currentSeconds() < frameEnd){
+    Tile* childtiles;
+    Tile* tile = popFromQueue(childtiles);
+    if(!tile)
+      break;
+
+    int newxmag = tile->xmag/xrefinementRatio;
+    if(newxmag < 1)
+      newxmag = 1;
+    int newymag = tile->ymag/yrefinementRatio;
+    if(newymag < 1)
+      newymag = 1;
+    int xs = xpacketsize * newxmag;
+    int ys = ypacketsize * newymag;
+
+    int nchild = 0;
+    for(int y = tile->ystart; y < tile->yend; y += ys){
+      for(int x = tile->xstart; x < tile->xend; x += xs){
+        int xend = x + xs;
+        if(xend > tile->xend)
+          xend = tile->xend;
+        int yend = y + ys;
+        if(yend > tile->yend)
+          yend = tile->yend;
+
+        Fragment frag(Fragment::SquareShape, Fragment::ConstantEye);
+        frag.setPixelSize(newxmag, newymag);
+        int idx = 0;
+        for (int j = y; j < yend; j+=newymag) {
+          for (int i = x; i < xend; i+=newxmag) {
+            frag.pixel[0][idx] = i;
+            frag.pixel[1][idx] = j;
+            frag.whichEye[idx] = 0;
+            idx++;
+          }
+        }
+        frag.setSize(idx);
+
+        if((newxmag | newymag) > 1){
+          singleSampler->renderFragment(context, frag);
+          Tile* childtile = &childtiles[nchild];
+          childtile->xstart = x;
+          childtile->xend = xend;
+          childtile->ystart = y;
+          childtile->yend = yend;
+          childtile->xmag = newxmag;
+          childtile->ymag = newymag;
+          computePriority(childtile, frag);
+          nchild++;
+        } else {
+          context.pixelSampler->renderFragment(context, frag);
+        }
+        image->set(frag);
+      }
+    }
+    if(nchild)
+      insertIntoQueue(childtiles, nchild);
+  }
+
+  // This can potentially happen before the other procesors are finished
+  // rendering, but that is okay because it won't get displayed until
+  // everyone enters the barrier anyway
+  if(context.proc == 0)
+    image->setValid(true);
+}
+
+void DeadlineImageTraverser::computePriority(Tile* tile, const Fragment& 
frag) const
+{
+  if(priority == LuminanceVariance){
+    double sum;
+    double sum2;
+    for(int i=frag.begin();i<frag.end();i++){
+      Color::ComponentType luminance = frag.getColor(i).luminance();
+      sum += luminance;
+      sum2 += luminance * luminance;
+    }
+    int n = frag.end()-frag.begin();
+    Color::ComponentType variance = (sum2 - sum * sum/n)/(n-1);
+    tile->priority = variance * tile->xmag * tile->ymag;
+  } else {
+    tile->priority = tile->xmag * tile->ymag;
+  }
+}
+

Added: trunk/Engine/ImageTraversers/DeadlineImageTraverser.h
==============================================================================
--- (empty file)
+++ trunk/Engine/ImageTraversers/DeadlineImageTraverser.h       Wed Mar 14 
15:09:21 2007
@@ -0,0 +1,100 @@
+
+#ifndef Manta_Engine_DeadlineImageTraverser_h
+#define Manta_Engine_DeadlineImageTraverser_h
+
+/*
+  For more information, please see: http://software.sci.utah.edu
+
+  The MIT License
+
+  Copyright (c) 2005
+  Scientific Computing and Imaging Institute, University of Utah
+
+  License for the specific language governing rights and limitations under
+  Permission is hereby granted, free of charge, to any person obtaining a
+  copy of this software and associated documentation files (the "Software"),
+  to deal in the Software without restriction, including without limitation
+  the rights to use, copy, modify, merge, publish, distribute, sublicense,
+  and/or sell copies of the Software, and to permit persons to whom the
+  Software is furnished to do so, subject to the following conditions:
+
+  The above copyright notice and this permission notice shall be included
+  in all copies or substantial portions of the Software.
+
+  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+  OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+  THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+  FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+  DEALINGS IN THE SOFTWARE.
+*/
+
+#include <Interface/ImageTraverser.h>
+#include <Interface/Fragment.h>
+#include <Core/Thread/Mutex.h>
+#include <sgi_stl_warnings_off.h>
+#include <string>
+#include <vector>
+#include <sgi_stl_warnings_on.h>
+#include <MantaSSE.h>
+
+namespace Manta {
+  using namespace std;
+  class SingleSampler;
+
+  class DeadlineImageTraverser : public ImageTraverser {
+  public:
+    DeadlineImageTraverser(const vector<string>& args);
+    virtual ~DeadlineImageTraverser();
+    virtual void setupBegin(SetupContext&, int numChannels);
+    virtual void setupDisplayChannel(SetupContext&);
+    virtual void setupFrame(const RenderContext& context);
+    virtual void renderImage(const RenderContext& context, Image* image);
+
+    static ImageTraverser* create(const vector<string>& args);
+  private:
+    DeadlineImageTraverser(const DeadlineImageTraverser&);
+    DeadlineImageTraverser& operator=(const DeadlineImageTraverser&);
+
+    SingleSampler* singleSampler;
+
+    int xpacketsize;
+    int ypacketsize;
+
+    int xcoarsepixelsize;
+    int ycoarsepixelsize;
+    int xrefinementRatio;
+    int yrefinementRatio;
+    double frameTime;
+    double frameEnd;
+
+    struct Tile {
+      float priority;
+      int xstart;
+      int ystart;
+      int xend;
+      int yend;
+      int xmag;
+      int ymag;
+    };
+    SCIRun::Mutex qlock;
+    Tile* tiles;
+    Tile** queue;
+    int next_tile;
+    int qsize;
+    int total_tiles;
+    int top_tiles;
+
+    enum PriorityScheme {
+      FIFO, LuminanceVariance
+    };
+    PriorityScheme priority;
+
+    void insertIntoQueue(Tile* oldtile, int numtiles);
+    Tile* popFromQueue(Tile*& childtiles);
+    void computePriority(Tile* tile, const Fragment& frag) const;
+  };
+}
+
+#endif

---

• [MANTA] r1302 - trunk/Engine/ImageTraversers, sparker, 03/14/2007

---

Archive powered by MHonArc 2.6.16.