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

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