diff options
author | Maxime Curioni <maxime.curioni@gmail.com> | 2008-05-08 23:16:40 +0400 |
---|---|---|
committer | Maxime Curioni <maxime.curioni@gmail.com> | 2008-05-08 23:16:40 +0400 |
commit | 64e4a3ec9aed6c8abe095e2cd1fe1552f7cde51c (patch) | |
tree | 6c77358bd447b6c2d215324ef48fc12d1f5ae5ca /source/blender/freestyle/intern/winged_edge | |
parent | cf2e1e2857cfc5b3c2848c7fc6c9d919ac72fabb (diff) | |
parent | 106974a9d2d5caa5188322507980e3d57d2e3517 (diff) |
soc-2008-mxcurioni: merged changes to revision 14747, cosmetic changes for source/blender/freestyle
Diffstat (limited to 'source/blender/freestyle/intern/winged_edge')
17 files changed, 4440 insertions, 0 deletions
diff --git a/source/blender/freestyle/intern/winged_edge/Curvature.cpp b/source/blender/freestyle/intern/winged_edge/Curvature.cpp new file mode 100755 index 00000000000..a890fb92c04 --- /dev/null +++ b/source/blender/freestyle/intern/winged_edge/Curvature.cpp @@ -0,0 +1,647 @@ +/* GTS - Library for the manipulation of triangulated surfaces + * Copyright (C) 1999-2002 Ray Jones, Stéphane Popinet + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Library General Public + * License as published by the Free Software Foundation; either + * version 2 of the License, or (at your option) any later version. + * + * This library 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 + * Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with this library; if not, write to the + * Free Software Foundation, Inc., 59 Temple Place - Suite 330, + * Boston, MA 02111-1307, USA. + */ + +#include "Curvature.h" +#include <math.h> +#include "WEdge.h" +#include "../system/FreestyleConfig.h" +#include "../geometry/normal_cycle.h" +#include <set> +#include <stack> + +static bool angle_obtuse (WVertex * v, WFace * f) +{ + WOEdge * e; + f->getOppositeEdge (v, e); + + Vec3r vec1(e->GetaVertex()->GetVertex()-v->GetVertex()); + Vec3r vec2(e->GetbVertex()->GetVertex()-v->GetVertex()); + return ((vec1 * vec2) < 0); +} + +// FIXME +// WVvertex is useless but kept for history reasons +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); + return b; +} + +static real cotan (WVertex * vo, WVertex * v1, WVertex * v2) +{ + /* cf. Appendix B of [Meyer et al 2002] */ + real udotv, denom; + + Vec3r u(v1->GetVertex()- vo->GetVertex()); + Vec3r v(v2->GetVertex()- vo->GetVertex()); + + udotv = u * v; + denom = sqrt(u.squareNorm() * v.squareNorm() - udotv * udotv); + + /* denom can be zero if u==v. Returning 0 is acceptable, based on + * the callers of this function below. */ + if (denom == 0.0) return (0.0); + + return (udotv / denom); +} + +static real angle_from_cotan (WVertex * vo, WVertex * v1, WVertex * v2) +{ + /* cf. Appendix B and the caption of Table 1 from [Meyer et al 2002] */ + real udotv, denom; + + Vec3r u (v1->GetVertex()-vo->GetVertex()); + Vec3r v(v2->GetVertex()-vo->GetVertex()); + + udotv = u * v; + denom = sqrt(u.squareNorm() * v.squareNorm() - udotv * udotv); + + /* Note: I assume this is what they mean by using atan2 (). -Ray Jones */ + + /* tan = denom/udotv = y/x (see man page for atan2) */ + return (fabs (atan2 (denom, udotv))); +} + +/** + * gts_vertex_mean_curvature_normal: + * @v: a #WVertex. + * @s: a #GtsSurface. + * @Kh: the Mean Curvature Normal at @v. + * + * Computes the Discrete Mean Curvature Normal approximation at @v. + * The mean curvature at @v is half the magnitude of the vector @Kh. + * + * Note: the normal computed is not unit length, and may point either + * into or out of the surface, depending on the curvature at @v. It + * is the responsibility of the caller of the function to use the mean + * curvature normal appropriately. + * + * This approximation is from the paper: + * Discrete Differential-Geometry Operators for Triangulated 2-Manifolds + * Mark Meyer, Mathieu Desbrun, Peter Schroder, Alan H. Barr + * VisMath '02, Berlin (Germany) + * http://www-grail.usc.edu/pubs.html + * + * Returns: %TRUE if the operator could be evaluated, %FALSE if the + * evaluation failed for some reason (@v is boundary or is the + * endpoint of a non-manifold edge.) + */ +bool gts_vertex_mean_curvature_normal (WVertex * v, Vec3r &Kh) +{ + real area = 0.0; + + if (!v) return false; + + /* this operator is not defined for boundary edges */ + if (v->isBoundary()) return false; + + WVertex::incoming_edge_iterator itE; + + for (itE=v->incoming_edges_begin(); + itE!=v->incoming_edges_end(); itE++) + area+=(*itE)->GetaFace()->getArea(); + + Kh=Vec3r(0.0, 0.0, 0.0); + + for (itE=v->incoming_edges_begin(); + itE!=v->incoming_edges_end(); itE++) + { + WOEdge * e = (*itE)->getPrevOnFace(); + //if ((e->GetaVertex()==v) || (e->GetbVertex()==v)) cerr<< "BUG "; + + WVertex * v1 = e->GetaVertex(); + WVertex * v2 = e->GetbVertex(); + real temp; + + temp = cotan (v1, v, v2); + Kh = Vec3r(Kh+temp*(v2->GetVertex()-v->GetVertex())); + + temp = cotan (v2, v, v1); + Kh = Vec3r(Kh+temp*(v1->GetVertex()-v->GetVertex())); + } + if (area > 0.0) + { + Kh[0] /= 2*area; + Kh[1] /= 2*area; + Kh[2] /= 2*area; + } + else return false; + + return true; +} + +/** + * gts_vertex_gaussian_curvature: + * @v: a #WVertex. + * @s: a #GtsSurface. + * @Kg: the Discrete Gaussian Curvature approximation at @v. + * + * Computes the Discrete Gaussian Curvature approximation at @v. + * + * This approximation is from the paper: + * Discrete Differential-Geometry Operators for Triangulated 2-Manifolds + * Mark Meyer, Mathieu Desbrun, Peter Schroder, Alan H. Barr + * VisMath '02, Berlin (Germany) + * http://www-grail.usc.edu/pubs.html + * + * Returns: %TRUE if the operator could be evaluated, %FALSE if the + * evaluation failed for some reason (@v is boundary or is the + * endpoint of a non-manifold edge.) + */ +bool gts_vertex_gaussian_curvature (WVertex * v, real * Kg) +{ + real area = 0.0; + real angle_sum = 0.0; + + if (!v) return false; + if (!Kg) return false; + + /* this operator is not defined for boundary edges */ + if (v->isBoundary()) {*Kg=0.0 ;return false;} + + WVertex::incoming_edge_iterator itE; + for (itE=v->incoming_edges_begin(); + itE!=v->incoming_edges_end(); itE++) + area+=(*itE)->GetaFace()->getArea(); + + for (itE=v->incoming_edges_begin(); + itE!=v->incoming_edges_end(); itE++) + { + WOEdge * e = (*itE)->getPrevOnFace(); + WVertex * v1 = e->GetaVertex(); + WVertex * v2 = e->GetbVertex(); + angle_sum += angle_from_cotan (v, v1, v2); + } + + *Kg = (2.0*M_PI - angle_sum)/area; + + return true; +} + +/** + * gts_vertex_principal_curvatures: + * @Kh: mean curvature. + * @Kg: Gaussian curvature. + * @K1: first principal curvature. + * @K2: second principal curvature. + * + * Computes the principal curvatures at a point given the mean and + * Gaussian curvatures at that point. + * + * The mean curvature can be computed as one-half the magnitude of the + * vector computed by gts_vertex_mean_curvature_normal(). + * + * The Gaussian curvature can be computed with + * gts_vertex_gaussian_curvature(). + */ +void gts_vertex_principal_curvatures (real Kh, real Kg, + real * K1, real * K2) +{ + real temp = Kh*Kh - Kg; + + if (!K1) return; + if (!K1) return; + + if (temp < 0.0) temp = 0.0; + temp = sqrt (temp); + *K1 = Kh + temp; + *K2 = Kh - temp; +} + +/* from Maple */ +static void linsolve (real m11, real m12, real b1, + real m21, real m22, real b2, + real * x1, real * x2) +{ + real temp; + + temp = 1.0 / (m21*m12 - m11*m22); + *x1 = (m12*b2 - m22*b1)*temp; + *x2 = (m11*b2 - m21*b1)*temp; +} + +/* from Maple - largest eigenvector of [a b; b c] */ +static void eigenvector (real a, real b, real c, + Vec3r e) +{ + if (b == 0.0) { + e[0] = 0.0; + } else { + e[0] = -(c - a - sqrt (c*c - 2*a*c + a*a + 4*b*b))/(2*b); + } + e[1] = 1.0; + e[2] = 0.0; +} + +/** + * gts_vertex_principal_directions: + * @v: a #WVertex. + * @s: a #GtsSurface. + * @Kh: mean curvature normal (a #Vec3r). + * @Kg: Gaussian curvature (a real). + * @e1: first principal curvature direction (direction of largest curvature). + * @e2: second principal curvature direction. + * + * Computes the principal curvature directions at a point given @Kh + * and @Kg, the mean curvature normal and Gaussian curvatures at that + * point, computed with gts_vertex_mean_curvature_normal() and + * gts_vertex_gaussian_curvature(), respectively. + * + * Note that this computation is very approximate and tends to be + * unstable. Smoothing of the surface or the principal directions may + * be necessary to achieve reasonable results. + */ +void gts_vertex_principal_directions (WVertex * v, + Vec3r Kh, real Kg, + Vec3r &e1, Vec3r &e2) +{ + Vec3r N; + real normKh; + + Vec3r basis1, basis2, d, eig; + real ve2, vdotN; + real aterm_da, bterm_da, cterm_da, const_da; + real aterm_db, bterm_db, cterm_db, const_db; + real a, b, c; + real K1, K2; + real *weights, *kappas, *d1s, *d2s; + int edge_count; + real err_e1, err_e2; + int e; + WVertex::incoming_edge_iterator itE; + + /* compute unit normal */ + normKh = Kh.norm(); + + if (normKh > 0.0) { + Kh.normalize(); + } else { + /* This vertex is a point of zero mean curvature (flat or saddle + * point). Compute a normal by averaging the adjacent triangles + */ + N[0] = N[1] = N[2] = 0.0; + + for (itE=v->incoming_edges_begin(); + itE!=v->incoming_edges_end(); itE++) + N=Vec3r(N+(*itE)->GetaFace()->GetNormal()); + real normN = N.norm(); + if (normN <= 0.0) + return; + N.normalize(); + } + + + /* construct a basis from N: */ + /* set basis1 to any component not the largest of N */ + basis1[0] = basis1[1] = basis1[2] = 0.0; + if (fabs (N[0]) > fabs (N[1])) + basis1[1] = 1.0; + else + basis1[0] = 1.0; + + /* make basis2 orthogonal to N */ + basis2 = (N ^ basis1); + basis2.normalize(); + + /* make basis1 orthogonal to N and basis2 */ + basis1 = (N ^ basis2); + basis1.normalize(); + + aterm_da = bterm_da = cterm_da = const_da = 0.0; + aterm_db = bterm_db = cterm_db = const_db = 0.0; + int nb_edges=v->GetEdges().size(); + + weights = (real *) malloc (sizeof (real)*nb_edges); + kappas = (real*) malloc (sizeof (real)*nb_edges); + d1s = (real*) malloc (sizeof (real)*nb_edges); + d2s = (real*) malloc (sizeof (real)*nb_edges); + edge_count = 0; + + for (itE=v->incoming_edges_begin(); + itE!=v->incoming_edges_end(); itE++) + { + WOEdge * e; + WFace * f1, * f2; + real weight, kappa, d1, d2; + Vec3r vec_edge; + if (! *itE) continue; + e = *itE; + + /* since this vertex passed the tests in + * gts_vertex_mean_curvature_normal(), this should be true. */ + //g_assert (gts_edge_face_number (e, s) == 2); + + /* identify the two triangles bordering e in s */ + f1=e->GetaFace(); + f2=e->GetbFace(); + + /* We are solving for the values of the curvature tensor + * B = [ a b ; b c ]. + * The computations here are from section 5 of [Meyer et al 2002]. + * + * The first step is to calculate the linear equations governing + * the values of (a,b,c). These can be computed by setting the + * derivatives of the error E to zero (section 5.3). + * + * Since a + c = norm(Kh), we only compute the linear equations + * for dE/da and dE/db. (NB: [Meyer et al 2002] has the + * equation a + b = norm(Kh), but I'm almost positive this is + * incorrect.) + * + * Note that the w_ij (defined in section 5.2) are all scaled by + * (1/8*A_mixed). We drop this uniform scale factor because the + * solution of the linear equations doesn't rely on it. + * + * The terms of the linear equations are xterm_dy with x in + * {a,b,c} and y in {a,b}. There are also const_dy terms that are + * the constant factors in the equations. + */ + + /* find the vector from v along edge e */ + vec_edge=Vec3r(-1*e->getVec3r()); + + ve2 = vec_edge.squareNorm(); + vdotN = vec_edge * N; + + /* section 5.2 - There is a typo in the computation of kappa. The + * edges should be x_j-x_i. + */ + kappa = 2.0 * vdotN / ve2; + + /* section 5.2 */ + + /* I don't like performing a minimization where some of the + * weights can be negative (as can be the case if f1 or f2 are + * obtuse). To ensure all-positive weights, we check for + * obtuseness. */ + weight = 0.0; + if (! triangle_obtuse(v, f1)) { + weight += ve2 * + cotan (f1->GetNextOEdge(e->twin())->GetbVertex(), + e->GetaVertex(), e->GetbVertex()) / 8.0; + } else { + if (angle_obtuse (v, f1)) { + weight += ve2 * f1->getArea() / 4.0; + } else { + weight += ve2 * f1->getArea() / 8.0; + } + } + + if (! triangle_obtuse(v, f2)) { + weight += ve2 * + cotan (f2->GetNextOEdge(e)->GetbVertex(), + e->GetaVertex(), e->GetbVertex()) / 8.0; + } else { + if (angle_obtuse (v, f2)) { + weight += ve2 * f1->getArea() / 4.0; + } else { + weight += ve2 * f1->getArea() / 8.0; + } + } + + /* projection of edge perpendicular to N (section 5.3) */ + d[0] = vec_edge[0] - vdotN * N[0]; + d[1] = vec_edge[1] - vdotN * N[1]; + d[2] = vec_edge[2] - vdotN * N[2]; + d.normalize(); + + /* not explicit in the paper, but necessary. Move d to 2D basis. */ + d1 = d * basis1; + d2 = d * basis2; + + /* store off the curvature, direction of edge, and weights for later use */ + weights[edge_count] = weight; + kappas[edge_count] = kappa; + d1s[edge_count] = d1; + d2s[edge_count] = d2; + edge_count++; + + /* Finally, update the linear equations */ + aterm_da += weight * d1 * d1 * d1 * d1; + bterm_da += weight * d1 * d1 * 2 * d1 * d2; + cterm_da += weight * d1 * d1 * d2 * d2; + const_da += weight * d1 * d1 * (- kappa); + + aterm_db += weight * d1 * d2 * d1 * d1; + bterm_db += weight * d1 * d2 * 2 * d1 * d2; + cterm_db += weight * d1 * d2 * d2 * d2; + const_db += weight * d1 * d2 * (- kappa); + + } + + /* now use the identity (Section 5.3) a + c = |Kh| = 2 * kappa_h */ + aterm_da -= cterm_da; + const_da += cterm_da * normKh; + + aterm_db -= cterm_db; + const_db += cterm_db * normKh; + + /* check for solvability of the linear system */ + if (((aterm_da * bterm_db - aterm_db * bterm_da) != 0.0) && + ((const_da != 0.0) || (const_db != 0.0))) { + linsolve (aterm_da, bterm_da, -const_da, + aterm_db, bterm_db, -const_db, + &a, &b); + + c = normKh - a; + + eigenvector (a, b, c, eig); + } else { + /* region of v is planar */ + eig[0] = 1.0; + eig[1] = 0.0; + } + + /* Although the eigenvectors of B are good estimates of the + * principal directions, it seems that which one is attached to + * which curvature direction is a bit arbitrary. This may be a bug + * in my implementation, or just a side-effect of the inaccuracy of + * B due to the discrete nature of the sampling. + * + * To overcome this behavior, we'll evaluate which assignment best + * matches the given eigenvectors by comparing the curvature + * estimates computed above and the curvatures calculated from the + * discrete differential operators. */ + + gts_vertex_principal_curvatures (0.5 * normKh, Kg, &K1, &K2); + + err_e1 = err_e2 = 0.0; + /* loop through the values previously saved */ + for (e = 0; e < edge_count; e++) { + real weight, kappa, d1, d2; + real temp1, temp2; + real delta; + + weight = weights[e]; + kappa = kappas[e]; + d1 = d1s[e]; + d2 = d2s[e]; + + temp1 = fabs (eig[0] * d1 + eig[1] * d2); + temp1 = temp1 * temp1; + temp2 = fabs (eig[1] * d1 - eig[0] * d2); + temp2 = temp2 * temp2; + + /* err_e1 is for K1 associated with e1 */ + delta = K1 * temp1 + K2 * temp2 - kappa; + err_e1 += weight * delta * delta; + + /* err_e2 is for K1 associated with e2 */ + delta = K2 * temp1 + K1 * temp2 - kappa; + err_e2 += weight * delta * delta; + } + free (weights); + free (kappas); + free (d1s); + free (d2s); + + /* rotate eig by a right angle if that would decrease the error */ + if (err_e2 < err_e1) { + real temp = eig[0]; + + eig[0] = eig[1]; + eig[1] = -temp; + } + + e1[0] = eig[0] * basis1[0] + eig[1] * basis2[0]; + e1[1] = eig[0] * basis1[1] + eig[1] * basis2[1]; + e1[2] = eig[0] * basis1[2] + eig[1] * basis2[2]; + e1.normalize(); + + /* make N,e1,e2 a right handed coordinate sytem */ + e2 = N ^ e1; + e2.normalize(); +} + +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() ; + if(sine >= 1.0) { + return M_PI / 2.0 ; + } + if(sine <= -1.0) { + return -M_PI / 2.0 ; + } + return ::asin(sine) ; + } + + // precondition1: P is inside the sphere + // precondition2: P,V points to the outside of + // the sphere (i.e. OP.V > 0) + static bool sphere_clip_vector( + const Vec3r& O, real r, + const Vec3r& P, Vec3r& V + ) { + + Vec3r W = P - O ; + real a = V.squareNorm() ; + real b = 2.0 * V * W ; + real c = W.squareNorm() - r*r ; + real delta = b*b - 4*a*c ; + if(delta < 0) { + // Should not happen, but happens sometimes (numerical precision) + return true ; + } + real t = - b + ::sqrt(delta) / (2.0 * a) ; + if(t < 0.0) { + // Should not happen, but happens sometimes (numerical precision) + return true ; + } + if(t >= 1.0) { + // Inside the sphere + return false ; + } + + V[0] = (t * V.x()) ; + V[1] = (t * V.y()) ; + V[2] = (t * V.z()) ; + + return true ; + } + + // TODO: check optimizations: + // use marking ? (measure *timings* ...) + void compute_curvature_tensor( + WVertex* start, real radius, NormalCycle& nc + ) { + // in case we have a non-manifold vertex, skip it... + if(start->isBoundary()) + return; + + std::set<WVertex*> vertices ; + const Vec3r& O = start->GetVertex() ; + std::stack<WVertex*> S ; + S.push(start) ; + vertices.insert(start) ; + while(!S.empty()) { + WVertex* v = S.top() ; + S.pop() ; + if(v->isBoundary()) + continue; + const Vec3r& P = v->GetVertex() ; + WVertex::incoming_edge_iterator woeit = v->incoming_edges_begin(); + 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) { + bool isect = sphere_clip_vector(O, radius, P, V) ; + if(h->GetOwner()->GetNumberOfOEdges() == 2) { + real beta = angle(h) ; + nc.accumulate_dihedral_angle(V, beta) ; + } + if(!isect) { + WVertex* w = h->GetaVertex() ; + if(vertices.find(w) == vertices.end()) { + vertices.insert(w) ; + S.push(w) ; + } + } + } + } + } + } + + + void compute_curvature_tensor_one_ring( + WVertex* start, NormalCycle& nc + ) { + // in case we have a non-manifold vertex, skip it... + if(start->isBoundary()) + return; + + WVertex::incoming_edge_iterator woeit = start->incoming_edges_begin(); + 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)) ; + WOEdge *hprev = h->getPrevOnFace(); + Vec3r hprevvec(hprev->GetbVertex()->GetVertex()-hprev->GetaVertex()->GetVertex()); + nc.accumulate_dihedral_angle(hprevvec, angle(hprev)) ; + } + } + +} diff --git a/source/blender/freestyle/intern/winged_edge/Curvature.h b/source/blender/freestyle/intern/winged_edge/Curvature.h new file mode 100755 index 00000000000..214a32ca922 --- /dev/null +++ b/source/blender/freestyle/intern/winged_edge/Curvature.h @@ -0,0 +1,156 @@ + +/* GTS - Library for the manipulation of triangulated surfaces + * Copyright (C) 1999 Stéphane Popinet + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Library General Public + * License as published by the Free Software Foundation; either + * version 2 of the License, or (at your option) any later version. + * + * This library 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 + * Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with this library; if not, write to the + * Free Software Foundation, Inc., 59 Temple Place - Suite 330, + * Boston, MA 02111-1307, USA. + */ + +#ifndef __CURVATURE_H__ +#define __CURVATURE_H__ + +# include "../system/FreestyleConfig.h" +# include "../system/Precision.h" +# include "../geometry/Geom.h" +using namespace Geometry; + +class WVertex; + +class LIB_WINGED_EDGE_EXPORT CurvatureInfo +{ +public: + + CurvatureInfo() + { + K1 = 0.0; + K2 = 0.0; + e1 = Vec3r(0.0,0.0,0.0); + e2 = Vec3r(0.0,0.0,0.0); + Kr = 0.0; + dKr = 0.0; + er = Vec3r(0.0,0.0,0.0); + } + + CurvatureInfo(const CurvatureInfo& iBrother){ + K1 = iBrother.K1; + K2 = iBrother.K2; + e1 = iBrother.e1; + e2 = iBrother.e2; + Kr = iBrother.Kr; + dKr = iBrother.dKr; + er = iBrother.er; + } + + CurvatureInfo(const CurvatureInfo& ca, const CurvatureInfo& cb, real t) { + K1 = ca.K1 + t * (cb.K1 - ca.K1); + K2 = ca.K2 + t * (cb.K2 - ca.K2); + e1 = ca.e1 + t * (cb.e1 - ca.e1); + e2 = ca.e2 + t * (cb.e2 - ca.e2); + Kr = ca.Kr + t * (cb.Kr - ca.Kr); + dKr = ca.dKr + t * (cb.dKr - ca.dKr); + er = ca.er + t * (cb.er - ca.er); + } + + real K1; // maximum curvature + real K2; // minimum curvature + Vec3r e1; // maximum curvature direction + Vec3r e2; // minimum curvature direction + real Kr; // radial curvature + real dKr; // radial curvature + Vec3r er; // radial curvature direction +}; + +class Face_Curvature_Info{ +public: + Face_Curvature_Info() {} + ~Face_Curvature_Info(){ + for(vector<CurvatureInfo*>::iterator ci=vec_curvature_info.begin(), ciend=vec_curvature_info.end(); + ci!=ciend; + ++ci){ + delete (*ci); + } + vec_curvature_info.clear(); + } + vector<CurvatureInfo *> vec_curvature_info; +}; + +bool LIB_WINGED_EDGE_EXPORT gts_vertex_mean_curvature_normal (WVertex * v, + Vec3r &n); + +bool LIB_WINGED_EDGE_EXPORT gts_vertex_gaussian_curvature (WVertex * v, + real * Kg); + +void LIB_WINGED_EDGE_EXPORT gts_vertex_principal_curvatures (real Kh, + real Kg, + real * K1, + real * K2); + +void LIB_WINGED_EDGE_EXPORT gts_vertex_principal_directions (WVertex * v, + Vec3r Kh, + real Kg, + Vec3r &e1, + Vec3r &e2); + +/* + * OGF/Graphite: Geometry and Graphics Programming Library + Utilities + * Copyright (C) 2000-2003 Bruno Levy + * + * 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., 675 Mass Ave, Cambridge, MA 02139, USA. + * + * If you modify this software, you should include a notice giving the + * name of the person performing the modification, the date of modification, + * and the reason for such modification. + * + * Contact: Bruno Levy + * + * levy@loria.fr + * + * ISA Project + * LORIA, INRIA Lorraine, + * Campus Scientifique, BP 239 + * 54506 VANDOEUVRE LES NANCY CEDEX + * FRANCE + * + * Note that the GNU General Public License does not permit incorporating + * the Software into proprietary programs. + */ + namespace OGF { + + class NormalCycle ; + + void LIB_WINGED_EDGE_EXPORT compute_curvature_tensor( + WVertex* start, double radius, NormalCycle& nc + ) ; + + void LIB_WINGED_EDGE_EXPORT compute_curvature_tensor_one_ring( + WVertex* start, NormalCycle& nc + ) ; + } + + +#endif /* __CURVATURE_H__ */ + diff --git a/source/blender/freestyle/intern/winged_edge/Nature.h b/source/blender/freestyle/intern/winged_edge/Nature.h new file mode 100755 index 00000000000..1f165e677f5 --- /dev/null +++ b/source/blender/freestyle/intern/winged_edge/Nature.h @@ -0,0 +1,75 @@ +// +// Filename : Nature.h +// Author(s) : Emmanuel Turquin +// Purpose : Different natures for both vertices and edges +// Date of creation : 01/07/2003 +// +/////////////////////////////////////////////////////////////////////////////// + + +// +// 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 NATURE_H +# define NATURE_H + +/*! \file Nature.h + * Definitions of Natures of the ViewMap's elements + */ + +/*! Namespace gathering the different possible + * natures of 0D and 1D elements of the ViewMap + */ +namespace Nature { + + typedef unsigned short VertexNature; + + /*! true for any 0D element */ + static const VertexNature POINT = 0; // 0 + /*! true for SVertex */ + static const VertexNature S_VERTEX = (1 << 0); // 1 + /*! true for ViewVertex */ + static const VertexNature VIEW_VERTEX = (1 << 1); // 2 + /*! true for NonTVertex */ + static const VertexNature NON_T_VERTEX = (1 << 2); // 4 + /*! true for TVertex */ + static const VertexNature T_VERTEX = (1 << 3); // 8 + /*! true for CUSP */ + static const VertexNature CUSP = (1 << 4); // 16 + + typedef unsigned short EdgeNature; + /*! true for non feature edges (always false for 1D elements of the ViewMap) */ + static const EdgeNature NO_FEATURE = 0; // 0 + /*! true for silhouettes */ + static const EdgeNature SILHOUETTE = (1 << 0); // 1 + /*! true for borders */ + static const EdgeNature BORDER = (1 << 1); // 2 + /*! true for creases */ + static const EdgeNature CREASE = (1 << 2); // 4 + /*! true for ridges */ + static const EdgeNature RIDGE = (1 << 3); // 8 + /*! true for valleys */ + static const EdgeNature VALLEY = (1 << 4); // 16 + /*! true for suggestive contours */ + static const EdgeNature SUGGESTIVE_CONTOUR = (1 << 5); // 32 + +} // end of namespace Nature + +#endif // NATURE_H diff --git a/source/blender/freestyle/intern/winged_edge/WEdge.cpp b/source/blender/freestyle/intern/winged_edge/WEdge.cpp new file mode 100755 index 00000000000..79b3a8dae26 --- /dev/null +++ b/source/blender/freestyle/intern/winged_edge/WEdge.cpp @@ -0,0 +1,732 @@ + +// +// 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 <iostream> +#include "WEdge.h" + +/*! Temporary structures */ +class vertexdata +{ +public: + WVertex *_copy; +}; + +class oedgedata +{ +public: + WOEdge *_copy; +}; + +class edgedata +{ +public: + WEdge *_copy; +}; + +class facedata +{ +public: + WFace *_copy; +}; + + + /**********************************/ + /* */ + /* */ + /* WVertex */ + /* */ + /* */ + /**********************************/ + +WVertex::WVertex(WVertex& iBrother) +{ + _Id = iBrother._Id; + _Vertex = iBrother._Vertex; + _EdgeList = iBrother._EdgeList; + + _Shape = iBrother._Shape; + _Smooth = iBrother._Smooth; + _Border = iBrother._Border; + userdata = NULL; + iBrother.userdata = new vertexdata; + ((vertexdata*)(iBrother.userdata))->_copy = this; +} + +WVertex* WVertex::dupplicate() +{ + WVertex *clone = new WVertex(*this); + return clone; +} + + +WOEdge* WVertex::incoming_edge_iterator::operator*() + +{ + return _current; +} +void WVertex::incoming_edge_iterator::increment(){ + WOEdge *twin = _current->twin(); + if(!twin){ + // we reached a hole + _current = 0; + return; + } + WOEdge *next = twin->getPrevOnFace(); + if(next == _begin){ + next = 0; + } + _current = next; +} + +WFace* WVertex::face_iterator::operator*(){ + WOEdge * woedge = *_edge_it; + if(woedge == 0) + return 0; + return (woedge)->GetbFace(); +} + +//bool WVertex::isBoundary () const{ +// return _Border; +//} +bool WVertex::isBoundary () +{ + if(_Border == 1) + return true; + else if(_Border == 0) + return false; + + vector<WEdge *>::const_iterator it; + for(it=_EdgeList.begin(); it!=_EdgeList.end(); it++){ + if((*it)->GetNumberOfOEdges() == 1){ + _Border = 1; + return true; + } + } + //if (!(*it)->GetaOEdge()->GetaFace()) return true; + _Border = 0; + return false; +} + +void WVertex::AddEdge(WEdge *iEdge) { + _EdgeList.push_back(iEdge); +} + +WVertex::incoming_edge_iterator WVertex::incoming_edges_begin(){ + WOEdge *begin; + WEdge * wedge = _EdgeList.front(); + WOEdge* aOEdge = wedge->GetaOEdge(); + if(aOEdge->GetbVertex() == this) + begin = aOEdge; + else + begin = _EdgeList.front()->GetbOEdge(); + return incoming_edge_iterator(this, begin, begin); +} +WVertex::incoming_edge_iterator WVertex::incoming_edges_end(){ + WOEdge *begin; + WOEdge* aOEdge = _EdgeList.front()->GetaOEdge(); + if(aOEdge->GetbVertex() == this) + begin = aOEdge; + else + begin = _EdgeList.front()->GetbOEdge(); + return incoming_edge_iterator(this, begin, 0); +} +//WOEdge** WVertex::incoming_edge_iterator::operator->() +//{ +// WOEdge ** ppaOEdge = (*_iter)->GetaOEdge(); +// if(aOEdge->GetbVertex() == _vertex) +// return ppaOEdge; +// else +// { +// WOEdge *bOEdge = (*_iter)->GetbOEdge(); +// return &bOEdge; +// } +// +//} + /**********************************/ + /* */ + /* */ + /* WOEdge */ + /* */ + /* */ + /**********************************/ + +WOEdge::WOEdge(WOEdge& iBrother) +{ + _paVertex = iBrother.GetaVertex(); + _pbVertex = iBrother.GetbVertex(); + _paFace = iBrother.GetaFace(); + _pbFace = iBrother.GetbFace(); + _pOwner = iBrother.GetOwner(); + userdata = NULL; + iBrother.userdata = new oedgedata; + ((oedgedata*)(iBrother.userdata))->_copy = this; +} + +WOEdge * WOEdge::dupplicate() +{ + WOEdge *clone = new WOEdge(*this); + return clone; +} + +Vec3r +WOEdge::getVec3r () +{ + return Vec3r(_pbVertex->GetVertex() - _paVertex->GetVertex()); +} + +WOEdge * WOEdge::twin () +{ + return GetOwner()->GetOtherOEdge(this); +} + +WOEdge * +WOEdge::getPrevOnFace() +{ + return _pbFace->GetPrevOEdge(this); +} + + /**********************************/ + /* */ + /* */ + /* WEdge */ + /* */ + /* */ + /**********************************/ + +WEdge::WEdge(WEdge& iBrother) +{ + _paOEdge = NULL; + _pbOEdge = NULL; + WOEdge *aoedge = iBrother.GetaOEdge(); + WOEdge *boedge = iBrother.GetbOEdge(); + userdata = NULL; + + if(NULL != aoedge) + //_paOEdge = new WOEdge(*aoedge); + _paOEdge = aoedge->dupplicate(); + if(NULL != boedge) + //_pbOEdge = new WOEdge(*boedge); + _pbOEdge = boedge->dupplicate(); + + _nOEdges = iBrother.GetNumberOfOEdges(); + _Id = iBrother.GetId(); + iBrother.userdata = new edgedata; + ((edgedata*)(iBrother.userdata))->_copy = this; +} + +WEdge * WEdge::dupplicate() +{ + WEdge *clone = new WEdge(*this); + return clone; +} + + /**********************************/ + /* */ + /* */ + /* WFace */ + /* */ + /* */ + /**********************************/ + + +WFace::WFace(WFace& iBrother) +{ + _OEdgeList = iBrother.GetEdgeList(); + _Normal = iBrother.GetNormal(); + _VerticesNormals = iBrother._VerticesNormals; + _VerticesTexCoords = iBrother._VerticesTexCoords; + _Id = iBrother.GetId(); + _MaterialIndex = iBrother._MaterialIndex; + userdata = NULL; + iBrother.userdata = new facedata; + ((facedata*)(iBrother.userdata))->_copy = this; +} + +WFace * WFace::dupplicate() +{ + WFace * clone = new WFace(*this); + return clone; +} + +const Material& WFace::material() { + return getShape()->material(_MaterialIndex); +} + +WOEdge * WFace::MakeEdge(WVertex *v1, WVertex *v2) +{ + // First check whether the same oriented edge already exists + // or not: + vector<WEdge *>& v1Edges = v1->GetEdges(); + for(vector<WEdge*>::iterator it1=v1Edges.begin(), end=v1Edges.end(); + it1!=end; + it1++) + { + + WEdge *we=(*it1); + + WOEdge *woea = we->GetaOEdge(); + + if((woea->GetaVertex() == v1) && (woea->GetbVertex() == v2)) + //if((*it1)->GetbVertex() == v2) + { + // The oriented edge already exists + cerr << "Warning: edge " << v1->GetId() << " - " << v2->GetId() << " appears twice, correcting" << endl; + // Adds the edge to the face + //AddEdge((*it1)->GetaOEdge()); + AddEdge(woea); + (*it1)->SetNumberOfOEdges((*it1)->GetNumberOfOEdges()+1); + //sets these vertices as border: + v1->SetBorder(true); + v2->SetBorder(true); + //return (*it1)->GetaOEdge(); + return woea; + } + + WOEdge *woeb = we->GetbOEdge(); + if((woeb != 0) && (woeb->GetaVertex() == v1) && (woeb->GetbVertex() == v2)) + + //if((*it1)->GetbVertex() == v2) + + { + // The oriented edge already exists + cerr << "Warning: edge " << v1->GetId() << " - " << v2->GetId() << " appears twice, correcting" << endl; + // Adds the edge to the face + //AddEdge((*it1)->GetaOEdge()); + AddEdge(woeb); + (*it1)->SetNumberOfOEdges((*it1)->GetNumberOfOEdges()+1); + //sets these vertices as border: + v1->SetBorder(true); + v2->SetBorder(true); + //return (*it1)->GetaOEdge(); + return woeb; + } + } + + // the oriented edge we're about to build + WOEdge *pOEdge = new WOEdge; + + WEdge * edge; // The edge containing the oriented edge. + + // checks whether this edge already exists or not + // If it exists, it points outward v2 + + bool exist = false; + WOEdge *pInvertEdge = NULL; // The inverted edge if it exists + vector<WEdge *>& v2Edges = v2->GetEdges(); + vector<WEdge *>::iterator it; + for(it=v2Edges.begin(); it!=v2Edges.end(); it++) + { + if((*it)->GetbVertex() == v1) + { + // The invert edge already exists + exist = true; + pInvertEdge = (*it)->GetaOEdge(); + break; + } + } + + //DEBUG: + + + if(true == exist) // The invert edge already exists + { + // Retrieves the corresponding edge + edge = pInvertEdge->GetOwner(); + + // Sets the a Face (retrieved from pInvertEdge + pOEdge->SetaFace(pInvertEdge->GetbFace()); + + // Updates the invert edge: + pInvertEdge->SetaFace(this); + } + else // The invert edge does not exist yet + { + // we must create a new edge + //edge = new WEdge; + edge = instanciateEdge(); + + // updates the a,b vertex edges list: + v1->AddEdge(edge); + v2->AddEdge(edge); + + } + + pOEdge->SetOwner(edge); + // Add the vertices: + pOEdge->SetaVertex(v1); + pOEdge->SetbVertex(v2); + + // Debug: + if(v1->GetId() == v2->GetId()) + cerr << "Warning: edge " << this << " null with vertex " << v1->GetId() << endl; + + edge->AddOEdge(pOEdge); + //edge->SetNumberOfOEdges(edge->GetNumberOfOEdges()+1); + + // Add this face (the b face) + pOEdge->SetbFace(this); + + // Adds the edge to the face + AddEdge(pOEdge); + + return pOEdge; +} + + +bool +WFace::getOppositeEdge (const WVertex *v, WOEdge* &e) +{ + if (_OEdgeList.size()!=3) return false; + + vector<WOEdge *>::iterator it; + e=NULL; + for(it=_OEdgeList.begin(); it!=_OEdgeList.end(); it++) + if ((*it)->GetaVertex()==v) e=*it; + if (!e) return false; + e=NULL; + for(it=_OEdgeList.begin(); it!=_OEdgeList.end(); it++) + if (((*it)->GetaVertex()!=v) && ((*it)->GetbVertex()!=v)) e=*it; + if (!e) return false; + else return true; +} + +real +WFace::getArea () +{ + vector<WOEdge *>::iterator it; + Vec3r origin=(*(_OEdgeList.begin()))->GetaVertex()->GetVertex(); + it=_OEdgeList.begin(); + real a=0; + for (it=it++; it!=_OEdgeList.end(); it++) { + Vec3r v1=Vec3r((*it)->GetaVertex()->GetVertex() - origin); + Vec3r v2=Vec3r((*it)->GetbVertex()->GetVertex() - origin); + a += (v1 ^ v2).norm() / 2.0; + } + return a; +} + + +WOEdge* +WFace::GetPrevOEdge(WOEdge* iOEdge) + { + vector<WOEdge*>::iterator woe,woend, woefirst; + woefirst = _OEdgeList.begin(); + woend=_OEdgeList.end(); + WOEdge *prev =*woefirst; + woe=woefirst; + woe++; + for(; + woe!=woend; + woe++) + { + if((*woe) == iOEdge) + return prev; + prev= *woe; + } + // We left the loop. That means that the first + // OEdge was the good one: + if((*woefirst)==iOEdge) + return prev; + + return NULL; + } + +WShape * WFace::getShape() +{ + return GetVertex(0)->shape(); +} + + /**********************************/ + /* */ + /* */ + /* WShape */ + /* */ + /* */ + /**********************************/ + + +LIB_WINGED_EDGE_EXPORT +unsigned WShape::_SceneCurrentId = 0; + +WShape * WShape::dupplicate() +{ + WShape *clone = new WShape(*this); + return clone; +} + +WShape::WShape(WShape& iBrother) +{ + _Id = iBrother.GetId(); + _Materials = iBrother._Materials; + _meanEdgeSize = iBrother._meanEdgeSize; + iBrother.bbox(_min, _max); + vector<WVertex*>& vertexList = iBrother.GetVertexList(); + vector<WVertex*>::iterator v=vertexList.begin(), vend=vertexList.end(); + for(; + v!=vend; + v++) + { + //WVertex *newVertex = new WVertex(*(*v)); + WVertex *newVertex = (*v)->dupplicate(); + + newVertex->SetShape(this); + AddVertex(newVertex); + } + + vector<WEdge*>& edgeList = iBrother.GetEdgeList(); + vector<WEdge*>::iterator e=edgeList.begin(), eend=edgeList.end(); + for(; + e!=eend; + e++) + { + //WEdge *newEdge = new WEdge(*(*e)); + WEdge *newEdge = (*e)->dupplicate(); + AddEdge(newEdge); + } + + vector<WFace*>& faceList = iBrother.GetFaceList(); + vector<WFace*>::iterator f=faceList.begin(), fend=faceList.end(); + for(; + f!=fend; + f++) + { + //WFace *newFace = new WFace(*(*f)); + WFace *newFace = (*f)->dupplicate(); + AddFace(newFace); + } + + // update all pointed addresses thanks to the newly created objects: + vend=_VertexList.end(); + for(v=_VertexList.begin(); + v!=vend; + v++) + { + const vector<WEdge*>& vedgeList = (*v)->GetEdges(); + vector<WEdge*> newvedgelist; + unsigned int i; + for(i=0; i<vedgeList.size(); i++) + { + WEdge *current = vedgeList[i]; + edgedata * currentvedata = (edgedata*)current->userdata; + newvedgelist.push_back(currentvedata->_copy); + } + (*v)->SetEdges(newvedgelist); + } + + eend = _EdgeList.end(); + for(e=_EdgeList.begin(); + e!=eend; + e++) + { + // update aOedge: + WOEdge *aoEdge = (*e)->GetaOEdge(); + aoEdge->SetaVertex(((vertexdata*)(aoEdge->GetaVertex()->userdata))->_copy); + aoEdge->SetbVertex(((vertexdata*)(aoEdge->GetbVertex()->userdata))->_copy); + if(NULL != aoEdge->GetaFace()) + aoEdge->SetaFace(((facedata*)(aoEdge->GetaFace()->userdata))->_copy); + aoEdge->SetbFace(((facedata*)(aoEdge->GetbFace()->userdata))->_copy); + aoEdge->SetOwner(((edgedata*)(aoEdge->GetOwner()->userdata))->_copy); + // update bOedge: + + WOEdge *boEdge = (*e)->GetbOEdge(); + if(boEdge != 0) + { + boEdge->SetaVertex(((vertexdata*)(boEdge->GetaVertex()->userdata))->_copy); + boEdge->SetbVertex(((vertexdata*)(boEdge->GetbVertex()->userdata))->_copy); + if(NULL != boEdge->GetaFace()) + boEdge->SetaFace(((facedata*)(boEdge->GetaFace()->userdata))->_copy); + boEdge->SetbFace(((facedata*)(boEdge->GetbFace()->userdata))->_copy); + boEdge->SetOwner(((edgedata*)(boEdge->GetOwner()->userdata))->_copy); + } + } + + fend = _FaceList.end(); + for(f=_FaceList.begin(); + f!=fend; + f++) + { + unsigned i; + const vector<WOEdge*>& oedgeList = (*f)->GetEdgeList(); + vector<WOEdge*> newoedgelist; + + unsigned n = oedgeList.size(); + for(i=0; i<n; i++) + { + WOEdge *current = oedgeList[i]; + oedgedata * currentoedata = (oedgedata*)current->userdata; + newoedgelist.push_back(currentoedata->_copy); + //oedgeList[i] = currentoedata->_copy; + //oedgeList[i] = ((oedgedata*)(oedgeList[i]->userdata))->_copy; + } + (*f)->SetEdgeList(newoedgelist); + } + + // Free all memory (arghh!) + // Vertex + vend = iBrother.GetVertexList().end(); + for(v=iBrother.GetVertexList().begin(); + v!=vend; + v++) + { + delete (vertexdata*)((*v)->userdata); + (*v)->userdata = NULL; + } + + // Edges and OEdges: + eend = iBrother.GetEdgeList().end(); + for(e=iBrother.GetEdgeList().begin(); + e!=eend; + e++) + { + delete (edgedata*)((*e)->userdata); + (*e)->userdata = NULL; + // OEdge a : + delete (oedgedata*)((*e)->GetaOEdge()->userdata); + (*e)->GetaOEdge()->userdata = NULL; + // OEdge b: + WOEdge* oedgeb = (*e)->GetbOEdge(); + if(NULL != oedgeb) + { + delete (oedgedata*)(oedgeb->userdata); + oedgeb->userdata = NULL; + } + } + // Faces + fend = iBrother.GetFaceList().end(); + for(f=iBrother.GetFaceList().begin(); + f!=fend; + f++) + { + delete (facedata*)((*f)->userdata); + (*f)->userdata = NULL; + } +} + +WFace* WShape::MakeFace(vector<WVertex*>& iVertexList, unsigned iMaterial) +{ + // allocate the new face + WFace *face = instanciateFace(); + + return MakeFace(iVertexList, iMaterial, face); +} + +WFace * WShape::MakeFace(vector<WVertex*>& iVertexList, vector<Vec3r>& iNormalsList, vector<Vec2r>& iTexCoordsList, unsigned iMaterial) +{ + // allocate the new face + WFace *face = MakeFace(iVertexList, iMaterial); + + if(0 == face) + + return 0; + + // set the list of per-vertex normals + face->SetNormalList(iNormalsList); + // set the list of per-vertex tex coords + face->SetTexCoordsList(iTexCoordsList); + + return face; +} + +WFace* WShape::MakeFace(vector<WVertex*>& iVertexList, unsigned iMaterial, WFace *face) +{ + + int id = _FaceList.size(); + + face->SetMaterialIndex(iMaterial); + + // Check whether we have a degenerated face: + + // LET'S HACK IT FOR THE TRIANGLE CASE: + + if(3 == iVertexList.size()) + + { + + if((iVertexList[0] == iVertexList[1]) + + || (iVertexList[0] == iVertexList[2]) + + || (iVertexList[2] == iVertexList[1])) + + { + + cerr << "Warning: degenerated triangle detected, correcting" << endl; + return 0; + + } + + } + // vertex pointers used to build each edge + vector<WVertex*>::iterator va, vb, it; + + va = iVertexList.begin(); + vb = va; + for(; va != iVertexList.end(); va = vb) + { + vb++; + // Adds va to the vertex list: + //face->AddVertex(*va); + + WOEdge * oedge; + if(*va == iVertexList.back()) + oedge = face->MakeEdge(*va, iVertexList.front()); //for the last (closing) edge + else + oedge = face->MakeEdge(*va, *vb); + + + if(oedge == 0) + return 0; + + + WEdge *edge = oedge->GetOwner(); + if(1 == edge->GetNumberOfOEdges()) + { + // means that we just created a new edge and that we must add it to the + // shape's edges list + edge->SetId(_EdgeList.size()); + AddEdge(edge); + // compute the mean edge value: + _meanEdgeSize += edge->GetaOEdge()->getVec3r().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); + AddFace(face); + + return face; +} diff --git a/source/blender/freestyle/intern/winged_edge/WEdge.h b/source/blender/freestyle/intern/winged_edge/WEdge.h new file mode 100755 index 00000000000..2369caf4566 --- /dev/null +++ b/source/blender/freestyle/intern/winged_edge/WEdge.h @@ -0,0 +1,952 @@ +// +// Filename : WEdge.h +// Author(s) : Stephane Grabli +// Purpose : Classes to define a Winged Edge data structure. +// Date of creation : 18/02/2002 +// +/////////////////////////////////////////////////////////////////////////////// + + +// +// 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 WEDGE_H +# define WEDGE_H + +# include <vector> +# include <iterator> +# include "../system/FreestyleConfig.h" +# include "../geometry/Geom.h" +# include "../scene_graph/Material.h" + +using namespace std; +using namespace Geometry; + + + /**********************************/ + /* */ + /* */ + /* WVertex */ + /* */ + /* */ + /**********************************/ + + +class WOEdge; +class WEdge; +class WShape; +class WFace; +class LIB_WINGED_EDGE_EXPORT WVertex +{ +protected: + int _Id; // an identificator + Vec3r _Vertex; + vector<WEdge*> _EdgeList; + WShape * _Shape; // the shape to which the vertex belongs + bool _Smooth; // flag to indicate whether the Vertex belongs to a smooth edge or not + int _Border; // 1 -> border, 0 -> no border, -1 -> not set + +public: + void * userdata; // designed to store specific user data + inline WVertex(const Vec3r &v) {_Id = 0; _Vertex = v; userdata = NULL; _Shape = NULL;_Smooth=true;_Border=-1;} + /*! Copy constructor */ + WVertex(WVertex& iBrother); + virtual WVertex * dupplicate(); + virtual ~WVertex() {} + + /*! accessors */ + inline Vec3r& GetVertex() {return _Vertex;} + inline vector<WEdge*>& GetEdges() {return _EdgeList;} + inline int GetId() {return _Id;} + inline WShape * shape() const {return _Shape;} + inline bool isSmooth() const {return _Smooth;} + bool isBoundary(); + + /*! modifiers */ + inline void SetVertex(const Vec3r& v) {_Vertex = v;} + inline void SetEdges(const vector<WEdge *>& iEdgeList) {_EdgeList = iEdgeList;} + inline void SetId(int id) {_Id = id;} + inline void SetShape(WShape *iShape) {_Shape = iShape;} + inline void SetSmooth(bool b) {_Smooth = b;} + inline void SetBorder(bool b) {if(b) _Border= 1; else _Border = 0;} + + /*! Adds an edge to the edges list */ + void AddEdge(WEdge *iEdge) ; + + virtual void ResetUserData() {userdata = 0;} + + + +public: + + + + /*! Iterator to iterate over a vertex incoming edges in the CCW order*/ +# if defined(__GNUC__) && (__GNUC__ < 3) + class incoming_edge_iterator : public input_iterator<WOEdge*,ptrdiff_t> +# else + class LIB_WINGED_EDGE_EXPORT incoming_edge_iterator : public iterator<input_iterator_tag, WOEdge*,ptrdiff_t> +# endif + { + private: + WVertex *_vertex; + // + WOEdge *_begin; + WOEdge *_current; + + public: +# if defined(__GNUC__) && (__GNUC__ < 3) + inline incoming_edge_iterator() : input_iterator<WOEdge*,ptrdiff_t>() {} +# else + inline incoming_edge_iterator() : iterator<input_iterator_tag, WOEdge*,ptrdiff_t>() {} +# endif + + protected: + friend class WVertex; + inline incoming_edge_iterator( + WVertex *iVertex, + WOEdge * iBegin, + WOEdge * iCurrent) +# if defined(__GNUC__) && (__GNUC__ < 3) + : input_iterator<WOEdge*,ptrdiff_t>() +# else + : iterator<input_iterator_tag, WOEdge*,ptrdiff_t>() +# endif + { + _vertex = iVertex; + _begin = iBegin; + _current = iCurrent; + } + + public: + inline incoming_edge_iterator(const incoming_edge_iterator& iBrother) +# if defined(__GNUC__) && (__GNUC__ < 3) + : input_iterator<WOEdge*,ptrdiff_t>(iBrother) +# else + : iterator<input_iterator_tag, WOEdge*,ptrdiff_t>(iBrother) +# endif + { + _vertex = iBrother._vertex; + _begin = iBrother._begin; + _current = iBrother._current; + } + + public: + // operators + virtual incoming_edge_iterator& operator++() // operator corresponding to ++i + { + increment(); + return *this; + } + virtual incoming_edge_iterator operator++(int) // opérateur correspondant à i++ + { // c.a.d qui renvoie la valeur *puis* incrémente. + incoming_edge_iterator tmp = *this; // C'est pour cela qu'on stocke la valeur + increment(); // dans un temporaire. + return tmp; + } + + // comparibility + virtual bool operator!=(const incoming_edge_iterator& b) const + { + return ((_current) != (b._current)); + } + + virtual bool operator==(const incoming_edge_iterator& b) const + { + return ((_current)== (b._current)); + } + + // dereferencing + virtual WOEdge* operator*(); + //virtual WOEdge** operator->(); + protected: + virtual void increment(); + }; + + + /*! Iterator to iterate over a vertex faces in the CCW order */ +# if defined(__GNUC__) && (__GNUC__ < 3) + class face_iterator : public input_iterator<WFace*,ptrdiff_t> +# else + class LIB_WINGED_EDGE_EXPORT face_iterator : public iterator<input_iterator_tag, WFace*,ptrdiff_t> +# endif + { + private: + incoming_edge_iterator _edge_it; + + public: +# if defined(__GNUC__) && (__GNUC__ < 3) + inline face_iterator() : input_iterator<WFace*,ptrdiff_t>() {} +# else + inline face_iterator() : iterator<input_iterator_tag, WFace*,ptrdiff_t>() {} +# endif + + protected: + friend class WVertex; + inline face_iterator( + incoming_edge_iterator it) +# if defined(__GNUC__) && (__GNUC__ < 3) + : input_iterator<WFace*,ptrdiff_t>() +# else + : iterator<input_iterator_tag, WFace*,ptrdiff_t>() +# endif + { + _edge_it = it; + } + + public: + inline face_iterator(const face_iterator& iBrother) +# if defined(__GNUC__) && (__GNUC__ < 3) + : input_iterator<WFace*,ptrdiff_t>(iBrother) +# else + : iterator<input_iterator_tag, WFace*,ptrdiff_t>(iBrother) +# endif + { + _edge_it = iBrother._edge_it; + } + + public: + // operators + virtual face_iterator& operator++() // operator corresponding to ++i + { + increment(); + return *this; + } + virtual face_iterator operator++(int) // opérateur correspondant à i++ + { // c.a.d qui renvoie la valeur *puis* incrémente. + face_iterator tmp = *this; // C'est pour cela qu'on stocke la valeur + increment(); // dans un temporaire. + return tmp; + } + + // comparibility + virtual bool operator!=(const face_iterator& b) const + { + return ((_edge_it) != (b._edge_it)); + } + + virtual bool operator==(const face_iterator& b) const + { + return ((_edge_it)== (b._edge_it)); + } + + // dereferencing + virtual WFace* operator*(); + //virtual WOEdge** operator->(); + protected: + inline void increment(){ + ++_edge_it; + } + }; + +public: + /*! iterators access */ + virtual incoming_edge_iterator incoming_edges_begin(); + virtual incoming_edge_iterator incoming_edges_end() ; + + virtual face_iterator faces_begin() { + return face_iterator(incoming_edges_begin()); + } + virtual face_iterator faces_end() { + return face_iterator(incoming_edges_end()); + } +}; + + + /**********************************/ + /* */ + /* */ + /* WOEdge */ + /* */ + /* */ + /**********************************/ +class WFace; +class WEdge; + +class LIB_WINGED_EDGE_EXPORT WOEdge +{ +protected: + // WOEdge *_paCWEdge; // edge reached when traveling clockwise on aFace from the edge + // WOEdge *_pbCWEdge; // edge reached when traveling clockwise on bFace from the edge + // WOEdge *_paCCWEdge; // edge reached when traveling counterclockwise on aFace from the edge + // WOEdge *_pbCCWEdge; // edge reached when traveling counterclockwise on bFace from the edge + WVertex *_paVertex; // starting vertex + WVertex *_pbVertex; // ending vertex + WFace *_paFace; // when following the edge, face on the right + WFace *_pbFace; // when following the edge, face on the left + WEdge *_pOwner; // Edge + +public: + void *userdata; + inline WOEdge() + { + // _paCWEdge = NULL; + // _pbCWEdge = NULL; + // _paCCWEdge = NULL; + // _pbCCWEdge = NULL; + _paVertex = NULL; + _pbVertex = NULL; + _paFace = NULL; + _pbFace = NULL; + _pOwner = NULL; + userdata = NULL; + } + + /*! copy constructor */ + WOEdge(WOEdge& iBrother); + virtual WOEdge * dupplicate(); + + /*! accessors */ + // inline WOEdge *GetaCWEdge() {return _paCWEdge;} + // inline WOEdge *GetbCWEdge() {return _pbCWEdge;} + // inline WOEdge *GetaCCWEdge() {return _paCCWEdge;} + // inline WOEdge *GetbCCWEdge() {return _pbCCWEdge;} + inline WVertex *GetaVertex() {return _paVertex;} + inline WVertex *GetbVertex() {return _pbVertex;} + inline WFace *GetaFace() {return _paFace;} + inline WFace *GetbFace() {return _pbFace;} + inline WEdge *GetOwner() {return _pOwner;} + + + /*! modifiers */ + // inline void SetaCWEdge(WOEdge *pe) {_paCWEdge = pe;} + // 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 SetOwner(WEdge *pe) {_pOwner = pe;} + + /*! Retrieves the list of edges in CW order */ + inline void RetrieveCWOrderedEdges(vector<WEdge*>& oEdges); + /*! returns the vector between the two vertices */ + Vec3r getVec3r (); + WOEdge * twin (); + WOEdge * getPrevOnFace(); + virtual void ResetUserData() {userdata = 0;} +}; + + + /**********************************/ + /* */ + /* */ + /* WEdge */ + /* */ + /* */ + /**********************************/ + +class LIB_WINGED_EDGE_EXPORT WEdge +{ +protected: + WOEdge *_paOEdge; // first oriented edge + WOEdge *_pbOEdge; // second oriented edge + int _nOEdges; // number of oriented edges associated with this edge. (1 means border edge) + int _Id; // Identifier for the edge + +public: + void * userdata; // designed to store specific user data + inline WEdge() + { + _paOEdge = NULL; + _pbOEdge = NULL; + _nOEdges = 0; + userdata = NULL; + } + + inline WEdge(WOEdge *iOEdge) + { + _paOEdge = iOEdge; + _pbOEdge = NULL; + _nOEdges = 1; + userdata = NULL; + } + + inline WEdge(WOEdge *iaOEdge, WOEdge *ibOEdge) + { + _paOEdge = iaOEdge; + _pbOEdge = ibOEdge; + _nOEdges = 2; + userdata = NULL; + } + + /*! Copy constructor */ + WEdge(WEdge& iBrother); + virtual WEdge * dupplicate(); + + virtual ~WEdge() + { + if(NULL != _paOEdge) + { + delete _paOEdge; + _paOEdge = NULL; + } + + if(NULL != _pbOEdge) + { + delete _pbOEdge; + _pbOEdge = NULL; + } + } + + /*! checks whether two WEdge have a common vertex. + * Returns a pointer on the common vertex if it exists, + * NULL otherwise. + */ + static inline WVertex* CommonVertex(WEdge *iEdge1, WEdge* iEdge2) + { + if((NULL == iEdge1) || (NULL == iEdge2)) + return NULL; + + WVertex *wv1 = iEdge1->GetaOEdge()->GetaVertex(); + WVertex *wv2 = iEdge1->GetaOEdge()->GetbVertex(); + WVertex *wv3 = iEdge2->GetaOEdge()->GetaVertex(); + WVertex *wv4 = iEdge2->GetaOEdge()->GetbVertex(); + + if((wv1 == wv3) || (wv1 == wv4)) + { + return wv1; + } + else if((wv2 == wv3) || (wv2 == wv4)) + { + return wv2; + } + + return NULL; + } + /*! accessors */ + inline WOEdge * GetaOEdge() {return _paOEdge;} + inline WOEdge * GetbOEdge() {return _pbOEdge;} + inline int GetNumberOfOEdges() {return _nOEdges;} + inline int GetId() {return _Id;} + inline WVertex * GetaVertex() {return _paOEdge->GetaVertex();} + inline WVertex * GetbVertex() {return _paOEdge->GetbVertex();} + inline WFace * GetaFace() {return _paOEdge->GetaFace();} + inline WFace * GetbFace() {return _paOEdge->GetbFace();} + inline WOEdge* GetOtherOEdge(WOEdge* iOEdge) + { + if(iOEdge == _paOEdge) + return _pbOEdge; + else + return _paOEdge; + } + + /*! modifiers */ + inline void SetaOEdge(WOEdge *iEdge) {_paOEdge = iEdge;} + inline void SetbOEdge(WOEdge *iEdge) {_pbOEdge = iEdge;} + inline void AddOEdge(WOEdge *iEdge) + { + if(NULL == _paOEdge) + { + _paOEdge = iEdge; + _nOEdges++; + return; + } + if(NULL == _pbOEdge) + { + _pbOEdge = iEdge; + _nOEdges++; + return; + } + } + inline void SetNumberOfOEdges(int n) {_nOEdges = n;} + inline void SetId(int id) {_Id = id;} + virtual void ResetUserData() {userdata = 0;} +}; + + /**********************************/ + /* */ + /* */ + /* WFace */ + /* */ + /* */ + /**********************************/ + + +class LIB_WINGED_EDGE_EXPORT WFace +{ +protected: + vector<WOEdge *> _OEdgeList; // list of oriented edges of bording the face + Vec3r _Normal; // normal to the face + vector<Vec3r> _VerticesNormals; // in case there is a normal per vertex. + // The normal number i corresponds to the + // aVertex of the oedge number i, for that face + vector<Vec2r> _VerticesTexCoords; + + int _Id; + unsigned _MaterialIndex; + +public: + void *userdata; + inline WFace() {userdata = NULL;_MaterialIndex = 0;} + /*! copy constructor */ + WFace(WFace& iBrother); + virtual WFace * dupplicate(); + virtual ~WFace() {} + + /*! accessors */ + inline const vector<WOEdge*>& GetEdgeList() {return _OEdgeList;} + inline WOEdge * GetOEdge(int i) {return _OEdgeList[i];} + inline Vec3r& GetNormal() {return _Normal;} + inline int GetId() {return _Id;} + inline unsigned materialIndex() const {return _MaterialIndex;} + const Material& material() ; + + /*! The vertex of index i corresponds to the a vertex + * of the edge of index i + */ + inline WVertex* GetVertex(unsigned int index) + { + // if(index >= _OEdgeList.size()) + // return NULL; + return _OEdgeList[index]->GetaVertex(); + } + /*! returns the index at which iVertex is stored in the + * array. + * returns -1 if iVertex doesn't belong to the face. + */ + inline int GetIndex(WVertex *iVertex){ + int index = 0; + for(vector<WOEdge*>::iterator woe=_OEdgeList.begin(), woend=_OEdgeList.end(); + woe!=woend; + woe++){ + if((*woe)->GetaVertex() == iVertex) + return index; + ++index; + } + return -1; + } + inline void RetrieveVertexList(vector<WVertex*>& oVertices) + { + for(vector<WOEdge*>::iterator woe=_OEdgeList.begin(), woend=_OEdgeList.end(); + woe!=woend; + woe++) + { + oVertices.push_back((*woe)->GetaVertex()); + } + } + inline void RetrieveBorderFaces(vector<const WFace*>& oWFaces) + { + for(vector<WOEdge*>::iterator woe=_OEdgeList.begin(), woend=_OEdgeList.end(); + woe!=woend; + woe++) + { + WFace *af; + if(NULL != (af = (*woe)->GetaFace())) + oWFaces.push_back(af); + } + } + inline WFace * GetBordingFace(int index) + { + // if(index >= _OEdgeList.size()) + // return 0; + return _OEdgeList[index]->GetaFace(); + } + inline WFace * GetBordingFace(WOEdge *iOEdge) + { + return iOEdge->GetaFace(); + } + inline vector<Vec3r>& GetPerVertexNormals() + { + return _VerticesNormals; + } + inline vector<Vec2r>& GetPerVertexTexCoords() + { + return _VerticesTexCoords; + } + /*! Returns the normal of the vertex of index index */ + inline Vec3r& GetVertexNormal(int index) + { + return _VerticesNormals[index]; + } + /*! Returns the tex coords of the vertex of index index */ + inline Vec2r& GetVertexTexCoords(int index) + { + return _VerticesTexCoords[index]; + } + /*! Returns the normal of the vertex iVertex for that face */ + inline Vec3r& GetVertexNormal(WVertex *iVertex) + { + int i = 0; + int index = 0; + for(vector<WOEdge*>::const_iterator woe=_OEdgeList.begin(), woend=_OEdgeList.end(); + woe!=woend; + woe++) + { + if((*woe)->GetaVertex() == iVertex) + { + index = i; + break; + } + ++i; + } + + return _VerticesNormals[index]; + } + inline WOEdge* GetNextOEdge(WOEdge* iOEdge) + { + bool found = false; + vector<WOEdge*>::iterator woe,woend, woefirst; + woefirst = _OEdgeList.begin(); + for(woe=woefirst,woend=_OEdgeList.end(); + woe!=woend; + woe++) + { + if(true == found) + return (*woe); + + if((*woe) == iOEdge) + { + found = true; + } + } + + // We left the loop. That means that the first + // OEdge was the good one: + if(found) + return (*woefirst); + + return NULL; + } + WOEdge* GetPrevOEdge(WOEdge* iOEdge); + + inline int numberOfEdges() const { return _OEdgeList.size();} + inline int numberOfVertices() const { return _OEdgeList.size();} + /*! Returns true if the face has one ot its edge which is a border + * edge + */ + inline bool isBorder() const + { + for(vector<WOEdge*>::const_iterator woe=_OEdgeList.begin(), woeend=_OEdgeList.end(); + woe!=woeend; + ++woe) + { + if((*woe)->GetOwner()->GetbOEdge() == 0) + return true; + } + return false; + } + /*! modifiers */ + inline void SetEdgeList(const vector<WOEdge*>& iEdgeList) {_OEdgeList = iEdgeList;} + inline void SetNormal(const Vec3r& iNormal) {_Normal = iNormal;} + inline void SetNormalList(const vector<Vec3r>& iNormalsList) {_VerticesNormals = iNormalsList;} + inline void SetTexCoordsList(const vector<Vec2r>& iTexCoordsList) {_VerticesTexCoords = iTexCoordsList;} + inline void SetId(int id) {_Id = id;} + inline void SetMaterialIndex(unsigned iMaterialIndex) {_MaterialIndex = iMaterialIndex;} + + /*! designed to build a specialized WEdge + * for use in MakeEdge + */ + virtual WEdge * instanciateEdge() const {return new WEdge;} + + /*! Builds an oriented edge + * Returns the built edge. + * v1, v2 + * Vertices at the edge's extremities + * The edge is oriented from v1 to v2. + */ + virtual WOEdge * MakeEdge(WVertex *v1, WVertex *v2); + + /*! Adds an edge to the edges list */ + inline void AddEdge(WOEdge *iEdge) {_OEdgeList.push_back(iEdge);} + + /*! For triangles, returns the edge opposite to the vertex in e. + returns flase if the face is not a triangle or if the vertex is not found*/ + bool getOppositeEdge (const WVertex *v, WOEdge* &e); + + /*! compute the area of the face */ + real getArea (); + + WShape * getShape() ; + virtual void ResetUserData() {userdata = 0;} +}; + + + /**********************************/ + /* */ + /* */ + /* WShape */ + /* */ + /* */ + /**********************************/ + + +class LIB_WINGED_EDGE_EXPORT WShape +{ +protected: + vector<WVertex*> _VertexList; + vector<WEdge*> _EdgeList; + vector<WFace*> _FaceList; + int _Id; + static unsigned _SceneCurrentId; + Vec3r _min; + Vec3r _max; + vector<Material> _Materials; + real _meanEdgeSize; + +public: + inline WShape() {_meanEdgeSize = 0;_Id = _SceneCurrentId; _SceneCurrentId++;} + /*! copy constructor */ + WShape(WShape& iBrother); + virtual WShape * dupplicate(); + virtual ~WShape() + { + if(_EdgeList.size() != 0) + { + vector<WEdge *>::iterator e; + for(e=_EdgeList.begin(); e!=_EdgeList.end(); e++) + { + delete (*e); + } + _EdgeList.clear(); + } + + if(_VertexList.size() != 0) + { + vector<WVertex *>::iterator v; + for(v=_VertexList.begin(); v!=_VertexList.end(); v++) + { + delete (*v); + } + _VertexList.clear(); + } + + if(_FaceList.size() != 0) + { + vector<WFace *>::iterator f; + for(f=_FaceList.begin(); f!=_FaceList.end(); f++) + { + delete (*f); + } + _FaceList.clear(); + } + } + + /*! accessors */ + inline vector<WEdge *>& GetEdgeList() {return _EdgeList;} + inline vector<WVertex*>& GetVertexList() {return _VertexList;} + inline vector<WFace*>& GetFaceList() {return _FaceList;} + inline unsigned GetId() {return _Id;} + inline void bbox(Vec3r& min, Vec3r& max) {min=_min; max=_max;} + inline const Material& material(unsigned i) const {return _Materials[i];} + inline const vector<Material>& materials() const {return _Materials;} + inline const real getMeanEdgeSize() const {return _meanEdgeSize;} + /*! modifiers */ + static inline void SetCurrentId(const unsigned id) { _SceneCurrentId = id; } + inline void SetEdgeList(const vector<WEdge*>& iEdgeList) {_EdgeList = iEdgeList;} + inline void SetVertexList(const vector<WVertex*>& iVertexList) {_VertexList = iVertexList;} + inline void SetFaceList(const vector<WFace*>& iFaceList) {_FaceList = iFaceList;} + inline void SetId(int id) {_Id = id;} + inline void SetBBox(const Vec3r& min, const Vec3r& max) {_min = min; _max=max;} + inline void SetMaterial(const Material& material, unsigned i) {_Materials[i]=material;} + inline void SetMaterials(const vector<Material>& iMaterials) {_Materials = iMaterials;} + + /*! designed to build a specialized WFace + * for use in MakeFace + */ + virtual WFace * instanciateFace() const {return new WFace;} + + /*! adds a new face to the shape + * returns the built face. + * iVertexList + * List of face's vertices. These vertices are + * not added to the WShape vertex list; they are + * supposed to be already stored when calling MakeFace. + * The order in which the vertices are stored in the list + * determines the face's edges orientation and (so) the + * face orientation. + * iMaterialIndex + * The material index for this face + */ + virtual WFace * MakeFace(vector<WVertex*>& iVertexList, unsigned iMaterialIndex); + + /*! adds a new face to the shape. The difference with + * the previous method is that this one is designed + * to build a WingedEdge structure for which there are + * per vertex normals, opposed to per face normals. + * returns the built face. + * iVertexList + * List of face's vertices. These vertices are + * not added to the WShape vertex list; they are + * supposed to be already stored when calling MakeFace. + * The order in which the vertices are stored in the list + * determines the face's edges orientation and (so) the + * face orientation. + * iMaterialIndex + * The materialIndex for this face + * iNormalsList + * The list of normals, iNormalsList[i] corresponding to the + * normal of the vertex iVertexList[i] for that face. + * iTexCoordsList + * The list of tex coords, iTexCoordsList[i] corresponding to the + * normal of the vertex iVertexList[i] for that face. + */ + virtual WFace * MakeFace(vector<WVertex*>& iVertexList, vector<Vec3r>& iNormalsList, vector<Vec2r>& iTexCoordsList, unsigned iMaterialIndex); + + inline void AddEdge(WEdge *iEdge) {_EdgeList.push_back(iEdge);} + inline void AddFace(WFace* iFace) {_FaceList.push_back(iFace);} + inline void AddVertex(WVertex *iVertex) {iVertex->SetShape(this); _VertexList.push_back(iVertex);} + + inline void ResetUserData() + { + for(vector<WVertex*>::iterator v=_VertexList.begin(),vend=_VertexList.end(); + v!=vend; + v++) + { + (*v)->ResetUserData(); + } + + for(vector<WEdge*>::iterator e=_EdgeList.begin(),eend=_EdgeList.end(); + e!=eend; + e++) + { + (*e)->ResetUserData(); + // manages WOEdge: + WOEdge *oe = (*e)->GetaOEdge(); + if(oe != NULL) + oe->ResetUserData(); + oe = (*e)->GetbOEdge(); + if(oe != NULL) + oe->ResetUserData(); + } + + for(vector<WFace*>::iterator f=_FaceList.begin(),fend=_FaceList.end(); + f!=fend; + f++) + { + (*f)->ResetUserData(); + } + + } + + inline void ComputeBBox() + { + _min = _VertexList[0]->GetVertex(); + _max = _VertexList[0]->GetVertex(); + + Vec3r v; + for(vector<WVertex*>::iterator wv=_VertexList.begin(), wvend=_VertexList.end(); + wv!=wvend; + wv++) + { + for(unsigned int i=0; i<3; i++) + { + v = (*wv)->GetVertex(); + if(v[i] < _min[i]) + _min[i] = v[i]; + if(v[i] > _max[i]) + _max[i] = v[i]; + } + } + } + + inline real ComputeMeanEdgeSize(){ + _meanEdgeSize = _meanEdgeSize/(_EdgeList.size()); + return _meanEdgeSize; + } + +protected: + /*! Builds the face passed as argument (which as already been allocated) + * iVertexList + * List of face's vertices. These vertices are + * not added to the WShape vertex list; they are + * supposed to be already stored when calling MakeFace. + * The order in which the vertices are stored in the list + * determines the face's edges orientation and (so) the + * face orientation. + * iMaterialIndex + * The material index for this face + * face + * The Face that is filled in + */ + virtual WFace * MakeFace(vector<WVertex*>& iVertexList, unsigned iMaterialIndex, WFace *face); +}; + + + /**********************************/ + /* */ + /* */ + /* WingedEdge */ + /* */ + /* */ + /**********************************/ + +class WingedEdge { + + public: + + WingedEdge() {} + + ~WingedEdge() { + clear(); + } + + void clear() { + for (vector<WShape*>::iterator it = _wshapes.begin(); + it != _wshapes.end(); + it++) + delete *it; + _wshapes.clear(); + } + + void addWShape(WShape* wshape) { + _wshapes.push_back(wshape); + } + + vector<WShape*>& getWShapes() { + return _wshapes; + } + + private: + + vector<WShape*> _wshapes; +}; + + + +/* + + ############################################# + ############################################# + ############################################# + ###### ###### + ###### I M P L E M E N T A T I O N ###### + ###### ###### + ############################################# + ############################################# + ############################################# + +*/ +/* for inline functions */ +void WOEdge::RetrieveCWOrderedEdges(vector<WEdge*>& oEdges) +{ + + WOEdge *currentOEdge = this; + do + { + WOEdge* nextOEdge = currentOEdge->GetbFace()->GetNextOEdge(currentOEdge); + oEdges.push_back(nextOEdge->GetOwner()); + currentOEdge = nextOEdge->GetOwner()->GetOtherOEdge(nextOEdge); + + } while((currentOEdge != NULL) && (currentOEdge->GetOwner() != GetOwner())); +} + +#endif // WEDGE_H diff --git a/source/blender/freestyle/intern/winged_edge/WFillGrid.cpp b/source/blender/freestyle/intern/winged_edge/WFillGrid.cpp new file mode 100755 index 00000000000..7d0a2d3c561 --- /dev/null +++ b/source/blender/freestyle/intern/winged_edge/WFillGrid.cpp @@ -0,0 +1,60 @@ + +// +// 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 "WEdge.h" +#include "WFillGrid.h" + +void WFillGrid::fillGrid() { + if (!_winged_edge || !_grid) + return; + + vector<WShape*> wshapes = _winged_edge->getWShapes(); + vector<WVertex*> fvertices; + vector<Vec3r> vectors; + vector<WFace*> faces; + + for (vector<WShape*>::const_iterator it = wshapes.begin(); + it != wshapes.end(); + it++) { + faces = (*it)->GetFaceList(); + + for (vector<WFace*>::const_iterator f = faces.begin(); + f != faces.end(); + f++) { + (*f)->RetrieveVertexList(fvertices); + + for (vector<WVertex*>::const_iterator wv = fvertices.begin(); + wv != fvertices.end(); + wv++) + vectors.push_back(Vec3r((*wv)->GetVertex())); + + // occluder will be deleted by the grid + Polygon3r *occluder = + new Polygon3r(vectors, (*f)->GetNormal()); + occluder->setId(_polygon_id++); + occluder->userdata = (void*)(*f); + _grid->insertOccluder(occluder); + vectors.clear(); + fvertices.clear(); + } + faces.clear(); + } +} diff --git a/source/blender/freestyle/intern/winged_edge/WFillGrid.h b/source/blender/freestyle/intern/winged_edge/WFillGrid.h new file mode 100755 index 00000000000..2ebbc2f359a --- /dev/null +++ b/source/blender/freestyle/intern/winged_edge/WFillGrid.h @@ -0,0 +1,80 @@ +// +// Filename : WFillGrid.h +// Author(s) : Stephane Grabli +// Emmanuel Turquin +// Purpose : Class to fill in a grid from a SceneGraph +// (uses only the WingedEdge structures) +// Date of creation : 03/05/2003 +// +/////////////////////////////////////////////////////////////////////////////// + + +// +// 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 W_FILL_GRID_H +# define W_FILL_GRID_H + +# include "../geometry/Grid.h" +# include "../geometry/Polygon.h" +# include "WEdge.h" + +class LIB_WINGED_EDGE_EXPORT WFillGrid +{ +public: + + inline WFillGrid(Grid* grid = 0, WingedEdge* winged_edge = 0) { + _winged_edge = winged_edge; + _grid = grid; + _polygon_id = 0; + } + + virtual ~WFillGrid() {} + + void fillGrid(); + + /*! Accessors */ + WingedEdge* getWingedEdge() { + return _winged_edge; + } + + Grid* getGrid() { + return _grid; + } + + /*! Modifiers */ + void setWingedEdge(WingedEdge* winged_edge) { + if (winged_edge) + _winged_edge = winged_edge; + } + + void setGrid(Grid* grid) { + if (grid) + _grid = grid; + } + +private: + + Grid* _grid; + WingedEdge* _winged_edge; + unsigned _polygon_id; +}; + +#endif // WS_FILL_GRID_H diff --git a/source/blender/freestyle/intern/winged_edge/WSFillGrid.cpp b/source/blender/freestyle/intern/winged_edge/WSFillGrid.cpp new file mode 100755 index 00000000000..cf3734b488e --- /dev/null +++ b/source/blender/freestyle/intern/winged_edge/WSFillGrid.cpp @@ -0,0 +1,60 @@ + +// +// 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 "WSEdge.h" +#include "WSFillGrid.h" + +void WSFillGrid::fillGrid() { + if (!_winged_edge || !_grid) + return; + + vector<WShape*> wshapes = _winged_edge->getWShapes(); + vector<WVertex*> fvertices; + vector<Vec3r> vectors; + vector<WFace*> faces; + + for (vector<WShape*>::const_iterator it = wshapes.begin(); + it != wshapes.end(); + it++) { + faces = (*it)->GetFaceList(); + + for (vector<WFace*>::const_iterator f = faces.begin(); + f != faces.end(); + f++) { + (*f)->RetrieveVertexList(fvertices); + + for (vector<WVertex*>::const_iterator wv = fvertices.begin(); + wv != fvertices.end(); + wv++) + vectors.push_back(Vec3r((*wv)->GetVertex())); + + // occluder will be deleted by the grid + Polygon3r *occluder = + new Polygon3r(vectors, (*f)->GetNormal()); + occluder->setId(_polygon_id++); + occluder->userdata = (void*)(*f); + _grid->insertOccluder(occluder); + vectors.clear(); + fvertices.clear(); + } + faces.clear(); + } +} diff --git a/source/blender/freestyle/intern/winged_edge/WSFillGrid.h b/source/blender/freestyle/intern/winged_edge/WSFillGrid.h new file mode 100755 index 00000000000..976fdca8e46 --- /dev/null +++ b/source/blender/freestyle/intern/winged_edge/WSFillGrid.h @@ -0,0 +1,79 @@ +// +// Filename : WSFillGrid.h +// Author(s) : Stephane Grabli +// Purpose : Class to fill in a grid from a SceneGraph +// (uses only the WingedEdge structures) +// Date of creation : 03/05/2003 +// +/////////////////////////////////////////////////////////////////////////////// + + +// +// 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 WS_FILL_GRID_H +# define WS_FILL_GRID_H + +# include "Grid.h" +# include "Polygon.h" +# include "WEdge.h" + +class LIB_WINGED_EDGE_EXPORT WSFillGrid +{ +public: + + inline WSFillGrid(Grid* grid = 0, WingedEdge* winged_edge = 0) { + _winged_edge = winged_edge; + _grid = grid; + _polygon_id = 0; + } + + virtual ~WSFillGrid() {} + + void fillGrid(); + + /*! Accessors */ + WingedEdge* getWingedEdge() { + return _winged_edge; + } + + Grid* getGrid() { + return _grid; + } + + /*! Modifiers */ + void setWingedEdge(WingedEdge* winged_edge) { + if (winged_edge) + _winged_edge = winged_edge; + } + + void setGrid(Grid* grid) { + if (grid) + _grid = grid; + } + +private: + + Grid* _grid; + WingedEdge* _winged_edge; + unsigned _polygon_id; +}; + +#endif // WS_FILL_GRID_H diff --git a/source/blender/freestyle/intern/winged_edge/WXEdge.cpp b/source/blender/freestyle/intern/winged_edge/WXEdge.cpp new file mode 100755 index 00000000000..115a4f61789 --- /dev/null +++ b/source/blender/freestyle/intern/winged_edge/WXEdge.cpp @@ -0,0 +1,296 @@ +// +// 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 "WXEdge.h" + + /**********************************/ + /* */ + /* */ + /* WXFace */ + /* */ + /* */ + /**********************************/ + +unsigned int WXFaceLayer::Get0VertexIndex() const { + int i = 0; + int nEdges = _pWXFace->numberOfEdges(); + for(i=0; i<nEdges; ++i){ + if(_DotP[i] == 0){ + return i; + } + } + return -1; +} +unsigned int WXFaceLayer::GetSmoothEdgeIndex() const{ + int i = 0; + int nEdges = _pWXFace->numberOfEdges(); + for(i=0; i<nEdges; ++i){ + if((_DotP[i] == 0) && (_DotP[(i+1)%nEdges] == 0)){ + return i; + } + } + return -1; +} + +void WXFaceLayer::RetrieveCuspEdgesIndices(vector<int>& oCuspEdges){ + int i = 0; + int nEdges = _pWXFace->numberOfEdges(); + for(i=0; i<nEdges; ++i){ + if(_DotP[i]*_DotP[(i+1)%nEdges] < 0){ + // we got one + oCuspEdges.push_back(i); + } + } +} + +WXSmoothEdge* WXFaceLayer::BuildSmoothEdge(){ + // if the smooth edge has already been + // built: exit + if(0 != _pSmoothEdge) + return _pSmoothEdge; + real ta, tb; + WOEdge *woea(0), *woeb(0); + bool ok = false; + vector<int> cuspEdgesIndices; + int indexStart, indexEnd; + unsigned nedges = _pWXFace->numberOfEdges(); + if(_nNullDotP == nedges){ + _pSmoothEdge = 0; + return _pSmoothEdge; + } + if((_nPosDotP != 0) && (_nPosDotP != _DotP.size()) && (_nNullDotP == 0)){ + // that means that we have a smooth edge that starts from + // an edge and ends at an edge + //----------------------------- + // We retrieve the 2 edges for which we have + // opposite signs for each extremity + RetrieveCuspEdgesIndices(cuspEdgesIndices); + if(cuspEdgesIndices.size() != 2) // we necessarly have 2 cusp edges + return 0; + + // let us determine which cusp edge corresponds to the starting: + // We can do that because we defined that + // a silhouette edge had the back facing part on its right. + // So if the WOEdge woea is such that woea[0].dotp > 0 and + // woea[1].dotp < 0, it is the starting edge. + //------------------------------------------- + + if(_DotP[cuspEdgesIndices[0]] > 0){ + woea = _pWXFace->GetOEdge(cuspEdgesIndices[0]); + woeb = _pWXFace->GetOEdge(cuspEdgesIndices[1]); + indexStart = cuspEdgesIndices[0]; + indexEnd = cuspEdgesIndices[1]; + }else{ + woea = _pWXFace->GetOEdge(cuspEdgesIndices[1]); + woeb = _pWXFace->GetOEdge(cuspEdgesIndices[0]); + indexStart = cuspEdgesIndices[1]; + indexEnd = cuspEdgesIndices[0]; + } + + // Compute the interpolation: + ta = _DotP[indexStart]/(_DotP[indexStart]-_DotP[(indexStart+1)%nedges]); + tb = _DotP[indexEnd]/(_DotP[indexEnd]-_DotP[(indexEnd+1)%nedges]); + ok = true; + }else if(_nNullDotP == 1){ + // that means that we have exactly one of the + // 2 extremities of our silhouette edge is + // a vertex of the mesh + if((_nPosDotP == 2) || (_nPosDotP == 0)){ + _pSmoothEdge = 0; + return _pSmoothEdge; + } + RetrieveCuspEdgesIndices(cuspEdgesIndices); + // We should have only one EdgeCusp: + if(cuspEdgesIndices.size() != 1){ + cout << "Warning in BuildSmoothEdge: weird WXFace configuration" << endl; + _pSmoothEdge = 0; + return 0; + } + unsigned index0 = Get0VertexIndex(); // retrieve the 0 vertex index + unsigned nedges = _pWXFace->numberOfEdges(); + if(_DotP[cuspEdgesIndices[0]] > 0){ + woea = _pWXFace->GetOEdge(cuspEdgesIndices[0]); + woeb = _pWXFace->GetOEdge(index0); + indexStart = cuspEdgesIndices[0]; + ta = _DotP[indexStart]/(_DotP[indexStart]-_DotP[(indexStart+1)%nedges]); + tb = 0.0; + }else{ + woea = _pWXFace->GetOEdge(index0); + woeb = _pWXFace->GetOEdge(cuspEdgesIndices[0]); + indexEnd = cuspEdgesIndices[0]; + ta = 0.0; + tb = _DotP[indexEnd]/(_DotP[indexEnd]-_DotP[(indexEnd+1)%nedges]); + } + ok = true; + }else if(_nNullDotP == 2){ + // that means that the silhouette edge + // is an edge of the mesh + int index = GetSmoothEdgeIndex(); + if(!_pWXFace->front()) {// is it in the right order ? + // the order of the WOEdge index is wrong + woea = _pWXFace->GetOEdge((index+1)%nedges); + woeb = _pWXFace->GetOEdge((index-1)%nedges); + ta = 0; + tb = 1; + ok = true; + }else{ + // here it's not good, our edge is a single point -> skip that face + ok = false; + // the order of the WOEdge index is good + // woea = _pWXFace->GetOEdge((index-1)%nedges); + // woeb = _pWXFace->GetOEdge((index+1)%nedges); + // ta = 1; + // tb = 0; + } + } + if(ok){ + _pSmoothEdge = new WXSmoothEdge; + _pSmoothEdge->SetWOeA(woea); + _pSmoothEdge->SetWOeB(woeb); + _pSmoothEdge->SetTa(ta); + _pSmoothEdge->SetTb(tb); + if(_Nature & Nature::SILHOUETTE){ + if(_nNullDotP != 2){ + if(_DotP[_ClosestPointIndex] + 0.01 > 0) + _pSmoothEdge->SetFront(true); + else + _pSmoothEdge->SetFront(false); + } + } + } + + // check bording edges to see if they have different dotp values + // in bording faces. + // for(int i=0; i<numberOfEdges(); i++) + // { + // WSFace * bface = (WSFace*)GetBordingFace(i); + // if(bface != 0) + // { + // if((front())^(bface->front())) // fA->front XOR fB->front (true if one is 0 and the other is 1) + // { + // // that means that the edge i of the face is + // // a silhouette edge + // // TESTER D'ABORD SI LE EXACTSILHOUETTEEDGE N'A PAS + // // ETE CONSTRUIT SUR L'AUTRE FACE.(1 suffit) + // if(0 != ((WSExactFace*)bface)->exactSilhouetteEdge()) + // { + // // that means that this silhouette edge has already been built + // return ((WSExactFace*)bface)->exactSilhouetteEdge(); + // } + // // Else we must build it + // WOEdge *woea, *woeb; + // real ta, tb; + // if(!front()) // is it in the right order ? + // { + // // the order of the WOEdge index is wrong + // woea = _OEdgeList[(i+1)%numberOfEdges()]; + // if(0 == i) + // woeb = _OEdgeList[numberOfEdges()-1]; + // else + // woeb = _OEdgeList[(i-1)]; + // ta = 0; + // tb = 1; + // } + // else + // { + // // the order of the WOEdge index is good + // if(0 == i) + // woea = _OEdgeList[numberOfEdges()-1]; + // else + // woea = _OEdgeList[(i-1)]; + // woeb = _OEdgeList[(i+1)%numberOfEdges()]; + // ta = 1; + // tb = 0; + // } + // + // _pSmoothEdge = new ExactSilhouetteEdge(ExactSilhouetteEdge::VERTEX_VERTEX); + // _pSmoothEdge->SetWOeA(woea); + // _pSmoothEdge->SetWOeA(woeb); + // _pSmoothEdge->SetTa(ta); + // _pSmoothEdge->SetTb(tb); + // + // return _pSmoothEdge; + // } + // } + //} + return _pSmoothEdge; +} + + +void WXFace::ComputeCenter() +{ + vector<WVertex*> iVertexList; + RetrieveVertexList(iVertexList); + Vec3r center; + for(vector<WVertex*>::iterator wv=iVertexList.begin(),wvend=iVertexList.end(); + wv!=wvend; + wv++) + { + center += (*wv)->GetVertex(); + } + center /= (real)iVertexList.size(); + SetCenter(center); +} + + /**********************************/ + /* */ + /* */ + /* WXShape */ + /* */ + /* */ + /**********************************/ + + +WFace* WXShape::MakeFace(vector<WVertex*>& iVertexList, unsigned iMaterialIndex) +{ + WFace *face = WShape::MakeFace(iVertexList, iMaterialIndex); + if(0 == face) + return 0; + + Vec3r center; + for(vector<WVertex*>::iterator wv=iVertexList.begin(),wvend=iVertexList.end(); + wv!=wvend; + wv++) + { + center += (*wv)->GetVertex(); + } + center /= (real)iVertexList.size(); + ((WXFace*)face)->SetCenter(center); + + return face; +} + +WFace * WXShape::MakeFace(vector<WVertex*>& iVertexList, vector<Vec3r>& iNormalsList, vector<Vec2r>& iTexCoordsList, unsigned iMaterialIndex) +{ + WFace *face = WShape::MakeFace(iVertexList, iNormalsList, iTexCoordsList, iMaterialIndex); + + // Vec3r center; + // for(vector<WVertex*>::iterator wv=iVertexList.begin(),wvend=iVertexList.end(); + // wv!=wvend; + // wv++) + // { + // center += (*wv)->GetVertex(); + // } + // center /= (real)iVertexList.size(); + // ((WSFace*)face)->SetCenter(center); + + return face; +} + diff --git a/source/blender/freestyle/intern/winged_edge/WXEdge.h b/source/blender/freestyle/intern/winged_edge/WXEdge.h new file mode 100755 index 00000000000..beacb1a9ca9 --- /dev/null +++ b/source/blender/freestyle/intern/winged_edge/WXEdge.h @@ -0,0 +1,582 @@ +// +// Filename : WXEdge.h +// Author(s) : Stephane Grabli +// Purpose : Classes to define an Extended Winged Edge data structure. +// Date of creation : 26/10/2003 +// +/////////////////////////////////////////////////////////////////////////////// + + +// +// 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 WXEDGE_H +# define WXEDGE_H + +# include "WEdge.h" +# include "Nature.h" +# include "Curvature.h" + +typedef Nature::EdgeNature WXNature; + + /**********************************/ + /* */ + /* */ + /* WXVertex */ + /* */ + /* */ + /**********************************/ + +class WXVertex : public WVertex +{ +private: + // Curvature info + CurvatureInfo *_curvatures; + +public: + inline WXVertex(const Vec3r &v) + : WVertex(v) + {_curvatures = 0;} + /*! Copy constructor */ + WXVertex(WXVertex& iBrother) + : WVertex(iBrother) + {_curvatures = new CurvatureInfo(*iBrother._curvatures);} + virtual WVertex * dupplicate() + { + WXVertex *clone = new WXVertex(*this); + return clone; + } + virtual ~WXVertex() {if(_curvatures) delete _curvatures;} + virtual void Reset() {if(_curvatures) _curvatures->Kr = 0.0;} + inline void setCurvatures(CurvatureInfo *ci) {_curvatures = ci;} + + inline bool isFeature(); + inline CurvatureInfo* curvatures() {return _curvatures;} + +}; + + + + /**********************************/ + /* */ + /* */ + /* WXEdge */ + /* */ + /* */ + /**********************************/ +class WXEdge : public WEdge +{ +private: + WXNature _nature; // flag to indicate whether the edge is a silhouette edge or not + int _order; // 0: the order doesn't matter. 1: the order is the orginal one. -1: the order is not good + bool _front; // a front facing edge is an edge for which the bording face which is the nearest + // from the viewpoint is front. A back facing edge is the opposite. + +public: + inline WXEdge() + : WEdge(){ + _nature = Nature::NO_FEATURE; + _front = false; + _order=0; + } + + inline WXEdge(WOEdge *iOEdge) + : WEdge(iOEdge) + { _nature = Nature::NO_FEATURE;_front = false;_order=0;} + + inline WXEdge(WOEdge *iaOEdge, WOEdge *ibOEdge) + : WEdge(iaOEdge, ibOEdge) + { _nature = Nature::NO_FEATURE;_front = false;_order=0;} + + /*! Copy constructor */ + inline WXEdge(WXEdge& iBrother) + : WEdge(iBrother) + {_nature = iBrother.nature();_front = iBrother._front;_order = iBrother._order;} + virtual WEdge * dupplicate() + { + WXEdge *clone = new WXEdge(*this); + return clone; + } + + virtual ~WXEdge() + {} + + virtual void Reset(){ + _nature = _nature & ~Nature::SILHOUETTE; + _nature = _nature & ~Nature::SUGGESTIVE_CONTOUR; + } + + /*! accessors */ + inline WXNature nature() {return _nature;} + inline bool front() {return _front;} + inline int order() const {return _order;} + + /*! modifiers */ + inline void SetFront(bool iFront) {_front = iFront;} + inline void SetNature(WXNature iNature) {_nature = iNature;} + inline void AddNature(WXNature iNature) {_nature = _nature|iNature;} + inline void SetOrder(int i) {_order = i;} + +}; + + /**********************************/ + /* */ + /* */ + /* WXFace */ + /* */ + /* */ + /**********************************/ + +/*! Class to store a smooth edge (i.e Hertzman & Zorin smooth silhouette edges) */ +class WXSmoothEdge{ +public: + typedef enum{ + EDGE_EDGE, + VERTEX_EDGE, + EDGE_VERTEX + } Configuration; + + WOEdge *_woea; // Oriented edge from which the silhouette edge starts + WOEdge *_woeb; // Oriented edge where the silhouette edge ends + real _ta; // The silhouette starting point's coordinates are : _woea[0]+ta*(_woea[1]-_woea[0]) + real _tb; // The silhouette ending point's coordinates are : _woeb[0]+ta*(_woeb[1]-_woeb[0]) + bool _front; + Configuration _config; + + WXSmoothEdge(){ + _woea = 0; + _woeb = 0; + _ta = 0; + _tb = 0; + _front = false; + _config = EDGE_EDGE; + } + WXSmoothEdge(const WXSmoothEdge& iBrother){ + _woea = iBrother._woea; + _woeb = iBrother._woeb; + _ta = iBrother._ta; + _tb = iBrother._tb; + _config = iBrother._config; + _front = iBrother._front; + } + ~WXSmoothEdge() {} + + inline WOEdge * woea() {return _woea;} + inline WOEdge * woeb() {return _woeb;} + inline real ta() const {return _ta;} + inline real tb() const {return _tb;} + inline bool front() const {return _front;} + inline Configuration configuration() const {return _config;} + + /*! modifiers */ + inline void SetWOeA(WOEdge *iwoea) {_woea = iwoea;} + inline void SetWOeB(WOEdge *iwoeb) {_woeb = iwoeb;} + inline void SetTa(real ta) {_ta = ta;} + inline void SetTb(real tb) {_tb = tb;} + inline void SetFront(bool iFront) {_front = iFront;} + inline void SetConfiguration(Configuration iConf) {_config = iConf;} + +}; +/* Class to store a value per vertex and a smooth edge. + * The WXFace stores a list of these + */ +class WXFace; +class LIB_WINGED_EDGE_EXPORT WXFaceLayer{ +public: + void * userdata; + WXFace * _pWXFace; + vector<real> _DotP;// in case of silhouette: the values obtained when computing the normal-view direction + // dot product. _DotP[i] is this value for the vertex i for that + // face. + WXSmoothEdge * _pSmoothEdge; + WXNature _Nature; + + //tmp values + unsigned _nPosDotP; // count the number of positive dot products for vertices. + // if this number is != 0 and !=_DotP.size() -> it is a silhouette fac + + unsigned _nNullDotP; // count the number of null dot products for vertices. + unsigned _ClosestPointIndex; + bool _viewDependant; + + WXFaceLayer(WXFace *iFace, WXNature iNature, bool viewDependant){ + _pWXFace = iFace; + _pSmoothEdge = 0; + _nPosDotP = 0; + _nNullDotP=0; + _Nature = iNature; + _viewDependant = viewDependant; + userdata = 0; + } + WXFaceLayer(const WXFaceLayer& iBrother){ + _pWXFace = iBrother._pWXFace; + _pSmoothEdge = 0; + _DotP = iBrother._DotP; + _nPosDotP = iBrother._nPosDotP; + _nNullDotP = iBrother._nNullDotP; + _Nature = iBrother._Nature; + if(0 != iBrother._pSmoothEdge) + { + _pSmoothEdge = new WXSmoothEdge(*(iBrother._pSmoothEdge)); + } + _viewDependant = iBrother._viewDependant; + userdata = 0; + } + virtual ~WXFaceLayer() { + if(!_DotP.empty()) + _DotP.clear(); + if(0 != _pSmoothEdge){ + delete _pSmoothEdge; + _pSmoothEdge = 0; + } + } + inline const real dotP(int i) const {return _DotP[i];} + inline unsigned nPosDotP() const {return _nPosDotP;} + inline unsigned nNullDotP() const {return _nNullDotP;} + inline int closestPointIndex() const {return _ClosestPointIndex;} + inline Nature::EdgeNature nature() const {return _Nature;} + inline bool hasSmoothEdge() const {if(_pSmoothEdge) return true; return false;} + inline WXFace * getFace() {return _pWXFace;} + inline WXSmoothEdge * getSmoothEdge() {return _pSmoothEdge;} + inline bool isViewDependant() const {return _viewDependant;} + inline void SetClosestPointIndex(int iIndex) {_ClosestPointIndex = iIndex;} + + inline void removeSmoothEdge() { + if(!_DotP.empty()) + _DotP.clear(); + if (_pSmoothEdge) { + delete _pSmoothEdge; + _pSmoothEdge = 0; + } + } + + /*! If one of the face layer vertex has a DotP equal + * to 0, this method returns the vertex where it happens + */ + unsigned int Get0VertexIndex() const ; + + /*! In case one of the edge of the triangle + * is a smooth edge, this method + * allows to retrieve the concerned edge + */ + unsigned int GetSmoothEdgeIndex() const; + /*! retrieves the edges of the triangle for which + * the signs are different (a null value is not considered) for the dotp + * values at each edge extrimity + */ + void RetrieveCuspEdgesIndices(vector<int>& oCuspEdges); + WXSmoothEdge * BuildSmoothEdge(); + inline void SetDotP(const vector<real>& iDotP) {_DotP = iDotP;} + inline void PushDotP(real iDotP) { + _DotP.push_back(iDotP); + if(iDotP > 0) + ++_nPosDotP; + if(iDotP == 0) + ++_nNullDotP; + } + inline void ReplaceDotP(unsigned int index, real newDotP){ + _DotP[index] = newDotP; + updateDotPInfos(); + } + inline void updateDotPInfos() { + for(vector<real>::iterator d=_DotP.begin(), dend=_DotP.end(); + d!=dend; + ++d){ + _nPosDotP = 0; + _nNullDotP = 0; + if((*d) > 0) + ++_nPosDotP; + if((*d) == 0) + ++_nNullDotP; + } + } +}; + + +class WXFace : public WFace +{ +protected: + Vec3r _center; // center of the face + real _Z; // distance from viewpoint to the center of the face + bool _front; // flag to tell whether the face is front facing or back facing + real _dotp; // value obtained when computing the normal-viewpoint dot product + + vector<WXFaceLayer*> _SmoothLayers; // The data needed to store one or several smooth edges that traverse the face +public: + inline WXFace() : WFace() {_Z=0.0;_front = false;} + /*! Copy constructor */ + WXFace(WXFace& iBrother) + : WFace(iBrother) + { + _center = iBrother.center(); + _Z = iBrother.Z(); + _front = iBrother.front(); + for(vector<WXFaceLayer*>::iterator wxf = iBrother._SmoothLayers.begin(), wxfend = iBrother._SmoothLayers.end(); + wxf != wxfend; + ++wxf){ + _SmoothLayers.push_back(new WXFaceLayer(**wxf)); + } + } + virtual WFace * dupplicate() + { + WXFace * clone = new WXFace(*this); + return clone; + } + + virtual ~WXFace() { + if(!_SmoothLayers.empty()){ + for(vector<WXFaceLayer*>::iterator wxf = _SmoothLayers.begin(), wxfend = _SmoothLayers.end(); + wxf != wxfend; + ++wxf){ + delete (*wxf); + } + _SmoothLayers.clear(); + } + } + + /*! designed to build a specialized WEdge + * for use in MakeEdge + */ + virtual WEdge * instanciateEdge() const {return new WXEdge;} + + /*! accessors */ + inline Vec3r& center() {return _center;} + inline real Z() {return _Z;} + inline bool front() {return _front;} + inline real dotp() {return _dotp;} + inline bool hasSmoothEdges() const { + for(vector<WXFaceLayer*>::const_iterator wxf = _SmoothLayers.begin(), wxfend = _SmoothLayers.end(); + wxf != wxfend; + ++wxf){ + if( ((*wxf)->hasSmoothEdge())){ + return true; + } + } + return false; + } + vector<WXFaceLayer*>& getSmoothLayers() {return _SmoothLayers;} + /*! retrieve the smooth edges that match the Nature given as argument */ + void retrieveSmoothEdges(WXNature iNature, vector<WXSmoothEdge*>& oSmoothEdges){ + for(vector<WXFaceLayer*>::iterator wxf = _SmoothLayers.begin(), wxfend = _SmoothLayers.end(); + wxf != wxfend; + ++wxf){ + if( ((*wxf)->hasSmoothEdge()) && ((*wxf)->_Nature & iNature) ){ + oSmoothEdges.push_back((*wxf)->_pSmoothEdge); + } + } + } + void retrieveSmoothEdgesLayers(WXNature iNature, vector<WXFaceLayer*>& oSmoothEdgesLayers){ + for(vector<WXFaceLayer*>::iterator wxf = _SmoothLayers.begin(), wxfend = _SmoothLayers.end(); + wxf != wxfend; + ++wxf){ + if( ((*wxf)->hasSmoothEdge()) && ((*wxf)->_Nature & iNature) ){ + oSmoothEdgesLayers.push_back((*wxf)); + } + } + } + void retrieveSmoothLayers(WXNature iNature, vector<WXFaceLayer*>& oSmoothLayers){ + for(vector<WXFaceLayer*>::iterator wxf = _SmoothLayers.begin(), wxfend = _SmoothLayers.end(); + wxf != wxfend; + ++wxf){ + if((*wxf)->_Nature & iNature){ + oSmoothLayers.push_back(*wxf); + } + } + } + /*! modifiers */ + inline void SetCenter(const Vec3r& iCenter) {_center = iCenter;} + void ComputeCenter(); + inline void SetZ(real z) {_Z = z;} + inline void SetFront(bool iFront) {_front = iFront;} + inline void SetDotP(real iDotP) + { + _dotp = iDotP; + if(_dotp > 0) + _front = true; + else + _front = false; + } + inline void AddSmoothLayer(WXFaceLayer * iLayer){ + _SmoothLayers.push_back(iLayer); + } + inline void Reset() { + vector<WXFaceLayer*> layersToKeep; + for(vector<WXFaceLayer*>::iterator wxf = _SmoothLayers.begin(), wxfend = _SmoothLayers.end(); + wxf != wxfend; + ++wxf){ + if((*wxf)->isViewDependant()) + delete (*wxf); + else + layersToKeep.push_back(*wxf); + } + _SmoothLayers = layersToKeep; + } + /*! Clears everything */ + inline void Clear() { + for(vector<WXFaceLayer*>::iterator wxf = _SmoothLayers.begin(), wxfend = _SmoothLayers.end(); + wxf != wxfend; + ++wxf){ + delete (*wxf); + } + _SmoothLayers.clear(); + } + virtual void ResetUserData() { + WFace::ResetUserData(); + for(vector<WXFaceLayer*>::iterator wxf = _SmoothLayers.begin(), wxfend = _SmoothLayers.end(); + wxf != wxfend; + ++wxf){ + (*wxf)->userdata = 0; + } + } +}; + + + /**********************************/ + /* */ + /* */ + /* WXShape */ + /* */ + /* */ + /**********************************/ + + +class WXShape : public WShape +{ +public: + typedef WXShape type_name; +protected: + bool _computeViewIndependant; // flag to indicate whether the view independant stuff must be computed or not +public: + inline WXShape() : WShape() {_computeViewIndependant = true;} + /*! copy constructor */ + inline WXShape(WXShape& iBrother) + :WShape(iBrother) + { + _computeViewIndependant = iBrother._computeViewIndependant; + } + virtual WShape * dupplicate() + { + WXShape *clone = new WXShape(*this); + return clone; + } + + virtual ~WXShape() + { + } + + inline bool getComputeViewIndependantFlag() const {return _computeViewIndependant;} + inline void setComputeViewIndependantFlag(bool iFlag) {_computeViewIndependant = iFlag;} + + /*! designed to build a specialized WFace + * for use in MakeFace + */ + virtual WFace * instanciateFace() const {return new WXFace;} + + /*! adds a new face to the shape + * returns the built face. + * iVertexList + * List of face's vertices. These vertices are + * not added to the WShape vertex list; they are + * supposed to be already stored when calling MakeFace. + * The order in which the vertices are stored in the list + * determines the face's edges orientation and (so) the + * face orientation. + */ + virtual WFace * MakeFace(vector<WVertex*>& iVertexList, unsigned iMaterialIndex); + + /*! adds a new face to the shape. The difference with + * the previous method is that this one is designed + * to build a WingedEdge structure for which there are + * per vertex normals, opposed to per face normals. + * returns the built face. + * iVertexList + * List of face's vertices. These vertices are + * not added to the WShape vertex list; they are + * supposed to be already stored when calling MakeFace. + * The order in which the vertices are stored in the list + * determines the face's edges orientation and (so) the + * face orientation. + * iNormalsList + * The list of normals, iNormalsList[i] corresponding to the + * normal of the vertex iVertexList[i] for that face. + * iTexCoordsList + * The list of tex coords, iTexCoordsList[i] corresponding to the + * normal of the vertex iVertexList[i] for that face. + */ + virtual WFace * MakeFace(vector<WVertex*>& iVertexList, vector<Vec3r>& iNormalsList, vector<Vec2r>& iTexCoordsList, unsigned iMaterialIndex); + + /*! Reset all edges and vertices flags (which might + * have been set up on a previous pass) + */ + virtual void Reset(){ + // Reset Edges + vector<WEdge*>& wedges = GetEdgeList(); + for(vector<WEdge*>::iterator we=wedges.begin(),weend=wedges.end(); + we!=weend; + we++){ + ((WXEdge*)(*we))->Reset(); + } + + //Reset faces: + vector<WFace*>& wfaces = GetFaceList(); + for(vector<WFace*>::iterator wf=wfaces.begin(),wfend=wfaces.end(); + wf!=wfend; + wf++){ + ((WXFace*)(*wf))->Reset(); + } + } + /*! accessors */ +}; + +/* + + ############################################# + ############################################# + ############################################# + ###### ###### + ###### I M P L E M E N T A T I O N ###### + ###### ###### + ############################################# + ############################################# + ############################################# + +*/ +/* for inline functions */ + +bool WXVertex::isFeature() +{ + int counter = 0; + vector<WEdge*>& vedges = GetEdges(); + for(vector<WEdge*>::iterator ve=vedges.begin(), vend=vedges.end(); + ve!=vend; + ve++) + { + if(((WXEdge*)(*ve))->nature() != Nature::NO_FEATURE) + counter++; + } + + if((counter == 1) || (counter > 2)) + return true; + + return false; +} + + +#endif diff --git a/source/blender/freestyle/intern/winged_edge/WXEdgeBuilder.cpp b/source/blender/freestyle/intern/winged_edge/WXEdgeBuilder.cpp new file mode 100755 index 00000000000..534c6e323a9 --- /dev/null +++ b/source/blender/freestyle/intern/winged_edge/WXEdgeBuilder.cpp @@ -0,0 +1,43 @@ +// +// 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 "WXEdgeBuilder.h" +#include "WXEdge.h" + +void WXEdgeBuilder::visitIndexedFaceSet(IndexedFaceSet& ifs) +{ + WXShape *shape = new WXShape; + buildWShape(*shape, ifs); + shape->SetId(ifs.getId().getFirst()); + //ifs.SetId(shape->GetId()); +} + +void WXEdgeBuilder::buildWVertices(WShape& shape, + const real *vertices, + unsigned vsize) { + WXVertex *vertex; + for (unsigned i = 0; i < vsize; i += 3) { + vertex = new WXVertex(Vec3r(vertices[i], + vertices[i + 1], + vertices[i + 2])); + vertex->SetId(i / 3); + shape.AddVertex(vertex); + } +} diff --git a/source/blender/freestyle/intern/winged_edge/WXEdgeBuilder.h b/source/blender/freestyle/intern/winged_edge/WXEdgeBuilder.h new file mode 100755 index 00000000000..b646d66a285 --- /dev/null +++ b/source/blender/freestyle/intern/winged_edge/WXEdgeBuilder.h @@ -0,0 +1,51 @@ +#ifndef WXEDGEBUILDER_H +# define WXEDGEBUILDER_H + +// +// Filename : WSBuilder.h +// Author(s) : Stephane Grabli +// Purpose : Class inherited from WingedEdgeBuilder and +// designed to build a WX (WingedEdge + extended info(silhouette etc...)) +// structure from a polygonal model +// Date of creation : 28/05/03 +// +/////////////////////////////////////////////////////////////////////////////// + + +// +// 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 "WingedEdgeBuilder.h" +# include "../scene_graph/IndexedFaceSet.h" + +class LIB_WINGED_EDGE_EXPORT WXEdgeBuilder : public WingedEdgeBuilder +{ +public: + WXEdgeBuilder() : WingedEdgeBuilder() {} + virtual ~WXEdgeBuilder() {} + VISIT_DECL(IndexedFaceSet) + +protected: + virtual void buildWVertices(WShape& shape, + const real *vertices, + unsigned vsize); +}; + +#endif // WXEDGEBUILDER_H diff --git a/source/blender/freestyle/intern/winged_edge/WingedEdgeBuilder.cpp b/source/blender/freestyle/intern/winged_edge/WingedEdgeBuilder.cpp new file mode 100755 index 00000000000..98e7c269248 --- /dev/null +++ b/source/blender/freestyle/intern/winged_edge/WingedEdgeBuilder.cpp @@ -0,0 +1,362 @@ + +// +// 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 "../geometry/GeomUtils.h" +#include "../scene_graph/NodeShape.h" +#include "WingedEdgeBuilder.h" +#include <set> +using namespace std; + +void WingedEdgeBuilder::visitIndexedFaceSet(IndexedFaceSet& ifs) { + WShape *shape = new WShape; + buildWShape(*shape, ifs); + shape->SetId(ifs.getId().getFirst()); + //ifs.SetId(shape->GetId()); +} + +void WingedEdgeBuilder::visitNodeShape(NodeShape& ns) { + //Sets the current material to iShapeode->material: + _current_material = &(ns.material()); +} + +void WingedEdgeBuilder::visitNodeTransform(NodeTransform& tn) { + if(!_current_matrix) { + _current_matrix = new Matrix44r(tn.matrix()); + return; + } + + _matrices_stack.push_back(_current_matrix); + Matrix44r *new_matrix = new Matrix44r(*_current_matrix * tn.matrix()); + _current_matrix = new_matrix; +} + +void WingedEdgeBuilder::visitNodeTransformAfter(NodeTransform&) { + if(_current_matrix) + delete _current_matrix; + + if(_matrices_stack.empty()) { + _current_matrix = NULL; + return; + } + + _current_matrix = _matrices_stack.back(); + _matrices_stack.pop_back(); +} + +void WingedEdgeBuilder::buildWShape(WShape& shape, IndexedFaceSet& ifs) { + unsigned vsize = ifs.vsize(); + unsigned nsize = ifs.nsize(); + unsigned tsize = ifs.tsize(); + + const real* vertices = ifs.vertices(); + const real* normals = ifs.normals(); + const real* texCoords = ifs.texCoords(); + + real* new_vertices; + real* new_normals; + + new_vertices = new real[vsize]; + new_normals = new real[nsize]; + + // transform coordinates from local to world system + if(_current_matrix) { + transformVertices(vertices, vsize, *_current_matrix, new_vertices); + transformNormals(normals, nsize, *_current_matrix, new_normals); + } + else { + memcpy(new_vertices, vertices, vsize * sizeof(*new_vertices)); + memcpy(new_normals, normals, nsize * sizeof(*new_normals)); + } + + const IndexedFaceSet::TRIANGLES_STYLE* faceStyle = ifs.trianglesStyle(); + + vector<Material> materials; + if(ifs.msize()){ + const Material*const* mats = ifs.materials(); + for(unsigned i=0; i<ifs.msize(); ++i) + materials.push_back(*(mats[i])); + shape.SetMaterials(materials); + } + + // const Material * mat = (ifs.material()); + // if (mat) + // shape.SetMaterial(*mat); + // else if(_current_material) + // shape.SetMaterial(*_current_material); + + // sets the current WShape to shape + _current_wshape = &shape; + + // create a WVertex for each vertex + buildWVertices(shape, new_vertices, vsize); + + const unsigned* vindices = ifs.vindices(); + const unsigned* nindices = ifs.nindices(); + const unsigned* tindices = 0; + if(ifs.tsize()){ + tindices = ifs.tindices(); + } + + const unsigned *mindices = 0; + if(ifs.msize()) + mindices = ifs.mindices(); + const unsigned* numVertexPerFace = ifs.numVertexPerFaces(); + const unsigned numfaces = ifs.numFaces(); + + for (unsigned index = 0; index < numfaces; index++) { + switch(faceStyle[index]) { + case IndexedFaceSet::TRIANGLE_STRIP: + buildTriangleStrip(new_vertices, + new_normals, + materials, + texCoords, + vindices, + nindices, + mindices, + tindices, + numVertexPerFace[index]); + break; + case IndexedFaceSet::TRIANGLE_FAN: + buildTriangleFan(new_vertices, + new_normals, + materials, + texCoords, + vindices, + nindices, + mindices, + tindices, + numVertexPerFace[index]); + break; + case IndexedFaceSet::TRIANGLES: + buildTriangles(new_vertices, + new_normals, + materials, + texCoords, + vindices, + nindices, + mindices, + tindices, + numVertexPerFace[index]); + break; + } + vindices += numVertexPerFace[index]; + nindices += numVertexPerFace[index]; + if(mindices) + mindices += numVertexPerFace[index]; + if(tindices) + tindices += numVertexPerFace[index]; + } + + delete[] new_vertices; + delete[] new_normals; + + // compute bbox + shape.ComputeBBox(); + // compute mean edge size: + shape.ComputeMeanEdgeSize(); + + // Parse the built winged-edge shape to update post-flags + set<Vec3r> normalsSet; + vector<WVertex*>& wvertices = shape.GetVertexList(); + for(vector<WVertex*>::iterator wv=wvertices.begin(), wvend=wvertices.end(); + wv!=wvend; + ++wv){ + if((*wv)->isBoundary()) + continue; + normalsSet.clear(); + WVertex::face_iterator fit = (*wv)->faces_begin(); + WVertex::face_iterator fitend = (*wv)->faces_end(); + while(fit!=fitend){ + WFace *face = *fit; + normalsSet.insert(face->GetVertexNormal(*wv)); + if(normalsSet.size()!=1){ + break; + } + ++fit; + } + if(normalsSet.size()!=1){ + (*wv)->SetSmooth(false); + } + } + // Adds the new WShape to the WingedEdge structure + _winged_edge->addWShape(&shape); +} + +void WingedEdgeBuilder::buildWVertices(WShape& shape, + const real *vertices, + unsigned vsize) { + WVertex *vertex; + for (unsigned i = 0; i < vsize; i += 3) { + vertex = new WVertex(Vec3r(vertices[i], + vertices[i + 1], + vertices[i + 2])); + vertex->SetId(i / 3); + shape.AddVertex(vertex); + } +} + +void WingedEdgeBuilder::buildTriangleStrip( const real *vertices, + const real *normals, + vector<Material>& iMaterials, + const real *texCoords, + const unsigned *vindices, + const unsigned *nindices, + const unsigned *mindices, + const unsigned *tindices, + const unsigned nvertices) { + unsigned nDoneVertices = 2; // number of vertices already treated + unsigned nTriangle = 0; // number of the triangle currently being treated + //int nVertex = 0; // vertex number + + WShape* currentShape = _current_wshape; // the current shape being built + vector<WVertex *> triangleVertices; + vector<Vec3r> triangleNormals; + vector<Vec2r> triangleTexCoords; + + while(nDoneVertices < nvertices) + { + //clear the vertices list: + triangleVertices.clear(); + //Then rebuild it: + if(0 == nTriangle%2) // if nTriangle is even + { + triangleVertices.push_back(currentShape->GetVertexList()[vindices[nTriangle]/3]); + triangleVertices.push_back(currentShape->GetVertexList()[vindices[nTriangle+1]/3]); + triangleVertices.push_back(currentShape->GetVertexList()[vindices[nTriangle+2]/3]); + + triangleNormals.push_back(Vec3r(normals[nindices[nTriangle]],normals[nindices[nTriangle]+1], normals[nindices[nTriangle]+2])); + triangleNormals.push_back(Vec3r(normals[nindices[nTriangle+1]],normals[nindices[nTriangle+1]+1],normals[nindices[nTriangle+1]+2])); + triangleNormals.push_back(Vec3r(normals[nindices[nTriangle+2]], normals[nindices[nTriangle+2]+1], normals[nindices[nTriangle+2]+2])); + + if(texCoords){ + triangleTexCoords.push_back(Vec2r(texCoords[tindices[nTriangle]],texCoords[tindices[nTriangle]+1])); + triangleTexCoords.push_back(Vec2r(texCoords[tindices[nTriangle+1]],texCoords[tindices[nTriangle+1]+1])); + triangleTexCoords.push_back(Vec2r(texCoords[tindices[nTriangle+2]], texCoords[tindices[nTriangle+2]+1])); + } + } + else // if nTriangle is odd + { + triangleVertices.push_back(currentShape->GetVertexList()[vindices[nTriangle]/3]); + triangleVertices.push_back(currentShape->GetVertexList()[vindices[nTriangle+2]/3]); + triangleVertices.push_back(currentShape->GetVertexList()[vindices[nTriangle+1]/3]); + + triangleNormals.push_back(Vec3r(normals[nindices[nTriangle]],normals[nindices[nTriangle]+1], normals[nindices[nTriangle]+2])); + triangleNormals.push_back(Vec3r(normals[nindices[nTriangle+2]],normals[nindices[nTriangle+2]+1],normals[nindices[nTriangle+2]+2])); + triangleNormals.push_back(Vec3r(normals[nindices[nTriangle+1]], normals[nindices[nTriangle+1]+1], normals[nindices[nTriangle+1]+2])); + + if(texCoords){ + triangleTexCoords.push_back(Vec2r(texCoords[tindices[nTriangle]],texCoords[tindices[nTriangle]+1])); + triangleTexCoords.push_back(Vec2r(texCoords[tindices[nTriangle+2]],texCoords[tindices[nTriangle+2]+1])); + triangleTexCoords.push_back(Vec2r(texCoords[tindices[nTriangle+1]], texCoords[tindices[nTriangle+1]+1])); + } + } + if(mindices) + currentShape->MakeFace(triangleVertices, triangleNormals, triangleTexCoords, mindices[nTriangle/3]); + else + currentShape->MakeFace(triangleVertices, triangleNormals, triangleTexCoords, 0); + nDoneVertices++; // with a strip, each triangle is one vertex more + nTriangle++; + } +} + +void WingedEdgeBuilder::buildTriangleFan( const real *vertices, + const real *normals, + vector<Material>& iMaterials, + const real *texCoords, + const unsigned *vindices, + const unsigned *nindices, + const unsigned *mindices, + const unsigned *tindices, + const unsigned nvertices) { + // Nothing to be done +} + +void WingedEdgeBuilder::buildTriangles(const real *vertices, + const real *normals, + vector<Material>& iMaterials, + const real *texCoords, + const unsigned *vindices, + const unsigned *nindices, + const unsigned *mindices, + const unsigned *tindices, + const unsigned nvertices) { + WShape * currentShape = _current_wshape; // the current shape begin built + vector<WVertex *> triangleVertices; + vector<Vec3r> triangleNormals; + vector<Vec2r> triangleTexCoords; + + // Each triplet of vertices is considered as an independent triangle + for(unsigned i = 0; i < nvertices / 3; i++) + { + triangleVertices.push_back(currentShape->GetVertexList()[vindices[3*i]/3]); + triangleVertices.push_back(currentShape->GetVertexList()[vindices[3*i+1]/3]); + triangleVertices.push_back(currentShape->GetVertexList()[vindices[3*i+2]/3]); + + triangleNormals.push_back(Vec3r(normals[nindices[3*i]],normals[nindices[3*i]+1], normals[nindices[3*i]+2])); + triangleNormals.push_back(Vec3r(normals[nindices[3*i+1]],normals[nindices[3*i+1]+1],normals[nindices[3*i+1]+2])); + triangleNormals.push_back(Vec3r(normals[nindices[3*i+2]], normals[nindices[3*i+2]+1], normals[nindices[3*i+2]+2])); + + if(texCoords){ + triangleTexCoords.push_back(Vec2r(texCoords[tindices[3*i]],texCoords[tindices[3*i]+1])); + triangleTexCoords.push_back(Vec2r(texCoords[tindices[3*i+1]],texCoords[tindices[3*i+1]+1])); + triangleTexCoords.push_back(Vec2r(texCoords[tindices[3*i+2]], texCoords[tindices[3*i+2]+1])); + } + } + if(mindices) + currentShape->MakeFace(triangleVertices, triangleNormals, triangleTexCoords, mindices[0]); + else + currentShape->MakeFace(triangleVertices, triangleNormals, triangleTexCoords,0); + +} + +void WingedEdgeBuilder::transformVertices(const real *vertices, + unsigned vsize, + const Matrix44r& transform, + real *res) { + const real *v = vertices; + real *pv = res; + + for (unsigned i = 0; i < vsize / 3; i++) { + HVec3r hv_tmp(v[0], v[1], v[2]); + HVec3r hv(transform * hv_tmp); + for (unsigned j = 0; j < 3; j++) + pv[j] = hv[j] / hv[3]; + v += 3; + pv += 3; + } +} + +void WingedEdgeBuilder::transformNormals(const real *normals, + unsigned nsize, + const Matrix44r& transform, + real* res) { + const real *n = normals; + real *pn = res; + + for (unsigned i = 0; i < nsize / 3; i++) { + Vec3r hn(n[0], n[1], n[2]); + hn = GeomUtils::rotateVector(transform, hn); + for (unsigned j = 0; j < 3; j++) + pn[j] = hn[j]; + n += 3; + pn += 3; + } +} diff --git a/source/blender/freestyle/intern/winged_edge/WingedEdgeBuilder.h b/source/blender/freestyle/intern/winged_edge/WingedEdgeBuilder.h new file mode 100755 index 00000000000..fe033f2ea0b --- /dev/null +++ b/source/blender/freestyle/intern/winged_edge/WingedEdgeBuilder.h @@ -0,0 +1,160 @@ +// +// Filename : WingedEdgeBuilder.h +// Author(s) : Stephane Grabli +// Purpose : Class to render a WingedEdge data structure +// from a polyhedral data structure organized in +// nodes of a scene graph +// Date of creation : 28/05/03 +// +/////////////////////////////////////////////////////////////////////////////// + + +// +// 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 WINGED_EDGE_BUILDER_H +# define WINGED_EDGE_BUILDER_H + +# include "../system/FreestyleConfig.h" +# include "../scene_graph/SceneVisitor.h" +# include "WEdge.h" +# include "../scene_graph/IndexedFaceSet.h" +# include "../scene_graph/NodeTransform.h" + +class LIB_WINGED_EDGE_EXPORT WingedEdgeBuilder : public SceneVisitor +{ + public: + + inline WingedEdgeBuilder() : SceneVisitor() { + _current_wshape = NULL; + _current_material = NULL; + _current_matrix = NULL; + _winged_edge = new WingedEdge; // Not deleted by the destructor + } + + virtual ~WingedEdgeBuilder() { + for (vector<Matrix44r*>::iterator it = _matrices_stack.begin(); + it != _matrices_stack.end(); + it++) + delete *it; + _matrices_stack.clear(); + } + + VISIT_DECL(IndexedFaceSet) + VISIT_DECL(NodeShape) + VISIT_DECL(NodeTransform) + + virtual void visitNodeTransformAfter(NodeTransform&); + + // + // Accessors + // + ///////////////////////////////////////////////////////////////////////////// + + inline WingedEdge* getWingedEdge() { + return _winged_edge; + } + + inline WShape* getCurrentWShape() { + return _current_wshape; + } + + inline Material* getCurrentMaterial() { + return _current_material; + } + + inline Matrix44r* getCurrentMatrix() { + return _current_matrix; + } + + // + // Modifiers + // + ///////////////////////////////////////////////////////////////////////////// + + inline void setCurrentWShape(WShape* wshape) { + _current_wshape = wshape; + } + + inline void setCurrentMaterial(Material* mat) { + _current_material = mat; + } + + // inline void setCurrentMatrix(Matrix44r* matrix) { + // _current_matrix = matrix; + // } + + protected: + + virtual void buildWShape(WShape& shape, IndexedFaceSet& ifs); + virtual void buildWVertices(WShape& shape, + const real *vertices, + unsigned vsize); + + private: + + void buildTriangleStrip(const real *vertices, + const real *normals, + vector<Material>& iMaterials, + const real *texCoords, + const unsigned *vindices, + const unsigned *nindices, + const unsigned *mindices, + const unsigned *tindices, + const unsigned nvertices); + + void buildTriangleFan(const real *vertices, + const real *normals, + vector<Material>& iMaterials, + const real *texCoords, + const unsigned *vindices, + const unsigned *nindices, + const unsigned *mindices, + const unsigned *tindices, + const unsigned nvertices); + + void buildTriangles(const real *vertices, + const real *normals, + vector<Material>& iMaterials, + const real *texCoords, + const unsigned *vindices, + const unsigned *nindices, + const unsigned *mindices, + const unsigned *tindices, + const unsigned nvertices); + + void transformVertices(const real *vertices, + unsigned vsize, + const Matrix44r& transform, + real *res); + + void transformNormals(const real *normals, + unsigned nsize, + const Matrix44r& transform, + real *res); + + WShape* _current_wshape; + Material* _current_material; + WingedEdge* _winged_edge; + Matrix44r* _current_matrix; + vector<Matrix44r*> _matrices_stack; +}; + +#endif // WINGED_EDGE_BUILDER_H diff --git a/source/blender/freestyle/intern/winged_edge/src.pri b/source/blender/freestyle/intern/winged_edge/src.pri new file mode 100755 index 00000000000..9cf40633dcf --- /dev/null +++ b/source/blender/freestyle/intern/winged_edge/src.pri @@ -0,0 +1,21 @@ +# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # +# W A R N I N G ! ! ! # +# a u t h o r i z e d p e r s o n a l o n l y # +# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # + +WINGED_EDGE_DIR = ../winged_edge + +SOURCES *= $${WINGED_EDGE_DIR}/Curvature.cpp \ + $${WINGED_EDGE_DIR}/WEdge.cpp \ + $${WINGED_EDGE_DIR}/WFillGrid.cpp \ + $${WINGED_EDGE_DIR}/WingedEdgeBuilder.cpp \ + $${WINGED_EDGE_DIR}/WXEdgeBuilder.cpp \ + $${WINGED_EDGE_DIR}/WXEdge.cpp + +HEADERS *= $${WINGED_EDGE_DIR}/Curvature.h \ + $${WINGED_EDGE_DIR}/Nature.h \ + $${WINGED_EDGE_DIR}/WEdge.h \ + $${WINGED_EDGE_DIR}/WFillGrid.h \ + $${WINGED_EDGE_DIR}/WingedEdgeBuilder.h \ + $${WINGED_EDGE_DIR}/WXEdgeBuilder.h \ + $${WINGED_EDGE_DIR}/WXEdge.h diff --git a/source/blender/freestyle/intern/winged_edge/winged_edge.pro b/source/blender/freestyle/intern/winged_edge/winged_edge.pro new file mode 100755 index 00000000000..e36d69454b6 --- /dev/null +++ b/source/blender/freestyle/intern/winged_edge/winged_edge.pro @@ -0,0 +1,84 @@ +# This file should be viewed as a -*- mode: Makefile -*- + +# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # +# W A R N I N G ! ! ! # +# a u t h o r i z e d p e r s o n a l o n l y # +# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # + +include(../Config.pri) + +TEMPLATE = lib + +TARGET = $${LIB_WINGED_EDGE} +VERSION = $${APPVERSION} +TARGET_VERSION_EXT = $${APPVERSION_MAJ}.$${APPVERSION_MID} + +# +# CONFIG +# +####################################### + +CONFIG *= dll + +# +# DEFINES +# +####################################### + +win32:DEFINES *= MAKE_LIB_WINGED_EDGE_DLL + +# +# INCLUDE PATH +# +####################################### + +#INCLUDEPATH *= ../geometry ../scene_graph ../system + +# +# BUILD DIRECTORIES +# +####################################### + +BUILD_DIR = ../../build + +OBJECTS_DIR = $${BUILD_DIR}/$${REL_OBJECTS_DIR} +!win32:DESTDIR = $${BUILD_DIR}/$${REL_DESTDIR}/lib +win32:DESTDIR = $${BUILD_DIR}/$${REL_DESTDIR} + +# +# LIBS +# +####################################### + +win32:LIBS *= $${DESTDIR}/$${LIB_GEOMETRY}$${LIBVERSION}.lib \ + $${DESTDIR}/$${LIB_SCENE_GRAPH}$${LIBVERSION}.lib \ + $${DESTDIR}/$${LIB_SYSTEM}$${LIBVERSION}.lib +!win32 { + lib_bundle { + LIBS += -F$${DESTDIR} -framework $${LIB_GEOMETRY} \ + -framework $${LIB_SYSTEM} -framework $${LIB_SCENE_GRAPH} + } else { + LIBS += -L$${DESTDIR} -l$${LIB_GEOMETRY} -l$${LIB_SCENE_GRAPH} -l$${LIB_SYSTEM} + } +} + + +# +# INSTALL +# +####################################### + +LIB_DIR = ../../lib +# install library +target.path = $$LIB_DIR +# "make install" configuration options +INSTALLS += target + +# +# SOURCES & HEADERS +# +####################################### + +!static { + include(src.pri) +} |