Blender  V3.3
SphericalGrid.h
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
3 #pragma once
4 
10 #define SPHERICAL_GRID_LOGGING 0
11 
12 // I would like to avoid using deque because including ViewMap.h and <deque> or <vector> separately
13 // results in redefinitions of identifiers. ViewMap.h already includes <vector> so it should be a
14 // safe fall-back.
15 //#include <vector>
16 //#include <deque>
17 
18 #include "GridDensityProvider.h"
19 #include "OccluderSource.h"
20 #include "ViewMap.h"
21 
22 #include "../geometry/BBox.h"
23 #include "../geometry/GridHelpers.h"
24 #include "../geometry/Polygon.h"
25 
26 #include "../system/PointerSequence.h"
27 
28 #include "../winged_edge/WEdge.h"
29 
30 #include "BKE_global.h"
31 
32 #ifdef WITH_CXX_GUARDEDALLOC
33 # include "MEM_guardedalloc.h"
34 #endif
35 
36 namespace Freestyle {
37 
39  public:
40  // Helper classes
41  struct OccluderData {
42  explicit OccluderData(OccluderSource &source, Polygon3r &p);
46  // N.B. We could, of course, store face in poly's userdata member, like the old ViewMapBuilder
47  // code does. However, code comments make it clear that userdata is deprecated, so we avoid the
48  // temptation to save 4 or 8 bytes.
50 
51 #ifdef WITH_CXX_GUARDEDALLOC
52  MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:SphericalGrid:OccluderData")
53 #endif
54  };
55 
56  private:
57  struct Cell {
58  // Can't store Cell in a vector without copy and assign
59  // Cell(const Cell& other);
60  // Cell& operator=(const Cell& other);
61 
62  explicit Cell() = default;
63 
64  static bool compareOccludersByShallowestPoint(const OccluderData *a, const OccluderData *b);
65 
66  void setDimensions(real x, real y, real sizeX, real sizeY);
67  void checkAndInsert(OccluderSource &source, Polygon3r &poly, OccluderData *&occluder);
68  void indexPolygons();
69 
70  real boundary[4];
71  // deque<OccluderData*> faces;
72  vector<OccluderData *> faces;
73  };
74 
75  public:
89  class Iterator {
90  public:
91  // epsilon is not used in this class, but other grids with the same interface may need an
92  // epsilon
93  explicit Iterator(SphericalGrid &grid, Vec3r &center, real epsilon = 1.0e-06);
94  void initBeforeTarget();
95  void initAfterTarget();
96  void nextOccluder();
97  void nextOccludee();
98  bool validBeforeTarget();
99  bool validAfterTarget();
100  WFace *getWFace() const;
102  void reportDepth(Vec3r origin, Vec3r u, real t);
103 
104  private:
105  bool testOccluder(bool wantOccludee);
106  void markCurrentOccludeeCandidate(real depth);
107 
108  Cell *_cell;
109  Vec3r _target;
110  bool _foundOccludee;
111  real _occludeeDepth;
112  // deque<OccluderData*>::iterator _current, _occludeeCandidate;
113  vector<OccluderData *>::iterator _current, _occludeeCandidate;
114 
115 #ifdef WITH_CXX_GUARDEDALLOC
116  MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:SphericalGrid:Iterator")
117 #endif
118  };
119 
121  public:
122  explicit Transform() = default;
123  explicit Transform(Transform &other);
124  Vec3r operator()(const Vec3r &point) const;
125  static Vec3r sphericalProjection(const Vec3r &M);
126  };
127 
128  private:
129  // Prevent implicit copies and assignments.
130  SphericalGrid(const SphericalGrid &other);
131  SphericalGrid &operator=(const SphericalGrid &other);
132 
133  public:
134  explicit SphericalGrid(OccluderSource &source,
136  ViewMap *viewMap,
137  Vec3r &viewpoint,
138  bool enableQI);
139  virtual ~SphericalGrid();
140 
141  // Generate Cell structure
143  // Fill Cells
144  void distributePolygons(OccluderSource &source);
145  // Insert one polygon into each matching cell, return true if any cell consumes the polygon
146  bool insertOccluder(OccluderSource &source, OccluderData *&occluder);
147  // Sort occluders in each cell
148  void reorganizeCells();
149 
150  Cell *findCell(const Vec3r &point);
151 
152  // Accessors:
153  bool orthographicProjection() const;
154  const Vec3r &viewpoint() const;
155  bool enableQI() const;
156 
157  private:
158  void getCellCoordinates(const Vec3r &point, unsigned &x, unsigned &y);
159 
161  // typedef PointerSequence<deque<OccluderData*>, OccluderData*> occluderContainer;
163  unsigned _cellsX, _cellsY;
164  float _cellSize;
165  float _cellOrigin[2];
166  cellContainer _cells;
167  occluderContainer _faces;
168  Vec3r _viewpoint;
169  bool _enableQI;
170 
171 #ifdef WITH_CXX_GUARDEDALLOC
172  MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:SphericalGrid")
173 #endif
174 };
175 
177 {
178  _current = _cell->faces.begin();
179  while (_current != _cell->faces.end() && !testOccluder(false)) {
180  ++_current;
181  }
182 }
183 
185 {
186  if (_foundOccludee) {
187 #if SPHERICAL_GRID_LOGGING
188  if (G.debug & G_DEBUG_FREESTYLE) {
189  std::cout << "\tStarting occludee search from occludeeCandidate at depth " << _occludeeDepth
190  << std::endl;
191  }
192 #endif
193  _current = _occludeeCandidate;
194  return;
195  }
196 
197 #if SPHERICAL_GRID_LOGGING
198  if (G.debug & G_DEBUG_FREESTYLE) {
199  std::cout << "\tStarting occludee search from current position" << std::endl;
200  }
201 #endif
202 
203  while (_current != _cell->faces.end() && !testOccluder(true)) {
204  ++_current;
205  }
206 }
207 
208 inline bool SphericalGrid::Iterator::testOccluder(bool wantOccludee)
209 {
210  // End-of-list is not even a valid iterator position
211  if (_current == _cell->faces.end()) {
212  // Returning true seems strange, but it will break us out of whatever loop is calling
213  // testOccluder, and _current=_cell->face.end() will make the calling routine give up.
214  return true;
215  }
216 #if SPHERICAL_GRID_LOGGING
217  if (G.debug & G_DEBUG_FREESTYLE) {
218  std::cout << "\tTesting occluder " << (*_current)->poly.getVertices()[0];
219  for (unsigned int i = 1; i < (*_current)->poly.getVertices().size(); ++i) {
220  std::cout << ", " << (*_current)->poly.getVertices()[i];
221  }
222  std::cout << " from shape " << (*_current)->face->GetVertex(0)->shape()->GetId() << std::endl;
223  }
224 #endif
225 
226  // If we have an occluder candidate and we are unambiguously after it, abort
227  if (_foundOccludee && (*_current)->shallowest > _occludeeDepth) {
228 #if SPHERICAL_GRID_LOGGING
229  if (G.debug & G_DEBUG_FREESTYLE) {
230  std::cout << "\t\tAborting: shallowest > occludeeCandidate->deepest" << std::endl;
231  }
232 #endif
233  _current = _cell->faces.end();
234 
235  // See note above
236  return true;
237  }
238 
239  // Specific continue or stop conditions when searching for each type
240  if (wantOccludee) {
241  if ((*_current)->deepest < _target[2]) {
242 #if SPHERICAL_GRID_LOGGING
243  if (G.debug & G_DEBUG_FREESTYLE) {
244  std::cout << "\t\tSkipping: shallower than target while looking for occludee" << std::endl;
245  }
246 #endif
247  return false;
248  }
249  }
250  else {
251  if ((*_current)->shallowest > _target[2]) {
252 #if SPHERICAL_GRID_LOGGING
253  if (G.debug & G_DEBUG_FREESTYLE) {
254  std::cout << "\t\tStopping: deeper than target while looking for occluder" << std::endl;
255  }
256 #endif
257  return true;
258  }
259  }
260 
261  // Depthwise, this is a valid occluder.
262 
263  // Check to see if target is in the 2D bounding box
264  Vec3r bbMin, bbMax;
265  (*_current)->poly.getBBox(bbMin, bbMax);
266  if (_target[0] < bbMin[0] || _target[0] > bbMax[0] || _target[1] < bbMin[1] ||
267  _target[1] > bbMax[1]) {
268 #if SPHERICAL_GRID_LOGGING
269  if (G.debug & G_DEBUG_FREESTYLE) {
270  std::cout << "\t\tSkipping: bounding box violation" << std::endl;
271  }
272 #endif
273  return false;
274  }
275 
276  // We've done all the corner cutting we can. Let the caller work out whether or not the geometry
277  // is correct.
278  return true;
279 }
280 
282 {
283  // The reported depth is the length of a ray in camera space. We need to convert it into the
284  // distance from viewpoint If origin is the viewpoint, depth == t. A future optimization could
285  // allow the caller to tell us if origin is viewponit or target, at the cost of changing the
286  // OptimizedGrid API.
287  real depth = (origin + u * t).norm();
288 #if SPHERICAL_GRID_LOGGING
289  if (G.debug & G_DEBUG_FREESTYLE) {
290  std::cout << "\t\tReporting depth of occluder/ee: " << depth;
291  }
292 #endif
293  if (depth > _target[2]) {
294 #if SPHERICAL_GRID_LOGGING
295  if (G.debug & G_DEBUG_FREESTYLE) {
296  std::cout << " is deeper than target" << std::endl;
297  }
298 #endif
299  // If the current occluder is the best occludee so far, save it.
300  if (!_foundOccludee || _occludeeDepth > depth) {
301  markCurrentOccludeeCandidate(depth);
302  }
303  }
304  else {
305 #if SPHERICAL_GRID_LOGGING
306  if (G.debug & G_DEBUG_FREESTYLE) {
307  std::cout << std::endl;
308  }
309 #endif
310  }
311 }
312 
314 {
315  if (_current != _cell->faces.end()) {
316  do {
317  ++_current;
318  } while (_current != _cell->faces.end() && !testOccluder(false));
319  }
320 }
321 
323 {
324  if (_current != _cell->faces.end()) {
325  do {
326  ++_current;
327  } while (_current != _cell->faces.end() && !testOccluder(true));
328  }
329 }
330 
332 {
333  return _current != _cell->faces.end() && (*_current)->shallowest <= _target[2];
334 }
335 
337 {
338  return _current != _cell->faces.end();
339 }
340 
341 inline void SphericalGrid::Iterator::markCurrentOccludeeCandidate(real depth)
342 {
343 #if SPHERICAL_GRID_LOGGING
344  if (G.debug & G_DEBUG_FREESTYLE) {
345  std::cout << "\t\tFound occludeeCandidate at depth " << depth << std::endl;
346  }
347 #endif
348  _occludeeCandidate = _current;
349  _occludeeDepth = depth;
350  _foundOccludee = true;
351 }
352 
354 {
355  return (*_current)->face;
356 }
357 
359 {
360  return &((*_current)->cameraSpacePolygon);
361 }
362 
364  : poly(p), cameraSpacePolygon(source.getCameraSpacePolygon()), face(source.getWFace())
365 {
366  const Vec3r viewpoint(0, 0, 0);
367  // Get the point on the camera-space polygon that is closest to the viewpoint
368  // shallowest is the distance from the viewpoint to that point
370 
371  // Get the point on the camera-space polygon that is furthest from the viewpoint
372  // deepest is the distance from the viewpoint to that point
373  deepest = cameraSpacePolygon.getVertices()[2].norm();
374  for (unsigned int i = 0; i < 2; ++i) {
375  real t = cameraSpacePolygon.getVertices()[i].norm();
376  if (t > deepest) {
377  deepest = t;
378  }
379  }
380 }
381 
382 inline void SphericalGrid::Cell::checkAndInsert(OccluderSource &source,
383  Polygon3r &poly,
384  OccluderData *&occluder)
385 {
386  if (GridHelpers::insideProscenium(boundary, poly)) {
387  if (occluder == NULL) {
388  // Disposal of occluder will be handled in SphericalGrid::distributePolygons(),
389  // or automatically by SphericalGrid::_faces;
390  occluder = new OccluderData(source, poly);
391  }
392  faces.push_back(occluder);
393  }
394 }
395 
397 {
398  Polygon3r &poly(source.getGridSpacePolygon());
399  occluder = NULL;
400 
401  Vec3r bbMin, bbMax;
402  poly.getBBox(bbMin, bbMax);
403  // Check overlapping cells
404  unsigned startX, startY, endX, endY;
405  getCellCoordinates(bbMin, startX, startY);
406  getCellCoordinates(bbMax, endX, endY);
407 
408  for (unsigned int i = startX; i <= endX; ++i) {
409  for (unsigned int j = startY; j <= endY; ++j) {
410  if (_cells[i * _cellsY + j] != NULL) {
411  _cells[i * _cellsY + j]->checkAndInsert(source, poly, occluder);
412  }
413  }
414  }
415 
416  return occluder != NULL;
417 }
418 
419 } /* namespace Freestyle */
@ G_DEBUG_FREESTYLE
Definition: BKE_global.h:181
NSNotificationCenter * center
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint y
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble u2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLdouble GLdouble v2 _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLdouble GLdouble nz _GL_VOID_RET _GL_VOID GLfloat GLfloat nz _GL_VOID_RET _GL_VOID GLint GLint nz _GL_VOID_RET _GL_VOID GLshort GLshort nz _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const GLfloat *values _GL_VOID_RET _GL_VOID GLsizei const GLushort *values _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID const GLuint const GLclampf *priorities _GL_VOID_RET _GL_VOID GLdouble y _GL_VOID_RET _GL_VOID GLfloat y _GL_VOID_RET _GL_VOID GLint y _GL_VOID_RET _GL_VOID GLshort y _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLfloat GLfloat z _GL_VOID_RET _GL_VOID GLint GLint z _GL_VOID_RET _GL_VOID GLshort GLshort z _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble w _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat w _GL_VOID_RET _GL_VOID GLint GLint GLint w _GL_VOID_RET _GL_VOID GLshort GLshort GLshort w _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble y2 _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat y2 _GL_VOID_RET _GL_VOID GLint GLint GLint y2 _GL_VOID_RET _GL_VOID GLshort GLshort GLshort y2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLuint *buffer _GL_VOID_RET _GL_VOID GLdouble t _GL_VOID_RET _GL_VOID GLfloat t _GL_VOID_RET _GL_VOID GLint t _GL_VOID_RET _GL_VOID GLshort t _GL_VOID_RET _GL_VOID GLdouble t
Class to define a cell grid surrounding the projected image of a scene.
Read Guarded memory(de)allocation.
in reality light always falls off quadratically Particle Retrieve the data of the particle that spawned the object for example to give variation to multiple instances of an object Point Retrieve information about points in a point cloud Retrieve the edges of an object as it appears to Cycles topology will always appear triangulated Convert a blackbody temperature to an RGB value Normal Generate a perturbed normal from an RGB normal map image Typically used for faking highly detailed surfaces Generate an OSL shader from a file or text data block Image Sample an image file as a texture Sky Generate a procedural sky texture Noise Generate fractal Perlin noise Wave Generate procedural bands or rings with noise Voronoi Generate Worley noise based on the distance to random points Typically used to generate textures such as or biological cells Brick Generate a procedural texture producing bricks Texture Retrieve multiple types of texture coordinates nTypically used as inputs for texture nodes Vector Convert a point
Class to define a cell grid surrounding the projected image of a scene.
Classes to define a View Map (ViewVertex, ViewEdge, etc.)
static DBVT_INLINE btScalar size(const btDbvtVolume &a)
Definition: btDbvt.cpp:52
SIMD_FORCE_INLINE btScalar norm() const
Return the norm (length) of the vector.
Definition: btVector3.h:263
const vector< Point > & getVertices() const
Definition: Polygon.h:67
void getBBox(Point &min, Point &max) const
Definition: Polygon.h:72
Polygon3r & getGridSpacePolygon()
void reportDepth(Vec3r origin, Vec3r u, real t)
Iterator(SphericalGrid &grid, Vec3r &center, real epsilon=1.0e-06)
static Vec3r sphericalProjection(const Vec3r &M)
Vec3r operator()(const Vec3r &point) const
void assignCells(OccluderSource &source, GridDensityProvider &density, ViewMap *viewMap)
const Vec3r & viewpoint() const
bool orthographicProjection() const
Cell * findCell(const Vec3r &point)
void distributePolygons(OccluderSource &source)
bool insertOccluder(OccluderSource &source, OccluderData *&occluder)
#define M
static char faces[256]
#define G(x, y, z)
VecMat::Vec3< real > Vec3r
Definition: Geom.h:28
real distancePointToPolygon(const Vec3r &point, const Polygon3r &poly)
Definition: GridHelpers.h:81
bool insideProscenium(const real proscenium[4], const Polygon3r &polygon)
Definition: GridHelpers.h:112
inherits from class Rep
Definition: AppCanvas.cpp:18
static unsigned x[3]
Definition: RandGen.cpp:73
static unsigned a[3]
Definition: RandGen.cpp:78
double real
Definition: Precision.h:12
static double epsilon
static const pxr::TfToken b("b", pxr::TfToken::Immortal)
static const pxr::TfToken density("density", pxr::TfToken::Immortal)
OccluderData(OccluderSource &source, Polygon3r &p)