Merged changes in the trunk up to revision 54594.

12 files changed, 144 insertions, 46 deletions

diff --git a/source/blender/blenlib/BLI_math_geom.h b/source/blender/blenlib/BLI_math_geom.h
index a822bdb9414..c4e17b1ed48 100644
--- a/source/blender/blenlib/BLI_math_geom.h
+++ b/source/blender/blenlib/BLI_math_geom.h
@@ -51,6 +51,7 @@ float normal_quad_v3(float r[3], const float a[3], const float b[3], const float
 float area_tri_v2(const float a[2], const float b[2], const float c[2]);
 float area_tri_signed_v2(const float v1[2], const float v2[2], const float v3[2]);
 float area_tri_v3(const float a[3], const float b[3], const float c[3]);
+float area_tri_signed_v3(const float v1[3], const float v2[3], const float v3[3], const float normal[3]);
 float area_quad_v3(const float a[3], const float b[3], const float c[3], const float d[3]);
 float area_poly_v3(int nr, float verts[][3], const float normal[3]);
 float area_poly_v2(int nr, float verts[][2]);
diff --git a/source/blender/blenlib/BLI_math_matrix.h b/source/blender/blenlib/BLI_math_matrix.h
index a5ab2373b89..97cd6a60862 100644
--- a/source/blender/blenlib/BLI_math_matrix.h
+++ b/source/blender/blenlib/BLI_math_matrix.h
@@ -88,6 +88,7 @@ void mul_serie_m4(float R[4][4],
 
 void mul_m4_v3(float M[4][4], float r[3]);
 void mul_v3_m4v3(float r[3], float M[4][4], const float v[3]);
+void mul_v2_m2v2(float r[2], float M[2][2], const float v[2]);
 void mul_mat3_m4_v3(float M[4][4], float r[3]);
 void mul_m4_v4(float M[4][4], float r[4]);
 void mul_v4_m4v4(float r[4], float M[4][4], const float v[4]);
@@ -170,6 +171,7 @@ void mat4_to_size(float r[3], float M[4][4]);
 
 void translate_m4(float mat[4][4], float tx, float ty, float tz);
 void rotate_m4(float mat[4][4], const char axis, const float angle);
+void rotate_m2(float mat[2][2], const float angle);
 
 
 void mat3_to_rot_size(float rot[3][3], float size[3], float mat3[3][3]);
diff --git a/source/blender/blenlib/BLI_string_cursor_utf8.h b/source/blender/blenlib/BLI_string_cursor_utf8.h
index 3c38c0380e0..04d9df2abda 100644
--- a/source/blender/blenlib/BLI_string_cursor_utf8.h
+++ b/source/blender/blenlib/BLI_string_cursor_utf8.h
@@ -46,6 +46,6 @@ int BLI_str_cursor_step_prev_utf8(const char *str, size_t maxlen, int *pos);
 
 void BLI_str_cursor_step_utf8(const char *str, size_t maxlen,
                               int *pos, strCursorJumpDirection direction,
-                              strCursorJumpType jump);
+                              strCursorJumpType jump, bool use_init_step);
 
 #endif /* __BLI_STRING_CURSOR_UTF8_H__ */
diff --git a/source/blender/blenlib/intern/BLI_mempool.c b/source/blender/blenlib/intern/BLI_mempool.c
index bf228f7456a..7670b057a7f 100644
--- a/source/blender/blenlib/intern/BLI_mempool.c
+++ b/source/blender/blenlib/intern/BLI_mempool.c
@@ -245,6 +245,10 @@ void BLI_mempool_free(BLI_mempool *pool, void *addr)
 	BLI_freenode *newhead = addr;
 
 	if (pool->flag & BLI_MEMPOOL_ALLOW_ITER) {
+#ifndef NDEBUG
+		/* this will detect double free's */
+		BLI_assert(newhead->freeword != FREEWORD);
+#endif
 		newhead->freeword = FREEWORD;
 	}
 
diff --git a/source/blender/blenlib/intern/fileops.c b/source/blender/blenlib/intern/fileops.c
index 0f42fca9f12..24b3c36a329 100644
--- a/source/blender/blenlib/intern/fileops.c
+++ b/source/blender/blenlib/intern/fileops.c
@@ -111,7 +111,7 @@ int BLI_file_gzip(const char *from, const char *to)
 	return rval;
 }
 
