1 #include "controlPoint.h"
2 #include "vcg/simplex/face/component.h"
3
4 /****************************************************************************
5 * Rgb Triangulations Plugin *
6 * *
7 * Author: Daniele Panozzo (daniele.panozzo@gmail.com) *
8 * Copyright(C) 2007 *
9 * DISI - Department of Computer Science *
10 * University of Genova *
11 * *
12 * All rights reserved. *
13 * *
14 * This program is free software; you can redistribute it and/or modify *
15 * it under the terms of the GNU General Public License as published by *
16 * the Free Software Foundation; either version 2 of the License, or *
17 * (at your option) any later version. *
18 * *
19 * This program is distributed in the hope that it will be useful, *
20 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
22 * GNU General Public License (http://www.gnu.org/licenses/gpl.txt) *
23 * for more details. *
24 ****************************************************************************/
25
26 namespace rgbt
27 {
28
init(TriMeshType & m,RgbInfo & info)29 void ControlPoint::init(TriMeshType& m, RgbInfo& info)
30 {
31 for (unsigned int i = 0; i < m.vert.size(); ++i)
32 {
33 //std::cerr << "index:" << i << std::endl;
34 VertexPointer v = & m.vert[i];
35 if (!v->IsD() && v->VFp())
36 {
37
38 RgbTriangleC t = RgbTriangleC(m,info,v->VFp()->Index());
39 int ti = v->VFi();
40 RgbVertexC vr = t.V(ti);
41 assert(&vr.vert() == v);
42 vr.setPl(vr.getCoord());
43
44 }
45 }
46
47 for (unsigned int i = 0; i < m.vert.size(); ++i)
48 {
49 VertexPointer v = & m.vert[i];
50 if (!v->IsD() && v->VFp())
51 {
52
53 RgbTriangleC t = RgbTriangleC(m,info,v->VFp()->Index());
54 int ti = v->VFi();
55 if (!t.getVertexIsBorder(ti))
56 {
57 RgbVertexC vr = t.V(ti);
58 assert(&vr.vert() == v);
59 searchContribute(vr,false);
60 assignPinf(vr,true);
61 }
62 else
63 {
64 RgbVertexC vr = t.V(ti);
65 assert(&vr.vert() == v);
66 searchContributeBoundary(vr,false);
67 assignPinf(vr,true);
68 }
69
70 }
71
72 }
73
74 }
75
findInitialStencil(RgbTriangleC & t,int EdgeIndex,int level,TopologicalOpC & to,vector<RgbVertexC> * indexes,vector<RgbVertexC> * firstVertex)76 void ControlPoint::findInitialStencil(RgbTriangleC& t, int EdgeIndex,int level, TopologicalOpC& to, vector<RgbVertexC>* indexes,vector<RgbVertexC>* firstVertex)
77 {
78 bool isBorder = t.getEdgeIsBorder(EdgeIndex);
79
80 RgbVertexC c1 = RgbPrimitives::findOppositeVertex(t,EdgeIndex,firstVertex);
81
82 RgbTriangleC ot;
83 int oi;
84 RgbVertexC c2;
85
86 if (!isBorder)
87 {
88 ot = t.FF(EdgeIndex);
89 oi = t.FFi(EdgeIndex);
90 c2 = RgbPrimitives::findOppositeVertex(ot,oi,firstVertex);
91 }
92
93 RgbPrimitives::splitGreenEdgeIfNeeded(t.V(EdgeIndex),level,to);
94 RgbPrimitives::splitGreenEdgeIfNeeded(t.V((EdgeIndex+1)%3),level,to);
95 RgbPrimitives::splitGreenEdgeIfNeeded(c1,level,to);
96 if (!isBorder)
97 RgbPrimitives::splitGreenEdgeIfNeeded(c2,level,to);
98
99 if (indexes)
100 {
101 indexes->push_back(t.V(EdgeIndex));
102 indexes->push_back(t.V((EdgeIndex+1)%3));
103 indexes->push_back(c1);
104 if (!isBorder)
105 indexes->push_back(c2);
106 }
107
108 }
109
assignPinf(RgbVertexC & v,bool initial)110 void ControlPoint::assignPinf(RgbVertexC& v, bool initial)
111 {
112 if (!v.getIsBorder())
113 {
114 assert(!v.getIsBorder());
115 assert(v.getLevel() == 0 || !v.getIsBorder());
116 if (!initial)
117 {
118 assert(6 == v.getCount());
119 }
120 Point acc = v.getPinf();
121 int rank = vertexRank(v);
122 double an = alpha(rank);
123 double c1 = (1.0 - (8.0*an)/(3.0+8.0*an));
124 double c2 = ((8.0*an)/(rank*(3.0+8.0*an)));
125 Point pinf = v.getPl();
126 pinf *= c1;
127 acc *= c2;
128 pinf += acc;
129 v.setPinf(pinf);
130 v.setIsPinfReady(true);
131 updateP(v);
132
133 addPinfContributeToVV(v);
134 cleanTakenList(v);
135 }
136 else
137 {
138 assert(v.getIsBorder());
139 Point acc = v.getPinf();
140 Point pinf = v.getPl();
141 pinf *= (2.0/3.0);
142 acc *= (1.0/6.0);
143 pinf += acc;
144 v.setPinf(pinf);
145 v.setIsPinfReady(true);
146 updateP(v);
147 //addPinfContributeToVV(v);
148 }
149
150
151 }
152
alpha(int n)153 double ControlPoint::alpha(int n)
154 {
155 return (5.0/8.0)-(pow((3.0+2.0*cos(2.0*M_PI/n)),2)/64.0);
156 }
157
gamma(int n,int k)158 double ControlPoint::gamma(int n,int k)
159 {
160 return pow((5.0/8.0) - alpha(n),k);
161 }
162
computePkl(RgbVertexC & v,int kl)163 ControlPoint::Point ControlPoint::computePkl(RgbVertexC& v, int kl)
164 {
165 if (kl == v.getLevel())
166 return v.getPl();
167 assert(v.getIsPinfReady());
168 if (!v.getIsBorder())
169 {
170 int n = vertexRank(v);
171
172 int k = kl - v.getLevel();
173 if (k < 0)
174 k = 0;
175
176 double gnk = gamma(n,k);
177 Point p1 = v.getPl();
178 p1 *= gnk;
179 Point p2 = v.getPinf();
180 p2 *= (1.0 - gnk);
181 return p1 + p2;
182 }
183 else
184 {
185 int k = kl - v.getLevel();
186 if (k < 0)
187 k = 0;
188
189 double cp = pow(1.0/4.0,k);
190
191 Point p1 = v.getPl();
192 p1 *= cp;
193 Point p2 = v.getPinf();
194 p2 *= (1.0 - cp);
195
196 return p1 + p2;
197 }
198
199 }
computePl(int l,vector<RgbVertexC> & stencil)200 ControlPoint::Point ControlPoint::computePl(int l, vector<RgbVertexC>& stencil)
201 {
202 assert(stencil.size() == 4);
203
204 Point p0 = computePkl(stencil[0],l);
205 p0 *= (3.0/8.0);
206 Point p1 = computePkl(stencil[1],l);
207 p1 *= (3.0/8.0);
208 Point p2 = computePkl(stencil[2],l);
209 p2 *= (1.0/8.0);
210 Point p3 = computePkl(stencil[3],l);
211 p3 *= (1.0/8.0);
212
213 return p0 + p1 + p2 + p3;
214 }
215
computePlBoundary(int l,vector<RgbVertexC> & stencil)216 ControlPoint::Point ControlPoint::computePlBoundary(int l,vector<RgbVertexC>& stencil)
217 {
218 assert(stencil.size() >= 2);
219
220 Point p0 = computePkl(stencil[0],l);
221 p0 *= (1.0/2.0);
222 Point p1 = computePkl(stencil[1],l);
223 p1 *= (1.0/2.0);
224
225 return p0 + p1;
226 }
227
228
updateP(RgbVertexC & v)229 void ControlPoint::updateP(RgbVertexC& v)
230 {
231 if (v.getIsPinfReady())
232 {
233
234 int minLevel = minimalEdgeLevel(v);
235 Point tmp = computePkl(v,minLevel);
236 v.setCoord(tmp);
237 }
238 RgbPrimitives::updateNormal(v);
239 }
240
241
addContribute(RgbVertexC & v,Point & p,bool update)242 void ControlPoint::addContribute(RgbVertexC& v,Point& p, bool update)
243 {
244 //assert(v.getLevel() == 0 || v.getCount() < 6);
245 //if (!(v.getLevel() == 0 || v.getCount() < 6))
246 // std::cerr << "cont: " << v.getCount() << "level" << v.getLevel() << std::endl;
247
248 v.setCount(v.getCount() + 1);
249 if (!v.getIsPinfReady())
250 {
251 Point temp = v.getPinf() + p;
252 v.setPinf(temp);
253 }
254 if (update)
255 {
256 if (v.getCount() == 6)
257 {
258 assignPinf(v);
259 }
260 }
261 }
removeContribute(RgbVertexC & v,Point & p)262 void ControlPoint::removeContribute(RgbVertexC& v,Point& p)
263 {
264 //if (v.getCount() <= 0)
265 // std::cerr << "conti: " << v.getCount() << std::endl;
266 //assert(v.getCount() > 0);
267 v.setCount(v.getCount() - 1);
268 if (!v.getIsPinfReady())
269 {
270 Point temp = v.getPinf() - p;
271 v.setPinf(temp);
272 }
273 updateP(v);
274 }
275
276
doSplit(RgbTriangleC & fp,int EdgeIndex,int level,TopologicalOpC & to,vector<FacePointer> * vfp,RgbVertexC * vNewInserted,vector<RgbVertexC> * vcont,vector<RgbVertexC> * vupd)277 bool ControlPoint::doSplit(RgbTriangleC& fp, int EdgeIndex, int level, TopologicalOpC& to , vector<FacePointer> *vfp, RgbVertexC* vNewInserted, vector<RgbVertexC>* vcont, vector<RgbVertexC>* vupd)
278 {
279 assert(EdgeIndex >= 0 && EdgeIndex <= 2);
280
281 vector<RgbVertexC> stencil;
282 stencil.reserve(4);
283 vector<RgbVertexC> firstVertexes;
284 firstVertexes.reserve(4);
285
286 RgbVertexC v1 = fp.V(EdgeIndex);
287 RgbVertexC v2 = fp.V((EdgeIndex+1)%3);
288 bool isBorder = fp.getEdgeIsBorder(EdgeIndex);
289
290 findInitialStencil(fp,EdgeIndex,level,to,&stencil,&firstVertexes);
291
292 fp.updateInfo();
293
294 if (!RgbPrimitives::IsValidEdge(v1,v2))
295 {
296 //std::cerr << "different" << std::endl;
297 return false; // The current split was already done by findInitialStencil
298 }
299
300 Point p;
301 if (!isBorder)
302 {
303 p = computePl(level-1,stencil);
304 }
305 else
306 {
307 p = computePlBoundary(level-1,stencil);
308 }
309
310 VertexPointer vp;
311 vector<VertexPointer> vtemp;
312
313 if (!isBorder)
314 to.doSplit(fp.face(),EdgeIndex, p, vfp, &vtemp);
315 else
316 to.doSplitBoundary(fp.face(),EdgeIndex, p, vfp, &vtemp);
317
318 #ifndef NDEBUG
319 std::cerr << fp.m->vn << std::endl;
320 #endif
321
322 vp = vtemp[0];
323
324 RgbVertexC vNew = RgbVertexC(*(fp.m),*(fp.rgbInfo),vp);
325 vNew.resetInfo();
326 vNew.setLevel(level);
327 vNew.setPl(p);
328 vNew.setIsNew(true);
329 vNew.setIsBorder(isBorder);
330
331 if (isBorder)
332 {
333 Point psum = computePkl(stencil[0],level);
334 psum += computePkl(stencil[1],level);
335 vNew.setPinf(psum);
336 assignPinf(vNew,false);
337 }
338
339 if (vcont)
340 {
341 vcont->push_back(stencil[0]);
342 vcont->push_back(stencil[1]);
343 for (unsigned int i = 0; i < firstVertexes.size(); ++i)
344 vcont->push_back(firstVertexes[i]);
345 }
346
347 if (vupd)
348 {
349 vupd->push_back(stencil[0]);
350 vupd->push_back(stencil[1]);
351 }
352
353 if (vNewInserted)
354 *vNewInserted = vNew;
355
356 ControlPoint::updateP(vNew);
357
358 return true;
359 }
360
addToLists(RgbVertexC & dest,RgbVertexC & orig)361 void ControlPoint::addToLists(RgbVertexC& dest, RgbVertexC& orig)
362 {
363 // Optimization: no need to track anything if one of the vertex is a vertex of the original mesh
364 if (dest.getLevel() == 0 || orig.getLevel() == 0)
365 return;
366
367 dest.taken().push_back(orig.index);
368 orig.given().push_back(dest.index);
369 }
370
contain(std::list<int> & l,int e)371 bool contain(std::list<int>& l, int e)
372 {
373 for (std::list<int>::iterator i = l.begin(); i != l.end(); ++i)
374 {
375 if (*i == e)
376 return true;
377 }
378 return false;
379 }
380
removeFromLists(RgbVertexC & dest,RgbVertexC & orig)381 void ControlPoint::removeFromLists(RgbVertexC& dest, RgbVertexC& orig)
382 {
383 assert(contain(dest.taken(),orig.index));
384 assert(contain(orig.given(),dest.index));
385 dest.taken().remove(orig.index);
386 orig.given().remove(dest.index);
387 }
388
listUpdateVertexRemoval(RgbVertexC & v,list<RgbVertexC> & l)389 void ControlPoint::listUpdateVertexRemoval(RgbVertexC& v, list<RgbVertexC>& l)
390 {
391 cleanTakenList(v);
392
393 list<int> templ = list<int>(v.given());
394
395 for (std::list<int>::iterator i = templ.begin(); i != templ.end(); ++i)
396 {
397 RgbVertexC orig = RgbVertexC(*v.m,*v.rgbInfo,*i);
398 removeFromLists(orig,v);
399 l.push_back(orig);
400 }
401 }
402
addContributeIfPossible(RgbVertexC & dest,RgbVertexC & orig,bool execute)403 bool ControlPoint::addContributeIfPossible(RgbVertexC& dest, RgbVertexC& orig, bool execute)
404 {
405 if (dest.getLevel() == 0)
406 return false;
407
408 if (dest.getIsBorder())
409 return false;
410
411 if ((dest.getLevel() == orig.getLevel()) && !dest.getIsPinfReady())
412 {
413 if (execute)
414 {
415 Point p = orig.getPl();
416 addToLists(dest,orig);
417 addContribute(dest,p);
418 }
419 return true;
420 }
421 else
422 {
423 if (dest.getLevel() > orig.getLevel() && orig.getIsPinfReady() && !dest.getIsPinfReady()) // && (orig.getLevel() == 0))
424 {
425 if (execute)
426 {
427 Point p = computePkl(orig,dest.getLevel());
428 addToLists(dest,orig);
429 addContribute(dest,p);
430 }
431 return true;
432 }
433 }
434 return false;
435
436 }
437
searchContribute(RgbVertexC & v,bool update)438 void ControlPoint::searchContribute(RgbVertexC& v,bool update)
439 {
440 vector<RgbVertexC> vv;
441 vv.reserve(6);
442
443 RgbPrimitives::VV(v,vv);
444
445 for (unsigned int i = 0; i < vv.size(); ++i)
446 {
447 if (vv[i].getLevel() == v.getLevel())
448 {
449 Point p = vv[i].getPl();
450 addContribute(v,p,update);
451 }
452 }
453 }
454
searchContributeBoundary(RgbVertexC & v,bool update)455 void ControlPoint::searchContributeBoundary(RgbVertexC& v,bool update)
456 {
457 assert(v.getIsBorder());
458 vector<RgbVertexC> vv;
459 vv.reserve(6);
460
461 RgbPrimitives::VV(v,vv,false);
462
463 int last = vv.size() -1;
464
465 assert(vv.size() >= 2);
466 assert(vv[0].getIsBorder());
467 assert(vv[last].getIsBorder());
468 vector<RgbVertexC> vv2(2);
469 vv2[0] = vv[0];
470 vv2[1] = vv[last];
471
472 for (int i = 0; i < 2; ++i)
473 {
474 if (vv2[i].getLevel() == v.getLevel())
475 {
476 Point p = vv2[i].getPl();
477 addContribute(v,p,update);
478 }
479 else
480 {
481 // pinf is computed during the vertex creation so it is available for all boundary points
482 assert(vv2[i].getIsPinfReady());
483 Point p = computePkl(vv2[i],v.getLevel());
484 addContribute(v,p,update);
485 }
486 }
487 }
488
489
addPinfContributeToVV(RgbVertexC & v)490 void ControlPoint::addPinfContributeToVV(RgbVertexC& v)
491 {
492 assert(v.getIsPinfReady());
493 vector<RgbVertexC> vv;
494 vv.reserve(6);
495
496 RgbPrimitives::VV(v,vv,true);
497
498 for (unsigned int i = 0; i < vv.size(); ++i)
499 {
500 if (vv[i].getLevel() > v.getLevel())
501 {
502 addContributeIfPossible(vv[i],v,true);
503 }
504 }
505
506 }
507
doCollapse(RgbTriangleC & fp,int EdgeIndex,TopologicalOpC & to,Point3<ScalarType> * p,vector<FacePointer> * vfp)508 void ControlPoint::doCollapse(RgbTriangleC& fp, int EdgeIndex, TopologicalOpC& to, Point3<ScalarType> *p, vector<FacePointer> *vfp)
509 {
510 //assert(!fp.V(EdgeIndex).getIsNew());
511 if (!fp.getEdgeIsBorder(EdgeIndex))
512 to.doCollapse(fp.face(),EdgeIndex, p, vfp);
513 else
514 to.doCollapseBoundary(fp.face(),EdgeIndex, p, vfp);
515
516 #ifndef NDEBUG
517 std::cerr << fp.m->vn << std::endl;
518 #endif
519
520 }
521
minimalEdgeLevel(RgbVertexC & v)522 int ControlPoint::minimalEdgeLevel(RgbVertexC& v)
523 {
524 int level;
525 int i = 0;
526
527 bool isBorder = v.getIsBorder();
528 FacePointer fp = v.vert().VFp();
529 int fi = v.vert().VFi();
530 vcg::face::Pos<FaceType> pos(fp,fi);
531 CMeshO::FacePointer first = pos.F();
532
533 RgbTriangleC t = RgbTriangleC(v.m,v.rgbInfo,pos.F()->Index());
534 if (t.getNumberOfBoundaryEdge(&v) >= 2)
535 {
536
537 int index;
538 bool res = t.containVertex(v.index, &index);
539 assert(res);
540
541 int l1 = t.getEdgeLevel(index);
542 int l2 = t.getEdgeLevel((index+2)%3);
543
544 if (l1 > l2)
545 return l2;
546 else
547 return l1;
548 }
549
550
551 if (isBorder) // if is border move ccw until the border is found
552 {
553
554 pos.FlipE();
555 pos.FlipF();
556
557 while (!pos.IsBorder())
558 {
559 pos.FlipE();
560 pos.FlipF();
561 }
562
563 pos.FlipE();
564 }
565
566 RgbTriangleC tmp = RgbTriangleC(v.m,v.rgbInfo,pos.F()->Index());
567 assert(tmp.containVertex(v.index));
568 tmp.containVertex(v.index,&i);
569 assert(i>=0 && i<= 2);
570 level = tmp.getEdgeLevel(i);
571
572 pos.FlipF();
573 pos.FlipE();
574
575 while(pos.F() != first)
576 {
577 RgbTriangleC tmp = RgbTriangleC(v.m,v.rgbInfo,pos.F()->Index());
578 assert(tmp.containVertex(v.index));
579 tmp.containVertex(v.index,&i);
580 assert(i>=0 && i<= 2);
581 if (tmp.getEdgeLevel(i) < level)
582 level = tmp.getEdgeLevel(i);
583
584 if (pos.IsBorder())
585 break;
586
587 pos.FlipF();
588 pos.FlipE();
589 assert(pos.F()->V(0) == fp->V(fi) || pos.F()->V(1) == fp->V(fi) || pos.F()->V(2) == fp->V(fi));
590 assert(!fp->IsD());
591 }
592 return level;
593 }
594
vertexRemovalUpdate(RgbVertexC & v)595 void ControlPoint::vertexRemovalUpdate(RgbVertexC& v)
596 {
597 list<RgbVertexC> l;
598 listUpdateVertexRemoval(v,l);
599
600 for (list<RgbVertexC>::iterator i = l.begin(); i != l.end(); ++i)
601 {
602 RgbVertexC& vv = *i;
603 if (!vv.getIsPinfReady())
604 {
605 if (vv.getLevel() > v.getLevel() && v.getIsPinfReady())
606 {
607 Point p = computePkl(v,vv.getLevel());
608 removeContribute(vv,p);
609 }
610 if (vv.getLevel() == v.getLevel())
611 {
612 Point p = v.getPl();
613 removeContribute(vv,p);
614 }
615 }
616 }
617
618 }
619
cleanTakenList(RgbVertexC & v)620 void ControlPoint::cleanTakenList(RgbVertexC& v)
621 {
622 list<int> templ = list<int>(v.taken());
623 // If depends on other control point remove all dependencies
624 for (std::list<int>::iterator i = templ.begin(); i != templ.end(); ++i)
625 {
626 RgbVertexC orig = RgbVertexC(*v.m,*v.rgbInfo,*i);
627 removeFromLists(v,orig);
628 }
629 }
630
vertexRank(RgbVertexC & v)631 unsigned int ControlPoint::vertexRank(RgbVertexC& v)
632 {
633 int rank;
634 if (v.getLevel() > 0)
635 {
636 rank = 6;
637 }
638 else
639 {
640 rank = v.getCount();
641 }
642 return rank;
643 }
644
645
646 }
647