[Bf-committers] Edge Based Subdivide Sanity Check

Johnny Matthews johnny.matthews at gmail.com
Wed Jun 8 17:42:09 CEST 2005


Ok, things are moving along well, I still have a todo list, but I 
thought I would post edge based subdivide as far as I have it to this 
point for comments, crits, etc.

There are still a bunch of little trivial things to fix like which edges 
get selected, etc, and UV and Vertcol are not right yet. But this is the 
core of the code,
this patch also includes edge ring select  CRTL-ALT-RMB  
(CTRL-ALT-SHIFT-RMB is add/subtract edgering to current selection)

Edge based subdiv is in the w menu e-subdiv. I know there are issues 
with having it at the top of the list. That will be address when it is 
integrated into bf, so
don't give me any grief about it :)

Anyway, let me know what you think.

Johnny
-------------- next part --------------
Index: source/blender/include/BIF_editmesh.h
===================================================================
RCS file: /cvsroot/bf-blender/blender/source/blender/include/BIF_editmesh.h,v
retrieving revision 1.37
diff -u -r1.37 BIF_editmesh.h
--- source/blender/include/BIF_editmesh.h	16 Feb 2005 15:02:58 -0000	1.37
+++ source/blender/include/BIF_editmesh.h	3 Jun 2005 20:05:05 -0000
@@ -156,6 +156,7 @@
 extern void xsortvert_flag(int flag);
 extern void hashvert_flag(int flag);
 extern void subdivideflag(int flag, float rad, int beauty);
+extern void esubdivideflag(int flag, float rad, int beauty, int numcuts);
 extern void extrude_mesh(void);
 extern void split_mesh(void);
 extern void extrude_repeat_mesh(int steps, float offs);
Index: source/blender/src/editmesh_mods.c
===================================================================
RCS file: /cvsroot/bf-blender/blender/source/blender/src/editmesh_mods.c,v
retrieving revision 1.52
diff -u -r1.52 editmesh_mods.c
--- source/blender/src/editmesh_mods.c	27 May 2005 09:51:07 -0000	1.52
+++ source/blender/src/editmesh_mods.c	5 Jun 2005 19:25:55 -0000
@@ -973,6 +973,74 @@
 	}
 }
 
+/* 
+   Almostly exactly the same code as faceloop select
+*/
+static void edgering_select(EditEdge *startedge, int select){
+	EditMesh *em = G.editMesh;
+	EditEdge *eed;
+	EditFace *efa;
+	int looking= 1;
+	
+	/* in eed->f1 we put the valence (amount of faces in edge) */
+	/* in eed->f2 we put tagged flag as correct loop */
+	/* in efa->f1 we put tagged flag as correct to select */
+
+	for(eed= em->edges.first; eed; eed= eed->next) {
+		eed->f1= 0;
+		eed->f2= 0;
+	}
+	for(efa= em->faces.first; efa; efa= efa->next) {
+		efa->f1= 0;
+		if(efa->h==0) {
+			efa->e1->f1++;
+			efa->e2->f1++;
+			efa->e3->f1++;
+			if(efa->e4) efa->e4->f1++;
+		}
+	}
+	
+	// tag startedge OK
+	startedge->f2= 1;
+	
+	while(looking) {
+		looking= 0;
+		
+		for(efa= em->faces.first; efa; efa= efa->next) {
+			if(efa->e4 && efa->f1==0) {	// not done quad
+				if(efa->e1->f1<=2 && efa->e2->f1<=2 && efa->e3->f1<=2 && efa->e4->f1<=2) { // valence ok
+
+					// if edge tagged, select opposing edge and mark face ok
+					if(efa->e1->f2) {
+						efa->e3->f2= 1;
+						efa->f1= 1;
+						looking= 1;
+					}
+					else if(efa->e2->f2) {
+						efa->e4->f2= 1;
+						efa->f1= 1;
+						looking= 1;
+					}
+					if(efa->e3->f2) {
+						efa->e1->f2= 1;
+						efa->f1= 1;
+						looking= 1;
+					}
+					if(efa->e4->f2) {
+						efa->e2->f2= 1;
+						efa->f1= 1;
+						looking= 1;
+					}
+				}
+			}
+		}
+	}
+	
+	/* (de)select the edges */
+	for(eed= em->edges.first; eed; eed= eed->next) {
+    		if(eed->f2) EM_select_edge(eed, select);
+	}
+}
 /* ***************** MAIN MOUSE SELECTION ************** */
 
 // just to have the functions nice together
@@ -992,8 +1060,14 @@
 		if(G.scene->selectmode & SCE_SELECT_FACE) {
 			faceloop_select(eed, eed->f & SELECT);
 		}
