[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [56079] trunk/blender/source/blender: move editmesh_bvh.c into blenkernel.
Campbell Barton
ideasman42 at gmail.com
Tue Apr 16 07:23:43 CEST 2013
Revision: 56079
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=56079
Author: campbellbarton
Date: 2013-04-16 05:23:34 +0000 (Tue, 16 Apr 2013)
Log Message:
-----------
move editmesh_bvh.c into blenkernel.
Modified Paths:
--------------
trunk/blender/source/blender/blenkernel/CMakeLists.txt
trunk/blender/source/blender/editors/include/ED_mesh.h
trunk/blender/source/blender/editors/mesh/CMakeLists.txt
trunk/blender/source/blender/editors/mesh/editmesh_knife.c
trunk/blender/source/blender/editors/mesh/editmesh_utils.c
trunk/blender/source/blender/editors/transform/transform.c
Added Paths:
-----------
trunk/blender/source/blender/blenkernel/BKE_editmesh_bvh.h
trunk/blender/source/blender/blenkernel/intern/editmesh_bvh.c
Removed Paths:
-------------
trunk/blender/source/blender/editors/mesh/editmesh_bvh.c
trunk/blender/source/blender/editors/mesh/editmesh_bvh.h
Copied: trunk/blender/source/blender/blenkernel/BKE_editmesh_bvh.h (from rev 56077, trunk/blender/source/blender/editors/mesh/editmesh_bvh.h)
===================================================================
--- trunk/blender/source/blender/blenkernel/BKE_editmesh_bvh.h (rev 0)
+++ trunk/blender/source/blender/blenkernel/BKE_editmesh_bvh.h 2013-04-16 05:23:34 UTC (rev 56079)
@@ -0,0 +1,65 @@
+/*
+ * ***** 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) 2001-2002 by NaN Holding BV.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): none yet.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file BKE_editmesh_bvh.h
+ * \ingroup bke
+ */
+
+#ifndef __BKE_EDITMESH_BVH_H__
+#define __BKE_EDITMESH_BVH_H__
+
+struct BMEditMesh;
+struct BMFace;
+struct BMEdge;
+struct BMVert;
+struct RegionView3D;
+struct BMBVHTree;
+struct BVHTree;
+struct Scene;
+struct Object;
+
+typedef struct BMBVHTree BMBVHTree;
+
+BMBVHTree *BMBVH_NewBVH(struct BMEditMesh *em, int flag, struct Scene *scene);
+void BMBVH_FreeBVH(BMBVHTree *tree);
+struct BVHTree *BMBVH_BVHTree(BMBVHTree *tree);
+
+struct BMFace *BMBVH_RayCast(BMBVHTree *tree, const float co[3], const float dir[3],
+ float r_hitout[3], float r_cagehit[3]);
+
+/*find a vert closest to co in a sphere of radius maxdist*/
+struct BMVert *BMBVH_FindClosestVert(BMBVHTree *tree, const float co[3], const float maxdist);
+
+/* BMBVH_NewBVH flag parameter */
+enum {
+ BMBVH_USE_CAGE = 1, /* project geometry onto modifier cage */
+ BMBVH_RETURN_ORIG = 2, /* use with BMBVH_USE_CAGE, returns hits in relation to original geometry */
+ BMBVH_RESPECT_SELECT = 4, /* restrict to hidden geometry (overrides BMBVH_RESPECT_HIDDEN) */
+ BMBVH_RESPECT_HIDDEN = 8 /* omit hidden geometry */
+};
+
+#endif /* __BKE_EDITMESH_BVH_H__ */
Modified: trunk/blender/source/blender/blenkernel/CMakeLists.txt
===================================================================
--- trunk/blender/source/blender/blenkernel/CMakeLists.txt 2013-04-16 03:27:51 UTC (rev 56078)
+++ trunk/blender/source/blender/blenkernel/CMakeLists.txt 2013-04-16 05:23:34 UTC (rev 56079)
@@ -84,6 +84,7 @@
intern/displist.c
intern/dynamicpaint.c
intern/editderivedmesh.c
+ intern/editmesh_bvh.c
intern/effect.c
intern/fcurve.c
intern/fluidsim.c
@@ -237,6 +238,7 @@
BKE_subsurf.h
BKE_suggestions.h
BKE_editmesh.h
+ BKE_editmesh_bvh.h
BKE_text.h
BKE_texture.h
BKE_tracking.h
Copied: trunk/blender/source/blender/blenkernel/intern/editmesh_bvh.c (from rev 56077, trunk/blender/source/blender/editors/mesh/editmesh_bvh.c)
===================================================================
--- trunk/blender/source/blender/blenkernel/intern/editmesh_bvh.c (rev 0)
+++ trunk/blender/source/blender/blenkernel/intern/editmesh_bvh.c 2013-04-16 05:23:34 UTC (rev 56079)
@@ -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;
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list