Blender  V3.3
Grid.h
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
3 #pragma once
4 
10 #include <cstring> // for memset
11 #include <float.h>
12 #include <stdint.h> // For POINTER_FROM_UINT, i.e. uintptr_t.
13 #include <vector>
14 
15 #include "Geom.h"
16 #include "GeomUtils.h"
17 #include "Polygon.h"
18 
19 #include "../system/FreestyleConfig.h"
20 
21 #include "BLI_utildefines.h"
22 
23 #ifdef WITH_CXX_GUARDEDALLOC
24 # include "MEM_guardedalloc.h"
25 #endif
26 
27 using namespace std;
28 
29 namespace Freestyle {
30 
31 using namespace Geometry;
32 
33 typedef vector<Polygon3r *> OccludersSet;
34 
35 //
36 // Class to define cells used by the regular grid
37 //
39 
40 class Cell {
41  public:
42  Cell(Vec3r &orig)
43  {
44  _orig = orig;
45  }
46 
47  virtual ~Cell()
48  {
49  }
50 
51  inline void addOccluder(Polygon3r *o)
52  {
53  if (o) {
54  _occluders.push_back(o);
55  }
56  }
57 
58  inline const Vec3r &getOrigin()
59  {
60  return _orig;
61  }
62 
64  {
65  return _occluders;
66  }
67 
68  private:
69  Vec3r _orig;
70  OccludersSet _occluders;
71 
72 #ifdef WITH_CXX_GUARDEDALLOC
73  MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:Cell")
74 #endif
75 };
76 
77 class GridVisitor {
78  public:
79  virtual ~GridVisitor(){}; // soc
80 
81  virtual void discoverCell(Cell * /*cell*/)
82  {
83  }
84 
85  virtual void examineOccluder(Polygon3r * /*occ*/)
86  {
87  }
88 
89  virtual void finishCell(Cell * /*cell*/)
90  {
91  }
92 
93  virtual bool stop()
94  {
95  return false;
96  }
97 
98 #ifdef WITH_CXX_GUARDEDALLOC
99  MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:GridVisitor")
100 #endif
101 };
102 
105  public:
106  allOccludersGridVisitor(OccludersSet &occluders) : GridVisitor(), occluders_(occluders)
107  {
108  }
109 
110  virtual void examineOccluder(Polygon3r *occ);
111 
113  {
114  return occluders_;
115  }
116 
117  void clear()
118  {
119  occluders_.clear();
120  }
121 
122  private:
123  OccludersSet &occluders_;
124 };
125 
130  // soc - changed order to remove warnings
131  public:
132  double u_, v_, t_;
133 
134  private:
135  Polygon3r *occluder_;
136  Vec3r ray_org_, ray_dir_, cell_size_;
137  Cell *current_cell_;
138 
139  public:
140  firstIntersectionGridVisitor(const Vec3r &ray_org, const Vec3r &ray_dir, const Vec3r &cell_size)
141  : GridVisitor(),
142  u_(0),
143  v_(0),
144  t_(DBL_MAX),
145  occluder_(0),
146  ray_org_(ray_org),
147  ray_dir_(ray_dir),
148  cell_size_(cell_size),
149  current_cell_(0)
150  {
151  }
152 
154  {
155  }
156 
157  virtual void discoverCell(Cell *cell)
158  {
159  current_cell_ = cell;
160  }
161 
162  virtual void examineOccluder(Polygon3r *occ);
163 
164  virtual bool stop();
165 
167  {
168  return occluder_;
169  }
170 };
171 
172 //
173 // Class to define a regular grid used for ray casting computations
174 //
176 
177 class Grid {
178  public:
181  {
182  }
183 
184  virtual ~Grid()
185  {
186  clear();
187  }
188 
192  virtual void clear();
193 
202  virtual void configure(const Vec3r &orig, const Vec3r &size, unsigned nb);
203 
209  inline void getCellCoordinates(const Vec3r &p, Vec3u &res)
210  {
211  int tmp;
212  for (int i = 0; i < 3; i++) {
213  tmp = (int)((p[i] - _orig[i]) / _cell_size[i]);
214  if (tmp < 0) {
215  res[i] = 0;
216  }
217  else if ((unsigned int)tmp >= _cells_nb[i]) {
218  res[i] = _cells_nb[i] - 1;
219  }
220  else {
221  res[i] = tmp;
222  }
223  }
224  }
225 
227  virtual void fillCell(const Vec3u &coord, Cell &cell) = 0;
228 
230  virtual Cell *getCell(const Vec3u &coord) = 0;
231 
237  inline Cell *getCell(const Vec3r &p)
238  {
239  Vec3u coord;
240  getCellCoordinates(p, coord);
241  return getCell(coord);
242  }
243 
251  inline void getCellOrigin(const Vec3u &cell_coord, Vec3r &orig)
252  {
253  for (unsigned int i = 0; i < 3; i++) {
254  orig[i] = _orig[i] + cell_coord[i] * _cell_size[i];
255  }
256  }
257 
266  inline void getCellBox(const Vec3u &cell_coord, Vec3r &min_out, Vec3r &max_out)
267  {
268  getCellOrigin(cell_coord, min_out);
269  max_out = min_out + _cell_size;
270  }
271 
276  void insertOccluder(Polygon3r *occluder);
277 
279  void addOccluder(Polygon3r *occluder)
280  {
281  _occluders.push_back(occluder);
282  }
283 
288  void castRay(const Vec3r &orig, const Vec3r &end, OccludersSet &occluders, unsigned timestamp);
289 
290  // Prepares to cast ray without generating OccludersSet
291  void initAcceleratedRay(const Vec3r &orig, const Vec3r &end, unsigned timestamp);
292 
297  void castInfiniteRay(const Vec3r &orig,
298  const Vec3r &dir,
299  OccludersSet &occluders,
300  unsigned timestamp);
301 
302  // Prepares to cast ray without generating OccludersSet.
303  bool initAcceleratedInfiniteRay(const Vec3r &orig, const Vec3r &dir, unsigned timestamp);
304 
309  Polygon3r *castRayToFindFirstIntersection(
310  const Vec3r &orig, const Vec3r &dir, double &t, double &u, double &v, unsigned timestamp);
311 
313  void initRay(const Vec3r &orig, const Vec3r &end, unsigned timestamp);
314 
318  bool initInfiniteRay(const Vec3r &orig, const Vec3r &dir, unsigned timestamp);
319 
321  inline const Vec3r &getOrigin() const
322  {
323  return _orig;
324  }
325 
326  inline Vec3r gridSize() const
327  {
328  return _size;
329  }
330 
331  inline Vec3r getCellSize() const
332  {
333  return _cell_size;
334  }
335 
336  // ARB profiling only:
338  {
339  return &_occluders;
340  }
341 
343  {
344  cerr << "Cells nb : " << _cells_nb << endl;
345  cerr << "Cell size : " << _cell_size << endl;
346  cerr << "Origin : " << _orig << endl;
347  cerr << "Occluders nb : " << _occluders.size() << endl;
348  }
349 
350  protected:
352  inline void castRayInternal(GridVisitor &visitor)
353  {
354  Cell *current_cell = NULL;
355  do {
356  current_cell = getCell(_current_cell);
357  if (current_cell) {
358  visitor.discoverCell(current_cell);
359  OccludersSet &occluders =
360  current_cell->getOccluders(); // FIXME: I had forgotten the ref &
361  for (OccludersSet::iterator it = occluders.begin(); it != occluders.end(); it++) {
362  if (POINTER_AS_UINT((*it)->userdata2) != _timestamp) {
363  (*it)->userdata2 = POINTER_FROM_UINT(_timestamp);
364  visitor.examineOccluder(*it);
365  }
366  }
367  visitor.finishCell(current_cell);
368  }
369  } while ((!visitor.stop()) && (nextRayCell(_current_cell, _current_cell)));
370  }
371 
373  bool nextRayCell(Vec3u &current_cell, Vec3u &next_cell);
374 
375  unsigned int _timestamp;
376 
377  Vec3u _cells_nb; // number of cells for x,y,z axis
378  Vec3r _cell_size; // cell x,y,z dimensions
379  Vec3r _size; // grid x,y,x dimensions
380  Vec3r _orig; // grid origin
381 
382  Vec3r _ray_dir; // direction vector for the ray
383  Vec3u _current_cell; // The current cell being processed (designated by its 3 coordinates)
384  Vec3r _pt; // Points corresponding to the incoming and outgoing intersections of one cell with
385  // the ray
386  real _t_end; // To know when we are at the end of the ray
388 
389  // OccludersSet _ray_occluders; // Set storing the occluders contained in the cells traversed by
390  // a ray
391  OccludersSet _occluders; // List of all occluders inserted in the grid
392 
393 #ifdef WITH_CXX_GUARDEDALLOC
394  MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:Grid")
395 #endif
396 };
397 
398 //
399 // Class to walk through occluders in grid without building intermediate data structures
400 //
402 
404  public:
405  VirtualOccludersSet(Grid &_grid) : grid(_grid){};
408  Polygon3r *next(bool stopOnNewCell);
409 
410  private:
411  Polygon3r *firstOccluderFromNextCell();
412  Grid &grid;
413  OccludersSet::iterator it, end;
414 
415 #ifdef WITH_CXX_GUARDEDALLOC
416  MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:VirtualOccludersSet")
417 #endif
418 };
419 
420 } /* namespace Freestyle */
#define POINTER_AS_UINT(i)
#define POINTER_FROM_UINT(i)
_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
Various tools for geometry.
Vectors and Matrices (useful type definitions)
Read Guarded memory(de)allocation.
Class to define a polygon.
ATTR_WARN_UNUSED_RESULT const BMVert * v
static DBVT_INLINE btScalar size(const btDbvtVolume &a)
Definition: btDbvt.cpp:52
void addOccluder(Polygon3r *o)
Definition: Grid.h:51
virtual ~Cell()
Definition: Grid.h:47
const Vec3r & getOrigin()
Definition: Grid.h:58
Cell(Vec3r &orig)
Definition: Grid.h:42
OccludersSet & getOccluders()
Definition: Grid.h:63
virtual void discoverCell(Cell *)
Definition: Grid.h:81
virtual void examineOccluder(Polygon3r *)
Definition: Grid.h:85
virtual void finishCell(Cell *)
Definition: Grid.h:89
virtual bool stop()
Definition: Grid.h:93
virtual ~GridVisitor()
Definition: Grid.h:79
OccludersSet _occluders
Definition: Grid.h:391
Vec3r gridSize() const
Definition: Grid.h:326
void getCellCoordinates(const Vec3r &p, Vec3u &res)
Definition: Grid.h:209
void getCellBox(const Vec3u &cell_coord, Vec3r &min_out, Vec3r &max_out)
Definition: Grid.h:266
real _t_end
Definition: Grid.h:386
void addOccluder(Polygon3r *occluder)
Definition: Grid.h:279
Vec3r getCellSize() const
Definition: Grid.h:331
Vec3u _current_cell
Definition: Grid.h:383
const Vec3r & getOrigin() const
Definition: Grid.h:321
Vec3r _cell_size
Definition: Grid.h:378
void getCellOrigin(const Vec3u &cell_coord, Vec3r &orig)
Definition: Grid.h:251
virtual ~Grid()
Definition: Grid.h:184
Vec3r _pt
Definition: Grid.h:384
Vec3r _size
Definition: Grid.h:379
OccludersSet * getOccluders()
Definition: Grid.h:337
bool initAcceleratedInfiniteRay(const Vec3r &orig, const Vec3r &dir, unsigned timestamp)
virtual void fillCell(const Vec3u &coord, Cell &cell)=0
Cell * getCell(const Vec3r &p)
Definition: Grid.h:237
void initAcceleratedRay(const Vec3r &orig, const Vec3r &end, unsigned timestamp)
virtual Cell * getCell(const Vec3u &coord)=0
void castRayInternal(GridVisitor &visitor)
Definition: Grid.h:352
Vec3u _cells_nb
Definition: Grid.h:377
unsigned int _timestamp
Definition: Grid.h:375
Vec3r _orig
Definition: Grid.h:380
void displayDebug()
Definition: Grid.h:342
Vec3r _ray_dir
Definition: Grid.h:382
VirtualOccludersSet(Grid &_grid)
Definition: Grid.h:405
Polygon3r * next(bool stopOnNewCell)
OccludersSet & occluders()
Definition: Grid.h:112
allOccludersGridVisitor(OccludersSet &occluders)
Definition: Grid.h:106
virtual void discoverCell(Cell *cell)
Definition: Grid.h:157
firstIntersectionGridVisitor(const Vec3r &ray_org, const Vec3r &ray_dir, const Vec3r &cell_size)
Definition: Grid.h:140
static void clear(Message *msg)
Definition: msgfmt.c:278
inherits from class Rep
Definition: AppCanvas.cpp:18
vector< Polygon3r * > OccludersSet
Definition: Grid.h:33
double real
Definition: Precision.h:12