1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
|
/*
* ***** BEGIN GPL LICENSE BLOCK *****
*
* 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.
*
* ***** END GPL LICENSE BLOCK *****
*/
#ifndef __GRID_H__
#define __GRID_H__
/** \file blender/freestyle/intern/geometry/Grid.h
* \ingroup freestyle
* \brief Base class to define a cell grid surrounding the bounding box of the scene
* \author Stephane Grabli
* \date 30/07/2002
*/
#include <cstring> // for memset
#include <float.h>
#ifndef _MSC_VER
#include <stdint.h> // For SET_UINT_IN_POINTER, i.e. uintptr_t.
#endif
#include <vector>
#include "Geom.h"
#include "GeomUtils.h"
#include "Polygon.h"
#include "../system/FreestyleConfig.h"
extern "C" {
#include "BLI_utildefines.h"
}
#ifdef WITH_CXX_GUARDEDALLOC
#include "MEM_guardedalloc.h"
#endif
using namespace std;
namespace Freestyle {
using namespace Geometry;
typedef vector<Polygon3r*> OccludersSet;
//
// Class to define cells used by the regular grid
//
///////////////////////////////////////////////////////////////////////////////
class LIB_GEOMETRY_EXPORT 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;
#ifdef WITH_CXX_GUARDEDALLOC
MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:Cell")
#endif
};
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;
}
#ifdef WITH_CXX_GUARDEDALLOC
MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:GridVisitor")
#endif
};
/*! Gathers all the occluders belonging to the cells traversed by the ray */
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_;
};
/*! Finds the first intersection and breaks.
* The occluder and the intersection information are stored and accessible.
*/
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 LIB_GEOMETRY_EXPORT Grid
{
public:
/*! Builds a Grid. Must be followed by a call to configure() */
Grid() {}
virtual ~Grid() {
clear();
}
/*! clears the grid
* Deletes all the cells, clears the hashtable, resets size, size of cell, number of cells.
*/
virtual void clear();
/*! Sets the different parameters of the grid
* orig
* The grid origin
* size
* The grid's dimensions
* nb
* The number of cells of the grid
*/
virtual void configure(const Vec3r& orig, const Vec3r& size, unsigned nb);
/*! returns a vector of integer containing the coordinates of the cell containing the point passed as argument
* p
* The point for which we're looking the cell
*/
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 ((unsigned int)tmp >= _cells_nb[i])
res[i] = _cells_nb[i] - 1;
else
res[i] = tmp;
}
}
/*! Fills the case corresponding to coord with the cell */
virtual void fillCell(const Vec3u& coord, Cell& cell) = 0;
/*! returns the cell whose coordinates are pased as argument */
virtual Cell *getCell(const Vec3u& coord) = 0;
/*! returns the cell containing the point passed as argument. If the cell is empty (contains no occluder),
* NULL is returned
* p
* The point for which we're looking the cell
*/
inline Cell *getCell(const Vec3r& p) {
Vec3u coord;
getCellCoordinates(p, coord);
return getCell(coord);
}
/*! Retrieves the x,y,z coordinates of the origin of the cell whose coordinates (i,j,k) is passed as argument
* cell_coord
* i,j,k integer coordinates for the cell
* orig
* x,y,x vector to be filled in with the cell origin's coordinates
*/
inline void getCellOrigin(const Vec3u& cell_coord, Vec3r& orig) {
for (unsigned int i = 0; i < 3; i++)
orig[i] = _orig[i] + cell_coord[i] * _cell_size[i];
}
/*! Retrieves the box corresponding to the cell whose coordinates are passed as argument.
* cell_coord
* i,j,k integer coordinates for the cell
* min_out
* The min x,y,x vector of the box. Filled in by the method.
* max_out
* The max x,y,z coordinates of the box. Filled in by the method.
*/
inline void getCellBox(const Vec3u& cell_coord, Vec3r& min_out, Vec3r& max_out) {
getCellOrigin(cell_coord, min_out);
max_out = min_out + _cell_size;
}
/*! inserts a convex polygon occluder
* This method is quite coarse insofar as it adds all cells intersecting the polygon bounding box
* convex_poly
* The list of 3D points constituting a convex polygon
*/
void insertOccluder(Polygon3r *convex_poly);
/*! Adds an occluder to the list of occluders */
void addOccluder(Polygon3r *occluder) {
_occluders.push_back(occluder);
}
/*! Casts a ray between a starting point and an ending point
* Returns the list of occluders contained in the cells intersected by this ray
* Starts with a call to InitRay.
*/
void castRay(const Vec3r& orig, const Vec3r& end, OccludersSet& occluders, unsigned timestamp);
// Prepares to cast ray without generating OccludersSet
void initAcceleratedRay(const Vec3r& orig, const Vec3r& end, unsigned timestamp);
/*! Casts an infinite ray (still finishing at the end of the grid) from a starting point and in a given direction.
* Returns the list of occluders contained in the cells intersected by this ray
* Starts with a call to InitRay.
*/
void castInfiniteRay(const Vec3r& orig, const Vec3r& dir, OccludersSet& occluders, unsigned timestamp);
// Prepares to cast ray without generating OccludersSet.
bool initAcceleratedInfiniteRay(const Vec3r& orig, const Vec3r& dir, unsigned timestamp);
/*! Casts an infinite ray (still finishing at the end of the grid) from a starting point and in a given direction.
* Returns the first intersection (occluder,t,u,v) or null.
* Starts with a call to InitRay.
*/
Polygon3r * castRayToFindFirstIntersection(const Vec3r& orig, const Vec3r& dir, double& t,
double& u, double& v, unsigned timestamp);
/*! Init all structures and values for computing the cells intersected by this new ray */
void initRay(const Vec3r &orig, const Vec3r& end, unsigned timestamp);
/*! Init all structures and values for computing the cells intersected by this infinite ray.
* Returns false if the ray doesn't intersect the grid.
*/
bool initInfiniteRay(const Vec3r &orig, const Vec3r& dir, unsigned timestamp);
/*! Accessors */
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:
/*! Core of castRay and castInfiniteRay, find occluders along the given ray */
inline void castRayInternal(GridVisitor& visitor) {
Cell *current_cell = NULL;
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 (GET_UINT_FROM_POINTER((*it)->userdata2) != _timestamp) {
(*it)->userdata2 = SET_UINT_IN_POINTER(_timestamp);
visitor.examineOccluder(*it);
}
}
visitor.finishCell(current_cell);
}
} while ((!visitor.stop()) && (nextRayCell(_current_cell, _current_cell)));
}
/*! returns the cell next to the cell passed as argument. */
bool nextRayCell(Vec3u& current_cell, Vec3u& next_cell);
unsigned int _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
#ifdef WITH_CXX_GUARDEDALLOC
MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:Grid")
#endif
};
//
// 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;
#ifdef WITH_CXX_GUARDEDALLOC
MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:VirtualOccludersSet")
#endif
};
} /* namespace Freestyle */
#endif // __GRID_H__
|