merge with/from trunk at r35190
[blender.git] / source / blender / editors / armature / meshlaplacian.c
index 700f4573e3a3c88933cc7e0d6a400b460f82ae94..d06464c486b2128a00676bfb8d6704bfb340a376 100644 (file)
@@ -1,4 +1,4 @@
-/**
+/*
  * $Id$
  *
  * ***** BEGIN GPL LICENSE BLOCK *****
 #include "DNA_object_types.h"
 #include "DNA_mesh_types.h"
 #include "DNA_meshdata_types.h"
-#include "DNA_modifier_types.h"
 #include "DNA_scene_types.h"
 
 #include "BLI_math.h"
 #include "BLI_edgehash.h"
 #include "BLI_memarena.h"
+#include "BLI_utildefines.h"
 
 #include "BKE_DerivedMesh.h"
-#include "BKE_utildefines.h"
+#include "BKE_modifier.h"
+
 
 #ifdef RIGID_DEFORM
 #include "BLI_editVert.h"
 #include "BLI_polardecomp.h"
 #endif
 
-#include "RE_raytrace.h"
-
 #include "ONL_opennl.h"
 
 #include "BLO_sys_types.h" // for intptr_t support
 
 #include "ED_mesh.h"
+#include "ED_armature.h"
 
 #include "meshlaplacian.h"
 
 
 /* ************* XXX *************** */
-static void waitcursor(int val) {}
-static void progress_bar() {}
-static void start_progress_bar() {}
-static void end_progress_bar() {}
-static void error(char *str) { printf("error: %s\n", str); }
+static void waitcursor(int UNUSED(val)) {}
+static void progress_bar(int UNUSED(dummy_val), const char *UNUSED(dummy)) {}
+static void start_progress_bar(void) {}
+static void end_progress_bar(void) {}
+static void error(const char *str) { printf("error: %s\n", str); }
 /* ************* XXX *************** */
 
 
@@ -106,8 +106,7 @@ struct LaplacianSystem {
                float *p;                       /* values from all p vectors */
                float *mindist;         /* minimum distance to a bone for all vertices */
                
-               RayObject *raytree;     /* ray tracing acceleration structure */
-               RayFace   *faces;       /* faces to add to the ray tracing struture */
+               BVHTree   *bvhtree;     /* ray tracing acceleration structure */
                MFace     **vface;      /* a face that the vertex belongs to */
        } heat;
 
@@ -239,7 +238,7 @@ static void laplacian_triangle_weights(LaplacianSystem *sys, int f, int i1, int
        }
 }
 
-LaplacianSystem *laplacian_system_construct_begin(int totvert, int totface, int lsq)
+static LaplacianSystem *laplacian_system_construct_begin(int totvert, int totface, int lsq)
 {
        LaplacianSystem *sys;
 
@@ -281,7 +280,7 @@ void laplacian_add_triangle(LaplacianSystem *sys, int v1, int v2, int v3)
        sys->totface++;
 }
 
-void laplacian_system_construct_end(LaplacianSystem *sys)
+static void laplacian_system_construct_end(LaplacianSystem *sys)
 {
        int (*face)[3];
        int a, totvert=sys->totvert, totface=sys->totface;
@@ -332,7 +331,7 @@ void laplacian_system_construct_end(LaplacianSystem *sys)
        sys->edgehash= NULL;
 }
 
-void laplacian_system_delete(LaplacianSystem *sys)
+static void laplacian_system_delete(LaplacianSystem *sys)
 {
        if(sys->verts) MEM_freeN(sys->verts);
        if(sys->varea) MEM_freeN(sys->varea);
@@ -365,7 +364,7 @@ void laplacian_begin_solve(LaplacianSystem *sys, int index)
        }
 }
 
-void laplacian_add_right_hand_side(LaplacianSystem *sys, int v, float value)
+void laplacian_add_right_hand_side(LaplacianSystem *UNUSED(sys), int v, float value)
 {
        nlRightHandSideAdd(0, v, value);
 }
@@ -395,29 +394,65 @@ float laplacian_system_get_solution(int v)
 #define WEIGHT_LIMIT_END       0.025f
 #define DISTANCE_EPSILON       1e-4f
 
