part 1 of vkey rip tool. still needs more work. ugh, doing this tool correctly...
authorJoseph Eagar <joeedh@gmail.com>
Wed, 7 Oct 2009 21:19:58 +0000 (21:19 +0000)
committerJoseph Eagar <joeedh@gmail.com>
Wed, 7 Oct 2009 21:19:58 +0000 (21:19 +0000)
14 files changed:
source/blender/blenkernel/intern/editderivedbmesh.c
source/blender/blenlib/BLI_array.h
source/blender/bmesh/bmesh_queries.h
source/blender/bmesh/intern/bmesh_opdefines.c
source/blender/bmesh/intern/bmesh_operators_private.h
source/blender/bmesh/intern/bmesh_queries.c
source/blender/bmesh/operators/edgesplitop.c [new file with mode: 0644]
source/blender/bmesh/operators/subdivideop.c
source/blender/editors/mesh/bmesh_tools.c
source/blender/editors/mesh/editbmesh_bvh.c [new file with mode: 0644]
source/blender/editors/mesh/editbmesh_bvh.h [new file with mode: 0644]
source/blender/editors/mesh/editmesh_tools.c
source/blender/editors/mesh/mesh_ops.c
source/blender/editors/space_view3d/view3d_view.c

index 6aca8d51bc26032e2cc8d2d3ed2b277e9ebe0584..72580b66def8844788601d68af91328ac9cf5cbb 100644 (file)
@@ -882,32 +882,50 @@ static void bmDM_drawFacesTex_common(DerivedMesh *dm,
                                        
                                        bmdm_get_tri_tex(bm, ls, luv, lcol, has_uv, has_vcol);
                                        
-                                       glTexCoord2fv(luv[0]->uv);
-                                       glColor3ub(lcol[0]->r, lcol[0]->g, lcol[0]->b);
+                                       if (luv[0])
+                                               glTexCoord2fv(luv[0]->uv);
+                                       if (lcol[0])
+                                               glColor3ub(lcol[0]->r, lcol[0]->g, lcol[0]->b);
+                                       else glColor3ub(0, 0, 0);
                                        glVertex3fv(ls[0]->v->co);
 
-                                       glTexCoord2fv(luv[1]->uv);
-                                       glColor3ub(lcol[1]->r, lcol[1]->g, lcol[1]->b);
+                                       if (luv[1])
+                                               glTexCoord2fv(luv[1]->uv);
+                                       if (lcol[1])
+                                               glColor3ub(lcol[1]->r, lcol[1]->g, lcol[1]->b);
+                                       else glColor3ub(0, 0, 0);
                                        glVertex3fv(ls[1]->v->co);
 
-                                       glTexCoord2fv(luv[2]->uv);
-                                       glColor3ub(lcol[2]->r, lcol[2]->g, lcol[2]->b);
+                                       if (luv[2])
+                                               glTexCoord2fv(luv[2]->uv);
+                                       if (lcol[2])
+                                               glColor3ub(lcol[2]->r, lcol[2]->g, lcol[2]->b);
+                                       else glColor3ub(0, 0, 0);
                                        glVertex3fv(ls[2]->v->co);
                                } else {
                                        bmdm_get_tri_tex(bm, ls, luv, lcol, has_uv, has_vcol);
                                        
-                                       glTexCoord2fv(luv[0]->uv);
-                                       glColor3ub(lcol[0]->r, lcol[0]->g, lcol[0]->b);
+                                       if (luv[0])
+                                               glTexCoord2fv(luv[0]->uv);
+                                       if (lcol[0])
+                                               glColor3ub(lcol[0]->r, lcol[0]->g, lcol[0]->b);
+                                       else glColor3ub(0, 0, 0);
                                        glNormal3fv(ls[0]->v->no);
                                        glVertex3fv(ls[0]->v->co);
 
-                                       glTexCoord2fv(luv[1]->uv);
-                                       glColor3ub(lcol[1]->r, lcol[1]->g, lcol[1]->b);
+                                       if (luv[1])
+                                               glTexCoord2fv(luv[1]->uv);
+                                       if (lcol[1])
+                                               glColor3ub(lcol[1]->r, lcol[1]->g, lcol[1]->b);
+                                       else glColor3ub(0, 0, 0);
                                        glNormal3fv(ls[1]->v->no);
                                        glVertex3fv(ls[1]->v->co);
 
-                                       glTexCoord2fv(luv[2]->uv);
-                                       glColor3ub(lcol[2]->r, lcol[2]->g, lcol[2]->b);
+                                       if (luv[2])
+                                               glTexCoord2fv(luv[2]->uv);
+                                       if (lcol[2])
+                                               glColor3ub(lcol[2]->r, lcol[2]->g, lcol[2]->b);
+                                       else glColor3ub(0, 0, 0);
                                        glNormal3fv(ls[2]->v->no);
                                        glVertex3fv(ls[2]->v->co);
                                }
index 3f4660f0597928e5e4e57103ce3725a7923e25e3..c01d821cb8b94ee3eaa0e466c059b71a9dea0311 100644 (file)
 
 /*
 this library needs to be changed to not use macros quite so heavily,
-and to be more of a complete vector array API.  The way arrays are
+and to be more of a complete array API.  The way arrays are
 exposed to client code as normal C arrays is very useful though, imho.
-it does require some use of macros, however.
+it does require some use of macros, however.  
+
+anyway, it's used a bit too heavily to simply rewrite as a 
+more "correct" solution without macros entirely.  I originally wrote this
+to be very easy to use, without the normal pain of most array libraries.
+This was especially helpful when it came to the massive refactors necessary for
+bmesh, and really helped to speed the process up. - joeedh
   
 little array macro library.  example of usage:
 
@@ -51,28 +57,35 @@ the array size is doubled).  supposedly this should give good Big Oh
 behaviour, though it may not be the best in practice.
 */
 
-#define BLI_array_declare(vec) int _##vec##_count=0; void *_##vec##_tmp
+#define BLI_array_declare(arr) int _##arr##_count=0; void *_##arr##_tmp
 
 /*this returns the entire size of the array, including any buffering.*/
-#define BLI_array_totalsize(vec) ((signed int)((vec)==NULL ? 0 : MEM_allocN_len(vec) / sizeof(*vec)))
+#define BLI_array_totalsize(arr) ((signed int)((arr)==NULL ? 0 : MEM_allocN_len(arr) / sizeof(*arr)))
 
 /*this returns the logical size of the array, not including buffering.*/
-#define BLI_array_count(vec) _##vec##_count
+#define BLI_array_count(arr) _##arr##_count
 
 /*grow the array by one.  zeroes the new elements.*/
