diff options
44 files changed, 4477 insertions, 182 deletions
diff --git a/release/scripts/ui/properties_render.py b/release/scripts/ui/properties_render.py index d09755a3f3c..14f940529e0 100644 --- a/release/scripts/ui/properties_render.py +++ b/release/scripts/ui/properties_render.py @@ -193,6 +193,7 @@ class RENDER_PT_freestyle(RenderButtonsPanel, bpy.types.Panel): split = layout.split() col = split.column() + col.prop(freestyle, "raycasting_algorithm", text="Raycasting Algorithm") col.prop(freestyle, "mode", text="Control Mode") if freestyle.mode == "EDITOR": diff --git a/source/blender/freestyle/intern/application/Controller.cpp b/source/blender/freestyle/intern/application/Controller.cpp index ad9db9422ba..37f29278ea7 100755 --- a/source/blender/freestyle/intern/application/Controller.cpp +++ b/source/blender/freestyle/intern/application/Controller.cpp @@ -40,7 +40,6 @@ #include "../scene_graph/VertexRep.h" #include "../winged_edge/WXEdgeBuilder.h" #include "../scene_graph/ScenePrettyPrinter.h" -#include "../winged_edge/WFillGrid.h" #include "../view_map/ViewMapTesselator.h" #include "../stroke/StrokeTesselator.h" @@ -60,6 +59,8 @@ #include "../blender_interface/BlenderStrokeRenderer.h" #include "../blender_interface/BlenderStyleModule.h" +#include "DNA_freestyle_types.h" + #ifdef __cplusplus extern "C" { #endif @@ -105,8 +106,8 @@ Controller::Controller() _Canvas = 0; - _VisibilityAlgo = ViewMapBuilder::ray_casting; - //_VisibilityAlgo = ViewMapBuilder::ray_casting_fast; + _VisibilityAlgo = ViewMapBuilder::ray_casting_adaptive_traditional; + //_VisibilityAlgo = ViewMapBuilder::ray_casting; _Canvas = new AppCanvas; @@ -250,29 +251,6 @@ int Controller::LoadMesh(Render *re, SceneRenderLayer* srl) printf("WEdge building : %lf\n", _Chrono.stop()); - _Chrono.start(); - - _Grid.clear(); - Vec3r size; - for(unsigned int i=0; i<3; i++) - { - size[i] = fabs(_RootNode->bbox().getMax()[i] - _RootNode->bbox().getMin()[i]); - size[i] += size[i]/10.0; // let make the grid 1/10 bigger to avoid numerical errors while computing triangles/cells intersections - if(size[i]==0){ - cout << "Warning: the bbox size is 0 in dimension "<<i<<endl; - } - } - _Grid.configure(Vec3r(_RootNode->bbox().getMin() - size / 20.0), size, - _SceneNumFaces); - - // Fill in the grid: - WFillGrid fillGridRenderer(&_Grid, _winged_edge); - fillGridRenderer.fillGrid(); - - printf("Grid building : %lf\n", _Chrono.stop()); - - // DEBUG - _Grid.displayDebug(); // // _pView->setDebug(_DebugNode); @@ -482,6 +460,7 @@ void Controller::ComputeViewMap() edgeDetector.enableRidgesAndValleysFlag(_ComputeRidges); edgeDetector.enableSuggestiveContours(_ComputeSuggestive); edgeDetector.enableMaterialBoundaries(_ComputeMaterialBoundaries); + edgeDetector.enableFaceSmoothness(_EnableFaceSmoothness); edgeDetector.setCreaseAngle(_creaseAngle); edgeDetector.setSphereRadius(_sphereRadius); edgeDetector.setSuggestiveContourKrDerivativeEpsilon(_suggestiveContourKrDerivativeEpsilon); @@ -509,7 +488,7 @@ void Controller::ComputeViewMap() cout << "\n=== Building the view map ===" << endl; _Chrono.start(); // Build View Map - _ViewMap = vmBuilder.BuildViewMap(*_winged_edge, _VisibilityAlgo, _EPSILON); + _ViewMap = vmBuilder.BuildViewMap(*_winged_edge, _VisibilityAlgo, _EPSILON, _RootNode->bbox(), _SceneNumFaces); _ViewMap->setScene3dBBox(_RootNode->bbox()); printf("ViewMap edge count : %i\n", _ViewMap->viewedges_size() ); @@ -649,6 +628,57 @@ void Controller::toggleVisibilityAlgo() } } +void Controller::setVisibilityAlgo(int algo) +{ + switch (algo) { + case FREESTYLE_ALGO_REGULAR: + _VisibilityAlgo = ViewMapBuilder::ray_casting; + break; + case FREESTYLE_ALGO_FAST: + _VisibilityAlgo = ViewMapBuilder::ray_casting_fast; + break; + case FREESTYLE_ALGO_VERYFAST: + _VisibilityAlgo = ViewMapBuilder::ray_casting_very_fast; + break; + case FREESTYLE_ALGO_CULLED_ADAPTIVE_TRADITIONAL: + _VisibilityAlgo = ViewMapBuilder::ray_casting_culled_adaptive_traditional; + break; + case FREESTYLE_ALGO_ADAPTIVE_TRADITIONAL: + _VisibilityAlgo = ViewMapBuilder::ray_casting_adaptive_traditional; + break; + case FREESTYLE_ALGO_CULLED_ADAPTIVE_CUMULATIVE: + _VisibilityAlgo = ViewMapBuilder::ray_casting_culled_adaptive_cumulative; + break; + case FREESTYLE_ALGO_ADAPTIVE_CUMULATIVE: + _VisibilityAlgo = ViewMapBuilder::ray_casting_adaptive_cumulative; + break; + } +} + +int Controller::getVisibilityAlgo() +{ + switch (_VisibilityAlgo) { + case ViewMapBuilder::ray_casting: + return FREESTYLE_ALGO_REGULAR; + case ViewMapBuilder::ray_casting_fast: + return FREESTYLE_ALGO_FAST; + case ViewMapBuilder::ray_casting_very_fast: + return FREESTYLE_ALGO_VERYFAST; + case ViewMapBuilder::ray_casting_culled_adaptive_traditional: + return FREESTYLE_ALGO_CULLED_ADAPTIVE_TRADITIONAL; + case ViewMapBuilder::ray_casting_adaptive_traditional: + return FREESTYLE_ALGO_ADAPTIVE_TRADITIONAL; + case ViewMapBuilder::ray_casting_culled_adaptive_cumulative: + return FREESTYLE_ALGO_CULLED_ADAPTIVE_CUMULATIVE; + case ViewMapBuilder::ray_casting_adaptive_cumulative: + return FREESTYLE_ALGO_ADAPTIVE_CUMULATIVE; + } + + // ray_casting_adaptive_traditional is the most exact replacement + // for legacy code + return FREESTYLE_ALGO_ADAPTIVE_TRADITIONAL; +} + void Controller::setQuantitativeInvisibility(bool iBool) { _EnableQI = iBool; @@ -659,6 +689,16 @@ bool Controller::getQuantitativeInvisibility() const return _EnableQI; } +void Controller::setFaceSmoothness(bool iBool) +{ + _EnableFaceSmoothness = iBool; +} + +bool Controller::getFaceSmoothness() const +{ + return _EnableFaceSmoothness; +} + void Controller::setComputeRidgesAndValleysFlag(bool iBool){ _ComputeRidges = iBool; } diff --git a/source/blender/freestyle/intern/application/Controller.h b/source/blender/freestyle/intern/application/Controller.h index a278b10a090..4ee79405fa9 100755 --- a/source/blender/freestyle/intern/application/Controller.h +++ b/source/blender/freestyle/intern/application/Controller.h @@ -34,7 +34,6 @@ # include <string> //# include "ConfigIO.h" # include "../geometry/FastGrid.h" -# include "../geometry/HashGrid.h" # include "../system/TimeUtils.h" # include "../system/ProgressBar.h" # include "../system/Precision.h" @@ -115,9 +114,13 @@ public: //Grid& grid() {return _Grid;} void toggleVisibilityAlgo(); + void setVisibilityAlgo(int algo); + int getVisibilityAlgo(); void setQuantitativeInvisibility(bool iBool); // if true, we compute quantitativeInvisibility bool getQuantitativeInvisibility() const; + void setFaceSmoothness(bool iBool); + bool getFaceSmoothness() const; void setComputeRidgesAndValleysFlag(bool b); bool getComputeRidgesAndValleysFlag() const ; @@ -228,6 +231,7 @@ private: string _browser_cmd; bool _EnableQI; + bool _EnableFaceSmoothness; bool _ComputeRidges; bool _ComputeSuggestive; bool _ComputeMaterialBoundaries; diff --git a/source/blender/freestyle/intern/blender_interface/FRS_freestyle.cpp b/source/blender/freestyle/intern/blender_interface/FRS_freestyle.cpp index 2df05cd8970..2a82f4ab812 100644 --- a/source/blender/freestyle/intern/blender_interface/FRS_freestyle.cpp +++ b/source/blender/freestyle/intern/blender_interface/FRS_freestyle.cpp @@ -234,12 +234,15 @@ extern "C" { } // set parameters + controller->setFaceSmoothness( (config->flags & FREESTYLE_FACE_SMOOTHNESS_FLAG) ? true : false); controller->setCreaseAngle( config->crease_angle ); controller->setSphereRadius( config->sphere_radius ); controller->setSuggestiveContourKrDerivativeEpsilon( config->dkr_epsilon ) ; + controller->setVisibilityAlgo( config->raycasting_algorithm ); cout << "Crease angle : " << controller->getCreaseAngle() << endl; cout << "Sphere radius : " << controller->getSphereRadius() << endl; + cout << "Face smoothness : " << (controller->getFaceSmoothness() ? "enabled" : "disabled") << endl; cout << "Redges and valleys : " << (controller->getComputeRidgesAndValleysFlag() ? "enabled" : "disabled") << endl; cout << "Suggestive contours : " << (controller->getComputeSuggestiveContoursFlag() ? "enabled" : "disabled") << endl; cout << "Suggestive contour Kr derivative epsilon : " << controller->getSuggestiveContourKrDerivativeEpsilon() << endl; @@ -406,6 +409,8 @@ extern "C" { config->crease_angle = 134.43f; config->linesets.first = config->linesets.last = NULL; + + config->raycasting_algorithm = FREESTYLE_ALGO_REGULAR; } void FRS_free_freestyle_config( SceneRenderLayer* srl ) diff --git a/source/blender/freestyle/intern/geometry/GeomUtils.cpp b/source/blender/freestyle/intern/geometry/GeomUtils.cpp index 2169bce0364..853f8cf82b5 100755 --- a/source/blender/freestyle/intern/geometry/GeomUtils.cpp +++ b/source/blender/freestyle/intern/geometry/GeomUtils.cpp @@ -370,9 +370,9 @@ namespace GeomUtils { // Ithaca, New York // wbt@graphics.cornell.edu - bool intersectRayTriangle(Vec3r& orig, Vec3r& dir, - Vec3r& v0, Vec3r& v1, Vec3r& v2, - real& t, real& u, real& v, real epsilon) { + bool intersectRayTriangle(const Vec3r& orig, const Vec3r& dir, + const Vec3r& v0, const Vec3r& v1, const Vec3r& v2, + real& t, real& u, real& v, const real epsilon) { Vec3r edge1, edge2, tvec, pvec, qvec; real det, inv_det; @@ -424,10 +424,10 @@ namespace GeomUtils { } // Intersection between plane and ray, adapted from Graphics Gems, Didier Badouel - intersection_test intersectRayPlane(Vec3r& orig, Vec3r& dir, - Vec3r& norm, real d, + intersection_test intersectRayPlane(const Vec3r& orig, const Vec3r& dir, + const Vec3r& norm, const real d, real& t, - real epsilon) { + const real epsilon) { real denom = norm * dir; if(fabs(denom) <= epsilon) { // plane and ray are parallel @@ -484,10 +484,10 @@ namespace GeomUtils { } // Checks whether 3D points p lies inside or outside of the triangle ABC - bool includePointTriangle(Vec3r& P, - Vec3r& A, - Vec3r& B, - Vec3r& C) { + bool includePointTriangle(const Vec3r& P, + const Vec3r& A, + const Vec3r& B, + const Vec3r& C) { Vec3r AB(B - A); Vec3r BC(C - B); Vec3r CA(A - C); diff --git a/source/blender/freestyle/intern/geometry/GeomUtils.h b/source/blender/freestyle/intern/geometry/GeomUtils.h index 787376108e1..bbbf42b5881 100755 --- a/source/blender/freestyle/intern/geometry/GeomUtils.h +++ b/source/blender/freestyle/intern/geometry/GeomUtils.h @@ -121,20 +121,20 @@ namespace GeomUtils { * adapted from Tomas Möller and Ben Trumbore code. */ LIB_GEOMETRY_EXPORT - bool intersectRayTriangle(Vec3r& orig, Vec3r& dir, - Vec3r& v0, Vec3r& v1, Vec3r& v2, + bool intersectRayTriangle(const Vec3r& orig, const Vec3r& dir, + const Vec3r& v0, const Vec3r& v1, const Vec3r& v2, real& t, // I = orig + t * dir real& u, real& v, // I = (1-u-v)*v0+u*v1+v*v2 - real epsilon = M_EPSILON); // the epsilon to use + const real epsilon = M_EPSILON); // the epsilon to use /*! Intersection between plane and ray * adapted from Graphics Gems, Didier Badouel */ LIB_GEOMETRY_EXPORT - intersection_test intersectRayPlane(Vec3r& orig, Vec3r& dir, // ray origin and direction - Vec3r& norm, real d, // plane's normal and offset (plane = { P / P.N + d = 0 }) + intersection_test intersectRayPlane(const Vec3r& orig, const Vec3r& dir, // ray origin and direction + const Vec3r& norm, const real d, // plane's normal and offset (plane = { P / P.N + d = 0 }) real& t, // I = orig + t * dir - real epsilon = M_EPSILON); // the epsilon to use + const real epsilon = M_EPSILON); // the epsilon to use /*! Intersection Ray-Bounding box (axis aligned). * Adapted from Williams et al, "An Efficient Robust Ray-Box Intersection Algorithm", @@ -151,10 +151,10 @@ namespace GeomUtils { /*! Checks whether 3D point P lies inside or outside of the triangle ABC */ LIB_GEOMETRY_EXPORT - bool includePointTriangle(Vec3r& P, - Vec3r& A, - Vec3r& B, - Vec3r& C); + bool includePointTriangle(const Vec3r& P, + const Vec3r& A, + const Vec3r& B, + const Vec3r& C); LIB_GEOMETRY_EXPORT void transformVertex(const Vec3r& vert, diff --git a/source/blender/freestyle/intern/geometry/Grid.cpp b/source/blender/freestyle/intern/geometry/Grid.cpp index 2477227c410..0096297f48b 100755 --- a/source/blender/freestyle/intern/geometry/Grid.cpp +++ b/source/blender/freestyle/intern/geometry/Grid.cpp @@ -318,6 +318,10 @@ Polygon3r* Grid::castRayToFindFirstIntersection(const Vec3r& orig, } firstIntersectionGridVisitor visitor(orig,dir,_cell_size); castRayInternal(visitor); + // ARB: This doesn't work, because occluders are unordered within any cell + // visitor.occluder() will be an occluder, but we have no guarantee + // it will be the *first* occluder. + // I assume that is the reason this code is not actually used for FindOccludee. occluder = visitor.occluder(); t = visitor.t_; u = visitor.u_; diff --git a/source/blender/freestyle/intern/geometry/Grid.h b/source/blender/freestyle/intern/geometry/Grid.h index e54b7b4d381..a490646ff51 100755 --- a/source/blender/freestyle/intern/geometry/Grid.h +++ b/source/blender/freestyle/intern/geometry/Grid.h @@ -253,6 +253,10 @@ public: 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 @@ -263,6 +267,10 @@ public: 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. @@ -303,6 +311,10 @@ public: inline Vec3r getCellSize() const { return _cell_size; } +//ARB profiling only: + inline OccludersSet* getOccluders() { + return &_occluders; + } void displayDebug() { cerr << "Cells nb : " << _cells_nb << endl; @@ -360,4 +372,21 @@ public: OccludersSet _occluders; // List of all occluders inserted in the grid }; +// +// Class to walk through occluders in grid without building intermediate data structures +// +/////////////////////////////////////////////////////////////////////////////// + +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; +}; + #endif // GRID_H diff --git a/source/blender/freestyle/intern/geometry/GridHelpers.cpp b/source/blender/freestyle/intern/geometry/GridHelpers.cpp new file mode 100644 index 00000000000..dcf24a72efb --- /dev/null +++ b/source/blender/freestyle/intern/geometry/GridHelpers.cpp @@ -0,0 +1,56 @@ +// +// Filename : GridHelpers.cpp +// Author(s) : Alexander Beels +// Purpose : Class to define a cell grid surrounding +// the projected image of a scene +// Date of creation : 2010-12-21 +// +/////////////////////////////////////////////////////////////////////////////// + +// +// 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. +// +/////////////////////////////////////////////////////////////////////////////// + +#include <math.h> +#include "GridHelpers.h" + +void GridHelpers::getDefaultViewProscenium(real viewProscenium[4]) { + // Get proscenium boundary for culling + // bufferZone determines the amount by which the area processed + // should exceed the actual image area. This is intended to + // avoid visible artifacts generated along the proscenium edge. + // Perhaps this is no longer needed now that entire view edges + // are culled at once, since that theoretically should eliminate + // visible artifacts. + // To the extent it is still useful, bufferZone should be put into + // the UI as configurable percentage value + const real bufferZone = 0.05; + // borderZone describes a blank border outside the proscenium, but + // still inside the image area. Only intended for exposing possible + // artifacts along or outside the proscenium edge during debugging. + const real borderZone = 0.0; + viewProscenium[0] = freestyle_viewport[2] * (borderZone - bufferZone); + viewProscenium[1] = freestyle_viewport[2] * (1.0f - borderZone + bufferZone); + viewProscenium[2] = freestyle_viewport[3] * (borderZone - bufferZone); + viewProscenium[3] = freestyle_viewport[3] * (1.0f - borderZone + bufferZone); +} + +GridHelpers::Transform::~Transform () {} + + diff --git a/source/blender/freestyle/intern/geometry/GridHelpers.h b/source/blender/freestyle/intern/geometry/GridHelpers.h new file mode 100644 index 00000000000..b079005c1b5 --- /dev/null +++ b/source/blender/freestyle/intern/geometry/GridHelpers.h @@ -0,0 +1,199 @@ +// +// Filename : GridHelpers.h +// Author(s) : Alexander Beels +// Purpose : Class to define a cell grid surrounding +// the projected image of a scene +// Date of creation : 2010-12-13 +// +/////////////////////////////////////////////////////////////////////////////// + + +// +// 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 GRIDHELPERS_H +#define GRIDHELPERS_H + +#include <vector> +#include "Polygon.h" +#include "../winged_edge/WEdge.h" +#include "FRS_freestyle.h" +#include "GeomUtils.h" + +namespace GridHelpers { + +/*! Computes the distance from a point P to a segment AB */ +template<class T> +T closestPointToSegment(const T& P, const T& A , const T& B, real& distance) { + T AB, AP, BP; + AB = B - A; + AP = P - A; + BP = P - B; + + real c1(AB * AP); + if (c1 <= 0) { + distance = AP.norm(); + return A; // A is closest point + } + + real c2(AB * AB); + if (c2 <= c1) { + distance = BP.norm(); + return B; // B is closest point + } + + real b = c1 / c2; + T Pb, PPb; + Pb = A + b * AB; + PPb = P - Pb; + + distance = PPb.norm(); + return Pb; // closest point lies on AB +} + +inline Vec3r closestPointOnPolygon(const Vec3r& point, const Polygon3r& poly) { + // First cast a ray from the point onto the polygon plane + // If the ray intersects the polygon, then the intersection point + // is the closest point on the polygon + real t, u, v; + if ( poly.rayIntersect(point, poly.getNormal(), t, u, v) ) { + return point + poly.getNormal() * t; + } + + // Otherwise, get the nearest point on each edge, and take the closest + real distance; + Vec3r closest = closestPointToSegment(point, poly.getVertices()[2], poly.getVertices()[0], distance); + for ( unsigned i = 0; i < 2; ++i ) { + real t; + Vec3r p = closestPointToSegment(point, poly.getVertices()[i], poly.getVertices()[i + 1], t); + if ( t < distance ) { + distance = t; + closest = p; + } + } + return closest; +} + +inline real distancePointToPolygon(const Vec3r& point, const Polygon3r& poly) { + // First cast a ray from the point onto the polygon plane + // If the ray intersects the polygon, then the intersection point + // is the closest point on the polygon + real t, u, v; + if ( poly.rayIntersect(point, poly.getNormal(), t, u, v) ) { + return t > 0.0 ? t : -t; + } + + // Otherwise, get the nearest point on each edge, and take the closest + real distance = GeomUtils::distPointSegment(point, poly.getVertices()[2], poly.getVertices()[0]); + for ( unsigned i = 0; i < 2; ++i ) { + real t = GeomUtils::distPointSegment(point, poly.getVertices()[i], poly.getVertices()[i + 1]); + if ( t < distance ) { + distance = t; + } + } + return distance; +} + +class Transform { +public: + virtual ~Transform () =0; + virtual Vec3r operator()(const Vec3r& point) const =0; +}; + +inline bool insideProscenium (const real proscenium[4], const Polygon3r& polygon) { + // N.B. The bounding box check is redundant for inserting occluders into + // cells, because the cell selection code in insertOccluders has already + // guaranteed that the bounding boxes will overlap. + // First check the viewport edges, since they are the easiest case + // Check if the bounding box is entirely outside the proscenium + Vec3r bbMin, bbMax; + polygon.getBBox(bbMin, bbMax); + if ( bbMax[0] < proscenium[0] + || bbMin[0] > proscenium[1] + || bbMax[1] < proscenium[2] + || bbMin[1] > proscenium[3] ) { + return false; + } + + Vec3r boxCenter(proscenium[0] + (proscenium[1] - proscenium[0]) / 2.0, proscenium[2] + (proscenium[3] - proscenium[2]) / 2.0, 0.0); + Vec3r boxHalfSize((proscenium[1] - proscenium[0]) / 2.0, (proscenium[3] - proscenium[2]) / 2.0, 1.0); + Vec3r triverts[3] = { Vec3r(polygon.getVertices()[0][0], polygon.getVertices()[0][1], 0.0), Vec3r(polygon.getVertices()[1][0], polygon.getVertices()[1][1], 0.0), Vec3r(polygon.getVertices()[2][0], polygon.getVertices()[2][1], 0.0) }; + return GeomUtils::overlapTriangleBox(boxCenter, boxHalfSize, triverts); +} + +inline vector<Vec3r> enumerateVertices(const vector<WOEdge*>& fedges) { + vector<Vec3r> points; + // Iterate over vertices, storing projections in points + for(vector<WOEdge*>::const_iterator woe=fedges.begin(), woend=fedges.end(); woe!=woend; woe++) { + points.push_back((*woe)->GetaVertex()->GetVertex()); + } + + return points; +} + +void getDefaultViewProscenium(real viewProscenium[4]); + +inline void expandProscenium (real proscenium[4], const Polygon3r& polygon) { + Vec3r bbMin, bbMax; + polygon.getBBox(bbMin, bbMax); + + const real epsilon = 1.0e-6; + + if ( bbMin[0] <= proscenium[0] ) { + proscenium[0] = bbMin[0] - epsilon; + } + + if ( bbMin[1] <= proscenium[2] ) { + proscenium[2] = bbMin[1] - epsilon; + } + + if ( bbMax[0] >= proscenium[1] ) { + proscenium[1] = bbMax[0] + epsilon; + } + + if ( bbMax[1] >= proscenium[3] ) { + proscenium[3] = bbMax[1] + epsilon; + } +} + +inline void expandProscenium (real proscenium[4], const Vec3r& point) { + const real epsilon = 1.0e-6; + + if ( point[0] <= proscenium[0] ) { + proscenium[0] = point[0] - epsilon; + } + + if ( point[1] <= proscenium[2] ) { + proscenium[2] = point[1] - epsilon; + } + + if ( point[0] >= proscenium[1] ) { + proscenium[1] = point[0] + epsilon; + } + + if ( point[1] >= proscenium[3] ) { + proscenium[3] = point[1] + epsilon; + } +} + +}; + +#endif // GRIDHELPERS_H + diff --git a/source/blender/freestyle/intern/geometry/Polygon.h b/source/blender/freestyle/intern/geometry/Polygon.h index f9c4c78d424..911804d80f7 100755 --- a/source/blender/freestyle/intern/geometry/Polygon.h +++ b/source/blender/freestyle/intern/geometry/Polygon.h @@ -175,7 +175,6 @@ class Polygon class Polygon3r : public Polygon<Vec3r> { public: - inline Polygon3r() : Polygon<Vec3r>() {} inline Polygon3r(const vector<Vec3r>& vertices, @@ -183,7 +182,7 @@ class Polygon3r : public Polygon<Vec3r> setNormal(normal); } - inline Polygon3r(const Polygon3r& poly) : Polygon<Vec3r>(poly) {} + inline Polygon3r(const Polygon3r& poly) : Polygon<Vec3r>(poly), _normal(poly._normal) {} virtual ~Polygon3r() {} @@ -191,13 +190,13 @@ class Polygon3r : public Polygon<Vec3r> _normal = normal; } - Vec3r getNormal() const { + inline Vec3r getNormal() const { return _normal; } /*! Check whether the Polygon intersects with the ray or not */ - inline bool rayIntersect(Vec3r& orig, Vec3r& dir, - real& t, real& u, real& v, real epsilon = M_EPSILON) { + inline bool rayIntersect(const Vec3r& orig, const Vec3r& dir, + real& t, real& u, real& v, real epsilon = M_EPSILON) const { // if (_vertices.size() < 3) // return false; return GeomUtils::intersectRayTriangle(orig, dir, diff --git a/source/blender/freestyle/intern/geometry/SweepLine.h b/source/blender/freestyle/intern/geometry/SweepLine.h index cf4c86d006d..deecf3c5485 100755 --- a/source/blender/freestyle/intern/geometry/SweepLine.h +++ b/source/blender/freestyle/intern/geometry/SweepLine.h @@ -210,17 +210,6 @@ public: { delete (*i); } - _Intersections.clear(); - - for(typename vector<Segment<T,Point>* >::iterator ie=_IntersectedEdges.begin(),ieend=_IntersectedEdges.end(); - ie!=ieend; - ie++) - { - delete (*ie); - } - _IntersectedEdges.clear(); - - _set.clear(); } diff --git a/source/blender/freestyle/intern/geometry/normal_cycle.cpp b/source/blender/freestyle/intern/geometry/normal_cycle.cpp index b456ced8331..3a697d54731 100755 --- a/source/blender/freestyle/intern/geometry/normal_cycle.cpp +++ b/source/blender/freestyle/intern/geometry/normal_cycle.cpp @@ -82,22 +82,6 @@ namespace OGF { } - void NormalCycle::accumulate_dihedral_angle( - const Vec3r& edge, double beta, double neigh_area - ) { - Vec3r e = edge ; - e.normalize() ; - - double s = edge.norm() * beta * neigh_area ; - - M_[0] += s * e.x() * e.x() ; - M_[1] += s * e.x() * e.y() ; - M_[2] += s * e.y() * e.y() ; - M_[3] += s * e.x() * e.z() ; - M_[4] += s * e.y() * e.z() ; - M_[5] += s * e.z() * e.z() ; - } - //_________________________________________________________ } diff --git a/source/blender/freestyle/intern/geometry/normal_cycle.h b/source/blender/freestyle/intern/geometry/normal_cycle.h index 41fbf7b3fab..cdf00a0b4c5 100755 --- a/source/blender/freestyle/intern/geometry/normal_cycle.h +++ b/source/blender/freestyle/intern/geometry/normal_cycle.h @@ -90,6 +90,19 @@ template <class T> inline void ogf_swap(T& x, T& y) { int i_[3] ; } ; + inline void NormalCycle::accumulate_dihedral_angle( + const Vec3r& edge, const double beta, double neigh_area + ) { + double s = beta * neigh_area / edge.norm(); + + M_[0] += s * edge.x() * edge.x() ; + M_[1] += s * edge.x() * edge.y() ; + M_[2] += s * edge.y() * edge.y() ; + M_[3] += s * edge.x() * edge.z() ; + M_[4] += s * edge.y() * edge.z() ; + M_[5] += s * edge.z() * edge.z() ; + } + //_________________________________________________________ } diff --git a/source/blender/freestyle/intern/stroke/StyleModule.h b/source/blender/freestyle/intern/stroke/StyleModule.h index 5bdb54cf16c..c97a8d7f999 100755 --- a/source/blender/freestyle/intern/stroke/StyleModule.h +++ b/source/blender/freestyle/intern/stroke/StyleModule.h @@ -71,12 +71,14 @@ public: if( interpret() ) { cerr << "Error: interpretation failed" << endl; + Operators::reset(); return NULL; } Operators::StrokesContainer* strokes_set = Operators::getStrokesSet(); if( strokes_set->empty() ) { - cerr << "Error: strokes set empty" << endl; + cerr << "Error: strokes set empty" << endl; + Operators::reset(); return NULL; } @@ -86,6 +88,8 @@ public: ++it) sl->AddStroke(*it); + Operators::reset(); + return sl; } diff --git a/source/blender/freestyle/intern/system/PointerSequence.h b/source/blender/freestyle/intern/system/PointerSequence.h new file mode 100644 index 00000000000..72c6aa458fd --- /dev/null +++ b/source/blender/freestyle/intern/system/PointerSequence.h @@ -0,0 +1,97 @@ +// +// Filename : PointerSequence.h +// Author(s) : Alexander Beels +// Purpose : Class to define a cell grid surrounding +// the projected image of a scene +// Date of creation : 22/11/2010 +// +/////////////////////////////////////////////////////////////////////////////// + + +// +// 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. +// +/////////////////////////////////////////////////////////////////////////////// + +// +// Simple RAII wrappers for std:: sequential containers +// +/////////////////////////////////////////////////////////////////////////////// + +// +// PointerSequence +// +// Produces a wrapped version of a sequence type (std::vector, std::deque, std::list) +// that will take ownership of pointers tht it stores. Those pointers will be deleted +// in its destructor. +// +// Because the contained pointers are wholly owned by the sequence, you cannot make a +// copy of the sequence. Making a copy would result in a double free. +// +// This is a no-frills class that provides no additional facilities. The user is +// responsible for managing any pointers that are removed from the list, and for making +// sure that any pointers contained in the class are not deleted elsewhere. Because +// this class does no reference counting, the user must also make sure that any pointer +// appears only once in the sequence. +// +// If more sophisticated facilities are needed, use tr1::shared_ptr or boost::shared_ptr. +// This class is only intended to allow one to eke by in projects where tr1 or boost are +// not available. +// +// Usage: The template takes two parameters, the standard container, and the class held +// in the container. This is a limitation of C++ templates, where T::iterator is not a +// type when T is a template parameter. If anyone knows a way around this +// limitation, then the second parameter can be eliminated. +// +// Example: +// PointerSequence<vector<Widget*>, Widget*> v; +// v.push_back(new Widget); +// cout << v[0] << endl; // operator[] is provided by std::vector, not by PointerSequence +// v.destroy(); // Deletes all pointers in sequence and sets them to NULL. +// +// The idiom for removing a pointer from a sequence is: +// Widget* w = v[3]; +// v.erase(v.begin() + 3); // or v[3] = 0; +// The user is now responsible for disposing of w properly. +// +/////////////////////////////////////////////////////////////////////////////// + +#ifndef POINTERSEQUENCE_H +# define POINTERSEQUENCE_H + +#include <algorithm> + +template <typename C, typename T> +class PointerSequence : public C { + PointerSequence (PointerSequence& other); + PointerSequence& operator= (PointerSequence& other); + static void destroyer (T t) { + delete t; + } +public: + PointerSequence () {}; + ~PointerSequence () { + destroy(); + } + void destroy () { + for_each (this->begin(), this->end(), destroyer); + } +}; + +#endif // POINTERSEQUENCE_H + diff --git a/source/blender/freestyle/intern/view_map/ArbitraryGridDensityProvider.cpp b/source/blender/freestyle/intern/view_map/ArbitraryGridDensityProvider.cpp new file mode 100644 index 00000000000..15b2b3343cc --- /dev/null +++ b/source/blender/freestyle/intern/view_map/ArbitraryGridDensityProvider.cpp @@ -0,0 +1,108 @@ +// +// Filename : ArbitraryGridDensityProvider.cpp +// Author(s) : Alexander Beels +// Purpose : Class to define a cell grid surrounding +// the projected image of a scene +// Date of creation : 2011-2-5 +// +/////////////////////////////////////////////////////////////////////////////// + + +// +// 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. +// +/////////////////////////////////////////////////////////////////////////////// + +#include "ArbitraryGridDensityProvider.h" + +ArbitraryGridDensityProvider::ArbitraryGridDensityProvider(OccluderSource& source, const real proscenium[4], unsigned numCells) + : GridDensityProvider(source), numCells(numCells) +{ + initialize (proscenium); +} + +ArbitraryGridDensityProvider::ArbitraryGridDensityProvider(OccluderSource& source, const BBox<Vec3r>& bbox, const GridHelpers::Transform& transform, unsigned numCells) + : GridDensityProvider(source), numCells(numCells) +{ + real proscenium[4]; + calculateQuickProscenium(transform, bbox, proscenium); + + initialize (proscenium); +} + +ArbitraryGridDensityProvider::ArbitraryGridDensityProvider(OccluderSource& source, unsigned numCells) + : GridDensityProvider(source), numCells(numCells) +{ + real proscenium[4]; + calculateOptimalProscenium(source, proscenium); + + initialize (proscenium); +} + +ArbitraryGridDensityProvider::~ArbitraryGridDensityProvider () {} + +void ArbitraryGridDensityProvider::initialize (const real proscenium[4]) +{ + float prosceniumWidth = (proscenium[1] - proscenium[0]); + float prosceniumHeight = (proscenium[3] - proscenium[2]); + real cellArea = prosceniumWidth * prosceniumHeight / numCells; + cout << prosceniumWidth << " x " << prosceniumHeight << " grid with cells of area " << cellArea << "." << endl; + + _cellSize = sqrt(cellArea); + // Now we know how many cells make each side of our grid + _cellsX = ceil(prosceniumWidth / _cellSize); + _cellsY = ceil(prosceniumHeight / _cellSize); + cout << _cellsX << "x" << _cellsY << " cells of size " << _cellSize << " square." << endl; + + // Make sure the grid exceeds the proscenium by a small amount + float safetyZone = 0.1; + if ( _cellsX * _cellSize < prosceniumWidth * (1.0 + safetyZone) ) { + _cellsX = prosceniumWidth * (1.0 + safetyZone) / _cellSize; + } + if ( _cellsY * _cellSize < prosceniumHeight * (1.0 + safetyZone) ) { + _cellsY = prosceniumHeight * (1.0 + safetyZone) / _cellSize; + } + cout << _cellsX << "x" << _cellsY << " cells of size " << _cellSize << " square." << endl; + + // Find grid origin + _cellOrigin[0] = ((proscenium[0] + proscenium[1]) / 2.0) - (_cellsX / 2.0) * _cellSize; + _cellOrigin[1] = ((proscenium[2] + proscenium[3]) / 2.0) - (_cellsY / 2.0) * _cellSize; +} + +ArbitraryGridDensityProviderFactory::ArbitraryGridDensityProviderFactory(unsigned numCells) + : numCells(numCells) +{ +} + +ArbitraryGridDensityProviderFactory::~ArbitraryGridDensityProviderFactory () {} + +auto_ptr<GridDensityProvider> ArbitraryGridDensityProviderFactory::newGridDensityProvider(OccluderSource& source, const real proscenium[4]) +{ + return auto_ptr<GridDensityProvider>(new ArbitraryGridDensityProvider(source, proscenium, numCells)); +} + +auto_ptr<GridDensityProvider> ArbitraryGridDensityProviderFactory::newGridDensityProvider(OccluderSource& source, const BBox<Vec3r>& bbox, const GridHelpers::Transform& transform) +{ + return auto_ptr<GridDensityProvider>(new ArbitraryGridDensityProvider(source, bbox, transform, numCells)); +} + +auto_ptr<GridDensityProvider> ArbitraryGridDensityProviderFactory::newGridDensityProvider(OccluderSource& source) +{ + return auto_ptr<GridDensityProvider>(new ArbitraryGridDensityProvider(source, numCells)); +} + diff --git a/source/blender/freestyle/intern/view_map/ArbitraryGridDensityProvider.h b/source/blender/freestyle/intern/view_map/ArbitraryGridDensityProvider.h new file mode 100644 index 00000000000..f863b2132a7 --- /dev/null +++ b/source/blender/freestyle/intern/view_map/ArbitraryGridDensityProvider.h @@ -0,0 +1,67 @@ +// +// Filename : ArbitraryGridDensityProvider.h +// Author(s) : Alexander Beels +// Purpose : Class to define a cell grid surrounding +// the projected image of a scene +// Date of creation : 2011-2-5 +// +/////////////////////////////////////////////////////////////////////////////// + + +// +// 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 ARBITRARYGRIDDENSITYPROVIDER_H +#define ARBITRARYGRIDDENSITYPROVIDER_H + +#include "GridDensityProvider.h" + +class ArbitraryGridDensityProvider : public GridDensityProvider { + // Disallow copying and assignment + ArbitraryGridDensityProvider (const ArbitraryGridDensityProvider& other); + ArbitraryGridDensityProvider& operator= (const ArbitraryGridDensityProvider& other); + +public: + ArbitraryGridDensityProvider(OccluderSource& source, const real proscenium[4], unsigned numCells); + ArbitraryGridDensityProvider(OccluderSource& source, const BBox<Vec3r>& bbox, const GridHelpers::Transform& transform, unsigned numCells); + ArbitraryGridDensityProvider(OccluderSource& source, unsigned numCells); + virtual ~ArbitraryGridDensityProvider (); + +protected: + unsigned numCells; + +private: + void initialize (const real proscenium[4]); +}; + +class ArbitraryGridDensityProviderFactory : public GridDensityProviderFactory { +public: + ArbitraryGridDensityProviderFactory(unsigned numCells); + ~ArbitraryGridDensityProviderFactory (); + + auto_ptr<GridDensityProvider> newGridDensityProvider(OccluderSource& source, const real proscenium[4]); + auto_ptr<GridDensityProvider> newGridDensityProvider(OccluderSource& source, const BBox<Vec3r>& bbox, const GridHelpers::Transform& transform); + auto_ptr<GridDensityProvider> newGridDensityProvider(OccluderSource& source); +protected: + unsigned numCells; +}; + +#endif // ARBITRARYGRIDDENSITYPROVIDER_H + diff --git a/source/blender/freestyle/intern/view_map/AverageAreaGridDensityProvider.cpp b/source/blender/freestyle/intern/view_map/AverageAreaGridDensityProvider.cpp new file mode 100644 index 00000000000..8b4c60a7fea --- /dev/null +++ b/source/blender/freestyle/intern/view_map/AverageAreaGridDensityProvider.cpp @@ -0,0 +1,120 @@ +// +// Filename : AverageAreaGridDensityProvider.cpp +// Author(s) : Alexander Beels +// Purpose : Class to define a cell grid surrounding +// the projected image of a scene +// Date of creation : 2011-2-9 +// +/////////////////////////////////////////////////////////////////////////////// + + +// +// 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. +// +/////////////////////////////////////////////////////////////////////////////// + +#include "AverageAreaGridDensityProvider.h" + +AverageAreaGridDensityProvider::AverageAreaGridDensityProvider(OccluderSource& source, const real proscenium[4], real sizeFactor) + : GridDensityProvider(source) +{ + initialize (proscenium, sizeFactor); +} + +AverageAreaGridDensityProvider::AverageAreaGridDensityProvider(OccluderSource& source, const BBox<Vec3r>& bbox, const GridHelpers::Transform& transform, real sizeFactor) + : GridDensityProvider(source) +{ + real proscenium[4]; + calculateQuickProscenium(transform, bbox, proscenium); + + initialize (proscenium, sizeFactor); +} + +AverageAreaGridDensityProvider::AverageAreaGridDensityProvider(OccluderSource& source, real sizeFactor) + : GridDensityProvider(source) +{ + real proscenium[4]; + calculateOptimalProscenium(source, proscenium); + + initialize (proscenium, sizeFactor); +} + +AverageAreaGridDensityProvider::~AverageAreaGridDensityProvider () {} + +void AverageAreaGridDensityProvider::initialize (const real proscenium[4], real sizeFactor) +{ + float prosceniumWidth = (proscenium[1] - proscenium[0]); + float prosceniumHeight = (proscenium[3] - proscenium[2]); + + real cellArea = 0.0; + unsigned numFaces = 0; + for ( source.begin(); source.isValid(); source.next() ) { + Polygon3r& poly(source.getGridSpacePolygon()); + Vec3r min, max; + poly.getBBox(min, max); + cellArea += (max[0] - min[0]) * (max[1] - min[1]); + ++numFaces; + } + cout << "Total area: " << cellArea << ". Number of faces: " << numFaces << "." << endl; + cellArea /= numFaces; + cellArea *= sizeFactor; + cout << "Building grid with average area " << cellArea << endl; + + _cellSize = sqrt(cellArea); + // Now we know how many cells make each side of our grid + _cellsX = ceil(prosceniumWidth / _cellSize); + _cellsY = ceil(prosceniumHeight / _cellSize); + cout << _cellsX << "x" << _cellsY << " cells of size " << _cellSize << " square." << endl; + + // Make sure the grid exceeds the proscenium by a small amount + float safetyZone = 0.1; + if ( _cellsX * _cellSize < prosceniumWidth * (1.0 + safetyZone) ) { + _cellsX = prosceniumWidth * (1.0 + safetyZone) / _cellSize; + } + if ( _cellsY * _cellSize < prosceniumHeight * (1.0 + safetyZone) ) { + _cellsY = prosceniumHeight * (1.0 + safetyZone) / _cellSize; + } + cout << _cellsX << "x" << _cellsY << " cells of size " << _cellSize << " square." << endl; + + // Find grid origin + _cellOrigin[0] = ((proscenium[0] + proscenium[1]) / 2.0) - (_cellsX / 2.0) * _cellSize; + _cellOrigin[1] = ((proscenium[2] + proscenium[3]) / 2.0) - (_cellsY / 2.0) * _cellSize; +} + +AverageAreaGridDensityProviderFactory::AverageAreaGridDensityProviderFactory(real sizeFactor) + : sizeFactor(sizeFactor) +{ +} + +AverageAreaGridDensityProviderFactory::~AverageAreaGridDensityProviderFactory () {} + +auto_ptr<GridDensityProvider> AverageAreaGridDensityProviderFactory::newGridDensityProvider(OccluderSource& source, const real proscenium[4]) +{ + return auto_ptr<GridDensityProvider>(new AverageAreaGridDensityProvider(source, proscenium, sizeFactor)); +} + +auto_ptr<GridDensityProvider> AverageAreaGridDensityProviderFactory::newGridDensityProvider(OccluderSource& source, const BBox<Vec3r>& bbox, const GridHelpers::Transform& transform) +{ + return auto_ptr<GridDensityProvider>(new AverageAreaGridDensityProvider(source, bbox, transform, sizeFactor)); +} + +auto_ptr<GridDensityProvider> AverageAreaGridDensityProviderFactory::newGridDensityProvider(OccluderSource& source) +{ + return auto_ptr<GridDensityProvider>(new AverageAreaGridDensityProvider(source, sizeFactor)); +} + diff --git a/source/blender/freestyle/intern/view_map/AverageAreaGridDensityProvider.h b/source/blender/freestyle/intern/view_map/AverageAreaGridDensityProvider.h new file mode 100644 index 00000000000..73d28f006a7 --- /dev/null +++ b/source/blender/freestyle/intern/view_map/AverageAreaGridDensityProvider.h @@ -0,0 +1,67 @@ +// +// Filename : AverageAreaGridDensityProvider.h +// Author(s) : Alexander Beels +// Purpose : Class to define a cell grid surrounding +// the projected image of a scene +// Date of creation : 2011-2-9 +// +/////////////////////////////////////////////////////////////////////////////// + + +// +// 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 AVERAGEAREAGRIDDENSITYPROVIDER_H +#define AVERAGEAREAGRIDDENSITYPROVIDER_H + +#include "GridDensityProvider.h" + +class AverageAreaGridDensityProvider : public GridDensityProvider { + // Disallow copying and assignment + AverageAreaGridDensityProvider (const AverageAreaGridDensityProvider& other); + AverageAreaGridDensityProvider& operator= (const AverageAreaGridDensityProvider& other); + +public: + AverageAreaGridDensityProvider(OccluderSource& source, const real proscenium[4], real sizeFactor); + AverageAreaGridDensityProvider(OccluderSource& source, const BBox<Vec3r>& bbox, const GridHelpers::Transform& transform, real sizeFactor); + AverageAreaGridDensityProvider(OccluderSource& source, real sizeFactor); + virtual ~AverageAreaGridDensityProvider (); + +protected: + +private: + void initialize (const real proscenium[4], real sizeFactor); +}; + +class AverageAreaGridDensityProviderFactory : public GridDensityProviderFactory { +public: + AverageAreaGridDensityProviderFactory(real sizeFactor); + ~AverageAreaGridDensityProviderFactory (); + + auto_ptr<GridDensityProvider> newGridDensityProvider(OccluderSource& source, const real proscenium[4]); + auto_ptr<GridDensityProvider> newGridDensityProvider(OccluderSource& source, const BBox<Vec3r>& bbox, const GridHelpers::Transform& transform); + auto_ptr<GridDensityProvider> newGridDensityProvider(OccluderSource& source); + +protected: + real sizeFactor; +}; + +#endif // AVERAGEAREAGRIDDENSITYPROVIDER_H + diff --git a/source/blender/freestyle/intern/view_map/BoxGrid.cpp b/source/blender/freestyle/intern/view_map/BoxGrid.cpp new file mode 100644 index 00000000000..757cf7b6559 --- /dev/null +++ b/source/blender/freestyle/intern/view_map/BoxGrid.cpp @@ -0,0 +1,210 @@ +// +// Filename : BoxGrid.cpp +// Author(s) : Alexander Beels +// Purpose : Class to define a cell grid surrounding +// the projected image of a scene +// Date of creation : 2011-1-29 +// +/////////////////////////////////////////////////////////////////////////////// + +// +// 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. +// +/////////////////////////////////////////////////////////////////////////////// + +#include "BoxGrid.h" + +#include <stdexcept> +#include <algorithm> + +using namespace std; + +// Helper Classes + +// OccluderData +/////////////// + +// Cell +///////// + +BoxGrid::Cell::Cell () {} + +BoxGrid::Cell::~Cell () {} + +void BoxGrid::Cell::setDimensions(real x, real y, real sizeX, real sizeY) { + const real epsilon = 1.0e-06; + boundary[0] = x - epsilon; + boundary[1] = x + sizeX + epsilon; + boundary[2] = y - epsilon; + boundary[3] = y + sizeY + epsilon; +} + +bool BoxGrid::Cell::compareOccludersByShallowestPoint (const BoxGrid::OccluderData* a, const BoxGrid::OccluderData* b) { + return a->shallowest < b->shallowest; +} + +void BoxGrid::Cell::indexPolygons() { + // Sort occluders by their shallowest points. + sort(faces.begin(), faces.end(), compareOccludersByShallowestPoint); +} + +// Iterator +////////////////// + +BoxGrid::Iterator::Iterator (BoxGrid& grid, Vec3r& center, real epsilon) + : _target(grid.transform(center)), + _foundOccludee(false) +{ + // Find target cell + _cell = grid.findCell(_target); + #if boxgridlogging == 1 + cout << "Searching for occluders of edge centered at " << _target << " in cell [" + << _cell->boundary[0] << ", " << _cell->boundary[1] << ", " << _cell->boundary[2] + << ", " << _cell->boundary[3] << "] (" << _cell->faces.size() << " occluders)" << endl; + #endif + + // Set iterator + _current = _cell->faces.begin(); +} + +BoxGrid::Iterator::~Iterator () {} + +// BoxGrid +///////////////// + +BoxGrid::BoxGrid(OccluderSource& source, GridDensityProvider& density, ViewMap *viewMap, Vec3r& viewpoint, bool enableQI) + : _viewpoint(viewpoint), + _enableQI(enableQI) +{ + cout << "Generate Cell structure" << endl; + // Generate Cell structure + assignCells(source, density, viewMap); + cout << "Distribute occluders" << endl; + // Fill Cells + distributePolygons(source); + cout << "Reorganize cells" << endl; + // Reorganize Cells + reorganizeCells(); + cout << "Ready to use BoxGrid" << endl; +} + +BoxGrid::~BoxGrid () { +} + +void BoxGrid::assignCells (OccluderSource& source, GridDensityProvider& density, ViewMap *viewMap) { + _cellSize = density.cellSize(); + _cellsX = density.cellsX(); + _cellsY = density.cellsY(); + _cellOrigin[0] = density.cellOrigin(0); + _cellOrigin[1] = density.cellOrigin(1); + + // Now allocate the cell table and fill it with default (empty) cells + _cells.resize(_cellsX * _cellsY); + for ( cellContainer::iterator i = _cells.begin(), end = _cells.end(); i != end; ++i ) { + (*i) = NULL; + } + + // Identify cells that will be used, and set the dimensions for each + ViewMap::fedges_container& fedges = viewMap->FEdges(); + for (ViewMap::fedges_container::iterator f = fedges.begin(), fend = fedges.end(); f != fend; ++f ) { + if ( (*f)->isInImage() ) { + Vec3r point = transform((*f)->center3d()); + unsigned i, j; + getCellCoordinates(point, i, j); + if ( _cells[i * _cellsY + j] == NULL ) { + // This is an uninitialized cell + + real x, y, width, height; + + x = _cellOrigin[0] + _cellSize * i; + width = _cellSize; + + y = _cellOrigin[1] + _cellSize * j; + height = _cellSize; + + // Initialize cell + Cell* b = _cells[i * _cellsY + j] = new Cell(); + b->setDimensions(x, y, width, height); + } + } + } +} + +void BoxGrid::distributePolygons (OccluderSource& source) { + unsigned long nFaces = 0; + unsigned long nKeptFaces = 0; + + for ( source.begin(); source.isValid(); source.next() ) { + OccluderData* occluder = NULL; + + try { + if ( insertOccluder(source, occluder) ) { + _faces.push_back(occluder); + ++nKeptFaces; + } + } catch (...) { + // If an exception was thrown, _faces.push_back() cannot have succeeded. + // occluder is not owned by anyone, and must be deleted. + // If the exception was thrown before or during new OccluderData(), then + // occluder is NULL, and this delete is harmless. + delete occluder; + throw; + } + ++nFaces; + } + cout << "Distributed " << nFaces << " occluders. Retained " << nKeptFaces << "." << endl; +} + +void BoxGrid::reorganizeCells () { + // Sort the occluders by shallowest point + for ( vector<Cell*>::iterator i = _cells.begin(), end = _cells.end(); i != end; ++i ) { + if ( *i != NULL ) { + (*i)->indexPolygons(); + } + } +} + +void BoxGrid::getCellCoordinates(const Vec3r& point, unsigned& x, unsigned& y) { + x = min(_cellsX - 1, (unsigned) floor (max((double) 0.0f, point[0] - _cellOrigin[0]) / _cellSize)); + y = min(_cellsY - 1, (unsigned) floor (max((double) 0.0f, point[1] - _cellOrigin[1]) / _cellSize)); +} + +BoxGrid::Cell* BoxGrid::findCell(const Vec3r& point) { + unsigned x, y; + getCellCoordinates(point, x, y); + return _cells[x * _cellsY + y]; +} + +bool BoxGrid::orthographicProjection () const { + return true; +} + +const Vec3r& BoxGrid::viewpoint() const { + return _viewpoint; +} + +bool BoxGrid::enableQI() const { + return _enableQI; +} + +BoxGrid::Transform::Transform () : GridHelpers::Transform() {} + +Vec3r BoxGrid::Transform::operator() (const Vec3r& point) const { + return Vec3r(point[0], point[1], -point[2]); +} + diff --git a/source/blender/freestyle/intern/view_map/BoxGrid.h b/source/blender/freestyle/intern/view_map/BoxGrid.h new file mode 100644 index 00000000000..43de8d713d5 --- /dev/null +++ b/source/blender/freestyle/intern/view_map/BoxGrid.h @@ -0,0 +1,376 @@ +// +// Filename : BoxGrid.h +// Author(s) : Alexander Beels +// Purpose : Class to define a cell grid surrounding +// the projected image of a scene +// Date of creation : 2011-1-29 +// +/////////////////////////////////////////////////////////////////////////////// + + +// +// 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 BOXGRID_H +#define BOXGRID_H + +#define boxgridlogging 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. +//#include <vector> +//#include <deque> +#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" + +class BoxGrid +{ +public: + // Helper classes + 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; + }; + +private: + struct Cell { + // Can't store Cell in a vector without copy and assign + //Cell(const Cell& other); + //Cell& operator= (const Cell& other); + + explicit Cell (); + ~Cell (); + + 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); + void indexPolygons(); + + real boundary[4]; + //deque<OccluderData*> faces; + vector<OccluderData*> faces; + }; + +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 { + public: + // epsilon is not used in this class, but other grids with the same interface may need an epsilon + explicit Iterator (BoxGrid& grid, Vec3r& center, real epsilon=1e-06); + ~Iterator (); + void initBeforeTarget (); + void initAfterTarget (); + void nextOccluder (); + void nextOccludee (); + bool validBeforeTarget(); + bool validAfterTarget(); + WFace* getWFace() const; + Polygon3r* getCameraSpacePolygon(); + void reportDepth(Vec3r origin, Vec3r u, real t); + private: + bool testOccluder(bool wantOccludee); + void markCurrentOccludeeCandidate(real depth); + + Cell* _cell; + Vec3r _target; + bool _foundOccludee; + real _occludeeDepth; + //deque<OccluderData*>::iterator _current, _occludeeCandidate; + vector<OccluderData*>::iterator _current, _occludeeCandidate; + }; + + class Transform : public GridHelpers::Transform { + public: + explicit Transform (); + explicit Transform (Transform& other); + Vec3r operator() (const Vec3r& point) const; + }; + +private: + // Prevent implicit copies and assignments. + BoxGrid(const BoxGrid& other); + BoxGrid& operator= (const BoxGrid& other); +public: + explicit BoxGrid (OccluderSource& source, GridDensityProvider& density, ViewMap *viewMap, Vec3r& viewpoint, bool enableQI); + virtual ~BoxGrid(); + + // 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 + bool insertOccluder(OccluderSource& source, OccluderData*& occluder); + // Sort occluders in each cell + void reorganizeCells(); + + Cell* findCell(const Vec3r& point); + + // Accessors: + bool orthographicProjection() const; + const Vec3r& viewpoint() const; + bool enableQI() const; + Transform transform; + +private: + void getCellCoordinates(const Vec3r& point, unsigned& x, unsigned& y); + + typedef PointerSequence<vector<Cell*>, Cell*> cellContainer; + //typedef PointerSequence<deque<OccluderData*>, OccluderData*> occluderContainer; + typedef PointerSequence<vector<OccluderData*>, OccluderData*> occluderContainer; + unsigned _cellsX, _cellsY; + float _cellSize; + float _cellOrigin[2]; + cellContainer _cells; + occluderContainer _faces; + Vec3r _viewpoint; + bool _enableQI; +}; + +inline void BoxGrid::Iterator::initBeforeTarget () { + _current = _cell->faces.begin(); + while ( _current != _cell->faces.end() && ! testOccluder(false) ) { + ++_current; + } +} + +inline void BoxGrid::Iterator::initAfterTarget () { + if ( _foundOccludee ) { + #if boxgridlogging == 1 + std::cout << "\tStarting occludee search from occludeeCandidate at depth " << _occludeeDepth << std::endl; + #endif + _current = _occludeeCandidate; + return; + } + + #if boxgridlogging == 1 + std::cout << "\tStarting occludee search from current position" << std::endl; + #endif + + while ( _current != _cell->faces.end() && ! testOccluder(true) ) { + ++_current; + } +} + +inline bool BoxGrid::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. + return true; + } + #if boxgridlogging == 1 + std::cout << "\tTesting occluder " << (*_current)->poly.getVertices()[0]; + for ( unsigned 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 boxgridlogging == 1 + std::cout << "\t\tAborting: shallowest > occludeeCandidate->deepest" << std::endl; + #endif + _current = _cell->faces.end(); + + // See note above + return true; + } + + // Specific continue or stop conditions when searching for each type + if ( wantOccludee ) { + if ( (*_current)->deepest < _target[2] ) { + #if boxgridlogging == 1 + std::cout << "\t\tSkipping: shallower than target while looking for occludee" << std::endl; + #endif + return false; + } + } else { + if ( (*_current)->shallowest > _target[2] ) { + #if boxgridlogging == 1 + std::cout << "\t\tStopping: deeper than target while looking for occluder" << std::endl; + #endif + return true; + } + } + + // Depthwise, this is a valid occluder. + + // 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 boxgridlogging == 1 + 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. + return true; +} + +inline void BoxGrid::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 a Z-value in grid space + real depth = -(origin + (u * t))[2]; + #if boxgridlogging == 1 + std::cout << "\t\tReporting depth of occluder/ee: " << depth; + #endif + if ( depth > _target[2] ) { + #if boxgridlogging == 1 + 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 ) { + markCurrentOccludeeCandidate(depth); + } + } else { + #if boxgridlogging == 1 + std::cout << std::endl; + #endif + } +} + +inline void BoxGrid::Iterator::nextOccluder () { + if ( _current != _cell->faces.end() ) { + do { + ++_current; + } while ( _current != _cell->faces.end() && ! testOccluder(false) ); + } +} + +inline void BoxGrid::Iterator::nextOccludee () { + if ( _current != _cell->faces.end() ) { + do { + ++_current; + } while ( _current != _cell->faces.end() && ! testOccluder(true) ); + } +} + +inline bool BoxGrid::Iterator::validBeforeTarget () { + return _current != _cell->faces.end() && (*_current)->shallowest <= _target[2]; +} + +inline bool BoxGrid::Iterator::validAfterTarget () { + return _current != _cell->faces.end(); +} + +inline void BoxGrid::Iterator::markCurrentOccludeeCandidate(real depth) { + #if boxgridlogging == 1 + std::cout << "\t\tFound occludeeCandidate at depth " << depth << std::endl; + #endif + _occludeeCandidate = _current; + _occludeeDepth = depth; + _foundOccludee = true; +} + +inline WFace* BoxGrid::Iterator::getWFace() const { + return (*_current)->face; +} + +inline Polygon3r* BoxGrid::Iterator::getCameraSpacePolygon() { + return &((*_current)->cameraSpacePolygon); +} + +inline BoxGrid::OccluderData::OccluderData (OccluderSource& source, Polygon3r& p) + : poly(p), + cameraSpacePolygon(source.getCameraSpacePolygon()), + face(source.getWFace()) +{ + // Set shallowest and deepest based on bbox + Vec3r min, max; + poly.getBBox(min, max); + shallowest = min[2]; + deepest = max[2]; +} + +inline void BoxGrid::Cell::checkAndInsert(OccluderSource& source, Polygon3r& poly, OccluderData*& occluder) { + if ( GridHelpers::insideProscenium (boundary, poly) ) { + if ( occluder == NULL) { + // Disposal of occluder will be handled in BoxGrid::distributePolygons(), + // or automatically by BoxGrid::_faces; + occluder = new OccluderData(source, poly); + } + faces.push_back(occluder); + } +} + +inline bool BoxGrid::insertOccluder(OccluderSource& source, OccluderData*& occluder) { + Polygon3r& poly(source.getGridSpacePolygon()); + occluder = NULL; + + Vec3r bbMin, bbMax; + poly.getBBox(bbMin, bbMax); + // Check overlapping cells + unsigned startX, startY, endX, endY; + 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 ) { + _cells[i * _cellsY + j]->checkAndInsert(source, poly, occluder); + } + } + } + + return occluder != NULL; +} + +#endif // BOXGRID_H + diff --git a/source/blender/freestyle/intern/view_map/CulledOccluderSource.cpp b/source/blender/freestyle/intern/view_map/CulledOccluderSource.cpp new file mode 100644 index 00000000000..ea57da93347 --- /dev/null +++ b/source/blender/freestyle/intern/view_map/CulledOccluderSource.cpp @@ -0,0 +1,277 @@ +// +// Filename : CulledOccluderSource.h +// Author(s) : Alexander Beels +// Purpose : Class to define a cell grid surrounding +// the projected image of a scene +// Date of creation : 2010-12-21 +// +/////////////////////////////////////////////////////////////////////////////// + + +// +// 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. +// +/////////////////////////////////////////////////////////////////////////////// + +#include "CulledOccluderSource.h" +#include "../geometry/GridHelpers.h" +#include "FRS_freestyle.h" + +CulledOccluderSource::CulledOccluderSource (const GridHelpers::Transform& t, WingedEdge& we, ViewMap& viewMap, bool extensiveFEdgeSearch) + : OccluderSource(t, we), + rejected(0), + gridSpaceOccluderProsceniumInitialized(false) +{ + cullViewEdges(viewMap, extensiveFEdgeSearch); + + // If we have not found any visible FEdges during our cull, then there is nothing + // to iterate over. Short-circuit everything. + valid = gridSpaceOccluderProsceniumInitialized; + + if ( valid && ! testCurrent() ) { + next(); + } +} + +CulledOccluderSource::~CulledOccluderSource() { +} + +bool CulledOccluderSource::testCurrent() { + if ( valid ) { + // The test for gridSpaceOccluderProsceniumInitialized should not be necessary + return gridSpaceOccluderProsceniumInitialized && GridHelpers::insideProscenium (gridSpaceOccluderProscenium, cachedPolygon); + } + return false; +} + +bool CulledOccluderSource::next() { + while ( OccluderSource::next() ) { + if ( testCurrent() ) { + ++rejected; + return true; + } + } + std::cout << "Finished generating occluders. Rejected " << rejected << " faces." << std::endl; + return false; +} + +void CulledOccluderSource::getOccluderProscenium(real proscenium[4]) { + for ( unsigned i = 0; i < 4; ++i ) { + proscenium[i] = gridSpaceOccluderProscenium[i]; + } +} + +static inline real distance2D(const Vec3r & point, const real origin[2]) { + return ::hypot((point[0] - origin[0]), (point[1] - origin[1])); +} + +static inline bool crossesProscenium(real proscenium[4], FEdge *fe) { + Vec2r min(proscenium[0], proscenium[2]); + Vec2r max(proscenium[1], proscenium[3]); + Vec2r A(fe->vertexA()->getProjectedX(), fe->vertexA()->getProjectedY()); + Vec2r B(fe->vertexB()->getProjectedX(), fe->vertexB()->getProjectedY()); + + return GeomUtils::intersect2dSeg2dArea (min, max, A, B); +} + +static inline bool insideProscenium(real proscenium[4], const Vec3r& point) { + return ! ( point[0] < proscenium[0] || point[0] > proscenium[1] || point[1] < proscenium[2] || point[1] > proscenium[3] ); +} + +void CulledOccluderSource::cullViewEdges(ViewMap& viewMap, bool extensiveFEdgeSearch) { + // Cull view edges by marking them as non-displayable. + // This avoids the complications of trying to delete + // edges from the ViewMap. + + // Non-displayable view edges will be skipped over during + // visibility calculation. + + // View edges will be culled according to their position + // w.r.t. the viewport proscenium (viewport + 5% border, + // or some such). + + // Get proscenium boundary for culling + real viewProscenium[4]; + GridHelpers::getDefaultViewProscenium(viewProscenium); + real prosceniumOrigin[2]; + prosceniumOrigin[0] = (viewProscenium[1] - viewProscenium[0]) / 2.0; + prosceniumOrigin[1] = (viewProscenium[3] - viewProscenium[2]) / 2.0; + cout << "Proscenium culling:" << endl; + cout << "Proscenium: [" << viewProscenium[0] << ", " << viewProscenium[1] << ", " << viewProscenium[2] << ", " << viewProscenium[3] << "]"<< endl; + cout << "Origin: [" << prosceniumOrigin[0] << ", " << prosceniumOrigin[1] << "]"<< endl; + + // A separate occluder proscenium will also be maintained, + // starting out the same as the viewport proscenium, and + // expanding as necessary so that it encompasses the center + // point of at least one feature edge in each retained view + // edge. + // The occluder proscenium will be used later to cull occluding + // triangles before they are inserted into the Grid. + // The occluder proscenium starts out the same size as the view + // proscenium + GridHelpers::getDefaultViewProscenium(occluderProscenium); + + // N.B. Freestyle is inconsistent in its use of ViewMap::viewedges_container + // and vector<ViewEdge*>::iterator. Probably all occurences of vector<ViewEdge*>::iterator + // should be replaced ViewMap::viewedges_container throughout the code. + // For each view edge + ViewMap::viewedges_container::iterator ve, veend; + + for(ve=viewMap.ViewEdges().begin(), veend=viewMap.ViewEdges().end(); ve!=veend; ve++) { + // Overview: + // Search for a visible feature edge + // If none: mark view edge as non-displayable + // Otherwise: + // Find a feature edge with center point inside occluder proscenium. + // If none exists, find the feature edge with center point + // closest to viewport origin. + // Expand occluder proscenium to enclose center point. + + // For each feature edge, while bestOccluderTarget not found and view edge not visibile + bool bestOccluderTargetFound = false; + FEdge *bestOccluderTarget = NULL; + real bestOccluderDistance = 0.0; + FEdge *festart = (*ve)->fedgeA(); + FEdge *fe = festart; + // All ViewEdges start culled + (*ve)->setIsInImage(false); + + // For simple visibility calculation: mark a feature edge + // that is known to have a center point inside the occluder proscenium. + // Cull all other feature edges. + do { + // All FEdges start culled + fe->setIsInImage(false); + + // Look for the visible edge that can most easily be included + // in the occluder proscenium. + if ( ! bestOccluderTargetFound ) { + // If center point is inside occluder proscenium, + if ( insideProscenium(occluderProscenium, fe->center2d()) ) { + // Use this feature edge for visibility deterimination + fe->setIsInImage(true); + expandGridSpaceOccluderProscenium(fe); + // Mark bestOccluderTarget as found + bestOccluderTargetFound = true; + bestOccluderTarget = fe; + } else { + real d = distance2D(fe->center2d(), prosceniumOrigin); + // If center point is closer to viewport origin than current target + if ( bestOccluderTarget == NULL || d < bestOccluderDistance ) { + // Then store as bestOccluderTarget + bestOccluderDistance = d; + bestOccluderTarget = fe; + } + } + } + + // If feature edge crosses the view proscenium + if ( ! (*ve)->isInImage() && crossesProscenium(viewProscenium, fe) ) { + // Then the view edge will be included in the image + (*ve)->setIsInImage(true); + } + fe = fe->nextEdge(); + } while ( fe != NULL && fe != festart && ! ( bestOccluderTargetFound && (*ve)->isInImage() ) ); + + // Either we have run out of FEdges, or we already have the one edge we need to determine visibility + // Cull all remaining edges. + while ( fe != NULL && fe != festart ) { + fe->setIsInImage(false); + fe = fe->nextEdge(); + } + + // If bestOccluderTarget was not found inside the occluder proscenium, + // we need to expand the occluder proscenium to include it. + if ( (*ve)->isInImage() && bestOccluderTarget != NULL && ! bestOccluderTargetFound ) { + // Expand occluder proscenium to enclose bestOccluderTarget + Vec3r point = bestOccluderTarget->center2d(); + if ( point[0] < occluderProscenium[0] ) { + occluderProscenium[0] = point[0]; + } else if ( point[0] > occluderProscenium[1] ) { + occluderProscenium[1] = point[0]; + } + if ( point[1] < occluderProscenium[2] ) { + occluderProscenium[2] = point[1]; + } else if ( point[1] > occluderProscenium[3] ) { + occluderProscenium[3] = point[1]; + } + // Use bestOccluderTarget for visibility determination + bestOccluderTarget->setIsInImage(true); + } + } + + // We are done calculating the occluder proscenium. + // Expand the occluder proscenium by an epsilon to avoid rounding errors. + const real epsilon = 1.0e-6; + occluderProscenium[0] -= epsilon; + occluderProscenium[1] += epsilon; + occluderProscenium[2] -= epsilon; + occluderProscenium[3] += epsilon; + + // For "Normal" or "Fast" style visibility computation only: + + // For more detailed visibility calculation, make a second pass through + // the view map, marking all feature edges with center points inside + // the final occluder proscenium. All of these feature edges can be + // considered during visibility calculation. + + // So far we have only found one FEdge per ViewEdge. The "Normal" and + // "Fast" styles of visibility computation want to consider many + // FEdges for each ViewEdge. + // Here we re-scan the view map to find any usable FEdges that we + // skipped on the first pass, or that have become usable because the + // occluder proscenium has been expanded since the edge was visited + // on the first pass. + if ( extensiveFEdgeSearch ) { + // For each view edge, + for(ve=viewMap.ViewEdges().begin(), veend=viewMap.ViewEdges().end(); ve!=veend; ve++) { + if ( ! (*ve)->isInImage() ) { + continue; + } + // For each feature edge, + FEdge *festart = (*ve)->fedgeA(); + FEdge *fe = festart; + do { + // If not (already) visible and center point inside occluder proscenium, + if ( ! fe->isInImage() && insideProscenium(occluderProscenium, fe->center2d()) ) { + // Use the feature edge for visibility determination + fe->setIsInImage(true); + expandGridSpaceOccluderProscenium(fe); + } + fe = fe->nextEdge(); + } while ( fe != NULL && fe != festart ); + } + } + + // Up until now, all calculations have been done in camera space. + // However, the occluder source's iteration and the grid that consumes the occluders + // both work in gridspace, so we need a version of the occluder proscenium in gridspace. + // Set the gridspace occlude proscenium +} + +void CulledOccluderSource::expandGridSpaceOccluderProscenium(FEdge* fe) { + if ( gridSpaceOccluderProsceniumInitialized ) { + GridHelpers::expandProscenium (gridSpaceOccluderProscenium, transform(fe->center3d())); + } else { + const Vec3r& point = transform(fe->center3d()); + gridSpaceOccluderProscenium[0] = gridSpaceOccluderProscenium[1] = point[0]; + gridSpaceOccluderProscenium[2] = gridSpaceOccluderProscenium[3] = point[1]; + gridSpaceOccluderProsceniumInitialized = true; + } +} + diff --git a/source/blender/freestyle/intern/view_map/CulledOccluderSource.h b/source/blender/freestyle/intern/view_map/CulledOccluderSource.h new file mode 100644 index 00000000000..3c00d5e34ad --- /dev/null +++ b/source/blender/freestyle/intern/view_map/CulledOccluderSource.h @@ -0,0 +1,63 @@ +// +// Filename : CulledOccluderSource.h +// Author(s) : Alexander Beels +// Purpose : Class to define a cell grid surrounding +// the projected image of a scene +// Date of creation : 2010-12-21 +// +/////////////////////////////////////////////////////////////////////////////// + + +// +// 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 CULLEDOCCLUDERSOURCE_H +#define CULLEDOCCLUDERSOURCE_H + +#include "OccluderSource.h" +#include "ViewMap.h" + +class CulledOccluderSource : public OccluderSource { + // Disallow copying and assignment + CulledOccluderSource (const CulledOccluderSource& other); + CulledOccluderSource& operator= (const CulledOccluderSource& other); + +public: + CulledOccluderSource (const GridHelpers::Transform& transform, WingedEdge& we, ViewMap& viewMap, bool extensiveFEdgeSearch = true); + virtual ~CulledOccluderSource(); + + void cullViewEdges(ViewMap& viewMap, bool extensiveFEdgeSearch); + + bool next(); + + void getOccluderProscenium(real proscenium[4]); + +private: + bool testCurrent(); + void expandGridSpaceOccluderProscenium(FEdge* fe); + + real occluderProscenium[4]; + real gridSpaceOccluderProscenium[4]; + + unsigned long rejected; + bool gridSpaceOccluderProsceniumInitialized; +}; + +#endif // CULLEDOCCLUDERSOURCE_H diff --git a/source/blender/freestyle/intern/view_map/FEdgeXDetector.cpp b/source/blender/freestyle/intern/view_map/FEdgeXDetector.cpp index 16c38c63813..65fe146aec5 100755 --- a/source/blender/freestyle/intern/view_map/FEdgeXDetector.cpp +++ b/source/blender/freestyle/intern/view_map/FEdgeXDetector.cpp @@ -114,16 +114,18 @@ void FEdgeXDetector::preProcessShape(WXShape* iWShape) { preProcessFace((WXFace*)(*f)); } - vector<WVertex*>& wvertices = iWShape->getVertexList(); - for(vector<WVertex*>::iterator wv=wvertices.begin(), wvend=wvertices.end(); - wv!=wvend; - ++wv){ - // Compute curvatures - WXVertex * wxv = dynamic_cast<WXVertex*>(*wv); - computeCurvatures(wxv); + if(_faceSmoothness || _computeRidgesAndValleys || _computeSuggestiveContours ) { + vector<WVertex*>& wvertices = iWShape->getVertexList(); + for(vector<WVertex*>::iterator wv=wvertices.begin(), wvend=wvertices.end(); + wv!=wvend; + ++wv){ + // Compute curvatures + WXVertex * wxv = dynamic_cast<WXVertex*>(*wv); + computeCurvatures(wxv); + } + _meanK1 /= (real)(_nPoints); + _meanKr /= (real)(_nPoints); } - _meanK1 /= (real)(_nPoints); - _meanKr /= (real)(_nPoints); } void FEdgeXDetector::preProcessFace(WXFace *iFace){ @@ -603,7 +605,7 @@ void FEdgeXDetector::postProcessSuggestiveContourFace(WXFace *iFace) { WXVertex *v, *opposite_vertex_a, *opposite_vertex_b; WXFace *wxf; WOEdge *opposite_edge; - Vec3r opposite_edge_vec, normal_vec, radial_normal_vec, er_vec, v_vec, inter, inter1, inter2, tmp_vec; + Vec3r normal_vec, radial_normal_vec, er_vec, v_vec, inter, inter1, inter2, tmp_vec; GeomUtils::intersection_test res; real kr(0), kr1(0), kr2(0), t; @@ -629,12 +631,11 @@ void FEdgeXDetector::postProcessSuggestiveContourFace(WXFace *iFace) { opposite_vertex_a = (WXVertex*)opposite_edge->GetaVertex(); opposite_vertex_b = (WXVertex*)opposite_edge->GetbVertex(); - opposite_edge_vec = opposite_vertex_b->GetVertex() - opposite_vertex_a->GetVertex(); normal_vec = wxf->GetVertexNormal(v); // FIXME: what about e1 ^ e2 ? radial_normal_vec = er_vec ^ normal_vec; // Test wether the radial plan intersects with the edge at the opposite of v. - res = GeomUtils::intersectRayPlane(opposite_vertex_a->GetVertex(), opposite_edge_vec, + res = GeomUtils::intersectRayPlane(opposite_vertex_a->GetVertex(), opposite_edge->GetVec(), radial_normal_vec, -(v_vec * radial_normal_vec), t, 1.e-06); @@ -642,7 +643,7 @@ void FEdgeXDetector::postProcessSuggestiveContourFace(WXFace *iFace) { // If there is an intersection, compute the value of the derivative ath that point. if ((res == GeomUtils::DO_INTERSECT) && (t >= 0) && (t <= 1)) { kr = t * opposite_vertex_a->curvatures()->Kr + (1 - t) * opposite_vertex_b->curvatures()->Kr; - inter = opposite_vertex_a->GetVertex() + t * opposite_edge_vec; + inter = opposite_vertex_a->GetVertex() + t * opposite_edge->GetVec(); tmp_vec = inter - v->GetVertex(); // Is it kr1 or kr2? if (tmp_vec * er_vec > 0) { diff --git a/source/blender/freestyle/intern/view_map/FEdgeXDetector.h b/source/blender/freestyle/intern/view_map/FEdgeXDetector.h index 4cbaa4a7b5a..d08d75a84b6 100755 --- a/source/blender/freestyle/intern/view_map/FEdgeXDetector.h +++ b/source/blender/freestyle/intern/view_map/FEdgeXDetector.h @@ -58,6 +58,7 @@ public: _computeMaterialBoundaries = true; _sphereRadius = 1.0; _orthographicProjection = false; + _faceSmoothness = false; _changes = false; _kr_derivative_epsilon = 0.0; _creaseAngle = 0.7; // angle of 134.43 degrees @@ -135,6 +136,12 @@ public: inline void enableRidgesAndValleysFlag(bool b) {_computeRidgesAndValleys = b;} inline void enableSuggestiveContours(bool b) {_computeSuggestiveContours = b;} inline void enableMaterialBoundaries(bool b) {_computeMaterialBoundaries = b;} + inline void enableFaceSmoothness(bool b) { + if (b != _faceSmoothness) { + _faceSmoothness = b; + _changes=true; + } + } /*! Sets the radius of the geodesic sphere around each vertex (for the curvature computation) * \param r * The radius of the sphere expressed as a ratio of the mean edge size @@ -167,6 +174,7 @@ protected: bool _computeRidgesAndValleys; bool _computeSuggestiveContours; bool _computeMaterialBoundaries; + bool _faceSmoothness; real _sphereRadius; // expressed as a ratio of the mean edge size real _creaseAngle; // [-1, 1] compared with the inner product of face normals bool _changes; diff --git a/source/blender/freestyle/intern/view_map/GridDensityProvider.h b/source/blender/freestyle/intern/view_map/GridDensityProvider.h new file mode 100644 index 00000000000..078fc5f2c98 --- /dev/null +++ b/source/blender/freestyle/intern/view_map/GridDensityProvider.h @@ -0,0 +1,131 @@ +// +// Filename : GridDensityProvider.h +// Author(s) : Alexander Beels +// Purpose : Class to define a cell grid surrounding +// the projected image of a scene +// Date of creation : 2011-2-5 +// +/////////////////////////////////////////////////////////////////////////////// + + +// +// 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 GRIDDENSITYPROVIDER_H +#define GRIDDENSITYPROVIDER_H + +#include <stdexcept> +#include <memory> +#include "OccluderSource.h" +#include "../geometry/BBox.h" + +class GridDensityProvider { + // Disallow copying and assignment + GridDensityProvider (const GridDensityProvider& other); + GridDensityProvider& operator= (const GridDensityProvider& other); + +public: + GridDensityProvider (OccluderSource& source) + : source(source) { + } + + virtual ~GridDensityProvider() {}; + + float cellSize() { + return _cellSize; + } + + unsigned cellsX() { + return _cellsX; + } + + unsigned cellsY() { + return _cellsY; + } + + float cellOrigin(int index) { + if ( index < 2 ) { + return _cellOrigin[index]; + } else { + throw new out_of_range("GridDensityProvider::cellOrigin can take only indexes of 0 or 1."); + } + } + + static void calculateOptimalProscenium(OccluderSource& source, real proscenium[4]) { + source.begin(); + if ( source.isValid() ) { + const Vec3r& initialPoint = source.getGridSpacePolygon().getVertices()[0]; + proscenium[0] = proscenium[1] = initialPoint[0]; + proscenium[2] = proscenium[3] = initialPoint[1]; + while ( source.isValid() ) { + GridHelpers::expandProscenium (proscenium, source.getGridSpacePolygon()); + source.next(); + } + } + cout << "Proscenium: (" << proscenium[0] << ", " << proscenium[1] << ", " << proscenium[2] << ", " << proscenium[3] << ")" << endl; + } + + static void calculateQuickProscenium(const GridHelpers::Transform& transform, const BBox<Vec3r>& bbox, real proscenium[4]) { + real z; + // We want to use the z-coordinate closest to the camera to determine the proscenium face + if ( ::fabs(bbox.getMin()[2]) < ::fabs(bbox.getMax()[2]) ) { + z = bbox.getMin()[2]; + } else { + z = bbox.getMax()[2]; + } + // Now calculate the proscenium according to the min and max values of the x and y coordinates + Vec3r minPoint = transform(Vec3r(bbox.getMin()[0], bbox.getMin()[1], z)); + Vec3r maxPoint = transform(Vec3r(bbox.getMax()[0], bbox.getMax()[1], z)); + cout << "Bounding box: " << minPoint << " to " << maxPoint << endl; + proscenium[0] = std::min(minPoint[0], maxPoint[0]); + proscenium[1] = std::max(minPoint[0], maxPoint[0]); + proscenium[2] = std::min(minPoint[1], maxPoint[1]); + proscenium[3] = std::max(minPoint[1], maxPoint[1]); + cout << "Proscenium : " << proscenium[0] << ", " << proscenium[1] << ", " << proscenium[2] << ", " << proscenium[3] << endl; + } + +protected: + OccluderSource& source; + unsigned _cellsX, _cellsY; + float _cellSize; + float _cellOrigin[2]; +}; + +class GridDensityProviderFactory { + // Disallow copying and assignment + GridDensityProviderFactory (const GridDensityProviderFactory& other); + GridDensityProviderFactory& operator= (const GridDensityProviderFactory& other); + +public: + GridDensityProviderFactory() + { + } + + virtual auto_ptr<GridDensityProvider> newGridDensityProvider(OccluderSource& source, const real proscenium[4]) =0; + + virtual auto_ptr<GridDensityProvider> newGridDensityProvider(OccluderSource& source, const BBox<Vec3r>& bbox, const GridHelpers::Transform& transform) =0; + + virtual auto_ptr<GridDensityProvider> newGridDensityProvider(OccluderSource& source) =0; + + virtual ~GridDensityProviderFactory () {} +}; + +#endif // GRIDDENSITYPROVIDER_H + diff --git a/source/blender/freestyle/intern/view_map/HeuristicGridDensityProviderFactory.cpp b/source/blender/freestyle/intern/view_map/HeuristicGridDensityProviderFactory.cpp new file mode 100644 index 00000000000..05b70af90b3 --- /dev/null +++ b/source/blender/freestyle/intern/view_map/HeuristicGridDensityProviderFactory.cpp @@ -0,0 +1,74 @@ +// +// Filename : HeuristicGridDensityProviderFactory.cpp +// Author(s) : Alexander Beels +// Purpose : Class to define a cell grid surrounding +// the projected image of a scene +// Date of creation : 2011-2-8 +// +/////////////////////////////////////////////////////////////////////////////// + + +// +// 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. +// +/////////////////////////////////////////////////////////////////////////////// + +#include "HeuristicGridDensityProviderFactory.h" + +HeuristicGridDensityProviderFactory::HeuristicGridDensityProviderFactory(real sizeFactor, unsigned numFaces) + : sizeFactor(sizeFactor), numFaces(numFaces) +{ +} + +HeuristicGridDensityProviderFactory::~HeuristicGridDensityProviderFactory () {} + +auto_ptr<GridDensityProvider> HeuristicGridDensityProviderFactory::newGridDensityProvider(OccluderSource& source, const real proscenium[4]) +{ + auto_ptr<AverageAreaGridDensityProvider> avg(new AverageAreaGridDensityProvider(source, proscenium, sizeFactor)); + auto_ptr<Pow23GridDensityProvider> p23(new Pow23GridDensityProvider(source, proscenium, numFaces)); + if ( avg->cellSize() > p23->cellSize() ) { + return (auto_ptr<GridDensityProvider>) p23; + } else { + return (auto_ptr<GridDensityProvider>) avg; + } +} + +auto_ptr<GridDensityProvider> HeuristicGridDensityProviderFactory::newGridDensityProvider(OccluderSource& source, const BBox<Vec3r>& bbox, const GridHelpers::Transform& transform) +{ + auto_ptr<AverageAreaGridDensityProvider> avg(new AverageAreaGridDensityProvider(source, bbox, transform, sizeFactor)); + auto_ptr<Pow23GridDensityProvider> p23(new Pow23GridDensityProvider(source, bbox, transform, numFaces)); + if ( avg->cellSize() > p23->cellSize() ) { + return (auto_ptr<GridDensityProvider>) p23; + } else { + return (auto_ptr<GridDensityProvider>) avg; + } +} + +auto_ptr<GridDensityProvider> HeuristicGridDensityProviderFactory::newGridDensityProvider(OccluderSource& source) +{ + real proscenium[4]; + GridDensityProvider::calculateOptimalProscenium(source, proscenium); + auto_ptr<AverageAreaGridDensityProvider> avg(new AverageAreaGridDensityProvider(source, proscenium, sizeFactor)); + auto_ptr<Pow23GridDensityProvider> p23(new Pow23GridDensityProvider(source, proscenium, numFaces)); + if ( avg->cellSize() > p23->cellSize() ) { + return (auto_ptr<GridDensityProvider>) p23; + } else { + return (auto_ptr<GridDensityProvider>) avg; + } +} + diff --git a/source/blender/freestyle/intern/view_map/HeuristicGridDensityProviderFactory.h b/source/blender/freestyle/intern/view_map/HeuristicGridDensityProviderFactory.h new file mode 100644 index 00000000000..d32c4ae4407 --- /dev/null +++ b/source/blender/freestyle/intern/view_map/HeuristicGridDensityProviderFactory.h @@ -0,0 +1,54 @@ +// +// Filename : HeuristicGridDensityProviderFactory.h +// Author(s) : Alexander Beels +// Purpose : Class to define a cell grid surrounding +// the projected image of a scene +// Date of creation : 2011-2-8 +// +/////////////////////////////////////////////////////////////////////////////// + + +// +// 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 HEURISTICGRIDDENSITYPROVIDERFACTORY_H +#define HEURISTICGRIDDENSITYPROVIDERFACTORY_H + +// #include <memory> // provided by GridDensityProvider.h +// #include "GridDensityProvider.h" // provided by *GridDensityProvider.h below +#include "Pow23GridDensityProvider.h" +#include "AverageAreaGridDensityProvider.h" + +class HeuristicGridDensityProviderFactory : public GridDensityProviderFactory { +public: + HeuristicGridDensityProviderFactory(real sizeFactor, unsigned numFaces); + ~HeuristicGridDensityProviderFactory (); + + auto_ptr<GridDensityProvider> newGridDensityProvider(OccluderSource& source, const real proscenium[4]); + auto_ptr<GridDensityProvider> newGridDensityProvider(OccluderSource& source, const BBox<Vec3r>& bbox, const GridHelpers::Transform& transform); + auto_ptr<GridDensityProvider> newGridDensityProvider(OccluderSource& source); + +protected: + real sizeFactor; + unsigned numFaces; +}; + +#endif // HEURISTICGRIDDENSITYPROVIDERFACTORY_H + diff --git a/source/blender/freestyle/intern/view_map/OccluderSource.cpp b/source/blender/freestyle/intern/view_map/OccluderSource.cpp new file mode 100644 index 00000000000..356e281be4b --- /dev/null +++ b/source/blender/freestyle/intern/view_map/OccluderSource.cpp @@ -0,0 +1,132 @@ +// +// Filename : OccluderSource.h +// Author(s) : Alexander Beels +// Purpose : Class to define a cell grid surrounding +// the projected image of a scene +// Date of creation : 2010-12-21 +// +/////////////////////////////////////////////////////////////////////////////// + + +// +// 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. +// +/////////////////////////////////////////////////////////////////////////////// + +#include "OccluderSource.h" +#include <algorithm> + +OccluderSource::OccluderSource (const GridHelpers::Transform& t, WingedEdge& we) : wingedEdge(we), valid(false), transform(t) { + begin(); +} + +OccluderSource::~OccluderSource() { +} + +void OccluderSource::buildCachedPolygon() { + vector<Vec3r> vertices(GridHelpers::enumerateVertices((*currentFace)->getEdgeList())); + // This doesn't work, because our functor's polymorphism won't survive the copy: + // std::transform(vertices.begin(), vertices.end(), vertices.begin(), transform); + // so we have to do: + for ( vector<Vec3r>::iterator i = vertices.begin(); i != vertices.end(); ++i ) { + (*i) = transform(*i); + } + cachedPolygon = Polygon3r(vertices, transform((*currentFace)->GetNormal())); +} + +void OccluderSource::begin() { + vector<WShape*>& wshapes = wingedEdge.getWShapes(); + currentShape = wshapes.begin(); + shapesEnd = wshapes.end(); + valid = false; + if ( currentShape != shapesEnd ) { + vector<WFace*>& wFaces = (*currentShape)->GetFaceList(); + currentFace = wFaces.begin(); + facesEnd = wFaces.end(); + + if ( currentFace != facesEnd ) { + buildCachedPolygon(); + valid = true; + } + } +} + +bool OccluderSource::next() { + if ( valid ) { + ++currentFace; + while ( currentFace == facesEnd ) { + ++currentShape; + if ( currentShape == shapesEnd ) { + valid = false; + return false; + } else { + vector<WFace*>& wFaces = (*currentShape)->GetFaceList(); + currentFace = wFaces.begin(); + facesEnd = wFaces.end(); + } + } + buildCachedPolygon(); + return true; + } + return false; +} + +bool OccluderSource::isValid() { + // Or: + // return currentShapes != shapesEnd && currentFace != facesEnd; + return valid; +} + +WFace* OccluderSource::getWFace() { + return valid ? *currentFace : NULL; +} + +Polygon3r OccluderSource::getCameraSpacePolygon() { + return Polygon3r(GridHelpers::enumerateVertices((*currentFace)->getEdgeList()), (*currentFace)->GetNormal()); +} + +Polygon3r& OccluderSource::getGridSpacePolygon() { + return cachedPolygon; +} + +void OccluderSource::getOccluderProscenium(real proscenium[4]) { + begin(); + const Vec3r& initialPoint = cachedPolygon.getVertices()[0]; + proscenium[0] = proscenium[1] = initialPoint[0]; + proscenium[2] = proscenium[3] = initialPoint[1]; + while ( isValid() ) { + GridHelpers::expandProscenium (proscenium, cachedPolygon); + next(); + } + cout << "Proscenium: (" << proscenium[0] << ", " << proscenium[1] << ", " << proscenium[2] << ", " << proscenium[3] << ")" << endl; +} + +real OccluderSource::averageOccluderArea() { + real area = 0.0; + unsigned numFaces = 0; + for ( begin(); isValid(); next() ) { + Vec3r min, max; + cachedPolygon.getBBox(min, max); + area += (max[0] - min[0]) * (max[1] - min[1]); + ++numFaces; + } + area /= numFaces; + return area; +} + + diff --git a/source/blender/freestyle/intern/view_map/OccluderSource.h b/source/blender/freestyle/intern/view_map/OccluderSource.h new file mode 100644 index 00000000000..d623cc63fed --- /dev/null +++ b/source/blender/freestyle/intern/view_map/OccluderSource.h @@ -0,0 +1,70 @@ +// +// Filename : OccluderSource.h +// Author(s) : Alexander Beels +// Purpose : Class to define a cell grid surrounding +// the projected image of a scene +// Date of creation : 2010-12-21 +// +/////////////////////////////////////////////////////////////////////////////// + + +// +// 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 OCCLUDERSOURCE_H +#define OCCLUDERSOURCE_H + +#include "../winged_edge/WEdge.h" +#include "../geometry/GridHelpers.h" + +class OccluderSource { + // Disallow copying and assignment + OccluderSource (const OccluderSource& other); + OccluderSource& operator= (const OccluderSource& other); + +public: + OccluderSource (const GridHelpers::Transform& transform, WingedEdge& we); + virtual ~OccluderSource(); + + void begin(); + virtual bool next(); + bool isValid(); + + WFace* getWFace(); + Polygon3r getCameraSpacePolygon(); + Polygon3r& getGridSpacePolygon(); + + virtual void getOccluderProscenium(real proscenium[4]); + virtual real averageOccluderArea(); + +protected: + WingedEdge& wingedEdge; + vector<WShape*>::const_iterator currentShape, shapesEnd; + vector<WFace*>::const_iterator currentFace, facesEnd; + + bool valid; + + Polygon3r cachedPolygon; + const GridHelpers::Transform& transform; + + void buildCachedPolygon(); +}; + +#endif // OCCLUDERSOURCE_H diff --git a/source/blender/freestyle/intern/view_map/Pow23GridDensityProvider.cpp b/source/blender/freestyle/intern/view_map/Pow23GridDensityProvider.cpp new file mode 100644 index 00000000000..2e506da9ee9 --- /dev/null +++ b/source/blender/freestyle/intern/view_map/Pow23GridDensityProvider.cpp @@ -0,0 +1,109 @@ +// +// Filename : Pow23GridDensityProvider.cpp +// Author(s) : Alexander Beels +// Purpose : Class to define a cell grid surrounding +// the projected image of a scene +// Date of creation : 2011-2-8 +// +/////////////////////////////////////////////////////////////////////////////// + + +// +// 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. +// +/////////////////////////////////////////////////////////////////////////////// + +#include "Pow23GridDensityProvider.h" + +Pow23GridDensityProvider::Pow23GridDensityProvider(OccluderSource& source, const real proscenium[4], unsigned numFaces) + : GridDensityProvider(source), numFaces(numFaces) +{ + initialize (proscenium); +} + +Pow23GridDensityProvider::Pow23GridDensityProvider(OccluderSource& source, const BBox<Vec3r>& bbox, const GridHelpers::Transform& transform, unsigned numFaces) + : GridDensityProvider(source), numFaces(numFaces) +{ + real proscenium[4]; + calculateQuickProscenium(transform, bbox, proscenium); + + initialize (proscenium); +} + +Pow23GridDensityProvider::Pow23GridDensityProvider(OccluderSource& source, unsigned numFaces) + : GridDensityProvider(source), numFaces(numFaces) +{ + real proscenium[4]; + calculateOptimalProscenium(source, proscenium); + + initialize (proscenium); +} + +Pow23GridDensityProvider::~Pow23GridDensityProvider () {} + +void Pow23GridDensityProvider::initialize (const real proscenium[4]) +{ + float prosceniumWidth = (proscenium[1] - proscenium[0]); + float prosceniumHeight = (proscenium[3] - proscenium[2]); + real cellArea = prosceniumWidth * prosceniumHeight / pow(numFaces, 2.0f / 3.0f); + cout << prosceniumWidth << " x " << prosceniumHeight << " grid with cells of area " << cellArea << "." << endl; + + _cellSize = sqrt(cellArea); + // Now we know how many cells make each side of our grid + _cellsX = ceil(prosceniumWidth / _cellSize); + _cellsY = ceil(prosceniumHeight / _cellSize); + cout << _cellsX << "x" << _cellsY << " cells of size " << _cellSize << " square." << endl; + + // Make sure the grid exceeds the proscenium by a small amount + float safetyZone = 0.1; + if ( _cellsX * _cellSize < prosceniumWidth * (1.0 + safetyZone) ) { + _cellsX = prosceniumWidth * (1.0 + safetyZone) / _cellSize; + } + if ( _cellsY * _cellSize < prosceniumHeight * (1.0 + safetyZone) ) { + _cellsY = prosceniumHeight * (1.0 + safetyZone) / _cellSize; + } + cout << _cellsX << "x" << _cellsY << " cells of size " << _cellSize << " square." << endl; + + // Find grid origin + _cellOrigin[0] = ((proscenium[0] + proscenium[1]) / 2.0) - (_cellsX / 2.0) * _cellSize; + _cellOrigin[1] = ((proscenium[2] + proscenium[3]) / 2.0) - (_cellsY / 2.0) * _cellSize; +} + +Pow23GridDensityProviderFactory::Pow23GridDensityProviderFactory(unsigned numFaces) + : numFaces(numFaces) +{ +} + +Pow23GridDensityProviderFactory::~Pow23GridDensityProviderFactory () {} + +auto_ptr<GridDensityProvider> Pow23GridDensityProviderFactory::newGridDensityProvider(OccluderSource& source, const real proscenium[4]) +{ + return auto_ptr<GridDensityProvider>(new Pow23GridDensityProvider(source, proscenium, numFaces)); +} + +auto_ptr<GridDensityProvider> Pow23GridDensityProviderFactory::newGridDensityProvider(OccluderSource& source, const BBox<Vec3r>& bbox, const GridHelpers::Transform& transform) +{ + return auto_ptr<GridDensityProvider>(new Pow23GridDensityProvider(source, bbox, transform, numFaces)); +} + +auto_ptr<GridDensityProvider> Pow23GridDensityProviderFactory::newGridDensityProvider(OccluderSource& source) +{ + return auto_ptr<GridDensityProvider>(new Pow23GridDensityProvider(source, numFaces)); +} + + diff --git a/source/blender/freestyle/intern/view_map/Pow23GridDensityProvider.h b/source/blender/freestyle/intern/view_map/Pow23GridDensityProvider.h new file mode 100644 index 00000000000..c398a1643a4 --- /dev/null +++ b/source/blender/freestyle/intern/view_map/Pow23GridDensityProvider.h @@ -0,0 +1,67 @@ +// +// Filename : Pow23GridDensityProvider.h +// Author(s) : Alexander Beels +// Purpose : Class to define a cell grid surrounding +// the projected image of a scene +// Date of creation : 2011-2-8 +// +/////////////////////////////////////////////////////////////////////////////// + + +// +// 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 POW23GRIDDENSITYPROVIDER_H +#define POW23GRIDDENSITYPROVIDER_H + +#include "GridDensityProvider.h" + +class Pow23GridDensityProvider : public GridDensityProvider { + // Disallow copying and assignment + Pow23GridDensityProvider (const Pow23GridDensityProvider& other); + Pow23GridDensityProvider& operator= (const Pow23GridDensityProvider& other); + +public: + Pow23GridDensityProvider(OccluderSource& source, const real proscenium[4], unsigned numFaces); + Pow23GridDensityProvider(OccluderSource& source, const BBox<Vec3r>& bbox, const GridHelpers::Transform& transform, unsigned numFaces); + Pow23GridDensityProvider(OccluderSource& source, unsigned numFaces); + virtual ~Pow23GridDensityProvider (); + +protected: + unsigned numFaces; + +private: + void initialize (const real proscenium[4]); +}; + +class Pow23GridDensityProviderFactory : public GridDensityProviderFactory { +public: + Pow23GridDensityProviderFactory(unsigned numFaces); + ~Pow23GridDensityProviderFactory (); + + auto_ptr<GridDensityProvider> newGridDensityProvider(OccluderSource& source, const real proscenium[4]); + auto_ptr<GridDensityProvider> newGridDensityProvider(OccluderSource& source, const BBox<Vec3r>& bbox, const GridHelpers::Transform& transform); + auto_ptr<GridDensityProvider> newGridDensityProvider(OccluderSource& source); +protected: + unsigned numFaces; +}; + +#endif // POW23GRIDDENSITYPROVIDER_H + diff --git a/source/blender/freestyle/intern/view_map/Silhouette.h b/source/blender/freestyle/intern/view_map/Silhouette.h index 86a4efcdc48..da337c1d0b3 100755 --- a/source/blender/freestyle/intern/view_map/Silhouette.h +++ b/source/blender/freestyle/intern/view_map/Silhouette.h @@ -404,6 +404,8 @@ protected: bool _isSmooth; + bool _isInImage; + public: /*! A field that can be used by the user to store any data. * This field must be reseted afterwards using ResetUserData(). @@ -421,6 +423,7 @@ public: //_hasVisibilityPoint=false; _occludeeEmpty = true; _isSmooth = false; + _isInImage = true; } /*! Builds an FEdge going from vA to vB. */ inline FEdge(SVertex *vA, SVertex *vB) { @@ -434,6 +437,7 @@ public: //_hasVisibilityPoint=false; _occludeeEmpty = true; _isSmooth = false; + _isInImage = true; } /*! Copy constructor */ inline FEdge(FEdge& iBrother) @@ -451,6 +455,7 @@ public: _aFace = iBrother._aFace; _occludeeEmpty = iBrother._occludeeEmpty; _isSmooth = iBrother._isSmooth; + _isInImage = iBrother._isInImage; iBrother.userdata = this; userdata = 0; } @@ -498,6 +503,7 @@ public: inline bool getOccludeeEmpty() { return _occludeeEmpty; } /*! Returns true if this FEdge is a smooth FEdge. */ inline bool isSmooth() const {return _isSmooth;} + inline bool isInImage () const { return _isInImage; } /* modifiers */ /*! Sets the first SVertex. */ @@ -525,6 +531,7 @@ public: * true for Smooth, false for Sharp. */ inline void setSmooth(bool iFlag) {_isSmooth = iFlag;} + inline void setIsInImage (bool iFlag) { _isInImage = iFlag; } /* checks whether two FEdge have a common vertex. * Returns a pointer on the common vertex if it exists, diff --git a/source/blender/freestyle/intern/view_map/SphericalGrid.cpp b/source/blender/freestyle/intern/view_map/SphericalGrid.cpp new file mode 100644 index 00000000000..c1647050d0d --- /dev/null +++ b/source/blender/freestyle/intern/view_map/SphericalGrid.cpp @@ -0,0 +1,221 @@ +// +// 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. +// +/////////////////////////////////////////////////////////////////////////////// + +#include "SphericalGrid.h" + +#include <stdexcept> +#include <algorithm> + +using namespace std; + +// Helper Classes + +// OccluderData +/////////////// + +// Cell +///////// + +SphericalGrid::Cell::Cell () {} + +SphericalGrid::Cell::~Cell () {} + +void SphericalGrid::Cell::setDimensions(real x, real y, real sizeX, real sizeY) { + const real epsilon = 1.0e-06; + boundary[0] = x - epsilon; + boundary[1] = x + sizeX + epsilon; + boundary[2] = y - epsilon; + boundary[3] = y + sizeY + epsilon; +} + +bool SphericalGrid::Cell::compareOccludersByShallowestPoint (const SphericalGrid::OccluderData* a, const SphericalGrid::OccluderData* b) { + return a->shallowest < b->shallowest; +} + +void SphericalGrid::Cell::indexPolygons() { + // Sort occluders by their shallowest points. + sort(faces.begin(), faces.end(), compareOccludersByShallowestPoint); +} + +// Iterator +////////////////// + +SphericalGrid::Iterator::Iterator (SphericalGrid& grid, Vec3r& center, real epsilon) + : _target(SphericalGrid::Transform::sphericalProjection(center)), + _foundOccludee(false) +{ + // Find target cell + _cell = grid.findCell(_target); + #if sphericalgridlogging == 1 + cout << "Searching for occluders of edge centered at " << _target << " in cell [" + << _cell->boundary[0] << ", " << _cell->boundary[1] << ", " << _cell->boundary[2] + << ", " << _cell->boundary[3] << "] (" << _cell->faces.size() << " occluders)" << endl; + #endif + + // Set iterator + _current = _cell->faces.begin(); +} + +SphericalGrid::Iterator::~Iterator () {} + +// SphericalGrid +///////////////// + +SphericalGrid::SphericalGrid(OccluderSource& source, GridDensityProvider& density, ViewMap *viewMap, Vec3r& viewpoint, bool enableQI) + : _viewpoint(viewpoint), + _enableQI(enableQI) +{ + cout << "Generate Cell structure" << endl; + // Generate Cell structure + assignCells(source, density, viewMap); + cout << "Distribute occluders" << endl; + // Fill Cells + distributePolygons(source); + cout << "Reorganize cells" << endl; + // Reorganize Cells + reorganizeCells(); + cout << "Ready to use SphericalGrid" << endl; +} + +SphericalGrid::~SphericalGrid () { +} + +void SphericalGrid::assignCells (OccluderSource& source, GridDensityProvider& density, ViewMap *viewMap) { + _cellSize = density.cellSize(); + _cellsX = density.cellsX(); + _cellsY = density.cellsY(); + _cellOrigin[0] = density.cellOrigin(0); + _cellOrigin[1] = density.cellOrigin(1); + + // Now allocate the cell table and fill it with default (empty) cells + _cells.resize(_cellsX * _cellsY); + for ( cellContainer::iterator i = _cells.begin(), end = _cells.end(); i != end; ++i ) { + (*i) = NULL; + } + + // Identify cells that will be used, and set the dimensions for each + ViewMap::fedges_container& fedges = viewMap->FEdges(); + for (ViewMap::fedges_container::iterator f = fedges.begin(), fend = fedges.end(); f != fend; ++f ) { + if ( (*f)->isInImage() ) { + Vec3r point = SphericalGrid::Transform::sphericalProjection((*f)->center3d()); + unsigned i, j; + getCellCoordinates(point, i, j); + if ( _cells[i * _cellsY + j] == NULL ) { + // This is an uninitialized cell + + real x, y, width, height; + + x = _cellOrigin[0] + _cellSize * i; + width = _cellSize; + + y = _cellOrigin[1] + _cellSize * j; + height = _cellSize; + + // Initialize cell + Cell* b = _cells[i * _cellsY + j] = new Cell(); + b->setDimensions(x, y, width, height); + } + } + } +} + +void SphericalGrid::distributePolygons (OccluderSource& source) { + unsigned long nFaces = 0; + unsigned long nKeptFaces = 0; + + for ( source.begin(); source.isValid(); source.next() ) { + OccluderData* occluder = NULL; + + try { + if ( insertOccluder(source, occluder) ) { + _faces.push_back(occluder); + ++nKeptFaces; + } + } catch (...) { + // If an exception was thrown, _faces.push_back() cannot have succeeded. + // occluder is not owned by anyone, and must be deleted. + // If the exception was thrown before or during new OccluderData(), then + // occluder is NULL, and this delete is harmless. + delete occluder; + throw; + } + ++nFaces; + } + cout << "Distributed " << nFaces << " occluders. Retained " << nKeptFaces << "." << endl; +} + +void SphericalGrid::reorganizeCells () { + // Sort the occluders by shallowest point + for ( vector<Cell*>::iterator i = _cells.begin(), end = _cells.end(); i != end; ++i ) { + if ( *i != NULL ) { + (*i)->indexPolygons(); + } + } +} + +void SphericalGrid::getCellCoordinates(const Vec3r& point, unsigned& x, unsigned& y) { + x = min(_cellsX - 1, (unsigned) floor (max((double) 0.0f, point[0] - _cellOrigin[0]) / _cellSize)); + y = min(_cellsY - 1, (unsigned) floor (max((double) 0.0f, point[1] - _cellOrigin[1]) / _cellSize)); +} + +SphericalGrid::Cell* SphericalGrid::findCell(const Vec3r& point) { + unsigned x, y; + getCellCoordinates(point, x, y); + return _cells[x * _cellsY + y]; +} + +bool SphericalGrid::orthographicProjection () const { + return false; +} + +const Vec3r& SphericalGrid::viewpoint() const { + return _viewpoint; +} + +bool SphericalGrid::enableQI() const { + return _enableQI; +} + +SphericalGrid::Transform::Transform () : GridHelpers::Transform() { +} + +Vec3r SphericalGrid::Transform::operator() (const Vec3r& point) const { + return sphericalProjection(point); +} + +Vec3r SphericalGrid::Transform::sphericalProjection(const Vec3r& M) { + Vec3r newPoint; + + newPoint[0] = ::atan(M[0] / M[2]); + newPoint[1] = ::atan(M[1] / M[2]); + newPoint[2] = ::sqrt(M[0] * M[0] + M[1] * M[1] + M[2] * M[2]); + + return newPoint; +} + diff --git a/source/blender/freestyle/intern/view_map/SphericalGrid.h b/source/blender/freestyle/intern/view_map/SphericalGrid.h new file mode 100644 index 00000000000..55cdee19a80 --- /dev/null +++ b/source/blender/freestyle/intern/view_map/SphericalGrid.h @@ -0,0 +1,388 @@ +// +// 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. +//#include <vector> +//#include <deque> +#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" + +class SphericalGrid +{ +public: + // Helper classes + 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; + }; + +private: + struct Cell { + // Can't store Cell in a vector without copy and assign + //Cell(const Cell& other); + //Cell& operator= (const Cell& other); + + explicit Cell (); + ~Cell (); + + 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); + void indexPolygons(); + + real boundary[4]; + //deque<OccluderData*> faces; + vector<OccluderData*> faces; + }; + +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 { + 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 (); + bool validBeforeTarget(); + bool validAfterTarget(); + WFace* getWFace() const; + Polygon3r* getCameraSpacePolygon(); + void reportDepth(Vec3r origin, Vec3r u, real t); + private: + bool testOccluder(bool wantOccludee); + void markCurrentOccludeeCandidate(real depth); + + Cell* _cell; + Vec3r _target; + bool _foundOccludee; + real _occludeeDepth; + //deque<OccluderData*>::iterator _current, _occludeeCandidate; + vector<OccluderData*>::iterator _current, _occludeeCandidate; + }; + + class Transform : public GridHelpers::Transform { + public: + 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); +public: + 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 + bool insertOccluder(OccluderSource& source, OccluderData*& occluder); + // Sort occluders in each cell + void reorganizeCells(); + + Cell* findCell(const Vec3r& point); + + // Accessors: + bool orthographicProjection() const; + const Vec3r& viewpoint() const; + bool enableQI() const; + +private: + void getCellCoordinates(const Vec3r& point, unsigned& x, unsigned& y); + + typedef PointerSequence<vector<Cell*>, Cell*> cellContainer; + //typedef PointerSequence<deque<OccluderData*>, OccluderData*> occluderContainer; + typedef PointerSequence<vector<OccluderData*>, OccluderData*> occluderContainer; + unsigned _cellsX, _cellsY; + float _cellSize; + float _cellOrigin[2]; + cellContainer _cells; + occluderContainer _faces; + Vec3r _viewpoint; + bool _enableQI; +}; + +inline void SphericalGrid::Iterator::initBeforeTarget () { + _current = _cell->faces.begin(); + while ( _current != _cell->faces.end() && ! testOccluder(false) ) { + ++_current; + } +} + +inline void SphericalGrid::Iterator::initAfterTarget () { + if ( _foundOccludee ) { + #if sphericalgridlogging == 1 + std::cout << "\tStarting occludee search from occludeeCandidate at depth " << _occludeeDepth << std::endl; + #endif + _current = _occludeeCandidate; + return; + } + + #if sphericalgridlogging == 1 + std::cout << "\tStarting occludee search from current position" << std::endl; + #endif + + while ( _current != _cell->faces.end() && ! testOccluder(true) ) { + ++_current; + } +} + +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. + return true; + } + #if sphericalgridlogging == 1 + std::cout << "\tTesting occluder " << (*_current)->poly.getVertices()[0]; + for ( unsigned 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 + std::cout << "\t\tAborting: shallowest > occludeeCandidate->deepest" << std::endl; + #endif + _current = _cell->faces.end(); + + // See note above + return true; + } + + // Specific continue or stop conditions when searching for each type + if ( wantOccludee ) { + if ( (*_current)->deepest < _target[2] ) { + #if sphericalgridlogging == 1 + 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 + std::cout << "\t\tStopping: deeper than target while looking for occluder" << std::endl; + #endif + return true; + } + } + + // Depthwise, this is a valid occluder. + + // 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 + 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. + 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. + real depth = (origin + u * t).norm(); + #if sphericalgridlogging == 1 + std::cout << "\t\tReporting depth of occluder/ee: " << depth; + #endif + if ( depth > _target[2] ) { + #if sphericalgridlogging == 1 + 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 ) { + markCurrentOccludeeCandidate(depth); + } + } else { + #if sphericalgridlogging == 1 + std::cout << std::endl; + #endif + } +} + +inline void SphericalGrid::Iterator::nextOccluder () { + if ( _current != _cell->faces.end() ) { + do { + ++_current; + } while ( _current != _cell->faces.end() && ! testOccluder(false) ); + } +} + +inline void SphericalGrid::Iterator::nextOccludee () { + if ( _current != _cell->faces.end() ) { + do { + ++_current; + } while ( _current != _cell->faces.end() && ! testOccluder(true) ); + } +} + +inline bool SphericalGrid::Iterator::validBeforeTarget () { + return _current != _cell->faces.end() && (*_current)->shallowest <= _target[2]; +} + +inline bool SphericalGrid::Iterator::validAfterTarget () { + return _current != _cell->faces.end(); +} + +inline void SphericalGrid::Iterator::markCurrentOccludeeCandidate(real depth) { + #if sphericalgridlogging == 1 + std::cout << "\t\tFound occludeeCandidate at depth " << depth << std::endl; + #endif + _occludeeCandidate = _current; + _occludeeDepth = depth; + _foundOccludee = true; +} + +inline WFace* SphericalGrid::Iterator::getWFace() const { + return (*_current)->face; +} + +inline Polygon3r* SphericalGrid::Iterator::getCameraSpacePolygon() { + return &((*_current)->cameraSpacePolygon); +} + +inline SphericalGrid::OccluderData::OccluderData (OccluderSource& source, Polygon3r& p) + : 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 + // shallowest is the distance from the viewpoint to that point + shallowest = GridHelpers::distancePointToPolygon(viewpoint, cameraSpacePolygon); + + // 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 ) { + real t = cameraSpacePolygon.getVertices()[i].norm(); + if ( t > deepest ) { + deepest = t; + } + } +} + +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); + } + faces.push_back(occluder); + } +} + +inline bool SphericalGrid::insertOccluder(OccluderSource& source, OccluderData*& occluder) { + Polygon3r& poly(source.getGridSpacePolygon()); + occluder = NULL; + + Vec3r bbMin, bbMax; + poly.getBBox(bbMin, bbMax); + // Check overlapping cells + unsigned startX, startY, endX, endY; + 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 ) { + _cells[i * _cellsY + j]->checkAndInsert(source, poly, occluder); + } + } + } + + return occluder != NULL; +} + +#endif // SPHERICALGRID_H + diff --git a/source/blender/freestyle/intern/view_map/ViewMap.h b/source/blender/freestyle/intern/view_map/ViewMap.h index a0e60ff7bd7..d2d7a9a5341 100755 --- a/source/blender/freestyle/intern/view_map/ViewMap.h +++ b/source/blender/freestyle/intern/view_map/ViewMap.h @@ -801,6 +801,7 @@ private: // and _aShape is the one on its right // NON GERE PAR LE COPY CONSTRUCTEUR int _qi; vector<ViewShape*> _Occluders; + bool _isInImage; // tmp Id * _splittingId; @@ -821,6 +822,7 @@ public: _aShape=0; userdata = 0; _splittingId = 0; + _isInImage = true; } inline ViewEdge(ViewVertex* iA, ViewVertex *iB) { @@ -834,6 +836,7 @@ public: _qi = 0; userdata = 0; _splittingId = 0; + _isInImage = true; } inline ViewEdge(ViewVertex* iA, ViewVertex *iB, FEdge *iFEdgeA) { @@ -847,6 +850,7 @@ public: _qi = 0; userdata = 0; _splittingId = 0; + _isInImage = true; } inline ViewEdge(ViewVertex* iA, ViewVertex *iB, FEdge *iFEdgeA, FEdge *iFEdgeB, ViewShape *iShape) { @@ -860,6 +864,7 @@ public: _qi = 0; userdata = 0; _splittingId = 0; + _isInImage = true; UpdateFEdges(); // tells every FEdge between iFEdgeA and iFEdgeB that this is theit ViewEdge } @@ -879,6 +884,7 @@ public: _aShape = iBrother._aShape; _qi = iBrother._qi; _splittingId = 0; + _isInImage = iBrother._isInImage; iBrother.userdata = this; userdata = 0; } @@ -937,6 +943,7 @@ public: inline const ViewShape * bShape() const {return _Shape;} inline vector<ViewShape*>& occluders() {return _Occluders;} inline Id * splittingId() {return _splittingId;} + inline bool isInImage() const { return _isInImage; } /* modifiers */ /*! Sets the first ViewVertex of the ViewEdge. */ @@ -966,6 +973,7 @@ public: inline void setChainingTimeStamp(unsigned ts) {_ChainingTimeStamp = ts;} inline void AddOccluder(ViewShape *iShape) {_Occluders.push_back(iShape);} inline void setSplittingId(Id * id) {_splittingId = id;} + inline void setIsInImage(bool iFlag) { _isInImage = iFlag; } /* stroke interface definition */ inline bool intersect_2d_area(const Vec2r& iMin, const Vec2r& iMax) const diff --git a/source/blender/freestyle/intern/view_map/ViewMapBuilder.cpp b/source/blender/freestyle/intern/view_map/ViewMapBuilder.cpp index dbd046f050a..242b769e8b5 100755 --- a/source/blender/freestyle/intern/view_map/ViewMapBuilder.cpp +++ b/source/blender/freestyle/intern/view_map/ViewMapBuilder.cpp @@ -21,15 +21,897 @@ #include "ViewMapBuilder.h" #include <algorithm> +#include <stdexcept> +#include <memory> +#include "../winged_edge/WFillGrid.h" +#include "../../FRS_freestyle.h" +#include "../geometry/GeomUtils.h" +#include "../geometry/GridHelpers.h" +#include "BoxGrid.h" +#include "SphericalGrid.h" +#include "OccluderSource.h" +#include "CulledOccluderSource.h" +#include "HeuristicGridDensityProviderFactory.h" + +#define logging 0 using namespace std; -ViewMap* ViewMapBuilder::BuildViewMap(WingedEdge& we, visibility_algo iAlgo, real epsilon) { +template <typename G, typename I> +static void findOccludee(FEdge *fe, G& grid, I& occluders, real epsilon, WFace** oaWFace, + Vec3r& u, Vec3r& A, Vec3r& origin, Vec3r& edge, vector<WVertex*>& faceVertices) +{ + WFace *face = 0; + if(fe->isSmooth()){ + FEdgeSmooth * fes = dynamic_cast<FEdgeSmooth*>(fe); + face = (WFace*)fes->face(); + } + WFace * oface; + bool skipFace; + + WVertex::incoming_edge_iterator ie; + + *oaWFace = 0; + if(((fe)->getNature() & Nature::SILHOUETTE) || ((fe)->getNature() & Nature::BORDER)) + { + // we cast a ray from A in the same direction but looking behind + Vec3r v(-u[0],-u[1],-u[2]); + bool noIntersection = true; + real mint=FLT_MAX; + + for( occluders.initAfterTarget(); occluders.validAfterTarget(); occluders.nextOccludee() ) + { +#if logging > 0 + cout << "\t\tEvaluating intersection for occludee " << occluders.getWFace() << " and ray " << A << " * " << u << endl; +#endif + oface = occluders.getWFace(); + Polygon3r* p = occluders.getCameraSpacePolygon(); + real d = -((p->getVertices())[0] * p->getNormal()); + real t,t_u,t_v; + + if(0 != face) + { + skipFace = false; + + if(face == oface) + continue; + + if(faceVertices.empty()) + continue; + + for(vector<WVertex*>::iterator fv=faceVertices.begin(), fvend=faceVertices.end(); + fv!=fvend; + ++fv) + { + if((*fv)->isBoundary()) + continue; + WVertex::incoming_edge_iterator iebegin=(*fv)->incoming_edges_begin(); + WVertex::incoming_edge_iterator ieend=(*fv)->incoming_edges_end(); + for(ie=iebegin;ie!=ieend; ++ie) + { + if((*ie) == 0) + continue; + + WFace * sface = (*ie)->GetbFace(); + if(sface == oface) + { + skipFace = true; + break; + } + } + if(skipFace) + break; + } + if(skipFace) + continue; + } + else + { + // check whether the edge and the polygon plane are coincident: + //------------------------------------------------------------- + //first let us compute the plane equation. + if(GeomUtils::COINCIDENT == GeomUtils::intersectRayPlane(origin, edge, p->getNormal(), d, t, epsilon)) { +#if logging > 0 +cout << "\t\tRejecting occluder for target coincidence." << endl; +#endif + continue; + } + } + + if(p->rayIntersect(A, v, t, t_u, t_v)) + { +#if logging > 0 +cout << "\t\tRay " << A << " * " << v << " intersects at time " << t << endl; +#endif +#if logging > 0 +cout << "\t\t(v * normal) == " << (v * p->getNormal()) << " for normal " << p->getNormal() << endl; +#endif + if (fabs(v * p->getNormal()) > 0.0001) + if ((t>0.0)) // && (t<1.0)) + { + if (t<mint) + { + *oaWFace = oface; + mint = t; + noIntersection = false; + fe->setOccludeeIntersection(Vec3r(A+t*v)); +#if logging > 0 +cout << "\t\tIs occludee" << endl; +#endif + } + } + + occluders.reportDepth(A, v, t); + } + + } + + if(noIntersection) + *oaWFace = 0; + } +} + +template <typename G, typename I> +static void findOccludee(FEdge *fe, G& grid, real epsilon, ViewEdge* ve, WFace** oaFace) +{ + Vec3r A; + Vec3r edge; + Vec3r origin; + A = Vec3r(((fe)->vertexA()->point3D() + (fe)->vertexB()->point3D()) / 2.0); + edge = Vec3r((fe)->vertexB()->point3D()-(fe)->vertexA()->point3D()); + origin = Vec3r((fe)->vertexA()->point3D()); + Vec3r u; + if (grid.orthographicProjection()) { + u = Vec3r(0.0, 0.0, grid.viewpoint().z()-A.z()); + } else { + u = Vec3r(grid.viewpoint()-A); + } + u.normalize(); + + vector<WVertex*> faceVertices; + + WFace *face = 0; + if(fe->isSmooth()) { + FEdgeSmooth * fes = dynamic_cast<FEdgeSmooth*>(fe); + face = (WFace*)fes->face(); + } + + if(0 != face) { + face->RetrieveVertexList(faceVertices); + } + + I occluders(grid, A, epsilon); + findOccludee<G, I>(fe, grid, occluders, epsilon, oaFace, u, A, origin, edge, faceVertices); +} + +// computeVisibility takes a pointer to foundOccluders, instead of using a reference, +// so that computeVeryFastVisibility can skip the AddOccluders step with minimal overhead. +template <typename G, typename I> +static int computeVisibility(ViewMap* viewMap, FEdge *fe, G& grid, real epsilon, ViewEdge* ve, WFace** oaWFace, set<ViewShape*>* foundOccluders) +{ + int qi = 0; + + Vec3r center; + Vec3r edge; + Vec3r origin; + + center = fe->center3d(); + edge = Vec3r(fe->vertexB()->point3D() - fe->vertexA()->point3D()); + origin = Vec3r(fe->vertexA()->point3D()); + + Vec3r vp; + if (grid.orthographicProjection()) { + vp = Vec3r(center.x(), center.y(), grid.viewpoint().z()); + } else { + vp = Vec3r(grid.viewpoint()); + } + Vec3r u(vp - center); + real raylength = u.norm(); + u.normalize(); + + WFace *face = 0; + if(fe->isSmooth()){ + FEdgeSmooth * fes = dynamic_cast<FEdgeSmooth*>(fe); + face = (WFace*)fes->face(); + } + vector<WVertex*> faceVertices; + WVertex::incoming_edge_iterator ie; + + WFace * oface; + bool skipFace; + + if(face) + face->RetrieveVertexList(faceVertices); + + I occluders(grid, center, epsilon); + + for(occluders.initBeforeTarget(); occluders.validBeforeTarget(); occluders.nextOccluder()) + { + // If we're dealing with an exact silhouette, check whether + // we must take care of this occluder of not. + // (Indeed, we don't consider the occluders that + // share at least one vertex with the face containing + // this edge). + //----------- + oface = occluders.getWFace(); + Polygon3r* p = occluders.getCameraSpacePolygon(); + real t, t_u, t_v; +#if logging > 0 + cout << "\t\tEvaluating intersection for occluder " << (p->getVertices())[0] << (p->getVertices())[1] << (p->getVertices())[2] << endl << "\t\t\tand ray " << vp << " * " << u << " (center " << center << ")" << endl; +#endif + +#if logging > 0 + Vec3r v(vp - center); + real rl = v.norm(); + v.normalize(); + vector<Vec3r> points; + // Iterate over vertices, storing projections in points + for(vector<WOEdge*>::const_iterator woe=oface->getEdgeList().begin(), woend=oface->getEdgeList().end(); woe!=woend; woe++) { + points.push_back(Vec3r((*woe)->GetaVertex()->GetVertex())); + } + Polygon3r p1(points, oface->GetNormal()); + Vec3r v1((p1.getVertices())[0]); + real d = -(v1 * p->getNormal()); + cout << "\t\tp: " << (p->getVertices())[0] << (p->getVertices())[1] << (p->getVertices())[2] << ", norm: " << p->getNormal() << endl; + cout << "\t\tp1: " << (p1.getVertices())[0] << (p1.getVertices())[1] << (p1.getVertices())[2] << ", norm: " << p1.getNormal() << endl; +#else + real d = -((p->getVertices())[0] * p->getNormal()); +#endif + + if(0 != face) + { +#if logging > 0 +cout << "\t\tDetermining face adjacency..."; +#endif + skipFace = false; + + if(face == oface) { +#if logging > 0 +cout << " Rejecting occluder for face concurrency." << endl; +#endif + continue; + } + + + for(vector<WVertex*>::iterator fv=faceVertices.begin(), fvend=faceVertices.end(); + fv!=fvend; + ++fv) + { + if((*fv)->isBoundary()) + continue; + + WVertex::incoming_edge_iterator iebegin=(*fv)->incoming_edges_begin(); + WVertex::incoming_edge_iterator ieend=(*fv)->incoming_edges_end(); + for(ie=iebegin;ie!=ieend; ++ie) + { + if((*ie) == 0) + continue; + + WFace * sface = (*ie)->GetbFace(); + //WFace * sfacea = (*ie)->GetaFace(); + //if((sface == oface) || (sfacea == oface)) + if(sface == oface) + { + skipFace = true; + break; + } + } + if(skipFace) + break; + } + if(skipFace) { +#if logging > 0 +cout << " Rejecting occluder for face adjacency." << endl; +#endif + continue; + } + } + else + { + // check whether the edge and the polygon plane are coincident: + //------------------------------------------------------------- + //first let us compute the plane equation. + + if(GeomUtils::COINCIDENT == GeomUtils::intersectRayPlane(origin, edge, p->getNormal(), d, t, epsilon)) { +#if logging > 0 +cout << "\t\tRejecting occluder for target coincidence." << endl; +#endif + continue; + } + } + +#if logging > 0 + + real x; + if ( p1.rayIntersect(center, v, x, t_u, t_v) ) { + cout << "\t\tRay should intersect at time " << (rl - x) << ". Center: " << center << ", V: " << v << ", RL: " << rl << ", T:" << x << endl; + } else { + cout << "\t\tRay should not intersect. Center: " << center << ", V: " << v << ", RL: " << rl << endl; + } + +#endif + + if(p->rayIntersect(center, u, t, t_u, t_v)) + { +#if logging > 0 +cout << "\t\tRay " << center << " * " << u << " intersects at time " << t << " (raylength is " << raylength << ")" << endl; +#endif +#if logging > 0 +cout << "\t\t(u * normal) == " << (u * p->getNormal()) << " for normal " << p->getNormal() << endl; +#endif + if (fabs(u * p->getNormal()) > 0.0001) + if ((t>0.0) && (t<raylength)) + { +#if logging > 0 +cout << "\t\tIs occluder" << endl; +#endif + if ( foundOccluders != NULL ) { + ViewShape *vshape = viewMap->viewShape(oface->GetVertex(0)->shape()->GetId()); + foundOccluders->insert(vshape); + } + + ++qi; + + if(! grid.enableQI()) + break; + } + + occluders.reportDepth(center, u, t); + } + } + + // Find occludee + findOccludee<G, I>(fe, grid, occluders, epsilon, oaWFace, u, center, origin, edge, faceVertices); + + return qi; +} + +// computeCumulativeVisibility returns the lowest x such that the majority +// of FEdges have QI <= x +// +// This was probably the original intention of the "normal" algorithm +// on which computeDetailedVisibility is based. But because the "normal" +// algorithm chooses the most popular QI, without considering any other +// values, a ViewEdge with FEdges having QIs of 0, 21, 22, 23, 24 and 25 +// will end up having a total QI of 0, even though most of the FEdges are +// heavily occluded. computeCumulativeVisibility will treat this case as +// a QI of 22 because 3 out of 6 occluders have QI <= 22. + +template <typename G, typename I> +static void computeCumulativeVisibility(ViewMap *ioViewMap, G& grid, real epsilon) +{ + vector<ViewEdge*>& vedges = ioViewMap->ViewEdges(); + + FEdge * fe, *festart; + int nSamples = 0; + vector<WFace*> wFaces; + WFace *wFace = 0; + unsigned tmpQI = 0; + unsigned qiClasses[256]; + unsigned maxIndex, maxCard; + unsigned qiMajority; + for(vector<ViewEdge*>::iterator ve=vedges.begin(), veend=vedges.end(); ve!=veend; ve++) { +#if logging > 0 +cout << "Processing ViewEdge " << (*ve)->getId() << endl; +#endif + // Find an edge to test + if ( ! (*ve)->isInImage() ) { + // This view edge has been proscenium culled + (*ve)->setQI(255); + (*ve)->setaShape(0); +#if logging > 0 +cout << "\tCulled." << endl; +#endif + continue; + } + + // Test edge + festart = (*ve)->fedgeA(); + fe = (*ve)->fedgeA(); + qiMajority = 0; + do { + if ( fe != NULL && fe->isInImage() ) { + qiMajority++; + } + fe = fe->nextEdge(); + } while (fe && fe != festart); + + if ( qiMajority == 0 ) { + // There are no occludable FEdges on this ViewEdge + // This should be impossible. + cout << "View Edge in viewport without occludable FEdges: " << (*ve)->getId() << endl; + // We can recover from this error: + // Treat this edge as fully visible with no occludee + (*ve)->setQI(0); + (*ve)->setaShape(0); + continue; + } else { + ++qiMajority; + qiMajority >>= 1; + } +#if logging > 0 +cout << "\tqiMajority: " << qiMajority << endl; +#endif + + tmpQI = 0; + maxIndex = 0; + maxCard = 0; + nSamples = 0; + memset(qiClasses, 0, 256 * sizeof(*qiClasses)); + set<ViewShape*> foundOccluders; + + fe = (*ve)->fedgeA(); + do + { + if ( fe == NULL || ! fe->isInImage() ) { + fe = fe->nextEdge(); + continue; + } + if((maxCard < qiMajority)) { + tmpQI = computeVisibility<G, I>(ioViewMap, fe, grid, epsilon, *ve, &wFace, &foundOccluders); //ARB: change &wFace to wFace and use reference in called function +#if logging > 0 +cout << "\tFEdge: visibility " << tmpQI << endl; +#endif + + //ARB: This is an error condition, not an alert condition. + // Some sort of recovery or abort is necessary. + if(tmpQI >= 256) { + cerr << "Warning: too many occluding levels" << endl; + //ARB: Wild guess: instead of aborting or corrupting memory, treat as tmpQI == 255 + tmpQI = 255; + } + + if (++qiClasses[tmpQI] > maxCard) { + maxCard = qiClasses[tmpQI]; + maxIndex = tmpQI; + } + } else { + //ARB: FindOccludee is redundant if ComputeRayCastingVisibility has been called + findOccludee<G, I>(fe, grid, epsilon, *ve, &wFace); //ARB: change &wFace to wFace and use reference in called function +#if logging > 0 +cout << "\tFEdge: occludee only (" << (wFace != NULL ? "found" : "not found") << ")" << endl; +#endif + } + + // Store test results + if(wFace) { + vector<Vec3r> vertices; + for ( int i = 0, numEdges = wFace->numberOfEdges(); i < numEdges; ++i ) { + vertices.push_back(Vec3r(wFace->GetVertex(i)->GetVertex())); + } + Polygon3r poly(vertices, wFace->GetNormal()); + poly.userdata = (void *) wFace; + fe->setaFace(poly); + wFaces.push_back(wFace); + fe->setOccludeeEmpty(false); +#if logging > 0 +cout << "\tFound occludee" << endl; +#endif + } else { + fe->setOccludeeEmpty(true); + } + + ++nSamples; + fe = fe->nextEdge(); + } + while((maxCard < qiMajority) && (0!=fe) && (fe!=festart)); +#if logging > 0 +cout << "\tFinished with " << nSamples << " samples, maxCard = " << maxCard << endl; +#endif + + // ViewEdge + // qi -- + // Find the minimum value that is >= the majority of the QI + for ( unsigned count = 0, i = 0; i < 256; ++i ) { + count += qiClasses[i]; + if ( count >= qiMajority ) { + (*ve)->setQI(i); + break; + } + } + // occluders -- + // I would rather not have to go through the effort of creating this + // this set and then copying out its contents. Is there a reason why + // ViewEdge::_Occluders cannot be converted to a set<>? + for(set<ViewShape*>::iterator o=foundOccluders.begin(), oend=foundOccluders.end(); o!=oend; ++o) { + (*ve)->AddOccluder((*o)); + } +#if logging > 0 +cout << "\tConclusion: QI = " << maxIndex << ", " << (*ve)->occluders_size() << " occluders." << endl; +#endif + // occludee -- + if(!wFaces.empty()) + { + if(wFaces.size() <= (float)nSamples/2.f) + { + (*ve)->setaShape(0); + } + else + { + ViewShape *vshape = ioViewMap->viewShape((*wFaces.begin())->GetVertex(0)->shape()->GetId()); + (*ve)->setaShape(vshape); + } + } + + wFaces.clear(); + } +} + +template <typename G, typename I> +static void computeDetailedVisibility(ViewMap *ioViewMap, G& grid, real epsilon) +{ + vector<ViewEdge*>& vedges = ioViewMap->ViewEdges(); + + FEdge * fe, *festart; + int nSamples = 0; + vector<WFace*> wFaces; + WFace *wFace = 0; + unsigned tmpQI = 0; + unsigned qiClasses[256]; + unsigned maxIndex, maxCard; + unsigned qiMajority; + for(vector<ViewEdge*>::iterator ve=vedges.begin(), veend=vedges.end(); ve!=veend; ve++) { +#if logging > 0 +cout << "Processing ViewEdge " << (*ve)->getId() << endl; +#endif + // Find an edge to test + if ( ! (*ve)->isInImage() ) { + // This view edge has been proscenium culled + (*ve)->setQI(255); + (*ve)->setaShape(0); +#if logging > 0 +cout << "\tCulled." << endl; +#endif + continue; + } + + // Test edge + festart = (*ve)->fedgeA(); + fe = (*ve)->fedgeA(); + qiMajority = 0; + do { + if ( fe != NULL && fe->isInImage() ) { + qiMajority++; + } + fe = fe->nextEdge(); + } while (fe && fe != festart); + + if ( qiMajority == 0 ) { + // There are no occludable FEdges on this ViewEdge + // This should be impossible. + cout << "View Edge in viewport without occludable FEdges: " << (*ve)->getId() << endl; + // We can recover from this error: + // Treat this edge as fully visible with no occludee + (*ve)->setQI(0); + (*ve)->setaShape(0); + continue; + } else { + ++qiMajority; + qiMajority >>= 1; + } +#if logging > 0 +cout << "\tqiMajority: " << qiMajority << endl; +#endif + + tmpQI = 0; + maxIndex = 0; + maxCard = 0; + nSamples = 0; + memset(qiClasses, 0, 256 * sizeof(*qiClasses)); + set<ViewShape*> foundOccluders; + + fe = (*ve)->fedgeA(); + do + { + if ( fe == NULL || ! fe->isInImage() ) { + fe = fe->nextEdge(); + continue; + } + if((maxCard < qiMajority)) { + tmpQI = computeVisibility<G, I>(ioViewMap, fe, grid, epsilon, *ve, &wFace, &foundOccluders); //ARB: change &wFace to wFace and use reference in called function +#if logging > 0 +cout << "\tFEdge: visibility " << tmpQI << endl; +#endif + + //ARB: This is an error condition, not an alert condition. + // Some sort of recovery or abort is necessary. + if(tmpQI >= 256) { + cerr << "Warning: too many occluding levels" << endl; + //ARB: Wild guess: instead of aborting or corrupting memory, treat as tmpQI == 255 + tmpQI = 255; + } + + if (++qiClasses[tmpQI] > maxCard) { + maxCard = qiClasses[tmpQI]; + maxIndex = tmpQI; + } + } else { + //ARB: FindOccludee is redundant if ComputeRayCastingVisibility has been called + findOccludee<G, I>(fe, grid, epsilon, *ve, &wFace); //ARB: change &wFace to wFace and use reference in called function +#if logging > 0 +cout << "\tFEdge: occludee only (" << (wFace != NULL ? "found" : "not found") << ")" << endl; +#endif + } + + // Store test results + if(wFace) { + vector<Vec3r> vertices; + for ( int i = 0, numEdges = wFace->numberOfEdges(); i < numEdges; ++i ) { + vertices.push_back(Vec3r(wFace->GetVertex(i)->GetVertex())); + } + Polygon3r poly(vertices, wFace->GetNormal()); + poly.userdata = (void *) wFace; + fe->setaFace(poly); + wFaces.push_back(wFace); + fe->setOccludeeEmpty(false); +#if logging > 0 +cout << "\tFound occludee" << endl; +#endif + } else { + fe->setOccludeeEmpty(true); + } + + ++nSamples; + fe = fe->nextEdge(); + } + while((maxCard < qiMajority) && (0!=fe) && (fe!=festart)); +#if logging > 0 +cout << "\tFinished with " << nSamples << " samples, maxCard = " << maxCard << endl; +#endif + + // ViewEdge + // qi -- + (*ve)->setQI(maxIndex); + // occluders -- + // I would rather not have to go through the effort of creating this + // this set and then copying out its contents. Is there a reason why + // ViewEdge::_Occluders cannot be converted to a set<>? + for(set<ViewShape*>::iterator o=foundOccluders.begin(), oend=foundOccluders.end(); o!=oend; ++o) { + (*ve)->AddOccluder((*o)); + } +#if logging > 0 +cout << "\tConclusion: QI = " << maxIndex << ", " << (*ve)->occluders_size() << " occluders." << endl; +#endif + // occludee -- + if(!wFaces.empty()) + { + if(wFaces.size() <= (float)nSamples/2.f) + { + (*ve)->setaShape(0); + } + else + { + ViewShape *vshape = ioViewMap->viewShape((*wFaces.begin())->GetVertex(0)->shape()->GetId()); + (*ve)->setaShape(vshape); + } + } + + wFaces.clear(); + } +} + +template <typename G, typename I> +static void computeFastVisibility(ViewMap *ioViewMap, G& grid, real epsilon) +{ + vector<ViewEdge*>& vedges = ioViewMap->ViewEdges(); + + FEdge * fe, *festart; + unsigned nSamples = 0; + vector<WFace*> wFaces; + WFace *wFace = 0; + unsigned tmpQI = 0; + unsigned qiClasses[256]; + unsigned maxIndex, maxCard; + unsigned qiMajority; + bool even_test; + for(vector<ViewEdge*>::iterator ve=vedges.begin(), veend=vedges.end(); ve!=veend; ve++) { + // Find an edge to test + if ( ! (*ve)->isInImage() ) { + // This view edge has been proscenium culled + (*ve)->setQI(255); + (*ve)->setaShape(0); + continue; + } + + // Test edge + festart = (*ve)->fedgeA(); + fe = (*ve)->fedgeA(); + + even_test = true; + qiMajority = 0; + do { + if ( even_test && fe != NULL && fe->isInImage() ) { + qiMajority++; + even_test = ! even_test; + } + fe = fe->nextEdge(); + } while (fe && fe != festart); + + if (qiMajority == 0 ) { + // There are no occludable FEdges on this ViewEdge + // This should be impossible. + cout << "View Edge in viewport without occludable FEdges: " << (*ve)->getId() << endl; + // We can recover from this error: + // Treat this edge as fully visible with no occludee + (*ve)->setQI(0); + (*ve)->setaShape(0); + continue; + } else { + ++qiMajority; + qiMajority >>= 1; + } + + even_test = true; + maxIndex = 0; + maxCard = 0; + nSamples = 0; + memset(qiClasses, 0, 256 * sizeof(*qiClasses)); + set<ViewShape*> foundOccluders; + + fe = (*ve)->fedgeA(); + do + { + if ( fe == NULL || ! fe->isInImage() ) { + fe = fe->nextEdge(); + continue; + } + if (even_test) + { + if((maxCard < qiMajority)) { + tmpQI = computeVisibility<G, I>(ioViewMap, fe, grid, epsilon, *ve, &wFace, &foundOccluders); //ARB: change &wFace to wFace and use reference in called function + + //ARB: This is an error condition, not an alert condition. + // Some sort of recovery or abort is necessary. + if(tmpQI >= 256) { + cerr << "Warning: too many occluding levels" << endl; + //ARB: Wild guess: instead of aborting or corrupting memory, treat as tmpQI == 255 + tmpQI = 255; + } + + if (++qiClasses[tmpQI] > maxCard) { + maxCard = qiClasses[tmpQI]; + maxIndex = tmpQI; + } + } else { + //ARB: FindOccludee is redundant if ComputeRayCastingVisibility has been called + findOccludee<G, I>(fe, grid, epsilon, *ve, &wFace); //ARB: change &wFace to wFace and use reference in called function + } + + if(wFace) + { + vector<Vec3r> vertices; + for ( int i = 0, numEdges = wFace->numberOfEdges(); i < numEdges; ++i ) { + vertices.push_back(Vec3r(wFace->GetVertex(i)->GetVertex())); + } + Polygon3r poly(vertices, wFace->GetNormal()); + poly.userdata = (void *) wFace; + fe->setaFace(poly); + wFaces.push_back(wFace); + } + ++nSamples; + } + + even_test = ! even_test; + fe = fe->nextEdge(); + } while ((maxCard < qiMajority) && (0!=fe) && (fe!=festart)); + + // qi -- + (*ve)->setQI(maxIndex); + + // occluders -- + for(set<ViewShape*>::iterator o=foundOccluders.begin(), oend=foundOccluders.end(); o!=oend; ++o) { + (*ve)->AddOccluder((*o)); + } + + // occludee -- + if(!wFaces.empty()) + { + if(wFaces.size() < nSamples / 2) + { + (*ve)->setaShape(0); + } + else + { + ViewShape *vshape = ioViewMap->viewShape((*wFaces.begin())->GetVertex(0)->shape()->GetId()); + (*ve)->setaShape(vshape); + } + } + + wFaces.clear(); + } +} + +template <typename G, typename I> +static void computeVeryFastVisibility(ViewMap *ioViewMap, G& grid, real epsilon) +{ + vector<ViewEdge*>& vedges = ioViewMap->ViewEdges(); + + FEdge* fe; + unsigned qi = 0; + WFace* wFace = 0; + + for(vector<ViewEdge*>::iterator ve=vedges.begin(), veend=vedges.end(); ve!=veend; ve++) + { + // Find an edge to test + if ( ! (*ve)->isInImage() ) { + // This view edge has been proscenium culled + (*ve)->setQI(255); + (*ve)->setaShape(0); + continue; + } + fe = (*ve)->fedgeA(); + // Find a FEdge inside the occluder proscenium to test for visibility + FEdge* festart = fe; + while ( fe != NULL && ! fe->isInImage() ) { + fe = fe->nextEdge(); + if ( fe == festart ) { + break; + } + } + + // Test edge + if ( fe == NULL || ! fe->isInImage() ) { + // There are no occludable FEdges on this ViewEdge + // This should be impossible. + cout << "View Edge in viewport without occludable FEdges: " << (*ve)->getId() << endl; + // We can recover from this error: + // Treat this edge as fully visible with no occludee + qi = 0; + wFace = NULL; + } else { + qi = computeVisibility<G, I>(ioViewMap, fe, grid, epsilon, *ve, &wFace, NULL); + } + + // Store test results + if(wFace) + { + vector<Vec3r> vertices; + for ( int i = 0, numEdges = wFace->numberOfEdges(); i < numEdges; ++i ) { + vertices.push_back(Vec3r(wFace->GetVertex(i)->GetVertex())); + } + Polygon3r poly(vertices, wFace->GetNormal()); + poly.userdata = (void *) wFace; + fe->setaFace(poly); // This works because setaFace *copies* the polygon + ViewShape *vshape = ioViewMap->viewShape(wFace->GetVertex(0)->shape()->GetId()); + (*ve)->setaShape(vshape); + } + else + { + (*ve)->setaShape(0); + } + (*ve)->setQI(qi); + } + +} + +void ViewMapBuilder::BuildGrid(WingedEdge& we, const BBox<Vec3r>& bbox, unsigned int sceneNumFaces) { + _Grid->clear(); + Vec3r size; + for(unsigned int i=0; i<3; i++) + { + size[i] = fabs(bbox.getMax()[i] - bbox.getMin()[i]); + size[i] += size[i]/10.0; // let make the grid 1/10 bigger to avoid numerical errors while computing triangles/cells intersections + if(size[i]==0){ + cout << "Warning: the bbox size is 0 in dimension "<<i<<endl; + } + } + _Grid->configure(Vec3r(bbox.getMin() - size / 20.0), size, sceneNumFaces); + + // Fill in the grid: + WFillGrid fillGridRenderer(_Grid, &we); + fillGridRenderer.fillGrid(); + + // DEBUG + _Grid->displayDebug(); +} + +ViewMap* ViewMapBuilder::BuildViewMap(WingedEdge& we, visibility_algo iAlgo, real epsilon, + const BBox<Vec3r>& bbox, unsigned int sceneNumFaces) { _ViewMap = new ViewMap; _currentId = 1; _currentFId = 0; _currentSVertexId = 0; - + // Builds initial view edges computeInitialViewEdges(we); @@ -40,11 +922,191 @@ ViewMap* ViewMapBuilder::BuildViewMap(WingedEdge& we, visibility_algo iAlgo, rea ComputeIntersections(_ViewMap, sweep_line, epsilon); // Compute visibility - ComputeEdgesVisibility(_ViewMap, iAlgo, _Grid, epsilon); - + ComputeEdgesVisibility(_ViewMap, we, bbox, sceneNumFaces, iAlgo, epsilon); + return _ViewMap; } +static inline real distance2D(const Vec3r & point, const real origin[2]) { + return ::hypot((point[0] - origin[0]), (point[1] - origin[1])); +} + +static inline bool crossesProscenium(real proscenium[4], FEdge *fe) { + Vec2r min(proscenium[0], proscenium[2]); + Vec2r max(proscenium[1], proscenium[3]); + Vec2r A(fe->vertexA()->getProjectedX(), fe->vertexA()->getProjectedY()); + Vec2r B(fe->vertexB()->getProjectedX(), fe->vertexB()->getProjectedY()); + + return GeomUtils::intersect2dSeg2dArea (min, max, A, B); +} + +static inline bool insideProscenium(real proscenium[4], const Vec3r& point) { + return ! ( point[0] < proscenium[0] || point[0] > proscenium[1] || point[1] < proscenium[2] || point[1] > proscenium[3] ); +} + +void ViewMapBuilder::CullViewEdges(ViewMap *ioViewMap, real viewProscenium[4], real occluderProscenium[4], bool extensiveFEdgeSearch) { + // Cull view edges by marking them as non-displayable. + // This avoids the complications of trying to delete + // edges from the ViewMap. + + // Non-displayable view edges will be skipped over during + // visibility calculation. + + // View edges will be culled according to their position + // w.r.t. the viewport proscenium (viewport + 5% border, + // or some such). + + // Get proscenium boundary for culling + GridHelpers::getDefaultViewProscenium(viewProscenium); + real prosceniumOrigin[2]; + prosceniumOrigin[0] = (viewProscenium[1] - viewProscenium[0]) / 2.0; + prosceniumOrigin[1] = (viewProscenium[3] - viewProscenium[2]) / 2.0; + cout << "Proscenium culling:" << endl; + cout << "Proscenium: [" << viewProscenium[0] << ", " << viewProscenium[1] << ", " << viewProscenium[2] << ", " << viewProscenium[3] << "]"<< endl; + cout << "Origin: [" << prosceniumOrigin[0] << ", " << prosceniumOrigin[1] << "]"<< endl; + + // A separate occluder proscenium will also be maintained, + // starting out the same as the viewport proscenium, and + // expanding as necessary so that it encompasses the center + // point of at least one feature edge in each retained view + // edge. + // The occluder proscenium will be used later to cull occluding + // triangles before they are inserted into the Grid. + // The occluder proscenium starts out the same size as the view + // proscenium + GridHelpers::getDefaultViewProscenium(occluderProscenium); + + // N.B. Freestyle is inconsistent in its use of ViewMap::viewedges_container + // and vector<ViewEdge*>::iterator. Probably all occurences of vector<ViewEdge*>::iterator + // should be replaced ViewMap::viewedges_container throughout the code. + // For each view edge + ViewMap::viewedges_container::iterator ve, veend; + + for(ve=ioViewMap->ViewEdges().begin(), veend=ioViewMap->ViewEdges().end(); ve!=veend; ve++) { + // Overview: + // Search for a visible feature edge + // If none: mark view edge as non-displayable + // Otherwise: + // Find a feature edge with center point inside occluder proscenium. + // If none exists, find the feature edge with center point + // closest to viewport origin. + // Expand occluder proscenium to enclose center point. + + // For each feature edge, while bestOccluderTarget not found and view edge not visibile + bool bestOccluderTargetFound = false; + FEdge *bestOccluderTarget = NULL; + real bestOccluderDistance = 0.0; + FEdge *festart = (*ve)->fedgeA(); + FEdge *fe = festart; + // All ViewEdges start culled + (*ve)->setIsInImage(false); + + // For simple visibility calculation: mark a feature edge + // that is known to have a center point inside the occluder proscenium. + // Cull all other feature edges. + do { + // All FEdges start culled + fe->setIsInImage(false); + + // Look for the visible edge that can most easily be included + // in the occluder proscenium. + if ( ! bestOccluderTargetFound ) { + // If center point is inside occluder proscenium, + if ( insideProscenium(occluderProscenium, fe->center2d()) ) { + // Use this feature edge for visibility deterimination + fe->setIsInImage(true); + // Mark bestOccluderTarget as found + bestOccluderTargetFound = true; + bestOccluderTarget = fe; + } else { + real d = distance2D(fe->center2d(), prosceniumOrigin); + // If center point is closer to viewport origin than current target + if ( bestOccluderTarget == NULL || d < bestOccluderDistance ) { + // Then store as bestOccluderTarget + bestOccluderDistance = d; + bestOccluderTarget = fe; + } + } + } + + // If feature edge crosses the view proscenium + if ( ! (*ve)->isInImage() && crossesProscenium(viewProscenium, fe) ) { + // Then the view edge will be included in the image + (*ve)->setIsInImage(true); + } + fe = fe->nextEdge(); + } while ( fe != NULL && fe != festart && ! ( bestOccluderTargetFound && (*ve)->isInImage() ) ); + + // Either we have run out of FEdges, or we already have the one edge we need to determine visibility + // Cull all remaining edges. + while ( fe != NULL && fe != festart ) { + fe->setIsInImage(false); + fe = fe->nextEdge(); + } + + // If bestOccluderTarget was not found inside the occluder proscenium, + // we need to expand the occluder proscenium to include it. + if ( (*ve)->isInImage() && bestOccluderTarget != NULL && ! bestOccluderTargetFound ) { + // Expand occluder proscenium to enclose bestOccluderTarget + Vec3r point = bestOccluderTarget->center2d(); + if ( point[0] < occluderProscenium[0] ) { + occluderProscenium[0] = point[0]; + } else if ( point[0] > occluderProscenium[1] ) { + occluderProscenium[1] = point[0]; + } + if ( point[1] < occluderProscenium[2] ) { + occluderProscenium[2] = point[1]; + } else if ( point[1] > occluderProscenium[3] ) { + occluderProscenium[3] = point[1]; + } + // Use bestOccluderTarget for visibility determination + bestOccluderTarget->setIsInImage(true); + } + } + + // We are done calculating the occluder proscenium. + // Expand the occluder proscenium by an epsilon to avoid rounding errors. + const real epsilon = 1.0e-6; + occluderProscenium[0] -= epsilon; + occluderProscenium[1] += epsilon; + occluderProscenium[2] -= epsilon; + occluderProscenium[3] += epsilon; + + // For "Normal" or "Fast" style visibility computation only: + + // For more detailed visibility calculation, make a second pass through + // the view map, marking all feature edges with center points inside + // the final occluder proscenium. All of these feature edges can be + // considered during visibility calculation. + + // So far we have only found one FEdge per ViewEdge. The "Normal" and + // "Fast" styles of visibility computation want to consider many + // FEdges for each ViewEdge. + // Here we re-scan the view map to find any usable FEdges that we + // skipped on the first pass, or that have become usable because the + // occluder proscenium has been expanded since the edge was visited + // on the first pass. + if ( extensiveFEdgeSearch ) { + // For each view edge, + for(ve=ioViewMap->ViewEdges().begin(), veend=ioViewMap->ViewEdges().end(); ve!=veend; ve++) { + if ( ! (*ve)->isInImage() ) { + continue; + } + // For each feature edge, + FEdge *festart = (*ve)->fedgeA(); + FEdge *fe = festart; + do { + // If not (already) visible and center point inside occluder proscenium, + if ( ! fe->isInImage() && insideProscenium(occluderProscenium, fe->center2d()) ) { + // Use the feature edge for visibility determination + fe->setIsInImage(true); + } + fe = fe->nextEdge(); + } while ( fe != NULL && fe != festart ); + } + } +} + void ViewMapBuilder::computeInitialViewEdges(WingedEdge& we) { vector<WShape*> wshapes = we.getWShapes(); @@ -151,26 +1213,130 @@ void ViewMapBuilder::computeCusps(ViewMap *ioViewMap){ vedges.push_back(*ve); } } -void ViewMapBuilder::ComputeEdgesVisibility(ViewMap *ioViewMap, visibility_algo iAlgo, Grid *iGrid, real epsilon) + +void ViewMapBuilder::ComputeCumulativeVisibility(ViewMap *ioViewMap, + WingedEdge& we, const BBox<Vec3r>& bbox, real epsilon, bool cull, GridDensityProviderFactory& factory) { - if((iAlgo == ray_casting || - iAlgo == ray_casting_fast || - iAlgo == ray_casting_very_fast) && (NULL == iGrid)) - { - cerr << "Error: can't cast ray, no grid defined" << endl; - return; - } + auto_ptr<GridHelpers::Transform> transform; + auto_ptr<OccluderSource> source; + if ( _orthographicProjection ) { + transform.reset(new BoxGrid::Transform); + } else { + transform.reset(new SphericalGrid::Transform); + } + + if ( cull ) { + source.reset(new CulledOccluderSource(*transform, we, *ioViewMap, true)); + } else { + source.reset(new OccluderSource(*transform, we)); + } + + auto_ptr<GridDensityProvider> density(factory.newGridDensityProvider(*source, bbox, *transform)); + + if ( _orthographicProjection ) { + BoxGrid grid(*source, *density, ioViewMap, _viewpoint, _EnableQI); + computeCumulativeVisibility<BoxGrid, BoxGrid::Iterator>(ioViewMap, grid, epsilon); + } else { + SphericalGrid grid(*source, *density, ioViewMap, _viewpoint, _EnableQI); + computeCumulativeVisibility<SphericalGrid, SphericalGrid::Iterator>(ioViewMap, grid, epsilon); + } +} + +void ViewMapBuilder::ComputeDetailedVisibility(ViewMap *ioViewMap, + WingedEdge& we, const BBox<Vec3r>& bbox, real epsilon, bool cull, GridDensityProviderFactory& factory) +{ + auto_ptr<GridHelpers::Transform> transform; + auto_ptr<OccluderSource> source; + + if ( _orthographicProjection ) { + transform.reset(new BoxGrid::Transform); + } else { + transform.reset(new SphericalGrid::Transform); + } + + if ( cull ) { + source.reset(new CulledOccluderSource(*transform, we, *ioViewMap, true)); + } else { + source.reset(new OccluderSource(*transform, we)); + } + + auto_ptr<GridDensityProvider> density(factory.newGridDensityProvider(*source, bbox, *transform)); + + if ( _orthographicProjection ) { + BoxGrid grid(*source, *density, ioViewMap, _viewpoint, _EnableQI); + computeDetailedVisibility<BoxGrid, BoxGrid::Iterator>(ioViewMap, grid, epsilon); + } else { + SphericalGrid grid(*source, *density, ioViewMap, _viewpoint, _EnableQI); + computeDetailedVisibility<SphericalGrid, SphericalGrid::Iterator>(ioViewMap, grid, epsilon); + } +} + +void ViewMapBuilder::ComputeEdgesVisibility(ViewMap *ioViewMap, + WingedEdge& we, const BBox<Vec3r>& bbox, unsigned int sceneNumFaces, visibility_algo iAlgo, real epsilon) +{ switch(iAlgo) { case ray_casting: - ComputeRayCastingVisibility(ioViewMap, iGrid, epsilon); + cout << "Using ordinary ray casting" << endl; + BuildGrid(we, bbox, sceneNumFaces); + ComputeRayCastingVisibility(ioViewMap, epsilon); break; case ray_casting_fast: - ComputeFastRayCastingVisibility(ioViewMap, iGrid, epsilon); + cout << "Using fast ray casting" << endl; + BuildGrid(we, bbox, sceneNumFaces); + ComputeFastRayCastingVisibility(ioViewMap, epsilon); break; case ray_casting_very_fast: - ComputeVeryFastRayCastingVisibility(ioViewMap, iGrid, epsilon); + cout << "Using very fast ray casting" << endl; + BuildGrid(we, bbox, sceneNumFaces); + ComputeVeryFastRayCastingVisibility(ioViewMap, epsilon); + break; + case ray_casting_culled_adaptive_traditional: + cout << "Using culled adaptive grid with heuristic density and traditional QI calculation" << endl; + try { + HeuristicGridDensityProviderFactory factory(0.5f, sceneNumFaces); + ComputeDetailedVisibility(ioViewMap, we, bbox, epsilon, true, factory); + } catch (...) { + // Last resort catch to make sure RAII semantics hold for OptimizedGrid + // Can be replaced with try...catch block around main() if the program + // as a whole is converted to RAII + + // This is the little-mentioned caveat of RAII: RAII does not work unless + // destructors are always called, but destructors are only called if all + // exceptions are caught (or std::terminate() is replaced). + + // We don't actually handle the exception here, so re-throw it + // now that our destructors have had a chance to run. + throw; + } + break; + case ray_casting_adaptive_traditional: + cout << "Using unculled adaptive grid with heuristic density and traditional QI calculation" << endl; + try { + HeuristicGridDensityProviderFactory factory(0.5f, sceneNumFaces); + ComputeDetailedVisibility(ioViewMap, we, bbox, epsilon, false, factory); + } catch (...) { + throw; + } + break; + case ray_casting_culled_adaptive_cumulative: + cout << "Using culled adaptive grid with heuristic density and cumulative QI calculation" << endl; + try { + HeuristicGridDensityProviderFactory factory(0.5f, sceneNumFaces); + ComputeCumulativeVisibility(ioViewMap, we, bbox, epsilon, true, factory); + } catch (...) { + throw; + } + break; + case ray_casting_adaptive_cumulative: + cout << "Using unculled adaptive grid with heuristic density and cumulative QI calculation" << endl; + try { + HeuristicGridDensityProviderFactory factory(0.5f, sceneNumFaces); + ComputeCumulativeVisibility(ioViewMap, we, bbox, epsilon, false, factory); + } catch (...) { + throw; + } break; default: break; @@ -180,7 +1346,7 @@ void ViewMapBuilder::ComputeEdgesVisibility(ViewMap *ioViewMap, visibility_algo static const unsigned gProgressBarMaxSteps = 10; static const unsigned gProgressBarMinSize = 2000; -void ViewMapBuilder::ComputeRayCastingVisibility(ViewMap *ioViewMap, Grid* iGrid, real epsilon) +void ViewMapBuilder::ComputeRayCastingVisibility(ViewMap *ioViewMap, real epsilon) { vector<ViewEdge*>& vedges = ioViewMap->ViewEdges(); bool progressBarDisplay = false; @@ -212,6 +1378,9 @@ void ViewMapBuilder::ComputeRayCastingVisibility(ViewMap *ioViewMap, Grid* iGrid ve!=veend; ve++) { +#if logging > 0 +cout << "Processing ViewEdge " << (*ve)->getId() << endl; +#endif festart = (*ve)->fedgeA(); fe = (*ve)->fedgeA(); qiMajority = 1; @@ -220,6 +1389,9 @@ void ViewMapBuilder::ComputeRayCastingVisibility(ViewMap *ioViewMap, Grid* iGrid fe = fe->nextEdge(); } while (fe && fe != festart); qiMajority >>= 1; +#if logging > 0 +cout << "\tqiMajority: " << qiMajority << endl; +#endif tmpQI = 0; maxIndex = 0; @@ -231,30 +1403,55 @@ void ViewMapBuilder::ComputeRayCastingVisibility(ViewMap *ioViewMap, Grid* iGrid do { if((maxCard < qiMajority)) { - tmpQI = ComputeRayCastingVisibility(fe, iGrid, epsilon, occluders, &aFace, timestamp++); + tmpQI = ComputeRayCastingVisibility(fe, _Grid, epsilon, occluders, &aFace, timestamp++); - if(tmpQI >= 256) +#if logging > 0 +cout << "\tFEdge: visibility " << tmpQI << endl; +#endif + //ARB: This is an error condition, not an alert condition. + // Some sort of recovery or abort is necessary. + if(tmpQI >= 256) { cerr << "Warning: too many occluding levels" << endl; + //ARB: Wild guess: instead of aborting or corrupting memory, treat as tmpQI == 255 + tmpQI = 255; + } if (++qiClasses[tmpQI] > maxCard) { maxCard = qiClasses[tmpQI]; maxIndex = tmpQI; } + } else { + //ARB: FindOccludee is redundant if ComputeRayCastingVisibility has been called + FindOccludee(fe, _Grid, epsilon, &aFace, timestamp++); +#if logging > 0 +cout << "\tFEdge: occludee only (" << (aFace != NULL ? "found" : "not found") << ")" << endl; +#endif } - FindOccludee(fe, iGrid, epsilon, &aFace, timestamp++); if(aFace) { fe->setaFace(*aFace); aFaces.push_back(aFace); fe->setOccludeeEmpty(false); +#if logging > 0 +cout << "\tFound occludee" << endl; +#endif } else + { + //ARB: We are arbitrarily using the last observed value for occludee + // (almost always the value observed for the edge before festart). + // Is that meaningful? + // ...in fact, _occludeeEmpty seems to be unused. fe->setOccludeeEmpty(true); + } ++nSamples; fe = fe->nextEdge(); } while((maxCard < qiMajority) && (0!=fe) && (fe!=festart)); +#if logging > 0 +cout << "\tFinished with " << nSamples << " samples, maxCard = " << maxCard << endl; +#endif // ViewEdge // qi -- @@ -264,6 +1461,9 @@ void ViewMapBuilder::ComputeRayCastingVisibility(ViewMap *ioViewMap, Grid* iGrid o!=oend; ++o) (*ve)->AddOccluder((*o)); +#if logging > 0 +cout << "\tConclusion: QI = " << maxIndex << ", " << (*ve)->occluders_size() << " occluders." << endl; +#endif // occludee -- if(!aFaces.empty()) { @@ -292,7 +1492,7 @@ void ViewMapBuilder::ComputeRayCastingVisibility(ViewMap *ioViewMap, Grid* iGrid } } -void ViewMapBuilder::ComputeFastRayCastingVisibility(ViewMap *ioViewMap, Grid* iGrid, real epsilon) +void ViewMapBuilder::ComputeFastRayCastingVisibility(ViewMap *ioViewMap, real epsilon) { vector<ViewEdge*>& vedges = ioViewMap->ViewEdges(); bool progressBarDisplay = false; @@ -350,17 +1550,24 @@ void ViewMapBuilder::ComputeFastRayCastingVisibility(ViewMap *ioViewMap, Grid* i if (even_test) { if((maxCard < qiMajority)) { - tmpQI = ComputeRayCastingVisibility(fe, iGrid, epsilon, occluders, &aFace, timestamp++); + tmpQI = ComputeRayCastingVisibility(fe, _Grid, epsilon, occluders, &aFace, timestamp++); - if(tmpQI >= 256) - cerr << "Warning: too many occluding levels" << endl; + //ARB: This is an error condition, not an alert condition. + // Some sort of recovery or abort is necessary. + if(tmpQI >= 256) { + cerr << "Warning: too many occluding levels" << endl; + //ARB: Wild guess: instead of aborting or corrupting memory, treat as tmpQI == 255 + tmpQI = 255; + } if (++qiClasses[tmpQI] > maxCard) { maxCard = qiClasses[tmpQI]; maxIndex = tmpQI; } - } - FindOccludee(fe, iGrid, epsilon, &aFace, timestamp++); + } else { + //ARB: FindOccludee is redundant if ComputeRayCastingVisibility has been called + FindOccludee(fe, _Grid, epsilon, &aFace, timestamp++); + } if(aFace) { @@ -419,7 +1626,7 @@ void ViewMapBuilder::ComputeFastRayCastingVisibility(ViewMap *ioViewMap, Grid* i } } -void ViewMapBuilder::ComputeVeryFastRayCastingVisibility(ViewMap *ioViewMap, Grid* iGrid, real epsilon) +void ViewMapBuilder::ComputeVeryFastRayCastingVisibility(ViewMap *ioViewMap, real epsilon) { vector<ViewEdge*>& vedges = ioViewMap->ViewEdges(); bool progressBarDisplay = false; @@ -449,7 +1656,7 @@ void ViewMapBuilder::ComputeVeryFastRayCastingVisibility(ViewMap *ioViewMap, Gri set<ViewShape*> occluders; fe = (*ve)->fedgeA(); - qi = ComputeRayCastingVisibility(fe, iGrid, epsilon, occluders, &aFace, timestamp++); + qi = ComputeRayCastingVisibility(fe, _Grid, epsilon, occluders, &aFace, timestamp++); if(aFace) { fe->setaFace(*aFace); @@ -474,7 +1681,6 @@ void ViewMapBuilder::ComputeVeryFastRayCastingVisibility(ViewMap *ioViewMap, Gri } } - void ViewMapBuilder::FindOccludee(FEdge *fe, Grid* iGrid, real epsilon, Polygon3r** oaPolygon, unsigned timestamp, Vec3r& u, Vec3r& A, Vec3r& origin, Vec3r& edge, vector<WVertex*>& faceVertices) { @@ -685,17 +1891,31 @@ int ViewMapBuilder::ComputeRayCastingVisibility(FEdge *fe, Grid* iGrid, real eps // this edge). //----------- oface = (WFace*)(*p)->userdata; +#if logging > 1 +cout << "\t\tEvaluating intersection for occluder " << ((*p)->getVertices())[0] << ((*p)->getVertices())[1] << ((*p)->getVertices())[2] << endl << "\t\t\tand ray " << vp << " * " << u << " (center " << center << ")" << endl; +#endif Vec3r v1(((*p)->getVertices())[0]); Vec3r normal((*p)->getNormal()); real d = -(v1 * normal); real t, t_u, t_v; +#if logging > 1 +cout << "\t\tp: " << ((*p)->getVertices())[0] << ((*p)->getVertices())[1] << ((*p)->getVertices())[2] << ", norm: " << (*p)->getNormal() << endl; +#endif + if(0 != face) { +#if logging > 1 +cout << "\t\tDetermining face adjacency..."; +#endif skipFace = false; - if(face == oface) + if(face == oface) { +#if logging > 1 +cout << " Rejecting occluder for face concurrency." << endl; +#endif continue; + } for(vector<WVertex*>::iterator fv=faceVertices.begin(), fvend=faceVertices.end(); @@ -724,8 +1944,12 @@ int ViewMapBuilder::ComputeRayCastingVisibility(FEdge *fe, Grid* iGrid, real eps if(skipFace) break; } - if(skipFace) + if(skipFace) { +#if logging > 1 +cout << " Rejecting occluder for face adjacency." << endl; +#endif continue; + } } else { @@ -733,15 +1957,28 @@ int ViewMapBuilder::ComputeRayCastingVisibility(FEdge *fe, Grid* iGrid, real eps //------------------------------------------------------------- //first let us compute the plane equation. - if(GeomUtils::COINCIDENT == GeomUtils::intersectRayPlane(origin, edge, normal, d, t, epsilon)) + if(GeomUtils::COINCIDENT == GeomUtils::intersectRayPlane(origin, edge, normal, d, t, epsilon)) { +#if logging > 1 +cout << "\t\tRejecting occluder for target coincidence." << endl; +#endif continue; + } } if((*p)->rayIntersect(center, u, t, t_u, t_v)) { +#if logging > 1 +cout << "\t\tRay " << vp << " * " << u << " intersects at time " << t << " (raylength is " << raylength << ")" << endl; +#endif +#if logging > 1 +cout << "\t\t(u * normal) == " << (u * normal) << " for normal " << normal << endl; +#endif if (fabs(u * normal) > 0.0001) if ((t>0.0) && (t<raylength)) { +#if logging > 1 +cout << "\t\tIs occluder" << endl; +#endif WFace *f = (WFace*)((*p)->userdata); ViewShape *vshape = _ViewMap->viewShape(f->GetVertex(0)->shape()->GetId()); oOccluders.insert(vshape); @@ -1051,13 +2288,13 @@ void ViewMapBuilder::ComputeSweepLineIntersections(ViewMap *ioViewMap, real epsi fe++) (*fe)->userdata = NULL; - // delete segments - // if(!segments.empty()){ - // for(s=segments.begin(),send=segments.end(); - // s!=send; - // s++){ - // delete *s; - // } - // segments.clear(); - // } + // delete segments + if(!segments.empty()){ + for(s=segments.begin(),send=segments.end(); + s!=send; + s++){ + delete *s; + } + } } + diff --git a/source/blender/freestyle/intern/view_map/ViewMapBuilder.h b/source/blender/freestyle/intern/view_map/ViewMapBuilder.h index 12b1266fa12..2e37a41df3c 100755 --- a/source/blender/freestyle/intern/view_map/ViewMapBuilder.h +++ b/source/blender/freestyle/intern/view_map/ViewMapBuilder.h @@ -46,7 +46,8 @@ # include "../scene_graph/TriangleRep.h" # include "../winged_edge/WEdge.h" # include "ViewEdgeXBuilder.h" - +# include "../system/TimeUtils.h" +# include "GridDensityProvider.h" using namespace Geometry; @@ -64,6 +65,7 @@ private: bool _EnableQI; double _epsilon; + // tmp values: int _currentId; int _currentFId; @@ -79,7 +81,11 @@ public: typedef enum { ray_casting, ray_casting_fast, - ray_casting_very_fast + ray_casting_very_fast, + ray_casting_culled_adaptive_traditional, + ray_casting_adaptive_traditional, + ray_casting_culled_adaptive_cumulative, + ray_casting_adaptive_cumulative } visibility_algo; inline ViewMapBuilder() @@ -101,6 +107,10 @@ public: } } + /* Build Grid for ray casting */ + /*! Build non-culled Grid in camera space for ray casting */ + void BuildGrid(WingedEdge& we, const BBox<Vec3r>& bbox, unsigned int sceneNumFaces); + /*! Compute Shapes from a WingedEdge containing a list of WShapes */ void computeInitialViewEdges(WingedEdge&); @@ -145,7 +155,9 @@ public: * The root group node containing the WEdge structured scene */ - ViewMap* BuildViewMap(WingedEdge& we, visibility_algo iAlgo = ray_casting, real epsilon=1e-06) ; + ViewMap* BuildViewMap(WingedEdge& we, visibility_algo iAlgo, real epsilon, + const BBox<Vec3r>& bbox, unsigned int sceneNumFaces); + void CullViewEdges(ViewMap *ioViewMap, real viewProscenium[4], real occluderProscenium[4], bool extensiveFEdgeSearch = true); /*! computes the intersection between all 2D * feature edges of the scene. * ioViewMap @@ -164,7 +176,8 @@ public: * iGrid * For the Ray Casting algorithm. */ - void ComputeEdgesVisibility(ViewMap *ioViewMap, visibility_algo iAlgo= ray_casting, Grid* iGrid = 0, real epsilon=1e-6); + void ComputeEdgesVisibility(ViewMap *ioViewMap, WingedEdge& we, const BBox<Vec3r>& bbox, unsigned int sceneNumFaces, + visibility_algo iAlgo= ray_casting, real epsilon=1e-6); void setGrid(Grid *iGrid) {_Grid = iGrid;} @@ -192,9 +205,14 @@ protected: * The visibility corresponding to each edge of ioScene is set is this * edge. */ - void ComputeRayCastingVisibility(ViewMap *ioViewMap, Grid *iGrid, real epsilon=1e-6); - void ComputeFastRayCastingVisibility(ViewMap *ioViewMap, Grid *iGrid, real epsilon=1e-6); - void ComputeVeryFastRayCastingVisibility(ViewMap *ioViewMap, Grid *iGrid, real epsilon=1e-6); + void ComputeRayCastingVisibility(ViewMap *ioViewMap, real epsilon=1e-6); + void ComputeFastRayCastingVisibility(ViewMap *ioViewMap, real epsilon=1e-6); + void ComputeVeryFastRayCastingVisibility(ViewMap *ioViewMap, real epsilon=1e-6); + +void ComputeCumulativeVisibility(ViewMap *ioViewMap, WingedEdge& we, + const BBox<Vec3r>& bbox, real epsilon, bool cull, GridDensityProviderFactory& factory); +void ComputeDetailedVisibility(ViewMap *ioViewMap, WingedEdge& we, + const BBox<Vec3r>& bbox, real epsilon, bool cull, GridDensityProviderFactory& factory); /*! Compute the visibility for the FEdge fe. * The occluders are added to fe occluders list. diff --git a/source/blender/freestyle/intern/winged_edge/Curvature.cpp b/source/blender/freestyle/intern/winged_edge/Curvature.cpp index 2997d9b6922..f8854b11d7b 100755 --- a/source/blender/freestyle/intern/winged_edge/Curvature.cpp +++ b/source/blender/freestyle/intern/winged_edge/Curvature.cpp @@ -20,6 +20,7 @@ #include <cstdlib> // for malloc and free #include "Curvature.h" #include <math.h> +#include <assert.h> #include "WEdge.h" #include "../system/FreestyleConfig.h" #include "../geometry/normal_cycle.h" @@ -43,7 +44,7 @@ static bool triangle_obtuse (WVertex*, WFace * f) bool b=false; for (int i=0; i<3; i++) b = b || - ((f->getEdgeList()[i]->getVec3r() * f->getEdgeList()[(i+1)%3]->getVec3r()) < 0); + ((f->getEdgeList()[i]->GetVec() * f->getEdgeList()[(i+1)%3]->GetVec()) < 0); return b; } @@ -378,7 +379,7 @@ void gts_vertex_principal_directions (WVertex * v, */ /* find the vector from v along edge e */ - vec_edge=Vec3r(-1*e->getVec3r()); + vec_edge=Vec3r(-1*e->GetVec()); ve2 = vec_edge.squareNorm(); vdotN = vec_edge * N; @@ -534,11 +535,11 @@ void gts_vertex_principal_directions (WVertex * v, } namespace OGF { - static real angle(WOEdge* h) { - Vec3r e(h->GetbVertex()->GetVertex()-h->GetaVertex()->GetVertex()) ; - Vec3r n1 = h->GetbFace()->GetNormal(); - Vec3r n2 = h->GetaFace()->GetNormal(); - real sine = (n1 ^ n2) * e / e.norm() ; + inline static real angle(WOEdge * h) { + const Vec3r& n1 = h->GetbFace()->GetNormal(); + const Vec3r& n2 = h->GetaFace()->GetNormal(); + const Vec3r v = h->getVec3r(); + real sine = (n1 ^ n2) * v / v.norm() ; if(sine >= 1.0) { return M_PI / 2.0 ; } @@ -606,13 +607,12 @@ namespace OGF { WVertex::incoming_edge_iterator woeitend = v->incoming_edges_end(); for(;woeit!=woeitend; ++woeit){ WOEdge *h = *woeit; - Vec3r V(h->GetaVertex()->GetVertex()-h->GetbVertex()->GetVertex()) ; - if((v == start) || V * (P - O) > 0.0) { + if((v == start) || h->GetVec() * (O - P) > 0.0) { + Vec3r V(-1 * h->GetVec()); bool isect = sphere_clip_vector(O, radius, P, V) ; - if(h->GetOwner()->GetNumberOfOEdges() == 2) { - real beta = angle(h) ; - nc.accumulate_dihedral_angle(V, beta) ; - } + assert (h->GetOwner()->GetNumberOfOEdges() == 2); // Because otherwise v->isBoundary() would be true + nc.accumulate_dihedral_angle(V, h->GetAngle()) ; + if(!isect) { WVertex* w = h->GetaVertex() ; if(vertices.find(w) == vertices.end()) { @@ -637,11 +637,9 @@ namespace OGF { WVertex::incoming_edge_iterator woeitend = start->incoming_edges_end(); for(;woeit!=woeitend; ++woeit){ WOEdge *h = (*woeit)->twin(); - Vec3r hvec(h->GetbVertex()->GetVertex()-h->GetaVertex()->GetVertex()); - nc.accumulate_dihedral_angle(hvec, angle(h)) ; + nc.accumulate_dihedral_angle(h->GetVec(), h->GetAngle()) ; WOEdge *hprev = h->getPrevOnFace(); - Vec3r hprevvec(hprev->GetbVertex()->GetVertex()-hprev->GetaVertex()->GetVertex()); - nc.accumulate_dihedral_angle(hprevvec, angle(hprev)) ; + nc.accumulate_dihedral_angle(hprev->GetVec(), hprev->GetAngle()) ; } } diff --git a/source/blender/freestyle/intern/winged_edge/WEdge.cpp b/source/blender/freestyle/intern/winged_edge/WEdge.cpp index 31082e3376f..a5918fd8400 100755 --- a/source/blender/freestyle/intern/winged_edge/WEdge.cpp +++ b/source/blender/freestyle/intern/winged_edge/WEdge.cpp @@ -178,6 +178,9 @@ WOEdge::WOEdge(WOEdge& iBrother) userdata = NULL; iBrother.userdata = new oedgedata; ((oedgedata*)(iBrother.userdata))->_copy = this; + + _vec = iBrother._vec; + _angle = iBrother._angle; } WOEdge * WOEdge::duplicate() @@ -680,8 +683,27 @@ WFace* WShape::MakeFace(vector<WVertex*>& iVertexList, unsigned iMaterial, WFace } } + + vector<WVertex*>::iterator it; + + // compute the face normal (v1v2 ^ v1v3) + WVertex *v1, *v2, *v3; + it = iVertexList.begin(); + v1 = *it; + it++; + v2 = *it; + it++; + v3 = *it; + + Vec3r vector1(v2->GetVertex()-v1->GetVertex()); + Vec3r vector2(v3->GetVertex()-v1->GetVertex()); + + Vec3r normal(vector1 ^ vector2); + normal.normalize(); + face->setNormal(normal); + // vertex pointers used to build each edge - vector<WVertex*>::iterator va, vb, it; + vector<WVertex*>::iterator va, vb; va = iVertexList.begin(); vb = va; @@ -710,25 +732,9 @@ WFace* WShape::MakeFace(vector<WVertex*>& iVertexList, unsigned iMaterial, WFace edge->setId(_EdgeList.size()); AddEdge(edge); // compute the mean edge value: - _meanEdgeSize += edge->GetaOEdge()->getVec3r().norm(); + _meanEdgeSize += edge->GetaOEdge()->GetVec().norm(); } } - - // compute the face normal (v1v2 ^ v1v3) - WVertex *v1, *v2, *v3; - it = iVertexList.begin(); - v1 = *it; - it++; - v2 = *it; - it++; - v3 = *it; - - Vec3r vector1(v2->GetVertex()-v1->GetVertex()); - Vec3r vector2(v3->GetVertex()-v1->GetVertex()); - - Vec3r normal(vector1 ^ vector2); - normal.normalize(); - face->setNormal(normal); // Add the face to the shape's faces list: face->setId(id); diff --git a/source/blender/freestyle/intern/winged_edge/WEdge.h b/source/blender/freestyle/intern/winged_edge/WEdge.h index ebf26cd6d23..abb6263ae69 100755 --- a/source/blender/freestyle/intern/winged_edge/WEdge.h +++ b/source/blender/freestyle/intern/winged_edge/WEdge.h @@ -32,6 +32,7 @@ # include <vector> # include <iterator> +# include <math.h> # include "../system/FreestyleConfig.h" # include "../geometry/Geom.h" # include "../scene_graph/FrsMaterial.h" @@ -295,7 +296,11 @@ protected: WFace *_pbFace; // when following the edge, face on the left WEdge *_pOwner; // Edge + Vec3r _vec; + real _angle; + public: + void *userdata; inline WOEdge() { @@ -326,6 +331,9 @@ public: inline WFace *GetaFace() {return _paFace;} inline WFace *GetbFace() {return _pbFace;} inline WEdge *GetOwner() {return _pOwner;} + + inline const Vec3r& GetVec() { return _vec; } + inline const real GetAngle() { return _angle; } /*! modifiers */ @@ -333,10 +341,11 @@ public: // inline void SetbCWEdge(WOEdge *pe) {_pbCWEdge = pe;} // inline void SetaCCWEdge(WOEdge *pe) {_paCCWEdge = pe;} // inline void SetbCCCWEdge(WOEdge *pe) {_pbCCWEdge = pe;} - inline void setaVertex(WVertex *pv) {_paVertex = pv;} - inline void setbVertex(WVertex *pv) {_pbVertex = pv;} - inline void setaFace(WFace *pf) {_paFace = pf;} - inline void setbFace(WFace *pf) {_pbFace = pf;} + inline void setVecAndAngle(); + inline void setaVertex(WVertex *pv) {_paVertex = pv; setVecAndAngle(); } + inline void setbVertex(WVertex *pv) {_pbVertex = pv; setVecAndAngle(); } + inline void setaFace(WFace *pf) {_paFace = pf; setVecAndAngle(); } + inline void setbFace(WFace *pf) {_pbFace = pf; setVecAndAngle(); } inline void setOwner(WEdge *pe) {_pOwner = pe;} /*! Retrieves the list of edges in CW order */ @@ -955,4 +964,22 @@ void WOEdge::RetrieveCWOrderedEdges(vector<WEdge*>& oEdges) } while((currentOEdge != NULL) && (currentOEdge->GetOwner() != GetOwner())); } +inline void WOEdge::setVecAndAngle() { + if ( _paVertex != NULL && _pbVertex != NULL ) { + _vec = _pbVertex->GetVertex() - _paVertex->GetVertex(); + if ( _paFace != NULL && _pbFace != NULL ) { + real sine = (_pbFace->GetNormal() ^ _paFace->GetNormal()) * _vec / _vec.norm() ; + if(sine >= 1.0) { + _angle = M_PI / 2.0 ; + return; + } + if(sine <= -1.0) { + _angle = -M_PI / 2.0 ; + return; + } + _angle = ::asin(sine); + } + } +} + #endif // WEDGE_H diff --git a/source/blender/makesdna/DNA_freestyle_types.h b/source/blender/makesdna/DNA_freestyle_types.h index 390f726de57..3eec6a97172 100644 --- a/source/blender/makesdna/DNA_freestyle_types.h +++ b/source/blender/makesdna/DNA_freestyle_types.h @@ -74,6 +74,16 @@ struct FreestyleLineStyle; #define FREESTYLE_QI_HIDDEN 2 #define FREESTYLE_QI_RANGE 3 +/* FreestyleConfig::raycasting_algorithm */ +// Defines should be replaced with ViewMapBuilder::visibility_algo +#define FREESTYLE_ALGO_REGULAR 1 +#define FREESTYLE_ALGO_FAST 2 +#define FREESTYLE_ALGO_VERYFAST 3 +#define FREESTYLE_ALGO_CULLED_ADAPTIVE_TRADITIONAL 4 +#define FREESTYLE_ALGO_ADAPTIVE_TRADITIONAL 5 +#define FREESTYLE_ALGO_CULLED_ADAPTIVE_CUMULATIVE 6 +#define FREESTYLE_ALGO_ADAPTIVE_CUMULATIVE 7 + typedef struct FreestyleLineSet { struct FreestyleLineSet *next, *prev; @@ -104,12 +114,12 @@ typedef struct FreestyleConfig { ListBase modules; int mode; /* scripting, editor */ + int raycasting_algorithm; /* regular, fast, very fast, etc. */ int flags; /* suggestive contours, ridges/valleys, material boundaries */ float sphere_radius; float dkr_epsilon; float crease_angle; - int pad; - + ListBase linesets; } FreestyleConfig; diff --git a/source/blender/makesrna/intern/rna_scene.c b/source/blender/makesrna/intern/rna_scene.c index dca2540af14..f6704efb777 100644 --- a/source/blender/makesrna/intern/rna_scene.c +++ b/source/blender/makesrna/intern/rna_scene.c @@ -1699,6 +1699,17 @@ static void rna_def_freestyle_settings(BlenderRNA *brna) {FREESTYLE_QI_RANGE, "RANGE", 0, "QI Range", "Select feature edges within a range of quantitative invisibility (QI) values."}, {0, NULL, 0, NULL, NULL}}; + static EnumPropertyItem freestyle_raycasting_algorithm_items[] = { + {FREESTYLE_ALGO_REGULAR, "REGULAR", 0, "Normal Ray Casting", "Consider all FEdges in each ViewEdge"}, + {FREESTYLE_ALGO_FAST, "FAST", 0, "Fast Ray Casting", "Sample some FEdges in each ViewEdge"}, + {FREESTYLE_ALGO_VERYFAST, "VERYFAST", 0, "Very Fast Ray Casting", "Sample one FEdge in each ViewEdge; do not save list of occluders"}, + {FREESTYLE_ALGO_CULLED_ADAPTIVE_TRADITIONAL, "CULLEDADAPTIVETRADITIONAL", 0, "Culled Traditional Visibility Detection", "Culled adaptive grid with heuristic density and traditional QI calculation"}, + {FREESTYLE_ALGO_ADAPTIVE_TRADITIONAL, "ADAPTIVETRADITIONAL", 0, "Unculled Traditional Visibility Detection", "Adaptive grid with heuristic density and traditional QI calculation"}, + {FREESTYLE_ALGO_CULLED_ADAPTIVE_CUMULATIVE, "CULLEDADAPTIVECUMULATIVE", 0, "Culled Cumulative Visibility Detection", "Culled adaptive grid with heuristic density and cumulative QI calculation"}, + {FREESTYLE_ALGO_ADAPTIVE_CUMULATIVE, "ADAPTIVECUMULATIVE", 0, "Unculled Cumulative Visibility Detection", "Adaptive grid with heuristic density and cumulative QI calculation"}, + {0, NULL, 0, NULL, NULL}}; + + /* FreestyleLineSet */ srna= RNA_def_struct(brna, "FreestyleLineSet", NULL); @@ -1866,6 +1877,12 @@ static void rna_def_freestyle_settings(BlenderRNA *brna) RNA_def_property_ui_text(prop, "Control Mode", "Select the Freestyle control mode"); RNA_def_property_update(prop, NC_SCENE, NULL); + prop= RNA_def_property(srna, "raycasting_algorithm", PROP_ENUM, PROP_NONE); + RNA_def_property_enum_sdna(prop, NULL, "raycasting_algorithm"); + RNA_def_property_enum_items(prop, freestyle_raycasting_algorithm_items); + RNA_def_property_ui_text(prop, "Raycasting Algorithm", "Select the Freestyle raycasting algorithm"); + RNA_def_property_update(prop, NC_SCENE, NULL); + prop= RNA_def_property(srna, "use_suggestive_contours", PROP_BOOLEAN, PROP_NONE); RNA_def_property_boolean_sdna(prop, NULL, "flags", FREESTYLE_SUGGESTIVE_CONTOURS_FLAG); RNA_def_property_ui_text(prop, "Suggestive Contours", "Enable suggestive contours."); |