1
2
3 // DO NOT EDIT !
4 // This file is generated using the MantaFlow preprocessor (prep generate).
5
6 /******************************************************************************
7 *
8 * MantaFlow fluid solver framework
9 * Copyright 2011 Tobias Pfaff, Nils Thuerey
10 *
11 * This program is free software, distributed under the terms of the
12 * Apache License, Version 2.0
13 * http://www.apache.org/licenses/LICENSE-2.0
14 *
15 * Mesh edge collapse and subdivision
16 *
17 ******************************************************************************/
18
19 /******************************************************************************/
20 // Copyright note:
21 //
22 // These functions (C) Chris Wojtan
23 // Long-term goal is to unify with his split&merge codebase
24 //
25 /******************************************************************************/
26
27 #include "edgecollapse.h"
28 #include <queue>
29
30 using namespace std;
31
32 namespace Manta {
33
34 // 8-point butterfly subdivision scheme (as described by Brochu&Bridson 2009)
ButterflySubdivision(Mesh & m,const Corner & ca,const Corner & cb)35 Vec3 ButterflySubdivision(Mesh &m, const Corner &ca, const Corner &cb)
36 {
37 Vec3 p = m.nodes(m.corners(ca.prev).node).pos + m.nodes(m.corners(ca.next).node).pos;
38 Vec3 q = m.nodes(ca.node).pos + m.nodes(cb.node).pos;
39 Vec3 r = m.nodes(m.corners(m.corners(ca.next).opposite).node).pos +
40 m.nodes(m.corners(m.corners(ca.prev).opposite).node).pos +
41 m.nodes(m.corners(m.corners(cb.next).opposite).node).pos +
42 m.nodes(m.corners(m.corners(cb.prev).opposite).node).pos;
43 return (8 * p + 2 * q - r) / 16.0;
44 }
45
46 // Modified Butterfly Subdivision Scheme from:
47 // Interpolating Subdivision for Meshes with Arbitrary Topology
48 // Denis Zorin, Peter Schroder, and Wim Sweldens
49 // input the Corner that satisfies the following:
50 // c.prev.node is the extraordinary vertex,
51 // and c.next.node is the other vertex involved in the subdivision
OneSidedButterflySubdivision(Mesh & m,const int valence,const Corner & c)52 Vec3 OneSidedButterflySubdivision(Mesh &m, const int valence, const Corner &c)
53 {
54 Vec3 out;
55 Vec3 p0 = m.nodes(m.corners(c.prev).node).pos;
56 Vec3 p1 = m.nodes(m.corners(c.next).node).pos;
57
58 if (valence == 3) {
59 Vec3 p2 = m.nodes(c.node).pos;
60 Vec3 p3 = m.nodes(m.corners(m.corners(c.next).opposite).node).pos;
61 out = (5.0 / 12.0) * p1 - (1.0 / 12.0) * (p2 + p3) + 0.75 * p0;
62 }
63 else if (valence == 4) {
64 Vec3 p2 = m.nodes(m.corners(m.corners(c.next).opposite).node).pos;
65 out = 0.375 * p1 - 0.125 * p2 + 0.75 * p0;
66 }
67 else {
68 // rotate around extraordinary vertex,
69 // calculate subdivision weights,
70 // and interpolate vertex position
71 double rv = 1.0 / (double)valence;
72 out = 0.0;
73 int current = c.prev;
74 for (int j = 0; j < valence; j++) {
75 double s = (0.25 + cos(2 * M_PI * j * rv) + 0.5 * cos(4 * M_PI * j * rv)) * rv;
76 Vec3 p = m.nodes(m.corners(m.corners(current).prev).node).pos;
77
78 out += s * p;
79 current = m.corners(m.corners(m.corners(current).next).opposite).next;
80 }
81 out += 0.75 * m.nodes(m.corners(c.prev).node).pos;
82 }
83 return out;
84 }
85
86 // Modified Butterfly Subdivision Scheme from:
87 // Interpolating Subdivision for Meshes with Arbitrary Topology
88 // Denis Zorin, Peter Schroder, and Wim Sweldens
ModifiedButterflySubdivision(Mesh & m,const Corner & ca,const Corner & cb,const Vec3 & fallback)89 Vec3 ModifiedButterflySubdivision(Mesh &m,
90 const Corner &ca,
91 const Corner &cb,
92 const Vec3 &fallback)
93 {
94 // calculate the valence of the two parent vertices
95 int start = ca.prev;
96 int current = start;
97 int valenceA = 0;
98 do {
99 valenceA++;
100 int op = m.corners(m.corners(current).next).opposite;
101 if (op < 0)
102 return fallback;
103 current = m.corners(op).next;
104 } while (current != start);
105 start = ca.next;
106 current = start;
107 int valenceB = 0;
108 do {
109 valenceB++;
110 int op = m.corners(m.corners(current).next).opposite;
111 if (op < 0)
112 return fallback;
113 current = m.corners(op).next;
114 } while (current != start);
115
116 // if both vertices have valence 6, use butterfly subdivision
117 if (valenceA == 6 && valenceB == 6) {
118 return ButterflySubdivision(m, ca, cb);
119 }
120 else if (valenceA == 6) // use a one-sided scheme
121 {
122 return OneSidedButterflySubdivision(m, valenceB, cb);
123 }
124 else if (valenceB == 6) // use a one-sided scheme
125 {
126 return OneSidedButterflySubdivision(m, valenceA, ca);
127 }
128 else // average the results from two one-sided schemes
129 {
130 return 0.5 * (OneSidedButterflySubdivision(m, valenceA, ca) +
131 OneSidedButterflySubdivision(m, valenceB, cb));
132 }
133 }
134
135 bool gAbort = false;
136
137 // collapse an edge on triangle "trinum".
138 // "which" is 0,1, or 2,
139 // where which==0 is the triangle edge from p0 to p1,
140 // which==1 is the triangle edge from p1 to p2,
141 // and which==2 is the triangle edge from p2 to p0,
CollapseEdge(Mesh & m,const int trinum,const int which,const Vec3 & edgevect,const Vec3 & endpoint,vector<int> & deletedNodes,std::map<int,bool> & taintedTris,int & numCollapses,bool doTubeCutting)142 void CollapseEdge(Mesh &m,
143 const int trinum,
144 const int which,
145 const Vec3 &edgevect,
146 const Vec3 &endpoint,
147 vector<int> &deletedNodes,
148 std::map<int, bool> &taintedTris,
149 int &numCollapses,
150 bool doTubeCutting)
151 {
152 if (gAbort)
153 return;
154 // I wanted to draw a pretty picture of an edge collapse,
155 // but I don't know how to make wacky angled lines in ASCII.
156 // Instead, I will show the before case and tell you what needs to be done.
157
158 // BEFORE:
159 // *
160 // / \.
161 // /C0 \.
162 // / \.
163 // / \.
164 // / B \.
165 // / \.
166 // /C1 C2 \.
167 // P0 *---------------* P1
168 // \C2 C1 /
169 // \ /
170 // \ A /
171 // \ /
172 // \ /
173 // \C0 /
174 // \ /
175 // *
176 //
177 // We are going to collapse the edge between P0 and P1
178 // by deleting P1,
179 // and taking all references to P1,
180 // and rerouting them to P0 instead
181 //
182 // What we need to do:
183 // Move position of P0
184 // Preserve connectivity in both triangles:
185 // (C1.opposite).opposite = C2.o
186 // (C2.opposite).opposite = C1.o
187 // Delete references to Corners of deleted triangles in both P0 and P1's Corner list
188 // Reassign references to P1:
189 // loop through P1 triangles:
190 // rename P1 references to P0 in p lists.
191 // rename Corner.v references
192 // Copy P1's list of Corners over to P0's list of Corners
193 // Delete P1
194
195 Corner ca_old[3], cb_old[3];
196 ca_old[0] = m.corners(trinum, which);
197 ca_old[1] = m.corners(ca_old[0].next);
198 ca_old[2] = m.corners(ca_old[0].prev);
199 bool haveB = false;
200 if (ca_old[0].opposite >= 0) {
201 cb_old[0] = m.corners(ca_old[0].opposite);
202 cb_old[1] = m.corners(cb_old[0].next);
203 cb_old[2] = m.corners(cb_old[0].prev);
204 haveB = true;
205 }
206 if (!haveB) {
207 // for now, don't collapse
208 return;
209 }
210
211 int P0 = ca_old[2].node;
212 int P1 = ca_old[1].node;
213
214 ///////////////
215 // avoid creating nonmanifold edges
216 bool nonmanifold = false;
217 bool nonmanifold2 = false;
218
219 set<int> &ring0 = m.get1Ring(P0).nodes;
220 set<int> &ring1 = m.get1Ring(P1).nodes;
221
222 // check for intersections of the 1-rings of P0,P1
223 int cl = 0, commonVert = -1;
224 for (set<int>::iterator it = ring1.begin(); it != ring1.end(); ++it)
225 if (ring0.find(*it) != ring0.end()) {
226 cl++;
227 if (*it != ca_old[0].node && *it != cb_old[0].node)
228 commonVert = *it;
229 }
230
231 nonmanifold = cl > 2;
232 nonmanifold2 = cl > 3;
233
234 if (nonmanifold && ca_old[1].opposite >= 0 && cb_old[1].opposite >= 0 &&
235 ca_old[2].opposite >= 0 &&
236 cb_old[2].opposite >= 0) // collapsing this edge would create a non-manifold edge
237 {
238 if (nonmanifold2)
239 return;
240
241 bool topTet = false;
242 bool botTet = false;
243 // check if collapsing this edge will collapse a tet.
244 if (m.corners(ca_old[1].opposite).node == m.corners(ca_old[2].opposite).node)
245 botTet = true;
246
247 if (m.corners(cb_old[1].opposite).node == m.corners(cb_old[2].opposite).node)
248 topTet = true;
249
250 if (topTet ^ botTet) {
251
252 // safe pyramid case.
253 // collapse the whole tet!
254 // First collapse the top of the pyramid,
255 // then carry on collapsing the original verts.
256 Corner cc_old[3], cd_old[3];
257 if (botTet)
258 cc_old[0] = m.corners(ca_old[1].opposite);
259 else // topTet
260 cc_old[0] = cb_old[2];
261 cc_old[1] = m.corners(cc_old[0].next);
262 cc_old[2] = m.corners(cc_old[0].prev);
263 if (cc_old[0].opposite < 0)
264 return;
265 cd_old[0] = m.corners(cc_old[0].opposite);
266 cd_old[1] = m.corners(cd_old[0].next);
267 cd_old[2] = m.corners(cd_old[0].prev);
268 int P2 = cc_old[2].node;
269 int P3 = cc_old[1].node;
270
271 // update tri props of all adjacent triangles of P0,P1 (do before CT updates!)
272 for (int i = 0; i < m.numTriChannels(); i++) {
273 }; // TODO: handleTriPropertyEdgeCollapse(trinum, P2,P3, cc_old[0], cd_old[0]);
274
275 m.mergeNode(P2, P3);
276
277 // Preserve connectivity in both triangles
278 if (cc_old[1].opposite >= 0)
279 m.corners(cc_old[1].opposite).opposite = cc_old[2].opposite;
280 if (cc_old[2].opposite >= 0)
281 m.corners(cc_old[2].opposite).opposite = cc_old[1].opposite;
282 if (cd_old[1].opposite >= 0)
283 m.corners(cd_old[1].opposite).opposite = cd_old[2].opposite;
284 if (cd_old[2].opposite >= 0)
285 m.corners(cd_old[2].opposite).opposite = cd_old[1].opposite;
286
287 ////////////////////
288 // mark the two triangles and the one node for deletion
289 int tmpTrinum = cc_old[0].tri;
290 int tmpOthertri = cd_old[0].tri;
291 m.removeTriFromLookup(tmpTrinum);
292 m.removeTriFromLookup(tmpOthertri);
293 taintedTris[tmpTrinum] = true;
294 taintedTris[tmpOthertri] = true;
295 deletedNodes.push_back(P3);
296
297 numCollapses++;
298
299 // recompute Corners for triangles A and B
300 if (botTet)
301 ca_old[0] = m.corners(ca_old[2].opposite);
302 else
303 ca_old[0] = m.corners(ca_old[1].prev);
304 ca_old[1] = m.corners(ca_old[0].next);
305 ca_old[2] = m.corners(ca_old[0].prev);
306 cb_old[0] = m.corners(ca_old[0].opposite);
307 cb_old[1] = m.corners(cb_old[0].next);
308 cb_old[2] = m.corners(cb_old[0].prev);
309
310 ///////////////
311 // avoid creating nonmanifold edges... again
312 ring0 = m.get1Ring(ca_old[2].node).nodes;
313 ring1 = m.get1Ring(ca_old[1].node).nodes;
314
315 // check for intersections of the 1-rings of P0,P1
316 cl = 0;
317 for (set<int>::iterator it = ring1.begin(); it != ring1.end(); ++it)
318 if (*it != ca_old[0].node && ring0.find(*it) != ring0.end())
319 cl++;
320
321 if (cl > 2) { // nonmanifold
322 // this can happen if collapsing the first tet leads to another similar collapse that
323 // requires the collapse of a tet. for now, just move on and pick this up later.
324
325 // if the original component was very small, this first collapse could have led to a tiny
326 // piece of nonmanifold geometry. in this case, just delete everything that remains.
327 if (m.corners(ca_old[0].opposite).tri == cb_old[0].tri &&
328 m.corners(ca_old[1].opposite).tri == cb_old[0].tri &&
329 m.corners(ca_old[2].opposite).tri == cb_old[0].tri) {
330 taintedTris[ca_old[0].tri] = true;
331 taintedTris[cb_old[0].tri] = true;
332 m.removeTriFromLookup(ca_old[0].tri);
333 m.removeTriFromLookup(cb_old[0].tri);
334 deletedNodes.push_back(ca_old[0].node);
335 deletedNodes.push_back(ca_old[1].node);
336 deletedNodes.push_back(ca_old[2].node);
337 }
338 return;
339 }
340 }
341 else if (topTet && botTet && ca_old[1].opposite >= 0 && ca_old[2].opposite >= 0 &&
342 cb_old[1].opposite >= 0 && cb_old[2].opposite >= 0) {
343 if (!(m.corners(ca_old[1].opposite).node == m.corners(ca_old[2].opposite).node &&
344 m.corners(cb_old[1].opposite).node == m.corners(cb_old[2].opposite).node &&
345 (m.corners(ca_old[1].opposite).node == m.corners(cb_old[1].opposite).node ||
346 (m.corners(ca_old[1].opposite).node == cb_old[0].node &&
347 m.corners(cb_old[1].opposite).node == ca_old[0].node)))) {
348 // just collapse one for now.
349
350 // collapse the whole tet!
351 // First collapse the top of the pyramid,
352 // then carry on collapsing the original verts.
353 Corner cc_old[3], cd_old[3];
354
355 // collapse top
356 {
357 cc_old[0] = m.corners(ca_old[1].opposite);
358 cc_old[1] = m.corners(cc_old[0].next);
359 cc_old[2] = m.corners(cc_old[0].prev);
360 if (cc_old[0].opposite < 0)
361 return;
362 cd_old[0] = m.corners(cc_old[0].opposite);
363 cd_old[1] = m.corners(cd_old[0].next);
364 cd_old[2] = m.corners(cd_old[0].prev);
365 int P2 = cc_old[2].node;
366 int P3 = cc_old[1].node;
367
368 // update tri props of all adjacent triangles of P0,P1 (do before CT updates!)
369 // TODO: handleTriPropertyEdgeCollapse(trinum, P2,P3, cc_old[0], cd_old[0]);
370
371 m.mergeNode(P2, P3);
372
373 // Preserve connectivity in both triangles
374 if (cc_old[1].opposite >= 0)
375 m.corners(cc_old[1].opposite).opposite = cc_old[2].opposite;
376 if (cc_old[2].opposite >= 0)
377 m.corners(cc_old[2].opposite).opposite = cc_old[1].opposite;
378 if (cd_old[1].opposite >= 0)
379 m.corners(cd_old[1].opposite).opposite = cd_old[2].opposite;
380 if (cd_old[2].opposite >= 0)
381 m.corners(cd_old[2].opposite).opposite = cd_old[1].opposite;
382
383 ////////////////////
384 // mark the two triangles and the one node for deletion
385 int tmpTrinum = cc_old[0].tri;
386 int tmpOthertri = cd_old[0].tri;
387 taintedTris[tmpTrinum] = true;
388 taintedTris[tmpOthertri] = true;
389 m.removeTriFromLookup(tmpTrinum);
390 m.removeTriFromLookup(tmpOthertri);
391 deletedNodes.push_back(P3);
392
393 numCollapses++;
394 }
395 // then collapse bottom
396 {
397 // cc_old[0] = [ca_old[1].opposite;
398 cc_old[0] = cb_old[2];
399 cc_old[1] = m.corners(cc_old[0].next);
400 cc_old[2] = m.corners(cc_old[0].prev);
401 if (cc_old[0].opposite < 0)
402 return;
403 cd_old[0] = m.corners(cc_old[0].opposite);
404 cd_old[1] = m.corners(cd_old[0].next);
405 cd_old[2] = m.corners(cd_old[0].prev);
406 int P2 = cc_old[2].node;
407 int P3 = cc_old[1].node;
408
409 // update tri props of all adjacent triangles of P0,P1 (do before CT updates!)
410 // TODO: handleTriPropertyEdgeCollapse(trinum, P2,P3, cc_old[0], cd_old[0]);
411
412 m.mergeNode(P2, P3);
413
414 // Preserve connectivity in both triangles
415 if (cc_old[1].opposite >= 0)
416 m.corners(cc_old[1].opposite).opposite = cc_old[2].opposite;
417 if (cc_old[2].opposite >= 0)
418 m.corners(cc_old[2].opposite).opposite = cc_old[1].opposite;
419 if (cd_old[1].opposite >= 0)
420 m.corners(cd_old[1].opposite).opposite = cd_old[2].opposite;
421 if (cd_old[2].opposite >= 0)
422 m.corners(cd_old[2].opposite).opposite = cd_old[1].opposite;
423
424 ////////////////////
425 // mark the two triangles and the one node for deletion
426 int tmpTrinum = cc_old[0].tri;
427 int tmpOthertri = cd_old[0].tri;
428 taintedTris[tmpTrinum] = true;
429 taintedTris[tmpOthertri] = true;
430 deletedNodes.push_back(P3);
431
432 numCollapses++;
433 }
434
435 // Though we've collapsed a lot of stuff, we still haven't collapsed the original edge.
436 // At this point we still haven't guaranteed that this original collapse weill be safe.
437 // quit for now, and we'll catch the remaining short edges the next time this function is
438 // called.
439 return;
440 }
441 }
442 else if (doTubeCutting) {
443 // tube case
444 // cout<<"CollapseEdge:tube case" << endl;
445
446 // find the edges that touch the common vert
447 int P2 = commonVert;
448 int P1P2 = -1, P2P1, P2P0 = -1, P0P2 = -1; // corners across from the cutting seam
449 int start = ca_old[0].next;
450 int end = cb_old[0].prev;
451 int current = start;
452 do {
453 // rotate around vertex P1 counter-clockwise
454 int op = m.corners(m.corners(current).next).opposite;
455 if (op < 0)
456 errMsg("tube cutting failed, no opposite");
457 current = m.corners(op).next;
458
459 if (m.corners(m.corners(current).prev).node == commonVert)
460 P1P2 = m.corners(current).next;
461 } while (current != end);
462
463 start = ca_old[0].prev;
464 end = cb_old[0].next;
465 current = start;
466 do {
467 // rotate around vertex P0 clockwise
468 int op = m.corners(m.corners(current).prev).opposite;
469 if (op < 0)
470 errMsg("tube cutting failed, no opposite");
471
472 current = m.corners(op).prev;
473 if (m.corners(m.corners(current).next).node == commonVert)
474 P2P0 = m.corners(current).prev;
475 } while (current != end);
476
477 if (P1P2 < 0 || P2P0 < 0)
478 errMsg("tube cutting failed, ill geometry");
479
480 P2P1 = m.corners(P1P2).opposite;
481 P0P2 = m.corners(P2P0).opposite;
482
483 // duplicate vertices on the top half of the cut,
484 // and use them to split the tube at this seam
485 int P0b = m.addNode(Node(m.nodes(P0).pos));
486 int P1b = m.addNode(Node(m.nodes(P1).pos));
487 int P2b = m.addNode(Node(m.nodes(P2).pos));
488 for (int i = 0; i < m.numNodeChannels(); i++) {
489 m.nodeChannel(i)->addInterpol(P0, P0, 0.5);
490 m.nodeChannel(i)->addInterpol(P1, P1, 0.5);
491 m.nodeChannel(i)->addInterpol(P2, P2, 0.5);
492 }
493
494 // offset the verts in the normal directions to avoid self intersections
495 Vec3 offsetVec = cross(m.nodes(P1).pos - m.nodes(P0).pos, m.nodes(P2).pos - m.nodes(P0).pos);
496 normalize(offsetVec);
497 offsetVec *= 0.01; // HACK:
498 m.nodes(P0).pos -= offsetVec;
499 m.nodes(P1).pos -= offsetVec;
500 m.nodes(P2).pos -= offsetVec;
501 m.nodes(P0b).pos += offsetVec;
502 m.nodes(P1b).pos += offsetVec;
503 m.nodes(P2b).pos += offsetVec;
504
505 // create a list of all triangles which touch P0, P1, and P2 from the top,
506 map<int, bool> topTris;
507 start = cb_old[0].next;
508 end = m.corners(P0P2).prev;
509 current = start;
510 topTris[start / 3] = true;
511 do {
512 // rotate around vertex P0 counter-clockwise
513 current = m.corners(m.corners(m.corners(current).next).opposite).next;
514 topTris[current / 3] = true;
515 } while (current != end);
516 start = m.corners(P0P2).next;
517 end = m.corners(P2P1).prev;
518 current = start;
519 topTris[start / 3] = true;
520 do {
521 // rotate around vertex P0 counter-clockwise
522 current = m.corners(m.corners(m.corners(current).next).opposite).next;
523 topTris[current / 3] = true;
524 } while (current != end);
525 start = m.corners(P2P1).next;
526 end = cb_old[0].prev;
527 current = start;
528 topTris[start / 3] = true;
529 do {
530 // rotate around vertex P0 counter-clockwise
531 current = m.corners(m.corners(m.corners(current).next).opposite).next;
532 topTris[current / 3] = true;
533 } while (current != end);
534
535 // create two new triangles,
536 int Ta = m.addTri(Triangle(P0, P1, P2));
537 int Tb = m.addTri(Triangle(P1b, P0b, P2b));
538 for (int i = 0; i < m.numTriChannels(); i++) {
539 m.triChannel(i)->addNew();
540 m.triChannel(i)->addNew();
541 }
542
543 // sew the tris to close the cut on each side
544 for (int c = 0; c < 3; c++)
545 m.addCorner(Corner(Ta, m.tris(Ta).c[c]));
546 for (int c = 0; c < 3; c++)
547 m.addCorner(Corner(Tb, m.tris(Tb).c[c]));
548 for (int c = 0; c < 3; c++) {
549 m.corners(Ta, c).next = 3 * Ta + ((c + 1) % 3);
550 m.corners(Ta, c).prev = 3 * Ta + ((c + 2) % 3);
551 m.corners(Tb, c).next = 3 * Tb + ((c + 1) % 3);
552 m.corners(Tb, c).prev = 3 * Tb + ((c + 2) % 3);
553 }
554 m.corners(Ta, 0).opposite = P1P2;
555 m.corners(Ta, 1).opposite = P2P0;
556 m.corners(Ta, 2).opposite = ca_old[1].prev;
557 m.corners(Tb, 0).opposite = P0P2;
558 m.corners(Tb, 1).opposite = P2P1;
559 m.corners(Tb, 2).opposite = cb_old[1].prev;
560 for (int c = 0; c < 3; c++) {
561 m.corners(m.corners(Ta, c).opposite).opposite = 3 * Ta + c;
562 m.corners(m.corners(Tb, c).opposite).opposite = 3 * Tb + c;
563 }
564 // replace P0,P1,P2 on the top with P0b,P1b,P2b.
565 for (map<int, bool>::iterator tti = topTris.begin(); tti != topTris.end(); tti++) {
566 // cout << "H " << tti->first << " : " << m.tris(tti->first).c[0] << " " <<
567 // m.tris(tti->first).c[1] << " " << m.tris(tti->first).c[2] << " " << endl;
568 for (int i = 0; i < 3; i++) {
569 int cn = m.tris(tti->first).c[i];
570 set<int> &ring = m.get1Ring(cn).nodes;
571
572 if (ring.find(P0) != ring.end() && cn != P0 && cn != P1 && cn != P2 && cn != P0b &&
573 cn != P1b && cn != P2b) {
574 ring.erase(P0);
575 ring.insert(P0b);
576 m.get1Ring(P0).nodes.erase(cn);
577 m.get1Ring(P0b).nodes.insert(cn);
578 }
579 if (ring.find(P1) != ring.end() && cn != P0 && cn != P1 && cn != P2 && cn != P0b &&
580 cn != P1b && cn != P2b) {
581 ring.erase(P1);
582 ring.insert(P1b);
583 m.get1Ring(P1).nodes.erase(cn);
584 m.get1Ring(P1b).nodes.insert(cn);
585 }
586 if (ring.find(P2) != ring.end() && cn != P0 && cn != P1 && cn != P2 && cn != P0b &&
587 cn != P1b && cn != P2b) {
588 ring.erase(P2);
589 ring.insert(P2b);
590 m.get1Ring(P2).nodes.erase(cn);
591 m.get1Ring(P2b).nodes.insert(cn);
592 }
593 if (cn == P0) {
594 m.tris(tti->first).c[i] = P0b;
595 m.corners(tti->first, i).node = P0b;
596 m.get1Ring(P0).tris.erase(tti->first);
597 m.get1Ring(P0b).tris.insert(tti->first);
598 }
599 else if (cn == P1) {
600 m.tris(tti->first).c[i] = P1b;
601 m.corners(tti->first, i).node = P1b;
602 m.get1Ring(P1).tris.erase(tti->first);
603 m.get1Ring(P1b).tris.insert(tti->first);
604 }
605 else if (cn == P2) {
606 m.tris(tti->first).c[i] = P2b;
607 m.corners(tti->first, i).node = P2b;
608 m.get1Ring(P2).tris.erase(tti->first);
609 m.get1Ring(P2b).tris.insert(tti->first);
610 }
611 }
612 }
613
614 // m.sanityCheck(true, &deletedNodes, &taintedTris);
615
616 return;
617 }
618 return;
619 }
620 if (ca_old[1].opposite >= 0 && ca_old[2].opposite >= 0 && cb_old[1].opposite >= 0 &&
621 cb_old[2].opposite >= 0 && ca_old[0].opposite >= 0 && cb_old[0].opposite >= 0 &&
622 ((m.corners(ca_old[1].opposite).node ==
623 m.corners(ca_old[2].opposite).node && // two-pyramid tubey case (6 tris, 5 verts)
624 m.corners(cb_old[1].opposite).node == m.corners(cb_old[2].opposite).node &&
625 (m.corners(ca_old[1].opposite).node == m.corners(cb_old[1].opposite).node ||
626 (m.corners(ca_old[1].opposite).node == cb_old[0].node && // single tetrahedron case
627 m.corners(cb_old[1].opposite).node == ca_old[0].node))) ||
628 (m.corners(ca_old[0].opposite).tri == m.corners(cb_old[0].opposite).tri &&
629 m.corners(ca_old[1].opposite).tri == m.corners(cb_old[0].opposite).tri &&
630 m.corners(ca_old[2].opposite).tri ==
631 m.corners(cb_old[0].opposite).tri // nonmanifold: 2 tris, 3 verts
632 && m.corners(cb_old[0].opposite).tri == m.corners(ca_old[0].opposite).tri &&
633 m.corners(cb_old[1].opposite).tri == m.corners(ca_old[0].opposite).tri &&
634 m.corners(cb_old[2].opposite).tri == m.corners(ca_old[0].opposite).tri))) {
635 // both top and bottom are closed pyramid caps, or it is a single tet
636 // delete the whole component!
637 // flood fill to mark all triangles in the component
638 map<int, bool> markedTris;
639 queue<int> triQ;
640 triQ.push(trinum);
641 markedTris[trinum] = true;
642 int iters = 0;
643 while (!triQ.empty()) {
644 int trival = triQ.front();
645 triQ.pop();
646 for (int i = 0; i < 3; i++) {
647 int newtri = m.corners(m.corners(trival, i).opposite).tri;
648 if (markedTris.find(newtri) == markedTris.end()) {
649 triQ.push(newtri);
650 markedTris[newtri] = true;
651 }
652 }
653 iters++;
654 }
655 map<int, bool> markedverts;
656 for (map<int, bool>::iterator mit = markedTris.begin(); mit != markedTris.end(); mit++) {
657 taintedTris[mit->first] = true;
658 markedverts[m.tris(mit->first).c[0]] = true;
659 markedverts[m.tris(mit->first).c[1]] = true;
660 markedverts[m.tris(mit->first).c[2]] = true;
661 }
662 for (map<int, bool>::iterator mit = markedverts.begin(); mit != markedverts.end(); mit++)
663 deletedNodes.push_back(mit->first);
664 return;
665 }
666
667 //////////////////////////
668 // begin original edge collapse
669
670 // update tri props of all adjacent triangles of P0,P1 (do before CT updates!)
671 // TODO: handleTriPropertyEdgeCollapse(trinum, P0,P1, ca_old[0], cb_old[0]);
672
673 m.mergeNode(P0, P1);
674
675 // Move position of P0
676 m.nodes(P0).pos = endpoint + 0.5 * edgevect;
677
678 // Preserve connectivity in both triangles
679 if (ca_old[1].opposite >= 0)
680 m.corners(ca_old[1].opposite).opposite = ca_old[2].opposite;
681 if (ca_old[2].opposite >= 0)
682 m.corners(ca_old[2].opposite).opposite = ca_old[1].opposite;
683 if (haveB && cb_old[1].opposite >= 0)
684 m.corners(cb_old[1].opposite).opposite = cb_old[2].opposite;
685 if (haveB && cb_old[2].opposite >= 0)
686 m.corners(cb_old[2].opposite).opposite = cb_old[1].opposite;
687
688 ////////////////////
689 // mark the two triangles and the one node for deletion
690 taintedTris[ca_old[0].tri] = true;
691 m.removeTriFromLookup(ca_old[0].tri);
692 if (haveB) {
693 taintedTris[cb_old[0].tri] = true;
694 m.removeTriFromLookup(cb_old[0].tri);
695 }
696 deletedNodes.push_back(P1);
697 numCollapses++;
698 }
699
700 } // namespace Manta
701