diff options
Diffstat (limited to 'source/blender/freestyle/intern/view_map/SphericalGrid.h')
| -rw-r--r-- | source/blender/freestyle/intern/view_map/SphericalGrid.h | 322 |
1 files changed, 166 insertions, 156 deletions
diff --git a/source/blender/freestyle/intern/view_map/SphericalGrid.h b/source/blender/freestyle/intern/view_map/SphericalGrid.h index 55cdee19a80..0f369b4b686 100644 --- a/source/blender/freestyle/intern/view_map/SphericalGrid.h +++ b/source/blender/freestyle/intern/view_map/SphericalGrid.h @@ -1,78 +1,86 @@ -// -// Filename : SphericalGrid.h -// Author(s) : Alexander Beels -// Purpose : Class to define a cell grid surrounding -// the projected image of a scene -// Date of creation : 2010-12-19 -// -/////////////////////////////////////////////////////////////////////////////// - - -// -// Copyright (C) : Please refer to the COPYRIGHT file distributed -// with this source distribution. -// -// 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. -// -/////////////////////////////////////////////////////////////////////////////// - -#ifndef SPHERICALGRID_H -#define SPHERICALGRID_H - -#define sphericalgridlogging 0 - -// 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. +/* + * ***** 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 "../winged_edge/WEdge.h" + #include "../geometry/Polygon.h" -#include "../system/PointerSequence.h" #include "../geometry/BBox.h" #include "../geometry/GridHelpers.h" -#include "OccluderSource.h" -#include "GridDensityProvider.h" + +#include "../system/PointerSequence.h" + +#include "../winged_edge/WEdge.h" class SphericalGrid { public: // Helper classes - struct OccluderData { + 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; + // 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 { + struct Cell + { // Can't store Cell in a vector without copy and assign //Cell(const Cell& other); - //Cell& operator= (const Cell& other); + //Cell& operator=(const Cell& other); - explicit Cell (); - ~Cell (); + explicit Cell(); + ~Cell(); - static bool compareOccludersByShallowestPoint (const OccluderData* a, const OccluderData* b); + 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); @@ -84,43 +92,37 @@ private: }; 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 { + /*! 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=1e-06); - ~Iterator (); - void initBeforeTarget (); - void initAfterTarget (); - void nextOccluder (); - void nextOccludee (); + 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(); + WFace *getWFace() const; + Polygon3r *getCameraSpacePolygon(); void reportDepth(Vec3r origin, Vec3r u, real t); private: bool testOccluder(bool wantOccludee); void markCurrentOccludeeCandidate(real depth); - Cell* _cell; + Cell *_cell; Vec3r _target; bool _foundOccludee; real _occludeeDepth; @@ -128,33 +130,35 @@ public: vector<OccluderData*>::iterator _current, _occludeeCandidate; }; - class Transform : public GridHelpers::Transform { + class Transform : public GridHelpers::Transform + { public: - explicit Transform (); - explicit Transform (Transform& other); - Vec3r operator() (const Vec3r& point) const; + 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); + SphericalGrid& operator=(const SphericalGrid& other); + public: - explicit SphericalGrid (OccluderSource& source, GridDensityProvider& density, ViewMap *viewMap, Vec3r& viewpoint, bool enableQI); + 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 + // 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); + Cell *findCell(const Vec3r& point); // Accessors: bool orthographicProjection() const; @@ -176,51 +180,52 @@ private: bool _enableQI; }; -inline void SphericalGrid::Iterator::initBeforeTarget () { +inline void SphericalGrid::Iterator::initBeforeTarget() +{ _current = _cell->faces.begin(); - while ( _current != _cell->faces.end() && ! testOccluder(false) ) { + while (_current != _cell->faces.end() && !testOccluder(false)) { ++_current; } } -inline void SphericalGrid::Iterator::initAfterTarget () { - if ( _foundOccludee ) { - #if sphericalgridlogging == 1 +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 sphericalgridlogging == 1 + #if SPHERICAL_GRID_LOGGING std::cout << "\tStarting occludee search from current position" << std::endl; #endif - while ( _current != _cell->faces.end() && ! testOccluder(true) ) { + while (_current != _cell->faces.end() && !testOccluder(true)) { ++_current; } } -inline bool SphericalGrid::Iterator::testOccluder (bool wantOccludee) { +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. + 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 sphericalgridlogging == 1 + #if SPHERICAL_GRID_LOGGING std::cout << "\tTesting occluder " << (*_current)->poly.getVertices()[0]; - for ( unsigned i = 1; i < (*_current)->poly.getVertices().size(); ++i ) { + 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 sphericalgridlogging == 1 + if (_foundOccludee && (*_current)->shallowest > _occludeeDepth) { + #if SPHERICAL_GRID_LOGGING std::cout << "\t\tAborting: shallowest > occludeeCandidate->deepest" << std::endl; #endif _current = _cell->faces.end(); @@ -230,16 +235,17 @@ inline bool SphericalGrid::Iterator::testOccluder (bool wantOccludee) { } // Specific continue or stop conditions when searching for each type - if ( wantOccludee ) { - if ( (*_current)->deepest < _target[2] ) { - #if sphericalgridlogging == 1 + 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 sphericalgridlogging == 1 + } + 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; @@ -251,70 +257,73 @@ inline bool SphericalGrid::Iterator::testOccluder (bool wantOccludee) { // 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 sphericalgridlogging == 1 + 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. + // 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. +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 sphericalgridlogging == 1 + #if SPHERICAL_GRID_LOGGING std::cout << "\t\tReporting depth of occluder/ee: " << depth; #endif - if ( depth > _target[2] ) { - #if sphericalgridlogging == 1 + 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 ) { + if (! _foundOccludee || _occludeeDepth > depth) { markCurrentOccludeeCandidate(depth); } - } else { - #if sphericalgridlogging == 1 + } + else { + #if SPHERICAL_GRID_LOGGING std::cout << std::endl; #endif } } -inline void SphericalGrid::Iterator::nextOccluder () { - if ( _current != _cell->faces.end() ) { +inline void SphericalGrid::Iterator::nextOccluder() +{ + if (_current != _cell->faces.end()) { do { ++_current; - } while ( _current != _cell->faces.end() && ! testOccluder(false) ); + } while (_current != _cell->faces.end() && !testOccluder(false)); } } -inline void SphericalGrid::Iterator::nextOccludee () { - if ( _current != _cell->faces.end() ) { +inline void SphericalGrid::Iterator::nextOccludee() +{ + if (_current != _cell->faces.end()) { do { ++_current; - } while ( _current != _cell->faces.end() && ! testOccluder(true) ); + } while (_current != _cell->faces.end() && !testOccluder(true)); } } -inline bool SphericalGrid::Iterator::validBeforeTarget () { +inline bool SphericalGrid::Iterator::validBeforeTarget() +{ return _current != _cell->faces.end() && (*_current)->shallowest <= _target[2]; } -inline bool SphericalGrid::Iterator::validAfterTarget () { +inline bool SphericalGrid::Iterator::validAfterTarget() +{ return _current != _cell->faces.end(); } -inline void SphericalGrid::Iterator::markCurrentOccludeeCandidate(real depth) { - #if sphericalgridlogging == 1 +inline void SphericalGrid::Iterator::markCurrentOccludeeCandidate(real depth) +{ + #if SPHERICAL_GRID_LOGGING std::cout << "\t\tFound occludeeCandidate at depth " << depth << std::endl; #endif _occludeeCandidate = _current; @@ -322,18 +331,18 @@ inline void SphericalGrid::Iterator::markCurrentOccludeeCandidate(real depth) { _foundOccludee = true; } -inline WFace* SphericalGrid::Iterator::getWFace() const { +inline WFace *SphericalGrid::Iterator::getWFace() const +{ return (*_current)->face; } -inline Polygon3r* SphericalGrid::Iterator::getCameraSpacePolygon() { +inline Polygon3r *SphericalGrid::Iterator::getCameraSpacePolygon() +{ return &((*_current)->cameraSpacePolygon); } inline SphericalGrid::OccluderData::OccluderData (OccluderSource& source, Polygon3r& p) - : poly(p), - cameraSpacePolygon(source.getCameraSpacePolygon()), - face(source.getWFace()) +: 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 @@ -343,17 +352,18 @@ inline SphericalGrid::OccluderData::OccluderData (OccluderSource& source, Polygo // 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 i = 0; i < 2; ++i ) { + for (unsigned int i = 0; i < 2; ++i) { real t = cameraSpacePolygon.getVertices()[i].norm(); - if ( t > deepest ) { + if (t > deepest) { deepest = t; } } } -inline void SphericalGrid::Cell::checkAndInsert(OccluderSource& source, Polygon3r& poly, OccluderData*& occluder) { - if ( GridHelpers::insideProscenium (boundary, poly) ) { - if ( occluder == NULL) { +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); @@ -362,7 +372,8 @@ inline void SphericalGrid::Cell::checkAndInsert(OccluderSource& source, Polygon3 } } -inline bool SphericalGrid::insertOccluder(OccluderSource& source, OccluderData*& occluder) { +inline bool SphericalGrid::insertOccluder(OccluderSource& source, OccluderData*& occluder) +{ Polygon3r& poly(source.getGridSpacePolygon()); occluder = NULL; @@ -373,9 +384,9 @@ inline bool SphericalGrid::insertOccluder(OccluderSource& source, OccluderData*& getCellCoordinates(bbMin, startX, startY); getCellCoordinates(bbMax, endX, endY); - for ( unsigned i = startX; i <= endX; ++i ) { - for ( unsigned j = startY; j <= endY; ++j ) { - if ( _cells[i * _cellsY + j] != NULL ) { + 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); } } @@ -384,5 +395,4 @@ inline bool SphericalGrid::insertOccluder(OccluderSource& source, OccluderData*& return occluder != NULL; } -#endif // SPHERICALGRID_H - +#endif // __FREESTYLE_SPHERICAL_GRID_H__ |