fix for lasso failing/glitches on overlapping lines, replace scanfill with 2d pixel filling for drawing and selection.

6 files changed, 149 insertions, 123 deletions

diff --git a/source/blender/blenlib/BLI_math_geom.h b/source/blender/blenlib/BLI_math_geom.h
index c7ef410a606..9f837c25a73 100644
--- a/source/blender/blenlib/BLI_math_geom.h
+++ b/source/blender/blenlib/BLI_math_geom.h
@@ -188,7 +188,10 @@ bool clip_segment_v3_plane(float p1[3], float p2[3], const float plane[4]);
 bool clip_segment_v3_plane_n(float p1[3], float p2[3], float plane_array[][4], const int plane_tot);
 
 void plot_line_v2v2i(const int p1[2], const int p2[2], bool (*callback)(int, int, void *), void *userData);
-
+void fill_poly_v2i_n(
+        const int xmin, const int ymin, const int xmax, const int ymax,
+        const int polyXY[][2], const int polyCorners,
+        void (*callback)(int, int, void *), void *userData);
 /****************************** Interpolation ********************************/
 
 /* tri or quad, d can be NULL */
diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c
index e45714f33da..ce36d1f9fc3 100644
--- a/source/blender/blenlib/intern/math_geom.c
+++ b/source/blender/blenlib/intern/math_geom.c
@@ -1997,6 +1997,59 @@ void plot_line_v2v2i(const int p1[2], const int p2[2], bool (*callback)(int, int
 	}
 }
 
+void fill_poly_v2i_n(
+        const int xmin, const int ymin, const int xmax, const int ymax,
+        const int verts[][2], const int nr,
+        void (*callback)(int, int, void *), void *userData)
+{
+	/* originally by Darel Rex Finley, 2007 */
+
+	int  nodes, pixel_y, i, j, swap;
+	int *node_x = MEM_mallocN(sizeof(*node_x) * (nr + 1), __func__);
+
+	/* Loop through the rows of the image. */
+	for (pixel_y = ymin; pixel_y < ymax; pixel_y++) {
+
+		/* Build a list of nodes. */
+		nodes = 0; j = nr - 1;
+		for (i=0; i<nr; i++) {
+			if ((verts[i][1] < pixel_y && verts[j][1] >= pixel_y) ||
+			    (verts[j][1] < pixel_y && verts[i][1] >= pixel_y))
+			{
+				node_x[nodes++] = (int)(verts[i][0] +
+				                        ((double)(pixel_y - verts[i][1]) / (verts[j][1] - verts[i][1])) *
+				                        (verts[j][0] - verts[i][0]));
+			}
+			j = i;
+		}
+
+		/* Sort the nodes, via a simple "Bubble" sort. */
+		i = 0;
+		while (i < nodes - 1) {
+			if (node_x[i] > node_x[i + 1]) {
+				SWAP_TVAL(swap, node_x[i], node_x[i + 1]);
+				if (i) i--;
+			}
+			else {
+				i++;
+			}
+		}
+
+		/* Fill the pixels between node pairs. */
+		for (i = 0; i < nodes; i += 2) {
+			if (node_x[i] >= xmax) break;
+			if (node_x[i + 1] >  xmin) {
+				if (node_x[i    ] < xmin) node_x[i    ] = xmin;
+				if (node_x[i + 1] > xmax) node_x[i + 1] = xmax;
+				for (j = node_x[i]; j < node_x[i + 1]; j++) {
+					callback(j - xmin, pixel_y - ymin, userData);
+				}
+			}
+		}
+	}
+	MEM_freeN(node_x);
+}
+
 /****************************** Axis Utils ********************************/
 
 /**
diff --git a/source/blender/editors/mesh/editmesh_select.c b/source/blender/editors/mesh/editmesh_select.c
index 85b0cbbc318..4d512fab1c0 100644
--- a/source/blender/editors/mesh/editmesh_select.c
+++ b/source/blender/editors/mesh/editmesh_select.c
@@ -186,53 +186,6 @@ unsigned int bm_solidoffs = 0, bm_wireoffs = 0, bm_vertoffs = 0;    /* set in dr
 /* facilities for border select and circle select */
 static char *selbuf = NULL;
 