-/* gzip the file in from_file and write it to memery to_mem, at most size bytes.
+/* gzip the file in from_file and write it to memory to_mem, at most size bytes.
  * return the unziped size
  */
 char *BLI_file_ungzip_to_mem(const char *from_file, int *size_r)
@@ -283,7 +283,7 @@ int BLI_move(const char *file, const char *to)
 {
 	int err;
 
-	/* windows doesn't support moveing to a directory
+	/* windows doesn't support moving to a directory
 	 * it has to be 'mv filename filename' and not
 	 * 'mv filename destdir' */
 
diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c
index ac9534dac25..810c15437dc 100644
--- a/source/blender/blenlib/intern/math_geom.c
+++ b/source/blender/blenlib/intern/math_geom.c
@@ -39,9 +39,9 @@
 
 void cent_tri_v3(float cent[3], const float v1[3], const float v2[3], const float v3[3])
 {
-	cent[0] = 0.33333f * (v1[0] + v2[0] + v3[0]);
-	cent[1] = 0.33333f * (v1[1] + v2[1] + v3[1]);
-	cent[2] = 0.33333f * (v1[2] + v2[2] + v3[2]);
+	cent[0] = (v1[0] + v2[0] + v3[0]) / 3.0f;
+	cent[1] = (v1[1] + v2[1] + v3[1]) / 3.0f;
+	cent[2] = (v1[2] + v2[2] + v3[2]) / 3.0f;
 }
 
 void cent_quad_v3(float cent[3], const float v1[3], const float v2[3], const float v3[3], const float v4[3])
@@ -129,6 +129,22 @@ float area_tri_v3(const float v1[3], const float v2[3], const float v3[3])
 	return (len / 2.0f);
 }
 