+typedef struct BVHCallbackUserData {
+       float start[3];
+       float vec[3];
+       LaplacianSystem *sys;
+} BVHCallbackUserData;
+
+static void bvh_callback(void *userdata, int index, const BVHTreeRay *UNUSED(ray), BVHTreeRayHit *hit)
+{
+       BVHCallbackUserData *data = (struct BVHCallbackUserData*)userdata;
+       MFace *mf = data->sys->heat.mface + index;
+       float (*verts)[3] = data->sys->heat.verts;
+       float lambda, uv[2], n[3], dir[3];
+
+       mul_v3_v3fl(dir, data->vec, hit->dist);
+
+       if(isect_ray_tri_v3(data->start, dir, verts[mf->v1], verts[mf->v2], verts[mf->v3], &lambda, uv)) {
+               normal_tri_v3(n, verts[mf->v1], verts[mf->v2], verts[mf->v3]);
+               if(lambda < 1.0f && dot_v3v3(n, data->vec) < -1e-5f) {
+                       hit->index = index;
+                       hit->dist *= lambda;
+               }
+       }
+
+       mul_v3_v3fl(dir, data->vec, hit->dist);
+
+       if(isect_ray_tri_v3(data->start, dir, verts[mf->v1], verts[mf->v3], verts[mf->v4], &lambda, uv)) {
+               normal_tri_v3(n, verts[mf->v1], verts[mf->v3], verts[mf->v4]);
+               if(lambda < 1.0f && dot_v3v3(n, data->vec) < -1e-5f) {
+                       hit->index = index;
+                       hit->dist *= lambda;
+               }
+       }
+}
+
 /* Raytracing for vertex to bone/vertex visibility */
 static void heat_ray_tree_create(LaplacianSystem *sys)
 {
        MFace *mface = sys->heat.mface;
+       float (*verts)[3] = sys->heat.verts;
        int totface = sys->heat.totface;
        int totvert = sys->heat.totvert;
        int a;
 
-       sys->heat.raytree = RE_rayobject_vbvh_create(totface);
-       sys->heat.faces = MEM_callocN(sizeof(RayFace)*totface, "Heat RayFaces");
+       sys->heat.bvhtree = BLI_bvhtree_new(totface, 0.0f, 4, 6);
        sys->heat.vface = MEM_callocN(sizeof(MFace*)*totvert, "HeatVFaces");
 
        for(a=0; a<totface; a++) {
-       
                MFace *mf = mface+a;
-               RayFace *rayface = sys->heat.faces+a;
-
-               RayObject *obj = RE_rayface_from_coords(
-                                                       rayface, &sys->heat, mf,
-                                                       sys->heat.verts[mf->v1], sys->heat.verts[mf->v2],
-                                                       sys->heat.verts[mf->v3], mf->v4 ? sys->heat.verts[mf->v4] : 0
-                                               );
-               RE_rayobject_add(sys->heat.raytree, obj); 
+               float bb[6];
+
+               INIT_MINMAX(bb, bb+3);
+               DO_MINMAX(verts[mf->v1], bb, bb+3);
+               DO_MINMAX(verts[mf->v2], bb, bb+3);
+               DO_MINMAX(verts[mf->v3], bb, bb+3);
+               if(mf->v4) {
+                       DO_MINMAX(verts[mf->v4], bb, bb+3);
+               }
+
+               BLI_bvhtree_insert(sys->heat.bvhtree, a, bb, 2);
                
                //Setup inverse pointers to use on isect.orig
                sys->heat.vface[mf->v1]= mf;
@@ -425,12 +460,14 @@ static void heat_ray_tree_create(LaplacianSystem *sys)
                sys->heat.vface[mf->v3]= mf;
                if(mf->v4) sys->heat.vface[mf->v4]= mf;
        }
-       RE_rayobject_done(sys->heat.raytree); 
+
+       BLI_bvhtree_balance(sys->heat.bvhtree); 
 }
 
 static int heat_ray_source_visible(LaplacianSystem *sys, int vertex, int source)
 {
-       Isect isec;
+    BVHTreeRayHit hit;
+       BVHCallbackUserData data;
        MFace *mface;
        float end[3];
        int visible;
@@ -439,27 +476,24 @@ static int heat_ray_source_visible(LaplacianSystem *sys, int vertex, int source)
        if(!mface)
                return 1;
 
-       /* setup isec */
-       memset(&isec, 0, sizeof(isec));
-       isec.mode= RE_RAY_SHADOW;
-       isec.lay= -1;
-       isec.orig.ob = &sys->heat;
-       isec.orig.face = mface;
-       isec.skip = RE_SKIP_CULLFACE;
-       
-       copy_v3_v3(isec.start, sys->heat.verts[vertex]);
+       data.sys= sys;
+       copy_v3_v3(data.start, sys->heat.verts[vertex]);
 
        if(sys->heat.root) /* bone */
-               closest_to_line_segment_v3(end, isec.start,
+               closest_to_line_segment_v3(end, data.start,
                        sys->heat.root[source], sys->heat.tip[source]);
        else /* vertex */
                copy_v3_v3(end, sys->heat.source[source]);
 
-       sub_v3_v3v3(isec.vec, end, isec.start);
-       isec.labda = 1.0f - 1e-5;
-       madd_v3_v3v3fl(isec.start, isec.start, isec.vec, 1e-5);
+       sub_v3_v3v3(data.vec, end, data.start);
+       madd_v3_v3v3fl(data.start, data.start, data.vec, 1e-5);
+       mul_v3_fl(data.vec, 1.0f - 2e-5);
+
+       /* pass normalized vec + distance to bvh */
+       hit.index = -1;
+       hit.dist = normalize_v3(data.vec);
 
-       visible= !RE_rayobject_raycast(sys->heat.raytree, &isec);
+       visible= BLI_bvhtree_ray_cast(sys->heat.bvhtree, data.start, data.vec, 0.0f, &hit, bvh_callback, (void*)&data) == -1;
 
        return visible;
 }
@@ -532,7 +566,7 @@ static void heat_set_H(LaplacianSystem *sys, int vertex)
        sys->heat.H[vertex]= h;
 }
 
