915398af02fb9a067a9ec21187be8eafdb3e8d53
[blender.git] / source / blender / freestyle / intern / view_map / SphericalGrid.h
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * ***** END GPL LICENSE BLOCK *****
19  */
20
21 #ifndef __FREESTYLE_SPHERICAL_GRID_H__
22 #define __FREESTYLE_SPHERICAL_GRID_H__
23
24 /** \file blender/freestyle/intern/view_map/SphericalGrid.h
25  *  \ingroup freestyle
26  *  \brief Class to define a cell grid surrounding the projected image of a scene
27  *  \author Alexander Beels
28  *  \date 2010-12-19
29  */
30
31 #define SPHERICAL_GRID_LOGGING false
32
33 // I would like to avoid using deque because including ViewMap.h and <deque> or <vector> separately results in
34 // redefinitions of identifiers. ViewMap.h already includes <vector> so it should be a safe fall-back.
35 //#include <vector>
36 //#include <deque>
37
38 #include "GridDensityProvider.h"
39 #include "OccluderSource.h"
40 #include "ViewMap.h"
41
42 #include "../geometry/Polygon.h"
43 #include "../geometry/BBox.h"
44 #include "../geometry/GridHelpers.h"
45
46 #include "../system/PointerSequence.h"
47
48 #include "../winged_edge/WEdge.h"
49
50 #include "BKE_global.h"
51
52 #ifdef WITH_CXX_GUARDEDALLOC
53 #include "MEM_guardedalloc.h"
54 #endif
55
56 namespace Freestyle {
57
58 class SphericalGrid
59 {
60 public:
61         // Helper classes
62         struct OccluderData
63         {
64                 explicit OccluderData (OccluderSource& source, Polygon3r& p);
65                 Polygon3r poly;
66                 Polygon3r cameraSpacePolygon;
67                 real shallowest, deepest;
68                 // N.B. We could, of course, store face in poly's userdata member, like the old ViewMapBuilder code does.
69                 // However, code comments make it clear that userdata is deprecated, so we avoid the temptation to save
70                 // 4 or 8 bytes.
71                 WFace *face;
72
73 #ifdef WITH_CXX_GUARDEDALLOC
74                 MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:SphericalGrid:OccluderData")
75 #endif
76         };
77
78 private:
79         struct Cell
80         {
81                 // Can't store Cell in a vector without copy and assign
82                 //Cell(const Cell& other);
83                 //Cell& operator=(const Cell& other);
84
85                 explicit Cell();
86                 ~Cell();
87
88                 static bool compareOccludersByShallowestPoint(const OccluderData *a, const OccluderData *b);
89
90                 void setDimensions(real x, real y, real sizeX, real sizeY);
91                 void checkAndInsert(OccluderSource& source, Polygon3r& poly, OccluderData*& occluder);
92                 void indexPolygons();
93
94                 real boundary[4];
95                 //deque<OccluderData*> faces;
96                 vector<OccluderData*> faces;
97         };
98
99 public:
100         /*! Iterator needs to allow the user to avoid full 3D comparison in two cases:
101          *
102          *  (1) Where (*current)->deepest < target[2], where the occluder is unambiguously in front of the target point.
103          *
104          *  (2) Where (*current)->shallowest > target[2], where the occluder is unambiguously in back of the target point.
105          *
106          *  In addition, when used by OptimizedFindOccludee, Iterator should stop iterating as soon as it has an occludee
107          *  candidate and (*current)->shallowest > candidate[2], because at that point forward no new occluder could
108          *  possibly be a better occludee.
109          */
110
111         class Iterator
112         {
113         public:
114                 // epsilon is not used in this class, but other grids with the same interface may need an epsilon
115                 explicit Iterator(SphericalGrid& grid, Vec3r& center, real epsilon = 1.0e-06);
116                 ~Iterator();
117                 void initBeforeTarget();
118                 void initAfterTarget();
119                 void nextOccluder();
120                 void nextOccludee();
121                 bool validBeforeTarget();
122                 bool validAfterTarget();
123                 WFace *getWFace() const;
124                 Polygon3r *getCameraSpacePolygon();
125                 void reportDepth(Vec3r origin, Vec3r u, real t);
126         private:
127                 bool testOccluder(bool wantOccludee);
128                 void markCurrentOccludeeCandidate(real depth);
129
130                 Cell *_cell;
131                 Vec3r _target;
132                 bool _foundOccludee;
133                 real _occludeeDepth;
134                 //deque<OccluderData*>::iterator _current, _occludeeCandidate;
135                 vector<OccluderData*>::iterator _current, _occludeeCandidate;
136
137 #ifdef WITH_CXX_GUARDEDALLOC
138                 MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:SphericalGrid:Iterator")
139 #endif
140
141         };
142
143         class Transform : public GridHelpers::Transform
144         {
145         public:
146                 explicit Transform();
147                 explicit Transform(Transform& other);
148                 Vec3r operator()(const Vec3r& point) const;
149                 static Vec3r sphericalProjection(const Vec3r& M);
150         };
151
152 private:
153         // Prevent implicit copies and assignments.
154         SphericalGrid(const SphericalGrid& other);
155         SphericalGrid& operator=(const SphericalGrid& other);
156
157 public:
158         explicit SphericalGrid(OccluderSource& source, GridDensityProvider& density, ViewMap *viewMap,
159                                Vec3r& viewpoint, bool enableQI);
160         virtual ~SphericalGrid();
161
162         // Generate Cell structure
163         void assignCells(OccluderSource& source, GridDensityProvider& density, ViewMap *viewMap);
164         // Fill Cells
165         void distributePolygons(OccluderSource& source);
166         // Insert one polygon into each matching cell, return true if any cell consumes the polygon
167         bool insertOccluder(OccluderSource& source, OccluderData*& occluder);
168         // Sort occluders in each cell
169         void reorganizeCells();
170
171         Cell *findCell(const Vec3r& point);
172
173         // Accessors:
174         bool orthographicProjection() const;
175         const Vec3r& viewpoint() const;
176         bool enableQI() const; 
177
178 private:
179         void getCellCoordinates(const Vec3r& point, unsigned& x, unsigned& y);
180
181         typedef PointerSequence<vector<Cell*>, Cell*> cellContainer;
182         //typedef PointerSequence<deque<OccluderData*>, OccluderData*> occluderContainer;
183         typedef PointerSequence<vector<OccluderData*>, OccluderData*> occluderContainer;
184         unsigned _cellsX, _cellsY;
185         float _cellSize;
186         float _cellOrigin[2];
187         cellContainer _cells;
188         occluderContainer _faces;
189         Vec3r _viewpoint;
190         bool _enableQI;
191
192 #ifdef WITH_CXX_GUARDEDALLOC
193         MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:SphericalGrid")
194 #endif
195 };
196
197 inline void SphericalGrid::Iterator::initBeforeTarget()
198 {
199         _current = _cell->faces.begin();
200         while (_current != _cell->faces.end() && !testOccluder(false)) {
201                 ++_current;
202         }
203 }
204
205 inline void SphericalGrid::Iterator::initAfterTarget()
206 {
207         if (_foundOccludee) {
208 #if SPHERICAL_GRID_LOGGING
209                 if (G.debug & G_DEBUG_FREESTYLE) {
210                         std::cout << "\tStarting occludee search from occludeeCandidate at depth " <<
211                                      _occludeeDepth << std::endl;
212                 }
213 #endif
214                 _current = _occludeeCandidate;
215                 return;
216         }
217
218 #if SPHERICAL_GRID_LOGGING
219         if (G.debug & G_DEBUG_FREESTYLE) {
220                 std::cout << "\tStarting occludee search from current position" << std::endl;
221         }
222 #endif
223
224         while (_current != _cell->faces.end() && !testOccluder(true)) {
225                 ++_current;
226         }
227 }
228
229 inline bool SphericalGrid::Iterator::testOccluder(bool wantOccludee)
230 {
231         // End-of-list is not even a valid iterator position
232         if (_current == _cell->faces.end()) {
233                 // Returning true seems strange, but it will break us out of whatever loop is calling testOccluder, and
234                 // _current=_cell->face.end() will make the calling routine give up.
235                 return true;
236         }
237 #if SPHERICAL_GRID_LOGGING
238         if (G.debug & G_DEBUG_FREESTYLE) {
239                 std::cout << "\tTesting occluder " << (*_current)->poly.getVertices()[0];
240                 for (unsigned int i = 1; i < (*_current)->poly.getVertices().size(); ++i) {
241                         std::cout << ", " << (*_current)->poly.getVertices()[i];
242                 }
243                 std::cout << " from shape " << (*_current)->face->GetVertex(0)->shape()->GetId() << std::endl;
244         }
245 #endif
246
247         // If we have an occluder candidate and we are unambiguously after it, abort
248         if (_foundOccludee && (*_current)->shallowest > _occludeeDepth) {
249 #if SPHERICAL_GRID_LOGGING
250                 if (G.debug & G_DEBUG_FREESTYLE) {
251                         std::cout << "\t\tAborting: shallowest > occludeeCandidate->deepest" << std::endl;
252                 }
253 #endif
254                 _current = _cell->faces.end();
255
256                 // See note above
257                 return true;
258         }
259
260         // Specific continue or stop conditions when searching for each type
261         if (wantOccludee) {
262                 if ((*_current)->deepest < _target[2]) {
263 #if SPHERICAL_GRID_LOGGING
264                         if (G.debug & G_DEBUG_FREESTYLE) {
265                                 std::cout << "\t\tSkipping: shallower than target while looking for occludee" << std::endl;
266                         }
267 #endif
268                         return false;
269                 }
270         }
271         else {
272                 if ((*_current)->shallowest > _target[2]) {
273 #if SPHERICAL_GRID_LOGGING
274                         if (G.debug & G_DEBUG_FREESTYLE) {
275                                 std::cout << "\t\tStopping: deeper than target while looking for occluder" << std::endl;
276                         }
277 #endif
278                         return true;
279                 }
280         }
281
282         // Depthwise, this is a valid occluder.
283
284         // Check to see if target is in the 2D bounding box
285         Vec3r bbMin, bbMax;
286         (*_current)->poly.getBBox(bbMin, bbMax);
287         if (_target[0] < bbMin[0] || _target[0] > bbMax[0] || _target[1] < bbMin[1] || _target[1] > bbMax[1]) {
288 #if SPHERICAL_GRID_LOGGING
289                 if (G.debug & G_DEBUG_FREESTYLE) {
290                         std::cout << "\t\tSkipping: bounding box violation" << std::endl;
291                 }
292 #endif
293                 return false;
294         }
295
296         // We've done all the corner cutting we can. Let the caller work out whether or not the geometry is correct.
297         return true;
298 }
299
300 inline void SphericalGrid::Iterator::reportDepth(Vec3r origin, Vec3r u, real t)
301 {
302         // The reported depth is the length of a ray in camera space. We need to convert it into the distance from viewpoint
303         // If origin is the viewpoint, depth == t. A future optimization could allow the caller to tell us if origin is
304         // viewponit or target, at the cost of changing the OptimizedGrid API.
305         real depth = (origin + u * t).norm();
306 #if SPHERICAL_GRID_LOGGING
307         if (G.debug & G_DEBUG_FREESTYLE) {
308                 std::cout << "\t\tReporting depth of occluder/ee: " << depth;
309         }
310 #endif
311         if (depth > _target[2]) {
312 #if SPHERICAL_GRID_LOGGING
313                 if (G.debug & G_DEBUG_FREESTYLE) {
314                         std::cout << " is deeper than target" << std::endl;
315                 }
316 #endif
317                 // If the current occluder is the best occludee so far, save it.
318                 if (! _foundOccludee || _occludeeDepth > depth) {
319                         markCurrentOccludeeCandidate(depth);
320                 } 
321         }
322         else {
323 #if SPHERICAL_GRID_LOGGING
324                 if (G.debug & G_DEBUG_FREESTYLE) {
325                         std::cout << std::endl;
326                 }
327 #endif
328         }
329 }
330
331 inline void SphericalGrid::Iterator::nextOccluder()
332 {
333         if (_current != _cell->faces.end()) {
334                 do {
335                         ++_current;
336                 } while (_current != _cell->faces.end() && !testOccluder(false));
337         }
338 }
339
340 inline void SphericalGrid::Iterator::nextOccludee()
341 {
342         if (_current != _cell->faces.end()) {
343                 do {
344                         ++_current;
345                 } while (_current != _cell->faces.end() && !testOccluder(true));
346         }
347 }
348
349 inline bool SphericalGrid::Iterator::validBeforeTarget()
350 {
351         return _current != _cell->faces.end() && (*_current)->shallowest <= _target[2];
352 }
353
354 inline bool SphericalGrid::Iterator::validAfterTarget()
355 {
356         return _current != _cell->faces.end();
357 }
358
359 inline void SphericalGrid::Iterator::markCurrentOccludeeCandidate(real depth)
360 {
361 #if SPHERICAL_GRID_LOGGING
362         if (G.debug & G_DEBUG_FREESTYLE) {
363                 std::cout << "\t\tFound occludeeCandidate at depth " << depth << std::endl;
364         }
365 #endif
366         _occludeeCandidate = _current;
367         _occludeeDepth = depth;
368         _foundOccludee = true;
369 }
370
371 inline WFace *SphericalGrid::Iterator::getWFace() const
372 {
373         return (*_current)->face;
374 }
375
376 inline Polygon3r *SphericalGrid::Iterator::getCameraSpacePolygon()
377 {
378         return &((*_current)->cameraSpacePolygon);
379 }
380
381 inline SphericalGrid::OccluderData::OccluderData (OccluderSource& source, Polygon3r& p)
382 : poly(p), cameraSpacePolygon(source.getCameraSpacePolygon()), face(source.getWFace())
383 {
384         const Vec3r viewpoint(0, 0, 0);
385         // Get the point on the camera-space polygon that is closest to the viewpoint
386         // shallowest is the distance from the viewpoint to that point
387         shallowest = GridHelpers::distancePointToPolygon(viewpoint, cameraSpacePolygon);
388
389         // Get the point on the camera-space polygon that is furthest from the viewpoint
390         // deepest is the distance from the viewpoint to that point
391         deepest = cameraSpacePolygon.getVertices()[2].norm();
392         for (unsigned int i = 0; i < 2; ++i) {
393                 real t = cameraSpacePolygon.getVertices()[i].norm();
394                 if (t > deepest) {
395                         deepest = t;
396                 }
397         }
398 }
399
400 inline void SphericalGrid::Cell::checkAndInsert(OccluderSource& source, Polygon3r& poly, OccluderData*& occluder)
401 {
402         if (GridHelpers::insideProscenium (boundary, poly)) {
403                 if (occluder == NULL) {
404                         // Disposal of occluder will be handled in SphericalGrid::distributePolygons(),
405                         // or automatically by SphericalGrid::_faces;
406                         occluder = new OccluderData(source, poly);
407                 }
408                 faces.push_back(occluder);
409         }
410 }
411
412 inline bool SphericalGrid::insertOccluder(OccluderSource& source, OccluderData*& occluder)
413 {
414         Polygon3r& poly(source.getGridSpacePolygon());
415         occluder = NULL;
416
417         Vec3r bbMin, bbMax;
418         poly.getBBox(bbMin, bbMax);
419         // Check overlapping cells
420         unsigned startX, startY, endX, endY;
421         getCellCoordinates(bbMin, startX, startY);
422         getCellCoordinates(bbMax, endX, endY);
423
424         for (unsigned int i = startX; i <= endX; ++i) {
425                 for (unsigned int j = startY; j <= endY; ++j) {
426                         if (_cells[i * _cellsY + j] != NULL) {
427                                 _cells[i * _cellsY + j]->checkAndInsert(source, poly, occluder);
428                         }
429                 }
430         }
431
432         return occluder != NULL;
433 }
434
435 } /* namespace Freestyle */
436
437 #endif // __FREESTYLE_SPHERICAL_GRID_H__