-#define BLI_array_growone(vec) \
-       BLI_array_totalsize(vec) > _##vec##_count ? _##vec##_count++ : \
-       ((_##vec##_tmp = MEM_callocN(sizeof(*vec)*(_##vec##_count*2+2), #vec " " __FILE__ " ")),\
-       (vec && memcpy(_##vec##_tmp, vec, sizeof(*vec) * _##vec##_count)),\
-       (vec && (MEM_freeN(vec),1)),\
-       (vec = _##vec##_tmp),\
-       _##vec##_count++)
+#define BLI_array_growone(arr) \
+       BLI_array_totalsize(arr) > _##arr##_count ? _##arr##_count++ : \
+       ((_##arr##_tmp = MEM_callocN(sizeof(*arr)*(_##arr##_count*2+2), #arr " " __FILE__ " ")),\
+       (arr && memcpy(_##arr##_tmp, arr, sizeof(*arr) * _##arr##_count)),\
+       (arr && (MEM_freeN(arr),1)),\
+       (arr = _##arr##_tmp),\
+       _##arr##_count++)
+
+/*appends an item to the array and returns a pointer to the item in the array.
+  item is not a pointer, but actual data value.*/
+#define BLI_array_append(arr, item) (BLI_array_growone(arr), arr[_##arr##_count] = item, (arr+_##arr##_count))
 
-#define BLI_array_free(vec) if (vec) MEM_freeN(vec);
+/*grow an array by a specified number of items.*/
+#define BLI_array_growitems(arr, num) {int _i; for (_i=0; _i<(num); _i++) {BLI_array_growone(arr);}}
+#define BLI_array_free(arr) if (arr) MEM_freeN(arr)
 
 /*resets the logical size of an array to zero, but doesn't
   free the memory.*/
-#define BLI_array_empty(vec) _##vec##_count=0
+#define BLI_array_empty(arr) _##arr##_count=0
 
-/*set the count of the array*/
-#define BLI_array_set_length(vec, count) _##vec##_count = (count)
+/*set the count of the array, doesn't actually increase the allocated array
+  size.  don't use this unless you know what your doing.*/
+#define BLI_array_set_length(arr, count) _##arr##_count = (count)
index dc38004929e7e4e17f253f472e9fefa69735cf3d..4f185d8725cae049bbab450953511d7d61bc2aa5 100644 (file)
@@ -13,7 +13,7 @@ int BM_Count_Element(struct BMesh *bm, int type);
 /*returns true if v is in f*/
 int BM_Vert_In_Face(struct BMFace *f, struct BMVert *v);
 
-// int BM_VERTS_OF_MESH_In_Face(struct BMFace *f, struct BMVert **varr, int len);
+// int BM_Verts_In_Face(struct BMFace *f, struct BMVert **varr, int len);
 int BM_Verts_In_Face(struct BMesh *bm, struct BMFace *f, struct BMVert **varr, int len);
 
 int BM_Edge_In_Face(struct BMFace *f, struct BMEdge *e);
index 70be33dc3156bda22ebad16f2d8bbf68501baeaf..caa09811ad93c7544328ed31eef3564560c5e25f 100644 (file)
@@ -154,12 +154,13 @@ BMOpDefine def_reversefaces = {
 };
 
 /*
-  Edge Split
+  Edge Bisect
 
   Splits input edges (but doesn't do anything else).
+  This creates a 2-valence vert.
 */
-BMOpDefine def_edgesplit = {
-       "edgesplit",
+BMOpDefine def_edgebisect = {
+       "edgebisect",
        {{BMOP_OPSLOT_ELEMENT_BUF, "edges"}, //input edges
        {BMOP_OPSLOT_INT, "numcuts"}, //number of cuts
        {BMOP_OPSLOT_ELEMENT_BUF, "outsplit"}, //newly created vertices and edges
@@ -802,6 +803,21 @@ BMOpDefine def_vertexshortestpath = {
        0
 };
 
+/*
+  Edge Split
+
+  Disconnects faces along input edges.
+ */
+BMOpDefine def_edgesplit = {
+       "edgesplit",
+       {{BMOP_OPSLOT_ELEMENT_BUF, "edges"}, /* input edges */
+        {BMOP_OPSLOT_ELEMENT_BUF, "edgeout1"}, /* old output disconnected edges */
+        {BMOP_OPSLOT_ELEMENT_BUF, "edgeout2"}, /* new output disconnected edges */
+        {0} /*null-terminating sentinel*/},
+       bmesh_edgesplitop_exec,
+       0
+};
+
 BMOpDefine *opdefines[] = {
        &def_splitop,
        &def_dupeop,
@@ -831,7 +847,7 @@ BMOpDefine *opdefines[] = {
        &def_removedoubles,
        &def_finddoubles,
        &def_mirror,
-       &def_edgesplit,
+       &def_edgebisect,
        &def_reversefaces,
        &def_edgerotate,
        &def_regionextend,
@@ -855,6 +871,7 @@ BMOpDefine *opdefines[] = {
        &def_meshreversecolors,
        &def_vertexshortestpath,
        &def_scale,
+       &def_edgesplit,
 };
 
 int bmesh_total_ops = (sizeof(opdefines) / sizeof(void*));
index faa767893b5fe71b58c82611f2a8cbb1aaa34323..e86920194c05a9aea6c8d254d6b5d8166b56fe04 100644 (file)
@@ -59,4 +59,5 @@ void bmesh_rotatecolors_exec(BMesh *bm, BMOperator *op);
 void bmesh_reversecolors_exec(BMesh *bm, BMOperator *op);
 void bmesh_vertexshortestpath_exec(BMesh *bm, BMOperator *op);
 void bmesh_scale_exec(BMesh *bm, BMOperator *op);
+void bmesh_edgesplitop_exec(BMesh *bm, BMOperator *op);
 #endif
index ace369cc2a1a1993a0ddc0b8a89964141b91d4cf..267bcd54a42afdf02aadd93d7c98ee6094558670 100644 (file)
@@ -184,6 +184,9 @@ BMEdge *BM_Edge_Exist(BMVert *v1, BMVert *v2)
        BMEdge *curedge;
        int i, len=0;
        
+       if (!v1 || !v2 || v1 == v2)
+               return NULL;
+       
        if(v1->edge){
                diskbase = bmesh_disk_getpointer(v1->edge,v1);
                len = bmesh_cycle_length(diskbase);
diff --git a/source/blender/bmesh/operators/edgesplitop.c b/source/blender/bmesh/operators/edgesplitop.c
new file mode 100644 (file)
index 0000000..1a878d2
--- /dev/null
@@ -0,0 +1,357 @@
+/**
+ * $Id:
+ *
+ * ***** 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. The Blender
+ * Foundation also sells licenses for use in proprietary software under
+ * the Blender License.  See http://www.blender.org/BL/ for information
+ * about this. 
+ *
+ * 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., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * Contributor(s): Joseph Eagar
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#include "MEM_guardedalloc.h"
+
+#include "BKE_utildefines.h"
+
+#include "BLI_arithb.h"
+#include "BLI_rand.h"
+#include "BLI_ghash.h"
+#include "BLI_array.h"
+
+#include "DNA_object_types.h"
+
+#include "ED_mesh.h"
+
+#include "bmesh.h"
+#include "mesh_intern.h"
+#include "subdivideop.h"
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <math.h>
+
+typedef struct EdgeTag {
+       BMVert *newv1, *newv2;
+       BMEdge *newe1, *newe2;
+       int tag;
+} EdgeTag;
+
+#define EDGE_SEAM      1
+#define EDGE_DEL       2
+#define EDGE_MARK      4
+#define EDGE_RET1      8
+#define EDGE_RET2      16
+
+#define FACE_DEL       1
+#define FACE_NEW       2
+
+static BMFace *remake_face(BMesh *bm, EdgeTag *etags, BMFace *f, BMVert **verts)
+{
+       BMIter liter1, liter2;
+       EdgeTag *et;
+       BMFace *f2;
+       BMLoop *l, *l2;
+       BMEdge **edges = (BMEdge**) verts; /*he he, can reuse this, sneaky! ;)*/
+       BMVert *lastv1, *lastv2, *v1, *v2;
+       int i;
+
+       /*we do final edge last*/
+       lastv1 = verts[f->len-1];
+       lastv2 = verts[0];
+       v1 = verts[0];
+       v2 = verts[1];
+       for (i=0; i<f->len-1; i++) {
+               edges[i] = BM_Make_Edge(bm, verts[i], verts[i+1], NULL, 1);
+
+               if (!edges[i])
+                       return NULL;
+       }
+       
+       edges[i] = BM_Make_Edge(bm, lastv1, lastv2, NULL, 1);
+
+       f2 = BM_Make_Ngon(bm, v1, v2, edges, f->len, 0);
+       if (!f2)
+               return NULL;
+       
+       BM_Copy_Attributes(bm, bm, f, f2);
+
+       l = BMIter_New(&liter1, bm, BM_LOOPS_OF_FACE, f);
+       l2 = BMIter_New(&liter2, bm, BM_LOOPS_OF_FACE, f2);
+       for (; l && l2; l=BMIter_Step(&liter1), l2=BMIter_Step(&liter2)) {
+               BM_Copy_Attributes(bm, bm, l, l2);
+               if (l->e != l2->e) {
+                       /*set up data for figuring out the two sides of
+                         the splits*/
+                       BMINDEX_SET(l2->e, BMINDEX_GET(l->e));
+                       et = etags + BMINDEX_GET(l->e);
+                       
+                       if (!et->newe1) et->newe1 = l2->e;
+                       else et->newe2 = l2->e;
+
+                       if (BMO_TestFlag(bm, l->e, EDGE_SEAM))
+                               BMO_SetFlag(bm, l2->e, EDGE_SEAM);
+
+                       BM_Copy_Attributes(bm, bm, l->e, l2->e);
+               }
+
+               BMO_SetFlag(bm, l->e, EDGE_MARK);
+               BMO_SetFlag(bm, l2->e, EDGE_MARK);
+       }
+
+       return f2;
+}
+
+void tag_out_edges(BMesh *bm, EdgeTag *etags, BMOperator *op)
+{
+       EdgeTag *et;
+       BMIter iter;
+       BMLoop *l, *startl;
+       BMEdge *e;
+       BMVert *v;
+       int i;
+
+       while (1) {
+               BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
+                       if (!BMO_TestFlag(bm, e, EDGE_SEAM))
+                               continue;
+
+                       et = etags + BMINDEX_GET(e);
+                       if (!et->tag && e->loop) {
+                               break;
+                       }
+               }
+               
+               if (!e)
+                       break;
+
+               /*ok we found an edge, part of a region of splits we need
+                 to identify.  now walk along it.*/
+               for (i=0; i<2; i++) {
+                       l = e->loop;
+                       
+                       v = i ? ((BMLoop*)l->head.next)->v : l->v;
+
+                       while (1) {
+                               et = etags + BMINDEX_GET(l->e);
+                               if (et->newe1 == l->e) {
+                                       if (et->newe1) {
+                                               BMO_SetFlag(bm, et->newe1, EDGE_RET1);
+                                               BMO_ClearFlag(bm, et->newe1, EDGE_SEAM);
+                                       }
+                                       if (et->newe2) {
+                                               BMO_SetFlag(bm, et->newe2, EDGE_RET2);
+                                               BMO_ClearFlag(bm, et->newe2, EDGE_SEAM);
+                                       }
+                               } else {
+                                       if (et->newe1) {
+                                               BMO_SetFlag(bm, et->newe1, EDGE_RET2);
+                                               BMO_ClearFlag(bm, et->newe1, EDGE_SEAM);
+                                       }
+                                       if (et->newe2) {
+                                               BMO_SetFlag(bm, et->newe2, EDGE_RET1);
+                                               BMO_ClearFlag(bm, et->newe2, EDGE_SEAM);
+                                       }
+                               }
+
+                               startl = l;
+                               do {
+                                       l = BM_OtherFaceLoop(l->e, l->f, v);
+                                       if (BM_Edge_FaceCount(l->e) != 2)
+                                               break;
+                                       l = (BMLoop*) l->radial.next->data;
+                               } while (l != startl && !BMO_TestFlag(bm, l->e, EDGE_SEAM));
+                               
+                               if (l == startl || !BMO_TestFlag(bm, l->e, EDGE_SEAM))
+                                       break;
+
+                               if (l->v == v) {
+                                       v = ((BMLoop*)l->head.next)->v;
+                               } else v = l->v;
+                       }
+               }
+       }
+}
+
+void bmesh_edgesplitop_exec(BMesh *bm, BMOperator *op)
+{
+       EdgeTag *etags, *et;
+       BMIter iter, liter;
+       BMOIter siter;
+       BMFace *f, *f2;
+       BMLoop *l, *nextl, *prevl, *l2, *l3;
+       BMEdge *e, *e2;
+       BLI_array_declare(verts);
+       BMVert *v, *v2, **verts = NULL;
+       int i, j;
+
+       BMO_Flag_Buffer(bm, op, "edges", EDGE_SEAM, BM_EDGE);
+       
+       /*single marked edges unconnected to any other marked edges
+         are illegal, go through and unmark them*/
+       BMO_ITER(e, &siter, bm, op, "edges", BM_EDGE) {
+               for (i=0; i<2; i++) {
+                       BM_ITER(e2, &iter, bm, BM_EDGES_OF_VERT, i ? e->v2 : e->v1) {
+                               if (e != e2 && BMO_TestFlag(bm, e2, EDGE_SEAM))
+                                       break;
+                       }
+                       if (e2)
+                               break;
+               }
+               if (!e2)
+                       BMO_ClearFlag(bm, e, EDGE_SEAM);
+       }
+
+       etags = MEM_callocN(sizeof(EdgeTag)*bm->totedge, "EdgeTag");
+       
+       i = 0;
+       BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
+               BMINDEX_SET(e, i);
+               i++;
+       }
+
+#ifdef ETV
+#undef ETV
+#endif
+#ifdef SETETV
+#undef SETETV
+#endif
+
+#define ETV(et, v, l) (l->e->v1 == v ? et->newv1 : et->newv2)
+#define SETETV(et, v, l, vs) l->e->v1 == v ? (et->newv1 = vs) : (et->newv2 = vs)
+
+       BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
+               if (BMO_TestFlag(bm, f, FACE_NEW))
+                       continue;
+               
+               BLI_array_empty(verts);
+               BLI_array_growitems(verts, f->len);
+               memset(verts, 0, sizeof(BMVert*)*f->len);
+               
+               i = 0;
+               BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
+                       if (!BMO_TestFlag(bm, l->e, EDGE_SEAM)) {
+                               if (!verts[i]) {
+                                       et = etags + BMINDEX_GET(l->e);
+                                       if (ETV(et, l->v, l))
+                                               verts[i] = ETV(et, l->v, l);
+                                       else verts[i] = l->v;
+                               }
+                               i++;
+                               continue;
+                       }
+
+                       BMO_SetFlag(bm, l->e, EDGE_DEL);
+
+                       nextl = (BMLoop*) l->head.next;
+                       prevl = (BMLoop*) l->head.prev;
+                       
+                       for (j=0; j<2; j++) {
+                               l2 = j ? nextl : prevl;
+                               v = j ? l2->v : l->v;
+
+                               if (BMO_TestFlag(bm, l2->e, EDGE_SEAM)) {
+                                       if (!verts[j ? (i+1) % f->len : i]) {
+                                               /*make unique vert here for this face only*/
+                                               v2 = BM_Make_Vert(bm, v->co, NULL);
+                                               VECCOPY(v2->no, v->no);
+                                               BM_Copy_Attributes(bm, bm, v, v2);
+
+                                               verts[j ? (i+1) % f->len : i] = v2;
+                                       } else v2 = verts[j ? (i+1) % f->len : i];
+                               } else {
+                                       /*generate unique vert for non-seam edge(s)
+                                         around the manifold vert fan if necassary*/
+
+                                       /*first check that we have two seam edges
+                                         somewhere within this fan*/
+                                       l3 = l2;
+                                       do {
+                                               if (BM_Edge_FaceCount(l3->e) != 2) {
+                                                       /*if we hit a boundary edge, tag
+                                                         l3 as null so we know to disconnect
+                                                         it*/
+                                                       if (BM_Edge_FaceCount(l3->e) == 1)
+                                                               l3 = NULL;
+                                                       break;
+                                               }
+
+                                               l3 = (BMLoop*)l3->radial.next->data;
+                                               l3 = BM_OtherFaceLoop(l3->e, l3->f, v);
+                                       } while (l3 != l2 && !BMO_TestFlag(bm, l3->e, EDGE_SEAM));
+
+                                       if (l3 == NULL || (BMO_TestFlag(bm, l3->e, EDGE_SEAM) && l3->e != l->e)) {
+                                               et = etags + BMINDEX_GET(l2->e);
+                                               if (ETV(et, v, l2) == NULL) {
+                                                       v2 = BM_Make_Vert(bm, v->co, NULL);
+                                                       VECCOPY(v2->no, v->no);
+                                                       BM_Copy_Attributes(bm, bm, v, v2);
+                                                       
+                                                       l3 = l2;
+                                                       do {
+                                                               SETETV(et, v, l3, v2);
+                                                               if (BM_Edge_FaceCount(l3->e) != 2)
+                                                                       break;
+
+                                                               l3 = (BMLoop*)l3->radial.next->data;
+                                                               l3 = BM_OtherFaceLoop(l3->e, l3->f, v);
+                                                               
+                                                               et = etags + BMINDEX_GET(l3->e);
+                                                       } while (l3 != l2 && !BMO_TestFlag(bm, l3->e, EDGE_SEAM));
+                                               } else v2 = ETV(et, v, l2);
+
+                                               verts[j ? (i+1) % f->len : i] = v2;
+                                       } else verts[j ? (i+1) % f->len : i] = v;
+                               }
+                       }
+
+                       i++;
+               }
+
+               f2 = remake_face(bm, etags, f, verts);
+               if (!f2)
+                       continue;
+
+               BMO_SetFlag(bm, f, FACE_DEL);
+               BMO_SetFlag(bm, f2, FACE_NEW);
+       }
+       
+       BMO_CallOpf(bm, "del geom=%ff context=%i", FACE_DEL, DEL_ONLYFACES);
+
+       /*test EDGE_MARK'd edges if we need to delete them, EDGE_MARK
+         is set in remake_face*/
+       BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
+               if (BMO_TestFlag(bm, e, EDGE_MARK)) {
+                       if (!e->loop)
+                               BMO_SetFlag(bm, e, EDGE_DEL);
+               }
+       }
+
+       BMO_CallOpf(bm, "del geom=%fe context=%i", EDGE_DEL, DEL_EDGES);
+       
+       tag_out_edges(bm, etags, op);
+       BMO_Flag_To_Slot(bm, op, "edgeout1", EDGE_RET1, BM_EDGE);
+       BMO_Flag_To_Slot(bm, op, "edgeout2", EDGE_RET2, BM_EDGE);
+
+       BLI_array_free(verts);
+       if (etags) MEM_freeN(etags);
+}
+
+#undef ETV
+#undef SETETV
index bbb972134d31e99364504819e1fa0bc8a558fe7e..2b72a734c83853a272e7145d05addc60cef2f724 100644 (file)
@@ -1,3 +1,30 @@
+/**
+ * $Id:
+ *
+ * ***** 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. The Blender
+ * Foundation also sells licenses for use in proprietary software under
+ * the Blender License.  See http://www.blender.org/BL/ for information
+ * about this. 
+ *
+ * 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., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * Contributor(s): Joseph Eagar.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
 #include "MEM_guardedalloc.h"
 
 #include "BKE_utildefines.h"
 #include <string.h>
 #include <math.h>
 
-/*subdivide future development notes:
-  each pattern should be able to be disabled
-  by the client code, and the client code 
-  should be able to pass in custom patterns.
-
-  so you can configure it anywhere from a simple
-  edge connect tool, to what's in 2.49a.
- */
-
 /*flags for all elements share a common bitfield space*/
 #define SUBD_SPLIT     1
 
index 0aec485ab96cb1d23c2b6a7ddc7637107fe477a8..eb1c84a382fc0854016a56d54244ea3076df8fea 100644 (file)
@@ -89,6 +89,8 @@
 #include "mesh_intern.h"
 #include "bmesh.h"
 
+#include "editbmesh_bvh.h"
+
 static void add_normal_aligned(float *nor, float *add)
 {
        if( INPR(nor, add) < -0.9999f)
@@ -2047,12 +2049,24 @@ static int bm_test_exec(bContext *C, wmOperator *op)
 {
        Scene *scene = CTX_data_scene(C);
        Object *obedit= CTX_data_edit_object(C);
+       RegionView3D *r3d = CTX_wm_region_view3d(C);            
        BMEditMesh *em= ((Mesh *)obedit->data)->edit_btmesh;
-#if 1
-       if (!EDBM_CallOpf(em, op, "collapse edges=%he", BM_SELECT))
-               return OPERATOR_CANCELLED;
+       BMBVHTree *tree = BMBVH_NewBVH(em);
+       BMIter iter;
+       BMEdge *e;
+
+       /*hide all back edges*/
+       BM_ITER(e, &iter, em->bm, BM_EDGES_OF_MESH, NULL) {
+               if (!BM_TestHFlag(e, BM_SELECT))
+                       continue;
+
+               if (!BMBVH_EdgeVisible(tree, e, r3d, obedit))
+                       BM_Select(em->bm, e, 0);
+       }
 
-#else //uv island walker test
+       BMBVH_FreeBVH(tree);
+       
+#if 0 //uv island walker test
        BMIter iter, liter;
        BMFace *f;
        BMLoop *l, *l2;
@@ -2908,3 +2922,396 @@ void MESH_OT_select_vertex_path(wmOperatorType *ot)
        /* properties */
        RNA_def_enum(ot->srna, "type", type_items, VPATH_SELECT_EDGE_LENGTH, "Type", "Method to compute distance.");
 }
+/********************** Rip Operator *************************/
+
+#if 0
+/* helper for below */
+static void mesh_rip_setface(EditMesh *em, EditFace *sefa)
+{
+       /* put new vertices & edges in best face */
+       if(sefa->v1->tmp.v) sefa->v1= sefa->v1->tmp.v;
+       if(sefa->v2->tmp.v) sefa->v2= sefa->v2->tmp.v;
+       if(sefa->v3->tmp.v) sefa->v3= sefa->v3->tmp.v;
+       if(sefa->v4 && sefa->v4->tmp.v) sefa->v4= sefa->v4->tmp.v;
+
+       sefa->e1= addedgelist(em, sefa->v1, sefa->v2, sefa->e1);
+       sefa->e2= addedgelist(em, sefa->v2, sefa->v3, sefa->e2);
+       if(sefa->v4) {
+               sefa->e3= addedgelist(em, sefa->v3, sefa->v4, sefa->e3);
+               sefa->e4= addedgelist(em, sefa->v4, sefa->v1, sefa->e4);
+       }
+       else
+               sefa->e3= addedgelist(em, sefa->v3, sefa->v1, sefa->e3);
+
+}
+#endif
+
+/* helper to find edge for edge_rip */
+static float mesh_rip_edgedist(ARegion *ar, float mat[][4], float *co1, float *co2, short *mval)
+{
+       float vec1[3], vec2[3], mvalf[2];
+
+       view3d_project_float(ar, co1, vec1, mat);
+       view3d_project_float(ar, co2, vec2, mat);
+       mvalf[0]= (float)mval[0];
+       mvalf[1]= (float)mval[1];
+
+       return PdistVL2Dfl(mvalf, vec1, vec2);
+}
+
+/* based on mouse cursor position, it defines how is being ripped */
+static int mesh_rip_invoke(bContext *C, wmOperator *op, wmEvent *event)
+{
+       Object *obedit= CTX_data_edit_object(C);
+       ARegion *ar= CTX_wm_region(C);
+       RegionView3D *rv3d= CTX_wm_region_view3d(C);
+       BMEditMesh *em= ((Mesh *)obedit->data)->edit_btmesh;
+       BMOperator bmop;
+       BMBVHTree *bvhtree;
+       BMOIter siter;
+       BMIter iter, eiter, liter;
+       BMLoop *l;
+       BMEdge *e, *e2, *closest = NULL;
+       BMVert *v;
+       int side = 0, i;
+       float projectMat[4][4], fmval[3] = {event->mval[0], event->mval[1], 0.0f};
+       float dist = FLT_MAX, d;
+
+       view3d_get_object_project_mat(rv3d, obedit, projectMat);
+
+       BM_ITER(e, &iter, em->bm, BM_EDGES_OF_MESH, NULL) {
+               if (BM_TestHFlag(e, BM_SELECT))
+                       BMINDEX_SET(e, 1);
+               else BMINDEX_SET(e, 0);
+       }
+
+       /*expand edge selection*/
+       BM_ITER(v, &iter, em->bm, BM_VERTS_OF_MESH, NULL) {
+               e2 = NULL;
+               i = 0;
+               BM_ITER(e, &eiter, em->bm, BM_EDGES_OF_VERT, v) {
+                       if (BMINDEX_GET(e)) {
+                               e2 = e;
+                               i++;
+                       }
+               }
+               
+               if (i == 1 && e2->loop) {
+                       l = BM_OtherFaceLoop(e2, e2->loop->f, v);
+                       l = (BMLoop*)l->radial.next->data;
+                       l = BM_OtherFaceLoop(l->e, l->f, v);
+
+                       if (l)
+                               BM_Select(em->bm, l->e, 1);
+               }
+       }
+
+       if (!EDBM_InitOpf(em, &bmop, op, "edgesplit edges=%he", BM_SELECT)) {
+               return OPERATOR_CANCELLED;
+       }
+       
+       BMO_Exec_Op(em->bm, &bmop);
+
+       /*build bvh tree for edge visibility tests*/
+       bvhtree = BMBVH_NewBVH(em);
+
+       for (i=0; i<2; i++) {
+               BMO_ITER(e, &siter, em->bm, &bmop, i ? "edgeout2":"edgeout1", BM_EDGE) {
+                       float cent[3] = {0, 0, 0}, mid[4], vec[3];
+
+                       if (!BMBVH_EdgeVisible(bvhtree, e, rv3d, obedit))
+                               continue;
+
+                       /*method for calculating distance:
+                       
+                         for each edge: calculate face center, then made a vector
+                         from edge midpoint to face center.  offset edge midpoint
+                         by a small amount along this vector.*/
+                       BM_ITER(l, &liter, em->bm, BM_LOOPS_OF_FACE, e->loop->f) {
+                               VecAddf(cent, cent, l->v->co);
+                       }
+                       VecMulf(cent, 1.0f/(float)e->loop->f->len);
+
+                       VecAddf(mid, e->v1->co, e->v2->co);
+                       VecMulf(mid, 0.5f);
+                       VecSubf(vec, cent, mid);
+                       Normalize(vec);
+                       VecMulf(vec, 0.01f);
+                       VecAddf(mid, mid, vec);
+
+                       /*yay we have our comparison point, now project it*/
+                       view3d_project_float(ar, mid, mid, projectMat);
+
+                       vec[0] = fmval[0] - mid[0];
+                       vec[1] = fmval[1] - mid[1];
+                       d = vec[0]*vec[0] + vec[1]*vec[1];
+
+                       if (d < dist) {
+                               side = i;
+                               closest = e;
+                               dist = d;
+                       }
+               }
+       }
+
+       EDBM_clear_flag_all(em, BM_SELECT);
+       BMO_HeaderFlag_Buffer(em->bm, &bmop, side?"edgeout2":"edgeout1", BM_SELECT, BM_EDGE);
+
+       BM_ITER(e, &iter, em->bm, BM_EDGES_OF_MESH, NULL) {
+               if (BM_TestHFlag(e, BM_SELECT))
+                       BMINDEX_SET(e, 1);
+               else BMINDEX_SET(e, 0);
+       }
+
+       /*constrict edge selection again*/
+       BM_ITER(v, &iter, em->bm, BM_VERTS_OF_MESH, NULL) {
+               e2 = NULL;
+               i = 0;
+               BM_ITER(e, &eiter, em->bm, BM_EDGES_OF_VERT, v) {
+                       if (BMINDEX_GET(e)) {
+                               e2 = e;
+                               i++;
+                       }
+               }
+               
+               if (i == 1) 
+                       BM_Select(em->bm, e2, 0);
+       }
+
+       EDBM_selectmode_flush(em);
+       
+       if (!EDBM_FinishOp(em, &bmop, op, 1)) {
+               BMBVH_FreeBVH(bvhtree);
+               return OPERATOR_CANCELLED;
+       }
+       
+       BMBVH_FreeBVH(bvhtree);
+
+       DAG_id_flush_update(obedit->data, OB_RECALC_DATA);
+       WM_event_add_notifier(C, NC_GEOM|ND_DATA, obedit->data);
+
+       return OPERATOR_FINISHED;
+#if 0 //BMESH_TODO
+       ARegion *ar= CTX_wm_region(C);
+       RegionView3D *rv3d= ar->regiondata;
+       Object *obedit= CTX_data_edit_object(C);
+       EditMesh *em= BKE_mesh_get_editmesh((Mesh *)obedit->data);
+       EditVert *eve, *nextve;
+       EditEdge *eed, *seed= NULL;
+       EditFace *efa, *sefa= NULL;
+       float projectMat[4][4], vec[3], dist, mindist;
+       short doit= 1, *mval= event->mval;
+
+       /* select flush... vertices are important */
+       EM_selectmode_set(em);
+
+       view3d_get_object_project_mat(rv3d, obedit, projectMat);
+
+       /* find best face, exclude triangles and break on face select or faces with 2 edges select */
+       mindist= 1000000.0f;
+       for(efa= em->faces.first; efa; efa=efa->next) {
+               if( efa->f & 1)
+                       break;
+               if(efa->v4 && faceselectedOR(efa, SELECT) ) {
+                       int totsel=0;
+
+                       if(efa->e1->f & SELECT) totsel++;
+                       if(efa->e2->f & SELECT) totsel++;
+                       if(efa->e3->f & SELECT) totsel++;
+                       if(efa->e4->f & SELECT) totsel++;
+
+                       if(totsel>1)
+                               break;
+                       view3d_project_float(ar, efa->cent, vec, projectMat);
+                       dist= sqrt( (vec[0]-mval[0])*(vec[0]-mval[0]) + (vec[1]-mval[1])*(vec[1]-mval[1]) );
+                       if(dist<mindist) {
+                               mindist= dist;
+                               sefa= efa;
+                       }
+               }
+       }
+
+       if(efa) {
+               BKE_report(op->reports, RPT_ERROR, "Can't perform ripping with faces selected this way");
+               BKE_mesh_end_editmesh(obedit->data, em);
+               return OPERATOR_CANCELLED;
+       }
+       if(sefa==NULL) {
+               BKE_report(op->reports, RPT_ERROR, "No proper selection or faces included");
+               BKE_mesh_end_editmesh(obedit->data, em);
+               return OPERATOR_CANCELLED;
+       }
+
+
+       /* duplicate vertices, new vertices get selected */
+       for(eve = em->verts.last; eve; eve= eve->prev) {
+               eve->tmp.v = NULL;
+               if(eve->f & SELECT) {
+                       eve->tmp.v = addvertlist(em, eve->co, eve);
+                       eve->f &= ~SELECT;
+                       eve->tmp.v->f |= SELECT;
+               }
+       }
+
+       /* find the best candidate edge */
+       /* or one of sefa edges is selected... */
+       if(sefa->e1->f & SELECT) seed= sefa->e2;
+       if(sefa->e2->f & SELECT) seed= sefa->e1;
+       if(sefa->e3->f & SELECT) seed= sefa->e2;
+       if(sefa->e4 && sefa->e4->f & SELECT) seed= sefa->e3;
+
+       /* or we do the distance trick */
+       if(seed==NULL) {
+               mindist= 1000000.0f;
+               if(sefa->e1->v1->tmp.v || sefa->e1->v2->tmp.v) {
+                       dist = mesh_rip_edgedist(ar, projectMat,
+                                                                        sefa->e1->v1->co,
+                                                                        sefa->e1->v2->co, mval);
+                       if(dist<mindist) {
+                               seed= sefa->e1;
+                               mindist= dist;
+                       }
+               }
+               if(sefa->e2->v1->tmp.v || sefa->e2->v2->tmp.v) {
+                       dist = mesh_rip_edgedist(ar, projectMat,
+                                                                        sefa->e2->v1->co,
+                                                                        sefa->e2->v2->co, mval);
+                       if(dist<mindist) {
+                               seed= sefa->e2;
+                               mindist= dist;
+                       }
+               }
+               if(sefa->e3->v1->tmp.v || sefa->e3->v2->tmp.v) {
+                       dist= mesh_rip_edgedist(ar, projectMat,
+                                                                       sefa->e3->v1->co,
+                                                                       sefa->e3->v2->co, mval);
+                       if(dist<mindist) {
+                               seed= sefa->e3;
+                               mindist= dist;
+                       }
+               }
+               if(sefa->e4 && (sefa->e4->v1->tmp.v || sefa->e4->v2->tmp.v)) {
+                       dist= mesh_rip_edgedist(ar, projectMat,
+                                                                       sefa->e4->v1->co,
+                                                                       sefa->e4->v2->co, mval);
+                       if(dist<mindist) {
+                               seed= sefa->e4;
+                               mindist= dist;
+                       }
+               }
+       }
+
+       if(seed==NULL) {        // never happens?
+               BKE_report(op->reports, RPT_ERROR, "No proper edge found to start");
+               BKE_mesh_end_editmesh(obedit->data, em);
+               return OPERATOR_CANCELLED;
+       }
+
+       faceloop_select(em, seed, 2);   // tmp abuse for finding all edges that need duplicated, returns OK faces with f1
+
+       /* duplicate edges in the loop, with at least 1 vertex selected, needed for selection flip */
+       for(eed = em->edges.last; eed; eed= eed->prev) {
+               eed->tmp.v = NULL;
+               if((eed->v1->tmp.v) || (eed->v2->tmp.v)) {
+                       EditEdge *newed;
+
+                       newed= addedgelist(em, eed->v1->tmp.v?eed->v1->tmp.v:eed->v1,
+                                                          eed->v2->tmp.v?eed->v2->tmp.v:eed->v2, eed);
+                       if(eed->f & SELECT) {
+                               EM_select_edge(eed, 0);
+                               EM_remove_selection(em, eed, EDITEDGE);
+                               EM_select_edge(newed, 1);
+                       }
+                       eed->tmp.v = (EditVert *)newed;
+               }
+       }
+
+       /* first clear edges to help finding neighbours */
+       for(eed = em->edges.last; eed; eed= eed->prev) eed->f1= 0;
+
+       /* put new vertices & edges && flag in best face */
+       mesh_rip_setface(em, sefa);
+
+       /* starting with neighbours of best face, we loop over the seam */
+       sefa->f1= 2;
+       doit= 1;
+       while(doit) {
+               doit= 0;
+
+               for(efa= em->faces.first; efa; efa=efa->next) {
+                       /* new vert in face */
+                       if (efa->v1->tmp.v || efa->v2->tmp.v ||
+                               efa->v3->tmp.v || (efa->v4 && efa->v4->tmp.v)) {
+                               /* face is tagged with loop */
+                               if(efa->f1==1) {
+                                       mesh_rip_setface(em, efa);
+                                       efa->f1= 2;
+                                       doit= 1;
+                               }
+                       }
+               }
+       }
+
+       /* remove loose edges, that were part of a ripped face */
+       for(eve = em->verts.first; eve; eve= eve->next) eve->f1= 0;
+       for(eed = em->edges.last; eed; eed= eed->prev) eed->f1= 0;
+       for(efa= em->faces.first; efa; efa=efa->next) {
+               efa->e1->f1= 1;
+               efa->e2->f1= 1;
+               efa->e3->f1= 1;
+               if(efa->e4) efa->e4->f1= 1;
+       }
+
+       for(eed = em->edges.last; eed; eed= seed) {
+               seed= eed->prev;
+               if(eed->f1==0) {
+                       if(eed->v1->tmp.v || eed->v2->tmp.v ||
+                          (eed->v1->f & SELECT) || (eed->v2->f & SELECT)) {
+                               remedge(em, eed);
+                               free_editedge(em, eed);
+                               eed= NULL;
+                       }
+               }
+               if(eed) {
+                       eed->v1->f1= 1;
+                       eed->v2->f1= 1;
+               }
+       }
+
+       /* and remove loose selected vertices, that got duplicated accidentally */
+       for(eve = em->verts.first; eve; eve= nextve) {
+               nextve= eve->next;
+               if(eve->f1==0 && (eve->tmp.v || (eve->f & SELECT))) {
+                       BLI_remlink(&em->verts,eve);
+                       free_editvert(em, eve);
+               }
+       }
+
+       DAG_id_flush_update(obedit->data, OB_RECALC_DATA);
+       WM_event_add_notifier(C, NC_GEOM|ND_DATA, obedit->data);
+
+       BKE_mesh_end_editmesh(obedit->data, em);
+
+//     RNA_enum_set(op->ptr, "proportional", 0);
+//     RNA_boolean_set(op->ptr, "mirror", 0);
+//     WM_operator_name_call(C, "TFM_OT_translate", WM_OP_INVOKE_REGION_WIN, op->ptr);
+#endif
+}
+
+void MESH_OT_rip(wmOperatorType *ot)
+{
+       /* identifiers */
+       ot->name= "Rip";
+       ot->idname= "MESH_OT_rip";
+
+       /* api callbacks */
+       ot->invoke= mesh_rip_invoke;
+       ot->poll= EM_view3d_poll;
+
+       /* flags */
+       ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
+
+       /* to give to transform */
+       Properties_Proportional(ot);
+       RNA_def_boolean(ot->srna, "mirror", 0, "Mirror Editing", "");
+}
\ No newline at end of file
diff --git a/source/blender/editors/mesh/editbmesh_bvh.c b/source/blender/editors/mesh/editbmesh_bvh.c
new file mode 100644 (file)
index 0000000..d93100e
--- /dev/null
@@ -0,0 +1,288 @@
+ /* $Id:
+ *
+ * ***** 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., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2004 by Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): Joseph Eagar
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+#include <stdlib.h>
+#include <stdarg.h>
+#include <string.h>
+#include <math.h>
+#include <float.h>
+
+#include "MEM_guardedalloc.h"
+#include "PIL_time.h"
+
+#include "BLO_sys_types.h" // for intptr_t support
+
+#include "DNA_mesh_types.h"
+#include "DNA_material_types.h"
+#include "DNA_meshdata_types.h"
+#include "DNA_modifier_types.h"
+#include "DNA_object_types.h"
+#include "DNA_scene_types.h"
+#include "DNA_screen_types.h"
+#include "DNA_view3d_types.h"
+#include "DNA_key_types.h"
+#include "DNA_windowmanager_types.h"
+
+#include "RNA_types.h"
+#include "RNA_define.h"
+#include "RNA_access.h"
+
+#include "BLI_blenlib.h"
+#include "BLI_arithb.h"
+#include "BLI_editVert.h"
+#include "BLI_rand.h"
+#include "BLI_ghash.h"
+#include "BLI_linklist.h"
+#include "BLI_heap.h"
+#include "BLI_array.h"
+#include "BLI_kdopbvh.h"
+
+#include "BKE_context.h"
+#include "BKE_customdata.h"
+#include "BKE_depsgraph.h"
+#include "BKE_global.h"
+#include "BKE_library.h"
+#include "BKE_mesh.h"
+#include "BKE_object.h"
+#include "BKE_utildefines.h"
+#include "BKE_bmesh.h"
+#include "BKE_report.h"
+#include "BKE_tessmesh.h"
+
+#include "BIF_gl.h"
+#include "BIF_glutil.h"
+
+#include "WM_api.h"
+#include "WM_types.h"
+
+#include "ED_mesh.h"
+#include "ED_view3d.h"
+#include "ED_util.h"
+#include "ED_screen.h"
+#include "ED_transform.h"
+
+#include "UI_interface.h"
+
+#include "mesh_intern.h"
+#include "bmesh.h"
+
+#include "editbmesh_bvh.h"
+
+typedef struct BMBVHTree {
+       BMEditMesh *em;
+       BMesh *bm;
+       BVHTree *tree;
+       float epsilon;
+} BMBVHTree;
+
+BMBVHTree *BMBVH_NewBVH(BMEditMesh *em)
+{
+       BMBVHTree *tree = MEM_callocN(sizeof(*tree), "BMBVHTree");
+       float cos[3][3];
+       int i;
+
+       BMEdit_RecalcTesselation(em);
+
+       tree->em = em;
+       tree->bm = em->bm;
+       tree->epsilon = FLT_EPSILON*2.0f;
+
+       tree->tree = BLI_bvhtree_new(em->tottri, tree->epsilon, 8, 8);
+
+       for (i=0; i<em->tottri; i++) {
+               VECCOPY(cos[0], em->looptris[i][0]->v->co);
+               VECCOPY(cos[1], em->looptris[i][1]->v->co);
+               VECCOPY(cos[2], em->looptris[i][2]->v->co);
+
+               BLI_bvhtree_insert(tree->tree, i, (float*)cos, 3);
+       }
+       
+       BLI_bvhtree_balance(tree->tree);
+       
+       return tree;
+}
+
+void BMBVH_FreeBVH(BMBVHTree *tree)
+{
+       BLI_bvhtree_free(tree->tree);
+       MEM_freeN(tree);
+}
+
+/*taken from bvhutils.c*/
+static float ray_tri_intersection(const BVHTreeRay *ray, const float m_dist, float *v0, 
+                                 float *v1, float *v2, float *uv, float e)
+{
+       float dist;
+#if 0
+       float vv1[3], vv2[3], vv3[3], cent[3];
+
+       /*expand triangle by an epsilon.  this is probably a really stupid
+         way of doing it, but I'm too tired to do better work.*/
+       VECCOPY(vv1, v0);
+       VECCOPY(vv2, v1);
+       VECCOPY(vv3, v2);
+
+       VecAddf(cent, vv1, vv2);
+       VecAddf(cent, cent, vv3);
+       VecMulf(cent, 1.0f/3.0f);
+
+       VecSubf(vv1, vv1, cent);
+       VecSubf(vv2, vv2, cent);
+       VecSubf(vv3, vv3, cent);
+
+       VecMulf(vv1, 1.0f + e);
+       VecMulf(vv2, 1.0f + e);
+       VecMulf(vv3, 1.0f + e);
+
+       VecAddf(vv1, vv1, cent);
+       VecAddf(vv2, vv2, cent);
+       VecAddf(vv3, vv3, cent);
+
+       if(RayIntersectsTriangle((float*)ray->origin, (float*)ray->direction, vv1, vv2, vv3, &dist, uv))
+               return dist;
+#else
+       if(RayIntersectsTriangle((float*)ray->origin, (float*)ray->direction, v0, v1, v2, &dist, uv))
+               return dist;
+#endif
+
+       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], co1[3], co2[3], co3[3];
+
+       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;
+               
+               VECCOPY(hit->no, ls[0]->v->no);
+
+               VECCOPY(co1, ls[0]->v->co);
+               VECCOPY(co2, ls[1]->v->co);
+               VECCOPY(co3, ls[2]->v->co);
+
+               VecMulf(co1, uv[0]);
+               VecMulf(co2, uv[1]);
+               VecMulf(co3, 1.0f-uv[0]-uv[1]);
+
+               VecAddf(hit->co, co1, co2);
+               VecAddf(hit->co, hit->co, co3);
+       }
+}
+
+BMFace *BMBVH_RayCast(BMBVHTree *tree, float *co, float *dir, float *hitout)
+{
+       BVHTreeRayHit hit;
+
+       hit.dist = FLT_MAX;
+       hit.index = -1;
+
+       BLI_bvhtree_ray_cast(tree->tree, co, dir, FLT_MAX, &hit, raycallback, tree);
+       if (hit.dist != FLT_MAX && hit.index != -1) {
+               if (hitout) {
+                       VECCOPY(hitout, hit.co);
+               }
+
+               return tree->em->looptris[hit.index][0]->f;
+       }
+
+       return NULL;
+}
+
+#if 0 //BMESH_TODO: not implemented yet
+int BMBVH_VertVisible(BMBVHTree *tree, BMEdge *e, RegionView3D *r3d)
+{
+
+}
+#endif
+
+static BMFace *edge_ray_cast(BMBVHTree *tree, float *co, float *dir, float *hitout, BMEdge *e)
+{
+       BMFace *f = BMBVH_RayCast(tree, co, dir, hitout);
+       
+       if (f && BM_Edge_In_Face(f, e))
+               return NULL;
+
+       return f;
+}
+
+int BMBVH_EdgeVisible(BMBVHTree *tree, BMEdge *e, RegionView3D *r3d, Object *obedit)
+{
+       BMFace *f;
+       float co1[3], co2[3], co3[3], dir1[4], dir2[4], dir3[4];
+       float origin[3], invmat[4][4];
+       float epsilon = 0.01f; 
+       
+       VECCOPY(origin, r3d->viewinv[3]);
+       Mat4Invert(invmat, obedit->obmat);
+       Mat4MulVecfl(invmat, origin);
+
+       VECCOPY(co1, e->v1->co);
+       VecAddf(co2, e->v1->co, e->v2->co);
+       VecMulf(co2, 0.5f);
+       VECCOPY(co3, e->v2->co);
+       
+       /*ok, idea is to generate rays going from the camera origin to the 
+         three points on the edge (v1, mid, v2)*/
+       VecSubf(dir1, origin, co1);
+       VecSubf(dir2, origin, co2);
+       VecSubf(dir3, origin, co3);
+       
+       Normalize(dir1);
+       Normalize(dir2);
+       Normalize(dir3);
+
+       VecMulf(dir1, epsilon);
+       VecMulf(dir2, epsilon);
+       VecMulf(dir3, epsilon);
+       
+       /*offset coordinates slightly along view vectors, to avoid
+         hitting the faces that own the edge.*/
+       VecAddf(co1, co1, dir1);
+       VecAddf(co2, co2, dir2);
+       VecAddf(co3, co3, dir3);
+
+       Normalize(dir1);
+       Normalize(dir2);
+       Normalize(dir3);
+
+       /*do three samplings: left, middle, right*/
+       f = edge_ray_cast(tree, co1, dir1, NULL, e);
+       if (f && !edge_ray_cast(tree, co2, dir2, NULL, e))
+               return 1;
+       else if (f && !edge_ray_cast(tree, co3, dir3, NULL, e))
+               return 1;
+       else if (!f)
+               return 1;
+
+       return 0;
+}
diff --git a/source/blender/editors/mesh/editbmesh_bvh.h b/source/blender/editors/mesh/editbmesh_bvh.h
new file mode 100644 (file)
index 0000000..fbbf26b
--- /dev/null
@@ -0,0 +1,15 @@
+struct BMEditMesh;
+struct BMFace;
+struct BMEdge;
+struct BMVert;
+struct RegionView3D;
+
+struct BMBVHTree;
+typedef struct BMBVHTree BMBVHTree;
+
+BMBVHTree *BMBVH_NewBVH(struct BMEditMesh *em);
+void BMBVH_FreeBVH(BMBVHTree *tree);
+
+struct BMFace *BMBVH_RayCast(BMBVHTree *tree, float *co, float *dir, float *hitout);
+int BMBVH_EdgeVisible(BMBVHTree *tree, struct BMEdge *e, 
+                      struct RegionView3D *r3d, struct Object *obedit);
index ab518f8d8788bbf4f18e7107cd796f6a5868b3d3..9c26c812de99b2d610065ef977c75e48de72628d 100644 (file)
@@ -4243,272 +4243,6 @@ void mesh_set_face_flags(EditMesh *em, short mode)
 }
 #endif
 
-/********************** Rip Operator *************************/
-
-/* helper to find edge for edge_rip */
-static float mesh_rip_edgedist(ARegion *ar, float mat[][4], float *co1, float *co2, short *mval)
-{
-       float vec1[3], vec2[3], mvalf[2];
-
-       view3d_project_float(ar, co1, vec1, mat);
-       view3d_project_float(ar, co2, vec2, mat);
-       mvalf[0]= (float)mval[0];
-       mvalf[1]= (float)mval[1];
-
-       return PdistVL2Dfl(mvalf, vec1, vec2);
-}
-
-/* helper for below */
-static void mesh_rip_setface(EditMesh *em, EditFace *sefa)
-{
-       /* put new vertices & edges in best face */
-       if(sefa->v1->tmp.v) sefa->v1= sefa->v1->tmp.v;
-       if(sefa->v2->tmp.v) sefa->v2= sefa->v2->tmp.v;
-       if(sefa->v3->tmp.v) sefa->v3= sefa->v3->tmp.v;
-       if(sefa->v4 && sefa->v4->tmp.v) sefa->v4= sefa->v4->tmp.v;
-
-       sefa->e1= addedgelist(em, sefa->v1, sefa->v2, sefa->e1);
-       sefa->e2= addedgelist(em, sefa->v2, sefa->v3, sefa->e2);
-       if(sefa->v4) {
-               sefa->e3= addedgelist(em, sefa->v3, sefa->v4, sefa->e3);
-               sefa->e4= addedgelist(em, sefa->v4, sefa->v1, sefa->e4);
-       }
-       else
-               sefa->e3= addedgelist(em, sefa->v3, sefa->v1, sefa->e3);
-
-}
-
-/* based on mouse cursor position, it defines how is being ripped */
-static int mesh_rip_invoke(bContext *C, wmOperator *op, wmEvent *event)
-{
-#if 0 //BMESH_TODO
-       ARegion *ar= CTX_wm_region(C);
-       RegionView3D *rv3d= ar->regiondata;
-       Object *obedit= CTX_data_edit_object(C);
-       EditMesh *em= BKE_mesh_get_editmesh((Mesh *)obedit->data);
-       EditVert *eve, *nextve;
-       EditEdge *eed, *seed= NULL;
-       EditFace *efa, *sefa= NULL;
-       float projectMat[4][4], vec[3], dist, mindist;
-       short doit= 1, *mval= event->mval;
-
-       /* select flush... vertices are important */
-       EM_selectmode_set(em);
-
-       view3d_get_object_project_mat(rv3d, obedit, projectMat);
-
-       /* find best face, exclude triangles and break on face select or faces with 2 edges select */
-       mindist= 1000000.0f;
-       for(efa= em->faces.first; efa; efa=efa->next) {
-               if( efa->f & 1)
-                       break;
-               if(efa->v4 && faceselectedOR(efa, SELECT) ) {
-                       int totsel=0;
-
-                       if(efa->e1->f & SELECT) totsel++;
-                       if(efa->e2->f & SELECT) totsel++;
-                       if(efa->e3->f & SELECT) totsel++;
-                       if(efa->e4->f & SELECT) totsel++;
-
-                       if(totsel>1)
-                               break;
-                       view3d_project_float(ar, efa->cent, vec, projectMat);
-                       dist= sqrt( (vec[0]-mval[0])*(vec[0]-mval[0]) + (vec[1]-mval[1])*(vec[1]-mval[1]) );
-                       if(dist<mindist) {
-                               mindist= dist;
-                               sefa= efa;
-                       }
-               }
-       }
-
-       if(efa) {
-               BKE_report(op->reports, RPT_ERROR, "Can't perform ripping with faces selected this way");
-               BKE_mesh_end_editmesh(obedit->data, em);
-               return OPERATOR_CANCELLED;
-       }
-       if(sefa==NULL) {
-               BKE_report(op->reports, RPT_ERROR, "No proper selection or faces included");
-               BKE_mesh_end_editmesh(obedit->data, em);
-               return OPERATOR_CANCELLED;
-       }
-
-
-       /* duplicate vertices, new vertices get selected */
-       for(eve = em->verts.last; eve; eve= eve->prev) {
-               eve->tmp.v = NULL;
-               if(eve->f & SELECT) {
-                       eve->tmp.v = addvertlist(em, eve->co, eve);
-                       eve->f &= ~SELECT;
-                       eve->tmp.v->f |= SELECT;
-               }
-       }
-
-       /* find the best candidate edge */
-       /* or one of sefa edges is selected... */
-       if(sefa->e1->f & SELECT) seed= sefa->e2;
-       if(sefa->e2->f & SELECT) seed= sefa->e1;
-       if(sefa->e3->f & SELECT) seed= sefa->e2;
-       if(sefa->e4 && sefa->e4->f & SELECT) seed= sefa->e3;
-
-       /* or we do the distance trick */
-       if(seed==NULL) {
-               mindist= 1000000.0f;
-               if(sefa->e1->v1->tmp.v || sefa->e1->v2->tmp.v) {
-                       dist = mesh_rip_edgedist(ar, projectMat,
-                                                                        sefa->e1->v1->co,
-                                                                        sefa->e1->v2->co, mval);
-                       if(dist<mindist) {
-                               seed= sefa->e1;
-                               mindist= dist;
-                       }
-               }
-               if(sefa->e2->v1->tmp.v || sefa->e2->v2->tmp.v) {
-                       dist = mesh_rip_edgedist(ar, projectMat,
-                                                                        sefa->e2->v1->co,
-                                                                        sefa->e2->v2->co, mval);
-                       if(dist<mindist) {
-                               seed= sefa->e2;
-                               mindist= dist;
-                       }
-               }
-               if(sefa->e3->v1->tmp.v || sefa->e3->v2->tmp.v) {
-                       dist= mesh_rip_edgedist(ar, projectMat,
-                                                                       sefa->e3->v1->co,
-                                                                       sefa->e3->v2->co, mval);
-                       if(dist<mindist) {
-                               seed= sefa->e3;
-                               mindist= dist;
-                       }
-               }
-               if(sefa->e4 && (sefa->e4->v1->tmp.v || sefa->e4->v2->tmp.v)) {
-                       dist= mesh_rip_edgedist(ar, projectMat,
-                                                                       sefa->e4->v1->co,
-                                                                       sefa->e4->v2->co, mval);
-                       if(dist<mindist) {
-                               seed= sefa->e4;
-                               mindist= dist;
-                       }
-               }
-       }
-
-       if(seed==NULL) {        // never happens?
-               BKE_report(op->reports, RPT_ERROR, "No proper edge found to start");
-               BKE_mesh_end_editmesh(obedit->data, em);
-               return OPERATOR_CANCELLED;
-       }
-
-       faceloop_select(em, seed, 2);   // tmp abuse for finding all edges that need duplicated, returns OK faces with f1
-
-       /* duplicate edges in the loop, with at least 1 vertex selected, needed for selection flip */
-       for(eed = em->edges.last; eed; eed= eed->prev) {
-               eed->tmp.v = NULL;
-               if((eed->v1->tmp.v) || (eed->v2->tmp.v)) {
-                       EditEdge *newed;
-
-                       newed= addedgelist(em, eed->v1->tmp.v?eed->v1->tmp.v:eed->v1,
-                                                          eed->v2->tmp.v?eed->v2->tmp.v:eed->v2, eed);
-                       if(eed->f & SELECT) {
-                               EM_select_edge(eed, 0);
-                               EM_remove_selection(em, eed, EDITEDGE);
-                               EM_select_edge(newed, 1);
-                       }
-                       eed->tmp.v = (EditVert *)newed;
-               }
-       }
-
-       /* first clear edges to help finding neighbours */
-       for(eed = em->edges.last; eed; eed= eed->prev) eed->f1= 0;
-
-       /* put new vertices & edges && flag in best face */
-       mesh_rip_setface(em, sefa);
-
-       /* starting with neighbours of best face, we loop over the seam */
-       sefa->f1= 2;
-       doit= 1;
-       while(doit) {
-               doit= 0;
-
-               for(efa= em->faces.first; efa; efa=efa->next) {
-                       /* new vert in face */
-                       if (efa->v1->tmp.v || efa->v2->tmp.v ||
-                               efa->v3->tmp.v || (efa->v4 && efa->v4->tmp.v)) {
-                               /* face is tagged with loop */
-                               if(efa->f1==1) {
-                                       mesh_rip_setface(em, efa);
-                                       efa->f1= 2;
-                                       doit= 1;
-                               }
-                       }
-               }
-       }
-
-       /* remove loose edges, that were part of a ripped face */
-       for(eve = em->verts.first; eve; eve= eve->next) eve->f1= 0;
-       for(eed = em->edges.last; eed; eed= eed->prev) eed->f1= 0;
-       for(efa= em->faces.first; efa; efa=efa->next) {
-               efa->e1->f1= 1;
-               efa->e2->f1= 1;
-               efa->e3->f1= 1;
-               if(efa->e4) efa->e4->f1= 1;
-       }
-
-       for(eed = em->edges.last; eed; eed= seed) {
-               seed= eed->prev;
-               if(eed->f1==0) {
-                       if(eed->v1->tmp.v || eed->v2->tmp.v ||
-                          (eed->v1->f & SELECT) || (eed->v2->f & SELECT)) {
-                               remedge(em, eed);
-                               free_editedge(em, eed);
-                               eed= NULL;
-                       }
-               }
-               if(eed) {
-                       eed->v1->f1= 1;
-                       eed->v2->f1= 1;
-               }
-       }
-
-       /* and remove loose selected vertices, that got duplicated accidentally */
-       for(eve = em->verts.first; eve; eve= nextve) {
-               nextve= eve->next;
-               if(eve->f1==0 && (eve->tmp.v || (eve->f & SELECT))) {
-                       BLI_remlink(&em->verts,eve);
-                       free_editvert(em, eve);
-               }
-       }
-
-       DAG_id_flush_update(obedit->data, OB_RECALC_DATA);
-       WM_event_add_notifier(C, NC_GEOM|ND_DATA, obedit->data);
-
-       BKE_mesh_end_editmesh(obedit->data, em);
-
-//     RNA_enum_set(op->ptr, "proportional", 0);
-//     RNA_boolean_set(op->ptr, "mirror", 0);
-//     WM_operator_name_call(C, "TFM_OT_translate", WM_OP_INVOKE_REGION_WIN, op->ptr);
-#endif
-
-       return OPERATOR_FINISHED;
-}
-
-void MESH_OT_rip(wmOperatorType *ot)
-{
-       /* identifiers */
-       ot->name= "Rip";
-       ot->idname= "MESH_OT_rip";
-
-       /* api callbacks */
-       ot->invoke= mesh_rip_invoke;
-       ot->poll= EM_view3d_poll;
-
-       /* flags */
-       ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
-
-       /* to give to transform */
-       Properties_Proportional(ot);
-       RNA_def_boolean(ot->srna, "mirror", 0, "Mirror Editing", "");
-}
-
-
 /************************ Shape Operators *************************/
 
 void shape_propagate(Scene *scene, Object *obedit, EditMesh *em, wmOperator *op)
index c704497292047e883d2860332a123cfd2dd1ee81..e75781aab2016b37541f6f66de18f49e765bf1af 100644 (file)
@@ -458,7 +458,7 @@ void ED_keymap_mesh(wmWindowManager *wm)
        //WM_keymap_add_item(keymap, "MESH_OT_colors_mirror",EIGHTKEY, KM_PRESS, KM_ALT, 0);
        WM_keymap_add_item(keymap, "MESH_OT_colors_reverse",EIGHTKEY, KM_PRESS, KM_ALT, 0);
 
-       WM_keymap_add_item(keymap, "MESH_OT_rip_move",VKEY, KM_PRESS, 0, 0);
+       WM_keymap_add_item(keymap, "MESH_OT_rip_move",VKEY, KM_PRESS, KM_SHIFT, 0);
        WM_keymap_add_item(keymap, "MESH_OT_merge", MKEY, KM_PRESS, KM_ALT, 0);
 
        /* add/remove */
index 7831d604ddf040229b157ec70f8dc72114421f7d..b6260e66af437fbe0effba3442129c294c0e8fab 100644 (file)
@@ -571,8 +571,8 @@ void view3d_project_float(ARegion *ar, float *vec, float *adr, float mat[4][4])
 {
        float vec4[4];
        
-       adr[0]= IS_CLIPPED;
        VECCOPY(vec4, vec);
+       adr[0]= IS_CLIPPED;
        vec4[3]= 1.0;
        
        Mat4MulVec4fl(mat, vec4);