[Bf-committers] Updated: Knife subdivide patch
Matthew H. Plough
mplough at Princeton.EDU
Fri Mar 4 23:09:15 CET 2005
Hi everyone,
I have factored a lot of the math out of my subdivide patch; I have
tested it, and believe that it is stable enough for inclusion. If
anyone knows if any of the math can be eliminated completely, I'd be
very happy to know about it.
The updated patch is attached
Best regards,
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 4 Mar 2005 22:00:12 -0000
@@ -400,6 +400,10 @@
short y;
} CutCurve;
+typedef struct CutFloat {
+ float co[3];
+} CutFloat;
+
CutCurve *get_mouse_trail(int *len, char mode){
CutCurve *curve,*temp;
@@ -540,15 +544,19 @@
/* prototype */
short seg_intersect(struct EditEdge * e, CutCurve *c, int len);
+CutFloat *persp_cut_init(CutCurve *c, int len);
+short persp_intersect(EditEdge *e, CutFloat *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;
+ CutFloat *curve_f = 1;
+ EditEdge *eed;
+ Window *win;
if (G.obedit==0) return;
@@ -560,7 +568,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 */
@@ -573,16 +581,19 @@
SetBlenderCursor(BC_KNIFECURSOR);
curve=get_mouse_trail(&len, TRAIL_MIXED);
+
+ if(G.vd->persp) curve_f = persp_cut_init(curve, len);
- if (curve && len && mode){
- eed= em->edges.first;
- while(eed) {
+ if (curve && curve_f && len && mode){
+ 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_f, len+1);
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;
@@ -606,6 +617,7 @@
addqueue(curarea->win, REDRAW, 0);
window_set_cursor(win, oldcursor);
if (curve) MEM_freeN(curve);
+ if (curve_f && G.vd->persp) MEM_freeN(curve_f);
BIF_undo_push("Knife");
}
@@ -717,6 +729,131 @@
}
return(isect);
}
+
+/**
+ * persp_cut_init
+ *
+ * Factored out transformations of CutCurve to improve performance
+ * The eye is placed as the first coordinate in the CutFloat
+ * to eliminate multiple matrix inversions
+*/
+
+CutFloat *persp_cut_init(CutCurve *c, int len) {
+ int i;
+ CutFloat *curve;
+ float mat[3][3], imat[3][3], vec[4], vec_s[2];
+
+ curve=(CutFloat *)MEM_callocN(len*sizeof(CutFloat), "PerspCut");
+
+ if (!curve) {
+ printf("failed to allocate memory in get_mouse_trail()\n");
+ return(NULL);
+ }
+
+ initgrabz(0,0,0);
+
+ /* all points need to be transformed to object space */
+ Mat3CpyMat4(mat, G.obedit->obmat);
+ Mat3Inv(imat, mat);
+
+ VecCopyf(curve[0].co, G.vd->viewinv[3]);
+ VecSubf(curve[0].co, curve[0].co, G.obedit->obmat[3]);
+ Mat3MulVecfl(imat, curve[0].co);
+
+ vec[0]=vec[1]=vec[2]=0.0;
+ vec[3]=1.0;
+ project_float(vec, vec_s);
+
+ for(i=1; i<len+1; i++) {
+ window_to_3d(curve[i].co, c[i].x - vec_s[0], c[i].y - vec_s[1]);
+ VecSubf(curve[i].co, curve[i].co, G.obedit->obmat[3]);
+ Mat3MulVecfl(imat, curve[i].co);
+ }
+
+ return curve;
+}
+
+/**
+ * persp_intersect
+ *
+ * Performs the function of seg_intersect when the view is in perspective mode
+*/
+
+short persp_intersect(EditEdge *e, CutFloat *c, int len) {
+ int i;
+ float perc;
+
+ for(i=2; i<len; i++) {
+ perc = line_band_intersect(e->v1->co, e->v2->co, c[0].co, c[i-1].co, c[i].co);
+ if(perc >= 0)
+ return (short)(32768.0*(perc+0.0000153)); /* Percentage in 1/32768ths */
+ }
+ return 0;
+}
+
+
+#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);
+ res1 = Inpf(pnor, in1);
+
+ VecSubf(cross1, r2, r0);
+ VecSubf(cross2, pI, r2);
+ Crossf(in2, cross1, cross2);
+ res2 = Inpf(pnor, in2);
+
+ if((res1 > 0 && res2 < 0) || (res1 < 0 && res2 > 0))
+ return t;
+ return -1.0f;
+}
+#undef EPSILON
/* ******************** LOOP ******************************************* */
More information about the Bf-committers
mailing list