Added bvh nearest neighbour for nearest surface shrinkwrap
authorAndre Susano Pinto <andresusanopinto@gmail.com>
Tue, 27 May 2008 18:32:23 +0000 (18:32 +0000)
committerAndre Susano Pinto <andresusanopinto@gmail.com>
Tue, 27 May 2008 18:32:23 +0000 (18:32 +0000)
source/blender/blenkernel/intern/shrinkwrap.c
source/blender/blenlib/BLI_kdopbvh.h
source/blender/blenlib/intern/BLI_kdopbvh.c

index 68e0d21b379b19a410b1733e4387e8abbe71b33f..3b0aae8be2b212037cef9fcd9dc0a6962c2d4746 100644 (file)
@@ -86,6 +86,7 @@
 
 typedef void ( *Shrinkwrap_ForeachVertexCallback) (DerivedMesh *target, float *co, float *normal);
 
+static float nearest_point_in_tri_surface(const float *point, const float *v0, const float *v1, const float *v2, float *nearest);
 
 static void normal_short2float(const short *ns, float *nf)
 {
@@ -145,18 +146,19 @@ static BVHTree* bvhtree_from_mesh_tri(DerivedMesh *mesh)
        {
                for(i = 0; i < numFaces; i++)
                {
-                       float co[4][3];
+                       float co[3][3];
 
                        VECCOPY(co[0], vert[ face[i].v1 ].co);
                        VECCOPY(co[1], vert[ face[i].v2 ].co);
                        VECCOPY(co[2], vert[ face[i].v3 ].co);
-                       if(face[i].v4)
-                               VECCOPY(co[3], vert[ face[i].v4 ].co);
-
-
                        BLI_bvhtree_insert(tree, 2*i, co[0], 3);
                        if(face[i].v4)
-                               BLI_bvhtree_insert(tree, 2*i+1, co[1], 3);
+                       {
+                               /* second face is v1,v3,v4 */
+                               VECCOPY(co[1], vert[ face[i].v3 ].co);
+                               VECCOPY(co[2], vert[ face[i].v4 ].co);
+                               BLI_bvhtree_insert(tree, 2*i+1, co[0], 3);
+                       }
                }
 
                BLI_bvhtree_balance(tree);
@@ -165,7 +167,17 @@ static BVHTree* bvhtree_from_mesh_tri(DerivedMesh *mesh)
        return tree;
 }
 
+static float mesh_tri_nearest_point(void *userdata, int index, const float *co, float *nearest)
+{
+       DerivedMesh *mesh = (DerivedMesh*)(userdata);
+       MVert *vert     = (MVert*)mesh->getVertDataArray(mesh, CD_MVERT);
+       MFace *face = (MFace*)mesh->getFaceDataArray(mesh, CD_MFACE) + index/2;
 
+       if(index & 1)
+               return nearest_point_in_tri_surface(co, vert[ face->v1 ].co, vert[ face->v3 ].co, vert[ face->v4 ].co, nearest);
+       else
+               return nearest_point_in_tri_surface(co, vert[ face->v1 ].co, vert[ face->v2 ].co, vert[ face->v3 ].co, nearest);
+}
 
 /*
  * Raytree from mesh
@@ -482,7 +494,7 @@ static float nearest_point_in_tri_surface(const float *point, const float *v0, c
                nearest[2] = du[2]*nearest_2d[0] + dv[2] * nearest_2d[1] + dw[2] * plane_offset;
        }
 
-       return sasqrt(plane_sdist + normal_dist*normal_dist);
+       return plane_sdist + normal_dist*normal_dist;
 }
 
 
@@ -808,8 +820,8 @@ DerivedMesh *shrinkwrapModifier_do(ShrinkwrapModifierData *smd, Object *ob, Deri
                switch(smd->shrinkType)
                {
                        case MOD_SHRINKWRAP_NEAREST_SURFACE:
-//                             BENCH(shrinkwrap_calc_nearest_surface_point(&calc));
-                               BENCH(shrinkwrap_calc_foreach_vertex(&calc, bruteforce_shrinkwrap_calc_nearest_surface_point));
+                               BENCH(shrinkwrap_calc_nearest_surface_point(&calc));
+//                             BENCH(shrinkwrap_calc_foreach_vertex(&calc, bruteforce_shrinkwrap_calc_nearest_surface_point));
                        break;
 
                        case MOD_SHRINKWRAP_NORMAL:
@@ -888,7 +900,7 @@ void shrinkwrap_calc_nearest_vertex(ShrinkwrapCalcData *calc)
                }
                else nearest.dist = FLT_MAX;
 
-               index = BLI_bvhtree_find_nearest(tree, tmp_co, &nearest);
+               index = BLI_bvhtree_find_nearest(tree, tmp_co, &nearest, NULL, NULL);
 
                if(index != -1)
                {
@@ -1046,7 +1058,7 @@ void shrinkwrap_calc_nearest_surface_point(ShrinkwrapCalcData *calc)
                }
                else nearest.dist = FLT_MAX;
 
-               index = BLI_bvhtree_find_nearest(tree, tmp_co, &nearest);
+               index = BLI_bvhtree_find_nearest(tree, tmp_co, &nearest, mesh_tri_nearest_point, calc->target);
 
                if(index != -1)
                {
index 6a91e0e283bacd212d07ef1af7f2f0758462bd76..055c2754a21a2019817cb2d1ca384fca412ad9b2 100644 (file)
@@ -47,6 +47,10 @@ typedef struct BVHTreeNearest
        float dist;                     /* squared distance to search arround */
 } BVHTreeNearest;
 
