Triangulate modifier

Useful for bump map baking where a consistent triangulation should be enforced when baking/exporting/importing, to avoid artifacts caused by a different triangulation of the mesh by that which was used for baking by internal/external tools. 

documentation is here http://wiki.blender.org/index.php/Dev:Ref/Release_Notes/2.65/More_Features

Will probably add some pictures too to demonstrate the issue that is solved more clearly.
Currently using the skin modifier icon, will soon change that.

Review by Brecht, thanks!

9 files changed, 194 insertions, 5 deletions

diff --git a/source/blender/blenkernel/intern/cdderivedmesh.c b/source/blender/blenkernel/intern/cdderivedmesh.c
index 3ade51d13eb..3181a0da1b0 100644
--- a/source/blender/blenkernel/intern/cdderivedmesh.c
+++ b/source/blender/blenkernel/intern/cdderivedmesh.c
@@ -2516,7 +2516,7 @@ void CDDM_calc_edges(DerivedMesh *dm)
 	EdgeHashIterator *ehi;
 	MPoly *mp = cddm->mpoly;
 	MLoop *ml;
-	MEdge *med;
+	MEdge *med, *origmed;
 	EdgeHash *eh = BLI_edgehash_new();
 	int v1, v2;
 	int *eindex;
@@ -2549,6 +2549,7 @@ void CDDM_calc_edges(DerivedMesh *dm)
 	CustomData_add_layer(&edgeData, CD_MEDGE, CD_CALLOC, NULL, numEdges);
 	CustomData_add_layer(&edgeData, CD_ORIGINDEX, CD_CALLOC, NULL, numEdges);
 
+	origmed = cddm->medge;
 	med = CustomData_get_layer(&edgeData, CD_MEDGE);
 	index = CustomData_get_layer(&edgeData, CD_ORIGINDEX);
 
@@ -2559,8 +2560,14 @@ void CDDM_calc_edges(DerivedMesh *dm)
 		BLI_edgehashIterator_getKey(ehi, &med->v1, &med->v2);
 		j = GET_INT_FROM_POINTER(BLI_edgehashIterator_getValue(ehi));
 
-		med->flag = ME_EDGEDRAW | ME_EDGERENDER;
-		*index = j == 0 ? ORIGINDEX_NONE : eindex[j - 1];
+		if(j == 0) {
+			med->flag = ME_EDGEDRAW | ME_EDGERENDER;
+			*index = ORIGINDEX_NONE;
+		}
+		else {
+			med->flag = ME_EDGEDRAW | ME_EDGERENDER | origmed[j - 1].flag;
+			*index = eindex[j - 1];
+		}
 
 		BLI_edgehashIterator_setValue(ehi, SET_INT_IN_POINTER(i));
 	}
