diff options
Diffstat (limited to 'source/blender/freestyle/intern/geometry/Grid.h')
| -rw-r--r-- | source/blender/freestyle/intern/geometry/Grid.h | 657 |
1 files changed, 321 insertions, 336 deletions
diff --git a/source/blender/freestyle/intern/geometry/Grid.h b/source/blender/freestyle/intern/geometry/Grid.h index a490646ff51..40bd0911c9c 100644 --- a/source/blender/freestyle/intern/geometry/Grid.h +++ b/source/blender/freestyle/intern/geometry/Grid.h @@ -1,49 +1,54 @@ -// -// Filename : Grid.h -// Author(s) : Stephane Grabli -// Purpose : Base class to define a cell grid surrounding -// the bounding box of the scene -// Date of creation : 30/07/2002 -// -/////////////////////////////////////////////////////////////////////////////// +/* + * ***** 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 __GRID_H__ +#define __GRID_H__ -// -// 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. -// -/////////////////////////////////////////////////////////////////////////////// +/** \file blender/freestyle/intern/geometry/Grid.h + * \ingroup freestyle + * \brief Base class to define a cell grid surrounding the bounding box of the scene + * \author Stephane Grabli + * \date 30/07/2002 + */ + +#include <cstring> // for memset +#include <float.h> +#include <vector> -#ifndef GRID_H -# define GRID_H +#include "Geom.h" +#include "GeomUtils.h" +#include "Polygon.h" -# include <cstring> // for memset -# include <float.h> -# include <vector> -# include "../system/FreestyleConfig.h" -# include "GeomUtils.h" -# include "Geom.h" -# include "Polygon.h" +#include "../system/FreestyleConfig.h" using namespace std; using namespace Geometry; -typedef vector<Polygon3r*> OccludersSet; - +typedef vector<Polygon3r*> OccludersSet; // // Class to define cells used by the regular grid @@ -52,84 +57,102 @@ typedef vector<Polygon3r*> OccludersSet; class LIB_GEOMETRY_EXPORT Cell { - public: - - Cell(Vec3r& orig) { - _orig = orig; - } - - virtual ~Cell() {} - - inline void addOccluder(Polygon3r* o) { - if (o) - _occluders.push_back(o); - } - - inline const Vec3r& getOrigin() { - return _orig; - } - - inline OccludersSet& getOccluders() { - return _occluders; - } - - private: - - Vec3r _orig; - OccludersSet _occluders; +public: + Cell(Vec3r& orig) { + _orig = orig; + } + + virtual ~Cell() {} + + inline void addOccluder(Polygon3r* o) { + if (o) + _occluders.push_back(o); + } + + inline const Vec3r& getOrigin() { + return _orig; + } + + inline OccludersSet& getOccluders() { + return _occluders; + } + +private: + Vec3r _orig; + OccludersSet _occluders; }; -class GridVisitor{ +class GridVisitor +{ public: virtual ~GridVisitor() {}; //soc - virtual void discoverCell(Cell *cell) {} - virtual void examineOccluder(Polygon3r *occ) {} - virtual void finishCell(Cell *cell) {} - virtual bool stop() {return false;} + + virtual void discoverCell(Cell *cell) {} + + virtual void examineOccluder(Polygon3r *occ) {} + + virtual void finishCell(Cell *cell) {} + + virtual bool stop() { + return false; + } }; -/*! Gathers all the occluders belonging to the cells - * traversed by the ray */ -class allOccludersGridVisitor : public GridVisitor{ +/*! Gathers all the occluders belonging to the cells traversed by the ray */ +class allOccludersGridVisitor : public GridVisitor +{ public: - allOccludersGridVisitor(OccludersSet& occluders) - :GridVisitor(), occluders_(occluders){} - virtual void examineOccluder(Polygon3r *occ); + allOccludersGridVisitor(OccludersSet& occluders) : GridVisitor(), occluders_(occluders) {} + + virtual void examineOccluder(Polygon3r *occ); + + OccludersSet& occluders() { + return occluders_; + } - OccludersSet& occluders() {return occluders_;} - void clear() {occluders_.clear();} + void clear() { + occluders_.clear(); + } private: - OccludersSet& occluders_; + OccludersSet& occluders_; }; -/*! Finds the first intersection and breaks. The occluder and - * the intersection information are stored and accessible. +/*! Finds the first intersection and breaks. + * The occluder and the intersection information are stored and accessible. */ -class firstIntersectionGridVisitor : public GridVisitor { - +class firstIntersectionGridVisitor : public GridVisitor +{ //soc - changed order to remove warnings public: - double u_, v_, t_; + double u_, v_, t_; + private: - Polygon3r *occluder_; + Polygon3r *occluder_; Vec3r ray_org_, ray_dir_, cell_size_; - Cell * current_cell_; + Cell *current_cell_; public: - firstIntersectionGridVisitor(const Vec3r& ray_org, const Vec3r& ray_dir, const Vec3r& cell_size) : - GridVisitor(), u_(0),v_(0),t_(DBL_MAX), - occluder_(0), - ray_org_(ray_org), ray_dir_(ray_dir), cell_size_(cell_size), - current_cell_(0) {} - virtual ~firstIntersectionGridVisitor() {} - - virtual void discoverCell(Cell *cell) {current_cell_=cell;} - virtual void examineOccluder(Polygon3r *occ); - virtual bool stop(); - - Polygon3r * occluder() {return occluder_;} + firstIntersectionGridVisitor(const Vec3r& ray_org, const Vec3r& ray_dir, const Vec3r& cell_size) : + GridVisitor(), u_(0),v_(0),t_(DBL_MAX), occluder_(0), ray_org_(ray_org), ray_dir_(ray_dir), + cell_size_(cell_size), current_cell_(0) + { + } + + virtual ~firstIntersectionGridVisitor() {} + + virtual void discoverCell(Cell *cell) { + current_cell_ = cell; + } + + virtual void examineOccluder(Polygon3r *occ); + + virtual bool stop(); + + Polygon3r *occluder() { + return occluder_; + } }; // @@ -140,236 +163,197 @@ public: class LIB_GEOMETRY_EXPORT Grid { public: - - /*! Builds a Grid - * Must be followed by a call to configure() - */ - Grid() {} - - virtual ~Grid() { - clear(); - } - - /*! clears the grid - * Deletes all the cells, clears the hashtable, - * resets size, size of cell, number of cells. - */ - virtual void clear(); - - /*! Sets the different parameters of the grid - * orig - * The grid origin - * size - * The grid's dimensions - * nb - * The number of cells of the grid - */ - virtual void configure(const Vec3r& orig, const Vec3r& size, unsigned nb); - - /*! returns a vector of integer containing the - * coordinates of the cell containing the point - * passed as argument - * p - * The point for which we're looking the cell - */ - inline void getCellCoordinates(const Vec3r& p, Vec3u& res) { - int tmp; - for (int i = 0; i < 3; i++) { - tmp = (int)((p[i] - _orig[i]) / _cell_size[i]); - if (tmp < 0) - res[i] = 0; - else if ((unsigned)tmp >= _cells_nb[i]) - res[i] = _cells_nb[i] - 1; - else - res[i] = tmp; - } - } - - /*! Fills the case corresponding to coord with the cell */ - virtual void fillCell(const Vec3u& coord, Cell& cell) = 0; - - /*! returns the cell whose coordinates - * are pased as argument - */ - virtual Cell* getCell(const Vec3u& coord) = 0; - - /*! returns the cell containing the point - * passed as argument. If the cell is empty - * (contains no occluder), NULL is returned - * p - * The point for which we're looking the cell - */ - inline Cell* getCell(const Vec3r& p) { - Vec3u coord; - getCellCoordinates(p, coord); - return getCell(coord); - } - - /*! Retrieves the x,y,z coordinates of the origin of the cell whose coordinates (i,j,k) - * is passed as argument - * cell_coord - * i,j,k integer coordinates for the cell - * orig - * x,y,x vector to be filled in with the cell origin's coordinates - */ - inline void getCellOrigin(const Vec3u& cell_coord, Vec3r& orig) { - for (unsigned i = 0; i < 3; i++) - orig[i] = _orig[i] + cell_coord[i] * _cell_size[i]; - } - - /*! Retrieves the box corresponding to the cell whose coordinates - * are passed as argument. - * cell_coord - * i,j,k integer coordinates for the cell - * min_out - * The min x,y,x vector of the box. Filled in by the method. - * max_out - * The max x,y,z coordinates of the box. Filled in by the method. - */ - inline void getCellBox(const Vec3u& cell_coord, Vec3r& min_out, Vec3r& max_out) { - getCellOrigin(cell_coord, min_out); - max_out = min_out + _cell_size; - } - - /*! inserts a convex polygon occluder - * This method is quite coarse insofar as it - * adds all cells intersecting the polygon bounding box - * convex_poly - * The list of 3D points constituing a convex polygon - */ - void insertOccluder(Polygon3r * convex_poly); - - /*! Adds an occluder to the list of occluders */ - void addOccluder(Polygon3r* occluder) { - _occluders.push_back(occluder); - } - - /*! Casts a ray between a starting point and an ending point - * Returns the list of occluders contained - * in the cells intersected by this ray - * Starts with a call to InitRay. - */ - void castRay(const Vec3r& orig, - const Vec3r& end, - OccludersSet& occluders, - unsigned timestamp); - // Prepares to cast ray without generating OccludersSet - void initAcceleratedRay(const Vec3r& orig, - const Vec3r& end, - unsigned timestamp); - - /*! Casts an infinite ray (still finishing at the end of the grid) from a starting point and in a given direction. - * Returns the list of occluders contained - * in the cells intersected by this ray - * Starts with a call to InitRay. - */ - void castInfiniteRay(const Vec3r& orig, - const Vec3r& dir, - OccludersSet& occluders, - unsigned timestamp); - // Prepares to cast ray without generating OccludersSet. - bool initAcceleratedInfiniteRay(const Vec3r& orig, - const Vec3r& dir, - unsigned timestamp); - - /*! Casts an infinite ray (still finishing at the end of the grid) from a starting point and in a given direction. - * Returns the first intersection (occluder,t,u,v) or null. - * Starts with a call to InitRay. - */ - Polygon3r * castRayToFindFirstIntersection(const Vec3r& orig, - const Vec3r& dir, - double& t, - double& u, - double& v, - unsigned timestamp); - - - /*! Init all structures and values for computing - * the cells intersected by this new ray - */ - void initRay (const Vec3r &orig, - const Vec3r& end, - unsigned timestamp); - - /*! Init all structures and values for computing - * the cells intersected by this infinite ray. - * Returns false if the ray doesn't intersect the - * grid. - */ - bool initInfiniteRay (const Vec3r &orig, - const Vec3r& dir, - unsigned timestamp); - - - /*! Accessors */ - inline const Vec3r& getOrigin() const { - return _orig; - } - inline Vec3r gridSize() const { - return _size; - } - inline Vec3r getCellSize() const { - return _cell_size; - } -//ARB profiling only: - inline OccludersSet* getOccluders() { - return &_occluders; - } - - void displayDebug() { - cerr << "Cells nb : " << _cells_nb << endl; - cerr << "Cell size : " << _cell_size << endl; - cerr << "Origin : " << _orig << endl; - cerr << "Occluders nb : " << _occluders.size() << endl; - } - - protected: - - /*! Core of castRay and castInfiniteRay, find occluders - * along the given ray - */ - inline void castRayInternal(GridVisitor& visitor) { - Cell* current_cell = NULL; - do { - current_cell = getCell(_current_cell); - if (current_cell){ - visitor.discoverCell(current_cell); - OccludersSet& occluders = current_cell->getOccluders(); // FIXME: I had forgotten the ref & - for (OccludersSet::iterator it = occluders.begin(); - it != occluders.end(); - it++) { - if ((unsigned long)(*it)->userdata2 != _timestamp) { - (*it)->userdata2 = (void*)_timestamp; - visitor.examineOccluder(*it); - } - } - visitor.finishCell(current_cell); - } - } while ((!visitor.stop()) && (nextRayCell(_current_cell, _current_cell))); - } - - - /*! returns the cell next to the cell - * passed as argument. - */ - bool nextRayCell(Vec3u& current_cell, Vec3u& next_cell); - - unsigned _timestamp; - - Vec3u _cells_nb; // number of cells for x,y,z axis - Vec3r _cell_size; // cell x,y,z dimensions - Vec3r _size; // grid x,y,x dimensions - Vec3r _orig; // grid origin - - Vec3r _ray_dir; // direction vector for the ray - Vec3u _current_cell; // The current cell being processed (designated by its 3 coordinates) - Vec3r _pt; // Points corresponding to the incoming and outgoing intersections - // of one cell with the ray - real _t_end; // To know when we are at the end of the ray - real _t; - - //OccludersSet _ray_occluders; // Set storing the occluders contained in the cells traversed by a ray - OccludersSet _occluders; // List of all occluders inserted in the grid + /*! Builds a Grid. Must be followed by a call to configure() */ + Grid() {} + + virtual ~Grid() { + clear(); + } + + /*! clears the grid + * Deletes all the cells, clears the hashtable, resets size, size of cell, number of cells. + */ + virtual void clear(); + + /*! Sets the different parameters of the grid + * orig + * The grid origin + * size + * The grid's dimensions + * nb + * The number of cells of the grid + */ + virtual void configure(const Vec3r& orig, const Vec3r& size, unsigned nb); + + /*! returns a vector of integer containing the coordinates of the cell containing the point passed as argument + * p + * The point for which we're looking the cell + */ + inline void getCellCoordinates(const Vec3r& p, Vec3u& res) { + int tmp; + for (int i = 0; i < 3; i++) { + tmp = (int)((p[i] - _orig[i]) / _cell_size[i]); + if (tmp < 0) + res[i] = 0; + else if ((unsigned int)tmp >= _cells_nb[i]) + res[i] = _cells_nb[i] - 1; + else + res[i] = tmp; + } + } + + /*! Fills the case corresponding to coord with the cell */ + virtual void fillCell(const Vec3u& coord, Cell& cell) = 0; + + /*! returns the cell whose coordinates are pased as argument */ + virtual Cell* getCell(const Vec3u& coord) = 0; + + /*! returns the cell containing the point passed as argument. If the cell is empty (contains no occluder), + * NULL is returned + * p + * The point for which we're looking the cell + */ + inline Cell* getCell(const Vec3r& p) { + Vec3u coord; + getCellCoordinates(p, coord); + return getCell(coord); + } + + /*! Retrieves the x,y,z coordinates of the origin of the cell whose coordinates (i,j,k) is passed as argument + * cell_coord + * i,j,k integer coordinates for the cell + * orig + * x,y,x vector to be filled in with the cell origin's coordinates + */ + inline void getCellOrigin(const Vec3u& cell_coord, Vec3r& orig) { + for (unsigned int i = 0; i < 3; i++) + orig[i] = _orig[i] + cell_coord[i] * _cell_size[i]; + } + + /*! Retrieves the box corresponding to the cell whose coordinates are passed as argument. + * cell_coord + * i,j,k integer coordinates for the cell + * min_out + * The min x,y,x vector of the box. Filled in by the method. + * max_out + * The max x,y,z coordinates of the box. Filled in by the method. + */ + inline void getCellBox(const Vec3u& cell_coord, Vec3r& min_out, Vec3r& max_out) { + getCellOrigin(cell_coord, min_out); + max_out = min_out + _cell_size; + } + + /*! inserts a convex polygon occluder + * This method is quite coarse insofar as it adds all cells intersecting the polygon bounding box + * convex_poly + * The list of 3D points constituing a convex polygon + */ + void insertOccluder(Polygon3r * convex_poly); + + /*! Adds an occluder to the list of occluders */ + void addOccluder(Polygon3r* occluder) { + _occluders.push_back(occluder); + } + + /*! Casts a ray between a starting point and an ending point + * Returns the list of occluders contained in the cells intersected by this ray + * Starts with a call to InitRay. + */ + void castRay(const Vec3r& orig, const Vec3r& end, OccludersSet& occluders, unsigned timestamp); + + // Prepares to cast ray without generating OccludersSet + void initAcceleratedRay(const Vec3r& orig, const Vec3r& end, unsigned timestamp); + + /*! Casts an infinite ray (still finishing at the end of the grid) from a starting point and in a given direction. + * Returns the list of occluders contained in the cells intersected by this ray + * Starts with a call to InitRay. + */ + void castInfiniteRay(const Vec3r& orig, const Vec3r& dir, OccludersSet& occluders, unsigned timestamp); + + // Prepares to cast ray without generating OccludersSet. + bool initAcceleratedInfiniteRay(const Vec3r& orig, const Vec3r& dir, unsigned timestamp); + + /*! Casts an infinite ray (still finishing at the end of the grid) from a starting point and in a given direction. + * Returns the first intersection (occluder,t,u,v) or null. + * Starts with a call to InitRay. + */ + Polygon3r * castRayToFindFirstIntersection(const Vec3r& orig, const Vec3r& dir, double& t, + double& u, double& v, unsigned timestamp); + + + /*! Init all structures and values for computing the cells intersected by this new ray */ + void initRay(const Vec3r &orig, const Vec3r& end, unsigned timestamp); + + /*! Init all structures and values for computing the cells intersected by this infinite ray. + * Returns false if the ray doesn't intersect the grid. + */ + bool initInfiniteRay(const Vec3r &orig, const Vec3r& dir, unsigned timestamp); + + + /*! Accessors */ + inline const Vec3r& getOrigin() const { + return _orig; + } + + inline Vec3r gridSize() const { + return _size; + } + + inline Vec3r getCellSize() const { + return _cell_size; + } + + //ARB profiling only: + inline OccludersSet* getOccluders() { + return &_occluders; + } + + void displayDebug() { + cerr << "Cells nb : " << _cells_nb << endl; + cerr << "Cell size : " << _cell_size << endl; + cerr << "Origin : " << _orig << endl; + cerr << "Occluders nb : " << _occluders.size() << endl; + } + +protected: + /*! Core of castRay and castInfiniteRay, find occluders along the given ray */ + inline void castRayInternal(GridVisitor& visitor) { + Cell *current_cell = NULL; + do { + current_cell = getCell(_current_cell); + if (current_cell) { + visitor.discoverCell(current_cell); + OccludersSet& occluders = current_cell->getOccluders(); // FIXME: I had forgotten the ref & + for (OccludersSet::iterator it = occluders.begin(); it != occluders.end(); it++) { + if ((unsigned long)(*it)->userdata2 != _timestamp) { + (*it)->userdata2 = (void*)_timestamp; + visitor.examineOccluder(*it); + } + } + visitor.finishCell(current_cell); + } + } while ((!visitor.stop()) && (nextRayCell(_current_cell, _current_cell))); + } + + + /*! returns the cell next to the cell passed as argument. */ + bool nextRayCell(Vec3u& current_cell, Vec3u& next_cell); + + unsigned int _timestamp; + + Vec3u _cells_nb; // number of cells for x,y,z axis + Vec3r _cell_size; // cell x,y,z dimensions + Vec3r _size; // grid x,y,x dimensions + Vec3r _orig; // grid origin + + Vec3r _ray_dir; // direction vector for the ray + Vec3u _current_cell; // The current cell being processed (designated by its 3 coordinates) + Vec3r _pt; // Points corresponding to the incoming and outgoing intersections of one cell with the ray + real _t_end; // To know when we are at the end of the ray + real _t; + + //OccludersSet _ray_occluders; // Set storing the occluders contained in the cells traversed by a ray + OccludersSet _occluders; // List of all occluders inserted in the grid }; // @@ -378,15 +362,16 @@ public: /////////////////////////////////////////////////////////////////////////////// class VirtualOccludersSet { - public: - VirtualOccludersSet(Grid& _grid) : grid (_grid) {}; - Polygon3r* begin(); - Polygon3r* next(); - Polygon3r* next(bool stopOnNewCell); - private: - Polygon3r* firstOccluderFromNextCell(); - Grid& grid; - OccludersSet::iterator it, end; +public: + VirtualOccludersSet(Grid& _grid) : grid (_grid) {}; + Polygon3r* begin(); + Polygon3r* next(); + Polygon3r* next(bool stopOnNewCell); + +private: + Polygon3r* firstOccluderFromNextCell(); + Grid& grid; + OccludersSet::iterator it, end; }; -#endif // GRID_H +#endif // __GRID_H__ |