-/* opengl doesn't support concave... */
-static void draw_triangulated(const int mcords[][2], const short tot)
-{
-	ListBase lb = {NULL, NULL};
-	DispList *dl;
-	float *fp;
-	int a;
-	const float z_up[3] = {0.0f, 0.0f, 1.0f};
-	
-	/* make displist */
-	dl = MEM_callocN(sizeof(DispList), "poly disp");
-	dl->type = DL_POLY;
-	dl->parts = 1;
-	dl->nr = tot;
-	dl->verts = fp = MEM_callocN(tot * 3 * sizeof(float), "poly verts");
-	BLI_addtail(&lb, dl);
-	
-	for (a = 0; a < tot; a++, fp += 3) {
-		fp[0] = (float)mcords[a][0];
-		fp[1] = (float)mcords[a][1];
-	}
-	
-	/* do the fill */
-	BKE_displist_fill(&lb, &lb, z_up, false);
-
-	/* do the draw */
-	dl = lb.first;  /* filldisplist adds in head of list */
-	if (dl->type == DL_INDEX3) {
-		int *index;
-		
-		a = dl->parts;
-		fp = dl->verts;
-		index = dl->index;
-		glBegin(GL_TRIANGLES);
-		while (a--) {
-			glVertex3fv(fp + 3 * index[0]);
-			glVertex3fv(fp + 3 * index[1]);
-			glVertex3fv(fp + 3 * index[2]);
-			index += 3;
-		}
-		glEnd();
-	}
-	
-	BKE_displist_free(&lb);
-}
-
-
 /* reads rect, and builds selection array for quick lookup */
 /* returns if all is OK */
 bool EDBM_backbuf_border_init(ViewContext *vc, short xmin, short ymin, short xmax, short ymax)
@@ -282,6 +235,18 @@ void EDBM_backbuf_free(void)
 	selbuf = NULL;
 }
 