diff --git a/source/blender/editors/space_outliner/outliner_draw.c b/source/blender/editors/space_outliner/outliner_draw.c
index 2c40e0e656d..4f640c579a5 100644
--- a/source/blender/editors/space_outliner/outliner_draw.c
+++ b/source/blender/editors/space_outliner/outliner_draw.c
@@ -1038,6 +1038,8 @@ static void tselem_draw_icon(uiBlock *block, int xmax, float x, float y, TreeSto
 						UI_icon_draw(x, y, ICON_MOD_WARP); break;
 					case eModifierType_Skin:
 						UI_icon_draw(x, y, ICON_MOD_SKIN); break;
+					case eModifierType_Triangulate:
+						UI_icon_draw(x, y, ICON_MOD_SKIN); break;
 
 					/* Default */
 					case eModifierType_None:
diff --git a/source/blender/editors/space_view3d/view3d_draw.c b/source/blender/editors/space_view3d/view3d_draw.c
index 7a1b97ff1d6..70c612d156b 100644
--- a/source/blender/editors/space_view3d/view3d_draw.c
+++ b/source/blender/editors/space_view3d/view3d_draw.c
@@ -1422,8 +1422,8 @@ ImBuf *view3d_read_backbuf(ViewContext *vc, short xmin, short ymin, short xmax,
 	
 	ibuf = IMB_allocImBuf((xmaxc - xminc + 1), (ymaxc - yminc + 1), 32, IB_rect);
 
-	view3d_validate_backbuf(vc); 
-	
+	view3d_validate_backbuf(vc);
+
 	glReadPixels(vc->ar->winrct.xmin + xminc,
 	             vc->ar->winrct.ymin + yminc,
 	             (xmaxc - xminc + 1),
diff --git a/source/blender/makesdna/DNA_modifier_types.h b/source/blender/makesdna/DNA_modifier_types.h
index 2c896e4893f..49b0534711e 100644
--- a/source/blender/makesdna/DNA_modifier_types.h
+++ b/source/blender/makesdna/DNA_modifier_types.h
@@ -76,6 +76,7 @@ typedef enum ModifierType {
 	eModifierType_Remesh            = 41,
 	eModifierType_Skin              = 42,
 	eModifierType_LaplacianSmooth   = 43,
+	eModifierType_Triangulate		= 44,
 	NUM_MODIFIER_TYPES
 } ModifierType;
 
@@ -1114,6 +1115,14 @@ enum {
 	MOD_SKIN_SMOOTH_SHADING = 1
 };
 
+/* Triangulate modifier */
+
+typedef struct TriangulateModifierData {
+	ModifierData modifier;
+	int beauty;
+	int pad;
+} TriangulateModifierData;
+
 /* Smooth modifier flags */
 #define MOD_LAPLACIANSMOOTH_X (1<<1)
 #define MOD_LAPLACIANSMOOTH_Y (1<<2)
diff --git a/source/blender/makesrna/intern/rna_modifier.c b/source/blender/makesrna/intern/rna_modifier.c
index 2e3f8feda44..1f6eb4af577 100644
--- a/source/blender/makesrna/intern/rna_modifier.c
+++ b/source/blender/makesrna/intern/rna_modifier.c
@@ -78,6 +78,7 @@ EnumPropertyItem modifier_type_items[] = {
 	{eModifierType_Skin, "SKIN", ICON_MOD_SKIN, "Skin", ""},
 	{eModifierType_Solidify, "SOLIDIFY", ICON_MOD_SOLIDIFY, "Solidify", ""},
 	{eModifierType_Subsurf, "SUBSURF", ICON_MOD_SUBSURF, "Subdivision Surface", ""},
+	{eModifierType_Triangulate, "TRIANGULATE", ICON_MOD_SKIN, "Triangulate", ""},
 	{0, "", 0, N_("Deform"), ""},
 	{eModifierType_Armature, "ARMATURE", ICON_MOD_ARMATURE, "Armature", ""},
 	{eModifierType_Cast, "CAST", ICON_MOD_CAST, "Cast", ""},
@@ -213,6 +214,8 @@ static StructRNA *rna_Modifier_refine(struct PointerRNA *ptr)
 			return &RNA_SkinModifier;
 		case eModifierType_LaplacianSmooth:
 			return &RNA_LaplacianSmoothModifier;
+		case eModifierType_Triangulate:
+			return &RNA_TriangulateModifier;
 		default:
 			return &RNA_Modifier;
 	}
@@ -3361,6 +3364,23 @@ static void rna_def_modifier_skin(BlenderRNA *brna)
 	RNA_def_property_update(prop, 0, "rna_Modifier_update");
 }
 
+static void rna_def_modifier_triangulate(BlenderRNA *brna)
+{
+	StructRNA *srna;
+	PropertyRNA *prop;
+
+	srna = RNA_def_struct(brna, "TriangulateModifier", "Modifier");
+	RNA_def_struct_ui_text(srna, "Triangulate Modifier", "Triangulate Mesh");
+	RNA_def_struct_sdna(srna, "TriangulateModifierData");
+	RNA_def_struct_ui_icon(srna, ICON_MOD_SKIN);
+
+	prop = RNA_def_property(srna, "use_beauty", PROP_BOOLEAN, PROP_NONE);
+	RNA_def_property_boolean_sdna(prop, NULL, "beauty", 1);
+	RNA_def_property_ui_text(prop, "Beauty Subdivide", "Subdivide across shortest diagonal");
+	RNA_def_property_update(prop, 0, "rna_Modifier_update");
+
+}
+
 void RNA_def_modifier(BlenderRNA *brna)
 {
 	StructRNA *srna;
@@ -3468,6 +3488,7 @@ void RNA_def_modifier(BlenderRNA *brna)
 	rna_def_modifier_remesh(brna);
 	rna_def_modifier_skin(brna);
 	rna_def_modifier_laplaciansmooth(brna);
+	rna_def_modifier_triangulate(brna);
 }
 
 #endif
diff --git a/source/blender/modifiers/CMakeLists.txt b/source/blender/modifiers/CMakeLists.txt
index 3a7066ff41a..cf3bb05849a 100644
--- a/source/blender/modifiers/CMakeLists.txt
+++ b/source/blender/modifiers/CMakeLists.txt
@@ -94,6 +94,7 @@ set(SRC
 	intern/MOD_weightvgedit.c
 	intern/MOD_weightvgmix.c
 	intern/MOD_weightvgproximity.c
+	intern/MOD_triangulate.c
 
 	MOD_modifiertypes.h
 	intern/MOD_boolean_util.h
diff --git a/source/blender/modifiers/MOD_modifiertypes.h b/source/blender/modifiers/MOD_modifiertypes.h
index a4817ff775d..290ba193567 100644
--- a/source/blender/modifiers/MOD_modifiertypes.h
+++ b/source/blender/modifiers/MOD_modifiertypes.h
@@ -76,6 +76,7 @@ extern ModifierTypeInfo modifierType_DynamicPaint;
 extern ModifierTypeInfo modifierType_Remesh;
 extern ModifierTypeInfo modifierType_Skin;
 extern ModifierTypeInfo modifierType_LaplacianSmooth;
+extern ModifierTypeInfo modifierType_Triangulate;
 
 /* MOD_util.c */
 void modifier_type_init(ModifierTypeInfo *types[]);
diff --git a/source/blender/modifiers/intern/MOD_triangulate.c b/source/blender/modifiers/intern/MOD_triangulate.c
new file mode 100644
index 00000000000..a9ec30067bf
--- /dev/null
+++ b/source/blender/modifiers/intern/MOD_triangulate.c
@@ -0,0 +1,147 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software  Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * Contributor(s): Antony Riakiotakis
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ *
+ */
+
+/** \file blender/modifiers/intern/MOD_triangulate.c
+ *  \ingroup modifiers
+ */
+#include <string.h>
+
+#include "MEM_guardedalloc.h"
+
+#include "DNA_mesh_types.h"
+#include "DNA_meshdata_types.h"
+#include "DNA_object_types.h"
+#include "DNA_modifier_types.h"
+
+#include "BLI_utildefines.h"
+#include "BLI_string.h"
+#include "BLI_array.h"
+
+#include "BKE_cdderivedmesh.h"
+#include "BKE_deform.h"
+#include "BKE_DerivedMesh.h"
+#include "BKE_mesh.h"
+#include "BKE_modifier.h"
+#include "BKE_tessmesh.h"
+
+#include "MOD_util.h"
+
+/* triangulation modifier, directly calls the bmesh operator */
+
+static DerivedMesh *triangulate(DerivedMesh *dm, char use_beauty)
+{
+	DerivedMesh *result;
+	BMesh *bm;
+
+	bm = DM_to_bmesh(dm);
+
+	BMO_push(bm, NULL);
+	BMO_op_callf(bm, BMO_FLAG_DEFAULTS,
+				  "triangulate faces=%af use_beauty=%b", use_beauty);
+
+	BMO_pop(bm);
+
+	result = CDDM_from_bmesh(bm, FALSE);
+	BM_mesh_free(bm);
+
+	CDDM_calc_edges(result);
+	CDDM_calc_normals(result);
+
+	return result;
+}
+
+
+static void initData(ModifierData *md)
+{
+	TriangulateModifierData *tmd = (TriangulateModifierData *)md;
+
+	/* Enable in editmode by default */
+	md->mode |= eModifierMode_Editmode;
+	tmd->beauty = TRUE;
+}
+
+
+static void copyData(ModifierData *md, ModifierData *target)
+{
+	TriangulateModifierData *smd = (TriangulateModifierData *) md;
+	TriangulateModifierData *tsmd = (TriangulateModifierData *) target;
+
+	*tsmd = *smd;
+}
+
+static DerivedMesh *applyModifierEM(ModifierData *md,
+                                    Object *UNUSED(ob),
+                                    struct BMEditMesh *UNUSED(em),
+                                    DerivedMesh *dm)
+{
+	TriangulateModifierData *tmd = (TriangulateModifierData *)md;
+	DerivedMesh *result;
+	if (!(result = triangulate(dm, tmd->beauty))) {
+		return dm;
+	}
+
+	return result;
+}
+
+static DerivedMesh *applyModifier(ModifierData *md,
+                                  Object *UNUSED(ob),
+                                  DerivedMesh *dm,
+                                  ModifierApplyFlag UNUSED(flag))
+{
+	TriangulateModifierData *tmd = (TriangulateModifierData *)md;
+	DerivedMesh *result;
+	if(!(result = triangulate(dm, tmd->beauty))) {
+		return dm;
+	}
+
+	return result;
+}
+
+ModifierTypeInfo modifierType_Triangulate = {
+	/* name */              "Triangulate",
+	/* structName */        "TriangulateModifierData",
+	/* structSize */        sizeof(TriangulateModifierData),
+	/* type */              eModifierTypeType_Constructive,
+	/* flags */             eModifierTypeFlag_AcceptsMesh |
+							eModifierTypeFlag_SupportsEditmode |
+							eModifierTypeFlag_SupportsMapping |
+							eModifierTypeFlag_EnableInEditmode |
+							eModifierTypeFlag_AcceptsCVs,
+
+	/* copyData */          copyData,
+	/* deformVerts */       NULL,
+	/* deformMatrices */    NULL,
+	/* deformVertsEM */     NULL,
+	/* deformMatricesEM */  NULL,
+	/* applyModifier */     applyModifier,
+	/* applyModifierEM */   applyModifierEM,
+	/* initData */          initData,
+	/* requiredDataMask */  NULL, //requiredDataMask,
+	/* freeData */          NULL,
+	/* isDisabled */        NULL,
+	/* updateDepgraph */    NULL,
+	/* dependsOnTime */     NULL,
+	/* dependsOnNormals */	NULL,
+	/* foreachObjectLink */ NULL,
+	/* foreachIDLink */     NULL,
+};
diff --git a/source/blender/modifiers/intern/MOD_util.c b/source/blender/modifiers/intern/MOD_util.c
index 3b769a30994..a27d5e5e03b 100644
--- a/source/blender/modifiers/intern/MOD_util.c
+++ b/source/blender/modifiers/intern/MOD_util.c
@@ -278,5 +278,6 @@ void modifier_type_init(ModifierTypeInfo *types[])
 	INIT_TYPE(Remesh);
 	INIT_TYPE(Skin);
 	INIT_TYPE(LaplacianSmooth);
+	INIT_TYPE(Triangulate);
 #undef INIT_TYPE
 }