Added merge option to shrinkwrap when using projection mode (bruteforce for now)
authorAndre Susano Pinto <andresusanopinto@gmail.com>
Tue, 17 Jun 2008 19:00:21 +0000 (19:00 +0000)
committerAndre Susano Pinto <andresusanopinto@gmail.com>
Tue, 17 Jun 2008 19:00:21 +0000 (19:00 +0000)
Changed code to remove faces (now quad faces that got one vertice projected are turned on tri)

Merge option is still not very usefull since shrinkwrap does not yet moves unprojected vertices

release/scripts/CreatePlane.py
source/blender/blenkernel/BKE_shrinkwrap.h
source/blender/blenkernel/intern/modifier.c
source/blender/blenkernel/intern/shrinkwrap.c
source/blender/makesdna/DNA_modifier_types.h
source/blender/src/buttons_editing.c

index 5b72c60f541f8efbf39b4831201ccfceeb3a27b9..393a3a94e65b2901e93498fb65cb745b2d1a8baa 100644 (file)
@@ -45,24 +45,23 @@ import Blender, bpy
 def matrix(dima, dimb):
        return [[0 for b in range(dimb)] for a in range(dima)]
 
-def makelist(a):
-       res = []
-       for i in a:
-               res.append(i)
-       return res
-
 def dotProduct(a):
-       sum = 0.0
-       for i in a:
-               sum += i*i
-       return sum
+       return reduce(lambda x, y: x + y*y, a) 
+
+def manhattanDistance(a, b):
+       return reduce(lambda x, y: x + abs(y[0]-y[1]), zip(a, b), 0)
+
+def xrange_tuple(low, upper):
+       for i in xrange( low[0], upper[0]):
+               for j in xrange( low[1], upper[1]):
+                       yield (i,j)
+
 
 # For now simply decompose in a triangle fan
 def DecomposePolygon(poly):
-       for i in range(2, len(poly), 1):
+       for i in xrange(2, len(poly), 1):
                yield [ poly[0], poly[i-1], poly[i] ]
 
-
 def Expand3dCoordsFrom2d(coords):
        for c in coords:
                yield ( c[0] , c[1], 0 )
@@ -76,34 +75,41 @@ def ExtractSections(image):
        mdim = max( image.size )
        dx = float(image.size[0]) / x_samples
        dy = float(image.size[1]) / y_samples
-       ox = -float(x_samples)*0.5
-       oy = -float(y_samples)*0.5
+
+       offset = [ -0.5*i for i in image.size]
 
        def scale(a):
-               return ( (a[0] + ox)*dx , (a[1] + oy)*dy )
-                       
-       used = matrix(x_samples, y_samples)
-       for a in range(x_samples):
-               for b in range(y_samples):
-                       if dotProduct(image.getPixelHDR( (int)(a*dx), (int)(b*dy))) <= 1:
-                               used[a][b] = 1
-
-       for a in range(x_samples-1):
-               for b in range(y_samples-1):
-                       sum = used[a][b] + used[a+1][b] + used[a][b+1] + used[a+1][b+1]
-                       
-                       if sum == 4:
-                               yield map( scale, [ (a,b) , (a+1,b), (a+1,b+1), (a,b+1) ] )
-                       elif sum == 3:
-                               if not used[a][b]:
-                                       yield map( scale, [ (a+1,b), (a+1,b+1) , (a,b+1) ] )
-                               if not used[a+1][b]:
-                                       yield map( scale, [ (a,b), (a+1,b+1) , (a,b+1) ] )
-                               if not used[a][b+1]:
-                                       yield map( scale, [ (a,b), (a+1,b) , (a+1,b+1) ] )
-                               if not used[a+1][b+1]:
-                                       yield map( scale, [ (a,b), (a+1,b) , (a,b+1) ] )
-                                       
+               return (a[0] + offset[0] , a[1] + offset[1])
+       
+       sx = 0
+#(int) (float(image.size[0]) / (x_samples))
+       sy = 0
+#(int) (float(image.size[1]) / (y_samples))
+
+       def get( center ):
+               best = None
+               for pos in xrange_tuple( (max(0, center[0]-sx),max(0, center[1]-sy)) , (min(image.size[0], center[0]+sx)+1, min(image.size[1], center[1]+sy)+1 )):
+                               if dotProduct(image.getPixelHDR(pos[0],pos[1])) <= 1:
+                                       if best == None or manhattanDistance(center, pos) < manhattanDistance(center, best):
+                                               best = pos
+               return best
+
+
+       pos = matrix(x_samples, y_samples)
+       sdx = dx
+       sdy = dy
+       for a in xrange(x_samples):
+               for b in xrange(y_samples):
+                       pos[a][b] = get(((int)(a*sdx),(int)(b*sdy)))
+
+       for a in xrange(x_samples-1):
+               for b in xrange(y_samples-1):
+                       arround = [ (a,b) , (a+1,b), (a+1,b+1), (a,b+1) ]
+
+                       valid = [ pos[c[0]][c[1]] for c in arround if pos[c[0]][c[1]] != None]
+                       if len(valid) >= 3:
+                               yield map( scale, valid )
+                               
 
 def ImportPlaneFromImage(image, mesh):
 