-		else {
-			edgeloop_select(eed, eed->f & SELECT);
+		else if(G.scene->selectmode & SCE_SELECT_EDGE) {
+            if(G.qual == (LR_CTRLKEY | LR_ALTKEY) || G.qual == (LR_CTRLKEY | LR_ALTKEY |LR_SHIFTKEY))
+    			edgering_select(eed, eed->f & SELECT);
+            else if(G.qual & LR_ALTKEY)
+    			edgeloop_select(eed, eed->f & SELECT);
+		}
+        else if(G.scene->selectmode & SCE_SELECT_VERTEX) {
+            edgeloop_select(eed, eed->f & SELECT);
 		}
 
 		/* frontbuffer draw of last selected only */
Index: source/blender/src/editmesh_tools.c
===================================================================
RCS file: /cvsroot/bf-blender/blender/source/blender/src/editmesh_tools.c,v
retrieving revision 1.51
diff -u -r1.51 editmesh_tools.c
--- source/blender/src/editmesh_tools.c	7 Jun 2005 13:04:31 -0000	1.51
+++ source/blender/src/editmesh_tools.c	8 Jun 2005 15:31:31 -0000
@@ -25,7 +25,7 @@
  *
  * The Original Code is: all of this file.
  *
- * Contributor(s): none yet.
+ * Contributor(s): Johnny Matthews.
  *
  * ***** END GPL/BL DUAL LICENSE BLOCK *****
  */
@@ -59,6 +59,7 @@
 #include "BLI_arithb.h"
 #include "BLI_editVert.h"
 #include "BLI_rand.h"
+#include "BLI_ghash.h"
 
 #include "BKE_displist.h"
 #include "BKE_global.h"
@@ -93,8 +94,8 @@
 
 /* local prototypes ---------------*/
 void bevel_menu(void);
-
-
+static void free_tagged_edgelist(EditEdge *eed);
+static void free_tagged_facelist(EditFace *efa);
 /********* qsort routines *********/
 
 
@@ -1959,6 +1960,852 @@
 	allqueue(REDRAWVIEW3D, 0);
 	makeDispList(G.obedit);
 }
