BoxGrid.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
 
#define BOX_GRID_LOGGING 0
 
// I would like to avoid using deque because including ViewMap.h and <deque> or <vector>
// separately results in redefinitions of identifiers. ViewMap.h already includes <vector>
// so it should be a safe fall-back.
//#include <vector>
//#include <deque>
 
#include "GridDensityProvider.h"
#include "OccluderSource.h"
#include "ViewMap.h"
 
#include "../geometry/BBox.h"
#include "../geometry/GridHelpers.h"
#include "../geometry/Polygon.h"
 
#include "../system/PointerSequence.h"
 
#include "../winged_edge/WEdge.h"
 
#include "BKE_global.h"
 
#ifdef WITH_CXX_GUARDEDALLOC
#  include "MEM_guardedalloc.h"
#endif
 
namespace Freestyle {
 
class BoxGrid {
 public:
  // Helper classes
  struct OccluderData {
    explicit OccluderData(OccluderSource &source, Polygon3r &p);
    Polygon3r poly;
    Polygon3r cameraSpacePolygon;
    real shallowest, deepest;
    // N.B. We could, of course, store face in poly's userdata member, like the old ViewMapBuilder
    // code does. However, code comments make it clear that userdata is deprecated, so we avoid the
    // temptation to save 4 or 8 bytes.
    WFace *face;
 
#ifdef WITH_CXX_GUARDEDALLOC
    MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:BoxGrid:OccluderData")
#endif
  };
 
 private:
  struct Cell {
    // Can't store Cell in a vector without copy and assign
    // Cell(const Cell& other);
    // Cell& operator=(const Cell& other);
 
    explicit Cell() = default;
 
    static bool compareOccludersByShallowestPoint(const OccluderData *a, const OccluderData *b);
 
    void setDimensions(real x, real y, real sizeX, real sizeY);
    void checkAndInsert(OccluderSource &source, Polygon3r &poly, OccluderData *&occluder);
    void indexPolygons();
 
    real boundary[4];
    // deque<OccluderData*> faces;
    vector<OccluderData *> faces;
  };
 
 public:
  /* Iterator needs to allow the user to avoid full 3D comparison in two cases:
   *
   * (1) Where (*current)->deepest < target[2], where the occluder is unambiguously in front of the
   * target point.
   *
   * (2) Where (*current)->shallowest > target[2], where the occluder is unambiguously in back of
   * the target point.
   *
   * In addition, when used by OptimizedFindOccludee, Iterator should stop iterating as soon as it
   * has an occludee candidate and (*current)->shallowest > candidate[2], because at that point
   * forward no new occluder could possibly be a better occludee.
   */
  class Iterator {
   public:
    // epsilon is not used in this class, but other grids with the same interface may need an
    // epsilon
    explicit Iterator(BoxGrid &grid, Vec3r &center, real epsilon = 1.0e-06);
    void initBeforeTarget();
    void initAfterTarget();
    void nextOccluder();
    void nextOccludee();
    bool validBeforeTarget();
    bool validAfterTarget();
    WFace *getWFace() const;
    Polygon3r *getCameraSpacePolygon();
    void reportDepth(Vec3r origin, Vec3r u, real t);
 
   private:
    bool testOccluder(bool wantOccludee);
    void markCurrentOccludeeCandidate(real depth);
 
    Cell *_cell;
    Vec3r _target;
    bool _foundOccludee;
    real _occludeeDepth;
    // deque<OccluderData*>::iterator _current, _occludeeCandidate;
    vector<OccluderData *>::iterator _current, _occludeeCandidate;
 
#ifdef WITH_CXX_GUARDEDALLOC
    MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:BoxGrid:Iterator")
#endif
  };
 
  class Transform : public GridHelpers::Transform {
   public:
    explicit Transform() = default;
    explicit Transform(Transform &other);
    Vec3r operator()(const Vec3r &point) const;
  };
 
 private:
  // Prevent implicit copies and assignments.
  BoxGrid(const BoxGrid &other);
  BoxGrid &operator=(const BoxGrid &other);
 
 public:
  explicit BoxGrid(OccluderSource &source,
                   GridDensityProvider &density,
                   ViewMap *viewMap,
                   Vec3r &viewpoint,
                   bool enableQI);
  virtual ~BoxGrid();
 
