[Bf-committers] Updated: Knife subdivide patch
Ton Roosendaal
ton at blender.org
Sat Mar 5 16:53:23 CET 2005
Hi,
No time for review, but do have time to give you more work! :)
https://projects.blender.org/tracker/index.php?
func=detail&aid=2201&group_id=9&atid=125
Could you check on bug 2201?
-Ton-
On 4 Mar, 2005, at 23:54, Matthew H. Plough wrote:
> Well, that was extremely unintelligent. There is a huge discussion
> going on about an off-by-one error, and I had one in my code. :-[
>
> This line -- + curve=(CutFloat
> *)MEM_callocN((len)*sizeof(CutFloat), "PerspCut");
> needs to read + curve=(CutFloat
> *)MEM_callocN((len+1)*sizeof(CutFloat), "PerspCut");
>
> The real code is attached. I promise it's good.
>
> Matt
>
> Matthew H. Plough wrote:
>
> 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.
>
> 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:45:29 -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+1)*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
> ******************************************* */
>
> _______________________________________________
> Bf-committers mailing list
> Bf-committers at projects.blender.org
> http://projects.blender.org/mailman/listinfo/bf-committers
>
------------------------------------------------------------------------
--
Ton Roosendaal Blender Foundation ton at blender.org
http://www.blender.org
More information about the Bf-committers
mailing list