Blender  V3.3
BoxGrid.h
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
3 #pragma once
4 
10 #define BOX_GRID_LOGGING 0
11 
12 // I would like to avoid using deque because including ViewMap.h and <deque> or <vector>
13 // separately results in redefinitions of identifiers. ViewMap.h already includes <vector>
14 // so it should be a 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 
38 class BoxGrid {
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:BoxGrid: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:
76  /* Iterator needs to allow the user to avoid full 3D comparison in two cases:
77  *
78  * (1) Where (*current)->deepest < target[2], where the occluder is unambiguously in front of the
79  * target point.
80  *
81  * (2) Where (*current)->shallowest > target[2], where the occluder is unambiguously in back of
82  * the target point.
83  *
84  * In addition, when used by OptimizedFindOccludee, Iterator should stop iterating as soon as it
85  * has an occludee candidate and (*current)->shallowest > candidate[2], because at that point
86  * forward no new occluder could possibly be a better occludee.
87  */
88  class Iterator {
89  public:
90  // epsilon is not used in this class, but other grids with the same interface may need an
91  // epsilon
92  explicit Iterator(BoxGrid &grid, Vec3r &center, real epsilon = 1.0e-06);
93  void initBeforeTarget();
94  void initAfterTarget();
95  void nextOccluder();
96  void nextOccludee();
97  bool validBeforeTarget();
98  bool validAfterTarget();
99  WFace *getWFace() const;
101  void reportDepth(Vec3r origin, Vec3r u, real t);
102 
103  private:
104  bool testOccluder(bool wantOccludee);
105  void markCurrentOccludeeCandidate(real depth);
106 
107  Cell *_cell;
108  Vec3r _target;
109  bool _foundOccludee;
110  real _occludeeDepth;
111  // deque<OccluderData*>::iterator _current, _occludeeCandidate;
112  vector<OccluderData *>::iterator _current, _occludeeCandidate;
113 
114 #ifdef WITH_CXX_GUARDEDALLOC
115  MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:BoxGrid:Iterator")
116 #endif
117  };
118 
120  public:
121  explicit Transform() = default;
122  explicit Transform(Transform &other);
123  Vec3r operator()(const Vec3r &point) const;
124  };
125 
126  private:
127  // Prevent implicit copies and assignments.
128  BoxGrid(const BoxGrid &other);
129  BoxGrid &operator=(const BoxGrid &other);
130 
131  public:
132  explicit BoxGrid(OccluderSource &source,
134  ViewMap *viewMap,
135  Vec3r &viewpoint,
136  bool enableQI);
137  virtual ~BoxGrid();
138 
139  // Generate Cell structure
141  // Fill Cells
142  void distributePolygons(OccluderSource &source);
143  // Insert one polygon into each matching cell, return true if any cell consumes the polygon
144  bool insertOccluder(OccluderSource &source, OccluderData *&occluder);
145  // Sort occluders in each cell
146  void reorganizeCells();
147 
148  Cell *findCell(const Vec3r &point);
149 
150  // Accessors:
151  bool orthographicProjection() const;
152  const Vec3r &viewpoint() const;
153  bool enableQI() const;
155 
156  private:
157  void getCellCoordinates(const Vec3r &point, unsigned &x, unsigned &y);
158 
160  // typedef PointerSequence<deque<OccluderData*>, OccluderData*> occluderContainer;
162  unsigned _cellsX, _cellsY;
163  float _cellSize;
164  float _cellOrigin[2];
165  cellContainer _cells;
166  occluderContainer _faces;
167  Vec3r _viewpoint;
168  bool _enableQI;
169 
170 #ifdef WITH_CXX_GUARDEDALLOC
171  MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:BoxGrid")
172 #endif
173 };
174 
176 {
177  _current = _cell->faces.begin();
178  while (_current != _cell->faces.end() && !testOccluder(false)) {
179  ++_current;
180  }
181 }
182 
184 {
185  if (_foundOccludee) {
186 #if BOX_GRID_LOGGING
187  if (G.debug & G_DEBUG_FREESTYLE) {
188  std::cout << "\tStarting occludee search from occludeeCandidate at depth " << _occludeeDepth
189  << std::endl;
190  }
191 #endif
192  _current = _occludeeCandidate;
193  return;
194  }
195 
196 #if BOX_GRID_LOGGING
197  if (G.debug & G_DEBUG_FREESTYLE) {
198  std::cout << "\tStarting occludee search from current position" << std::endl;
199  }
200 #endif
201 
202  while (_current != _cell->faces.end() && !testOccluder(true)) {
203  ++_current;
204  }
205 }
206 
207 inline bool BoxGrid::Iterator::testOccluder(bool wantOccludee)
208 {
209  // End-of-list is not even a valid iterator position
210  if (_current == _cell->faces.end()) {
211  // Returning true seems strange, but it will break us out of whatever loop is calling
212  // testOccluder, and _current = _cell->face.end() will make the calling routine give up.
213  return true;
214  }
215 #if BOX_GRID_LOGGING
216  if (G.debug & G_DEBUG_FREESTYLE) {
217  std::cout << "\tTesting occluder " << (*_current)->poly.getVertices()[0];
218  for (unsigned int i = 1; i < (*_current)->poly.getVertices().size(); ++i) {
219  std::cout << ", " << (*_current)->poly.getVertices()[i];
220  }
221  std::cout << " from shape " << (*_current)->face->GetVertex(0)->shape()->GetId() << std::endl;
222  }
223 #endif
224 
225  // If we have an occluder candidate and we are unambiguously after it, abort
226  if (_foundOccludee && (*_current)->shallowest > _occludeeDepth) {
227 #if BOX_GRID_LOGGING
228  if (G.debug & G_DEBUG_FREESTYLE) {
229  std::cout << "\t\tAborting: shallowest > occludeeCandidate->deepest" << std::endl;
230  }
231 #endif
232  _current = _cell->faces.end();
233 
234  // See note above
235  return true;
236  }
237 
238  // Specific continue or stop conditions when searching for each type
239  if (wantOccludee) {
240  if ((*_current)->deepest < _target[2]) {
241 #if BOX_GRID_LOGGING
242  if (G.debug & G_DEBUG_FREESTYLE) {
243  std::cout << "\t\tSkipping: shallower than target while looking for occludee" << std::endl;
244  }
245 #endif
246  return false;
247  }
248  }
249  else {
250  if ((*_current)->shallowest > _target[2]) {
251 #if BOX_GRID_LOGGING
252  if (G.debug & G_DEBUG_FREESTYLE) {
253  std::cout << "\t\tStopping: deeper than target while looking for occluder" << std::endl;
254  }
255 #endif
256  return true;
257  }
258  }
259 
260  // Depthwise, this is a valid occluder.
261 
262  // Check to see if target is in the 2D bounding box
263  Vec3r bbMin, bbMax;
264  (*_current)->poly.getBBox(bbMin, bbMax);
265  if (_target[0] < bbMin[0] || _target[0] > bbMax[0] || _target[1] < bbMin[1] ||
266  _target[1] > bbMax[1]) {
267 #if BOX_GRID_LOGGING
268  if (G.debug & G_DEBUG_FREESTYLE) {
269  std::cout << "\t\tSkipping: bounding box violation" << std::endl;
270  }
271 #endif
272  return false;
273  }
274 
275  // We've done all the corner cutting we can.
276  // Let the caller work out whether or not the geometry is correct.
277  return true;
278 }
279 
281 {
282  // The reported depth is the length of a ray in camera space
283  // We need to convert it into a Z-value in grid space
284  real depth = -(origin + (u * t))[2];
285 #if BOX_GRID_LOGGING
286  if (G.debug & G_DEBUG_FREESTYLE) {
287  std::cout << "\t\tReporting depth of occluder/ee: " << depth;
288  }
289 #endif
290  if (depth > _target[2]) {
291 #if BOX_GRID_LOGGING
292  if (G.debug & G_DEBUG_FREESTYLE) {
293  std::cout << " is deeper than target" << std::endl;
294  }
295 #endif
296  // If the current occluder is the best occludee so far, save it.
297  if (!_foundOccludee || _occludeeDepth > depth) {
298  markCurrentOccludeeCandidate(depth);
299  }
300  }
301  else {
302 #if BOX_GRID_LOGGING
303  if (G.debug & G_DEBUG_FREESTYLE) {
304  std::cout << std::endl;
305  }
306 #endif
307  }
308 }
309 
311 {
312  if (_current != _cell->faces.end()) {
313  do {
314  ++_current;
315  } while (_current != _cell->faces.end() && !testOccluder(false));
316  }
317 }
318 
320 {
321  if (_current != _cell->faces.end()) {
322  do {
323  ++_current;
324  } while (_current != _cell->faces.end() && !testOccluder(true));
325  }
326 }
327 
329 {
330  return _current != _cell->faces.end() && (*_current)->shallowest <= _target[2];
331 }
332 
334 {
335  return _current != _cell->faces.end();
336 }
337 
338 inline void BoxGrid::Iterator::markCurrentOccludeeCandidate(real depth)
339 {
340 #if BOX_GRID_LOGGING
341  if (G.debug & G_DEBUG_FREESTYLE) {
342  std::cout << "\t\tFound occludeeCandidate at depth " << depth << std::endl;
343  }
344 #endif
345  _occludeeCandidate = _current;
346  _occludeeDepth = depth;
347  _foundOccludee = true;
348 }
349 
351 {
352  return (*_current)->face;
353 }
354 
356 {
357  return &((*_current)->cameraSpacePolygon);
358 }
359 
361  : poly(p), cameraSpacePolygon(source.getCameraSpacePolygon()), face(source.getWFace())
362 {
363  // Set shallowest and deepest based on bbox
364  Vec3r min, max;
365  poly.getBBox(min, max);
366  shallowest = min[2];
367  deepest = max[2];
368 }
369 
370 inline void BoxGrid::Cell::checkAndInsert(OccluderSource &source,
371  Polygon3r &poly,
372  OccluderData *&occluder)
373 {
374  if (GridHelpers::insideProscenium(boundary, poly)) {
375  if (occluder == NULL) {
376  // Disposal of occluder will be handled in BoxGrid::distributePolygons(),
377  // or automatically by BoxGrid::_faces;
378  occluder = new OccluderData(source, poly);
379  }
380  faces.push_back(occluder);
381  }
382 }
383 
384 inline bool BoxGrid::insertOccluder(OccluderSource &source, OccluderData *&occluder)
385 {
386  Polygon3r &poly(source.getGridSpacePolygon());
387  occluder = NULL;
388 
389  Vec3r bbMin, bbMax;
390  poly.getBBox(bbMin, bbMax);
391  // Check overlapping cells
392  unsigned startX, startY, endX, endY;
393  getCellCoordinates(bbMin, startX, startY);
394  getCellCoordinates(bbMax, endX, endY);
395 
396  for (unsigned int i = startX; i <= endX; ++i) {
397  for (unsigned int j = startY; j <= endY; ++j) {
398  if (_cells[i * _cellsY + j] != NULL) {
399  _cells[i * _cellsY + j]->checkAndInsert(source, poly, occluder);
400  }
401  }
402  }
403 
404  return occluder != NULL;
405 }
406 
407 } /* 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
Polygon3r * getCameraSpacePolygon()
Definition: BoxGrid.h:355
Iterator(BoxGrid &grid, Vec3r &center, real epsilon=1.0e-06)
Definition: BoxGrid.cpp:51
void reportDepth(Vec3r origin, Vec3r u, real t)
Definition: BoxGrid.h:280
WFace * getWFace() const
Definition: BoxGrid.h:350
Vec3r operator()(const Vec3r &point) const
Definition: BoxGrid.cpp:217
Transform(Transform &other)
Transform transform
Definition: BoxGrid.h:154
void assignCells(OccluderSource &source, GridDensityProvider &density, ViewMap *viewMap)
Definition: BoxGrid.cpp:103
const Vec3r & viewpoint() const
Definition: BoxGrid.cpp:207
void reorganizeCells()
Definition: BoxGrid.cpp:179
Cell * findCell(const Vec3r &point)
Definition: BoxGrid.cpp:195
bool enableQI() const
Definition: BoxGrid.cpp:212
void distributePolygons(OccluderSource &source)
Definition: BoxGrid.cpp:150
bool insertOccluder(OccluderSource &source, OccluderData *&occluder)
Definition: BoxGrid.h:384
bool orthographicProjection() const
Definition: BoxGrid.cpp:202
void getBBox(Point &min, Point &max) const
Definition: Polygon.h:72
Polygon3r & getGridSpacePolygon()
static char faces[256]
#define G(x, y, z)
VecMat::Vec3< real > Vec3r
Definition: Geom.h:28
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)
#define min(a, b)
Definition: sort.c:35
OccluderData(OccluderSource &source, Polygon3r &p)
Definition: BoxGrid.h:360
float max