Grid.h

Go to the documentation of this file.

/*
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 */
 
#pragma once
 
#include <cstring>  // for memset
#include <float.h>
#include <stdint.h>  // For POINTER_FROM_UINT, i.e. uintptr_t.
#include <vector>
 
#include "Geom.h"
#include "GeomUtils.h"
#include "Polygon.h"
 
#include "../system/FreestyleConfig.h"
 
#include "BLI_utildefines.h"
 
#ifdef WITH_CXX_GUARDEDALLOC
#  include "MEM_guardedalloc.h"
#endif
 
using namespace std;
 
namespace Freestyle {
 
using namespace Geometry;
 
typedef vector<Polygon3r *> OccludersSet;
 
//
// Class to define cells used by the regular grid
//
 
class Cell {
 public:
  Cell(Vec3r &orig)
  {
    _orig = orig;
  }
 
  virtual ~Cell()
  {
  }
 
  inline void addOccluder(Polygon3r *o)
  {
    if (o) {
      _occluders.push_back(o);
    }
  }
 
  inline const Vec3r &getOrigin()
  {
    return _orig;
  }
 
  inline OccludersSet &getOccluders()
  {
    return _occluders;
  }
 
 private:
  Vec3r _orig;
  OccludersSet _occluders;
 
#ifdef WITH_CXX_GUARDEDALLOC
  MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:Cell")
#endif
};
 
class GridVisitor {
 public:
  virtual ~GridVisitor(){};  // soc
 
  virtual void discoverCell(Cell * /*cell*/)
  {
  }
 
  virtual void examineOccluder(Polygon3r * /*occ*/)
  {
  }
 
  virtual void finishCell(Cell * /*cell*/)
  {
  }
 
  virtual bool stop()
  {
    return false;
  }
 
#ifdef WITH_CXX_GUARDEDALLOC
  MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:GridVisitor")
#endif
};
 
class allOccludersGridVisitor : public GridVisitor {
 public:
  allOccludersGridVisitor(OccludersSet &occluders) : GridVisitor(), occluders_(occluders)
  {
  }
 
  virtual void examineOccluder(Polygon3r *occ);
 
  OccludersSet &occluders()
  {
    return occluders_;
  }
 
  void clear()
  {
    occluders_.clear();
  }
 
 private:
  OccludersSet &occluders_;
};
 
class firstIntersectionGridVisitor : public GridVisitor {
  // soc - changed order to remove warnings
 public:
  double u_, v_, t_;
 
 private:
  Polygon3r *occluder_;
  Vec3r ray_org_, ray_dir_, cell_size_;
  Cell *current_cell_;
 
 public:
  firstIntersectionGridVisitor(const Vec3r &ray_org, const Vec3r &ray_dir, const Vec3r &cell_size)
      : GridVisitor(),
        u_(0),
        v_(0),
        t_(DBL_MAX),
        occluder_(0),
        ray_org_(ray_org),
        ray_dir_(ray_dir),
        cell_size_(cell_size),
        current_cell_(0)
  {
  }
 
  virtual ~firstIntersectionGridVisitor()
  {
  }
 
  virtual void discoverCell(Cell *cell)
  {
    current_cell_ = cell;
  }
 
  virtual void examineOccluder(Polygon3r *occ);
 
  virtual bool stop();
 
  Polygon3r *occluder()
  {
    return occluder_;
  }
};
 
//
// Class to define a regular grid used for ray casting computations
//
 
class Grid {
 public:
  Grid()
  {
  }
 
  virtual ~Grid()
  {
    clear();
  }
 
  virtual void clear();
 
  virtual void configure(const Vec3r &orig, const Vec3r &size, unsigned nb);
 
  inline void getCellCoordinates(const Vec3r &p, Vec3u &res)
  {
    int tmp;
    for (int i = 0; i < 3; i++) {
      tmp = (int)((p[i] - _orig[i]) / _cell_size[i]);
      if (tmp < 0) {
        res[i] = 0;
      }
      else if ((unsigned int)tmp >= _cells_nb[i]) {
        res[i] = _cells_nb[i] - 1;
      }
      else {
        res[i] = tmp;
      }
    }
  }
 
  virtual void fillCell(const Vec3u &coord, Cell &cell) = 0;
 
  virtual Cell *getCell(const Vec3u &coord) = 0;
 
  inline Cell *getCell(const Vec3r &p)
  {
    Vec3u coord;
    getCellCoordinates(p, coord);
    return getCell(coord);
  }
 