@@ -134,8 +140,6 @@ def ImportPlaneFromImage(image, mesh):
 
 
 
-#use the current image on the image editor? or ask the user what image to load
-#image = Blender.Image.GetCurrent()
 
 def load_image(filename):
        print "Loading ",filename
@@ -144,11 +148,13 @@ def load_image(filename):
        Blender.Scene.GetCurrent().objects.new(mesh)
 
        image = Blender.Image.Load(filename)
-       print image
        ImportPlaneFromImage(image, mesh)
        Blender.Redraw()
        
 
-image = Blender.Window.FileSelector(load_image, "Load Image")
+Blender.Window.FileSelector(load_image, "Load Image")
+#use the current image on the image editor? or ask the user what image to load
+#image = Blender.Image.GetCurrent()
+#load_image("/home/darkaj/develop/blender/shrinkwrap/road.png")
 
 
index babdcd78261b3d5442ed5800c4e228e9e4de8e18..3eb0b6fa579b3a1ebc5aebf606d24df873bc9574 100644 (file)
@@ -39,6 +39,8 @@ typedef char* BitSet;
 
 #define bitset_get(set,index)  ((set)[(index)>>3] & (1 << ((index)&0x7)))
 #define bitset_set(set,index)  ((set)[(index)>>3] |= (1 << ((index)&0x7)))
+#define bitset_unset(set,index)        ((set)[(index)>>3] &= ~(1 << ((index)&0x7)))
+
 
 
 struct Object;
index 63d2da31b2011729d87e61e51a8464117474571c..cd65aace1588efc875d805df0bbde3e61eb42ca5 100644 (file)
@@ -7021,6 +7021,7 @@ static void shrinkwrapModifier_initData(ModifierData *md)
        smd->shrinkType = MOD_SHRINKWRAP_NEAREST_SURFACE;
        smd->shrinkOpts = MOD_SHRINKWRAP_ALLOW_DEFAULT_NORMAL;
        smd->keptDist   = 0.0f;
+       smd->mergeDist  = 0.0f;
 }
 
 static void shrinkwrapModifier_copyData(ModifierData *md, ModifierData *target)
index 14ed29d058394d2da6ebffd782173b9a915cc6c2..893cff3dd25142f18a2ee84e61f6035ab20b2bb4 100644 (file)
@@ -29,6 +29,7 @@
 #include <string.h>
 #include <float.h>
 #include <math.h>
+#include <memory.h>
 #include <stdio.h>
 #include <time.h>
 
@@ -58,7 +59,7 @@
 #define OUT_OF_MEMORY()        ((void)printf("Shrinkwrap: Out of memory\n"))
 
 /* Benchmark macros */
