[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [59665] trunk/blender/source/blender: Some knife fixes.
Howard Trickey
howard.trickey at gmail.com
Fri Aug 30 18:34:44 CEST 2013
Revision: 59665
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=59665
Author: howardt
Date: 2013-08-30 16:34:44 +0000 (Fri, 30 Aug 2013)
Log Message:
-----------
Some knife fixes. Avoids duplicating verts; better handling of cut-through ortho.
Now cut lines detect vertices that they pass (almost) exactly over
and snap to them, to avoid making verts vert close to other ones.
Added radius arg to BKE_bmbvh_ray_cast so that can detect an obscuring
face when the ray might otherwise go exactly between two triangles.
Needed an isect_line_tri_epsilon function for similar reason.
Fixes last part of bug #35002. Other knife bugs still present but
getting this commit in now before continuing bug fixing.
Modified Paths:
--------------
trunk/blender/source/blender/blenkernel/BKE_editmesh_bvh.h
trunk/blender/source/blender/blenkernel/intern/editderivedmesh.c
trunk/blender/source/blender/blenkernel/intern/editmesh_bvh.c
trunk/blender/source/blender/blenlib/BLI_math_geom.h
trunk/blender/source/blender/blenlib/intern/math_geom.c
trunk/blender/source/blender/editors/mesh/editmesh_knife.c
trunk/blender/source/blender/editors/mesh/editmesh_utils.c
Modified: trunk/blender/source/blender/blenkernel/BKE_editmesh_bvh.h
===================================================================
--- trunk/blender/source/blender/blenkernel/BKE_editmesh_bvh.h 2013-08-30 16:25:56 UTC (rev 59664)
+++ trunk/blender/source/blender/blenkernel/BKE_editmesh_bvh.h 2013-08-30 16:34:44 UTC (rev 59665)
@@ -44,7 +44,7 @@
BMBVHTree *BKE_bmbvh_new(struct BMEditMesh *em, int flag, const float (*cos_cage)[3], const bool cos_cage_free);
void BKE_bmbvh_free(BMBVHTree *tree);
struct BVHTree *BKE_bmbvh_tree_get(BMBVHTree *tree);
-struct BMFace *BKE_bmbvh_ray_cast(BMBVHTree *tree, const float co[3], const float dir[3],
+struct BMFace *BKE_bmbvh_ray_cast(BMBVHTree *tree, const float co[3], const float dir[3], const float radius,
float *r_dist, float r_hitout[3], float r_cagehit[3]);
/* find a face intersecting a segment (but not apart of the segment) */
struct BMFace *BKE_bmbvh_find_face_segment(BMBVHTree *tree, const float co_a[3], const float co_b[3],
Modified: trunk/blender/source/blender/blenkernel/intern/editderivedmesh.c
===================================================================
--- trunk/blender/source/blender/blenkernel/intern/editderivedmesh.c 2013-08-30 16:25:56 UTC (rev 59664)
+++ trunk/blender/source/blender/blenkernel/intern/editderivedmesh.c 2013-08-30 16:34:44 UTC (rev 59665)
@@ -1872,7 +1872,7 @@
normal_tri_v3(ray_no, cos[2], cos[1], cos[0]);
#define FACE_RAY_TEST_ANGLE \
- f_hit = BKE_bmbvh_ray_cast(bmtree, ray_co, ray_no, \
+ f_hit = BKE_bmbvh_ray_cast(bmtree, ray_co, ray_no, 0.0f, \
&dist, NULL, NULL); \
if (f_hit && dist < face_dists[index]) { \
float angle_fac = fabsf(dot_v3v3(ltri[0]->f->no, f_hit->no)); \
Modified: trunk/blender/source/blender/blenkernel/intern/editmesh_bvh.c
===================================================================
--- trunk/blender/source/blender/blenkernel/intern/editmesh_bvh.c 2013-08-30 16:25:56 UTC (rev 59664)
+++ trunk/blender/source/blender/blenkernel/intern/editmesh_bvh.c 2013-08-30 16:34:44 UTC (rev 59665)
@@ -193,11 +193,14 @@
const BMLoop **ltri = bmcb_data->looptris[index];
float dist, uv[2];
const float *tri_cos[3];
+ bool isect;
bmbvh_tri_from_face(tri_cos, ltri, bmcb_data->cos_cage);
- if (isect_ray_tri_v3(ray->origin, ray->direction, tri_cos[0], tri_cos[1], tri_cos[2], &dist, uv) &&
- (dist < hit->dist))
+ 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) :
+ isect_ray_tri_v3(ray->origin, ray->direction, tri_cos[0], tri_cos[1], tri_cos[2], &dist, uv);
+ if (isect && dist < hit->dist)
{
hit->dist = dist;
hit->index = index;
@@ -213,7 +216,7 @@
}
}
-BMFace *BKE_bmbvh_ray_cast(BMBVHTree *bmtree, const float co[3], const float dir[3],
+BMFace *BKE_bmbvh_ray_cast(BMBVHTree *bmtree, const float co[3], const float dir[3], const float radius,
float *r_dist, float r_hitout[3], float r_cagehit[3])
{
BVHTreeRayHit hit;
@@ -229,7 +232,7 @@
bmcb_data.looptris = (const BMLoop *(*)[3])bmtree->em->looptris;
bmcb_data.cos_cage = (const float (*)[3])bmtree->cos_cage;
- BLI_bvhtree_ray_cast(bmtree->tree, co, dir, 0.0f, &hit, bmbvh_ray_cast_cb, &bmcb_data);
+ BLI_bvhtree_ray_cast(bmtree->tree, co, dir, radius, &hit, bmbvh_ray_cast_cb, &bmcb_data);
if (hit.index != -1 && hit.dist != dist) {
if (r_hitout) {
if (bmtree->flag & BMBVH_RETURN_ORIG) {
Modified: trunk/blender/source/blender/blenlib/BLI_math_geom.h
===================================================================
--- trunk/blender/source/blender/blenlib/BLI_math_geom.h 2013-08-30 16:25:56 UTC (rev 59664)
+++ trunk/blender/source/blender/blenlib/BLI_math_geom.h 2013-08-30 16:34:44 UTC (rev 59665)
@@ -139,6 +139,9 @@
/* line/ray triangle */
bool isect_line_tri_v3(const float p1[3], const float p2[3],
const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float r_uv[2]);
+bool isect_line_tri_epsilon_v3(const float p1[3], const float p2[3],
+ const float v0[3], const float v1[3], const float v2[3],
+ float *r_lambda, float r_uv[2], const float epsilon);
bool isect_ray_tri_v3(const float p1[3], const float d[3],
const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float r_uv[2]);
bool isect_ray_tri_threshold_v3(const float p1[3], const float d[3],
Modified: trunk/blender/source/blender/blenlib/intern/math_geom.c
===================================================================
--- trunk/blender/source/blender/blenlib/intern/math_geom.c 2013-08-30 16:25:56 UTC (rev 59664)
+++ trunk/blender/source/blender/blenlib/intern/math_geom.c 2013-08-30 16:34:44 UTC (rev 59665)
@@ -894,6 +894,45 @@
return 1;
}
+/* like isect_line_tri_v3, but allows epsilon tolerance around triangle */
+bool isect_line_tri_epsilon_v3(const float p1[3], const float p2[3],
+ const float v0[3], const float v1[3], const float v2[3],
+ float *r_lambda, float r_uv[2], const float epsilon)
+{
+
+ float p[3], s[3], d[3], e1[3], e2[3], q[3];
+ float a, f, u, v;
+
+ sub_v3_v3v3(e1, v1, v0);
+ sub_v3_v3v3(e2, v2, v0);
+ sub_v3_v3v3(d, p2, p1);
+
+ cross_v3_v3v3(p, d, e2);
+ a = dot_v3v3(e1, p);
+ if ((a > -0.000001f) && (a < 0.000001f)) return 0;
+ f = 1.0f / a;
+
+ sub_v3_v3v3(s, p1, v0);
+
+ u = f * dot_v3v3(s, p);
+ if ((u < -epsilon) || (u > 1.0f + epsilon)) return 0;
+
+ cross_v3_v3v3(q, s, e1);
+
+ v = f * dot_v3v3(d, q);
+ if ((v < -epsilon) || ((u + v) > 1.0f + epsilon)) return 0;
+
+ *r_lambda = f * dot_v3v3(e2, q);
+ if ((*r_lambda < 0.0f) || (*r_lambda > 1.0f)) return 0;
+
+ if (r_uv) {
+ r_uv[0] = u;
+ r_uv[1] = v;
+ }
+
+ return 1;
+}
+
/* moved from effect.c
* test if the ray starting at p1 going in d direction intersects the triangle v0..v2
* return non zero if it does
Modified: trunk/blender/source/blender/editors/mesh/editmesh_knife.c
===================================================================
--- trunk/blender/source/blender/editors/mesh/editmesh_knife.c 2013-08-30 16:25:56 UTC (rev 59664)
+++ trunk/blender/source/blender/editors/mesh/editmesh_knife.c 2013-08-30 16:34:44 UTC (rev 59665)
@@ -499,10 +499,11 @@
{
KnifeEdge *kfe = new_knife_edge(kcd), *kfe2 = NULL, *kfe3 = NULL;
- if (kcd->prev.vert && kcd->prev.vert == kcd->curr.vert)
+ if ((kcd->prev.vert && kcd->prev.vert == kcd->curr.vert) ||
+ (kcd->prev.edge && kcd->prev.edge == kcd->curr.edge)) {
+ kcd->prev = kcd->curr;
return;
- if (kcd->prev.edge && kcd->prev.edge == kcd->curr.edge)
- return;
+ }
kfe->draw = true;
@@ -573,10 +574,17 @@
if (lh1->l < lh2->l) return -1;
else if (lh1->l > lh2->l) return 1;
+ else if (lh1->v && lh2->v) {
+ /* want like verts to sort together; just compare pointers */
+ if (lh1->v < lh2->v) return -1;
+ else if (lh1->v > lh2->v) return 1;
+ else return 0;
+ }
else return 0;
}
/* If there's a linehit connected (same face) as testi in range [firsti, lasti], return the first such, else -1.
+ * It also counts as connected if both linehits are snapped to the same vertex.
* If testi is out of range, look for connection to f instead, if f is non-NULL */
static int find_connected_linehit(KnifeTool_OpData *kcd, int testi, BMFace *f, int firsti, int lasti)
{
@@ -586,9 +594,10 @@
if (testi >= 0 && testi < kcd->totlinehit) {
if (knife_find_common_face(&kcd->linehits[testi].kfe->faces,
&kcd->linehits[i].kfe->faces))
- {
return i;
- }
+ else if (kcd->linehits[testi].v &&
+ kcd->linehits[testi].v == kcd->linehits[i].v)
+ return i;
}
else if (f) {
if (find_ref(&kcd->linehits[i].kfe->faces, f))
@@ -598,13 +607,38 @@
return -1;
}
-/* Sort in order of distance along cut line, but take care when distances are equal */
-static void knife_sort_linehits(KnifeTool_OpData *kcd)
+/* Sort in order of distance along cut line.
+ * Remove any successive linehits that are snapped to the same vertex.
+ * If joinfaces, treat hits at same distance as follows: try to find
+ * ordering so that preceding and succeeding hits will share a face.
+ */
+static void knife_sort_linehits(KnifeTool_OpData *kcd, bool joinfaces)
{
int i, j, k, nexti, nsame;
qsort(kcd->linehits, kcd->totlinehit, sizeof(BMEdgeHit), verge_linehit);
+ /* Remove duplicated linehits snapped to same vertex */
+ i = j = 0; /* loop copies from j to i */
+ while (j < kcd->totlinehit) {
+ nsame = 0;
+ if (kcd->linehits[j].v) {
+ for (k = j + 1; k < kcd->totlinehit; k++) {
+ if (kcd->linehits[k].v != kcd->linehits[j].v)
+ break;
+ nsame++;
+ }
+ }
+ if (i != j)
+ kcd->linehits[i] = kcd->linehits[j];
+ i++;
+ j += 1 + nsame;
+ }
+ kcd->totlinehit = i;
+
+ if (!joinfaces)
+ return;
+
/* for ranges of equal "l", swap if neccesary to make predecessor and
* successor faces connected to the linehits at either end of the range */
for (i = 0; i < kcd->totlinehit - 1; i = nexti) {
@@ -653,6 +687,7 @@
knife_edge_append_face(kcd, kfenew, f);
}
+#if 0
static void knife_get_vert_faces(KnifeTool_OpData *kcd, KnifeVert *kfv, BMFace *facef, ListBase *lst)
{
BMIter bmiter;
@@ -685,20 +720,32 @@
}
}
}
+#endif
+static void copy_hit_from_posdata(BMEdgeHit *lh, KnifePosData *pos, float lambda) {
+ lh->kfe = pos->edge;
+ lh->v = pos->vert;
+ lh->f = pos->bmface;
+ copy_v3_v3(lh->hit, pos->co);
+ copy_v3_v3(lh->cagehit, pos->cage);
+ copy_v3_v3(lh->realhit, pos->co);
+ lh->l = lambda;
+ /* perc and schit not used by callers of this function */
+}
+
/* BMESH_TODO: add more functionality to cut-through:
* - cutting "in face" (e.g., holes) should cut in all faces, not just visible one
* - perhaps improve O(n^2) algorithm used here */
static void knife_cut_through(KnifeTool_OpData *kcd)
{
- BMEdgeHit *lh, *lh2;
+ BMEdgeHit *lh, *lh2, *linehits;
BMFace *f;
- KnifeEdge *kfe, *kfe2, *kfe3;
- KnifeVert *v1, *v2, *firstv = NULL, *lastv = NULL;
- ListBase firstfaces = {NULL, NULL}, lastfaces = {NULL, NULL};
- Ref *r, *r2;
+ KnifeEdge *kfe, *kfe2;
+ KnifeVert *v1, *v2, *lastv;
+ ListBase *faces1, *faces2;
KnifeEdge **splitkfe;
- int i, j;
+ bool needprev, needcurr;
+ int i, j, n;
if (!kcd->totlinehit) {
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list