Grid.h

Go to the documentation of this file.

/* SPDX-FileCopyrightText: 2023 Blender Authors
 *
 * SPDX-License-Identifier: GPL-2.0-or-later */
 
#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"
 
#include "MEM_guardedalloc.h"
 
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;
 
  MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:Cell")
};
 
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;
  }
 
  MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:GridVisitor")
};

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, uint 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 ((uint)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 (uint 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, uint timestamp);
 
  // Prepares to cast ray without generating OccludersSet
  void initAcceleratedRay(const Vec3r &orig, const Vec3r &end, uint timestamp);

  void castInfiniteRay(const Vec3r &orig,
                       const Vec3r &dir,
                       OccludersSet &occluders,
                       uint timestamp);
 
  // Prepares to cast ray without generating OccludersSet.
  bool initAcceleratedInfiniteRay(const Vec3r &orig, const Vec3r &dir, uint timestamp);

  Polygon3r *castRayToFindFirstIntersection(
      const Vec3r &orig, const Vec3r &dir, double &t, double &u, double &v, uint timestamp);

  void initRay(const Vec3r &orig, const Vec3r &end, uint timestamp);

  bool initInfiniteRay(const Vec3r &orig, const Vec3r &dir, uint 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 = nullptr;
    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);
 
  uint _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
 
  MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:Grid")
};
 
//
// 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;
 
  MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:VirtualOccludersSet")
};
 
} /* namespace Freestyle */