+/* returns square of the minimum distance from given co to the node, nearest point is stored on nearest */
+typedef float (*BVHTree_NearestPointCallback) (void *userdata, int index, const float *co, float *nearest);
+
+
 BVHTree *BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis);
 void BLI_bvhtree_free(BVHTree *tree);
 
@@ -64,7 +68,7 @@ BVHTreeOverlap *BLI_bvhtree_overlap(BVHTree *tree1, BVHTree *tree2, int *result)
 float BLI_bvhtree_getepsilon(BVHTree *tree);
 
 /* find nearest node to the given coordinates (if nearest is given it will only search nodes where square distance is smaller than nearest->dist) */
-int BLI_bvhtree_find_nearest(BVHTree *tree, float *co, BVHTreeNearest *nearest);
+int BLI_bvhtree_find_nearest(BVHTree *tree, float *co, BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata);
 
 #endif // BLI_KDOPBVH_H
 
index b3cd00c00427a63429b6ead57e7d42c56fafece7..ef7c13a8918e2189bf9bcfb7f085628edc526cd0 100644 (file)
@@ -117,6 +117,8 @@ typedef struct BVHNearestData
 {
        BVHTree *tree;
        float   *co;
+       BVHTree_NearestPointCallback callback;
+       void    *userdata;
        float proj[13];                 //coordinates projection over axis
        BVHTreeNearest nearest;
 } BVHNearestData;
@@ -919,25 +921,32 @@ static void dfs_find_nearest(BVHNearestData *data, BVHNode *node)
        float nearest[3], sdist;
 
        sdist = calc_nearest_point(data, node, nearest);
-
        if(sdist >= data->nearest.dist) return;
 
        if(node->totnode == 0)
        {
+               if(data->callback)
+                       sdist = data->callback(data->userdata , node->index, data->co, nearest);
+
+               if(sdist >= data->nearest.dist) return;
+
                data->nearest.index     = node->index;
                VECCOPY(data->nearest.nearest, nearest);
                data->nearest.dist      = sdist;
        }
        else
        {
-               for(i=0; i != node->totnode; i++)
+               if(sdist < data->nearest.dist)
                {
-                       dfs_find_nearest(data, node->children[i]);
+                       for(i=0; i != node->totnode; i++)
+                       {
+                               dfs_find_nearest(data, node->children[i]);
+                       }
                }
        }
 }
 
-int BLI_bvhtree_find_nearest(BVHTree *tree, float *co, BVHTreeNearest *nearest)
+int BLI_bvhtree_find_nearest(BVHTree *tree, float *co, BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata)
 {
        int i;
 
@@ -947,6 +956,9 @@ int BLI_bvhtree_find_nearest(BVHTree *tree, float *co, BVHTreeNearest *nearest)
        data.tree = tree;
        data.co = co;
 
+       data.callback = callback;
+       data.userdata = userdata;
+
        for(i = data.tree->start_axis; i != data.tree->stop_axis; i++)
        {
                data.proj[i] = INPR(data.co, KDOP_AXES[i]);