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
|
/*
* ***** 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.
*
* The Original Code is Copyright (C) 2010 Blender Foundation.
* All rights reserved.
*
* The Original Code is: all of this file.
*
* Contributor(s): none yet.
*
* ***** END GPL LICENSE BLOCK *****
*/
#ifndef __FREESTYLE_SPHERICAL_GRID_H__
#define __FREESTYLE_SPHERICAL_GRID_H__
/** \file blender/freestyle/intern/view_map/SphericalGrid.h
* \ingroup freestyle
* \brief Class to define a cell grid surrounding the projected image of a scene
* \author Alexander Beels
* \date 2010-12-19
*/
#define SPHERICAL_GRID_LOGGING FALSE
// I would like to avoid using deque because including ViewMap.h and <deque> or <vector> separately results in
// redefinitions of identifiers. ViewMap.h already includes <vector> so it should be a safe fall-back.
//#include <vector>
//#include <deque>
#include "GridDensityProvider.h"
#include "OccluderSource.h"
#include "ViewMap.h"
#include "../geometry/Polygon.h"
#include "../geometry/BBox.h"
#include "../geometry/GridHelpers.h"
#include "../system/PointerSequence.h"
#include "../winged_edge/WEdge.h"
class SphericalGrid
{
public:
// Helper classes
struct OccluderData
{
explicit OccluderData (OccluderSource& source, Polygon3r& p);
Polygon3r poly;
Polygon3r cameraSpacePolygon;
real shallowest, deepest;
// N.B. We could, of course, store face in poly's userdata member, like the old ViewMapBuilder code does.
// However, code comments make it clear that userdata is deprecated, so we avoid the temptation to save
// 4 or 8 bytes.
WFace *face;
};
private:
struct Cell
{
// Can't store Cell in a vector without copy and assign
//Cell(const Cell& other);
//Cell& operator=(const Cell& other);
explicit Cell();
~Cell();
static bool compareOccludersByShallowestPoint(const OccluderData *a, const OccluderData *b);
void setDimensions(real x, real y, real sizeX, real sizeY);
void checkAndInsert(OccluderSource& source, Polygon3r& poly, OccluderData*& occluder);
void indexPolygons();
real boundary[4];
//deque<OccluderData*> faces;
vector<OccluderData*> faces;
};
public:
/*! Iterator needs to allow the user to avoid full 3D comparison in two cases:
*
* (1) Where (*current)->deepest < target[2], where the occluder is unambiguously in front of the target point.
*
* (2) Where (*current)->shallowest > target[2], where the occluder is unambiguously in back of the target point.
*
* In addition, when used by OptimizedFindOccludee, Iterator should stop iterating as soon as it has an occludee
* candidate and (*current)->shallowest > candidate[2], because at that point forward no new occluder could
* possibly be a better occludee.
*/
class Iterator
{
public:
// epsilon is not used in this class, but other grids with the same interface may need an epsilon
explicit Iterator(SphericalGrid& grid, Vec3r& center, real epsilon = 1.0e-06);
~Iterator();
void initBeforeTarget();
void initAfterTarget();
void nextOccluder();
void nextOccludee();
bool validBeforeTarget();
bool validAfterTarget();
WFace *getWFace() const;
Polygon3r *getCameraSpacePolygon();
void reportDepth(Vec3r origin, Vec3r u, real t);
private:
bool testOccluder(bool wantOccludee);
void markCurrentOccludeeCandidate(real depth);
Cell *_cell;
Vec3r _target;
bool _foundOccludee;
real _occludeeDepth;
//deque<OccluderData*>::iterator _current, _occludeeCandidate;
vector<OccluderData*>::iterator _current, _occludeeCandidate;
};
class Transform : public GridHelpers::Transform
{
public:
explicit Transform();
explicit Transform(Transform& other);
Vec3r operator()(const Vec3r& point) const;
static Vec3r sphericalProjection(const Vec3r& M);
};
private:
// Prevent implicit copies and assignments.
SphericalGrid(const SphericalGrid& other);
SphericalGrid& operator=(const SphericalGrid& other);
public:
explicit SphericalGrid(OccluderSource& source, GridDensityProvider& density, ViewMap *viewMap,
Vec3r& viewpoint, bool enableQI);
virtual ~SphericalGrid();
// Generate Cell structure
void assignCells(OccluderSource& source, GridDensityProvider& density, ViewMap *viewMap);
// Fill Cells
void distributePolygons(OccluderSource& source);
// Insert one polygon into each matching cell, return true if any cell consumes the polygon
bool insertOccluder(OccluderSource& source, OccluderData*& occluder);
// Sort occluders in each cell
void reorganizeCells();
Cell *findCell(const Vec3r& point);
// Accessors:
bool orthographicProjection() const;
const Vec3r& viewpoint() const;
bool enableQI() const;
private:
void getCellCoordinates(const Vec3r& point, unsigned& x, unsigned& y);
typedef PointerSequence<vector<Cell*>, Cell*> cellContainer;
//typedef PointerSequence<deque<OccluderData*>, OccluderData*> occluderContainer;
typedef PointerSequence<vector<OccluderData*>, OccluderData*> occluderContainer;
unsigned _cellsX, _cellsY;
float _cellSize;
float _cellOrigin[2];
cellContainer _cells;
occluderContainer _faces;
Vec3r _viewpoint;
bool _enableQI;
};
inline void SphericalGrid::Iterator::initBeforeTarget()
{
_current = _cell->faces.begin();
while (_current != _cell->faces.end() && !testOccluder(false)) {
++_current;
}
}
inline void SphericalGrid::Iterator::initAfterTarget()
{
if (_foundOccludee) {
#if SPHERICAL_GRID_LOGGING
std::cout << "\tStarting occludee search from occludeeCandidate at depth " << _occludeeDepth << std::endl;
#endif
_current = _occludeeCandidate;
return;
}
#if SPHERICAL_GRID_LOGGING
std::cout << "\tStarting occludee search from current position" << std::endl;
#endif
while (_current != _cell->faces.end() && !testOccluder(true)) {
++_current;
}
}
inline bool SphericalGrid::Iterator::testOccluder(bool wantOccludee)
{
// End-of-list is not even a valid iterator position
if (_current == _cell->faces.end()) {
// Returning true seems strange, but it will break us out of whatever loop is calling testOccluder, and
// _current=_cell->face.end() will make the calling routine give up.
return true;
}
#if SPHERICAL_GRID_LOGGING
std::cout << "\tTesting occluder " << (*_current)->poly.getVertices()[0];
for (unsigned int i = 1; i < (*_current)->poly.getVertices().size(); ++i) {
std::cout << ", " << (*_current)->poly.getVertices()[i];
}
std::cout << " from shape " << (*_current)->face->GetVertex(0)->shape()->GetId() << std::endl;
#endif
// If we have an occluder candidate and we are unambiguously after it, abort
if (_foundOccludee && (*_current)->shallowest > _occludeeDepth) {
#if SPHERICAL_GRID_LOGGING
std::cout << "\t\tAborting: shallowest > occludeeCandidate->deepest" << std::endl;
#endif
_current = _cell->faces.end();
// See note above
return true;
}
// Specific continue or stop conditions when searching for each type
if (wantOccludee) {
if ((*_current)->deepest < _target[2]) {
#if SPHERICAL_GRID_LOGGING
std::cout << "\t\tSkipping: shallower than target while looking for occludee" << std::endl;
#endif
return false;
}
}
else {
if ((*_current)->shallowest > _target[2]) {
#if SPHERICAL_GRID_LOGGING
std::cout << "\t\tStopping: deeper than target while looking for occluder" << std::endl;
#endif
return true;
}
}
// Depthwise, this is a valid occluder.
// Check to see if target is in the 2D bounding box
Vec3r bbMin, bbMax;
(*_current)->poly.getBBox(bbMin, bbMax);
if (_target[0] < bbMin[0] || _target[0] > bbMax[0] || _target[1] < bbMin[1] || _target[1] > bbMax[1]) {
#if SPHERICAL_GRID_LOGGING
std::cout << "\t\tSkipping: bounding box violation" << std::endl;
#endif
return false;
}
// We've done all the corner cutting we can. Let the caller work out whether or not the geometry is correct.
return true;
}
inline void SphericalGrid::Iterator::reportDepth(Vec3r origin, Vec3r u, real t)
{
// The reported depth is the length of a ray in camera space. We need to convert it into the distance from viewpoint
// If origin is the viewpoint, depth == t. A future optimization could allow the caller to tell us if origin is
// viewponit or target, at the cost of changing the OptimizedGrid API.
real depth = (origin + u * t).norm();
#if SPHERICAL_GRID_LOGGING
std::cout << "\t\tReporting depth of occluder/ee: " << depth;
#endif
if (depth > _target[2]) {
#if SPHERICAL_GRID_LOGGING
std::cout << " is deeper than target" << std::endl;
#endif
// If the current occluder is the best occludee so far, save it.
if (! _foundOccludee || _occludeeDepth > depth) {
markCurrentOccludeeCandidate(depth);
}
}
else {
#if SPHERICAL_GRID_LOGGING
std::cout << std::endl;
#endif
}
}
inline void SphericalGrid::Iterator::nextOccluder()
{
if (_current != _cell->faces.end()) {
do {
++_current;
} while (_current != _cell->faces.end() && !testOccluder(false));
}
}
inline void SphericalGrid::Iterator::nextOccludee()
{
if (_current != _cell->faces.end()) {
do {
++_current;
} while (_current != _cell->faces.end() && !testOccluder(true));
}
}
inline bool SphericalGrid::Iterator::validBeforeTarget()
{
return _current != _cell->faces.end() && (*_current)->shallowest <= _target[2];
}
inline bool SphericalGrid::Iterator::validAfterTarget()
{
return _current != _cell->faces.end();
}
inline void SphericalGrid::Iterator::markCurrentOccludeeCandidate(real depth)
{
#if SPHERICAL_GRID_LOGGING
std::cout << "\t\tFound occludeeCandidate at depth " << depth << std::endl;
#endif
_occludeeCandidate = _current;
_occludeeDepth = depth;
_foundOccludee = true;
}
inline WFace *SphericalGrid::Iterator::getWFace() const
{
return (*_current)->face;
}
inline Polygon3r *SphericalGrid::Iterator::getCameraSpacePolygon()
{
return &((*_current)->cameraSpacePolygon);
}
inline SphericalGrid::OccluderData::OccluderData (OccluderSource& source, Polygon3r& p)
: poly(p), cameraSpacePolygon(source.getCameraSpacePolygon()), face(source.getWFace())
{
const Vec3r viewpoint(0, 0, 0);
// Get the point on the camera-space polygon that is closest to the viewpoint
// shallowest is the distance from the viewpoint to that point
shallowest = GridHelpers::distancePointToPolygon(viewpoint, cameraSpacePolygon);
// Get the point on the camera-space polygon that is furthest from the viewpoint
// deepest is the distance from the viewpoint to that point
deepest = cameraSpacePolygon.getVertices()[2].norm();
for (unsigned int i = 0; i < 2; ++i) {
real t = cameraSpacePolygon.getVertices()[i].norm();
if (t > deepest) {
deepest = t;
}
}
}
inline void SphericalGrid::Cell::checkAndInsert(OccluderSource& source, Polygon3r& poly, OccluderData*& occluder)
{
if (GridHelpers::insideProscenium (boundary, poly)) {
if (occluder == NULL) {
// Disposal of occluder will be handled in SphericalGrid::distributePolygons(),
// or automatically by SphericalGrid::_faces;
occluder = new OccluderData(source, poly);
}
faces.push_back(occluder);
}
}
inline bool SphericalGrid::insertOccluder(OccluderSource& source, OccluderData*& occluder)
{
Polygon3r& poly(source.getGridSpacePolygon());
occluder = NULL;
Vec3r bbMin, bbMax;
poly.getBBox(bbMin, bbMax);
// Check overlapping cells
unsigned startX, startY, endX, endY;
getCellCoordinates(bbMin, startX, startY);
getCellCoordinates(bbMax, endX, endY);
for (unsigned int i = startX; i <= endX; ++i) {
for (unsigned int j = startY; j <= endY; ++j) {
if (_cells[i * _cellsY + j] != NULL) {
_cells[i * _cellsY + j]->checkAndInsert(source, poly, occluder);
}
}
}
return occluder != NULL;
}
#endif // __FREESTYLE_SPHERICAL_GRID_H__
|