Subversion Repositories gelsvn

#include <queue>
#include <vector>

#include "triangulate.h"
#include "HMesh/VertexCirculator.h"
#include "HMesh/FaceCirculator.h"

using namespace std;
using namespace CGLA;
using namespace HMesh;

namespace HMesh
{
        namespace
        {
                float normal_cone(vector<Vec3f>& norms)
                {
                        float val = 1.0f;
                        for(size_t i=0;i<norms.size()-1;++i)
                                for(size_t j=i+1;j<norms.size();++j)
                                        val = min(val, dot(norms[i], norms[j]));
                        return val;
                }
 

                void get_candidates(const VertexIter& v,
                                                                                                vector<VertexIter>& vertices_check)
                {
                        VertexCirculator vc(v);
                        for(;!vc.end();++vc)
                                vertices_check.push_back(vc.get_vertex());
                }
                
                const CGLA::Vec3f extended_normal(const VertexIter& v)
                {
                        vector<HalfEdgeIter> hedges;
                                                
                        VertexCirculator vc(v);
                        for(;!vc.end();++vc)
                                hedges.push_back(vc.get_halfedge());

                        vector<Vec3f> one_ring;
                        int N = vc.no_steps();
                        for(int i=N-1;i>=0;--i)
                                {
                                        HalfEdgeIter h = hedges[i];
                                        //one_ring.push_back(h->vert->get_pos());
                                        h = h->next;
                                        while(h->vert != v)
                                                {
                                                        one_ring.push_back(h->vert->pos);
                                                        h = h->next;
                                                }
                                }
                        Vec3f norm(0);
                        N= one_ring.size();
                        Vec3f p0 = v->pos;
                        for(int i=0;i<N;++i)
                                {
                                        Vec3f p1 = one_ring[i];
                                        Vec3f p2 = one_ring[(i+1)%N];
                                        Vec3f e0 = normalize(p1-p0);
                                        Vec3f e1 = normalize(p2-p0);
                                        norm += cross(e0,e1)*acos(dot(e0,e1));
                                }
                        return normalize(norm);
                }


                struct PotentialEdge
                { 
                        VertexIter v0;
                        VertexIter v1;
                        FaceIter f;
                        int time;
                        float badness;
                };


        bool operator>(const PotentialEdge& e0, const PotentialEdge& e1)
        {
                return e0.badness>e1.badness;
        }

        typedef std::priority_queue<PotentialEdge,
                                                                                                                        std::vector<PotentialEdge>,
                                                                                                                        std::greater<PotentialEdge> > 
        PotentialEdgeQueue;
                
        }

        
        //algorithm: process_face(f, Q)
        void process_face(FaceIter& f, PotentialEdgeQueue& Q)
        {
                //if f is triangle, return
                if(f->last->next->next->next == f->last)
                        return;
                
                vector<VertexIter> verts;
                vector<Vec3f> norms;
                
                typedef vector<VertexIter> VertVec; 
                vector<VertVec> nbrs;

                //for each vertex v in f
                for(FaceCirculator fc(f);!fc.end();++fc)
                        {
                                VertexIter v = fc.get_vertex();
                                verts.push_back(v);
                                norms.push_back(extended_normal(v));
                                VertVec nbr_vec;
                                get_candidates(v, nbr_vec);
                                nbrs.push_back(nbr_vec);
                        }
                
                int n = verts.size();

                for(int i=0;i<n-2;++i)
                        for(int j=i+2;j<n;++j)
                                {
                                        if(i==0 && j==(n-1)) continue;
                                        assert((i-j)*(i-j)==1);
                                        
                                        //                      For each vertex pair (v0,v1)
                                        //              if v0 belongs to check_lists[v1] then continue with next pair
                                        if(find(nbrs[j].begin(), nbrs[j].end(), verts[i])
                                                 == nbrs[j].end())
                                                {
                                                        vector<Vec3f> norms_a;
                                                        vector<Vec3f> norms_b;

                                                        for(int k=0;k<n;++k)
                                                                {
                                                                        if(k>=i && k<=j)
                                                                                norms_a.push_back(norms[k]);
                                                                        if(k<=i || k>=j)
                                                                                norms_b.push_back(norms[k]);
                                                                }
                                                        float badness_a = normal_cone(norms_a);
                                                        float badness_b = normal_cone(norms_b);
                                                        
                                                        float badness = 1.0f/(sqr(badness_a)*sqr(badness_b));
                                                        //              add (v0,v1,f,f.touchvalue,badness) to Q;
                                                        PotentialEdge pot_edge;
                                                        pot_edge.v0 = verts[i];
                                                        pot_edge.v1 = verts[j];
                                                        pot_edge.f = f;
                                                        pot_edge.time = f->touched;
                                                        pot_edge.badness = badness;
                                                        Q.push(pot_edge);
                                                }
                                }
        }
        

        void triangulate_face_order(Manifold& m)
        {
                PotentialEdgeQueue Q;
                
                for(FaceIter f_itr = m.faces_begin(); 
                                f_itr != m.faces_end(); ++f_itr)
                        process_face(f_itr, Q);

                while(!Q.empty())
                        {
                                PotentialEdge pot = Q.top();

                                // If face has NOT been processed since this record
                                // was created. 
                                if(pot.f->touched == pot.time)
                                        {
                                                // Make list of faces adjacent to f (adj_faces).
                                                vector<FaceIter> nbr_faces;
                                                FaceCirculator fc(pot.f);
                                                for(; !fc.end(); ++fc)
                                                        nbr_faces.push_back(fc.get_face());
                                                
                                                // create edge(v0,v1) producing a new face fn;
                                                FaceIter fn = m.split_face(pot.f, pot.v0, pot.v1);
                                                
                                                nbr_faces.push_back(pot.f);
                                                nbr_faces.push_back(fn);
                                                
                                                for(size_t i=0;i<nbr_faces.size();++i)
                                                        {
                                                                nbr_faces[i]->touched++;
                                                                process_face(nbr_faces[i],Q);
                                                        }
                                        }
                                Q.pop();
                        }
        }
                                                
        
        


}