-void heat_calc_vnormals(LaplacianSystem *sys)
+static void heat_calc_vnormals(LaplacianSystem *sys)
 {
        float fnor[3];
        int a, v1, v2, v3, (*face)[3];
@@ -586,9 +620,8 @@ static void heat_laplacian_create(LaplacianSystem *sys)
 
 static void heat_system_free(LaplacianSystem *sys)
 {
-       RE_rayobject_free(sys->heat.raytree);
+       BLI_bvhtree_free(sys->heat.bvhtree);
        MEM_freeN(sys->heat.vface);
-       MEM_freeN(sys->heat.faces);
 
        MEM_freeN(sys->heat.mindist);
        MEM_freeN(sys->heat.H);
@@ -611,13 +644,15 @@ static float heat_limit_weight(float weight)
                return weight;
 }
 
-void heat_bone_weighting(Object *ob, Mesh *me, float (*verts)[3], int numsource, bDeformGroup **dgrouplist, bDeformGroup **dgroupflip, float (*root)[3], float (*tip)[3], int *selected)
+void heat_bone_weighting(Object *ob, Mesh *me, float (*verts)[3], int numsource, bDeformGroup **dgrouplist, bDeformGroup **dgroupflip, float (*root)[3], float (*tip)[3], int *selected, const char **err_str)
 {
        LaplacianSystem *sys;
        MFace *mface;
        float solution, weight;
        int *vertsflipped = NULL, *mask= NULL;
-       int a, totface, j, bbone, firstsegment, lastsegment, thrownerror = 0;
+       int a, totface, j, bbone, firstsegment, lastsegment;
+
+       *err_str= NULL;
 
        /* count triangles and create mask */
        if(me->editflag & ME_EDIT_PAINT_MASK)
@@ -652,12 +687,16 @@ void heat_bone_weighting(Object *ob, Mesh *me, float (*verts)[3], int numsource,
 
        laplacian_system_construct_end(sys);
 
+#if 0 /*BMESH_TODO*/
        if(dgroupflip) {
                vertsflipped = MEM_callocN(sizeof(int)*me->totvert, "vertsflipped");
                for(a=0; a<me->totvert; a++)
                        vertsflipped[a] = mesh_get_x_mirror_vert(ob, a);
        }
-
+#else
+       dgroupflip = 0;
+#endif
+       
        /* compute weights per bone */
        for(j=0; j<numsource; j++) {
                if(!selected[j])
@@ -728,10 +767,8 @@ void heat_bone_weighting(Object *ob, Mesh *me, float (*verts)[3], int numsource,
                                }
                        }
                }
-               else if(!thrownerror) {
-                       error("Bone Heat Weighting:"
-                               " failed to find solution for one or more bones");
-                       thrownerror= 1;
+               else if(*err_str == NULL) {
+                       *err_str= "Bone Heat Weighting: failed to find solution for one or more bones";
                        break;
                }
 
@@ -1049,11 +1086,19 @@ typedef struct MeshDeformBind {
 
        /* direct solver */
        int *varidx;
-
-       /* raytrace */
-       RayObject *raytree;
 } MeshDeformBind;
 
+typedef struct MeshDeformIsect {
+       float start[3];
+       float vec[3];
+       float labda;
+
+       void *face;
+       int isect;
+       float u, v;
+       
+} MeshDeformIsect;
+
 /* ray intersection */
 
 /* our own triangle intersection, so we can fully control the epsilons and
@@ -1116,63 +1161,7 @@ static int meshdeform_tri_intersect(float orig[3], float end[3], float vert0[3],
        return 1;
 }
 
-/* blender's raytracer is not use now, even though it is much faster. it can
- * give problems with rays falling through, so we use our own intersection 
- * function above with tweaked epsilons */
-
-#if 0
-static MeshDeformBind *MESHDEFORM_BIND = NULL;
-
-static void meshdeform_ray_coords_func(RayFace *face, float **v1, float **v2, float **v3, float **v4)
-{
-       MFace *mface= (MFace*)face;
-       float (*cagecos)[3]= MESHDEFORM_BIND->cagecos;
-
-       *v1= cagecos[mface->v1];
-       *v2= cagecos[mface->v2];
-       *v3= cagecos[mface->v3];
-       *v4= (mface->v4)? cagecos[mface->v4]: NULL;
-}
-
-static int meshdeform_ray_check_func(Isect *is, RayFace *face)
-{
-       return 1;
-}
-
-static void meshdeform_ray_tree_create(MeshDeformBind *mdb)
-{
-       MFace *mface;
-       float min[3], max[3];
-       int a, totface;
-
-       /* create a raytrace tree from the mesh */
-       INIT_MINMAX(min, max);
-
-       for(a=0; a<mdb->totcagevert; a++)
-               DO_MINMAX(mdb->cagecos[a], min, max)
-
-       MESHDEFORM_BIND= mdb;
-
-       mface= mdb->cagedm->getFaceArray(mdb->cagedm);
-       totface= mdb->cagedm->getNumFaces(mdb->cagedm);
-
-       mdb->raytree= RE_ray_tree_create(64, totface, min, max,
-               meshdeform_ray_coords_func, meshdeform_ray_check_func);
-
-       for(a=0; a<totface; a++, mface++)
-               RE_ray_tree_add_face(mdb->raytree, mface);
-
-       RE_ray_tree_done(mdb->raytree);
-}
-
-static void meshdeform_ray_tree_free(MeshDeformBind *mdb)
-{
-       MESHDEFORM_BIND= NULL;
-       RE_ray_tree_free(mdb->raytree);
-}
-#endif
-
-static int meshdeform_intersect(MeshDeformBind *mdb, Isect *isec)
+static int meshdeform_intersect(MeshDeformBind *mdb, MeshDeformIsect *isec)
 {
        MFace *mface;
        float face[4][3], co[3], uvw[3], len, nor[3], end[3];
@@ -1180,8 +1169,8 @@ static int meshdeform_intersect(MeshDeformBind *mdb, Isect *isec)
 
        isec->labda= 1e10;
 
-       mface= mdb->cagedm->getFaceArray(mdb->cagedm);
-       totface= mdb->cagedm->getNumFaces(mdb->cagedm);
+       mface= mdb->cagedm->getTessFaceArray(mdb->cagedm);
+       totface= mdb->cagedm->getNumTessFaces(mdb->cagedm);
 
        add_v3_v3v3(end, isec->start, isec->vec);
 
@@ -1211,7 +1200,7 @@ static int meshdeform_intersect(MeshDeformBind *mdb, Isect *isec)
                        len= len_v3v3(isec->start, co)/len_v3v3(isec->start, end);
                        if(len < isec->labda) {
                                isec->labda= len;
-                               isec->hit.face = mface;
+                               isec->face = mface;
                                isec->isect= (INPR(isec->vec, nor) <= 0.0f);
                                is= 1;
                        }
@@ -1224,7 +1213,7 @@ static int meshdeform_intersect(MeshDeformBind *mdb, Isect *isec)
 static MDefBoundIsect *meshdeform_ray_tree_intersect(MeshDeformBind *mdb, float *co1, float *co2)
 {
        MDefBoundIsect *isect;
-       Isect isec;
+       MeshDeformIsect isec;
        float (*cagecos)[3];
        MFace *mface;
        float vert[4][3], len, end[3];
@@ -1232,21 +1221,15 @@ static MDefBoundIsect *meshdeform_ray_tree_intersect(MeshDeformBind *mdb, float
 
        /* setup isec */
        memset(&isec, 0, sizeof(isec));
-       isec.mode= RE_RAY_MIRROR; /* we want the closest intersection */
-       isec.lay= -1;
        isec.labda= 1e10f;
 
        VECADD(isec.start, co1, epsilon);
        VECADD(end, co2, epsilon);
        sub_v3_v3v3(isec.vec, end, isec.start);
 
-#if 0
-       /*if(RE_ray_tree_intersect(mdb->raytree, &isec)) {*/
-#endif
-
        if(meshdeform_intersect(mdb, &isec)) {
                len= isec.labda;
-               mface=(MFace*)isec.hit.face;
+               mface=(MFace*)isec.face;
 
                /* create MDefBoundIsect */
                isect= BLI_memarena_alloc(mdb->memarena, sizeof(*isect));
@@ -1286,11 +1269,9 @@ static int meshdeform_inside_cage(MeshDeformBind *mdb, float *co)
 {
        MDefBoundIsect *isect;
        float outside[3], start[3], dir[3];
-       int i, counter;
+       int i;
 
        for(i=1; i<=6; i++) {
-               counter = 0;
-
                outside[0] = co[0] + (mdb->max[0] - mdb->min[0] + 1.0f)*MESHDEFORM_OFFSET[i][0];
                outside[1] = co[1] + (mdb->max[1] - mdb->min[1] + 1.0f)*MESHDEFORM_OFFSET[i][1];
                outside[2] = co[2] + (mdb->max[2] - mdb->min[2] + 1.0f)*MESHDEFORM_OFFSET[i][2];
@@ -1423,7 +1404,7 @@ static void meshdeform_bind_floodfill(MeshDeformBind *mdb)
        MEM_freeN(stack);
 }
 
-static float meshdeform_boundary_phi(MeshDeformBind *mdb, MDefBoundIsect *isect, int cagevert)
+static float meshdeform_boundary_phi(MeshDeformBind *UNUSED(mdb), MDefBoundIsect *isect, int cagevert)
 {
        int a;
 
@@ -1434,7 +1415,7 @@ static float meshdeform_boundary_phi(MeshDeformBind *mdb, MDefBoundIsect *isect,
        return 0.0f;
 }
 
-static float meshdeform_interp_w(MeshDeformBind *mdb, float *gridvec, float *vec, int cagevert)
+static float meshdeform_interp_w(MeshDeformBind *mdb, float *gridvec, float *UNUSED(vec), int UNUSED(cagevert))
 {
        float dvec[3], ivec[3], wx, wy, wz, result=0.0f;
        float weight, totweight= 0.0f;
@@ -1585,7 +1566,7 @@ static void meshdeform_matrix_add_semibound_phi(MeshDeformBind *mdb, int x, int
        }
 }
 
-static void meshdeform_matrix_add_exterior_phi(MeshDeformBind *mdb, int x, int y, int z, int cagevert)
+static void meshdeform_matrix_add_exterior_phi(MeshDeformBind *mdb, int x, int y, int z, int UNUSED(cagevert))
 {
        float phi, totweight;
        int i, a, acenter;
@@ -1734,7 +1715,7 @@ static void meshdeform_matrix_solve(MeshDeformBind *mdb)
        nlDeleteContext(context);
 }
 
-static void harmonic_coordinates_bind(Scene *scene, MeshDeformModifierData *mmd, MeshDeformBind *mdb)
+static void harmonic_coordinates_bind(Scene *UNUSED(scene), MeshDeformModifierData *mmd, MeshDeformBind *mdb)
 {
        MDefBindInfluence *inf;
        MDefInfluence *mdinf;
@@ -1789,11 +1770,6 @@ static void harmonic_coordinates_bind(Scene *scene, MeshDeformModifierData *mmd,
 
        progress_bar(0, "Setting up mesh deform system");
 
-#if 0
-       /* create ray tree */
-       meshdeform_ray_tree_create(mdb);
-#endif
-
        totinside= 0;
        for(a=0; a<mdb->totvert; a++) {
                copy_v3_v3(vec, mdb->vertexcos[a]);
@@ -1816,11 +1792,6 @@ static void harmonic_coordinates_bind(Scene *scene, MeshDeformModifierData *mmd,
                        for(x=0; x<mdb->size; x++)
                                meshdeform_add_intersections(mdb, x, y, z);
 
-#if 0
-       /* free ray tree */
-       meshdeform_ray_tree_free(mdb);
-#endif
-
        /* compute exterior and interior tags */
        meshdeform_bind_floodfill(mdb);
 
@@ -1888,7 +1859,7 @@ static void harmonic_coordinates_bind(Scene *scene, MeshDeformModifierData *mmd,
 static void heat_weighting_bind(Scene *scene, DerivedMesh *dm, MeshDeformModifierData *mmd, MeshDeformBind *mdb)
 {
        LaplacianSystem *sys;
-       MFace *mface= dm->getFaceArray(dm), *mf;
+       MFace *mface= dm->getTessFaceArray(dm), *mf;
        int totvert= dm->getNumVerts(dm);
        int totface= dm->getNumFaces(dm);
        float solution, weight;
@@ -1954,7 +1925,7 @@ static void heat_weighting_bind(Scene *scene, DerivedMesh *dm, MeshDeformModifie
 }
 #endif
 
-void mesh_deform_bind(Scene *scene, DerivedMesh *dm, MeshDeformModifierData *mmd, float *vertexcos, int totvert, float cagemat[][4])
+void mesh_deform_bind(Scene *scene, MeshDeformModifierData *mmd, float *vertexcos, int totvert, float cagemat[][4])
 {
        MeshDeformBind mdb;
        MVert *mvert;
@@ -1991,19 +1962,22 @@ void mesh_deform_bind(Scene *scene, DerivedMesh *dm, MeshDeformModifierData *mmd
 #endif
 
        /* assign bind variables */
-       mmd->bindcos= (float*)mdb.cagecos;
+       mmd->bindcagecos= (float*)mdb.cagecos;
        mmd->totvert= mdb.totvert;
        mmd->totcagevert= mdb.totcagevert;
        copy_m4_m4(mmd->bindmat, mmd->object->obmat);
 
-       /* transform bindcos to world space */
+       /* transform bindcagecos to world space */
        for(a=0; a<mdb.totcagevert; a++)
-               mul_m4_v3(mmd->object->obmat, mmd->bindcos+a*3);
+               mul_m4_v3(mmd->object->obmat, mmd->bindcagecos+a*3);
 
        /* free */
        mdb.cagedm->release(mdb.cagedm);
        MEM_freeN(mdb.vertexcos);
 
+       /* compact weights */
+       modifier_mdef_compact_influences((ModifierData*)mmd);
+
        end_progress_bar();
        waitcursor(0);
 }