-#if 1
+#if 0
 
 #define BENCH(a)       \
        do {                    \
@@ -322,6 +323,82 @@ static float squared_dist(const float *a, const float *b)
        return INPR(tmp, tmp);
 }
 
+/*
+ *
+ */
+static void derivedmesh_mergeNearestPoints(DerivedMesh *dm, float mdist, BitSet skipVert)
+{
+       if(mdist > 0.0f)
+       {
+               int i, j, merged;
+               int     numVerts = dm->getNumVerts(dm);
+               int *translate_vert = MEM_mallocN( sizeof(int)*numVerts, "merge points array");
+
+               MVert *vert = dm->getVertDataArray(dm, CD_MVERT);
+
+               if(!translate_vert) return;
+
+               merged = 0;
+               for(i=0; i<numVerts; i++)
+               {
+                       translate_vert[i] = i;
+
+                       if(skipVert && bitset_get(skipVert, i)) continue;
+
+                       for(j = 0; j<i; j++)
+                       {
+                               if(skipVert && bitset_get(skipVert, j)) continue;
+                               if(squared_dist(vert[i].co, vert[j].co) < mdist)
+                               {
+                                       translate_vert[i] = j;
+                                       merged++;
+                                       break;
+                               }
+                       }
+               }
+
+               //some vertexs were merged.. recalculate structure (edges and faces)
+               if(merged > 0)
+               {
+                       int     numFaces = dm->getNumFaces(dm);
+                       int freeVert;
+                       MFace *face = dm->getFaceDataArray(dm, CD_MFACE);
+
+
+                       //Adjust vertexs using the translation_table.. only translations to back indexs are allowed
+                       //which means t[i] <= i must always verify
+                       for(i=0, freeVert = 0; i<numVerts; i++)
+                       {
+                               if(translate_vert[i] == i)
+                               {
+                                       memcpy(&vert[freeVert], &vert[i], sizeof(*vert));
+                                       translate_vert[i] = freeVert++;
+                               }
+                               else translate_vert[i] = translate_vert[ translate_vert[i] ];
+                       }
+
+                       CDDM_lower_num_verts(dm, numVerts - merged);
+
+                       for(i=0; i<numFaces; i++)
+                       {
+                               MFace *f = face+i;
+                               f->v1 = translate_vert[f->v1];
+                               f->v2 = translate_vert[f->v2];
+                               f->v3 = translate_vert[f->v3];
+                               //TODO be carefull with vertexs v4 being translated to 0
+                               f->v4 = translate_vert[f->v4];
+                       }
+
+                       //TODO: maybe update edges could be done outside this function
+                       CDDM_calc_edges(dm);
+                       //CDDM_calc_normals(dm);
+               }
+
+               if(translate_vert) MEM_freeN( translate_vert );
+       }
+}
+
+
 /*
  * This calculates the distance (in dir units) that the ray must travel to intersect plane
  * It can return negative values
@@ -703,25 +780,57 @@ static void shrinkwrap_removeUnused(ShrinkwrapCalcData *calc)
        BitSet used_faces = bitset_new(numFaces, "shrinkwrap used faces");
        int numUsedFaces = 0;
 
+
+       //calculate which vertexs need to be used
+       //even unmoved vertices might need to be used if theres a face that needs it
        //calc real number of faces, and vertices
        //Count used faces
        for(i=0; i<numFaces; i++)
        {
-               char res = bitset_get(moved_verts, face[i].v1)
-                                | bitset_get(moved_verts, face[i].v2)
-                                | bitset_get(moved_verts, face[i].v3)
-                                | (face[i].v4 ? bitset_get(moved_verts, face[i].v4) : 0);
+               char res = 0;
+               if(bitset_get(moved_verts, face[i].v1)) res++;
+               if(bitset_get(moved_verts, face[i].v2)) res++;
+               if(bitset_get(moved_verts, face[i].v3)) res++;
+               if(face[i].v4 && bitset_get(moved_verts, face[i].v4)) res++;
+
+               //Ignore a face were not a single vertice moved
+               if(res == 0) continue;
 
-               if(res)
+               //Only 1 vertice moved.. (if its a quad.. remove the vertice oposite to it)
+               if(res == 1 && face[i].v4)
                {
-                       bitset_set(used_faces, i);      //Mark face to maintain
-                       numUsedFaces++;
+                       if(bitset_get(moved_verts, face[i].v1))
+                       {
+                               //remove vertex 3
+                               face[i].v3 = face[i].v4;
+                       }
+                       else if(bitset_get(moved_verts, face[i].v2))
+                       {
+                               //remove vertex 4
+                       }
+                       else if(bitset_get(moved_verts, face[i].v3))
+                       {
+                               //remove vertex 1
+                               face[i].v1 = face[i].v4;
+                       }
+                       else if(bitset_get(moved_verts, face[i].v4))
+                       {
+                               //remove vertex 2
+                               face[i].v2 = face[i].v3;
+                               face[i].v3 = face[i].v4;
+                       }
 
-                       vert_index[face[i].v1] = 1;
-                       vert_index[face[i].v2] = 1;
-                       vert_index[face[i].v3] = 1;
-                       if(face[i].v4) vert_index[face[i].v4] = 1;
+                       face[i].v4 = 0; //this quad turned on a tri
                }
+
+               bitset_set(used_faces, i);      //Mark face to maintain
+               numUsedFaces++;
+
+               //Mark vertices are needed
+               vert_index[face[i].v1] = 1;
+               vert_index[face[i].v2] = 1;
+               vert_index[face[i].v3] = 1;
+               if(face[i].v4) vert_index[face[i].v4] = 1;
        }
 
        //DP: Accumulate vertexs indexs.. (will calculate the new vertex index with a 1 offset)
@@ -736,10 +845,16 @@ static void shrinkwrap_removeUnused(ShrinkwrapCalcData *calc)
        new_vert  = new->getVertDataArray(new, CD_MVERT);
        for(i=0, t=0; i<numVerts; i++)
        {
+               
                if(vert_index[i] != t)
                {
                        t = vert_index[i];
                        memcpy(new_vert++, vert+i, sizeof(MVert));
+
+                       if(bitset_get(moved_verts, i))
+                               bitset_set(moved_verts, t-1);
+                       else
+                               bitset_unset(moved_verts, t-1);
                }
        }
 
@@ -779,6 +894,7 @@ static void shrinkwrap_removeUnused(ShrinkwrapCalcData *calc)
        calc->final = new;
 }
 
+
 /* Main shrinkwrap function */
 DerivedMesh *shrinkwrapModifier_do(ShrinkwrapModifierData *smd, Object *ob, DerivedMesh *dm, int useRenderParams, int isFinalCalc)
 {
@@ -820,10 +936,12 @@ DerivedMesh *shrinkwrapModifier_do(ShrinkwrapModifierData *smd, Object *ob, Deri
        //Projecting target defined - lets work!
        if(calc.target)
        {
+/*
                printf("Shrinkwrap (%s)%d over (%s)%d\n",
                        calc.ob->id.name,                       calc.final->getNumVerts(calc.final),
                        calc.smd->target->id.name,      calc.target->getNumVerts(calc.target)
                );
+*/
 
                switch(smd->shrinkType)
                {
@@ -845,14 +963,21 @@ DerivedMesh *shrinkwrapModifier_do(ShrinkwrapModifierData *smd, Object *ob, Deri
 
        }
 
-       //Destroy faces, edges and stuff
        if(calc.moved)
        {
+               //Destroy faces, edges and stuff
                shrinkwrap_removeUnused(&calc);
-               bitset_free(calc.moved);
+
+               if(calc.moved)
+                       derivedmesh_mergeNearestPoints(calc.final, calc.smd->mergeDist, calc.moved);
        }
 
-       CDDM_calc_normals(calc.final);  
+       CDDM_calc_normals(calc.final);
+
+       //clean memory
+       if(calc.moved)
+               bitset_free(calc.moved);
+
 
        return calc.final;
 }
@@ -873,12 +998,11 @@ void shrinkwrap_calc_nearest_vertex(ShrinkwrapCalcData *calc)
        BVHTree *tree   = NULL;
        BVHTreeNearest nearest;
 
-       BENCH_VAR(query);
-
        int     numVerts;
        MVert *vert = NULL;
        MDeformVert *dvert = NULL;
 
+       BENCH_VAR(query);
 
 
        BENCH(tree = bvhtree_from_mesh_verts(calc->target));
index 7590cd0c3b9b6c6bd9dd77f1ff088bc465b1b413..25830321b93ca60ce149909aeb176d0911831f84 100644 (file)
@@ -495,8 +495,11 @@ typedef struct ShrinkwrapModifierData {
        struct Object *target;  /* shrink target */
        char vgroup_name[32];   /* optional vertexgroup name */
        float keptDist;                 /* distance offset from mesh/projection point */
+       float mergeDist;                /* distance to merge vertexs */
        short shrinkType;               /* shrink type projection */
        short shrinkOpts;               /* shrink options */
+
+       int pad;
 } ShrinkwrapModifierData;
 
 /* Shrinkwrap->shrinkType */
index 808a964019febed2f436420a913a1885cf880d99..5e1cfbea1839a6c3f7c0a2d55d5c15d5ee8177b9 100644 (file)
@@ -1830,7 +1830,7 @@ static void draw_modifier(uiBlock *block, Object *ob, ModifierData *md, int *xco
                        ShrinkwrapModifierData *smd = (ShrinkwrapModifierData*) md;
                        height = 86;
                        if (smd->shrinkType == MOD_SHRINKWRAP_NORMAL)
-                               height += 19*5;
+                               height += 19*6;
                }
                                                        /* roundbox 4 free variables: corner-rounding, nop, roundbox type, shade */
                uiDefBut(block, ROUNDBOX, 0, "", x-10, y-height-2, width, height-2, NULL, 5.0, 0.0, 12, 40, ""); 
@@ -2461,9 +2461,10 @@ static void draw_modifier(uiBlock *block, Object *ob, ModifierData *md, int *xco
 
                                uiDefButBitS(block, TOG, MOD_SHRINKWRAP_CULL_TARGET_FRONTFACE, B_MODIFIER_RECALC, "Cull frontfaces",    lx,(cy-=19),buttonWidth,19, &smd->shrinkOpts, 0, 0, 0, 0, "Controls whether a vertex can be projected to a front face on target");
                                uiDefButBitS(block, TOG, MOD_SHRINKWRAP_CULL_TARGET_BACKFACE,  B_MODIFIER_RECALC, "Cull backfaces",     lx,(cy-=19),buttonWidth,19, &smd->shrinkOpts, 0, 0, 0, 0, "Controls whether a vertex can be projected to a back face on target");
+                               uiDefButF(block, NUM, B_MODIFIER_RECALC, "Merge Dist:", lx,(cy-=19),buttonWidth,19, &smd->mergeDist, 0.0f, 0.01f, 0.01f, 0.01f, "Specify merge distance");
                        }
 
-                       but=uiDefBut(block, TEX, B_MODIFIER_RECALC, "VGroup: ",         lx, (cy-=19), buttonWidth,19, &smd->vgroup_name, 0.0, 31.0, 0, 0, "Vertex Group name");
+                       but=uiDefBut(block, TEX, B_MODIFIER_RECALC, "VGroup: ",         lx, (cy-=19), buttonWidth,19, &smd->vgroup_name, 0, 31, 0, 0, "Vertex Group name");
                        uiButSetCompleteFunc(but, autocomplete_vgroup, (void *)ob);
 
                        uiDefIDPoinBut(block, modifier_testMeshObj, ID_OB, B_CHANGEDEP, "Ob: ", lx, (cy-=19), buttonWidth,19, &smd->target, "Target to shrink to");