[Bf-blender-cvs] [ca5e1615a10] master: BMesh: New tool `BM_mesh_intersect_edges`
mano-wii
noreply at git.blender.org
Thu Sep 12 18:33:55 CEST 2019
Commit: ca5e1615a10fd8c31bb0367332cd5f3a1e8bd9aa
Author: mano-wii
Date: Thu Sep 12 13:28:53 2019 -0300
Branches: master
https://developer.blender.org/rBca5e1615a10fd8c31bb0367332cd5f3a1e8bd9aa
BMesh: New tool `BM_mesh_intersect_edges`
Along with the new utility `BM_vert_weld_linked_wire_edges_into_linked_faces`
===================================================================
M source/blender/blenlib/BLI_math_geom.h
M source/blender/blenlib/intern/math_geom.c
M source/blender/bmesh/CMakeLists.txt
A source/blender/bmesh/tools/bmesh_intersect_edges.c
A source/blender/bmesh/tools/bmesh_intersect_edges.h
===================================================================
diff --git a/source/blender/blenlib/BLI_math_geom.h b/source/blender/blenlib/BLI_math_geom.h
index caecc0aebc2..87517ebe060 100644
--- a/source/blender/blenlib/BLI_math_geom.h
+++ b/source/blender/blenlib/BLI_math_geom.h
@@ -311,7 +311,13 @@ bool isect_line_line_strict_v3(const float v1[3],
const float v4[3],
float vi[3],
float *r_lambda);
-
+bool isect_ray_ray_epsilon_v3(const float ray_origin_a[3],
+ const float ray_direction_a[3],
+ const float ray_origin_b[3],
+ const float ray_direction_b[3],
+ const float epsilon,
+ float *r_lambda_a,
+ float *r_lambda_b);
bool isect_ray_ray_v3(const float ray_origin_a[3],
const float ray_direction_a[3],
const float ray_origin_b[3],
diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c
index a81dc018ed0..6d8193e7675 100644
--- a/source/blender/blenlib/intern/math_geom.c
+++ b/source/blender/blenlib/intern/math_geom.c
@@ -3057,19 +3057,21 @@ bool isect_line_line_strict_v3(const float v1[3],
*
* \note Neither directions need to be normalized.
*/
-bool isect_ray_ray_v3(const float ray_origin_a[3],
- const float ray_direction_a[3],
- const float ray_origin_b[3],
- const float ray_direction_b[3],
- float *r_lambda_a,
- float *r_lambda_b)
+bool isect_ray_ray_epsilon_v3(const float ray_origin_a[3],
+ const float ray_direction_a[3],
+ const float ray_origin_b[3],
+ const float ray_direction_b[3],
+ const float epsilon,
+ float *r_lambda_a,
+ float *r_lambda_b)
{
BLI_assert(r_lambda_a || r_lambda_b);
float n[3];
cross_v3_v3v3(n, ray_direction_b, ray_direction_a);
const float nlen = len_squared_v3(n);
- if (UNLIKELY(nlen == 0.0f)) {
+ /* `nlen` is the the square of the area formed by the two vectors. */
+ if (UNLIKELY(nlen < epsilon)) {
/* The lines are parallel. */
return false;
}
@@ -3091,6 +3093,22 @@ bool isect_ray_ray_v3(const float ray_origin_a[3],
return true;
}
+bool isect_ray_ray_v3(const float ray_origin_a[3],
+ const float ray_direction_a[3],
+ const float ray_origin_b[3],
+ const float ray_direction_b[3],
+ float *r_lambda_a,
+ float *r_lambda_b)
+{
+ return isect_ray_ray_epsilon_v3(ray_origin_a,
+ ray_direction_a,
+ ray_origin_b,
+ ray_direction_b,
+ FLT_MIN,
+ r_lambda_a,
+ r_lambda_b);
+}
+
bool isect_aabb_aabb_v3(const float min1[3],
const float max1[3],
const float min2[3],
diff --git a/source/blender/bmesh/CMakeLists.txt b/source/blender/bmesh/CMakeLists.txt
index f5095ca2b5f..599871a505a 100644
--- a/source/blender/bmesh/CMakeLists.txt
+++ b/source/blender/bmesh/CMakeLists.txt
@@ -143,6 +143,8 @@ set(SRC
tools/bmesh_edgesplit.h
tools/bmesh_intersect.c
tools/bmesh_intersect.h
+ tools/bmesh_intersect_edges.c
+ tools/bmesh_intersect_edges.h
tools/bmesh_path.c
tools/bmesh_path.h
tools/bmesh_path_region.c
diff --git a/source/blender/bmesh/tools/bmesh_intersect_edges.c b/source/blender/bmesh/tools/bmesh_intersect_edges.c
new file mode 100644
index 00000000000..04c6968bfa0
--- /dev/null
+++ b/source/blender/bmesh/tools/bmesh_intersect_edges.c
@@ -0,0 +1,909 @@
+/*
+ * 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) 2019 Blender Foundation.
+ * All rights reserved.
+ */
+
+/** \file
+ * \ingroup bmesh
+ */
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_math.h"
+#include "BLI_sort.h"
+#include "BLI_stack.h"
+
+#include "BKE_bvhutils.h"
+
+#include "bmesh.h"
+
+#include "bmesh_intersect_edges.h" /* own include */
+
+#define KDOP_AXIS_LEN 14
+
+/* -------------------------------------------------------------------- */
+/** \name Weld Linked Wire Edges into Linked Faces
+ *
+ * Used with the merge vertices option.
+ * \{ */
+
+/* Callbacks for `BM_vert_pair_shared_face_cb` */
+
+struct EDBMSplitBestFaceData {
+ BMEdge **edgenet;
+ int edgenet_len;
+
+ /**
+ * Track the range of vertices in edgenet along the faces normal,
+ * find the lowest since it's most likely to be most co-planar with the face.
+ */
+ float best_face_range_on_normal_axis;
+ BMFace *r_best_face;
+};
+
+static bool bm_vert_pair_share_best_splittable_face_cb(BMFace *f,
+ BMLoop *l_a,
+ BMLoop *l_b,
+ void *userdata)
+{
+ struct EDBMSplitBestFaceData *data = userdata;
+ float no[3];
+ copy_v3_v3(no, f->no);
+
+ float min = dot_v3v3(l_a->v->co, no);
+ float max = dot_v3v3(l_b->v->co, no);
+ if (min > max) {
+ SWAP(float, min, max);
+ }
+
+ BMVert *v_test = l_b->v;
+ BMEdge **e_iter = &data->edgenet[0];
+ int verts_len = data->edgenet_len - 1;
+ for (int i = verts_len; i--; e_iter++) {
+ v_test = BM_edge_other_vert(*e_iter, v_test);
+ if (!BM_face_point_inside_test(f, v_test->co)) {
+ return false;
+ }
+ float dot = dot_v3v3(v_test->co, no);
+ if (dot < min) {
+ min = dot;
+ }
+ if (dot > max) {
+ max = dot;
+ }
+ }
+
+ const float test_face_range_on_normal_axis = max - min;
+ if (test_face_range_on_normal_axis < data->best_face_range_on_normal_axis) {
+ data->best_face_range_on_normal_axis = test_face_range_on_normal_axis;
+ data->r_best_face = f;
+ }
+
+ return false;
+}
+
+/* find the best splittable face between the two vertices. */
+static bool bm_vert_pair_share_splittable_face_cb(BMFace *UNUSED(f),
+ BMLoop *l_a,
+ BMLoop *l_b,
+ void *userdata)
+{
+ float(*data)[3] = userdata;
+ float *v_a_co = data[0];
+ float *v_a_b_dir = data[1];
+
+ float lambda;
+ if (isect_ray_seg_v3(v_a_co, v_a_b_dir, l_a->prev->v->co, l_a->next->v->co, &lambda)) {
+ if (IN_RANGE(lambda, 0.0f, 1.0f)) {
+ return true;
+ }
+ else if (isect_ray_seg_v3(v_a_co, v_a_b_dir, l_b->prev->v->co, l_b->next->v->co, &lambda)) {
+ return IN_RANGE(lambda, 0.0f, 1.0f);
+ }
+ }
+ return false;
+}
+
+void BM_vert_weld_linked_wire_edges_into_linked_faces(
+ BMesh *bm, BMVert *v, const float epsilon, BMEdge **r_edgenet[], int *r_edgenet_alloc_len)
+{
+ BMEdge **edgenet = *r_edgenet;
+ int edgenet_alloc_len = *r_edgenet_alloc_len;
+
+ BMIter iter;
+ BMEdge *e;
+ BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
+ int edgenet_len = 0;
+ BMVert *v_other = v;
+ while (BM_edge_is_wire(e)) {
+ if (edgenet_alloc_len == edgenet_len) {
+ edgenet_alloc_len = (edgenet_alloc_len + 1) * 2;
+ edgenet = MEM_reallocN(edgenet, (edgenet_alloc_len) * sizeof(*edgenet));
+ }
+ edgenet[edgenet_len++] = e;
+ v_other = BM_edge_other_vert(e, v_other);
+ if (v_other == v) {
+ /* Endless loop. */
+ break;
+ }
+
+ BMEdge *e_next = BM_DISK_EDGE_NEXT(e, v_other);
+ if (e_next == e) {
+ /* Vert is wire_endpoint. */
+ edgenet_len = 0;
+ break;
+ }
+
+ BMEdge *e_test = e_next;
+ while ((e_test = BM_DISK_EDGE_NEXT(e_test, v_other)) != e) {
+ if (e_test->l) {
+ /* Vert is linked to a face. */
+ goto l_break;
+ }
+ }
+
+ e = e_next;
+ }
+
+ BMLoop *dummy;
+ BMFace *best_face;
+
+ l_break:
+ if (edgenet_len == 0) {
+ /* Nothing to do. */
+ continue;
+ }
+ if (edgenet_len == 1) {
+ float data[2][3];
+ copy_v3_v3(data[0], v_other->co);
+ sub_v3_v3v3(data[1], v->co, data[0]);
+ best_face = BM_vert_pair_shared_face_cb(
+ v_other, v, true, bm_vert_pair_share_splittable_face_cb, &data, &dummy, &dummy);
+ }
+ else {
+ struct EDBMSplitBestFaceData data = {
+ .edgenet = edgenet,
+ .edgenet_len = edgenet_len,
+ .best_face_range_on_normal_axis = FLT_MAX,
+ .r_best_face = NULL,
+ };
+ BM_vert_pair_shared_face_cb(
+ v_other, v, true, bm_vert_pair_share_best_splittable_face_cb, &data, &dummy, &dummy);
+
+ if (data.r_best_face) {
+ float no[3], min = FLT_MAX, max = -FLT_MAX;
+ copy_v3_v3(no, data.r_best_face->no);
+ BMVert *v_test;
+ BMIter f_iter;
+ BM_ITER_ELEM (v_test, &f_iter, data.r_best_face, BM_VERTS_OF_FACE) {
+ float dot = dot_v3v3(v_test->co, no);
+ if (dot < min) {
+ min = dot;
+ }
+ if (dot > max) {
+ max = dot;
+ }
+ }
+ float range = max - min + 2 * epsilon;
+ if (range < data.best_face_range_on_normal_axis) {
+ data.r_best_face = NULL;
+ }
+
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list