Merged changes in the trunk up to revision 53146.
[blender.git] / source / blender / freestyle / intern / view_map / SphericalGrid.cpp
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 //  Copyright (C) : Please refer to the COPYRIGHT file distributed 
12 //   with this source distribution. 
13 //
14 //  This program is free software; you can redistribute it and/or
15 //  modify it under the terms of the GNU General Public License
16 //  as published by the Free Software Foundation; either version 2
17 //  of the License, or (at your option) any later version.
18 //
19 //  This program is distributed in the hope that it will be useful,
20 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
21 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
22 //  GNU General Public License for more details.
23 //
24 //  You should have received a copy of the GNU General Public License
25 //  along with this program; if not, write to the Free Software
26 //  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
27 //
28 ///////////////////////////////////////////////////////////////////////////////
29
30 #include "SphericalGrid.h"
31
32 #include <stdexcept>
33 #include <algorithm>
34
35 using namespace std;
36
37 // Helper Classes
38
39 // OccluderData
40 ///////////////
41
42 // Cell
43 /////////
44
45 SphericalGrid::Cell::Cell () {}
46
47 SphericalGrid::Cell::~Cell () {}
48
49 void SphericalGrid::Cell::setDimensions(real x, real y, real sizeX, real sizeY) {
50         const real epsilon = 1.0e-06;
51         boundary[0] = x - epsilon;
52         boundary[1] = x + sizeX + epsilon;
53         boundary[2] = y - epsilon;
54         boundary[3] = y + sizeY + epsilon;
55 }
56
57 bool SphericalGrid::Cell::compareOccludersByShallowestPoint (const SphericalGrid::OccluderData* a, const SphericalGrid::OccluderData* b) {
58         return a->shallowest < b->shallowest;
59 }
60
61 void SphericalGrid::Cell::indexPolygons() {
62         // Sort occluders by their shallowest points.
63         sort(faces.begin(), faces.end(), compareOccludersByShallowestPoint);
64 }
65
66 // Iterator
67 //////////////////
68
69 SphericalGrid::Iterator::Iterator (SphericalGrid& grid, Vec3r& center, real epsilon) 
70         : _target(SphericalGrid::Transform::sphericalProjection(center)), 
71         _foundOccludee(false)
72 {
73         // Find target cell
74         _cell = grid.findCell(_target);
75         #if sphericalgridlogging == 1
76                 cout << "Searching for occluders of edge centered at " << _target << " in cell [" 
77                         << _cell->boundary[0] << ", " << _cell->boundary[1] << ", " << _cell->boundary[2] 
78                         << ", " << _cell->boundary[3] << "] (" << _cell->faces.size() << " occluders)" << endl;
79         #endif
80
81         // Set iterator
82         _current = _cell->faces.begin();
83 }
84
85 SphericalGrid::Iterator::~Iterator () {}
86
87 // SphericalGrid
88 /////////////////
89
90 SphericalGrid::SphericalGrid(OccluderSource& source, GridDensityProvider& density, ViewMap *viewMap, Vec3r& viewpoint, bool enableQI)
91         : _viewpoint(viewpoint),
92         _enableQI(enableQI)
93 {
94         cout << "Generate Cell structure" << endl;
95         // Generate Cell structure
96         assignCells(source, density, viewMap);
97         cout << "Distribute occluders" << endl;
98         // Fill Cells
99         distributePolygons(source);
100         cout << "Reorganize cells" << endl;
101         // Reorganize Cells
102         reorganizeCells();
103         cout << "Ready to use SphericalGrid" << endl;
104 }
105
106 SphericalGrid::~SphericalGrid () {
107 }
108
109 void SphericalGrid::assignCells (OccluderSource& source, GridDensityProvider& density, ViewMap *viewMap) {
110         _cellSize = density.cellSize();
111         _cellsX = density.cellsX();
112         _cellsY = density.cellsY();
113         _cellOrigin[0] = density.cellOrigin(0);
114         _cellOrigin[1] = density.cellOrigin(1);
115
116         // Now allocate the cell table and fill it with default (empty) cells
117         _cells.resize(_cellsX * _cellsY);
118         for ( cellContainer::iterator i = _cells.begin(), end = _cells.end(); i != end; ++i ) {
119                 (*i) = NULL;
120         }
121
122         // Identify cells that will be used, and set the dimensions for each
123         ViewMap::fedges_container& fedges = viewMap->FEdges();
124         for (ViewMap::fedges_container::iterator f = fedges.begin(), fend = fedges.end(); f != fend; ++f ) {
125                 if ( (*f)->isInImage() ) {
126                         Vec3r point = SphericalGrid::Transform::sphericalProjection((*f)->center3d());
127                         unsigned i, j;
128                         getCellCoordinates(point, i, j);
129                         if ( _cells[i * _cellsY + j] == NULL ) {
130                                 // This is an uninitialized cell
131
132                                 real x, y, width, height;
133
134                                 x = _cellOrigin[0] + _cellSize * i;
135                                 width = _cellSize;
136
137                                 y = _cellOrigin[1] + _cellSize * j;
138                                 height = _cellSize;
139
140                                 // Initialize cell
141                                 Cell* b = _cells[i * _cellsY + j] = new Cell();
142                                 b->setDimensions(x, y, width, height);
143                         }
144                 }
145         }
146 }
147
148 void SphericalGrid::distributePolygons (OccluderSource& source) {
149         unsigned long nFaces = 0;
150         unsigned long nKeptFaces = 0;
151
152         for ( source.begin(); source.isValid(); source.next() ) {
153                 OccluderData* occluder = NULL;
154
155                 try {
156                         if ( insertOccluder(source, occluder) ) {
157                                 _faces.push_back(occluder);
158                                 ++nKeptFaces;
159                         }
160                 } catch (...) {
161                         // If an exception was thrown, _faces.push_back() cannot have succeeded.
162                         // occluder is not owned by anyone, and must be deleted.
163                         // If the exception was thrown before or during new OccluderData(), then
164                         // occluder is NULL, and this delete is harmless.
165                         delete occluder;
166                         throw;
167                 }
168                 ++nFaces;
169         }
170         cout << "Distributed " << nFaces << " occluders.  Retained " << nKeptFaces << "." << endl;
171 }
172
173 void SphericalGrid::reorganizeCells () {
174         // Sort the occluders by shallowest point
175         for ( vector<Cell*>::iterator i = _cells.begin(), end = _cells.end(); i != end; ++i ) {
176                 if ( *i != NULL ) {
177                         (*i)->indexPolygons();
178                 }
179         }
180 }
181
182 void SphericalGrid::getCellCoordinates(const Vec3r& point, unsigned& x, unsigned& y) {
183         x = min(_cellsX - 1, (unsigned) floor (max((double) 0.0f, point[0] - _cellOrigin[0]) / _cellSize));
184         y = min(_cellsY - 1, (unsigned) floor (max((double) 0.0f, point[1] - _cellOrigin[1]) / _cellSize));
185 }
186
187 SphericalGrid::Cell* SphericalGrid::findCell(const Vec3r& point) {
188         unsigned x, y;
189         getCellCoordinates(point, x, y);
190         return _cells[x * _cellsY + y];
191 }
192
193 bool SphericalGrid::orthographicProjection () const {
194         return false;
195 }
196
197 const Vec3r& SphericalGrid::viewpoint() const {
198         return _viewpoint;
199 }
200
201 bool SphericalGrid::enableQI() const {
202         return _enableQI;
203 }
204
205 SphericalGrid::Transform::Transform () : GridHelpers::Transform() {
206 }
207
208 Vec3r SphericalGrid::Transform::operator() (const Vec3r& point) const {
209         return sphericalProjection(point);
210 }
211
212 Vec3r SphericalGrid::Transform::sphericalProjection(const Vec3r& M) {
213         Vec3r newPoint;
214
215         newPoint[0] = ::atan(M[0] / M[2]);
216         newPoint[1] = ::atan(M[1] / M[2]);
217         newPoint[2] = ::sqrt(M[0] * M[0] + M[1] * M[1] + M[2] * M[2]);
218
219         return newPoint;
220 }
221