Subversion Repositories gelsvn

Rev

Rev 183 | Rev 601 | Go to most recent revision | Show entire file | Regard whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 183 Rev 595
Line -... Line 1...
- 
 
 1 
/* ----------------------------------------------------------------------- *
- 
 
 2 
 * This file is part of GEL, http://www.imm.dtu.dk/GEL
- 
 
 3 
 * Copyright (C) the authors and DTU Informatics
- 
 
 4 
 * For license and list of authors, see ../../doc/intro.pdf
- 
 
 5 
 * ----------------------------------------------------------------------- */
- 
 
 6 
 
- 
 
 7 
#include "triangulate.h"
- 
 
 8 
 
1 
#include <queue>
 9 
#include <queue>
2 
#include <vector>
 10 
#include <vector>
- 
 
 11 
#include <iterator>
- 
 
 12 
#include <cassert>
3 
 
 13 
 
4 
#include "triangulate.h"
 14 
#include <CGLA/Vec3d.h>
5 
#include "HMesh/VertexCirculator.h"
 - 
 
6 
#include "HMesh/FaceCirculator.h"
 - 
 
7 
 
 15 
 
8 
using namespace std;
 16 
#include "Manifold.h"
9 
using namespace CGLA;
 - 
 
10 
using namespace HMesh;
 17 
#include "AttributeVector.h"
11 
 
 18 
 
12 
namespace HMesh
 19 
