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