+float area_tri_signed_v3(const float v1[3], const float v2[3], const float v3[3], const float normal[3])
+{
+	float area, vec1[3], vec2[3], n[3];
+
+	sub_v3_v3v3(vec1, v3, v2);
+	sub_v3_v3v3(vec2, v1, v2);
+	cross_v3_v3v3(n, vec1, vec2);
+	area = len_v3(n) / 2.0f;
+
+	/* negate area for flipped triangles */
+	if (dot_v3v3(n, normal) < 0.0f)
+		area = -area;
+
+	return area;
+}
+
 float area_poly_v3(int nr, float verts[][3], const float normal[3])
 {
 	int a, px, py;
@@ -3578,25 +3594,42 @@ float form_factor_hemi_poly(float p[3], float n[3], float v1[3], float v2[3], fl
 /* evaluate if entire quad is a proper convex quad */
 int is_quad_convex_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3])
 {
-	float nor[3], nor1[3], nor2[3], vec[4][2];
+	float nor[3], nor_a[3], nor_b[3], vec[4][2];
 	float mat[3][3];
+	const bool is_ok_a = (normal_tri_v3(nor_a, v1, v2, v3) > FLT_EPSILON);
+	const bool is_ok_b = (normal_tri_v3(nor_b, v1, v3, v4) > FLT_EPSILON);
 
 	/* define projection, do both trias apart, quad is undefined! */
 
-	normal_tri_v3(nor1, v1, v2, v3);
-	normal_tri_v3(nor2, v1, v3, v4);
+	/* check normal length incase one size is zero area */
+	if (is_ok_a) {
+		if (is_ok_b) {
+			/* use both, most common outcome */
+
+			/* when the face is folded over as 2 tris we probably don't want to create
+			 * a quad from it, but go ahead with the intersection test since this
+			 * isn't a function for degenerate faces */
+			if (UNLIKELY(dot_v3v3(nor_a, nor_b) < 0.0f)) {
+				/* flip so adding normals in the opposite direction
+				 * doesn't give a zero length vector */
+				negate_v3(nor_b);
+			}
 
-	/* when the face is folded over as 2 tris we probably don't want to create
-	 * a quad from it, but go ahead with the intersection test since this
-	 * isn't a function for degenerate faces */
-	if (UNLIKELY(dot_v3v3(nor1, nor2) < 0.0f)) {
-		/* flip so adding normals in the opposite direction
-		 * doesnt give a zero length vector */
-		negate_v3(nor2);
+			add_v3_v3v3(nor, nor_a, nor_b);
+			normalize_v3(nor);
+		}
+		else {
+			copy_v3_v3(nor, nor_a);  /* only 'a' */
+		}
+	}
+	else {
+		if (is_ok_b) {
+			copy_v3_v3(nor, nor_b);  /* only 'b' */
+		}
+		else {
+			return false;  /* both zero, we can't do anything useful here */
+		}
 	}
-
-	add_v3_v3v3(nor, nor1, nor2);
-	normalize_v3(nor);
 
 	axis_dominant_v3_to_m3(mat, nor);
 
@@ -3606,12 +3639,12 @@ int is_quad_convex_v3(const float v1[3], const float v2[3], const float v3[3], c
 	mul_v2_m3v3(vec[3], mat, v4);
 
 	/* linetests, the 2 diagonals have to instersect to be convex */
-	return (isect_line_line_v2(vec[0], vec[2], vec[1], vec[3]) > 0) ? TRUE : FALSE;
+	return (isect_line_line_v2(vec[0], vec[2], vec[1], vec[3]) > 0);
 }
 
 int is_quad_convex_v2(const float v1[2], const float v2[2], const float v3[2], const float v4[2])
 {
 	/* linetests, the 2 diagonals have to instersect to be convex */
-	return (isect_line_line_v2(v1, v3, v2, v4) > 0) ? TRUE : FALSE;
+	return (isect_line_line_v2(v1, v3, v2, v4) > 0);
 }
 
diff --git a/source/blender/blenlib/intern/math_matrix.c b/source/blender/blenlib/intern/math_matrix.c
index 5c443b9b1f3..9d9e3e611e1 100644
--- a/source/blender/blenlib/intern/math_matrix.c
+++ b/source/blender/blenlib/intern/math_matrix.c
@@ -344,6 +344,15 @@ void mul_v3_m4v3(float in[3], float mat[4][4], const float vec[3])
 	in[2] = x * mat[0][2] + y * mat[1][2] + mat[2][2] * vec[2] + mat[3][2];
 }
 
+void mul_v2_m2v2(float r[2], float mat[2][2], const float vec[2])
+{
+	float x;
+
+	x = vec[0];
+	r[0] = mat[0][0] * x + mat[1][0] * vec[1];
+	r[1] = mat[0][1] * x + mat[1][1] * vec[1];
+}
+
 /* same as mul_m4_v3() but doesnt apply translation component */
 void mul_mat3_m4_v3(float mat[4][4], float vec[3])
 {
@@ -1304,6 +1313,13 @@ void rotate_m4(float mat[4][4], const char axis, const float angle)
 	}
 }
 
