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

Revision 2103, 22.5 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        //      Debug.
767        cout    <<      "Simplification steps: "
768                                <<      steps.size()
769                                <<      " new vertices: "
770                                <<      mSequence->mNewVertices.size()
771                                <<      endl;
772
773        for     (size_t i       =       0;      i < steps.size(); i++)
774        {
775                step    =       steps[i];
776
777                lb0     =       mVertices.lower_bound(steps[i].mV0);
778                ub0     =       mVertices.upper_bound(steps[i].mV0);
779                lb1     =       mVertices.lower_bound(steps[i].mV1);
780                ub1     =       mVertices.upper_bound(steps[i].mV1);
781
782                edge_found      =       false;
783
784                //      Debug.
785                cout    <<      "step "
786                                        <<      i
787                                        <<      " V0: "
788                                        <<      steps[i].mV0
789                                        <<      " V1: "
790                                        <<      steps[i].mV1
791                                        <<      endl;
792
793                //      Removed vertex.
794                while ((lb1 != ub1) && !edge_found)
795                {
796                        //      Real index.
797                        v1      =       (*lb1).second;
798
799                        lv1     =       edgesAdjToVertex(mesh,v1,&num_edges);
800
801                        //      Edje iterator.
802                        edge    =       0;
803
804                        while   ((edge < num_edges) &&  !edge_found)
805                        {
806                                econ    =       &mesh->edges[lv1[edge]];
807
808                                //      Begin of iteration v0.
809                                it0     =       lb0;
810
811                                //      Remaining vertex.
812                                while ((it0 != ub0) &&  !edge_found)
813                                {
814                                        //      Real index.
815                                        v0      =       (*it0).second;
816                                       
817                                        if (compareVertices(mesh->vertices,econ->v,v0))
818                                        {
819                                                c = newChange(mesh, econ->u, econ->v);
820
821                                                edge_found      =       true;
822                                        }
823                                        else if (compareVertices(mesh->vertices,econ->u,v0))
824                                        {
825                                                c = newChange(mesh, econ->v, econ->u);
826
827                                                edge_found      =       true;
828                                        }
829                                        else
830                                        {
831                                                it0++;
832                                        }
833                                }
834
835                                edge++;
836                        }
837
838                        lb1++;
839                }
840
841                if (edge_found)
842                {
843                        //      Debug.
844                        cout    <<      "Contracting edge of the initial mesh..."       
845                                                <<      endl
846                                                <<      "u: "
847                                                <<      c->u
848                                                <<      " v: "
849                                                <<      c->v
850                                                <<      endl;
851       
852                        //      Collapse new edge.
853                        doChange(mesh, c); // the mesh has been updated.
854
855                        //      Write Simplification sequence.
856                        saveSimplificationSequence(c,0);
857
858                        deleteVertexOfMap(mesh, c->u);
859                        deleteEdges(mesh, c);
860                        modifyEdges(mesh, c);
861                        deleteChange(c);
862
863                        //      Contract twin vertices.
864                        contractTwinVertices(mesh,v1,v0);
865                }
866        }
867}
868
869//-------------------------------------------------------------------------
870//      Find twin vertices and contract them.
871//-------------------------------------------------------------------------
872void VMI::contractTwinVertices( Mesh    *mesh,
873                                                                                                                                int             u,
874                                                                                                                                int             v)
875{
876        bool                                    twin_found;
877        int                                             edge;
878        int                                             lonely_vert;
879        int                                             new_vert;
880        t_map_str                       lb;
881        t_map_str                       ub;
882        t_map_str                       it;
883        _float3_                        fu;
884        _float3_                        fv;
885        Edge                                    *econ;
886        float                                   x,y,z;
887        int                                             *le;
888        int                                             num_edges;
889        Change                          *c;
890
891        Geometry::GeoVertex     vertex_added;
892
893        if (!compareVertices(mesh->vertices,u,v))
894        {
895                //take_bone_from_vert = v;
896
897                fu      =       _float3_(       mesh->vertices[u].x,
898                                                                                mesh->vertices[u].y,
899                                                                                mesh->vertices[u].z);
900
901                fv      =       _float3_(       mesh->vertices[v].x,
902                                                                                mesh->vertices[v].y,
903                                                                                mesh->vertices[v].z);
904
905                //      Find vertices width u coordinates.
906                while ((it = mVertexMap.find(fu)) != mVertexMap.end())
907                {
908                        twin_found      =       false;
909
910                        lonely_vert     =       (*it).second;
911
912                        le      =       edgesAdjToVertex(mesh,lonely_vert,&num_edges);
913
914                        //      Find an edge width v coordinates.
915                        int     i       =       0;
916
917                        while((i < num_edges) && !twin_found)
918                        {
919                                econ    =       &mesh->edges[le[i]];
920
921                                if (compareVertices(mesh->vertices,econ->u,v)
922                                                ||
923                                                compareVertices(mesh->vertices,econ->v,v))
924                                {
925                                        lb      =       mVertexMap.lower_bound(fv);
926                                        ub      =       mVertexMap.upper_bound(fv);
927
928                                        //      For each vertex.
929                                        while   (lb != ub)
930                                        {
931                                                //      If removed vertex is found.
932                                                if (((*lb).second == econ->u)
933                                                                ||
934                                                                ((*lb).second == econ->v))
935                                                {
936                                                        twin_found      =       true;
937
938                                                        //      Break while.
939                                                        lb      =       ub;
940                                                }
941                                                else
942                                                {
943                                                        //      Next iteration.
944                                                        lb++;
945                                                }
946                                        }
947                                }
948                                i++;
949                        }
950
951                        //      If a twin edge has been found.
952                        if (twin_found)
953                        {
954                                //      Debug.
955                                cout    <<      "Twin Collapsed..."     <<      endl;
956
957                                //      Compare vertices coordinates.
958                                if (compareVertices(mesh->vertices,econ->u,v))
959                                {
960                                        // New edge for the change
961                                        c = newChange(mesh, econ->v, econ->u);
962
963                                        //      Debug.
964                                        cout    <<      "--Reverse--"   <<      endl;
965                                }
966                                else
967                                {
968                                        // New edge for the change
969                                        c = newChange (mesh, econ->u, econ->v);
970                                }
971
972                                // Collapse new edge.
973                                doChange(mesh, c); // the mesh has been updated.
974
975                                // Write Simplification sequence.
976                                saveSimplificationSequence(c,1);
977
978                                deleteVertexOfMap(mesh, c->u);
979                                deleteEdges(mesh, c);
980                                modifyEdges(mesh, c);
981                                deleteChange(c);
982                        }
983                        else
984                        {
985                                //      Debug.
986                                cout    <<      "Collapsing new edge..."        <<      endl;
987
988                                x       =       mesh->vertices[v].x;
989                                y       =       mesh->vertices[v].y;
990                                z       =       mesh->vertices[v].z;
991
992                                mesh->vertices = addVertex(     mesh->vertices,
993                                                                                                                                                (int *)&mesh->numVertices,
994                                                                                                                                                x,
995                                                                                                                                                y,
996                                                                                                                                                z,
997                                                                                                                                                &new_vert);
998                               
999                                // When a new vertex is added to the mesh, not only the
1000                                // total number of vertices is increased but also current number
1001                                mesh->currentNumVertices++;
1002
1003                                //      Adds new vertex to multimap.
1004                                mVertexMap.insert(t_pair(_float3_(x,y,z),new_vert));
1005
1006                                //      Creates new edge.
1007                                mesh->edges     =       addEdge(mesh->edges,
1008                                                                                                                        (int *)&mesh->numEdges,
1009                                                                                                                        lonely_vert,
1010                                                                                                                        new_vert,
1011                                                                                                                        &edge);
1012
1013                                /*
1014                                //      Debug.
1015                                cout    <<      "lonely_vert"
1016                                        <<      lonely_vert
1017                                        <<      "("
1018                                        <<      mesh->vertices[lonely_vert].x
1019                                        <<      ","
1020                                        <<      mesh->vertices[lonely_vert].y
1021                                        <<      ","
1022                                        <<      mesh->vertices[lonely_vert].z
1023                                        <<      ")"
1024                                        <<      endl;
1025                                //      Debug.
1026                                cout    <<      "new_vert"
1027                                        <<      new_vert
1028                                        <<      "("
1029                                        <<      mesh->vertices[new_vert].x
1030                                        <<      ","
1031                                        <<      mesh->vertices[new_vert].y
1032                                        <<      ","
1033                                        <<      mesh->vertices[new_vert].z
1034                                        <<      ")"
1035                                        <<      endl;
1036                                */
1037
1038                                //      We assume here there are the same number of vertices
1039                                //      and texture coordinates and normals.
1040
1041                                //      Assigns the position of the vertex.
1042                                vPositions.push_back(Geometry::Vector3(x,y,z));
1043
1044                                //      Assigns a texture coordinate for the vertex.
1045                                vTexCoords.push_back(vTexCoords[lonely_vert]);
1046
1047                                //      Assigns a normal coordinate for the vertex.
1048                                vNormals.push_back(vNormals[lonely_vert]);
1049
1050                                //      Adds new vertex information to simplification sequence.
1051                                vertex_added.id                         =       new_vert;
1052                                vertex_added.bonefrom   =       v;
1053
1054                                vertex_added.position   =       vPositions[new_vert];
1055
1056                                vertex_added.texcoord   =       vTexCoords[new_vert];
1057
1058                                vertex_added.normal     =       vNormals[new_vert];
1059
1060                                mSequence->mNewVertices.push_back(vertex_added);
1061
1062                                // Collapse new edge
1063                                c = newChange(mesh, lonely_vert, new_vert);
1064
1065                                doChange(mesh, c); // the mesh has been updated
1066
1067                                // Write Simplification sequence.
1068                                saveSimplificationSequence(c,1);
1069
1070                                deleteVertexOfMap(mesh, c->u);
1071                                deleteEdges(mesh, c);
1072                                modifyEdges(mesh, c);
1073                                deleteChange(c);
1074                        }
1075                }
1076        }
1077}
1078
Note: See TracBrowser for help on using the repository browser.