[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [61144] trunk/blender/source/blender/ editors/mesh/editmesh_knife.c: Rewrote a lot of knife tool.
Howard Trickey
howard.trickey at gmail.com
Tue Nov 5 17:24:00 CET 2013
Revision: 61144
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=61144
Author: howardt
Date: 2013-11-05 16:24:00 +0000 (Tue, 05 Nov 2013)
Log Message:
-----------
Rewrote a lot of knife tool. Now allows cut-through
to make new vertices in the middle of faces.
This also fixes knife bugs:
#36678, #35945, #35943, #35387, #35045, #35002.
Modified Paths:
--------------
trunk/blender/source/blender/editors/mesh/editmesh_knife.c
Modified: trunk/blender/source/blender/editors/mesh/editmesh_knife.c
===================================================================
--- trunk/blender/source/blender/editors/mesh/editmesh_knife.c 2013-11-05 16:20:06 UTC (rev 61143)
+++ trunk/blender/source/blender/editors/mesh/editmesh_knife.c 2013-11-05 16:24:00 UTC (rev 61144)
@@ -76,6 +76,7 @@
#define KNIFE_FLT_EPS 0.00001f
#define KNIFE_FLT_EPS_SQUARED (KNIFE_FLT_EPS * KNIFE_FLT_EPS)
+#define KNIFE_FLT_EPSBIG 0.001f
typedef struct KnifeColors {
unsigned char line[3];
@@ -111,16 +112,20 @@
bool draw;
} KnifeEdge;
-typedef struct BMEdgeHit {
- KnifeEdge *kfe;
+typedef struct KnifeLineHit {
float hit[3], cagehit[3];
- float realhit[3]; /* used in midpoint mode */
float schit[2];
float l; /* lambda along cut line */
float perc; /* lambda along hit line */
- KnifeVert *v; /* set if snapped to a vert */
+ float m; /* depth front-to-back */
+
+ /* Exactly one of kfe, v, or f should be non-NULL,
+ * saying whether cut line crosses and edge,
+ * is snapped to a vert, or is in the middle of some face. */
+ KnifeEdge *kfe;
+ KnifeVert *v;
BMFace *f;
-} BMEdgeHit;
+} KnifeLineHit;
typedef struct KnifePosData {
float co[3];
@@ -152,8 +157,8 @@
GHash *origvertmap;
GHash *origedgemap;
-
GHash *kedgefacemap;
+ GHash *facetrimap;
BMBVHTree *bmbvh;
@@ -164,7 +169,7 @@
float ethresh;
/* used for drag-cutting */
- BMEdgeHit *linehits;
+ KnifeLineHit *linehits;
int totlinehit;
/* Data for mouse-position-derived data (cur) and previous click (prev) */
@@ -215,13 +220,11 @@
static ListBase *knife_get_face_kedges(KnifeTool_OpData *kcd, BMFace *f);
-#if 0
-static void knife_input_ray_cast(KnifeTool_OpData *kcd, const float mval[2],
- float r_origin[3], float r_ray[3]);
-#endif
static void knife_input_ray_segment(KnifeTool_OpData *kcd, const float mval[2], const float ofs,
float r_origin[3], float r_dest[3]);
+static bool knife_verts_edge_in_face(KnifeVert *v1, KnifeVert *v2, BMFace *f);
+
static void knife_update_header(bContext *C, KnifeTool_OpData *kcd)
{
#define HEADER_LENGTH 256
@@ -238,13 +241,6 @@
ED_area_headerprint(CTX_wm_area(C), header);
}
-#if 0
-BLI_INLINE int round_ftoi(float x)
-{
- return x > 0.0f ? (int)(x + 0.5f) : (int)(x - 0.5f);
-}
-#endif
-
static void knife_project_v2(const KnifeTool_OpData *kcd, const float co[3], float sco[2])
{
ED_view3d_project_float_v2_m4(kcd->ar, co, sco, (float (*)[4])kcd->projmat);
@@ -290,6 +286,12 @@
return NULL;
}
+static void knife_append_list_no_dup(KnifeTool_OpData *kcd, ListBase *lst, void *elem)
+{
+ if (!find_ref(lst, elem))
+ knife_append_list(kcd, lst, elem);
+}
+
static KnifeEdge *new_knife_edge(KnifeTool_OpData *kcd)
{
kcd->totkedge++;
@@ -387,6 +389,45 @@
return kfe;
}
+/* Record the index in kcd->em->looptris of first looptri triple for a given face,
+ * given an index for some triple in that array.
+ * This assumes that all of the triangles for a given face are contiguous
+ * in that array (as they are by the current tesselation routines).
+ * Actually store index + 1 in the hash, because 0 looks like "no entry"
+ * to hash lookup routine; will reverse this in the get routine.
+ * Doing this lazily rather than all at once for all faces.
+ */
+static void set_lowest_face_tri(KnifeTool_OpData *kcd, BMFace *f, int index)
+{
+ int i;
+
+ if (BLI_ghash_lookup(kcd->facetrimap, f))
+ return;
+
+ BLI_assert(index >= 0 && index < kcd->em->tottri);
+ BLI_assert(kcd->em->looptris[index][0]->f == f);
+ for (i = index - 1; i >= 0; i--) {
+ if (kcd->em->looptris[i][0]->f != f) {
+ i++;
+ break;
+ }
+ }
+ if (i == -1)
+ i++;
+
+ BLI_ghash_insert(kcd->facetrimap, f, SET_INT_IN_POINTER(i + 1));
+}
+
+/* This should only be called for faces that have had a lowest face tri set by previous function */
+static int get_lowest_face_tri(KnifeTool_OpData *kcd, BMFace *f)
+{
+ int ans;
+
+ ans = GET_INT_FROM_POINTER(BLI_ghash_lookup(kcd->facetrimap, f));
+ BLI_assert(ans != 0);
+ return ans - 1;
+}
+
/* User has just clicked for first time or first time after a restart (E key).
* Copy the current position data into prev. */
static void knife_start_cut(KnifeTool_OpData *kcd)
@@ -430,12 +471,6 @@
return lst;
}
-/* finds the proper face to restrict face fill to */
-static void knife_find_basef(KnifeEdge *kfe)
-{
- kfe->basef = knife_find_common_face(&kfe->v1->faces, &kfe->v2->faces);
-}
-
static void knife_edge_append_face(KnifeTool_OpData *kcd, KnifeEdge *kfe, BMFace *f)
{
knife_append_list(kcd, knife_get_face_kedges(kcd, f), kfe);
@@ -493,466 +528,263 @@
return newkfe->v2;
}
-/* Make a single KnifeEdge for cut from kcd->prev to kcd->curr.
- * and move cur data to prev. */
-static void knife_add_single_cut(KnifeTool_OpData *kcd)
+/* primary key: lambda along cut
+ * secondary key: lambda along depth
+ * tertiary key: pointer comparisons of verts if both snapped to verts
+ */
+static int linehit_compare(const void *vlh1, const void *vlh2)
{
- KnifeEdge *kfe, *kfe2 = NULL, *kfe3 = NULL;
+ const KnifeLineHit *lh1 = vlh1;
+ const KnifeLineHit *lh2 = vlh2;
- if ((kcd->prev.vert && kcd->prev.vert == kcd->curr.vert) ||
- (kcd->prev.edge && kcd->prev.edge == kcd->curr.edge))
- {
- kcd->prev = kcd->curr;
- return;
- }
-
- kfe = new_knife_edge(kcd);
- kfe->draw = true;
-
- if (kcd->prev.vert) {
- kfe->v1 = kcd->prev.vert;
- }
- else if (kcd->prev.edge) {
- kfe->v1 = knife_split_edge(kcd, kcd->prev.edge, kcd->prev.co, &kfe2);
- }
- else {
- kfe->v1 = new_knife_vert(kcd, kcd->prev.co, kcd->prev.co);
- kfe->v1->draw = kfe->draw = !kcd->prev.is_space;
- kfe->v1->in_space = kcd->prev.is_space;
- kfe->draw = !kcd->prev.is_space;
- kfe->v1->is_face = true;
- if (kfe->v1->draw && kcd->prev.bmface)
- knife_append_list(kcd, &kfe->v1->faces, kcd->prev.bmface);
- }
-
- if (kcd->curr.vert) {
- kfe->v2 = kcd->curr.vert;
- }
- else if (kcd->curr.edge) {
- kfe->v2 = knife_split_edge(kcd, kcd->curr.edge, kcd->curr.co, &kfe3);
- kcd->curr.vert = kfe->v2;
- }
- else {
- kfe->v2 = new_knife_vert(kcd, kcd->curr.co, kcd->curr.co);
- kfe->v2->draw = !kcd->curr.is_space;
- kfe->v2->is_face = true;
- kfe->v2->in_space = kcd->curr.is_space;
- if (kfe->v2->draw && kcd->curr.bmface)
- knife_append_list(kcd, &kfe->v2->faces, kcd->curr.bmface);
-
- if (kcd->curr.is_space)
- kfe->draw = false;
-
- kcd->curr.vert = kfe->v2;
- }
-
- knife_find_basef(kfe);
-
- knife_add_to_vert_edges(kcd, kfe);
-
- if (kfe->basef && !find_ref(&kfe->faces, kfe->basef))
- knife_edge_append_face(kcd, kfe, kfe->basef);
-
- /* sanity check to make sure we're in the right edge/face lists */
- if (kcd->curr.bmface) {
- if (!find_ref(&kfe->faces, kcd->curr.bmface)) {
- knife_edge_append_face(kcd, kfe, kcd->curr.bmface);
- }
-
- if (kcd->prev.bmface && kcd->prev.bmface != kcd->curr.bmface) {
- if (!find_ref(&kfe->faces, kcd->prev.bmface)) {
- knife_edge_append_face(kcd, kfe, kcd->prev.bmface);
- }
- }
- }
-
- /* set up for next cut */
- kcd->prev = kcd->curr;
-}
-
-static int verge_linehit(const void *vlh1, const void *vlh2)
-{
- const BMEdgeHit *lh1 = vlh1, *lh2 = vlh2;
-
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)
-{
- int i;
- ListBase *testfaces, *ifaces;
- BMFace *testface, *iface;
- BMEdgeHit *lh;
- bool shareface;
-
- if (testi >= 0 && testi < kcd->totlinehit) {
- testface = NULL;
- testfaces = NULL;
- lh = &kcd->linehits[testi];
- if (lh->v)
- testfaces = &lh->v->faces;
- else if (lh->kfe)
- testfaces = &lh->kfe->faces;
- else if (lh->f) {
- testfaces = NULL;
- testface = lh->f;
- }
- }
+ else if (lh1->l > lh2->l) return 1;
else {
- testface = f;
- testfaces = NULL;
- }
- for (i = firsti; i <= lasti; i++) {
- shareface = false;
- lh = &kcd->linehits[i];
- iface = NULL;
- ifaces = NULL;
- if (lh->v)
- ifaces = &lh->v->faces;
- else if (lh->kfe)
- ifaces = &lh->kfe->faces;
- else if (lh->f) {
- ifaces = NULL;
- iface = lh->f;
+ if (lh1->m < lh2->m) return -1;
+ else if (lh1->m > lh2->m) return 1;
+ else {
+ if (lh1->v < lh2->v) return -1;
+ else if (lh1->v > lh2->v) return 1;
+ else return 0;
}
- if (testfaces) {
- if (ifaces)
- shareface = (knife_find_common_face(testfaces, ifaces) != NULL);
- else if (iface)
- shareface = (find_ref(testfaces, iface) != NULL);
- }
- else if (ifaces) {
- if (testface)
- shareface = (find_ref(ifaces, testface) != NULL);
- }
- else if (testface && iface) {
- shareface = (testface == iface);
- }
- if (shareface)
- return i;
}
- return -1;
}
-/* 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.
+/*
+ * Sort linehits by distance along cut line, and secondarily from
+ * front to back (from eye), and tertiarily by snap vertex,
+ * and remove any duplicates.
*/
-static void knife_sort_linehits(KnifeTool_OpData *kcd, bool joinfaces)
+static void prepare_linehits_for_cut(KnifeTool_OpData *kcd)
{
- int i, j, k, nexti, nsame;
+ KnifeLineHit *linehits, *lhi, *lhj;
+ int i, j, n;
- qsort(kcd->linehits, kcd->totlinehit, sizeof(BMEdgeHit), verge_linehit);
+ n = kcd->totlinehit;
+ linehits = kcd->linehits;
+ if (n == 0)
+ return;
- /* 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)
+ qsort(linehits, n, sizeof(KnifeLineHit), linehit_compare);
+
+ /* Remove any edge hits that are preceded or followed
+ * by a vertex hit that is very near. Mark such edge hits using
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list