diff options
Diffstat (limited to 'source/blender/freestyle/intern/geometry')
10 files changed, 325 insertions, 52 deletions
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() ; + } + //_________________________________________________________ } |