+
+
+/*--------------Edge Based Subdivide------------------*/
+#define EDGENEW    8
+
+static void fill_quad_single(EditFace *efa, struct GHash *gh, int numcuts);
+
+
+static void flipvertarray(EditVert** arr, short size){
+    EditVert *hold;
+    int i;
+    
+    for(i=0;i<size/2;i++){
+        hold = arr[i];
+        arr[i] = arr[size-i-1];
+        arr[size-i-1] = hold;   
+    }
+}
+static void facecopy(EditFace *source,EditFace *target){
+    UVCOPY(target->tf.uv[0],source->tf.uv[0]);
+    UVCOPY(target->tf.uv[1],source->tf.uv[1]);
+    UVCOPY(target->tf.uv[2],source->tf.uv[2]);
+    UVCOPY(target->tf.uv[3],source->tf.uv[3]);
+
+	target->mat_nr     = source->mat_nr;
+	target->tf.flag    = source->tf.flag;
+	target->tf.transp  = source->tf.transp;
+	target->tf.mode    = source->tf.mode;
+	target->tf.tile    = source->tf.tile;
+	target->tf.unwrap  = source->tf.unwrap;
+	target->tf.tpage   = source->tf.tpage;
+	target->flag       = source->flag;    
+    
+}
+
+static void fill_quad_single(EditFace *efa, struct GHash *gh, int numcuts){
+       EditEdge *cedge;
+       EditVert *v[4], **verts;
+       EditFace *hold;
+       short start, end, left, right, vertsize,i;   
+                                
+       v[0] = efa->v1;
+       v[1] = efa->v2;
+       v[2] = efa->v3;
+       v[3] = efa->v4;     
+       
+       if(efa->e1->f & SELECT)      { cedge = efa->e1; start = 0;}
+       else if(efa->e2->f & SELECT) { cedge = efa->e2; start = 1;}       
+       else if(efa->e3->f & SELECT) { cedge = efa->e3; start = 2;}       
+       else if(efa->e4->f & SELECT) { cedge = efa->e4; start = 3;}         
+ 
+       // Point verts to the array of new verts for cedge
+       verts = BLI_ghash_lookup(gh, cedge);
+       //This is the index size of the verts array
+       vertsize = numcuts+2;
+       
+       // Is the original v1 the same as the first vert on the selected edge?
+       // if not, the edge is running the opposite direction in this face so flip
+       // the array to the correct direction
+       
+       if(verts[0] != v[start]){flipvertarray(verts,numcuts+2);}
+           end    = (start+1)%4;
+           left   = (start+2)%4;
+           right  = (start+3)%4; 
+               
+       /*
+       We should have something like this now
+       
+                  end         start                 
+                   3   2   1   0   
+                   |---*---*---|
+                   |           |
+                   |           |       
+                   |           |
+                   -------------       
+                  left       right
+
+        where start,end,left, right are indexes of EditFace->v1, etc (stored in v)
+        and 0,1,2... are the indexes of the new verts stored in verts
+        
+        We will fill this case like this or this depending on even or odd cuts
+         
+                   |---*---*---|          |---*---|
+                   |  /     \  |          |  / \  |
+                   | /       \ |          | /   \ |     
+                   |/         \|          |/     \|
+                   -------------          ---------  
+       */
+    
+        // Make center face
+        if(vertsize % 2 == 0){
+                hold = addfacelist(verts[(vertsize-1)/2],verts[((vertsize-1)/2)+1],v[left],v[right], NULL,NULL);
+        }else{
+                hold = addfacelist(verts[(vertsize-1)/2],v[left],v[right],NULL, NULL,NULL);            
+        }
+        facecopy(efa,hold);
+        
+        // Make side faces
+        for(i=0;i<(vertsize-1)/2;i++){
+                hold = addfacelist(verts[i],verts[i+1],v[right],NULL,NULL,NULL);  
+                facecopy(efa,hold);
+                hold = addfacelist(verts[vertsize-2-i],verts[vertsize-1-i],v[left],NULL,NULL,NULL); 
+                facecopy(efa,hold);
+        }      
+}
+
+static void fill_tri_single(EditFace *efa, struct GHash *gh, int numcuts){
+       EditEdge *cedge;
+       EditVert *v[3], **verts;
+       EditFace *hold;
+       short start, end, op, vertsize,i;   
+                                
+       v[0] = efa->v1;
+       v[1] = efa->v2;
+       v[2] = efa->v3;    
+       
+       if(efa->e1->f & SELECT)      { cedge = efa->e1; start = 0;}
+       else if(efa->e2->f & SELECT) { cedge = efa->e2; start = 1;}       
+       else if(efa->e3->f & SELECT) { cedge = efa->e3; start = 2;}         
+ 
+       // Point verts to the array of new verts for cedge
+       verts = BLI_ghash_lookup(gh, cedge);
+       //This is the index size of the verts array
+       vertsize = numcuts+2;
+       
+       // Is the original v1 the same as the first vert on the selected edge?
+       // if not, the edge is running the opposite direction in this face so flip
+       // the array to the correct direction
+       
+       if(verts[0] != v[start]){flipvertarray(verts,numcuts+2);}
+           end    = (start+1)%3;
+           op     = (start+2)%3;
+               
+       /*
+       We should have something like this now
+       
+                  end         start                 
+                   3   2   1   0   
+                   |---*---*---|
+                   \           |
+                     \         |       
+                       \       |
+                         \     |
+                           \   |
+                             \ |
+                               |op
+                               
+        where start,end,op are indexes of EditFace->v1, etc (stored in v)
+        and 0,1,2... are the indexes of the new verts stored in verts
+        
+        We will fill this case like this or this depending on even or odd cuts
+         
+                   3   2   1   0   
+                   |---*---*---|
+                   \    \  \   |
+                     \    \ \  |       
+                       \   \ \ |
+                         \  \ \|
+                           \ \\|
+                             \ |
+                               |op
+       */
+        
+        // Make side faces
+        for(i=0;i<(vertsize-1);i++){
+                hold = addfacelist(verts[i],verts[i+1],v[op],NULL,NULL,NULL);  
+                facecopy(efa,hold);
+        }      
+}
+
+static void fill_quad_double_op(EditFace *efa, struct GHash *gh, int numcuts){
+       EditEdge *cedge[2];
+       EditVert *v[4], **verts[2];
+       EditFace *hold;
+       short start, end, left, right, vertsize,i;
+                                
+       v[0] = efa->v1;
+       v[1] = efa->v2;
+       v[2] = efa->v3;
+       v[3] = efa->v4;     
+       
+       if(efa->e1->f & SELECT)      { cedge[0] = efa->e1;  cedge[1] = efa->e3; start = 0;}
+       else if(efa->e2->f & SELECT)      { cedge[0] = efa->e2;  cedge[1] = efa->e4; start = 1;}
+ 
+       // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
+       verts[0] = BLI_ghash_lookup(gh, cedge[0]);
+       verts[1] = BLI_ghash_lookup(gh, cedge[1]);
+       //This is the index size of the verts array
+       vertsize = numcuts+2;
+       
+       // Is the original v1 the same as the first vert on the selected edge?
+       // if not, the edge is running the opposite direction in this face so flip
+       // the array to the correct direction
+       
+       if(verts[0][0] != v[start]){flipvertarray(verts[0],numcuts+2);}
+           end    = (start+1)%4;
+           left   = (start+2)%4;
+           right  = (start+3)%4; 
+       if(verts[1][0] != v[left]){flipvertarray(verts[1],numcuts+2);}    
+       /*
+       We should have something like this now
+       
+                  end         start                 
+                   3   2   1   0   
+                   |---*---*---|
+                   |           |
+                   |           |       
+                   |           |
+                   |---*---*---|      
+                   0   1   2   3
+                  left       right
+        
+        We will fill this case like this or this depending on even or odd cuts
+         
+                   |---*---*---|
+                   |   |   |   |
+                   |   |   |   |       
+                   |   |   |   |
+                   |---*---*---| 
+       */
+           
+        // Make side faces
+        for(i=0;i<vertsize-1;i++){
+                hold = addfacelist(verts[0][i],verts[0][i+1],verts[1][vertsize-2-i],verts[1][vertsize-1-i],NULL,NULL);  
+                facecopy(efa,hold);
+        }      
+}
+
+
+static void fill_quad_double_adj(EditFace *efa, struct GHash *gh, int numcuts){
+       EditEdge *cedge[2];
+       EditVert *v[4], **verts[2];
+       EditFace *hold;
+       short start, start2, vertsize,i;
+                                
+       v[0] = efa->v1;
+       v[1] = efa->v2;
+       v[2] = efa->v3;
+       v[3] = efa->v4;     
+       
+       if(efa->e1->f & SELECT && efa->e2->f & SELECT) {cedge[0] = efa->e1;  cedge[1] = efa->e2; start = 0; start2 = 1;}
+       if(efa->e2->f & SELECT && efa->e3->f & SELECT) {cedge[0] = efa->e2;  cedge[1] = efa->e3; start = 1; start2 = 2;}
+       if(efa->e3->f & SELECT && efa->e4->f & SELECT) {cedge[0] = efa->e3;  cedge[1] = efa->e4; start = 2; start2 = 3;}
+       if(efa->e4->f & SELECT && efa->e1->f & SELECT) {cedge[0] = efa->e4;  cedge[1] = efa->e1; start = 3; start2 = 0;}
+ 
+       // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
+       verts[0] = BLI_ghash_lookup(gh, cedge[0]);
+       verts[1] = BLI_ghash_lookup(gh, cedge[1]);
+       //This is the index size of the verts array
+       vertsize = numcuts+2;
+       
+       // Is the original v1 the same as the first vert on the selected edge?
+       // if not, the edge is running the opposite direction in this face so flip
+       // the array to the correct direction
+       
+       if(verts[0][0] != v[start]){flipvertarray(verts[0],numcuts+2);}
+       if(verts[1][0] != v[start2]){flipvertarray(verts[1],numcuts+2);}    
+       /*
+       We should have something like this now
+       
+                   end         start                 
+                    3   2   1   0   
+            start2 0|---*---*---|
+                    |           |
+                   1*           |
+                    |           |
+                   2*           |       
+                    |           |
+             end2  3|-----------|   
+        
+        We will fill this case like this or this depending on even or odd cuts
+                   |---*---*---|
+                   | /   /   / |
+                   *   /   /   |
+                   | /   /     |
+                   *   /       |       
+                   | /         |
+                   |-----------|  
+     */
+
+        // Make outside tris
+        hold = addfacelist(verts[0][vertsize-2],verts[0][vertsize-1],verts[1][1],NULL,NULL,NULL);  
+        facecopy(efa,hold);       
+        hold = addfacelist(verts[0][0],verts[1][vertsize-1],v[(start2+2)%4],NULL,NULL,NULL);  
+        facecopy(efa,hold);               
+        // Make side faces
+
+        for(i=0;i<numcuts;i++){
+                hold = addfacelist(verts[0][i],verts[0][i+1],verts[1][vertsize-1-(i+1)],verts[1][vertsize-1-i],NULL,NULL);  
+                facecopy(efa,hold);
+        }      
+}
+
+static void fill_tri_double(EditFace *efa, struct GHash *gh, int numcuts){
+       EditEdge *cedge[2];
+       EditVert *v[3], **verts[2];
+       EditFace *hold;
+       short start, start2, vertsize,i;
+                                
+       v[0] = efa->v1;
+       v[1] = efa->v2;
+       v[2] = efa->v3;
+       
+       if(efa->e1->f & SELECT && efa->e2->f & SELECT) {cedge[0] = efa->e1;  cedge[1] = efa->e2; start = 0; start2 = 1;}
+       if(efa->e2->f & SELECT && efa->e3->f & SELECT) {cedge[0] = efa->e2;  cedge[1] = efa->e3; start = 1; start2 = 2;}
+       if(efa->e3->f & SELECT && efa->e1->f & SELECT) {cedge[0] = efa->e3;  cedge[1] = efa->e1; start = 2; start2 = 0;}
+ 
+       // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
+       verts[0] = BLI_ghash_lookup(gh, cedge[0]);
+       verts[1] = BLI_ghash_lookup(gh, cedge[1]);
+       //This is the index size of the verts array
+       vertsize = numcuts+2;
+       
+       // Is the original v1 the same as the first vert on the selected edge?
+       // if not, the edge is running the opposite direction in this face so flip
+       // the array to the correct direction
+       
+       if(verts[0][0] != v[start]){flipvertarray(verts[0],numcuts+2);}
+       if(verts[1][0] != v[start2]){flipvertarray(verts[1],numcuts+2);}    
+       /*
+       We should have something like this now
+       
+                   end         start                 
+                    3   2   1   0   
+            start2 0|---*---*---|
+                    |         /     
+                   1*       /        
+                    |     /         
+                   2*   /                 
+                    | /           
+             end2  3|  
+        
+        We will fill this case like this or this depending on even or odd cuts
+                   |---*---*---|
+                   | /   /   / 
+                   *   /   /   
+                   | /   /     
+                   *   /              
+                   | /         
+                   |
+     */
+
+        // Make outside tri
+        hold = addfacelist(verts[0][vertsize-2],verts[0][vertsize-1],verts[1][1],NULL,NULL,NULL);  
+        facecopy(efa,hold);              
+        // Make side faces
+
+        for(i=0;i<numcuts;i++){
+                hold = addfacelist(verts[0][i],verts[0][i+1],verts[1][vertsize-1-(i+1)],verts[1][vertsize-1-i],NULL,NULL);  
+                facecopy(efa,hold);
+        }      
+}
+
+static void fill_quad_triple(EditFace *efa, struct GHash *gh, int numcuts){
+       EditEdge *cedge[3];
+       EditVert *v[4], **verts[3];
+       EditFace *hold;
+       short start, start2, start3, vertsize, i, repeats;
+                                
+       v[0] = efa->v1;
+       v[1] = efa->v2;
+       v[2] = efa->v3;
+       v[3] = efa->v4;     
+           
+       if(!(efa->e1->f & SELECT)) {
+            cedge[0] = efa->e2;  
+            cedge[1] = efa->e3; 
+            cedge[2] = efa->e4;
+            start = 1;start2 = 2;start3 = 3;   
+       }
+       if(!(efa->e2->f & SELECT)) {
+            cedge[0] = efa->e3;  
+            cedge[1] = efa->e4; 
+            cedge[2] = efa->e1;
+            start = 2;start2 = 3;start3 = 0;   
+       }
+        if(!(efa->e3->f & SELECT)) {
+            cedge[0] = efa->e4;  
+            cedge[1] = efa->e1; 
+            cedge[2] = efa->e2;
+            start = 3;start2 = 0;start3 = 1;   
+       }
+       if(!(efa->e4->f & SELECT)) {
+            cedge[0] = efa->e1;  
+            cedge[1] = efa->e2; 
+            cedge[2] = efa->e3;
+            start = 0;start2 = 1;start3 = 2;   
+       }       
+       // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
+       verts[0] = BLI_ghash_lookup(gh, cedge[0]);
+       verts[1] = BLI_ghash_lookup(gh, cedge[1]);
+       verts[2] = BLI_ghash_lookup(gh, cedge[2]);
+       //This is the index size of the verts array
+       vertsize = numcuts+2;
+       
+       // Is the original v1 the same as the first vert on the selected edge?
+       // if not, the edge is running the opposite direction in this face so flip
+       // the array to the correct direction
+       
+       if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
+       if(verts[1][0] != v[start2]){flipvertarray(verts[1],numcuts+2);}  
+       if(verts[2][0] != v[start3]){flipvertarray(verts[2],numcuts+2);}   
+       /*
+       We should have something like this now
+       
+                              start2                 
+                    3   2   1   0   
+            start3 0|---*---*---|3 
+                    |           |
+                   1*           *2
+                    |           |
+                   2*           *1       
+                    |           |
+                   3|-----------|0 start   
+        
+        We will fill this case like this or this depending on even or odd cuts  
+        there are a couple of differences. For odd cuts, there is a tri in the
+        middle as well as 1 quad at the bottom (not including the extra quads
+        for odd cuts > 1          
+        
+        For even cuts, there is a quad in the middle and 2 quads on the bottom
+        
+        they are numbered here for clarity
+        
+        1 outer tris and bottom quads
+        2 inner tri or quad
+        3 repeating quads
+        
+                   |---*---*---*---|
+                   |1/   /  \   \ 1|
+                   |/ 3 /    \  3 \|
+                   *  /    2   \   *
+                   | /          \  |
+                   |/            \ | 
+                   *---------------*
+                   |      3        |
+                   |               |  
+                   *---------------*
+                   |               |
+                   |      1        |                  
+                   |               |
+                   |---------------|
+
+                   |---*---*---*---*---|
+                   | 1/   /     \   \ 1|   
+                   | /   /       \   \ |  
+                   |/ 3 /         \ 3 \|
+                   *   /           \   *
+                   |  /             \  |    
+                   | /       2       \ |   
+                   |/                 \|
+                   *-------------------*
+                   |                   |
+                   |         3         |
+                   |                   | 
+                   *-------------------*
+                   |                   |
+                   |         1         |
+                   |                   | 
+                   *-------------------*
+                   |                   |
+                   |        1          |
+                   |                   | 
+                   |-------------------|
+          
+     */
+
+        // Make outside tris
+        hold = addfacelist(verts[0][vertsize-2],verts[0][vertsize-1],verts[1][1],NULL,NULL,NULL);  
+        facecopy(efa,hold);      
+        hold = addfacelist(verts[1][vertsize-2],verts[1][vertsize-1],verts[2][1],NULL,NULL,NULL);  
+        facecopy(efa,hold);              
+        // Make bottom quad
+        hold = addfacelist(verts[0][0],verts[0][1],verts[2][vertsize-2],verts[2][vertsize-1],NULL,NULL);  
+        facecopy(efa,hold);         
+        //If it is even cuts, add the 2nd lower quad
+        if(numcuts % 2 == 0){
+            hold = addfacelist(verts[0][1],verts[0][2],verts[2][vertsize-3],verts[2][vertsize-2],NULL,NULL);  
+            facecopy(efa,hold);         
+            // Also Make inner quad
+            hold = addfacelist(verts[1][numcuts/2],verts[1][(numcuts/2)+1],verts[2][numcuts/2],verts[0][(numcuts/2)+1],NULL,NULL);           
+            facecopy(efa,hold);
+            repeats = (numcuts / 2) -1;
+        } else {
+            // Make inner tri     
+            hold = addfacelist(verts[1][(numcuts/2)+1],verts[2][(numcuts/2)+1],verts[0][(numcuts/2)+1],NULL,NULL,NULL);           
+            facecopy(efa,hold);   
+            repeats = ((numcuts+1) / 2)-1;
+        }
+        
+        // cuts for 1 and 2 do not have the repeating quads
+        if(numcuts < 3){repeats = 0;}
+        for(i=0;i<repeats;i++){
+            //Make side repeating Quads
+            hold = addfacelist(verts[1][i+1],verts[1][i+2],verts[0][vertsize-i-3],verts[0][vertsize-i-2],NULL,NULL);           
+            facecopy(efa,hold);               
+            hold = addfacelist(verts[1][vertsize-i-3],verts[1][vertsize-i-2],verts[2][i+1],verts[2][i+2],NULL,NULL);           
+            facecopy(efa,hold); 
+        }
+        // Do repeating bottom quads 
+        for(i=0;i<repeats;i++){
+            if(numcuts % 2 == 1){     
+                hold = addfacelist(verts[0][1+i],verts[0][2+i],verts[2][vertsize-3-i],verts[2][vertsize-2-i],NULL,NULL);  
+            } else {
+                hold = addfacelist(verts[0][2+i],verts[0][3+i],verts[2][vertsize-4-i],verts[2][vertsize-3-i],NULL,NULL);                  
+            }
+            facecopy(efa,hold);                
+        }    
+}
+
+static void fill_quad_quadruple(EditFace *efa, struct GHash *gh, int numcuts){
+       EditVert **verts[4], ***innerverts;
+       short vertsize, i, j;
+       float co[3];     
+       EditVert *ev;               
+       EditFace *hold;      
+       // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
+       verts[0] = BLI_ghash_lookup(gh, efa->e1);
+       verts[1] = BLI_ghash_lookup(gh, efa->e2);
+       verts[2] = BLI_ghash_lookup(gh, efa->e3);
+       verts[3] = BLI_ghash_lookup(gh, efa->e4);
+       
+       //This is the index size of the verts array
+       vertsize = numcuts+2;
+       
+       // Is the original v1 the same as the first vert on the selected edge?
+       // if not, the edge is running the opposite direction in this face so flip
+       // the array to the correct direction
+       
+       if(verts[0][0] != efa->v1) {flipvertarray(verts[0],numcuts+2);}
+       if(verts[1][0] != efa->v2) {flipvertarray(verts[1],numcuts+2);}  
+       if(verts[2][0] == efa->v3) {flipvertarray(verts[2],numcuts+2);}
+       if(verts[3][0] == efa->v4) {flipvertarray(verts[3],numcuts+2);}     
+       /*
+       We should have something like this now
+                          1
+                                              
+                    3   2   1   0   
+                   0|---*---*---|0 
+                    |           |
+                   1*           *1
+             2      |           |      4
+                   2*           *2       
+                    |           |
+                   3|---*---*---|3    
+                    3   2   1   0
+        
+                          3
+    // we will fill a 2 dim array of editvert*s to make filling easier
+    //  the innervert order is shown
+
+                0   0---1---2---3 
+                    |   |   |   |
+                1   0---1---2---3 
+                    |   |   |   |
+                2   0---1---2---3        
+                    |   |   |   |
+                3   0---1---2---3  
+          
+     */
+    innerverts = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"quad-quad subdiv inner verts outer array"); 
+    for(i=0;i<numcuts+2;i++){
+          innerverts[i] = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"quad-quad subdiv inner verts inner array");
+    }   
+    // first row is e1 last row is e3
+    for(i=0;i<numcuts+2;i++){
+          innerverts[0][i]          = verts[0][(numcuts+1)-i];
+          innerverts[numcuts+1][i]  = verts[2][(numcuts+1)-i];
+    }           
+    for(i=1;i<=numcuts;i++){
+        innerverts[i][0]          = verts[1][i];
+        innerverts[i][numcuts+1]  = verts[3][i];
+        for(j=1;j<=numcuts;j++){ 
+             co[0] = ((verts[1][i]->co[0] - verts[3][i]->co[0]) * (j /(float)(numcuts+1))) + verts[3][i]->co[0];
+             co[1] = ((verts[1][i]->co[1] - verts[3][i]->co[1]) * (j /(float)(numcuts+1))) + verts[3][i]->co[1];
+             co[2] = ((verts[1][i]->co[2] - verts[3][i]->co[2]) * (j /(float)(numcuts+1))) + verts[3][i]->co[2];
+             innerverts[i][(numcuts+1)-j] = addvertlist(co);               
+             innerindex++;
+        }    
+    }    
+    // Fill with faces
+    for(i=0;i<numcuts+1;i++){
+        for(j=0;j<numcuts+1;j++){
+            hold = addfacelist(innerverts[i][j+1],innerverts[i][j],innerverts[i+1][j],innerverts[i+1][j+1],NULL,NULL);           
+            facecopy(efa,hold);             
+        }        
+    }
+    // Clean up our dynamic multi-dim array
+    for(i=0;i<numcuts+2;i++){
+       MEM_freeN(innerverts[i]);   
+    }    
+    MEM_freeN(innerverts);
+}
+
+static void fill_tri_triple(EditFace *efa, struct GHash *gh, int numcuts){
+       EditVert **verts[3], ***innerverts;
+       short vertsize, i, j;
+       float co[3];     
+       EditVert *ev;               
+       EditFace *hold;      
+       // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
+       verts[0] = BLI_ghash_lookup(gh, efa->e1);
+       verts[1] = BLI_ghash_lookup(gh, efa->e2);
+       verts[2] = BLI_ghash_lookup(gh, efa->e3);
+       
+       //This is the index size of the verts array
+       vertsize = numcuts+2;
+       
+       // Is the original v1 the same as the first vert on the selected edge?
+       // if not, the edge is running the opposite direction in this face so flip
+       // the array to the correct direction
+       
+       if(verts[0][0] != efa->v1) {flipvertarray(verts[0],numcuts+2);}
+       if(verts[1][0] != efa->v2) {flipvertarray(verts[1],numcuts+2);}  
+       if(verts[2][0] != efa->v3) {flipvertarray(verts[2],numcuts+2);}   
+       /*
+       We should have something like this now
+                           3
+                                              
+                    3   2   1   0   
+                   0|---*---*---|3 
+                    |          /    
+              1    1*        *2   
+                    |      /      
+                   2*    *1       2         
+                    |  /           
+                   3|/ 
+                     0
+        
+     we will fill a 2 dim array of editvert*s to make filling easier
+
+                            3
+
+                 0  0---1---2---3---4
+                    | / | /  |/  | /    
+                 1  0---1----2---3 
+           1        | /  | / | /    
+                 2  0----1---2     2
+                    |  / |  /       
+                    |/   |/   
+                 3  0---1 
+                    |  /
+                    |/
+                 4  0  
+          
+     */
+    
+    innerverts = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"tri-tri subdiv inner verts outer array"); 
+    for(i=0;i<numcuts+2;i++){
+          innerverts[i] = MEM_mallocN(sizeof(EditVert*)*((numcuts+2)-i),"tri-tri subdiv inner verts inner array");
+    }
+    //top row is e3 backwards
+    for(i=0;i<numcuts+2;i++){
+          innerverts[0][i]          = verts[2][(numcuts+1)-i];
+    }   
+           
+    for(i=1;i<=numcuts+1;i++){
+        //first vert is from e1, last is from e2
+        innerverts[i][0]              = verts[0][i];
+        innerverts[i][(numcuts+1)-i]  = verts[1][(numcuts+1)-i];        
+        for(j=1;j<(numcuts+1)-i;j++){
+             co[0] = ((verts[0][i]->co[0] - verts[1][(numcuts+1)-i]->co[0]) * (j/(float)((numcuts+1)-i))) + verts[1][(numcuts+1)-i]->co[0];
+             co[1] = ((verts[0][i]->co[1] - verts[1][(numcuts+1)-i]->co[1]) * (j/(float)((numcuts+1)-i))) + verts[1][(numcuts+1)-i]->co[1];
+             co[2] = ((verts[0][i]->co[2] - verts[1][(numcuts+1)-i]->co[2]) * (j/(float)((numcuts+1)-i))) + verts[1][(numcuts+1)-i]->co[2];
+             innerverts[i][((numcuts+1)-i)-j] = addvertlist(co);               
+             innerindex++;          
+        }
+    }
+    // Now fill the verts with happy little tris :)
+    for(i=0;i<=numcuts+1;i++){
+        for(j=0;j<(numcuts+1)-i;j++){   
+            //We always do the first tri
+            hold = addfacelist(innerverts[i][j+1],innerverts[i][j],innerverts[i+1][j],NULL,NULL,NULL);           
+            facecopy(efa,hold);         
+            //if there are more to come, we do the 2nd     
+            if(j+1 <= numcuts-i){
+                hold = addfacelist(innerverts[i+1][j],innerverts[i+1][j+1],innerverts[i][j+1],NULL,NULL,NULL);           
+                facecopy(efa,hold); 
+           }
+        } 
+    }
+    
+    // Clean up our dynamic multi-dim array
+    for(i=0;i<numcuts+2;i++){
+       MEM_freeN(innerverts[i]);   
+    }    
+    MEM_freeN(innerverts);
+}
+
+// This function takes an example edge, the current point to create and 
+// the total # of points to create, then creates the point and return the
+// editvert pointer to it.
+static EditVert *subdivideedgenum(EditEdge *edge,int curpoint,int totpoint){
+         float co[3];     
+         EditVert *ev;
+         co[0] = (edge->v2->co[0]-edge->v1->co[0])*(curpoint/(float)(totpoint+1))+edge->v1->co[0];
+         co[1] = (edge->v2->co[1]-edge->v1->co[1])*(curpoint/(float)(totpoint+1))+edge->v1->co[1];
+         co[2] = (edge->v2->co[2]-edge->v1->co[2])*(curpoint/(float)(totpoint+1))+edge->v1->co[2];
+
+         ev = addvertlist(co);
+         //ev->f = 0;
+         return ev;
+}
+
+/*
+static void edgecopy(EditEdge *source, EditEdge *target){
+    target->crease = source->crease;
+    target->h     = source->h;
+    target->dir   = source->dir;
+    target->seam  = source->seam;
+}*/
+
+void esubdivideflag(int flag, float rad, int beauty, int numcuts)
+{
+    EditMesh *em = G.editMesh;
+    EditFace *ef;
+    EditEdge *eed, *cedge;
+    EditVert **templist;
+    struct GHash *gh;
+    int i,edgecount,facetype;
+    short cuttype=0;
+
+    //Set faces f1 to 0 cause we need it later
+        	
+    for(ef=em->faces.first;ef;ef = ef->next){
+        ef->f1 = 0;
+    }
+    
+    // We store an array of verts for each edge that is subdivided,
+    // we put this array as a value in a ghash which is keyed by the EditEdge*
+    
+    gh = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp); 
+    
+    
+    // So for each edge, if it is selected, we allocate an array of size cuts+2
+    // so we can have a place for the v1, the new verts and v2  
+    for(eed=em->edges.first;eed;eed = eed->next){
+         if(eed->f & SELECT){
+              templist = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"vertlist");
+              templist[0] = eed->v1;
+              for(i=0;i<numcuts;i++){
+                  // This function creates the new vert and returns it back
+                  // to the array
+                  templist[i+1] = subdivideedgenum(eed,i+1,numcuts);
+                  
+                  //while we are here, we can copy edge info from the original edge
+                  cedge = addedgelist(templist[i],templist[i+1],eed);
+                  cedge->f2 = EDGENEW;
+              }
+              templist[i+1] = eed->v2;
+              //Do the last edge too
+              cedge = addedgelist(templist[i],templist[i+1],eed);
+              cedge->f2 = EDGENEW;
+              // Now that the edge is subdivided, we can put its verts in the ghash 
+              BLI_ghash_insert(gh, eed, templist);               
+          }                                  
+    }
+ 
+    // Now for each face in the mesh we need to figure out How many edges were cut
+    // and which filling method to use for that face
+ 
+    for(ef = em->faces.first;ef;ef = ef->next){
+           edgecount = 0;
+           facetype = 3;
+           if(ef->e1->f & SELECT) {edgecount++;}
+           if(ef->e2->f & SELECT) {edgecount++;}
+           if(ef->e3->f & SELECT) {edgecount++;}
+           if(ef->v4){
+               facetype = 4;
+               if(ef->e4->f & SELECT){edgecount++;}
+           }  
+           printf("facetype - %d, edgecount - %d\n",facetype,edgecount);
+           if(facetype == 4){
+                   switch(edgecount){
+                       case 0: break;
+                       case 1: ef->f1 = SELECT;
+                               fill_quad_single(ef, gh, numcuts);
+                               break;   
+                       case 2: ef->f1 = SELECT;
+                               // if there are 2, we check if edge 1 and 3 are either both on or off that way
+                               // we can tell if the selected pair is Adjacent or Opposite of each other
+                               if((ef->e1->f & SELECT && ef->e3->f & SELECT) || 
+                                  (ef->e2->f & SELECT && ef->e4->f & SELECT)){
+                                    printf("op\n");
+                                    fill_quad_double_op(ef, gh, numcuts);                              
+                               }else{
+                                    printf("adj\n");
+                                    fill_quad_double_adj(ef, gh, numcuts);                          
+                               }
+                               break;    
+                       case 3: ef->f1 = SELECT;
+                               fill_quad_triple(ef, gh, numcuts); 
+                               break;    
+                       case 4: ef->f1 = SELECT;
+                               fill_quad_quadruple(ef, gh, numcuts); 
+                               break;    
+                   }
+            } else {
+                   switch(edgecount){
+                       case 0: break;
+                       case 1: ef->f1 = SELECT;
+                               fill_tri_single(ef, gh, numcuts);
+                               break;   
+                       case 2: ef->f1 = SELECT;
+                               fill_tri_double(ef, gh, numcuts);
+                               break;    
+                       case 3: ef->f1 = SELECT;
+                               fill_tri_triple(ef, gh, numcuts);
+                               break;  
+                   }    
+            }    
+    }
+ 
+ 
+    // Delete Old Faces
+    free_tagged_facelist(em->faces.first);     
+    //Delete Old Edges
+    for(eed = em->edges.first;eed;eed = eed->next){
+        if(BLI_ghash_haskey(gh,eed)){
+             eed->f1 = SELECT; 
+        } else {
+             eed->f1 = 0;   
+        }
+    } 
+    free_tagged_edgelist(em->edges.first); 
+    
+    for(eed = em->edges.first;eed;eed = eed->next){
+        if(eed->f2 & EDGENEW){
+            eed->f |= SELECT;   
+        }
+    }    
+       
+    // Free the ghash and call MEM_freeN on all the value entries to return 
+    // that memory
+    BLI_ghash_free(gh, NULL, MEM_freeN);   
+     
+	/* since this is all on vertex level, flush vertex selection */
+	//EM_select_flush();
+	recalc_editnormals();
+	
+	countall();
+	allqueue(REDRAWVIEW3D, 0);
+	makeDispList(G.obedit); 
+}
+
+
 
 static int count_selected_edges(EditEdge *ed)
 {
Index: source/blender/src/editobject.c
===================================================================
RCS file: /cvsroot/bf-blender/blender/source/blender/src/editobject.c,v
retrieving revision 1.188
diff -u -r1.188 editobject.c
--- source/blender/src/editobject.c	12 May 2005 19:17:12 -0000	1.188
+++ source/blender/src/editobject.c	6 Jun 2005 05:15:59 -0000
@@ -1895,7 +1895,7 @@
 	extern float doublimit;
 	float fac;
 	int nr,ret;
-	short randfac;
+	short randfac,numcuts;
 	
 	if(G.obedit==0) {
 		if(G.f & G_FACESELECT) {
@@ -2008,9 +2008,9 @@
 		}
 	}
 	else if(G.obedit->type==OB_MESH) {
-
-		nr= pupmenu("Specials%t|Subdivide%x1|Subdivide Fractal%x2|Subdivide Smooth%x3|Merge%x4|Remove Doubles%x5|Hide%x6|Reveal%x7|Select Swap%x8|Flip Normals %x9|Smooth %x10|Bevel %x11");
-		if(nr>0) waitcursor(1);
+        
+		nr= pupmenu("Specials%t|E-Subdivide%x12|Subdivide%x1|Subdivide Fractal%x2|Subdivide Smooth%x3|Merge%x4|Remove Doubles%x5|Hide%x6|Reveal%x7|Select Swap%x8|Flip Normals %x9|Smooth %x10|Bevel %x11");
+		//if(nr>0) waitcursor(1);
 		
 		switch(nr) {
 		case 1:
@@ -2053,6 +2053,14 @@
 			break;
 		case 11:
 			bevel_menu();
+			break;
+		case 12:
+            numcuts = 1;
+            if(button(&numcuts, 1, 128, "Number of Cuts:")==0) return;
+			waitcursor(1);
+            esubdivideflag(1, 0.0, editbutflag,numcuts);
+			
+			BIF_undo_push("ESubdivide");
 			break;
 		}		
 		


More information about the Bf-committers mailing list