[Bf-blender-cvs] [cbbd1782e62] soc-2021-knife-tools: Knife: Custom Knife BVH for multiple BMesh
Cian Jinks
noreply at git.blender.org
Tue Aug 10 14:18:09 CEST 2021
Commit: cbbd1782e626e7738e4f27a2ce3f3fb5672da6b6
Author: Cian Jinks
Date: Tue Aug 10 13:11:05 2021 +0100
Branches: soc-2021-knife-tools
https://developer.blender.org/rBcbbd1782e626e7738e4f27a2ce3f3fb5672da6b6
Knife: Custom Knife BVH for multiple BMesh
Adds a custom Knife BVH which works with multiple BMesh's to replace the old BMBVH.
Currently, the new BVH is used in a functionally equivalent way to the old BMBVH but avoids re-allocating BVH's in multi-object edit mode.
This makes the current code slightly more complex, but will be incredibly useful when converting the knife tool code from object to world space, something that will need to be done to implement a better multi-object edit mode and further improvements to the tool.
===================================================================
M source/blender/editors/mesh/editmesh_knife.c
===================================================================
diff --git a/source/blender/editors/mesh/editmesh_knife.c b/source/blender/editors/mesh/editmesh_knife.c
index 6d89063491f..37188af714b 100644
--- a/source/blender/editors/mesh/editmesh_knife.c
+++ b/source/blender/editors/mesh/editmesh_knife.c
@@ -189,6 +189,18 @@ typedef struct KnifeUndoFrame {
} KnifeUndoFrame;
+typedef struct KnifeBVH {
+ BVHTree *tree; /* Knife Custom BVH Tree. */
+ BMLoop *(*looptris)[3]; /* Used by #knife_bvh_raycast_cb to store the intersecting looptri. */
+ float uv[2]; /* Used by #knife_bvh_raycast_cb to store the intersecting uv. */
+ uint base_index;
+
+ /* Use #bm_ray_cast_cb_elem_not_in_face_check. */
+ bool (*filter_cb)(BMFace *f, void *userdata);
+ void *filter_data;
+
+} KnifeBVH;
+
/* struct for properties used while drawing */
typedef struct KnifeTool_OpData {
ARegion *region; /* Region that knifetool was activated in. */
@@ -204,6 +216,7 @@ typedef struct KnifeTool_OpData {
/* Used for swapping current object when in multi-object edit mode. */
Base **bases;
uint bases_len;
+ int base_index;
MemArena *arena;
@@ -221,7 +234,8 @@ typedef struct KnifeTool_OpData {
GHash *kedgefacemap;
GHash *facetrimap;
- BMBVHTree *bmbvh;
+ KnifeBVH bvh;
+ const float (**cagecos)[3];
BLI_mempool *kverts;
BLI_mempool *kedges;
@@ -292,8 +306,6 @@ typedef struct KnifeTool_OpData {
bool angle_snapping;
float angle;
- const float (*cagecos)[3];
-
short constrain_axis;
short constrain_axis_mode;
bool axis_constrained;
@@ -1125,6 +1137,345 @@ static void knife_update_header(bContext *C, wmOperator *op, KnifeTool_OpData *k
/** \} */
+/* -------------------------------------------------------------------- */
+/** \name Knife BVH Utils
+ * \{ */
+
+static bool knife_bm_face_is_select(BMFace *f)
+{
+ return (BM_elem_flag_test(f, BM_ELEM_SELECT) != 0);
+}
+
+static bool knife_bm_face_is_not_hidden(BMFace *f)
+{
+ return (BM_elem_flag_test(f, BM_ELEM_HIDDEN) == 0);
+}
+
+static void knife_bvh_init(KnifeTool_OpData *kcd)
+{
+ Object *ob;
+ BMEditMesh *em;
+
+ /* Test Function. */
+ bool (*test_fn)(BMFace *);
+ if ((kcd->only_select && kcd->cut_through)) {
+ test_fn = knife_bm_face_is_select;
+ }
+ else {
+ test_fn = knife_bm_face_is_not_hidden;
+ }
+
+ /* Construct BVH Tree. */
+ float cos[3][3];
+ const float epsilon = FLT_EPSILON * 2.0f;
+ int tottri = 0;
+ int ob_tottri = 0;
+ BMLoop *(*looptris)[3];
+ BMFace *f_test = NULL, *f_test_prev = NULL;
+ bool test_fn_ret = false;
+
+ /* Calculate tottri. */
+ for (int b = 0; b < kcd->bases_len; b++) {
+ ob_tottri = 0;
+ ob = kcd->bases[b]->object;
+ em = BKE_editmesh_from_object(ob);
+
+ for (int i = 0; i < em->tottri; i++) {
+ f_test = em->looptris[i][0]->f;
+ if (f_test != f_test_prev) {
+ test_fn_ret = test_fn(f_test);
+ f_test_prev = f_test;
+ }
+
+ if (test_fn_ret) {
+ ob_tottri++;
+ }
+ }
+
+ tottri += ob_tottri;
+ }
+
+ kcd->bvh.tree = BLI_bvhtree_new(tottri, epsilon, 8, 8);
+
+ f_test_prev = NULL;
+ test_fn_ret = false;
+
+ /* Add tri's for each object.
+ * TODO:
+ * test_fn can leave large gaps between bvh tree indices.
+ * Compacting bvh tree indices may be possible.
+ * Don't forget to update #knife_bvh_intersect_plane!
+ */
+ tottri = 0;
+ for (int b = 0; b < kcd->bases_len; b++) {
+ ob = kcd->bases[b]->object;
+ em = BKE_editmesh_from_object(ob);
+ looptris = em->looptris;
+
+ for (int i = 0; i < em->tottri; i++) {
+
+ f_test = looptris[i][0]->f;
+ if (f_test != f_test_prev) {
+ test_fn_ret = test_fn(f_test);
+ f_test_prev = f_test;
+ }
+
+ if (!test_fn_ret) {
+ continue;
+ }
+
+ copy_v3_v3(cos[0], kcd->cagecos[b][BM_elem_index_get(looptris[i][0]->v)]);
+ copy_v3_v3(cos[1], kcd->cagecos[b][BM_elem_index_get(looptris[i][1]->v)]);
+ copy_v3_v3(cos[2], kcd->cagecos[b][BM_elem_index_get(looptris[i][2]->v)]);
+
+ /* Convert to world-space. */
+ mul_m4_v3(ob->obmat, cos[0]);
+ mul_m4_v3(ob->obmat, cos[1]);
+ mul_m4_v3(ob->obmat, cos[2]);
+
+ BLI_bvhtree_insert(kcd->bvh.tree, i + tottri, (float *)cos, 3);
+ }
+
+ tottri += em->tottri;
+ }
+
+ BLI_bvhtree_balance(kcd->bvh.tree);
+}
+
+/* Wrapper for #BLI_bvhtree_free. */
+static void knife_bvh_free(KnifeTool_OpData *kcd)
+{
+ if (kcd->bvh.tree) {
+ BLI_bvhtree_free(kcd->bvh.tree);
+ kcd->bvh.tree = NULL;
+ }
+}
+
+static void knife_bvh_raycast_cb(void *userdata,
+ int index,
+ const BVHTreeRay *ray,
+ BVHTreeRayHit *hit)
+{
+ KnifeTool_OpData *kcd = userdata;
+ BMLoop **ltri;
+ Object *ob;
+ BMEditMesh *em;
+
+ float dist, uv[2];
+ bool isect;
+ int tottri;
+ float tri_cos[3][3];
+ float ob_imat[4][4];
+
+ if (index != -1) {
+ tottri = 0;
+ int b = 0;
+ for (; b < kcd->bases_len; b++) {
+ index -= tottri;
+ ob = kcd->bases[b]->object;
+ em = BKE_editmesh_from_object(ob);
+ tottri = em->tottri;
+ if (index < tottri) {
+ ltri = em->looptris[index];
+ break;
+ }
+ }
+
+ if (kcd->bvh.filter_cb) {
+ if (!kcd->bvh.filter_cb(ltri[0]->f, kcd->bvh.filter_data)) {
+ return;
+ }
+ }
+
+ copy_v3_v3(tri_cos[0], kcd->cagecos[b][BM_elem_index_get(ltri[0]->v)]);
+ copy_v3_v3(tri_cos[1], kcd->cagecos[b][BM_elem_index_get(ltri[1]->v)]);
+ copy_v3_v3(tri_cos[2], kcd->cagecos[b][BM_elem_index_get(ltri[2]->v)]);
+ mul_m4_v3(ob->obmat, tri_cos[0]);
+ mul_m4_v3(ob->obmat, tri_cos[1]);
+ mul_m4_v3(ob->obmat, tri_cos[2]);
+
+ isect =
+ (ray->radius > 0.0f ?
+ isect_ray_tri_epsilon_v3(ray->origin,
+ ray->direction,
+ tri_cos[0],
+ tri_cos[1],
+ tri_cos[2],
+ &dist,
+ uv,
+ ray->radius) :
+#ifdef USE_KDOPBVH_WATERTIGHT
+ isect_ray_tri_watertight_v3(
+ ray->origin, ray->isect_precalc, tri_cos[0], tri_cos[1], tri_cos[2], &dist, uv));
+#else
+ isect_ray_tri_v3(
+ ray->origin, ray->direction, tri_cos[0], tri_cos[1], tri_cos[2], &dist, uv));
+#endif
+
+ if (isect && dist < hit->dist) {
+ hit->dist = dist;
+ hit->index = index;
+
+ copy_v3_v3(hit->no, ltri[0]->f->no);
+
+ madd_v3_v3v3fl(hit->co, ray->origin, ray->direction, dist);
+
+ /* TODO: Remove when converting tool code to world space. */
+ invert_m4_m4_safe_ortho(ob_imat, ob->obmat);
+ mul_m4_v3(ob_imat, hit->co);
+
+ kcd->bvh.looptris = em->looptris;
+ copy_v2_v2(kcd->bvh.uv, uv);
+ kcd->bvh.base_index = b;
+ }
+ }
+}
+
+/* `co` is expected to be in world space. */
+static BMFace *knife_bvh_raycast(KnifeTool_OpData *kcd,
+ const float co[3],
+ const float dir[3],
+ const float radius,
+ float *r_dist,
+ float r_hitout[3],
+ float r_cagehit[3],
+ bool same_object, /* Fail intersection if object != kcd->ob. */
+ uint *r_base_index)
+{
+ BMFace *face;
+ BMLoop **ltri;
+ BVHTreeRayHit hit;
+ const float dist = r_dist ? *r_dist : FLT_MAX;
+ hit.dist = dist;
+ hit.index = -1;
+
+ int index = BLI_bvhtree_ray_cast(
+ kcd->bvh.tree, co, dir, radius, &hit, knife_bvh_raycast_cb, kcd);
+
+ // Handle Hit
+ if (hit.index != -1 && hit.dist != dist) {
+ if (same_object) {
+ if (kcd->base_index != kcd->bvh.base_index) {
+ return NULL;
+ }
+ }
+
+ face = kcd->bvh.looptris[hit.index][0]->f;
+
+ if (r_hitout) {
+ ltri = kcd->bvh.looptris[hit.index];
+ interp_v3_v3v3v3_uv(r_hitout, ltri[0]->v->co, ltri[1]->v->co, ltri[2]->v->co, kcd->bvh.uv);
+
+ if (r_cagehit) {
+ copy_v3_v3(r_cagehit, hit.co);
+ }
+ }
+
+ if (r_dist) {
+ *r_dist = hit.dist;
+ }
+
+ if (r_base_index) {
+ *r_base_index = kcd->bvh.base_index;
+ }
+
+ return face;
+ }
+ return NULL;
+}
+
+/* `co` is expected to be in world space. */
+static BMFace *knife_bvh_raycast_filter(
+ KnifeTool_OpData *kcd,
+ const float co[3],
+ const float dir[3],
+ const float radius,
+ float *r_dist,
+ float r_hitout[3],
+ float r_cagehit[3],
+ bool same_object, /* Fail intersection if object != kcd->ob. */
+ uint *r_base_index,
+ bool (*filter_cb)(BMFace *f, void *userdata),
+ void *filter_userdata)
+{
+ kcd->bvh.filter_cb = filter_cb;
+ kcd->bvh.filter_data = filter_userdata;
+
+ BMFace *face;
+ BMLoop **ltri;
+ BVHTreeRayHit hit;
+ const float dist = r_dist ? *r_dist : FLT_MAX;
+ hit.dist = dist;
+ hit.index = -1;
+
+ int index = BLI_bvhtree_ray_cast(
+ kcd->bvh.tree, co, dir, radius, &hit, knife_bvh_raycast_cb, kcd);
+
+ kcd->bvh.filter_cb = NULL;
+ kcd->bvh.filter_data = NULL;
+
+ // Handle Hit
+ if (hit.index != -1 && hit.dist != dist) {
+ if (same_object) {
+ if (kcd->base_index != kcd->bvh.base_index) {
+ return NULL;
+ }
+ }
+
+ face = kcd->bvh.looptris[hit.index][0]->f;
+
+ if (r_hitout) {
+ ltri = kcd->bvh.looptris[hit.index];
+ interp_v3_v3v3v3_uv(r_hitout, ltri[0]->v->co, ltri[1]->v->co, ltri[2]->v->co, kcd->bvh.uv);
+
+ if (r_cagehit) {
+ copy_v3_v3(r_cagehit, hit.co);
+ }
+ }
+
+ if (r_dist) {
+ *r_dist = hit.dist;
+ }
+
+ if (r_base_index) {
+ *r_base_index = kcd->bvh.base_index;
+ }
+
+ return face;
+ }
+ return NULL;
+}
+
+/* TODO: Currently filters to only intersections with kcd->ob.
+ * Change when converting tool code to world space. */
+static int *knife_bvh_intersect_plane(KnifeTool_OpData *kcd, float *plane, uint *r_intersect_tot)
+{
+ Object *ob;
+ BMEditMesh *em;
+ int tottri = 0;
+
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list