svn merge ^/trunk/blender -r40390:40394
authorCampbell Barton <ideasman42@gmail.com>
Fri, 23 Sep 2011 07:20:27 +0000 (07:20 +0000)
committerCampbell Barton <ideasman42@gmail.com>
Fri, 23 Sep 2011 07:20:27 +0000 (07:20 +0000)
1  2 
source/blender/editors/transform/transform_conversions.c
source/blender/windowmanager/intern/wm_init_exit.c

index 60784639436cc220cda33c78577823e1efce5296,77d2e6e7ff07a6bcadd417fd4f0cffdeb33a4eca..ed98a179d05dc4e35eff7eac4c46e3afbb481252
@@@ -1816,95 -1807,96 +1816,95 @@@ void flushTransParticles(TransInfo *t
  /* ********************* mesh ****************** */
  
  /* proportional distance based on connectivity  */
- #define THRESHOLD     0.000000000000001f
+ #define THRESHOLD     0.0001f
  
 -static int connectivity_edge(float mtx[][3], EditVert *v1, EditVert *v2)
 +/*I did this wrong, it should be a breadth-first search
 +  but instead it's a depth-first search, fudged
 +  to report shortest distances.  I have no idea how fast
 +  or slow this is.*/
 +static void editmesh_set_connectivity_distance(BMEditMesh *em, float mtx[][3], float *dists)
  {
 -      float edge_vec[3];
 -      float edge_len;
 -      int done = 0;
 -
 -      /* note: hidden verts are not being checked for, this assumes
 -       * flushing of hidden faces & edges is working right */
 -      
 -      if (v1->f2 + v2->f2 == 4)
 -              return 0;
 +      BMVert **queue = NULL;
 +      float *dqueue = NULL;
 +      int *tots = MEM_callocN(sizeof(int)*em->bm->totvert, "tots editmesh_set_connectivity_distance");
 +      BLI_array_declare(queue);
 +      BLI_array_declare(dqueue);
 +      SmallHash svisit, *visit=&svisit;
 +      BMVert *v;
 +      BMIter viter;
 +      int i, start;
        
 -      sub_v3_v3v3(edge_vec, v1->co, v2->co);
 -      mul_m3_v3(mtx, edge_vec);
 -
 -      edge_len = len_v3(edge_vec);
 -
 -      if (v1->f2) {
 -              if (v2->f2) {
 -                      if (v2->tmp.fp + edge_len + THRESHOLD < v1->tmp.fp) {
 -                              v1->tmp.fp = v2->tmp.fp + edge_len;
 -                              done = 1;
 -                      } else if (v1->tmp.fp + edge_len + THRESHOLD < v2->tmp.fp) {
 -                              v2->tmp.fp = v1->tmp.fp + edge_len;
 -                              done = 1;
 -                      }
 -              }
 -              else {
 -                      v2->f2 = 1;
 -                      v2->tmp.fp = v1->tmp.fp + edge_len;
 -                      done = 1;
 -              }
 -      }
 -      else if (v2->f2) {
 -              v1->f2 = 1;
 -              v1->tmp.fp = v2->tmp.fp + edge_len;
 -              done = 1;
 +      i = 0;
 +      BM_ITER(v, &viter, em->bm, BM_VERTS_OF_MESH, NULL) {
 +              BM_SetIndex(v, i);
 +              dists[i] = FLT_MAX;
 +              i++;
        }
 +      
 +      BLI_smallhash_init(visit);
  
 -      return done;
 -}
 -
 -static void editmesh_set_connectivity_distance(EditMesh *em, float mtx[][3])
 -{
 -      EditVert *eve;
 -      EditEdge *eed;
 -      EditFace *efa;
 -      int done= 1;
 -
 -      /* f2 flag is used for 'selection' */
 -      /* tmp.l is offset on scratch array   */
 -      for(eve= em->verts.first; eve; eve= eve->next) {
 -              if(eve->h==0) {
 -                      eve->tmp.fp = 0;
 -
 -                      if(eve->f & SELECT) {
 -                              eve->f2= 2;
 -                      }
 -                      else {
 -                              eve->f2 = 0;
 -                      }
 -              }
 +      BM_ITER(v, &viter, em->bm, BM_VERTS_OF_MESH, NULL) {
 +              if (BM_TestHFlag(v, BM_SELECT)==0 || BM_TestHFlag(v, BM_HIDDEN))
 +                      continue;
 +                      
 +              
 +              BLI_smallhash_insert(visit, (uintptr_t)v, NULL);
 +              BLI_array_append(queue, v);
 +              BLI_array_append(dqueue, 0.0f);
 +              dists[BM_GetIndex(v)] = 0.0f;
        }
 +      
 +      start = 0;
 +      while (start < BLI_array_count(queue)) {
 +              BMIter eiter;
 +              BMEdge *e;
 +              BMVert *v3, *v2;
 +              float d, vec[3];
 +              
 +              v2 = queue[start];
 +              d = dqueue[start];
 +              
 +              BM_ITER(e, &eiter, em->bm, BM_EDGES_OF_VERT, v2) {
 +                      float d2;
 +                      v3 = BM_OtherEdgeVert(e, v2);
 +                      
 +                      if (BM_TestHFlag(v3, BM_SELECT) || BM_TestHFlag(v3, BM_HIDDEN))
 +                              continue;
 +                      
 +                      sub_v3_v3v3(vec, v2->co, v3->co);
 +                      mul_m3_v3(mtx, vec);
 +                      
 +                      d2 = d + len_v3(vec);
 +                      
 +                      if (dists[BM_GetIndex(v3)] != FLT_MAX)
 +                              dists[BM_GetIndex(v3)] = MIN2(d2, dists[BM_GetIndex(v3)]);
 +                      else
 +                              dists[BM_GetIndex(v3)] = d2;
 +                      
 +                      tots[BM_GetIndex(v3)] = 1;
  
 -
 -      /* Floodfill routine */
 -      /*
 -      At worst this is n*n of complexity where n is number of edges
 -      Best case would be n if the list is ordered perfectly.
 -      Estimate is n log n in average (so not too bad)
 -      */
 -      while(done) {
 -              done= 0;
 -
 -              for(eed= em->edges.first; eed; eed= eed->next) {
 -                      if(eed->h==0) {
 -                              done |= connectivity_edge(mtx, eed->v1, eed->v2);
 -                      }
 +                      if (BLI_smallhash_haskey(visit, (uintptr_t)v3))
 +                              continue;
 +                      
 +                      BLI_smallhash_insert(visit, (uintptr_t)v3, NULL);
 +                      
 +                      BLI_array_append(queue, v3);
 +                      BLI_array_append(dqueue, d2);
                }
 +              
 +              start++;
 +      }
  
 -              /* do internal edges for quads */
 -              for(efa= em->faces.first; efa; efa= efa->next) {
 -                      if (efa->v4 && efa->h==0) {
 -                              done |= connectivity_edge(mtx, efa->v1, efa->v3);
 -                              done |= connectivity_edge(mtx, efa->v2, efa->v4);
 -                      }
 -              }
 +      BLI_smallhash_release(visit);
 +      
 +      for (i=0; i<em->bm->totvert; i++) {
 +              if (tots[i])
 +                      dists[i] /= (float)tots[i];
        }
 +      
 +      BLI_array_free(queue);
 +      BLI_array_free(dqueue);
 +      MEM_freeN(tots);
  }
  
  /* loop-in-a-loop I know, but we need it! (ton) */