  // Generate Cell structure
  void assignCells(OccluderSource &source, GridDensityProvider &density, ViewMap *viewMap);
  // Fill Cells
  void distributePolygons(OccluderSource &source);
  // Insert one polygon into each matching cell, return true if any cell consumes the polygon
  bool insertOccluder(OccluderSource &source, OccluderData *&occluder);
  // Sort occluders in each cell
  void reorganizeCells();
 
  Cell *findCell(const Vec3r &point);
 
  // Accessors:
  bool orthographicProjection() const;
  const Vec3r &viewpoint() const;
  bool enableQI() const;
  Transform transform;
 
 private:
  void getCellCoordinates(const Vec3r &point, unsigned &x, unsigned &y);
 
  typedef PointerSequence<vector<Cell *>, Cell *> cellContainer;
  // typedef PointerSequence<deque<OccluderData*>, OccluderData*> occluderContainer;
  typedef PointerSequence<vector<OccluderData *>, OccluderData *> occluderContainer;
  unsigned _cellsX, _cellsY;
  float _cellSize;
  float _cellOrigin[2];
  cellContainer _cells;
  occluderContainer _faces;
  Vec3r _viewpoint;
  bool _enableQI;
 
#ifdef WITH_CXX_GUARDEDALLOC
  MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:BoxGrid")
#endif
};
 
inline void BoxGrid::Iterator::initBeforeTarget()
{
  _current = _cell->faces.begin();
  while (_current != _cell->faces.end() && !testOccluder(false)) {
    ++_current;
  }
}
 
inline void BoxGrid::Iterator::initAfterTarget()
{
  if (_foundOccludee) {
#if BOX_GRID_LOGGING
    if (G.debug & G_DEBUG_FREESTYLE) {
      std::cout << "\tStarting occludee search from occludeeCandidate at depth " << _occludeeDepth
                << std::endl;
    }
#endif
    _current = _occludeeCandidate;
    return;
  }
 
#if BOX_GRID_LOGGING
  if (G.debug & G_DEBUG_FREESTYLE) {
    std::cout << "\tStarting occludee search from current position" << std::endl;
  }
#endif
 
  while (_current != _cell->faces.end() && !testOccluder(true)) {
    ++_current;
  }
}
 
inline bool BoxGrid::Iterator::testOccluder(bool wantOccludee)
{
  // End-of-list is not even a valid iterator position
  if (_current == _cell->faces.end()) {
    // Returning true seems strange, but it will break us out of whatever loop is calling
    // testOccluder, and _current = _cell->face.end() will make the calling routine give up.
    return true;
  }
#if BOX_GRID_LOGGING
  if (G.debug & G_DEBUG_FREESTYLE) {
    std::cout << "\tTesting occluder " << (*_current)->poly.getVertices()[0];
    for (unsigned int i = 1; i < (*_current)->poly.getVertices().size(); ++i) {
      std::cout << ", " << (*_current)->poly.getVertices()[i];
    }
    std::cout << " from shape " << (*_current)->face->GetVertex(0)->shape()->GetId() << std::endl;
  }
#endif
 
  // If we have an occluder candidate and we are unambiguously after it, abort
  if (_foundOccludee && (*_current)->shallowest > _occludeeDepth) {
#if BOX_GRID_LOGGING
    if (G.debug & G_DEBUG_FREESTYLE) {
      std::cout << "\t\tAborting: shallowest > occludeeCandidate->deepest" << std::endl;
    }
#endif
    _current = _cell->faces.end();
 
    // See note above
    return true;
  }
 
  // Specific continue or stop conditions when searching for each type
  if (wantOccludee) {
    if ((*_current)->deepest < _target[2]) {
#if BOX_GRID_LOGGING
      if (G.debug & G_DEBUG_FREESTYLE) {
        std::cout << "\t\tSkipping: shallower than target while looking for occludee" << std::endl;
      }
#endif
      return false;
    }
  }
  else {
    if ((*_current)->shallowest > _target[2]) {
#if BOX_GRID_LOGGING
      if (G.debug & G_DEBUG_FREESTYLE) {
        std::cout << "\t\tStopping: deeper than target while looking for occluder" << std::endl;
      }
#endif
      return true;
    }
  }
 
  // Depthwise, this is a valid occluder.
 
  // Check to see if target is in the 2D bounding box
  Vec3r bbMin, bbMax;
  (*_current)->poly.getBBox(bbMin, bbMax);
  if (_target[0] < bbMin[0] || _target[0] > bbMax[0] || _target[1] < bbMin[1] ||
      _target[1] > bbMax[1]) {
#if BOX_GRID_LOGGING
    if (G.debug & G_DEBUG_FREESTYLE) {
      std::cout << "\t\tSkipping: bounding box violation" << std::endl;
    }
#endif
    return false;
  }
 
  // We've done all the corner cutting we can.
  // Let the caller work out whether or not the geometry is correct.
  return true;
}
 
inline void BoxGrid::Iterator::reportDepth(Vec3r origin, Vec3r u, real t)
{
  // The reported depth is the length of a ray in camera space
  // We need to convert it into a Z-value in grid space
  real depth = -(origin + (u * t))[2];
#if BOX_GRID_LOGGING
  if (G.debug & G_DEBUG_FREESTYLE) {
    std::cout << "\t\tReporting depth of occluder/ee: " << depth;
  }
#endif
  if (depth > _target[2]) {
#if BOX_GRID_LOGGING
    if (G.debug & G_DEBUG_FREESTYLE) {
      std::cout << " is deeper than target" << std::endl;
    }
#endif
    // If the current occluder is the best occludee so far, save it.
    if (!_foundOccludee || _occludeeDepth > depth) {
      markCurrentOccludeeCandidate(depth);
    }
  }
  else {
#if BOX_GRID_LOGGING
    if (G.debug & G_DEBUG_FREESTYLE) {
      std::cout << std::endl;
    }
#endif
  }
}
 
inline void BoxGrid::Iterator::nextOccluder()
{
  if (_current != _cell->faces.end()) {
    do {
      ++_current;
    } while (_current != _cell->faces.end() && !testOccluder(false));
  }
}
 
inline void BoxGrid::Iterator::nextOccludee()
{
  if (_current != _cell->faces.end()) {
    do {
      ++_current;
    } while (_current != _cell->faces.end() && !testOccluder(true));
  }
}
 
inline bool BoxGrid::Iterator::validBeforeTarget()
{
  return _current != _cell->faces.end() && (*_current)->shallowest <= _target[2];
}
 
inline bool BoxGrid::Iterator::validAfterTarget()
{
  return _current != _cell->faces.end();
}
 
inline void BoxGrid::Iterator::markCurrentOccludeeCandidate(real depth)
{
#if BOX_GRID_LOGGING
  if (G.debug & G_DEBUG_FREESTYLE) {
    std::cout << "\t\tFound occludeeCandidate at depth " << depth << std::endl;
  }
#endif
  _occludeeCandidate = _current;
  _occludeeDepth = depth;
  _foundOccludee = true;
}
 
inline WFace *BoxGrid::Iterator::getWFace() const
{
  return (*_current)->face;
}
 
inline Polygon3r *BoxGrid::Iterator::getCameraSpacePolygon()
{
  return &((*_current)->cameraSpacePolygon);
}
 
inline BoxGrid::OccluderData::OccluderData(OccluderSource &source, Polygon3r &p)
    : poly(p), cameraSpacePolygon(source.getCameraSpacePolygon()), face(source.getWFace())
{
  // Set shallowest and deepest based on bbox
  Vec3r min, max;
  poly.getBBox(min, max);
  shallowest = min[2];
  deepest = max[2];
}
 
inline void BoxGrid::Cell::checkAndInsert(OccluderSource &source,
                                          Polygon3r &poly,
                                          OccluderData *&occluder)
{
  if (GridHelpers::insideProscenium(boundary, poly)) {
    if (occluder == NULL) {
      // Disposal of occluder will be handled in BoxGrid::distributePolygons(),
      // or automatically by BoxGrid::_faces;
      occluder = new OccluderData(source, poly);
    }
    faces.push_back(occluder);
  }
}
 
inline bool BoxGrid::insertOccluder(OccluderSource &source, OccluderData *&occluder)
{
  Polygon3r &poly(source.getGridSpacePolygon());
  occluder = NULL;
 
  Vec3r bbMin, bbMax;
  poly.getBBox(bbMin, bbMax);
  // Check overlapping cells
  unsigned startX, startY, endX, endY;
  getCellCoordinates(bbMin, startX, startY);
  getCellCoordinates(bbMax, endX, endY);
 
  for (unsigned int i = startX; i <= endX; ++i) {
    for (unsigned int j = startY; j <= endY; ++j) {
      if (_cells[i * _cellsY + j] != NULL) {
        _cells[i * _cellsY + j]->checkAndInsert(source, poly, occluder);
      }
    }
  }
 
  return occluder != NULL;
}
 
} /* namespace Freestyle */