+struct LassoMaskData {
+	unsigned int *px;
+	int width;
+};
+
+static void edbm_mask_lasso_px_cb(int x, int y, void *user_data)
+{
+	struct LassoMaskData *data = user_data;
+	data->px[(y * data->width) + x] = true;
+}
+
+
 /* mcords is a polygon mask
  * - grab backbuffer,
  * - draw with black in backbuffer, 
@@ -290,9 +255,10 @@ void EDBM_backbuf_free(void)
  */
 bool EDBM_backbuf_border_mask_init(ViewContext *vc, const int mcords[][2], short tot, short xmin, short ymin, short xmax, short ymax)
 {
-	unsigned int *dr, *drm;
-	struct ImBuf *buf, *bufmask;
+	unsigned int *dr, *dr_mask, *dr_mask_arr;
+	struct ImBuf *buf;
 	int a;
+	struct LassoMaskData lasso_mask_data;
 	
 	/* method in use for face selecting too */
 	if (vc->obedit == NULL) {
@@ -310,49 +276,25 @@ bool EDBM_backbuf_border_mask_init(ViewContext *vc, const int mcords[][2], short
 
 	dr = buf->rect;
 
-	if (vc->rv3d->gpuoffscreen)
-		GPU_offscreen_bind(vc->rv3d->gpuoffscreen);
-	
-	/* draw the mask */
-	glDisable(GL_DEPTH_TEST);
-	
-	glColor3ub(0, 0, 0);
-	
-	/* yah, opengl doesn't do concave... tsk! */
-	ED_region_pixelspace(vc->ar);
-	draw_triangulated(mcords, tot);
-	
-	glBegin(GL_LINE_LOOP);  /* for zero sized masks, lines */
-	for (a = 0; a < tot; a++) {
-		glVertex2iv(mcords[a]);
-	}
-	glEnd();
-	
-	glFinish(); /* to be sure readpixels sees mask */
-	
-	if (vc->rv3d->gpuoffscreen)
-		GPU_offscreen_unbind(vc->rv3d->gpuoffscreen);
-	
-	/* grab mask */
-	bufmask = view3d_read_backbuf(vc, xmin, ymin, xmax, ymax);
+	dr_mask = dr_mask_arr = MEM_callocN(sizeof(*dr_mask) * buf->x * buf->y, __func__);
+	lasso_mask_data.px = dr_mask;
+	lasso_mask_data.width = (xmax - xmin) + 1;
 
-	if (bufmask == NULL) {
-		return false;  /* only when mem alloc fails, go crash somewhere else! */
-	}
-	else {
-		drm = bufmask->rect;
-	}
+	fill_poly_v2i_n(
+	       xmin, ymin, xmax + 1, ymax + 1,
+	       mcords, tot,
+	       edbm_mask_lasso_px_cb, &lasso_mask_data);
 
 	/* build selection lookup */
 	selbuf = MEM_callocN(bm_vertoffs + 1, "selbuf");
 	
 	a = (xmax - xmin + 1) * (ymax - ymin + 1);
 	while (a--) {
-		if (*dr > 0 && *dr <= bm_vertoffs && *drm == 0) selbuf[*dr] = 1;
-		dr++; drm++;
+		if (*dr > 0 && *dr <= bm_vertoffs && *dr_mask == true) selbuf[*dr] = 1;
+		dr++; dr_mask++;
 	}
 	IMB_freeImBuf(buf);
-	IMB_freeImBuf(bufmask);
+	MEM_freeN(dr_mask_arr);
 
 	return true;
 }
diff --git a/source/blender/windowmanager/intern/wm_gesture.c b/source/blender/windowmanager/intern/wm_gesture.c
index adf159bcfee..05ee23e2361 100644
--- a/source/blender/windowmanager/intern/wm_gesture.c
+++ b/source/blender/windowmanager/intern/wm_gesture.c
@@ -40,6 +40,7 @@
 #include "BLI_math.h"
 #include "BLI_scanfill.h"   /* lasso tessellation */
 #include "BLI_utildefines.h"
+#include "BLI_lasso.h"
 
 #include "BKE_context.h"
 
@@ -231,56 +232,73 @@ static void wm_gesture_draw_circle(wmGesture *gt)
 	
 }
 
-static void draw_filled_lasso(wmGesture *gt)
+struct LassoFillData {
+	unsigned int *px;
+	int width;
+};
+
+static void draw_filled_lasso_px_cb(int x, int y, void *user_data)
+{
+	struct LassoFillData *data = user_data;
+	unsigned char *col = (unsigned char *)&(data->px[(y * data->width) + x]);
+	col[0] = col[1] = col[2] = 0xff;
+	col[3] = 0x10;
+}
+
+static void draw_filled_lasso(wmWindow *win, wmGesture *gt)
 {
-	ScanFillContext sf_ctx;
-	ScanFillVert *sf_vert = NULL, *sf_vert_last = NULL, *sf_vert_first = NULL;
-	ScanFillFace *sf_tri;
 	short *lasso = (short *)gt->customdata;
+	const int tot = gt->points;
+	int (*moves)[2] = MEM_mallocN(sizeof(*moves) * (tot + 1), __func__);
 	int i;
-	
-	BLI_scanfill_begin(&sf_ctx);
-	for (i = 0; i < gt->points; i++, lasso += 2) {
-		float co[3];
-
-		co[0] = (float)lasso[0];
-		co[1] = (float)lasso[1];
-		co[2] = 0.0f;
-
-		sf_vert = BLI_scanfill_vert_add(&sf_ctx, co);
-		if (sf_vert_last)
-			/* e = */ /* UNUSED */ BLI_scanfill_edge_add(&sf_ctx, sf_vert_last, sf_vert);
-		sf_vert_last = sf_vert;
-		if (sf_vert_first == NULL) sf_vert_first = sf_vert;
+	rcti rect;
+	rcti rect_win;
+
+	for (i = 0; i < tot; i++, lasso += 2) {
+		moves[i][0] = lasso[0];
+		moves[i][1] = lasso[1];
 	}
-	
-	/* highly unlikely this will fail, but could crash if (gt->points == 0) */
-	if (sf_vert_first) {
-		const float zvec[3] = {0.0f, 0.0f, 1.0f};
-		BLI_scanfill_edge_add(&sf_ctx, sf_vert_first, sf_vert);
-		BLI_scanfill_calc_ex(&sf_ctx, BLI_SCANFILL_CALC_REMOVE_DOUBLES | BLI_SCANFILL_CALC_HOLES, zvec);
-	
+
+	BLI_lasso_boundbox(&rect, (const int (*)[2])moves, tot);
+
+	wm_subwindow_getrect(win, gt->swinid, &rect_win);
+	BLI_rcti_translate(&rect, rect_win.xmin, rect_win.ymin);
+	BLI_rcti_isect(&rect_win, &rect, &rect);
+	BLI_rcti_translate(&rect, -rect_win.xmin, -rect_win.ymin);
+
+	/* highly unlikely this will fail, but could crash if (tot == 0) */
+	if (BLI_rcti_is_empty(&rect) == false) {
+		const int w = BLI_rcti_size_x(&rect);
+		const int h = BLI_rcti_size_y(&rect);
+		unsigned int *pixel_buf = MEM_callocN(sizeof(*pixel_buf) * w * h, __func__);
+		struct LassoFillData lasso_fill_data = {pixel_buf, w};
+
+		fill_poly_v2i_n(
+		       rect.xmin, rect.ymin, rect.xmax, rect.ymax,
+		       (const int (*)[2])moves, tot,
+		       draw_filled_lasso_px_cb, &lasso_fill_data);
+
 		glEnable(GL_BLEND);
-		glColor4f(1.0, 1.0, 1.0, 0.05);
-		glBegin(GL_TRIANGLES);
-		for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next) {
-			glVertex2fv(sf_tri->v1->co);
-			glVertex2fv(sf_tri->v2->co);
-			glVertex2fv(sf_tri->v3->co);
-		}
-		glEnd();
+		// glColor4f(1.0, 1.0, 1.0, 0.05);
+
+		glRasterPos2f(rect.xmin, rect.ymin);
+
+		glDrawPixels(w, h, GL_RGBA, GL_UNSIGNED_BYTE, pixel_buf);
+
 		glDisable(GL_BLEND);
-	
-		BLI_scanfill_end(&sf_ctx);
+		MEM_freeN(pixel_buf);
 	}
+
+	MEM_freeN(moves);
 }
 
-static void wm_gesture_draw_lasso(wmGesture *gt)
+
+static void wm_gesture_draw_lasso(wmWindow *win, wmGesture *gt)
 {
 	short *lasso = (short *)gt->customdata;
 	int i;
 
-	draw_filled_lasso(gt);
+	draw_filled_lasso(win, gt);
 	
 	glEnable(GL_LINE_STIPPLE);
 	glColor3ub(96, 96, 96);
@@ -347,9 +365,9 @@ void wm_gesture_draw(wmWindow *win)
 				wm_gesture_draw_cross(win, gt);
 		}
 		else if (gt->type == WM_GESTURE_LINES)
-			wm_gesture_draw_lasso(gt);
+			wm_gesture_draw_lasso(win, gt);
 		else if (gt->type == WM_GESTURE_LASSO)
-			wm_gesture_draw_lasso(gt);
+			wm_gesture_draw_lasso(win, gt);
 		else if (gt->type == WM_GESTURE_STRAIGHTLINE)
 			wm_gesture_draw_line(gt);
 	}
diff --git a/source/blender/windowmanager/intern/wm_subwindow.c b/source/blender/windowmanager/intern/wm_subwindow.c
index 4ad4286b657..ae535ed45e8 100644
--- a/source/blender/windowmanager/intern/wm_subwindow.c
+++ b/source/blender/windowmanager/intern/wm_subwindow.c
@@ -148,6 +148,15 @@ void wm_subwindow_getmatrix(wmWindow *win, int swinid, float mat[4][4])
 	}
 }
 
