source: GTP/trunk/Lib/Geom/shared/GTGeometry/src/libs/vmi/src/simplify.cpp @ 2090

Revision 2090, 22.4 KB checked in by gumbau, 17 years ago (diff)
Line 
1#include <stdio.h>
2#include <stdlib.h>
3#include <memory.h>
4#include <float.h>
5#include <math.h>
6
7#include "../include/metrics.h"
8#include "../include/global.h"
9#include "../include/simplify.h"
10#include "../include/saliency.h"
11#include "../include/histogram.h"
12
13//#define RECOMPUTE_THE_WHOLE_HEAP
14
15using namespace VMI;
16using   namespace       std;
17
18//      Multimap to store current vertex in a simplification state.
19typedef multimap<_float3_,      int>    t_map;
20typedef t_map::iterator                                         t_map_str;
21typedef t_map::value_type                                       t_pair;
22t_map                                                                                                                   mVertexMap;
23multimap<int,int>                                                                       mVertices;
24
25vector<Geometry::Vector3>       VMI::vPositions;
26vector<Geometry::Vector3>       VMI::vNormals;
27vector<Geometry::Vector2>       VMI::vTexCoords;
28
29///////////////////////////////////////////////////////////////////////////////
30
31void VMI::bh_mydump(Mesh *mesh, bheap_t *h) {
32        int i, d;
33
34        printf("Heap status.\n");
35        for(i = 1; i <= h->n; i++) {
36                d = h->a[i].item;
37                printf ("Heap [%d] = pri %f, e%d(%d, %d) d:%d\n",
38                                i,
39                                h->a[i].key,d,
40                                mesh->edges[d].u,
41                                mesh->edges[d].v,
42                                h->a[i].dirty);
43        }
44        printf("\n");
45
46        for(i = 2; i <= h->n; i++) {
47                if(h->a[i].key < h->a[i/2].key) {
48                        printf("key error at entry %d, value %f\n", i, h->a[i].key);
49                        exit(1);
50                }
51        }
52        for(i = 1; i <= h->n; i++) {
53                if(h->p[h->a[i].item] != i) {
54                        printf("indexing error at entry %d", i);
55                        exit(1);
56                }
57        }   
58}
59
60bheap_t *VMI::initHeap(Mesh *mesh) {
61        GLuint i;
62        double cost;
63        bheap_t *h = NULL;
64
65        printf("Creating a heap for simplification...");
66
67        h = bh_alloc(mesh->numEdges);
68
69        //      Init percent update count.
70        float   percent =       60.0 / mesh->numEdges;
71
72        for (i = 0; i <mesh->numEdges; i++) {
73
74                //      Update progress bar.
75                mUPB(percent);
76
77                if (mesh->edges[i].enable == TRUE) {
78
79                        cost = computeEdgeCost(mesh, i);
80
81                        // Add only valid edges
82                        if (cost != FLT_MAX) {
83                                bh_insert(h, i, cost);
84                                /* set dirty flag to FALSE */
85                                bh_mark(h, i, FALSE);
86                        }
87                }
88        }
89
90        printf("Ok\n");
91
92#ifdef DEBUG
93        bh_mydump(mesh, h);
94        //getchar();
95#endif
96
97        return h;
98}
99
100bheap_t *VMI::updateHeap(bheap_t *h, Mesh *mesh, Change *c) {
101        int e, i;
102#ifdef RECOMPUTE_THE_WHOLE_HEAP
103        bheap_t *nh;
104        double cost;
105#else
106        int *lv, *le, numV, numE;
107#endif
108
109#ifdef RECOMPUTE_THE_WHOLE_HEAP
110
111        nh = bh_alloc(mesh->numEdges);
112
113        // Recompute heap
114        for(i = 1; i <= h->n; i++) {
115                e = h->a[i].item;
116
117                cost = computeEdgeCost(mesh, e);
118
119                // Add only valid edges
120                if (cost != FLT_MAX)
121                        bh_insert(nh, e, cost);
122        }
123
124        bh_free(h);
125
126        h = nh;
127
128#else
129
130        // Compute vertices adjacent to a vertex
131        lv = verticesAdjToVertex(mesh, c->v, &numV);
132
133        // Compute edges adjacent to vertices
134        le = edgesAdjToVertices(mesh, lv, numV, &numE);
135
136        free(lv);
137
138        // Set a dirty flag to adjacent edges from the heap
139        for(i = 0; i <numE; i++) {
140                e = le[i];
141
142                bh_mark(h, e, TRUE);
143        }
144
145        free(le);
146#endif
147
148#ifdef DEBUG
149        bh_mydump(mesh, h);
150        //getchar();
151#endif
152
153        return h;
154}
155
156GLdouble VMI::computeEdgeLength(Vertex *vertices, int u, int v) {
157        GLfloat ux, uy, uz, vx, vy ,vz, rx, ry, rz;
158
159        ux = vertices[u].x;
160        uy = vertices[u].y;
161        uz = vertices[u].z;
162
163        vx = vertices[v].x;
164        vy = vertices[v].y;
165        vz = vertices[v].z;
166
167        rx = ux - vx;
168        ry = uy - vy;
169        rz = uz - vz;
170
171        return sqrt((rx * rx) + (ry * ry) + (rz * rz));
172}
173
174///////////////////////////////////////////////////////////////////////////////
175
176void VMI::chooseBestEndPoints(Mesh *mesh, int e) {
177        int v = mesh->edges[e].v;
178        int u = mesh->edges[e].u;
179        int numTu = mesh->vertices[u].numTriangles;
180        int numTuv = 0;
181        int *Tuv = (int *)malloc(numTu * sizeof(int));
182        int i, j, f, n, n0, n1, n2;
183        float cost_u_v, cost_v_u, mincurve, curve, dot;
184
185        // Compute Tuv
186        for (i=0; i<(int)numTu; i++) {
187
188                n = mesh->vertices[u].triangles[i];
189
190                n0 = mesh->triangles[n].indices[0];
191                n1 = mesh->triangles[n].indices[1];
192                n2 = mesh->triangles[n].indices[2];
193
194                if ((n0 == v) || (n1 == v) || (n2 == v))
195
196                        Tuv[numTuv++] = n;
197        }
198        //printItemList(Tuv, numTuv);
199
200        curve = 0.0f;
201        for (i=0; i<numTu; i++) {
202                n = mesh->vertices[u].triangles[i];
203                mincurve = 1.0f;
204                for (j=0; j<numTuv; j++) {
205                        f = Tuv[j];
206                        dot = glmDot(mesh->triangles[f].normal, mesh->triangles[n].normal);
207                        //printf("dot: %f \n", dot);
208                        mincurve = MIN(mincurve, (1.0f - dot) / 2.0f);
209                }
210                //printf("mincurve: %f \n", mincurve);
211                curve = MAX(curve, mincurve);
212        }
213        cost_u_v = curve;
214
215        curve = 0.0f;
216        for (i=0; i<(int)mesh->vertices[v].numTriangles; i++) {
217                n = mesh->vertices[v].triangles[i];
218                mincurve = 1.0f;
219                for (j=0; j<numTuv; j++) {
220                        f = Tuv[j];
221                        dot = glmDot(mesh->triangles[f].normal, mesh->triangles[n].normal);
222                        //printf("%f \n", dot);
223                        mincurve = MIN(mincurve, (1.0f - dot) / 2.0f);
224                }
225                curve = MAX(curve, mincurve);
226        }
227
228        cost_v_u = curve;
229
230        //printf("e%d(%d,%d) cost: %f \n", e, u, v, cost_u_v);
231        //printf("e%d(%d,%d) cost: %f \n", e, v, u, cost_v_u);
232
233        if ( (cost_v_u + 0.000001) < cost_u_v) {
234                //printf("Swap edge\n");
235                //printf("e%d(%d,%d) cost: %f \n", e, u, v, cost_u_v);
236                //printf("e%d(%d,%d) cost: %f \n", e, v, u, cost_v_u);
237               
238                swap((int *)&mesh->edges[e].u, (int *)&mesh->edges[e].v);
239        }
240
241        free(Tuv);
242}
243///////////////////////////////////////////////////////////////////////////////
244
245void saveProjectedAreas(GLuint **histogram, GLuint numCameras, Change *c, GLuint *dest) {
246        GLuint i, j, t, n = 0;
247
248        for (j=0; j<(GLuint)c->numDel; j++) {
249
250                t = c->deleted[j].id;
251
252                for (i=0; i<numCameras; i++) {
253
254                        dest[n] = histogram[i][t + 1];
255                        n++;
256                }
257        }
258
259        for (j=0; j<(GLuint)c->numMod; j++) {
260
261                t = c->modified[j].id;
262
263                for (i=0; i<numCameras; i++) {
264
265                        dest[n] = histogram[i][t + 1];
266                        n++;
267                }   
268        }
269
270        // Save background area
271        for (i=0; i<numCameras; i++) {
272
273                dest[n] = histogram[i][0];
274                n++;
275        }
276}
277
278void loadProjectedAreas(GLuint *src, GLuint numCameras, Change *c, GLuint **histogram) {
279        GLuint i, j, t, n = 0;
280
281        for (j=0; j<(GLuint)c->numDel; j++) {
282
283                t = c->deleted[j].id;
284
285                for (i=0; i<numCameras; i++) {
286
287                        histogram[i][t + 1] = src[n];
288                        n++;
289                }
290        }
291
292        for (j=0; j<(GLuint)c->numMod; j++) {
293
294                t = c->modified[j].id;
295
296                for (i=0; i<numCameras; i++) {
297
298                        histogram[i][t + 1] = src[n];
299                        n++;
300                }
301        }
302
303        // Load background area
304        for (i=0; i<numCameras; i++) {
305
306                histogram[i][0] = src[n];
307                n++;
308        }
309}
310
311///////////////////////////////////////////////////////////////////////////////
312
313GLdouble VMI::computeEdgeCost(Mesh *mesh, int e) {
314        GLdouble cost = 0.0, sal = 1.0;
315#ifdef MI
316        GLdouble *auxIs = NULL;
317#else
318        GLdouble newI;
319#endif
320        GLuint i, *histoAux = NULL;
321        Change *c;
322
323        chooseBestEndPoints(mesh, e);
324        //getchar();
325
326        c = createChange(mesh, e);
327
328        // Compute cost only for boundary or manifold edges
329        if (c->numDel == 2
330                        /*(c->numDel <3) && (c->numDel > 0)*/) {
331                // Allocate memory
332                histoAux = (GLuint *)malloc((c->numDel + c->numMod + 1) * numCameras * sizeof(GLuint));
333
334#ifdef MI // Mutual Information
335                ///////////////////////////////////////////////////////////////////////////////
336                // Allocate memory
337                auxIs = (GLdouble *)malloc(numCameras * sizeof(GLdouble));
338
339                //printFullHistogram(histogram, numCameras, mesh->numTriangles);
340
341                for (i=0; i<numCameras; i++) {
342                        // Copy old informations
343                        auxIs[i] = initialIs[i];
344
345                        initialIs[i] = decMI(initialIs[i], histogram, numCameras, i, c);
346                }
347
348                saveProjectedAreas(histogram, numCameras, c, histoAux);
349    // Apply the edge collapse
350                doChange(mesh, c);
351
352                // Compute the cost of an edge collapse
353                getProjectedAreasWin(histogram, numCameras, c);
354                //printFullHistogram(histogram, numCameras, mesh->numTriangles);
355                //getchar();
356
357#ifdef SALIENCY
358                sal = computeEdgeSaliency(mesh, c, percentile);
359                //printf("  e:%d s: %f\n", c->e, sal);
360#endif
361
362                for (i=0; i<numCameras; i++) {
363
364                        initialIs[i] = incMI(initialIs[i], histogram, numCameras, i, c);
365                        //printf("  I0:%f Is: %f\n", auxE[i], initialIs[i]);
366
367                        cost += (ABS(auxIs[i] - initialIs[i]) * cameras[i].weight * sal);
368
369                        // Restore old informations
370                        initialIs[i] = auxIs[i];
371                }
372
373                undoChange(mesh, c);
374
375                loadProjectedAreas(histoAux, numCameras, c, histogram);
376                //printFullHistogram(histogram, numCameras, mesh->numTriangles);
377                //exit(1);
378
379                // Free memory
380                free(auxIs);
381#else
382                ///////////////////////////////////////////////////////////////////////////////
383
384                saveProjectedAreas(histogram, numCameras, c, histoAux);
385
386                doChange(mesh, c);
387
388                // Compute the cost of an edge collapse
389                getProjectedAreasWin(histogram, numCameras, c);
390                //printFullHistogram(histogram, numCameras, mesh->numTriangles);
391
392#ifdef SALIENCY
393                sal = computeEdgeSaliency(mesh, c, percentile);
394                //printf("  e:%d s: %f\n", c->e, sal);
395#endif
396                for (i=0;i <numCameras; i++) {
397
398#ifdef KL // Kullback-Leibler
399                        newI = computeKL(mesh, histogram[i]);
400#endif
401#ifdef HE // Hellinger
402                        newI = computeHE(mesh, histogram[i]);
403#endif
404#ifdef CS // Chi-Square
405                        newI = computeCS(mesh, histogram[i]);
406#endif
407                        cost += (ABS(initialIs[i] - newI) * cameras[i].weight * sal);
408                }
409                undoChange(mesh, c);
410
411                loadProjectedAreas(histoAux, numCameras, c, histogram);
412                //printFullHistogram(histogram, numCameras, mesh->numTriangles);
413                //exit(1);
414
415                ///////////////////////////////////////////////////////////////////////////////
416#endif
417                // Free memory
418                free(histoAux);
419
420        } else cost = FLT_MAX;
421
422        deleteChange(c);
423
424        return cost;
425}
426/* Get a valid edge from the heap */
427int getMinValidEdge(Mesh *mesh, bheap_t *h) {
428        int e;
429
430        /* pick the minimum-cost valid edge from heap */
431        e = bh_min(h);
432
433        while (mesh->edges[e].enable == FALSE) {
434                /* delete invalid edge */
435                bh_delete(h, e);
436                /* pick again*/
437                e = bh_min(h);
438        }
439
440        return e;
441}
442
443/* Get the mininum edge cost from the heap using lazy evaluation */
444int getMinEdge(Mesh *mesh, bheap_t *h) {
445        double cost;
446        int e;
447
448        /* pick the minimum-cost edge from heap */
449        e = getMinValidEdge(mesh, h);
450
451        while (bh_is_dirty(h, e)) {
452                /* delete edge from heap */
453                bh_delete(h, e);
454                mesh->edges[e].enable = FALSE;
455                /* recompute cost*/
456                cost = computeEdgeCost(mesh, e);
457
458                // Add only valid edges
459                if (cost != FLT_MAX) {
460                        /* reinsert into the heap */
461                        bh_insert(h, e, cost);
462                        mesh->edges[e].enable = TRUE;
463                        /* set dirty flag to FALSE */
464                        bh_mark(h, e, FALSE);
465                }
466
467                /* pick again */
468                e = getMinValidEdge(mesh, h);
469        }
470
471        return e;
472}
473
474///////////////////////////////////////////////////////////////////////////
475void VMI::simplifyModel(Mesh *mesh, GLuint numDemandedTri)
476{
477        int                     e;
478        Change  *c;
479        FILE            *file                                   = NULL;
480        FILE            *file_simp_seq  =       NULL;
481        char            s[MAX_CHAR];
482        double  cost                                            = 0.0;
483        bheap_t *h                                                      = NULL;
484        float           percent =       (40.0) / (float)(mesh->numTriangles - numDemandedTri);
485
486        if (numDemandedTri > mesh->currentNumTriangles)
487        {
488                return;
489        }
490
491        // Save changes into a file
492        if (bSaveLog == TRUE)
493        {
494#ifdef SALIENCY       
495                sprintf(s,"%s_%s_S.log", filename, EXT);
496#else
497                sprintf(s,"%s_%s.log", filename, EXT);
498#endif
499
500                glmWriteOBJ(pmodel, s, GLM_NONE);
501
502                /* open the file */
503                file = fopen(s, "a+");
504
505                if (!file)
506                {
507                        fprintf(stderr, "simplifyModel() failed: can't open file \"%s\" to write.\n", s);
508                        exit(1);
509                }
510        }
511
512        //      Open file of simplification sequence.
513        file_simp_seq   =       fopen("SimplifSequence.txt", "w");
514
515        if (!file_simp_seq)
516        {
517                fprintf(stderr,
518                                "simplifyModel() failed: ",
519                                "can't open file \"SimplifSequence\" to write.\n");
520        }
521
522        h = initHeap(mesh);
523
524        printf("Starting simplification...\n");
525
526        while (mesh->currentNumTriangles > numDemandedTri /*&& cost == 0.0*/)
527        {
528                // Get the edge that has the minimum cost
529                //e = getMinEdge(mesh, h);
530                e = extractValidEdge(mesh, h);
531
532                c = createChange(mesh, e);
533
534                // Apply the edge collapse
535                doChange(mesh, c);
536                //deleteVertexOfMap(mesh, c->u);
537
538                // Write Simplification sequence.
539                saveSimplificationSequence(c,0);
540
541                //contractTwinVertices(mesh, c->u, c->v); // vertex u is removed
542
543                if (bSaveLog == TRUE) writeChange(file, c);
544
545                cost = h->a[h->p[e]].key;
546
547                /*
548                printf( "Edge collapse e%d(%d,%d) %f MIN d %d m %d\n",
549                                c->e,
550                                c->u,
551                                c->v,
552                                cost,
553                                c->numDel,
554                                c->numMod);
555                */
556
557                mesh->edges[e].enable = FALSE;
558                bh_delete(h, e);
559
560                // Get projected areas after the edge collapse
561                getProjectedAreas(histogram, numCameras);
562
563                computeCameraIs(histogram, numCameras, initialIs);
564
565                deleteEdges(mesh, c);
566                modifyEdges(mesh, c);
567
568                // Update the heap according to the edge collapse
569                h = updateHeap(h, mesh, c);
570
571                mUPB((float)c->numDel * percent);
572
573                deleteChange(c);
574
575                //printf("t %d\n", mesh->currentNumTriangles);
576        }
577
578        //      Debug.
579        cout    <<      "Number of vertices: "
580                <<      mesh->currentNumVertices
581                <<      endl;
582
583        if (bSaveLog == TRUE)
584        {
585                fclose(file);
586                printf("Log file written...Ok\n");
587        }
588
589        //      Close simplification sequence file.
590        fclose(file_simp_seq);
591
592        bh_free(h);
593}
594
595///////////////////////////////////////////////////////////////////////////////
596//      Extract a correct edge of the heap.
597///////////////////////////////////////////////////////////////////////////////
598int VMI::extractValidEdge(Mesh *mesh,   bheap_t *h)
599{
600        int     e;
601
602        while((e        =       isValidEdge(mesh,getMinEdge(mesh, h))) == -1);
603
604        return  e;
605}
606
607///////////////////////////////////////////////////////////////////////////////
608//      Indicates if an edge is valid.
609///////////////////////////////////////////////////////////////////////////////
610int     VMI::isValidEdge(Mesh   *mesh,  int edge)
611{
612        int     result;
613        Vertex  *u;
614        Vertex  *v;
615        _float3_        fu;
616        _float3_        fv;
617
618        u       =       &mesh->vertices[mesh->edges[edge].u];
619        v       =       &mesh->vertices[mesh->edges[edge].v];
620
621        fu      =       _float3_(u->x,u->y,u->z);
622        fv      =       _float3_(v->x,v->y,v->z);
623
624        if ((mVertexMap.find(fu) != mVertexMap.end())
625                        ||
626                        (mVertexMap.find(fv) != mVertexMap.end()))
627        {
628                result  = edge;
629        }
630        //      Edge is not valid.
631        else
632        {
633                result  =       -1;
634        }
635
636        return  result;
637}
638
639//-------------------------------------------------------------------------
640//      Inits the multimap of vertices.
641//-------------------------------------------------------------------------
642void    VMI::initVertexMultimap(Mesh *mesh,multimap<int,int> &vertexMultimap)
643{
644        Vertex  *vertex;
645        float           x,y,z;
646
647        //      Clears multimap of vertices.
648        mVertexMap.clear();
649        mVertices.clear();
650
651        mVertices       =       vertexMultimap;
652
653        //      Debug.
654        cout    <<      "Vertex Map Elements: "
655                                <<      mVertices.size()
656                                <<      endl;
657
658        //      For each vertex.
659        for (int        i       =       0;      i < mesh->numVertices;  i++)
660        {
661                vertex  =       &mesh->vertices[i];
662
663                x       =       vertex->x;
664                y       =       vertex->y;
665                z       =       vertex->z;
666
667                mVertexMap.insert(t_pair(_float3_(x,y,z),i));
668        }
669}
670
671//-------------------------------------------------------------------------
672//      Deletes a vertex in the multimap.
673//-------------------------------------------------------------------------
674void    VMI::deleteVertexOfMap(Mesh     *mesh, int u)
675{
676        _float3_        removed_vert;
677        t_map_str       lb;
678        t_map_str       ub;
679
680        //      Position of the vertex removed.
681        removed_vert    =       _float3_(       mesh->vertices[u].x,
682                                                                                                                mesh->vertices[u].y,
683                                                                                                                mesh->vertices[u].z);
684
685        //      If position of the removed vertex is found.
686        if (mVertexMap.end() != mVertexMap.find(removed_vert))
687        {
688                lb      =       mVertexMap.lower_bound(removed_vert);
689                ub      =       mVertexMap.upper_bound(removed_vert);
690
691                //      For each vertex.
692                while   (lb != ub)
693                {
694                        //      If removed vertex is found.
695                        if ((*lb).second == u)
696                        {
697                                //      Debug.
698                                cout    <<      "Vertex erased: "
699                                                        <<      (*lb).second
700                                                        <<      endl;
701
702                                //      Delete vertex that disappears.
703                                mVertexMap.erase(lb);
704                               
705                                //      Break while.
706                                lb      =       ub;
707                        }
708                        else
709                        {
710                                //      Next iteration.
711                                lb++;
712                        }
713                }
714        }
715}
716
717//-------------------------------------------------------------------------
718//      Compare the coordinates of two vertices.
719//-------------------------------------------------------------------------
720bool    VMI::compareVertices(Vertex *vertices,int       u,      int v)
721{
722        if ((vertices[u].x == vertices[v].x)
723                        &&
724                        (vertices[u].y == vertices[v].y)
725                        &&
726                        (vertices[u].z == vertices[v].z))
727        {
728                return  true;
729        }
730        else
731        {
732                return  false;
733        }
734}
735
736//-------------------------------------------------------------------------
737//      Find edge of the simplification sequence.
738//-------------------------------------------------------------------------
739void    VMI::contractInitialMesh(Mesh   *mesh)
740{
741        bool            edge_found;
742        Geometry::MeshSimplificationSequence::Step      step;
743
744        multimap<int,int>::iterator     it0;
745        multimap<int,int>::iterator     lb0;
746        multimap<int,int>::iterator     ub0;
747        multimap<int,int>::iterator     lb1;
748        multimap<int,int>::iterator     ub1;
749
750        std::vector<Geometry::MeshSimplificationSequence::Step> steps;
751
752        Edge            *econ;
753        float           x,y,z;
754        int                     *lv1;
755        int                     v0;
756        int                     v1;
757        int                     edge;
758        int                     num_edges;
759        Change  *c;
760
761        //      Copy simplification steps of the joined mesh.
762        steps   =       mSequence->mSteps;
763
764        mSequence->mSteps.clear();
765
766        for     (size_t i       =       0;      i < steps.size(); i++)
767        {
768                step    =       steps[i];
769
770                lb0     =       mVertices.lower_bound(steps[i].mV0);
771                ub0     =       mVertices.upper_bound(steps[i].mV0);
772                lb1     =       mVertices.lower_bound(steps[i].mV1);
773                ub1     =       mVertices.upper_bound(steps[i].mV1);
774
775                edge_found      =       false;
776
777                //      Debug.
778                cout    <<      "step "
779                                        <<      i
780                                        <<      " V0: "
781                                        <<      steps[i].mV0
782                                        <<      " V1: "
783                                        <<      steps[i].mV1
784                                        <<      endl;
785
786                //      Removed vertex.
787                while ((lb1 != ub1) && !edge_found)
788                {
789                        //      Real index.
790                        v1      =       (*lb1).second;
791
792                        lv1     =       edgesAdjToVertex(mesh,v1,&num_edges);
793
794                        //      Edje iterator.
795                        edge    =       0;
796
797                        while   ((edge < num_edges) &&  !edge_found)
798                        {
799                                econ    =       &mesh->edges[lv1[edge]];
800
801                                //      Begin of iteration v0.
802                                it0     =       lb0;
803
804                                //      Remaining vertex.
805                                while ((it0 != ub0) &&  !edge_found)
806                                {
807                                        //      Real index.
808                                        v0      =       (*it0).second;
809                                       
810                                        if (compareVertices(mesh->vertices,econ->v,v0))
811                                        {
812                                                c = newChange(mesh, econ->u, econ->v);
813
814                                                edge_found      =       true;
815                                        }
816                                        else if (compareVertices(mesh->vertices,econ->u,v0))
817                                        {
818                                                c = newChange(mesh, econ->v, econ->u);
819
820                                                edge_found      =       true;
821                                        }
822                                        else
823                                        {
824                                                it0++;
825                                        }
826                                }
827
828                                edge++;
829                        }
830
831                        lb1++;
832                }
833
834                if (edge_found)
835                {
836                        //      Debug.
837                        cout    <<      "Contracting edge of the initial mesh..."       
838                                                <<      endl
839                                                <<      "u: "
840                                                <<      c->u
841                                                <<      " v: "
842                                                <<      c->v
843                                                <<      endl;
844       
845                        // Collapse new edge.
846                        doChange(mesh, c); // the mesh has been updated.
847
848                        // Write Simplification sequence.
849                        saveSimplificationSequence(c,0);
850
851                        deleteVertexOfMap(mesh, c->u);
852                        deleteEdges(mesh, c);
853                        modifyEdges(mesh, c);
854                        deleteChange(c);
855
856                        //      Contract twin vertices.
857                        contractTwinVertices(mesh,v1,v0);
858                }
859        }
860}
861
862//-------------------------------------------------------------------------
863//      Find twin vertices and contract them.
864//-------------------------------------------------------------------------
865void VMI::contractTwinVertices( Mesh    *mesh,
866                                                                                                                                int             u,
867                                                                                                                                int             v)
868{
869        bool                                    twin_found;
870        int                                             edge;
871        int                                             lonely_vert;
872        int                                             new_vert;
873        t_map_str                       lb;
874        t_map_str                       ub;
875        t_map_str                       it;
876        _float3_                        fu;
877        _float3_                        fv;
878        Edge                                    *econ;
879        float                                   x,y,z;
880        int                                             *le;
881        int                                             num_edges;
882        Change                          *c;
883
884        Geometry::GeoVertex     vertex_added;
885
886        if (!compareVertices(mesh->vertices,u,v))
887        {
888                //take_bone_from_vert = v;
889
890                fu      =       _float3_(       mesh->vertices[u].x,
891                                                                                mesh->vertices[u].y,
892                                                                                mesh->vertices[u].z);
893
894                fv      =       _float3_(       mesh->vertices[v].x,
895                                                                                mesh->vertices[v].y,
896                                                                                mesh->vertices[v].z);
897
898                //      Find vertices width u coordinates.
899                while ((it = mVertexMap.find(fu)) != mVertexMap.end())
900                {
901                        twin_found      =       false;
902
903                        lonely_vert     =       (*it).second;
904
905                        le      =       edgesAdjToVertex(mesh,lonely_vert,&num_edges);
906
907                        //      Find an edge width v coordinates.
908                        int     i       =       0;
909
910                        while((i < num_edges) && !twin_found)
911                        {
912                                econ    =       &mesh->edges[le[i]];
913
914                                if (compareVertices(mesh->vertices,econ->u,v)
915                                                ||
916                                                compareVertices(mesh->vertices,econ->v,v))
917                                {
918                                        lb      =       mVertexMap.lower_bound(fv);
919                                        ub      =       mVertexMap.upper_bound(fv);
920
921                                        //      For each vertex.
922                                        while   (lb != ub)
923                                        {
924                                                //      If removed vertex is found.
925                                                if (((*lb).second == econ->u)
926                                                                ||
927                                                                ((*lb).second == econ->v))
928                                                {
929                                                        twin_found      =       true;
930
931                                                        //      Break while.
932                                                        lb      =       ub;
933                                                }
934                                                else
935                                                {
936                                                        //      Next iteration.
937                                                        lb++;
938                                                }
939                                        }
940                                }
941                                i++;
942                        }
943
944                        //      If a twin edge has been found.
945                        if (twin_found)
946                        {
947                                //      Debug.
948                                cout    <<      "Twin Collapsed..."     <<      endl;
949
950                                //      Compare vertices coordinates.
951                                if (compareVertices(mesh->vertices,econ->u,v))
952                                {
953                                        // New edge for the change
954                                        c = newChange(mesh, econ->v, econ->u);
955
956                                        //      Debug.
957                                        cout    <<      "--Reverse--"   <<      endl;
958                                }
959                                else
960                                {
961                                        // New edge for the change
962                                        c = newChange (mesh, econ->u, econ->v);
963                                }
964
965                                // Collapse new edge.
966                                doChange(mesh, c); // the mesh has been updated.
967
968                                // Write Simplification sequence.
969                                saveSimplificationSequence(c,1);
970
971                                deleteVertexOfMap(mesh, c->u);
972                                deleteEdges(mesh, c);
973                                modifyEdges(mesh, c);
974                                deleteChange(c);
975                        }
976                        else
977                        {
978                                //      Debug.
979                                cout    <<      "Collapsing new edge..."        <<      endl;
980
981                                x       =       mesh->vertices[v].x;
982                                y       =       mesh->vertices[v].y;
983                                z       =       mesh->vertices[v].z;
984
985                                mesh->vertices = addVertex(     mesh->vertices,
986                                                                                                                                                (int *)&mesh->numVertices,
987                                                                                                                                                x,
988                                                                                                                                                y,
989                                                                                                                                                z,
990                                                                                                                                                &new_vert);
991                               
992                                // When a new vertex is added to the mesh, not only the
993                                // total number of vertices is increased but also current number
994                                mesh->currentNumVertices++;
995
996                                //      Adds new vertex to multimap.
997                                mVertexMap.insert(t_pair(_float3_(x,y,z),new_vert));
998
999                                //      Creates new edge.
1000                                mesh->edges     =       addEdge(mesh->edges,
1001                                                                                                                        (int *)&mesh->numEdges,
1002                                                                                                                        lonely_vert,
1003                                                                                                                        new_vert,
1004                                                                                                                        &edge);
1005
1006                                /*
1007                                //      Debug.
1008                                cout    <<      "lonely_vert"
1009                                        <<      lonely_vert
1010                                        <<      "("
1011                                        <<      mesh->vertices[lonely_vert].x
1012                                        <<      ","
1013                                        <<      mesh->vertices[lonely_vert].y
1014                                        <<      ","
1015                                        <<      mesh->vertices[lonely_vert].z
1016                                        <<      ")"
1017                                        <<      endl;
1018                                //      Debug.
1019                                cout    <<      "new_vert"
1020                                        <<      new_vert
1021                                        <<      "("
1022                                        <<      mesh->vertices[new_vert].x
1023                                        <<      ","
1024                                        <<      mesh->vertices[new_vert].y
1025                                        <<      ","
1026                                        <<      mesh->vertices[new_vert].z
1027                                        <<      ")"
1028                                        <<      endl;
1029                                */
1030
1031                                //      We assume here there are the same number of vertices
1032                                //      and texture coordinates and normals.
1033
1034                                //      Assigns the position of the vertex.
1035                                vPositions.push_back(Geometry::Vector3(x,y,z));
1036
1037                                //      Assigns a texture coordinate for the vertex.
1038                                vTexCoords.push_back(vTexCoords[lonely_vert]);
1039
1040                                //      Assigns a normal coordinate for the vertex.
1041                                vNormals.push_back(vNormals[lonely_vert]);
1042
1043                                //      Adds new vertex information to simplification sequence.
1044                                vertex_added.id                         =       new_vert;
1045                                vertex_added.bonefrom   =       v;
1046
1047                                vertex_added.position   =       vPositions[new_vert];
1048
1049                                vertex_added.texcoord   =       vTexCoords[new_vert];
1050
1051                                vertex_added.normal     =       vNormals[new_vert];
1052
1053                                mSequence->mNewVertices.push_back(vertex_added);
1054
1055                                // Collapse new edge
1056                                c = newChange(mesh, lonely_vert, new_vert);
1057
1058                                doChange(mesh, c); // the mesh has been updated
1059
1060                                // Write Simplification sequence.
1061                                saveSimplificationSequence(c,1);
1062
1063                                deleteVertexOfMap(mesh, c->u);
1064                                deleteEdges(mesh, c);
1065                                modifyEdges(mesh, c);
1066                                deleteChange(c);
1067                        }
1068                }
1069        }
1070}
1071
Note: See TracBrowser for help on using the repository browser.