D1705: Fix Grease Pencil Fill for Concave Shapes

Improve filling for concave shapes using a triangulation of the stroke.
The triangulation information is saved in an internal cache and only is
recalculated if the stroke changes.

The triangulation is not saved in .blend file.

Reviewers: aligorith

Maniphest Tasks: T47102

Differential Revision: https://developer.blender.org/D1705

5 files changed, 232 insertions, 33 deletions

diff --git a/source/blender/editors/gpencil/drawgpencil.c b/source/blender/editors/gpencil/drawgpencil.c
index b5d9283f6c6..3f7805fa2c4 100644
--- a/source/blender/editors/gpencil/drawgpencil.c
+++ b/source/blender/editors/gpencil/drawgpencil.c
@@ -35,10 +35,13 @@
 #include <math.h>
 #include <float.h>
 
+#include "MEM_guardedalloc.h"
+
 #include "BLI_sys_types.h"
 
 #include "BLI_math.h"
 #include "BLI_utildefines.h"
+#include "BLI_polyfill2d.h"
 
 #include "BLF_api.h"
 #include "BLT_translation.h"
@@ -82,6 +85,7 @@ typedef enum eDrawStrokeFlags {
 	GP_DRAWDATA_NO_ONIONS   = (1 << 6),	  /* no onionskins should be drawn (for animation playback) */
 	GP_DRAWDATA_VOLUMETRIC	= (1 << 7),   /* draw strokes as "volumetric" circular billboards */
 	GP_DRAWDATA_FILL        = (1 << 8),   /* fill insides/bounded-regions of strokes */
+	GP_DRAWDATA_HQ_FILL     = (1 << 9)    /* Use high quality fill */
 } eDrawStrokeFlags;
 
 
