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

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