+void wm_subwindow_getrect(wmWindow *win, int swinid, rcti *r_rect)
+{
+	wmSubWindow *swin = swin_from_swinid(win, swinid);
+
+	if (swin) {
+		*r_rect = swin->winrct;
+	}
+}
+
 /* always sets pixel-precise 2D window/view matrices */
 /* coords is in whole pixels. xmin = 15, xmax = 16: means window is 2 pix big */
 int wm_subwindow_open(wmWindow *win, rcti *winrct)
diff --git a/source/blender/windowmanager/wm_subwindow.h b/source/blender/windowmanager/wm_subwindow.h
index 064d00b0723..a70e7765ecf 100644
--- a/source/blender/windowmanager/wm_subwindow.h
+++ b/source/blender/windowmanager/wm_subwindow.h
@@ -45,6 +45,7 @@ void	wm_subwindow_position(wmWindow *win, int swinid, rcti *winrct);
 void	wm_subwindow_getsize(wmWindow *win, int swinid, int *x, int *y);
 void	wm_subwindow_getorigin(wmWindow *win, int swinid, int *x, int *y);
 void	wm_subwindow_getmatrix(wmWindow *win, int swinid, float mat[4][4]);
+void	wm_subwindow_getrect(wmWindow *win, int swinid, struct rcti *r_rect);
 
 unsigned int index_to_framebuffer(int index);