@@ -324,37 +328,184 @@ static void gp_draw_stroke_volumetric_3d(bGPDspoint *points, int totpoints, shor
 
 
 /* --------------- Stroke Fills ----------------- */
+/* get points of stroke always flat to view not affected by camera view or view position
+ */
+static void gp_stroke_2d_flat(bGPDspoint *points, int totpoints, float(*points2d)[2], int *r_direction)
+{
+	bGPDspoint *pt0 = &points[0];
+	bGPDspoint *pt1 = &points[1];
+	bGPDspoint *pt3 = &points[(int) (totpoints * 0.75)];
+	bGPDspoint *pt;
+	float locx[3];
+	float locy[3];
+	float loc3[3];
+	float normal[3];
+
+	/* local X axis (p0-p1) */
+	sub_v3_v3v3(locx, &pt1->x, &pt0->x);
+
+	/* point vector at 3/4 */
+	sub_v3_v3v3(loc3, &pt3->x, &pt0->x);
+
+	/* vector orthogonal to polygon plane */
+	cross_v3_v3v3(normal, locx, loc3);
+
+	/* local Y axis (cross to normal/x axis) */
+	cross_v3_v3v3(locy, normal, locx);
+
+	/* Normalize vectors */
+	normalize_v3(locx);
+	normalize_v3(locy);
+
+	/* Get all points in local space */
+	for (int i = 0; i < totpoints; i++)	{
+
+		float loc[3];
+		/* Get local space using first point as origin */
+		pt = &points[i];
+		sub_v3_v3v3(loc, &pt->x, &pt0->x);
+
+		float co[2];
+		co[0] = dot_v3v3(loc, locx);
+		co[1] = dot_v3v3(loc, locy);
+		points2d[i][0] = co[0];
+		points2d[i][1] = co[1];
+	}
+
+	*r_direction = (int)locy[2];
+}
+
+
+/* triangulate stroke for high quality fill (this is done only if cache is null or stroke was modified) */
+static void gp_triangulate_stroke_fill(bGPDstroke *gps)
+{
+	BLI_assert(gps->totpoints >= 3);
+
+	bGPDtriangle *stroke_triangle;
+	int i;
+
+	/* allocate memory for temporary areas */
+	unsigned int(*tmp_triangles)[3] = MEM_mallocN(sizeof(*tmp_triangles) * gps->totpoints, "GP Stroke temp triangulation");
+	float(*points2d)[2] = MEM_mallocN(sizeof(*points2d) * gps->totpoints, "GP Stroke temp 2d points");
+
+	int direction;
+
+	/* convert to 2d and triangulate */
+	gp_stroke_2d_flat(gps->points, gps->totpoints, points2d, &direction);
+	BLI_polyfill_calc((const float(*)[2])points2d, (unsigned int)gps->totpoints, direction, (unsigned int(*)[3])tmp_triangles);
+
+	/* count number of valid triangles */
+	gps->tot_triangles = 0;
+	for (i = 0; i < gps->totpoints; i++) {
+		if ((tmp_triangles[i][0] >= 0) && (tmp_triangles[i][0] < gps->totpoints) &&
+			(tmp_triangles[i][1] >= 0) && (tmp_triangles[i][1] < gps->totpoints) &&
+			(tmp_triangles[i][2] >= 0) && (tmp_triangles[i][2] < gps->totpoints))
+		{
+			gps->tot_triangles += 1;
+		}
+	}
+
+	/* save triangulation data in stroke cache */
+	if (gps->triangles == NULL) {
+		gps->triangles = MEM_callocN(sizeof(bGPDtriangle) * gps->tot_triangles, "GP Stroke triangulation");
+	}
+	else {
+		gps->triangles = MEM_recallocN(gps->triangles, sizeof(*gps->triangles) * gps->tot_triangles);
+	}
+
+	for (i = 0; i < gps->tot_triangles; i++) {
+		if ((tmp_triangles[i][0] >= 0) && (tmp_triangles[i][0] < gps->totpoints) &&
+			(tmp_triangles[i][1] >= 0) && (tmp_triangles[i][1] < gps->totpoints) &&
+			(tmp_triangles[i][2] >= 0) && (tmp_triangles[i][2] < gps->totpoints))
+		{
+			stroke_triangle = &gps->triangles[i];
+			stroke_triangle->v1 = tmp_triangles[i][0];
+			stroke_triangle->v2 = tmp_triangles[i][1];
+			stroke_triangle->v3 = tmp_triangles[i][2];
+		}
+	}
+	/* disable recalculation flag (False)*/
+	if (gps->flag & GP_STROKE_RECALC_CACHES) {
+		gps->flag ^= GP_STROKE_RECALC_CACHES;
+	}
+	/* clear memory */
+	if (tmp_triangles) MEM_freeN(tmp_triangles);
+	if (points2d) MEM_freeN(points2d);
+
+}
+
 
 /* draw fills for shapes */
-static void gp_draw_stroke_fill(bGPDspoint *points, int totpoints, short UNUSED(thickness),
-                                short UNUSED(dflag), short sflag,
-                                int offsx, int offsy, int winx, int winy)
+static void gp_draw_stroke_fill(bGPDstroke *gps, short UNUSED(thickness), short dflag, int offsx, int offsy, int winx, int winy)
 {
-	bGPDspoint *pt;
 	int i;
-	
-	BLI_assert(totpoints >= 3);
-	
-	/* As an initial implementation, we use the OpenGL filled polygon drawing
-	 * here since it's the easiest option to implement for this case. It does
-	 * come with limitations (notably for concave shapes), though it shouldn't
-	 * be much of an issue in most cases.
-	 */
-	glBegin(GL_POLYGON);
-	
-	for (i = 0, pt = points; i < totpoints; i++, pt++) {
-		if (sflag & GP_STROKE_3DSPACE) {
-			glVertex3fv(&pt->x);
+
+	BLI_assert(gps->totpoints >= 3);
+	/* Triangulation fill if high quality flag is enabled */
+	if (dflag & GP_DRAWDATA_HQ_FILL) {
+		bGPDtriangle *stroke_triangle;
+		bGPDspoint *pt;
+
+		/* Calculate triangles cache for filling area (must be done only after changes) */
+		if ((gps->flag & GP_STROKE_RECALC_CACHES) || (gps->tot_triangles == 0) || (gps->triangles == NULL)) {
+			gp_triangulate_stroke_fill(gps);
 		}
-		else {
-			float co[2];
-			
-			gp_calc_2d_stroke_xy(pt, sflag, offsx, offsy, winx, winy, co);
-			glVertex2fv(co);
+		/* Draw all triangles for filling the polygon (cache must be calculated before) */
+		BLI_assert(gps->tot_triangles >= 1);
+		glBegin(GL_TRIANGLES);
+		for (i = 0, stroke_triangle = gps->triangles; i < gps->tot_triangles; i++, stroke_triangle++) {
+			if (gps->flag & GP_STROKE_3DSPACE) {
+				/* vertex 1 */
+				pt = &gps->points[stroke_triangle->v1];
+				glVertex3fv(&pt->x);
+				/* vertex 2 */
+				pt = &gps->points[stroke_triangle->v2];
+				glVertex3fv(&pt->x);
+				/* vertex 3 */
+				pt = &gps->points[stroke_triangle->v3];
+				glVertex3fv(&pt->x);
+			}
+			else {
+				float co[2];
+				/* vertex 1 */
+				pt = &gps->points[stroke_triangle->v1];
+				gp_calc_2d_stroke_xy(pt, gps->flag, offsx, offsy, winx, winy, co);
+				glVertex2fv(co);
+				/* vertex 2 */
+				pt = &gps->points[stroke_triangle->v2];
+				gp_calc_2d_stroke_xy(pt, gps->flag, offsx, offsy, winx, winy, co);
+				glVertex2fv(co);
+				/* vertex 3 */
+				pt = &gps->points[stroke_triangle->v3];
+				gp_calc_2d_stroke_xy(pt, gps->flag, offsx, offsy, winx, winy, co);
+				glVertex2fv(co);
+			}
 		}
+		glEnd();
+	}
+	else {
+		/* As an initial implementation, we use the OpenGL filled polygon drawing
+		 * here since it's the easiest option to implement for this case. It does
+		 * come with limitations (notably for concave shapes), though it shouldn't
+		 * be much of an issue in most cases.
+		 */
+		bGPDspoint *pt;
+
+		glBegin(GL_POLYGON);
+		for (i = 0, pt = gps->points; i < gps->totpoints; i++, pt++) {
+			if (gps->flag & GP_STROKE_3DSPACE) {
+				glVertex3fv(&pt->x);
+			}
+			else {
+				float co[2];
+
+				gp_calc_2d_stroke_xy(pt, gps->flag, offsx, offsy, winx, winy, co);
+				glVertex2fv(co);
+			}
+		}
+
+		glEnd();
 	}
-	
-	glEnd();
 }
 
 /* ----- Existing Strokes Drawing (3D and Point) ------ */
@@ -695,7 +846,7 @@ static void gp_draw_strokes(bGPDframe *gpf, int offsx, int offsy, int winx, int
 			/* 3D Fill */
 			if ((dflag & GP_DRAWDATA_FILL) && (gps->totpoints >= 3)) {
 				glColor4fv(fill_color);
-				gp_draw_stroke_fill(gps->points, gps->totpoints, lthick, dflag, gps->flag, offsx, offsy, winx, winy);
+				gp_draw_stroke_fill(gps, lthick, dflag, offsx, offsy, winx, winy);
 			}
 			
 			/* 3D Stroke */
@@ -730,7 +881,7 @@ static void gp_draw_strokes(bGPDframe *gpf, int offsx, int offsy, int winx, int
 			/* 2D - Fill */
 			if ((dflag & GP_DRAWDATA_FILL) && (gps->totpoints >= 3)) {
 				glColor4fv(fill_color);
-				gp_draw_stroke_fill(gps->points, gps->totpoints, lthick, dflag, gps->flag, offsx, offsy, winx, winy);
+				gp_draw_stroke_fill(gps, lthick, dflag, offsx, offsy, winx, winy);
 			}
 			
 			/* 2D Strokes... */
@@ -990,7 +1141,10 @@ static void gp_draw_data_layers(bGPdata *gpd, int offsx, int offsy, int winx, in
 		
 		/* volumetric strokes... */
 		GP_DRAWFLAG_APPLY((gpl->flag & GP_LAYER_VOLUMETRIC), GP_DRAWDATA_VOLUMETRIC);
-		
+
+		/* HQ fills... */
+		GP_DRAWFLAG_APPLY((gpl->flag & GP_LAYER_HQ_FILL), GP_DRAWDATA_HQ_FILL);
+
 		/* fill strokes... */
 		// XXX: this is not a very good limit
 		GP_DRAWFLAG_APPLY((gpl->fill[3] > GPENCIL_ALPHA_OPACITY_THRESH), GP_DRAWDATA_FILL);
diff --git a/source/blender/editors/gpencil/editaction_gpencil.c b/source/blender/editors/gpencil/editaction_gpencil.c
index 09a72c10457..a49b3362155 100644
--- a/source/blender/editors/gpencil/editaction_gpencil.c
+++ b/source/blender/editors/gpencil/editaction_gpencil.c
@@ -460,7 +460,8 @@ bool ED_gpencil_anim_copybuf_paste(bAnimContext *ac, const short offset_mode)
 					/* make a copy of stroke, then of its points array */
 					gpsn = MEM_dupallocN(gps);
 					gpsn->points = MEM_dupallocN(gps->points);
-					
+					/* duplicate triangle information */
+					gpsn->triangles = MEM_dupallocN(gps->triangles);
 					/* append stroke to frame */
 					BLI_addtail(&gpf->strokes, gpsn);				
 				}
diff --git a/source/blender/editors/gpencil/gpencil_brush.c b/source/blender/editors/gpencil/gpencil_brush.c
index 43751dbadb9..0bf5a259d5a 100644
--- a/source/blender/editors/gpencil/gpencil_brush.c
+++ b/source/blender/editors/gpencil/gpencil_brush.c
@@ -766,6 +766,8 @@ static void gp_brush_clone_add(bContext *C, tGP_BrushEditData *gso)
 			new_stroke = MEM_dupallocN(gps);
 			
 			new_stroke->points = MEM_dupallocN(gps->points);
+			/* duplicate triangle information */
+			new_stroke->triangles = MEM_dupallocN(gps->triangles);
 			new_stroke->next = new_stroke->prev = NULL;
 			
 			BLI_addtail(&gpf->strokes, new_stroke);
@@ -1284,6 +1286,11 @@ static bool gpsculpt_brush_apply_standard(bContext *C, tGP_BrushEditData *gso)
 				printf("ERROR: Unknown type of GPencil Sculpt brush - %u\n", gso->brush_type);
 				break;
 		}
+		/* Triangulation must be calculated if changed */
+		if (changed) {
+			gps->flag |= GP_STROKE_RECALC_CACHES;
+			gps->tot_triangles = 0;
+		}
 	}
 	CTX_DATA_END;
 	
diff --git a/source/blender/editors/gpencil/gpencil_edit.c b/source/blender/editors/gpencil/gpencil_edit.c
index 03d5ed3e24f..e3501dfa987 100644
--- a/source/blender/editors/gpencil/gpencil_edit.c
+++ b/source/blender/editors/gpencil/gpencil_edit.c
@@ -169,7 +169,10 @@ static void gp_duplicate_points(const bGPDstroke *gps, ListBase *new_strokes)
 				
 				/* make a stupid copy first of the entire stroke (to get the flags too) */
 				gpsd = MEM_dupallocN(gps);
-				
+				/* initialize triangle memory */
+				gpsd->triangles = NULL;
+				gpsd->flag |= GP_STROKE_RECALC_CACHES;
+				gpsd->tot_triangles = 0;
 				/* now, make a new points array, and copy of the relevant parts */
 				gpsd->points = MEM_callocN(sizeof(bGPDspoint) * len, "gps stroke points copy");
 				memcpy(gpsd->points, gps->points + start_idx, sizeof(bGPDspoint) * len);
@@ -222,7 +225,10 @@ static int gp_duplicate_exec(bContext *C, wmOperator *op)
 					/* make direct copies of the stroke and its points */
 					gpsd = MEM_dupallocN(gps);
 					gpsd->points = MEM_dupallocN(gps->points);
-					
+					/* triangle information */
+					gpsd->triangles = MEM_dupallocN(gps->triangles);
+					gpsd->flag |= GP_STROKE_RECALC_CACHES;
+
 					/* add to temp buffer */
 					gpsd->next = gpsd->prev = NULL;
 					BLI_addtail(&new_strokes, gpsd);
@@ -288,6 +294,7 @@ void ED_gpencil_strokes_copybuf_free(void)
 		gpsn = gps->next;
 		
 		MEM_freeN(gps->points);
+		MEM_freeN(gps->triangles);
 		BLI_freelinkN(&gp_strokes_copypastebuf, gps);
 	}
 	
@@ -335,7 +342,10 @@ static int gp_strokes_copy_exec(bContext *C, wmOperator *op)
 					/* make direct copies of the stroke and its points */
 					gpsd = MEM_dupallocN(gps);
 					gpsd->points = MEM_dupallocN(gps->points);
-					
+					/* duplicate triangle information */
+					gpsd->triangles = MEM_dupallocN(gps->triangles);
+					gpsd->flag |= GP_STROKE_RECALC_CACHES;
+					gpsd->tot_triangles = 0;
 					/* add to temp buffer */
 					gpsd->next = gpsd->prev = NULL;
 					BLI_addtail(&gp_strokes_copypastebuf, gpsd);
@@ -450,6 +460,9 @@ static int gp_strokes_paste_exec(bContext *C, wmOperator *op)
 				bGPDstroke *new_stroke = MEM_dupallocN(gps);
 				
 				new_stroke->points = MEM_dupallocN(gps->points);
+				/* triangle information */
+				new_stroke->triangles = MEM_dupallocN(gps->triangles);
+				new_stroke->flag |= GP_STROKE_RECALC_CACHES;
 				new_stroke->next = new_stroke->prev = NULL;
 				
 				BLI_addtail(&gpf->strokes, new_stroke);
@@ -672,6 +685,7 @@ static int gp_delete_selected_strokes(bContext *C)
 			if (gps->flag & GP_STROKE_SELECT) {
 				/* free stroke memory arrays, then stroke itself */
 				if (gps->points) MEM_freeN(gps->points);
+				if (gps->triangles) MEM_freeN(gps->triangles);
 				BLI_freelinkN(&gpf->strokes, gps);
 				
 				changed = true;
@@ -732,6 +746,9 @@ static int gp_dissolve_selected_points(bContext *C)
 				if (tot <= 0) {
 					/* remove the entire stroke */
 					MEM_freeN(gps->points);
+					if (gps->triangles) {
+						MEM_freeN(gps->triangles);
+					}
 					BLI_freelinkN(&gpf->strokes, gps);
 				}
 				else {
@@ -752,7 +769,9 @@ static int gp_dissolve_selected_points(bContext *C)
 					/* save the new buffer */
 					gps->points = new_points;
 					gps->totpoints = tot;
-					
+					/* recalculate cache */
+					gps->flag |= GP_STROKE_RECALC_CACHES;
+					gps->tot_triangles = 0;
 					/* deselect the stroke, since none of its selected points will still be selected */
 					gps->flag &= ~GP_STROKE_SELECT;
 				}
@@ -842,6 +861,11 @@ void gp_stroke_delete_tagged_points(bGPDframe *gpf, bGPDstroke *gps, bGPDstroke
 			tGPDeleteIsland *island = &islands[idx];
 			bGPDstroke *new_stroke  = MEM_dupallocN(gps);
 			
+			/* initialize triangle memory */
+			new_stroke->triangles = NULL;
+			new_stroke->flag |= GP_STROKE_RECALC_CACHES;
+			new_stroke->tot_triangles = 0;
+			
 			/* Compute new buffer size (+ 1 needed as the endpoint index is "inclusive") */
 			new_stroke->totpoints = island->end_idx - island->start_idx + 1;
 			new_stroke->points    = MEM_callocN(sizeof(bGPDspoint) * new_stroke->totpoints, "gp delete stroke fragment");
@@ -886,6 +910,9 @@ void gp_stroke_delete_tagged_points(bGPDframe *gpf, bGPDstroke *gps, bGPDstroke
 	
 	/* Delete the old stroke */
 	MEM_freeN(gps->points);
+	if (gps->triangles) {
+		MEM_freeN(gps->triangles);
+	}
 	BLI_freelinkN(&gpf->strokes, gps);
 }
 
diff --git a/source/blender/editors/gpencil/gpencil_paint.c b/source/blender/editors/gpencil/gpencil_paint.c
index 2a81b481ed1..06829cc92be 100644
--- a/source/blender/editors/gpencil/gpencil_paint.c
+++ b/source/blender/editors/gpencil/gpencil_paint.c
@@ -572,6 +572,9 @@ static void gp_stroke_newfrombuffer(tGPsdata *p)
 	gps->flag = gpd->sbuffer_sflag;
 	gps->inittime = p->inittime;
 	
+	/* enable recalculation flag by default (only used if hq fill) */
+	gps->flag |= GP_STROKE_RECALC_CACHES;
+
 	/* allocate enough memory for a continuous array for storage points */
 	int sublevel = gpl->sublevel;
 	int new_totpoints = gps->totpoints;
@@ -580,7 +583,10 @@ static void gp_stroke_newfrombuffer(tGPsdata *p)
 		new_totpoints += new_totpoints - 1;
 	}
 	gps->points = MEM_callocN(sizeof(bGPDspoint) * new_totpoints, "gp_stroke_points");
-	
+	/* initialize triangle memory to dummy data */
+	gps->triangles = MEM_callocN(sizeof(bGPDtriangle), "GP Stroke triangulation");
+	gps->flag |= GP_STROKE_RECALC_CACHES;
+	gps->tot_triangles = 0;
 	/* set pointer to first non-initialized point */
 	pt = gps->points + (gps->totpoints - totelem);
 	
@@ -795,6 +801,8 @@ static void gp_stroke_eraser_dostroke(tGPsdata *p,
 		/* just free stroke */
 		if (gps->points)
 			MEM_freeN(gps->points);
+		if (gps->triangles)
+			MEM_freeN(gps->triangles);
 		BLI_freelinkN(&gpf->strokes, gps);
 	}
 	else if (gps->totpoints == 1) {
@@ -807,6 +815,8 @@ static void gp_stroke_eraser_dostroke(tGPsdata *p,
 				/* free stroke */
 				// XXX: pressure sensitive eraser should apply here too?
 				MEM_freeN(gps->points);
+				if (gps->triangles)
+					 MEM_freeN(gps->triangles);
 				BLI_freelinkN(&gpf->strokes, gps);
 			}
 		}