From fa919d23bc45ff5d9db5bb374d4fad561bf18b6c Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Tue, 16 Apr 2013 05:23:34 +0000 Subject: move editmesh_bvh.c into blenkernel. --- source/blender/blenkernel/intern/editmesh_bvh.c | 357 ++++++++++++++++++++++++ 1 file changed, 357 insertions(+) create mode 100644 source/blender/blenkernel/intern/editmesh_bvh.c (limited to 'source/blender/blenkernel/intern/editmesh_bvh.c') diff --git a/source/blender/blenkernel/intern/editmesh_bvh.c b/source/blender/blenkernel/intern/editmesh_bvh.c new file mode 100644 index 00000000000..ceca90d47b6 --- /dev/null +++ b/source/blender/blenkernel/intern/editmesh_bvh.c @@ -0,0 +1,357 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * The Original Code is Copyright (C) 2010 by Blender Foundation. + * All rights reserved. + * + * The Original Code is: all of this file. + * + * Contributor(s): Joseph Eagar + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/blenkernel/intern/editmesh_bvh.c + * \ingroup bke + */ + +#include "MEM_guardedalloc.h" + +#include "DNA_scene_types.h" +#include "DNA_object_types.h" + +#include "BLI_math.h" +#include "BLI_smallhash.h" + +#include "BKE_DerivedMesh.h" +#include "BKE_editmesh.h" + +#include "BKE_editmesh_bvh.h" /* own include */ + + +typedef struct BMBVHTree { + BMEditMesh *em; + BMesh *bm; + BVHTree *tree; + float epsilon; + float maxdist; /* for nearest point search */ + float uv[2]; + + /* stuff for topological vert search */ + BMVert *v, *curv; + GHash *gh; + float curw, curd; + float co[3], (*cagecos)[3], (*cos)[3]; + int curtag, flag; + + Object *ob; + Scene *scene; +} BMBVHTree; + +static void cage_mapped_verts_callback(void *userData, int index, const float co[3], + const float UNUSED(no_f[3]), const short UNUSED(no_s[3])) +{ + void **data = userData; + BMEditMesh *em = data[0]; + float (*cagecos)[3] = data[1]; + SmallHash *hash = data[2]; + + if (index >= 0 && index < em->bm->totvert && !BLI_smallhash_haskey(hash, index)) { + BLI_smallhash_insert(hash, index, NULL); + copy_v3_v3(cagecos[index], co); + } +} + +BMBVHTree *BMBVH_NewBVH(BMEditMesh *em, int flag, Scene *scene) +{ + BMBVHTree *tree = MEM_callocN(sizeof(*tree), "BMBVHTree"); + DerivedMesh *cage, *final; + SmallHash shash; + float cos[3][3], (*cagecos)[3] = NULL; + int i; + int tottri; + + /* when initializing cage verts, we only want the first cage coordinate for each vertex, + * so that e.g. mirror or array use original vertex coordinates and not mirrored or duplicate */ + BLI_smallhash_init(&shash); + + BMEdit_RecalcTessellation(em); + + tree->ob = em->ob; + tree->scene = scene; + tree->em = em; + tree->bm = em->bm; + tree->epsilon = FLT_EPSILON * 2.0f; + tree->flag = flag; + + if (flag & (BMBVH_RESPECT_SELECT)) { + tottri = 0; + for (i = 0; i < em->tottri; i++) { + if (BM_elem_flag_test(em->looptris[i][0]->f, BM_ELEM_SELECT)) { + tottri++; + } + } + } + else if (flag & (BMBVH_RESPECT_HIDDEN)) { + tottri = 0; + for (i = 0; i < em->tottri; i++) { + if (!BM_elem_flag_test(em->looptris[i][0]->f, BM_ELEM_HIDDEN)) { + tottri++; + } + } + } + else { + tottri = em->tottri; + } + + tree->tree = BLI_bvhtree_new(tottri, tree->epsilon, 8, 8); + + if (flag & BMBVH_USE_CAGE) { + BMIter iter; + BMVert *v; + void *data[3]; + + tree->cos = MEM_callocN(sizeof(float) * 3 * em->bm->totvert, "bmbvh cos"); + BM_ITER_MESH_INDEX (v, &iter, em->bm, BM_VERTS_OF_MESH, i) { + BM_elem_index_set(v, i); /* set_inline */ + copy_v3_v3(tree->cos[i], v->co); + } + em->bm->elem_index_dirty &= ~BM_VERT; + + + cage = editbmesh_get_derived_cage_and_final(scene, em->ob, em, &final, CD_MASK_DERIVEDMESH); + cagecos = MEM_callocN(sizeof(float) * 3 * em->bm->totvert, "bmbvh cagecos"); + + data[0] = em; + data[1] = cagecos; + data[2] = &shash; + + cage->foreachMappedVert(cage, cage_mapped_verts_callback, data); + } + + tree->cagecos = cagecos; + + for (i = 0; i < em->tottri; i++) { + + + if (flag & BMBVH_RESPECT_SELECT) { + /* note, the arrays wont align now! take care */ + if (!BM_elem_flag_test(em->looptris[i][0]->f, BM_ELEM_SELECT)) { + continue; + } + } + else if (flag & BMBVH_RESPECT_HIDDEN) { + /* note, the arrays wont align now! take care */ + if (BM_elem_flag_test(em->looptris[i][0]->f, BM_ELEM_HIDDEN)) { + continue; + } + } + + if (flag & BMBVH_USE_CAGE) { + copy_v3_v3(cos[0], cagecos[BM_elem_index_get(em->looptris[i][0]->v)]); + copy_v3_v3(cos[1], cagecos[BM_elem_index_get(em->looptris[i][1]->v)]); + copy_v3_v3(cos[2], cagecos[BM_elem_index_get(em->looptris[i][2]->v)]); + } + else { + copy_v3_v3(cos[0], em->looptris[i][0]->v->co); + copy_v3_v3(cos[1], em->looptris[i][1]->v->co); + copy_v3_v3(cos[2], em->looptris[i][2]->v->co); + } + + BLI_bvhtree_insert(tree->tree, i, (float *)cos, 3); + } + + BLI_bvhtree_balance(tree->tree); + BLI_smallhash_release(&shash); + + return tree; +} + +void BMBVH_FreeBVH(BMBVHTree *tree) +{ + BLI_bvhtree_free(tree->tree); + + if (tree->cagecos) + MEM_freeN(tree->cagecos); + if (tree->cos) + MEM_freeN(tree->cos); + + MEM_freeN(tree); +} + +/* taken from bvhutils.c */ +static float ray_tri_intersection(const BVHTreeRay *ray, const float UNUSED(m_dist), + const float v0[3], const float v1[3], const float v2[3], + float r_uv[2], float UNUSED(e)) +{ + float dist; + + if (isect_ray_tri_v3((float *)ray->origin, (float *)ray->direction, v0, v1, v2, &dist, r_uv)) { + return dist; + } + + return FLT_MAX; +} + +static void raycallback(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit) +{ + BMBVHTree *tree = userdata; + BMLoop **ls = tree->em->looptris[index]; + float dist, uv[2]; + + if (!ls[0] || !ls[1] || !ls[2]) + return; + + dist = ray_tri_intersection(ray, hit->dist, ls[0]->v->co, ls[1]->v->co, + ls[2]->v->co, uv, tree->epsilon); + if (dist < hit->dist) { + hit->dist = dist; + hit->index = index; + + copy_v3_v3(hit->no, ls[0]->v->no); + + copy_v3_v3(hit->co, ray->direction); + normalize_v3(hit->co); + mul_v3_fl(hit->co, dist); + add_v3_v3(hit->co, ray->origin); + + copy_v2_v2(tree->uv, uv); + } +} + +BMFace *BMBVH_RayCast(BMBVHTree *tree, const float co[3], const float dir[3], + float r_hitout[3], float r_cagehit[3]) +{ + BVHTreeRayHit hit; + + hit.dist = FLT_MAX; + hit.index = -1; + + tree->uv[0] = tree->uv[1] = 0.0f; + + BLI_bvhtree_ray_cast(tree->tree, co, dir, 0.0f, &hit, raycallback, tree); + if (hit.dist != FLT_MAX && hit.index != -1) { + if (r_hitout) { + if (tree->flag & BMBVH_RETURN_ORIG) { + BMVert *v1, *v2, *v3; + int i; + + v1 = tree->em->looptris[hit.index][0]->v; + v2 = tree->em->looptris[hit.index][1]->v; + v3 = tree->em->looptris[hit.index][2]->v; + + for (i = 0; i < 3; i++) { + r_hitout[i] = v1->co[i] + ((v2->co[i] - v1->co[i]) * tree->uv[0]) + + ((v3->co[i] - v1->co[i]) * tree->uv[1]); + } + } + else { + copy_v3_v3(r_hitout, hit.co); + } + + if (r_cagehit) { + copy_v3_v3(r_cagehit, hit.co); + } + } + + return tree->em->looptris[hit.index][0]->f; + } + + return NULL; +} + +BVHTree *BMBVH_BVHTree(BMBVHTree *tree) +{ + return tree->tree; +} + +static void vertsearchcallback(void *userdata, int index, const float *UNUSED(co), BVHTreeNearest *hit) +{ + BMBVHTree *tree = userdata; + BMLoop **ls = tree->em->looptris[index]; + float dist, maxdist, v[3]; + int i; + + maxdist = tree->maxdist; + + for (i = 0; i < 3; i++) { + sub_v3_v3v3(v, hit->co, ls[i]->v->co); + + dist = len_v3(v); + if (dist < hit->dist && dist < maxdist) { + copy_v3_v3(hit->co, ls[i]->v->co); + copy_v3_v3(hit->no, ls[i]->v->no); + hit->dist = dist; + hit->index = index; + } + } +} + +BMVert *BMBVH_FindClosestVert(BMBVHTree *tree, const float co[3], const float maxdist) +{ + BVHTreeNearest hit; + + copy_v3_v3(hit.co, co); + hit.dist = maxdist * 5; + hit.index = -1; + + tree->maxdist = maxdist; + + BLI_bvhtree_find_nearest(tree->tree, co, &hit, vertsearchcallback, tree); + if (hit.dist != FLT_MAX && hit.index != -1) { + BMLoop **ls = tree->em->looptris[hit.index]; + float dist, curdist = tree->maxdist, v[3]; + int cur = 0, i; + + /* maxdist = tree->maxdist; */ /* UNUSED */ + + for (i = 0; i < 3; i++) { + sub_v3_v3v3(v, hit.co, ls[i]->v->co); + + dist = len_v3(v); + if (dist < curdist) { + cur = i; + curdist = dist; + } + } + + return ls[cur]->v; + } + + return NULL; +} + +/* UNUSED */ +#if 0 +static short winding(const float v1[3], const float v2[3], const float v3[3]) +/* is v3 to the right of (v1 - v2) ? With exception: v3 == v1 || v3 == v2 */ +{ + double inp; + + //inp = (v2[cox] - v1[cox]) * (v1[coy] - v3[coy]) + (v1[coy] - v2[coy]) * (v1[cox] - v3[cox]); + inp = (v2[0] - v1[0]) * (v1[1] - v3[1]) + (v1[1] - v2[1]) * (v1[0] - v3[0]); + + if (inp < 0.0) { + return 0; + } + else if (inp == 0) { + if (v1[0] == v3[0] && v1[1] == v3[1]) return 0; + if (v2[0] == v3[0] && v2[1] == v3[1]) return 0; + } + return 1; +} +#endif -- cgit v1.2.3