[Bf-committers] Perspective mode knife subdivide patch

[Matthew H. Plough]

Hooray!  After ages and eons (and a bit of a graphics course), I've 
finally fixed the incorrect knife subdivide functionality in perspective 
mode.  I've attached a patch.

I created the patch file with this command:

Administrator at mplough /cygdrive/c/projects/bfblender/blender
$ cvs diff -u source/blender/src/editmesh_loop.c >patch_file

Matt
-------------- next part --------------
Index: source/blender/src/editmesh_loop.c
===================================================================
RCS file: /cvsroot/bf-blender/blender/source/blender/src/editmesh_loop.c,v
retrieving revision 1.11
diff -u -r1.11 editmesh_loop.c
--- source/blender/src/editmesh_loop.c	28 Dec 2004 05:38:56 -0000	1.11
+++ source/blender/src/editmesh_loop.c	27 Feb 2005 22:54:19 -0000
@@ -540,15 +540,17 @@
 
 /* prototype */
 short seg_intersect(struct EditEdge * e, CutCurve *c, int len);
+short persp_intersect(EditEdge *e, CutCurve *c, int len);
+float line_band_intersect(float p0[3], float p1[3], float r0[3], float r1[3], float r2[3]);
 
 void KnifeSubdivide(char mode)
 {
 	EditMesh *em = G.editMesh;
 	int oldcursor, len=0;
 	short isect=0;
-	CutCurve *curve;		
-	EditEdge *eed; 
-	Window *win;	
+	CutCurve *curve;
+	EditEdge *eed;
+	Window *win;
 	
 	if (G.obedit==0) return;
 
@@ -560,7 +562,7 @@
 	if (mode==KNIFE_PROMPT) {
 		short val= pupmenu("Cut Type %t|Exact Line%x1|Midpoints%x2");
 		if(val<1) return;
-		mode= val;	// warning, mode is char, pupmenu returns -1 with ESC
+		mode= val;	/* warning, mode is char, pupmenu returns -1 with ESC */
 	}
 
 	calc_meshverts_ext();  /*Update screen coords for current window */
@@ -575,14 +577,15 @@
 	curve=get_mouse_trail(&len, TRAIL_MIXED);
 	
 	if (curve && len && mode){
-		eed= em->edges.first;		
-		while(eed) {	
+		eed= em->edges.first;
+		while(eed) {
 			if( eed->f & SELECT ){
-				isect=seg_intersect(eed, curve, len);
+				if(!G.vd->persp) isect=seg_intersect(eed, curve, len);
+				else isect= persp_intersect(eed, curve, len);
 				if (isect) eed->f2= 1;
 				else eed->f2=0;
 				eed->f1= isect;
-				//printf("isect=%i\n", isect);
+				/*printf("isect=%i\n", isect);*/
 			}
 			else {
 				eed->f2=0;
@@ -717,6 +720,124 @@
 	}
 	return(isect);
 } 
+
+/**
+ * persp_intersect
+ *
+ * Performs the function of seg_intersect when the view is in perspective mode
+*/
+
+short persp_intersect(EditEdge *e, CutCurve *c, int len) {
+	short isect;
+	int i;
+	float perc;
+	float ray1[3], ray2[3];
+	float eye[3], mat[3][3], imat[3][3], vec[4], vec_s[2];
+	
+	isect=0;
+
+	initgrabz(0,0,0);
+
+	/* all points need to be transformed to object space */
+	Mat3CpyMat4(mat, G.obedit->obmat);
+	Mat3Inv(imat, mat);
+
+	VecCopyf(eye, G.vd->viewinv[3]);
+	VecSubf(eye, eye, G.obedit->obmat[3]);
+	Mat3MulVecfl(imat, eye);
+	
+	vec[0]=vec[1]=vec[2]=0.0;
+	vec[3]=1.0;
+	project_float(vec, vec_s);
+	
+	window_to_3d(ray1, c[0].x - vec_s[0], c[0].y - vec_s[1]);
+	VecSubf(ray1, ray1, G.obedit->obmat[3]);
+	Mat3MulVecfl(imat, ray1);
+	
+	for(i=1; i<len; i++) {
+		window_to_3d(ray2, c[i].x - vec_s[0], c[i].y - vec_s[1]);
+		/* and transform to object space... */
+		VecSubf(ray2, ray2, G.obedit->obmat[3]);
+		Mat3MulVecfl(imat, ray2);
+		perc = line_band_intersect(e->v1->co, e->v2->co, eye, ray1, ray2);
+		if(perc >= 0) {
+			isect=32768.0*(perc+0.0000153); /* Percentage in 1/32768ths */
+			break;
+		}
+		VecCopyf(ray1, ray2);
+	}
+	return isect;
+}
+
+
+#define EPSILON (1e-6)
+
+/**
+ * line_band_intersect
+ *
+ * A modified line-plane intersect.  Checks to see if line intersects plane
+ * and checks if the intersection point lies between two rays in the plane.
+ *
+ * p0, p1 -- points on line
+ * r0 -- origin of two rays that define the plane
+ * r1, r2 -- points along the two rays
+ *
+ * Returns negative if intersect does not occur.
+ * Else returns the percentage of the way from p0 to p1 where intersection occurs
+**/
+
+
+float line_band_intersect(float p0[3], float p1[3], float r0[3], float r1[3], float r2[3]) {
+	float ray1[3], ray2[3], pnor[3], linedir[3], v[3], pI[3];
+	float t; /* 0 <= t <= 1 for intersection to occur on segment */
+	float res1, res2, cross1[3], cross2[3], in1[3], in2[3];
+
+	/* calculate plane normal of unit length */
+	VecSubf(ray1, r1, r0);
+	VecSubf(ray2, r2, r0);
+	Crossf(pnor, ray1, ray2);
+	Normalise(pnor); 
+	
+	/* http://softsurfer.com/Archive/algorithm_0105/algorithm_0105.htm 
+		describes a nice algorithm that uses only dot products. */
+	
+	VecSubf(linedir, p1, p0); /* don't normalize! */
+	t = Inpf(pnor, linedir);
+	
+	/* t could be negative -- careful! */
+	if(fabs(t) <= EPSILON) /* plane and line are parallel */
+		return -1.0f;
+	
+	VecSubf(v, r0, p0);
+	t = Inpf(pnor, v) / t;
+
+	if(t <= 0.0 || t >= 1.0) /* not in the segment */
+		return -1.0f;
+
+	
+	VecMulf(linedir, t);
+	VecAddf(pI, p0, linedir);
+	
+	VecSubf(cross1, r1, r0);
+	VecSubf(cross2, pI, r1);
+	Crossf(in1, cross1, cross2);
+	Normalise(in1);
+	res1 = Inpf(pnor, in1);
+	
+	
+	VecSubf(cross1, r2, r0);
+	VecSubf(cross2, pI, r2);
+	Crossf(in2, cross1, cross2);
+	Normalise(in2);
+	res2 = Inpf(pnor, in2);
+	
+	printf("%.2f, %.2f\n", res1, res2);
+	
+	if((res1 > 0 && res2 < 0) || (res1 < 0 && res2 > 0))
+		return t;
+	return -1.0f;
+}
+#undef EPSILON
 
 /* ******************** LOOP ******************************************* */