  inline void getCellOrigin(const Vec3u &cell_coord, Vec3r &orig)
  {
    for (unsigned int i = 0; i < 3; i++) {
      orig[i] = _orig[i] + cell_coord[i] * _cell_size[i];
    }
  }
 
  inline void getCellBox(const Vec3u &cell_coord, Vec3r &min_out, Vec3r &max_out)
  {
    getCellOrigin(cell_coord, min_out);
    max_out = min_out + _cell_size;
  }
 
  void insertOccluder(Polygon3r *occluder);
 
  void addOccluder(Polygon3r *occluder)
  {
    _occluders.push_back(occluder);
  }
 
  void castRay(const Vec3r &orig, const Vec3r &end, OccludersSet &occluders, unsigned timestamp);
 
  // Prepares to cast ray without generating OccludersSet
  void initAcceleratedRay(const Vec3r &orig, const Vec3r &end, unsigned timestamp);
 
  void castInfiniteRay(const Vec3r &orig,
                       const Vec3r &dir,
                       OccludersSet &occluders,
                       unsigned timestamp);
 
  // Prepares to cast ray without generating OccludersSet.
  bool initAcceleratedInfiniteRay(const Vec3r &orig, const Vec3r &dir, unsigned timestamp);
 
  Polygon3r *castRayToFindFirstIntersection(
      const Vec3r &orig, const Vec3r &dir, double &t, double &u, double &v, unsigned timestamp);
 
  void initRay(const Vec3r &orig, const Vec3r &end, unsigned timestamp);
 
  bool initInfiniteRay(const Vec3r &orig, const Vec3r &dir, unsigned timestamp);
 
  inline const Vec3r &getOrigin() const
  {
    return _orig;
  }
 
  inline Vec3r gridSize() const
  {
    return _size;
  }
 
  inline Vec3r getCellSize() const
  {
    return _cell_size;
  }
 
  // ARB profiling only:
  inline OccludersSet *getOccluders()
  {
    return &_occluders;
  }
 
  void displayDebug()
  {
    cerr << "Cells nb     : " << _cells_nb << endl;
    cerr << "Cell size    : " << _cell_size << endl;
    cerr << "Origin       : " << _orig << endl;
    cerr << "Occluders nb : " << _occluders.size() << endl;
  }
 
 protected:
  inline void castRayInternal(GridVisitor &visitor)
  {
    Cell *current_cell = NULL;
    do {
      current_cell = getCell(_current_cell);
      if (current_cell) {
        visitor.discoverCell(current_cell);
        OccludersSet &occluders =
            current_cell->getOccluders();  // FIXME: I had forgotten the ref &
        for (OccludersSet::iterator it = occluders.begin(); it != occluders.end(); it++) {
          if (POINTER_AS_UINT((*it)->userdata2) != _timestamp) {
            (*it)->userdata2 = POINTER_FROM_UINT(_timestamp);
            visitor.examineOccluder(*it);
          }
        }
        visitor.finishCell(current_cell);
      }
    } while ((!visitor.stop()) && (nextRayCell(_current_cell, _current_cell)));
  }
 
  bool nextRayCell(Vec3u &current_cell, Vec3u &next_cell);
 
  unsigned int _timestamp;
 
  Vec3u _cells_nb;   // number of cells for x,y,z axis
  Vec3r _cell_size;  // cell x,y,z dimensions
  Vec3r _size;       // grid x,y,x dimensions
  Vec3r _orig;       // grid origin
 
  Vec3r _ray_dir;       // direction vector for the ray
  Vec3u _current_cell;  // The current cell being processed (designated by its 3 coordinates)
  Vec3r _pt;    // Points corresponding to the incoming and outgoing intersections of one cell with
                // the ray
  real _t_end;  // To know when we are at the end of the ray
  real _t;
 
  // OccludersSet _ray_occluders; // Set storing the occluders contained in the cells traversed by
  // a ray
  OccludersSet _occluders;  // List of all occluders inserted in the grid
 
#ifdef WITH_CXX_GUARDEDALLOC
  MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:Grid")
#endif
};
 
//
// Class to walk through occluders in grid without building intermediate data structures
//
 
class VirtualOccludersSet {
 public:
  VirtualOccludersSet(Grid &_grid) : grid(_grid){};
  Polygon3r *begin();
  Polygon3r *next();
  Polygon3r *next(bool stopOnNewCell);
 
 private:
  Polygon3r *firstOccluderFromNextCell();
  Grid &grid;
  OccludersSet::iterator it, end;
 
#ifdef WITH_CXX_GUARDEDALLOC
  MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:VirtualOccludersSet")
#endif
};
 
} /* namespace Freestyle */