diff options
Diffstat (limited to 'source/blender/blenkernel/intern/bvhutils.c')
-rw-r--r-- | source/blender/blenkernel/intern/bvhutils.c | 115 |
1 files changed, 56 insertions, 59 deletions
diff --git a/source/blender/blenkernel/intern/bvhutils.c b/source/blender/blenkernel/intern/bvhutils.c index f0bc2dddbad..24583c124e6 100644 --- a/source/blender/blenkernel/intern/bvhutils.c +++ b/source/blender/blenkernel/intern/bvhutils.c @@ -101,11 +101,11 @@ float nearest_point_in_tri_surface(const float v0[3], const float v1[3], const f sub_v3_v3v3(e1, v2, v0); A00 = dot_v3v3(e0, e0); - A01 = dot_v3v3(e0, e1 ); - A11 = dot_v3v3(e1, e1 ); - B0 = dot_v3v3(diff, e0 ); - B1 = dot_v3v3(diff, e1 ); - C = dot_v3v3(diff, diff ); + A01 = dot_v3v3(e0, e1); + A11 = dot_v3v3(e1, e1); + B0 = dot_v3v3(diff, e0); + B1 = dot_v3v3(diff, e1); + C = dot_v3v3(diff, diff); Det = fabs(A00 * A11 - A01 * A01); S = A01 * B1 - A11 * B0; T = A01 * B0 - A00 * B1; @@ -122,7 +122,7 @@ float nearest_point_in_tri_surface(const float v0[3], const float v1[3], const f } else { if (fabsf(A00) > FLT_EPSILON) - S = -B0/A00; + S = -B0 / A00; else S = 0.0f; sqrDist = B0 * S + C; @@ -195,7 +195,7 @@ float nearest_point_in_tri_surface(const float v0[3], const float v1[3], const f } } else { /* Region 0 */ - // Minimum at interior lv + /* Minimum at interior lv */ float invDet; if (fabsf(Det) > FLT_EPSILON) invDet = 1.0f / Det; @@ -203,8 +203,8 @@ float nearest_point_in_tri_surface(const float v0[3], const float v1[3], const f invDet = 0.0f; S *= invDet; T *= invDet; - sqrDist = S * ( A00 * S + A01 * T + 2.0f * B0) + - T * ( A01 * S + A11 * T + 2.0f * B1 ) + C; + sqrDist = S * (A00 * S + A01 * T + 2.0f * B0) + + T * (A01 * S + A11 * T + 2.0f * B1) + C; } } else { @@ -213,10 +213,10 @@ float nearest_point_in_tri_surface(const float v0[3], const float v1[3], const f if (S < 0.0f) { /* Region 2 */ tmp0 = A01 + B0; tmp1 = A11 + B1; - if ( tmp1 > tmp0 ) { + if (tmp1 > tmp0) { numer = tmp1 - tmp0; denom = A00 - 2.0f * A01 + A11; - if ( numer >= denom ) { + if (numer >= denom) { S = 1.0f; T = 0.0f; sqrDist = A00 + 2.0f * B0 + C; @@ -228,14 +228,14 @@ float nearest_point_in_tri_surface(const float v0[3], const float v1[3], const f else S = 0.0f; T = 1.0f - S; - sqrDist = S * ( A00 * S + A01 * T + 2.0f * B0 ) + - T * ( A01 * S + A11 * T + 2.0f * B1 ) + C; + sqrDist = S * (A00 * S + A01 * T + 2.0f * B0) + + T * (A01 * S + A11 * T + 2.0f * B1) + C; le = 2; } } else { S = 0.0f; - if ( tmp1 <= 0.0f ) { + if (tmp1 <= 0.0f) { T = 1.0f; sqrDist = A11 + 2.0f * B1 + C; lv = 2; @@ -258,10 +258,10 @@ float nearest_point_in_tri_surface(const float v0[3], const float v1[3], const f else if (T < 0.0f) { /* Region 6 */ tmp0 = A01 + B1; tmp1 = A00 + B0; - if ( tmp1 > tmp0 ) { + if (tmp1 > tmp0) { numer = tmp1 - tmp0; denom = A00 - 2.0f * A01 + A11; - if ( numer >= denom ) { + if (numer >= denom) { T = 1.0f; S = 0.0f; sqrDist = A11 + 2.0f * B1 + C; @@ -273,8 +273,8 @@ float nearest_point_in_tri_surface(const float v0[3], const float v1[3], const f else T = 0.0f; S = 1.0f - T; - sqrDist = S * ( A00 * S + A01 * T + 2.0f * B0 ) + - T * ( A01 * S + A11 * T + 2.0f * B1 ) + C; + sqrDist = S * (A00 * S + A01 * T + 2.0f * B0) + + T * (A01 * S + A11 * T + 2.0f * B1) + C; le = 2; } } @@ -302,7 +302,7 @@ float nearest_point_in_tri_surface(const float v0[3], const float v1[3], const f } else { /* Region 1 */ numer = A11 + B1 - A01 - B0; - if ( numer <= 0.0f ) { + if (numer <= 0.0f) { S = 0.0f; T = 1.0f; sqrDist = A11 + 2.0f * B1 + C; @@ -310,7 +310,7 @@ float nearest_point_in_tri_surface(const float v0[3], const float v1[3], const f } else { denom = A00 - 2.0f * A01 + A11; - if ( numer >= denom ) { + if (numer >= denom) { S = 1.0f; T = 0.0f; sqrDist = A00 + 2.0f * B0 + C; @@ -322,8 +322,8 @@ float nearest_point_in_tri_surface(const float v0[3], const float v1[3], const f else S = 0.0f; T = 1.0f - S; - sqrDist = S * ( A00 * S + A01 * T + 2.0f * B0 ) + - T * ( A01 * S + A11 * T + 2.0f * B1 ) + C; + sqrDist = S * (A00 * S + A01 * T + 2.0f * B0) + + T * (A01 * S + A11 * T + 2.0f * B1) + C; le = 2; } } @@ -331,7 +331,7 @@ float nearest_point_in_tri_surface(const float v0[3], const float v1[3], const f } // Account for numerical round-off error - if ( sqrDist < FLT_EPSILON ) + if (sqrDist < FLT_EPSILON) sqrDist = 0.0f; { @@ -362,19 +362,18 @@ float nearest_point_in_tri_surface(const float v0[3], const float v1[3], const f // userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree. static void mesh_faces_nearest_point(void *userdata, int index, const float co[3], BVHTreeNearest *nearest) { - const BVHTreeFromMesh *data = (BVHTreeFromMesh*) userdata; - MVert *vert = data->vert; + const BVHTreeFromMesh *data = (BVHTreeFromMesh *) userdata; + MVert *vert = data->vert; MFace *face = data->face + index; float *t0, *t1, *t2, *t3; - t0 = vert[ face->v1 ].co; - t1 = vert[ face->v2 ].co; - t2 = vert[ face->v3 ].co; - t3 = face->v4 ? vert[ face->v4].co : NULL; + t0 = vert[face->v1].co; + t1 = vert[face->v2].co; + t2 = vert[face->v3].co; + t3 = face->v4 ? vert[face->v4].co : NULL; - do - { + do { float nearest_tmp[3], dist; int vertex, edge; @@ -397,8 +396,8 @@ static void mesh_faces_nearest_point(void *userdata, int index, const float co[3 // userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree. static void mesh_faces_spherecast(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit) { - const BVHTreeFromMesh *data = (BVHTreeFromMesh*) userdata; - MVert *vert = data->vert; + const BVHTreeFromMesh *data = (BVHTreeFromMesh *) userdata; + MVert *vert = data->vert; MFace *face = data->face + index; float *t0, *t1, *t2, *t3; @@ -408,8 +407,7 @@ static void mesh_faces_spherecast(void *userdata, int index, const BVHTreeRay *r t3 = face->v4 ? vert[face->v4].co : NULL; - do - { + do { float dist; if (data->sphere_radius == 0.0f) dist = bvhtree_ray_tri_intersection(ray, hit->dist, t0, t1, t2); @@ -435,14 +433,14 @@ static void mesh_faces_spherecast(void *userdata, int index, const BVHTreeRay *r // userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree. static void mesh_edges_nearest_point(void *userdata, int index, const float co[3], BVHTreeNearest *nearest) { - const BVHTreeFromMesh *data = (BVHTreeFromMesh*) userdata; - MVert *vert = data->vert; + const BVHTreeFromMesh *data = (BVHTreeFromMesh *) userdata; + MVert *vert = data->vert; MEdge *edge = data->edge + index; float nearest_tmp[3], dist; float *t0, *t1; - t0 = vert[ edge->v1 ].co; - t1 = vert[ edge->v2 ].co; + t0 = vert[edge->v1].co; + t1 = vert[edge->v2].co; closest_to_line_segment_v3(nearest_tmp, co, t0, t1); dist = len_squared_v3v3(nearest_tmp, co); @@ -460,15 +458,15 @@ static void mesh_edges_nearest_point(void *userdata, int index, const float co[3 * BVH builders */ // Builds a bvh tree.. where nodes are the vertexs of the given mesh -BVHTree* bvhtree_from_mesh_verts(BVHTreeFromMesh *data, DerivedMesh *mesh, float epsilon, int tree_type, int axis) +BVHTree *bvhtree_from_mesh_verts(BVHTreeFromMesh *data, DerivedMesh *mesh, float epsilon, int tree_type, int axis) { BVHTree *tree = bvhcache_find(&mesh->bvhCache, BVHTREE_FROM_VERTICES); //Not in cache if (tree == NULL) { int i; - int numVerts= mesh->getNumVerts(mesh); - MVert *vert = mesh->getVertDataArray(mesh, CD_MVERT); + int numVerts = mesh->getNumVerts(mesh); + MVert *vert = mesh->getVertDataArray(mesh, CD_MVERT); if (vert != NULL) { tree = BLI_bvhtree_new(numVerts, epsilon, tree_type, axis); @@ -514,14 +512,14 @@ BVHTree* bvhtree_from_mesh_verts(BVHTreeFromMesh *data, DerivedMesh *mesh, float } // Builds a bvh tree.. where nodes are the faces of the given mesh. -BVHTree* bvhtree_from_mesh_faces(BVHTreeFromMesh *data, DerivedMesh *mesh, float epsilon, int tree_type, int axis) +BVHTree *bvhtree_from_mesh_faces(BVHTreeFromMesh *data, DerivedMesh *mesh, float epsilon, int tree_type, int axis) { BVHTree *tree = bvhcache_find(&mesh->bvhCache, BVHTREE_FROM_FACES); //Not in cache if (tree == NULL) { int i; - int numFaces= mesh->getNumTessFaces(mesh); + int numFaces = mesh->getNumTessFaces(mesh); /* BMESH specific check that we have tessfaces, * we _could_ tessellate here but rather not - campbell @@ -534,7 +532,7 @@ BVHTree* bvhtree_from_mesh_faces(BVHTreeFromMesh *data, DerivedMesh *mesh, float /* Create a bvh-tree of the given target */ tree = BLI_bvhtree_new(numFaces, epsilon, tree_type, axis); if (tree != NULL) { - BMEditMesh *em= data->em_evil; + BMEditMesh *em = data->em_evil; if (em) { /* data->em_evil is only set for snapping, and only for the mesh of the object * which is currently open in edit mode. When set, the bvhtree should not contain @@ -594,17 +592,17 @@ BVHTree* bvhtree_from_mesh_faces(BVHTreeFromMesh *data, DerivedMesh *mesh, float } } else { - MVert *vert = mesh->getVertDataArray(mesh, CD_MVERT); + MVert *vert = mesh->getVertDataArray(mesh, CD_MVERT); MFace *face = mesh->getTessFaceDataArray(mesh, CD_MFACE); if (vert != NULL && face != NULL) { for (i = 0; i < numFaces; i++) { float co[4][3]; - copy_v3_v3(co[0], vert[ face[i].v1 ].co); - copy_v3_v3(co[1], vert[ face[i].v2 ].co); - copy_v3_v3(co[2], vert[ face[i].v3 ].co); + copy_v3_v3(co[0], vert[face[i].v1].co); + copy_v3_v3(co[1], vert[face[i].v2].co); + copy_v3_v3(co[2], vert[face[i].v3].co); if (face[i].v4) - copy_v3_v3(co[3], vert[ face[i].v4 ].co); + copy_v3_v3(co[3], vert[face[i].v4].co); BLI_bvhtree_insert(tree, i, co[0], face[i].v4 ? 4 : 3); } @@ -644,15 +642,15 @@ BVHTree* bvhtree_from_mesh_faces(BVHTreeFromMesh *data, DerivedMesh *mesh, float } // Builds a bvh tree.. where nodes are the faces of the given mesh. -BVHTree* bvhtree_from_mesh_edges(BVHTreeFromMesh *data, DerivedMesh *mesh, float epsilon, int tree_type, int axis) +BVHTree *bvhtree_from_mesh_edges(BVHTreeFromMesh *data, DerivedMesh *mesh, float epsilon, int tree_type, int axis) { BVHTree *tree = bvhcache_find(&mesh->bvhCache, BVHTREE_FROM_EDGES); //Not in cache if (tree == NULL) { int i; - int numEdges= mesh->getNumEdges(mesh); - MVert *vert = mesh->getVertDataArray(mesh, CD_MVERT); + int numEdges = mesh->getNumEdges(mesh); + MVert *vert = mesh->getVertDataArray(mesh, CD_MVERT); MEdge *edge = mesh->getEdgeDataArray(mesh, CD_MEDGE); if (vert != NULL && edge != NULL) { @@ -661,8 +659,8 @@ BVHTree* bvhtree_from_mesh_edges(BVHTreeFromMesh *data, DerivedMesh *mesh, float if (tree != NULL) { for (i = 0; i < numEdges; i++) { float co[4][3]; - copy_v3_v3(co[0], vert[ edge[i].v1 ].co); - copy_v3_v3(co[1], vert[ edge[i].v2 ].co); + copy_v3_v3(co[0], vert[edge[i].v1].co); + copy_v3_v3(co[1], vert[edge[i].v2].co); BLI_bvhtree_insert(tree, i, co[0], 2); } @@ -712,8 +710,7 @@ void free_bvhtree_from_mesh(struct BVHTreeFromMesh *data) /* BVHCache */ -typedef struct BVHCacheItem -{ +typedef struct BVHCacheItem { int type; BVHTree *tree; @@ -721,8 +718,8 @@ typedef struct BVHCacheItem static void bvhcacheitem_set_if_match(void *_cached, void *_search) { - BVHCacheItem * cached = (BVHCacheItem *)_cached; - BVHCacheItem * search = (BVHCacheItem *)_search; + BVHCacheItem *cached = (BVHCacheItem *)_cached; + BVHCacheItem *search = (BVHCacheItem *)_search; if (search->type == cached->type) { search->tree = cached->tree; |