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