namespace HMesh
13 
{
 20 
{
14 
  void get_candidates(const VertexIter& v,
 21 
    using namespace std;
15 
											vector<HalfEdgeIter>& candidates)
 22 
    using namespace CGLA;
16
- 
 
17
23 
 
- 
 
 24 
    void get_candidates(const Manifold& m, VertexID v, vector<HalfEdgeID>& candidates)
18 
  {
 25 
    {
19 
    vector<VertexIter> vertices;
 26 
        vector<VertexID> vertices;
20 
    vector<HalfEdgeIter> hedges;
 27 
        vector<HalfEdgeID> hedges;
21
28 
 
22 
    VertexCirculator vc(v);
 29 
        Walker wv = m.walker(v);
23 
    for(;!vc.end();++vc)
 30 
        for(;!wv.full_circle(); wv = wv.circulate_vertex_cw()){
24 
      {
 - 
 
25 
				vertices.push_back(vc.get_vertex());
 31 
            vertices.push_back(wv.vertex());
26 
				hedges.push_back(vc.get_halfedge());
 32 
            hedges.push_back(wv.halfedge());
27 
      }
 33 
        }
28 
    size_t N = vc.no_steps();
 34 
        int N = wv.no_steps();
29 
    vector<VertexIter> vertices_check(vertices);
 35 
        vector<VertexID> vertices_check(vertices);
30 
    assert(N==vertices.size());
 36 
        assert(N == vertices.size());
31 
 
 37 
 
32 
    for(int i=N-1;i>=0;--i)
 38 
        for(int i = N - 1; i >= 0; --i){
33 
      {
 - 
 
34 
				HalfEdgeIter h = hedges[i]->next;
 - 
 
35 
				while(h->vert != vertices[(i+N-1)%N])
 39 
            for(Walker w = m.walker(hedges[i]).next(); w.vertex() != vertices[(i+N-1)%N]; w = w.next()){
36 
					{
 - 
 
37 
						if(find(vertices_check.begin(),vertices_check.end(),
40 
                if(find(vertices_check.begin(), vertices_check.end(), w.vertex()) == vertices_check.end())
38 
										h->vert) == vertices_check.end())
 - 
 
39 
							candidates.push_back(h);
 41 
                    candidates.push_back(w.halfedge());
40 
						h = h->next;
 - 
 
41
- 
 
42 
						// TODO : does not compile in debug mode in visual studio
 - 
 
43 
						//assert(h!=v);
 - 
 
44 
					}
 42 
            }
45 
      }
 43 
        }
46 
  }
 44 
    }
47 
 
 45 
 
48 
  float curv(const Vec3f& p, std::vector<Vec3f>& vec)
 46 
    float curv(const Vec3d& p, vector<Vec3d>& vec)
49 
  {
 - 
 
50 
    int N = vec.size();
 - 
 
51 
    std::vector<Vec3f> normals;
 - 
 
52 
    for(int i=0;i<N;++i)
 - 
 
53 
      {
 47 
    {
54
48 
        size_t N = vec.size();
- 
 
 49 
        std::vector<Vec3d> normals;
- 
 
 50 
        for(size_t i = 0; i < N; ++i){
55 
				Vec3f norm = normalize(cross(vec[i]-p, vec[(i+1)%N]-p));
 51 
            Vec3d norm = normalize(cross(vec[i]-p, vec[(i+1)%N]-p));
56 
				normals.push_back(norm);
 52 
            normals.push_back(norm);
57 
      }
 53 
        }
58 
    float alpha = 0;
 54 
        float alpha = 0;
59 
    for(int i=0;i<N;++i)
 55 
        for(size_t i = 0; i < N; ++i)
60 
      {
 - 
 
61 
				alpha += (vec[i]-p).length()*acos(dot(normals[i],normals[(i+1)%N]));
 56 
            alpha += (vec[i]-p).length()*acos(dot(normals[i],normals[(i+1)%N]));
62 
      }
 57 
 
63 
    return alpha;
 58 
        return alpha;
64 
  }
 59 
    }
65 
 
 60 
 
66 
  float get_badness(const VertexIter& v, const VertexIter& n)
 61 
    float get_badness(const Manifold& m, VertexID v, VertexID n)
67 
  {
 62 
    {
68 
    vector<HalfEdgeIter> hedges;
 63 
        vector<HalfEdgeID> hedges;
69
64 
 
70 
    VertexCirculator vc(v);
 65 
        Walker wv = m.walker(v);
71 
    for(;!vc.end();++vc)
 66 
        for(; !wv.full_circle(); wv = wv.circulate_vertex_cw())
72 
      hedges.push_back(vc.get_halfedge());
 67 
            hedges.push_back(wv.halfedge());
73 
 
 68 
 
74 
    vector<Vec3f> one_ring;
 69 
        vector<Vec3d> one_ring;
75 
    vector<Vec3f> one_ring_n;
 70 
        vector<Vec3d> one_ring_n;
76 
    int N = vc.no_steps();
 71 
        int N = wv.no_steps();
77 
    for(int i=N-1;i>=0;--i)
 72 
        for(int i = N - 1; i >= 0; --i){
78 
      {
 - 
 
79 
				HalfEdgeIter h = hedges[i];
 73 
            for(Walker w = m.walker(hedges[i]).next(); w.vertex() != v; w = w.next()){
80 
				h = h->next;
 - 
 
81 
				while(h->vert != v)
 - 
 
82 
					{
 - 
 
83 
						one_ring.push_back(h->vert->pos);
 74 
                one_ring.push_back(m.pos(w.vertex()));
84 
						if(h->vert != n)
 75 
                if(w.vertex() != n)
85 
							one_ring_n.push_back(h->vert->pos);
 76 
                    one_ring_n.push_back(m.pos(w.vertex()));
86 
						h = h->next;
 - 
 
87 
					}
 77 
            }
88 
      }
 78 
        }
89 
    return curv(v->pos,one_ring)-curv(v->pos,one_ring_n);
 79 
        return curv(m.pos(v), one_ring) - curv(m.pos(v), one_ring_n);
90 
  }
 80 
    }
91 
 
 81 
 
92 
 
 82 
 
93 
  const CGLA::Vec3f get_normal(const VertexIter& v)
 83 
    const CGLA::Vec3d get_normal(const Manifold& m, VertexID v)
94 
  {
 84 
    {
95 
 
 85 
 
96 
    vector<HalfEdgeIter> hedges;
 86 
        vector<HalfEdgeID> hedges;
97
87 
 
98 
    VertexCirculator vc(v);
 88 
        Walker wv = m.walker(v);
99 
    for(;!vc.end();++vc)
 89 
        for(; !wv.full_circle(); wv = wv.circulate_vertex_cw())
100 
      hedges.push_back(vc.get_halfedge());
 90 
            hedges.push_back(wv.halfedge());
101 
 
 91 
 
102 
    vector<Vec3f> one_ring;
 92 
        vector<Vec3d> one_ring;
103 
    int N = vc.no_steps();
 93 
        size_t N = wv.no_steps();
104 
    for(int i=N-1;i>=0;--i)
 94 
        for(int i = N - 1; i >= 0; --i){
105 
      {
 - 
 
106 
				HalfEdgeIter h = hedges[i];
 95 
            for(Walker w = m.walker(hedges[i]).next(); w.vertex() != v; w = w.next())
107 
				h = h->next;
 - 
 
108 
				while(h->vert != v)
 - 
 
109 
					{
 - 
 
110 
						one_ring.push_back(h->vert->pos);
 96 
                one_ring.push_back(m.pos(w.vertex()));
111 
						h = h->next;
 - 
 
112 
					}
 97 
        }
113 
      }
 98 
 
114 
    Vec3f norm(0);
 99 
        Vec3d norm(0);
115 
    N= one_ring.size();
 100 
        N = one_ring.size();
116 
    Vec3f p0 = v->pos;
 101 
        Vec3d p0 = m.pos(v);
117 
    for(int i=0;i<N;++i)
 102 
        for(int i = 0; i < N; ++i){
118 
      {
 - 
 
119 
				Vec3f p1 = one_ring[i];
 103 
            Vec3d p1 = one_ring[i];
120 
				Vec3f p2 = one_ring[(i+1)%N];
 104 
            Vec3d p2 = one_ring[(i+1) % N];
121 
				Vec3f e0 = normalize(p1-p0);
 105 
            Vec3d e0 = normalize(p1 - p0);
122 
				Vec3f e1 = normalize(p2-p0);
 106 
            Vec3d e1 = normalize(p2 - p0);
123 
				norm += cross(e0,e1)*acos(dot(e0,e1));
 107 
            norm += cross(e0, e1) * acos(dot(e0, e1));
124 
      }
 108 
        }
125 
    return normalize(norm);
 109 
        return normalize(norm);
126 
  }
 110 
    }
127 
 
 111 
 
128 
  void safe_triangulate(Manifold& m)
 112 
    void triangulate_by_vertex_face_split(Manifold& m)
129 
  {
 113 
    {
130 
    vector<FaceIter> fv;
 114 
        vector<FaceID> fv;
131 
    for(FaceIter  fi=m.faces_begin(); fi != m.faces_end(); ++fi)
 115 
        fv.reserve(m.no_faces());
132 
      fv.push_back(fi);
 116 
        copy(m.faces_begin(), m.faces_end(), back_inserter(fv));
- 
 
 117 
 
133 
    for(size_t i=0;i<fv.size();++i)
 118 
        for(size_t i = 0; i < fv.size(); ++i)
134 
      m.safe_triangulate(fv[i]);
 119 
            m.split_face_by_vertex(fv[i]);
135 
  }
 120 
    }
136 
 
 121 
 
137 
  void triangulate(Manifold& m)
 122 
    void triangulate_by_edge_face_split(Manifold& m)
138 
  {
 123 
    {
139 
    vector<FaceIter> fv;
 124 
        vector<FaceID> fv;
140 
    for(FaceIter  fi=m.faces_begin(); fi != m.faces_end(); ++fi)
 125 
        fv.reserve(m.no_faces());
141 
      fv.push_back(fi);
 126 
        copy(m.faces_begin(), m.faces_end(), back_inserter(fv));
- 
 
 127 
 
142 
    for(size_t i=0;i<fv.size();++i)
 128 
        for(size_t i = 0; i < fv.size(); ++i)
143 
      m.triangulate(fv[i]);
 129 
            triangulate_face_by_edge_split(m, fv[i]);
144 
  }
 130 
    }
145 
 
 131 
 
146 
  struct PotentialEdge
 132 
    struct PotentialEdge
147 
  {
 133 
    {
148 
    int time_tag;
 134 
        int time_tag;
149 
    float badness;
 135 
        float badness;
150 
    FaceIter f;
 136 
        FaceID f;
151 
    VertexIter v0, v1;
 137 
        VertexID v0, v1;
152 
  };
 138 
    };
153 
 
 139 
 
154 
  bool operator>(const PotentialEdge& e0, const PotentialEdge& e1)
 140 
    bool operator>(const PotentialEdge& e0, const PotentialEdge& e1)
155 
  {
 - 
 
156 
    return e0.badness>e1.badness;
 141 
    { return e0.badness>e1.badness; }
157 
  }
 - 
 
158 
 
 142 
 
159 
  typedef std::priority_queue<PotentialEdge,
 143 
    typedef std::priority_queue<PotentialEdge,
160 
															std::vector<PotentialEdge>,
 144 
        std::vector<PotentialEdge>,
161 
															std::greater<PotentialEdge> >
145 
        std::greater<PotentialEdge> >
162 
  PotentialEdgeQueue;
 146 
        PotentialEdgeQueue;
163 
 
 147 
 
164 
  void insert_potential_edges(const VertexIter& v,
 148 
    void insert_potential_edges(const Manifold& m, VertexAttributeVector<int>& vtouched, VertexID v, PotentialEdgeQueue& pot_edges)
165 
															PotentialEdgeQueue& pot_edges)
 - 
 
166 
  {
 149 
    {
167 
    vector<Vec3f> one_ring;
 150 
        vector<Vec3d> one_ring;
168 
    vector<HalfEdgeIter> candidates;
 151 
        vector<HalfEdgeID> candidates;
169 
    get_candidates(v, candidates);
 152 
        get_candidates(m, v, candidates);
170 
 
 153 
 
171 
    Vec3f p0 = v->pos;
 154 
        Vec3d p0 = m.pos(v);
172 
    Vec3f norm = normal(v);
 155 
        Vec3d norm = normal(m, v);
173 
    int n = candidates.size();
 156 
        int n = candidates.size();
174 
    for(int i=0;i<n;++i)
 157 
        for(int i = 0; i < n; ++i){
175 
      {
 158 
            Walker w = m.walker(candidates[i]);
176 
				VertexIter v_n = candidates[i]->vert;
 159 
            VertexID v_n = w.vertex();
177 
				Vec3f edir = normalize(v_n->pos-p0);
 160 
            Vec3d edir = normalize(m.pos(v_n) - p0);
178 
				Vec3f norm_n = normal(v_n);
 161 
            Vec3d norm_n = normal(m, v_n);
179 
				float bad = sqr(dot(edir, norm));
 162 
            float bad = sqr(dot(edir, norm));
180 
				float bad_n = sqr(dot(edir, norm_n));
 163 
            float bad_n = sqr(dot(edir, norm_n));
181
164 
 
182 
				PotentialEdge pot;
 165 
            PotentialEdge pot;
183 
 
 166 
 
184 
				/* So if the edge between two vertices is not orthogonal to
167 
            /* So if the edge between two vertices is not orthogonal to
185 
					 their normals, the badness is increased. Badness is also
 168 
            their normals, the badness is increased. Badness is also
186 
					 increased if the normals are very different. */
 169 
            increased if the normals are very different. */
187 
 
 170 
 
188 
				pot.badness = bad+bad_n - dot(norm_n,norm);
 171 
            pot.badness = bad+bad_n - dot(norm_n,norm);
189 
				pot.time_tag = v->touched;
 172 
            pot.time_tag = vtouched[v];
190 
				pot.v0 = v;
 173 
            pot.v0 = v;
191 
				pot.v1 = candidates[i]->vert;
 174 
            pot.v1 = w.vertex();
192 
				pot.f = candidates[i]->face;
 175 
            pot.f = w.face();
193
176 
 
194 
				pot_edges.push(pot);
 177 
            pot_edges.push(pot);
195 
      }
 178 
        }
196 
  }
 179 
    }
197 
 
 180 
 
198
- 
 
199 
  void create_candidates(Manifold& m, PotentialEdgeQueue& pot_edges)
 - 
 
200 
  {
 - 
 
201 
    for(VertexIter v= m.vertices_begin(); v!= m.vertices_end();++v)
 - 
 
202 
      {
 - 
 
203 
				v->touched = 0;
 - 
 
204 
				insert_potential_edges(v, pot_edges);
 - 
 
205 
      }
 - 
 
206 
  }
 - 
 
207 
 
 - 
 
208
- 
 
209 
 
 - 
 
210 
 
 - 
 
211 
  void curvature_triangulate(Manifold& m)
 181 
    void curvature_triangulate(Manifold& m)
212 
  {
 182 
    {
213 
    PotentialEdgeQueue pot_edges;
 183 
        PotentialEdgeQueue pot_edges;
- 
 
 184 
        VertexAttributeVector<int> vtouched(m.allocated_vertices(), 0);
214 
 
 185 
 
215 
    // Create candidates
 186 
        // Create candidates
- 
 
 187 
        for(VertexIDIterator v = m.vertices_begin(); v!= m.vertices_end(); ++v)
216 
    create_candidates(m,pot_edges);
 188 
            insert_potential_edges(m, vtouched, *v, pot_edges);
217
189 
 
218 
    while(!pot_edges.empty())
 190 
        while(!pot_edges.empty()){
219 
      {
 - 
 
220 
				const PotentialEdge& pot_edge = pot_edges.top();
 191 
            const PotentialEdge& pot_edge = pot_edges.top();
221 
 
 - 
 
222 
				// Record all the vertices of the face. We need to
192 
            // Record all the vertices of the face. We need to
223 
				// recompute the candidates.
 193 
            // recompute the candidates.
224 
				std::vector<VertexIter> reeval_vec;
 194 
            std::vector<VertexID> reeval_vec;
225 
				FaceCirculator fc(pot_edge.f);
 - 
 
226 
				while(!fc.end())
 - 
 
227 
					{
 - 
 
228 
						reeval_vec.push_back(fc.get_vertex());
 - 
 
229 
						++fc;
 - 
 
230 
					}
 - 
 
231 
 
 195 
 
- 
 
 196 
            for(Walker w = m.walker(pot_edge.f); !w.full_circle(); w = w.circulate_face_cw())
232 
				VertexIter v0 = pot_edge.v0;
 197 
                reeval_vec.push_back(w.vertex());
233 
 
 198 
 
234 
				// Make sure that the vertex has not been touched since
199 
            // Make sure that the vertex has not been touched since
235 
				// we created the potential edge. If the vertex has been
 200 
            // we created the potential edge. If the vertex has been
236 
				// touched the candidate edge has either (a) been processed,
 201 
            // touched the candidate edge has either (a) been processed,
237 
				// (b) received a lower priority or (c) become invalid.
 202 
            // (b) received a lower priority or (c) become invalid.
238 
				if(pot_edge.time_tag == v0->touched)
 203 
            if(pot_edge.time_tag == vtouched[pot_edge.v0]){
239 
					{
 - 
 
240 
						VertexIter v1 = pot_edge.v1;
 - 
 
241 
 
 - 
 
242 
						vector<Vec3f> one_ring;
 204 
                vector<Vec3d> one_ring;
243 
						vector<HalfEdgeIter> candidates;
 205 
                vector<HalfEdgeID> candidates;
244
206 
 
245 
						m.split_face(pot_edge.f, v0, v1);
 207 
                m.split_face_by_edge(pot_edge.f, pot_edge.v0, pot_edge.v1);
246 
 
 208 
 
247 
						// Recompute priorities.
 209 
                // Recompute priorities.
248 
						for(size_t i=0;i<reeval_vec.size();++i)
 210 
                for(size_t i = 0; i < reeval_vec.size(); ++i){
249 
							{
 - 
 
250 
								VertexIter& v = reeval_vec[i];
 211 
                    VertexID& v = reeval_vec[i];
251 
								v->touched++;
 212 
                    ++vtouched[v];
252 
								insert_potential_edges(v, pot_edges);
 213 
                    insert_potential_edges(m, vtouched, v, pot_edges);
253 
							}
 214 
                }
254
215 
 
255 
					}
 216 
            }
256 
				pot_edges.pop();
 217 
            pot_edges.pop();
257 
      }
 218 
        }
Line 259... Line 220...
259 
  }
 220 
    }
260 
 
 221 
 
261 
		void shortest_edge_triangulate(Manifold& m)
 222 
    void shortest_edge_triangulate(Manifold& m)
262 
		{
 223 
    {
263 
			int work;
 224 
        int work;
264 
			do
 225 
        do{
265 
				{
 - 
 
266 
					// For every face.
 226 
            // For every face.
267 
					work = 0;
 227 
            work = 0;
268 
					for(FaceIter fi =m.faces_begin(); fi != m.faces_end(); ++fi)
 228 
            for(FaceIDIterator f = m.faces_begin(); f != m.faces_end(); ++f){
269 
						{
 - 
 
270 
							// Create a vector of vertices.
 229 
                // Create a vector of vertices.
271 
							vector<VertexIter> verts;
 230 
                vector<VertexID> verts;
- 
 
 231 
                for(Walker w = m.walker(*f); !w.full_circle(); w = w.circulate_face_ccw())
- 
 
 232 
				{
272 
							for(FaceCirculator fc(fi); !fc.end(); ++fc)
 233 
					FaceID fa = w.face();
- 
 
 234 
					FaceID fb = *f;
- 
 
 235 
					assert(fa==fb);
273 
								verts.push_back(fc.get_vertex());
 236 
                    verts.push_back(w.vertex());
274
237 
				}
275 
							// If there are just three we are done.
 238 
                // If there are just three we are done.
276 
							if(verts.size() == 3) continue;
 239 
                if(verts.size() == 3) continue;
277
240 
 
278 
							// Find vertex pairs that may be connected.
 241 
                // Find vertex pairs that may be connected.
279 
							vector<pair<int,int> > vpairs;
 242 
                vector<pair<int,int> > vpairs;
280 
							const int N = verts.size();
 243 
                const int N = verts.size();
281 
							for(int i=0;i<N-2;++i)
 244 
                for(int i = 0; i < N - 2; ++i){
282 
								for(int j=i+2;j<N; ++j)
 245 
                    for(int j = i + 2; j < N; ++j){
283 
									if(!is_connected(verts[i], verts[j]))
 246 
                        if(verts[i] != verts[j] && !connected(m, verts[i], verts[j]))
284 
										vpairs.push_back(pair<int,int>(i,j));
 247 
                            vpairs.push_back(pair<int,int>(i, j));
- 
 
 248 
                    }
285
249 
                }
286 
							if(vpairs.empty())
 250 
                if(vpairs.empty()){
287 
								{
 - 
 
288 
									cout << "Warning: could not triangulate a face."
251 
                    cout << "Warning: could not triangulate a face."
289 
											 << "Probably a vertex appears more than one time in other vertex's one-ring" << endl;
 252 
                        << "Probably a vertex appears more than one time in other vertex's one-ring" << endl;
290 
									continue;
 253 
                    continue;
291 
								}
 254 
                }
292
255 
 
293 
							/* For all vertex pairs, find the edge lengths. Combine the
 256 
                /* For all vertex pairs, find the edge lengths. Combine the
294 
								 vertices forming the shortest edge. */
 257 
                vertices forming the shortest edge. */
295
258 
 
296 
							float min_len=FLT_MAX;
 259 
                float min_len=FLT_MAX;
297 
							int min_k = -1;
 260 
                int min_k = -1;
298 
							for(size_t k=0;k<vpairs.size(); ++k)
 261 
                for(size_t k = 0; k < vpairs.size(); ++k){
299 
								{
 - 
 
300 
									int i = vpairs[k].first;
 262 
                    int i = vpairs[k].first;
301 
									int j = vpairs[k].second;
 263 
                    int j = vpairs[k].second;
302 
									float len = sqr_length(verts[i]->pos-verts[j]->pos);
 264 
                    float len = sqr_length(m.pos(verts[i]) - m.pos(verts[j]));
303
265 
 
304 
									if(len<min_len)
 266 
                    if(len<min_len){
305 
										{
 - 
 
306 
											min_len = len;
 267 
                        min_len = len;
307 
											min_k = k;
 268 
                        min_k = k;
308 
										}
 269 
                    }
309 
								}
 270 
                }
310 
							assert(min_k != -1);
 271 
                assert(min_k != -1);
311
272 
 
312 
							{
 273 
                {
313 
								// Split faces along edge whose midpoint is closest to isovalue
 274 
                    // Split faces along edge whose midpoint is closest to isovalue
314 
								int i = vpairs[min_k].first;
 275 
                    int i = vpairs[min_k].first;
315 
								int j = vpairs[min_k].second;
 276 
                    int j = vpairs[min_k].second;
316 
								m.split_face(fi, verts[i], verts[j]);
 277 
                    m.split_face_by_edge(*f, verts[i], verts[j]);
317 
							}
 278 
                }
318 
							++work;
 279 
                ++work;
319
280 
 
320 
						}
 281 
            }
321 
				}
 282 
        }
322 
			while(work);
 283 
        while(work);
323 
		}
 284 
    }
324 
 
 285 
 
- 
 
 286 
    void triangulate_face_by_edge_split(Manifold& m, FaceID f)
- 
 
 287 
    {
- 
 
 288 
        if(no_edges(m, f)<=3)
- 
 
 289 
            return;
325 
 
 290
- 
 
 291 
        Walker w = m.walker(f);
326 
 
 292 
 
- 
 
 293 
        // as long as f is not a triangle
- 
 
 294 
        while(w.next().next().next().halfedge() != w.halfedge()){
- 
 
 295 
            // assert that face has at least 3 edges
- 
 
 296 
            // f is split into triangle from first three vertices, and becomes remaining polygon in next iteration
- 
 
 297 
            assert(w.next().next().halfedge() != w.halfedge());
- 
 
 298 
            VertexID v0 = w.vertex();
- 
 
 299 
            VertexID v1 = w.next().next().vertex();
- 
 
 300 
            FaceID f_old = f;
- 
 
 301 
            if(v0 != v1 && !connected(m, v0, v1))
- 
 
 302 
                f = m.split_face_by_edge(f, v0, v1);
- 
 
 303 
            if(f == f_old)
- 
 
 304 
                return;
- 
 
 305 
        }
327 
 
 306 
    }
328 
}
 307 
}