+void rotate_m2(float mat[2][2], const float angle)
+{
+	mat[0][0] = mat[1][1] = cosf(angle);
+	mat[0][1] = sinf(angle);
+	mat[1][0] = -mat[0][1];
+}
+
 void blend_m3_m3m3(float out[3][3], float dst[3][3], float src[3][3], const float srcweight)
 {
 	float srot[3][3], drot[3][3];
diff --git a/source/blender/blenlib/intern/math_rotation.c b/source/blender/blenlib/intern/math_rotation.c
index e6399ed356e..c0ea817ae4a 100644
--- a/source/blender/blenlib/intern/math_rotation.c
+++ b/source/blender/blenlib/intern/math_rotation.c
@@ -1662,7 +1662,7 @@ void quat_apply_track(float quat[4], short axis, short upflag)
 		axis = axis - 3;
 
 	/* there are 2 possible up-axis for each axis used, the 'quat_track' applies so the first
-	 * up axis is used X->Y, Y->X, Z->X, if this first up axis isn used then rotate 90d
+	 * up axis is used X->Y, Y->X, Z->X, if this first up axis isn't used then rotate 90d
 	 * the strange bit shift below just find the low axis {X:Y, Y:X, Z:X} */
 	if (upflag != (2 - axis) >> 1) {
 		float q[4] = {M_SQRT1_2, 0.0, 0.0, 0.0}; /* assign 90d rotation axis */
diff --git a/source/blender/blenlib/intern/math_vector_inline.c b/source/blender/blenlib/intern/math_vector_inline.c
index c4def539c10..48e7de43a86 100644
--- a/source/blender/blenlib/intern/math_vector_inline.c
+++ b/source/blender/blenlib/intern/math_vector_inline.c
@@ -663,7 +663,7 @@ MINLINE float normalize_v3_v3(float r[3], const float a[3])
 	float d = dot_v3v3(a, a);
 
 	/* a larger value causes normalize errors in a
-	 * scaled down models with camera xtreme close */
+	 * scaled down models with camera extreme close */
 	if (d > 1.0e-35f) {
 		d = sqrtf(d);
 		mul_v3_v3fl(r, a, 1.0f / d);
@@ -681,7 +681,7 @@ MINLINE double normalize_v3_d(double n[3])
 	double d = n[0] * n[0] + n[1] * n[1] + n[2] * n[2];
 
 	/* a larger value causes normalize errors in a
-	 * scaled down models with camera xtreme close */
+	 * scaled down models with camera extreme close */
 	if (d > 1.0e-35) {
 		double mul;
 
diff --git a/source/blender/blenlib/intern/scanfill.c b/source/blender/blenlib/intern/scanfill.c
index 771295b4b78..298e37137ce 100644
--- a/source/blender/blenlib/intern/scanfill.c
+++ b/source/blender/blenlib/intern/scanfill.c
@@ -325,7 +325,9 @@ static short addedgetoscanvert(ScanFillVertLink *sc, ScanFillEdge *eed)
 		fac1 = 1.0e10f * (eed->v2->xy[0] - x);
 
 	}
-	else fac1 = (x - eed->v2->xy[0]) / fac1;
+	else {
+		fac1 = (x - eed->v2->xy[0]) / fac1;
+	}
 
 	for (ed = sc->edge_first; ed; ed = ed->next) {
 
@@ -509,7 +511,7 @@ static int scanfill(ScanFillContext *sf_ctx, PolyFill *pf, const int flag)
 	ScanFillVert *eve, *v1, *v2, *v3;
 	ScanFillEdge *eed, *nexted, *ed1, *ed2, *ed3;
 	int a, b, verts, maxface, totface;
-	short nr, test, twoconnected = 0;
+	short nr, twoconnected = 0;
 
 	nr = pf->nr;
 
@@ -565,6 +567,7 @@ static int scanfill(ScanFillContext *sf_ctx, PolyFill *pf, const int flag)
 				verts++;
 				eve->f = 0;  /* flag for connectedges later on */
 				sc->vert = eve;
+				/* if (even->tmp.v == NULL) eve->tmp.u = verts; */ /* Note, debug print only will work for curve polyfill, union is in use for mesh */
 				sc++;
 			}
 		}
@@ -639,7 +642,7 @@ static int scanfill(ScanFillContext *sf_ctx, PolyFill *pf, const int flag)
 
 	sc = sf_ctx->_scdata;
 	for (a = 0; a < verts; a++) {
-		/* printf("VERTEX %d %x\n", a, sc->v1); */
+		/* printf("VERTEX %d index %d\n", a, sc->vert->tmp.u); */
 		ed1 = sc->edge_first;
 		while (ed1) {   /* set connectflags  */
 			nexted = ed1->next;
@@ -649,7 +652,9 @@ static int scanfill(ScanFillContext *sf_ctx, PolyFill *pf, const int flag)
 				if (ed1->v1->h > 1) ed1->v1->h--;
 				if (ed1->v2->h > 1) ed1->v2->h--;
 			}
-			else ed1->v2->f = SF_VERT_UNKNOWN;
+			else {
+				ed1->v2->f = SF_VERT_UNKNOWN;
+			}
 
 			ed1 = nexted;
 		}
@@ -674,39 +679,67 @@ static int scanfill(ScanFillContext *sf_ctx, PolyFill *pf, const int flag)
 			}
 			else {
 				/* test rest of vertices */
+				ScanFillVertLink *best_sc = NULL;
+				float best_angle = 3.14f;
 				float miny;
+				bool firsttime = false;
+				
 				v1 = ed1->v2;
 				v2 = ed1->v1;
 				v3 = ed2->v2;
+				
 				/* this happens with a serial of overlapping edges */
 				if (v1 == v2 || v2 == v3) break;
-				/* printf("test verts %x %x %x\n", v1, v2, v3); */
+				
+				/* printf("test verts %d %d %d\n", v1->tmp.u, v2->tmp.u, v3->tmp.u); */
 				miny = min_ff(v1->xy[1], v3->xy[1]);
-				/*  miny = min_ff(v1->xy[1], v3->xy[1]); */
 				sc1 = sc + 1;
-				test = 0;
 
-				for (b = a + 1; b < verts; b++) {
+				for (b = a + 1; b < verts; b++, sc1++) {
 					if (sc1->vert->f == 0) {
 						if (sc1->vert->xy[1] <= miny) break;
 						if (testedgeside(v1->xy, v2->xy, sc1->vert->xy)) {
 							if (testedgeside(v2->xy, v3->xy, sc1->vert->xy)) {
 								if (testedgeside(v3->xy, v1->xy, sc1->vert->xy)) {
-									/* point in triangle */
-
-									test = 1;
-									break;
+									/* point is in triangle */
+									
+									/* because multiple points can be inside triangle (concave holes) */
+									/* we continue searching and pick the one with sharpest corner */
+									
+									if (best_sc == NULL) {
+										best_sc = sc1;
+										/* only need to continue checking with holes */
+										if ((flag & BLI_SCANFILL_CALC_HOLES) == 0) {
+											break;
+										}
+									}
+									else {
+										float angle;
+										
+										/* prevent angle calc for the simple cases only 1 vertex is found */
+										if (firsttime == false) {
+											best_angle = angle_v2v2v2(v2->co, v1->co, best_sc->vert->co);
+											firsttime = true;
+										}
+
+										angle = angle_v2v2v2(v2->co, v1->co, sc1->vert->co);
+										if (angle < best_angle) {
+											best_sc = sc1;
+											best_angle = angle;
+										}
+									}
+										
 								}
 							}
 						}
 					}
-					sc1++;
 				}
-				if (test) {
+					
+				if (best_sc) {
 					/* make new edge, and start over */
-					/* printf("add new edge %x %x and start again\n", v2, sc1->vert); */
+					/* printf("add new edge %d %d and start again\n", v2->tmp.u, best_sc->vert->tmp.u); */
 
-					ed3 = BLI_scanfill_edge_add(sf_ctx, v2, sc1->vert);
+					ed3 = BLI_scanfill_edge_add(sf_ctx, v2, best_sc->vert);
 					BLI_remlink(&sf_ctx->filledgebase, ed3);
 					BLI_insertlinkbefore((ListBase *)&(sc->edge_first), ed2, ed3);
 					ed3->v2->f = SF_VERT_UNKNOWN;
@@ -716,7 +749,7 @@ static int scanfill(ScanFillContext *sf_ctx, PolyFill *pf, const int flag)
 				}
 				else {
 					/* new triangle */
-					/* printf("add face %x %x %x\n", v1, v2, v3); */
+					/* printf("add face %d %d %d\n", v1->tmp.u, v2->tmp.u, v3->tmp.u); */
 					addfillface(sf_ctx, v1, v2, v3);
 					totface++;
 					BLI_remlink((ListBase *)&(sc->edge_first), ed1);
@@ -762,7 +795,6 @@ static int scanfill(ScanFillContext *sf_ctx, PolyFill *pf, const int flag)
 							ed3 = ed3->next;
 						}
 					}
-
 				}
 			}
 			/* test for loose edges */
diff --git a/source/blender/blenlib/intern/string_cursor_utf8.c b/source/blender/blenlib/intern/string_cursor_utf8.c
index 65763f21b0f..674d5ae5c8d 100644
--- a/source/blender/blenlib/intern/string_cursor_utf8.c
+++ b/source/blender/blenlib/intern/string_cursor_utf8.c
@@ -139,12 +139,17 @@ int BLI_str_cursor_step_prev_utf8(const char *str, size_t UNUSED(maxlen), int *p
 
 void BLI_str_cursor_step_utf8(const char *str, size_t maxlen,
                               int *pos, strCursorJumpDirection direction,
-                              strCursorJumpType jump)
+                              strCursorJumpType jump, bool use_init_step)
 {
 	const int pos_prev = *pos;
 
 	if (direction == STRCUR_DIR_NEXT) {
-		BLI_str_cursor_step_next_utf8(str, maxlen, pos);
+		if (use_init_step) {
+			BLI_str_cursor_step_next_utf8(str, maxlen, pos);
+		}
+		else {
+			BLI_assert(jump == STRCUR_JUMP_DELIM);
+		}
 
 		if (jump != STRCUR_JUMP_NONE) {
 			const strCursorDelimType delim_type = (*pos) < maxlen ? cursor_delim_type(&str[*pos]) : STRCUR_DELIM_NONE;
@@ -163,7 +168,12 @@ void BLI_str_cursor_step_utf8(const char *str, size_t maxlen,
 		}
 	}
 	else if (direction == STRCUR_DIR_PREV) {
-		BLI_str_cursor_step_prev_utf8(str, maxlen, pos);
+		if (use_init_step) {
+			BLI_str_cursor_step_prev_utf8(str, maxlen, pos);
+		}
+		else {
+			BLI_assert(jump == STRCUR_JUMP_DELIM);
+		}
 
 		if (jump != STRCUR_JUMP_NONE) {
 			const strCursorDelimType delim_type = (*pos) > 1 ? cursor_delim_type(&str[(*pos) - 1]) : STRCUR_DELIM_NONE;
diff --git a/source/blender/blenlib/intern/string_utf8.c b/source/blender/blenlib/intern/string_utf8.c
index bf98f2ae77c..9e0f9197ca3 100644
--- a/source/blender/blenlib/intern/string_utf8.c
+++ b/source/blender/blenlib/intern/string_utf8.c
@@ -114,7 +114,7 @@ int BLI_utf8_invalid_byte(const char *str, int length)
 
 		/* Check for valid bytes after the 2nd, if any; all must start 10 */
 		while (--ab > 0) {
-			if ((*(p+1) & 0xc0) != 0x80) goto utf8_error;
+			if ((*(p + 1) & 0xc0) != 0x80) goto utf8_error;
 			p++; /* do this after so we get usable offset - campbell */
 		}
 	}