- added wave modifier & removed old wave effect

 - added decimate modifier & removed old decimate interface
   (currently lacks warning about destroying data, and there needs
   to be a way for modifiers to return errors back to the interface)
 - allow applyModifier to return NULL to indicate error
 - unfortunately new decimate modifier means it does not know exact
   number of faces in mesh (other modifiers may come before) and so
   instead interface uses a percentage. if people need exact face
   count slider then I will have to think of some hack to fit this
   in. note that it does display the output face count so its possible
   to tweak the pct to get what you want regardless.
 - removed python Wave object

If you are bored now how much easier it is to implement something
like decimate as a modifier. Very few changes to interface, very
few entry points.

6 files changed, 258 insertions, 99 deletions

diff --git a/source/blender/blenkernel/BKE_effect.h b/source/blender/blenkernel/BKE_effect.h
index a1bc5967b0b..f371220bab5 100644
--- a/source/blender/blenkernel/BKE_effect.h
+++ b/source/blender/blenkernel/BKE_effect.h
@@ -53,8 +53,6 @@ void deselectall_eff(struct Object *ob);
 struct PartEff *give_parteff(struct Object *ob);
 void where_is_particle(struct PartEff *paf, struct Particle *pa, float ctime, float *vec);
 void build_particle_system(struct Object *ob);
-void init_wave_deform(struct WaveEff *wav);
-void calc_wave_deform(struct WaveEff *wav, float ctime, float *co);
 
 /* particle deflector */
 #define PE_WIND_AS_SPEED 0x00000001
diff --git a/source/blender/blenkernel/intern/DerivedMesh.c b/source/blender/blenkernel/intern/DerivedMesh.c
index e33de2baf8d..3b00fb034a0 100644
--- a/source/blender/blenkernel/intern/DerivedMesh.c
+++ b/source/blender/blenkernel/intern/DerivedMesh.c
@@ -1309,14 +1309,18 @@ static void mesh_calc_modifiers(Object *ob, float (*inputVertexCos)[3], DerivedM
 				 * by the modifier apply function, which will also free the DerivedMesh if
 				 * it exists.
 				 */
-			dm = mti->applyModifier(md, ob, dm, deformedVerts, useRenderParams, !inputVertexCos);
+			DerivedMesh *ndm = mti->applyModifier(md, ob, dm, deformedVerts, useRenderParams, !inputVertexCos);
 
-			if (deformedVerts) {
-				if (deformedVerts!=inputVertexCos) {
-					MEM_freeN(deformedVerts);
+			if (ndm) {
+				dm = ndm;
+
+				if (deformedVerts) {
+					if (deformedVerts!=inputVertexCos) {
+						MEM_freeN(deformedVerts);
+					}
+					deformedVerts = NULL;
 				}
-				deformedVerts = NULL;
-			}
+			} 
 		}
 	}
 
diff --git a/source/blender/blenkernel/intern/deform.c b/source/blender/blenkernel/intern/deform.c
index 91e8f3e2b7b..c99b3986059 100644
--- a/source/blender/blenkernel/intern/deform.c
+++ b/source/blender/blenkernel/intern/deform.c
@@ -249,23 +249,6 @@ void mesh_modifier(Object *ob, float (**vertexCos_r)[3])
 		}
 	}
 		
-	if(ob->effect.first) {
-		WaveEff *wav;
-		float ctime = bsystem_time(ob, 0, (float)G.scene->r.cfra, 0.0);
-		int a;
-	
-		for (wav= ob->effect.first; wav; wav= wav->next) {
-			if(wav->type==EFF_WAVE) {
-				if (!vertexCos) vertexCos = mesh_getVertexCos(me, NULL);
-				init_wave_deform(wav);
-
-				for(a=0; a<me->totvert; a++) {
-					calc_wave_deform(wav, ctime, vertexCos[a]);
-				}
-			}
-		}
-	}
-
 	if((ob->softflag & OB_SB_ENABLE) && !(ob->softflag & OB_SB_POSTDEF)) {
 		if (!vertexCos) vertexCos = mesh_getVertexCos(me, NULL);
 		sbObjectStep(ob, (float)G.scene->r.cfra, vertexCos);
diff --git a/source/blender/blenkernel/intern/effect.c b/source/blender/blenkernel/intern/effect.c
index 00869089155..af23cf70ce9 100644
--- a/source/blender/blenkernel/intern/effect.c
+++ b/source/blender/blenkernel/intern/effect.c
@@ -84,7 +84,6 @@ Effect *add_effect(int type)
 {
 	Effect *eff=0;
 	PartEff *paf;
-	WaveEff *wav;
 	int a;
 	
 	switch(type) {
@@ -108,21 +107,6 @@ Effect *add_effect(int type)
 		paf->nabla= 0.05f;
 		
 		break;
-		
-	case EFF_WAVE:
-		wav= MEM_callocN(sizeof(WaveEff), "neweff");
-		eff= (Effect *)wav;
-		
-		wav->flag |= (WAV_X+WAV_Y+WAV_CYCL);
-		
-		wav->height= 0.5f;
-		wav->width= 1.5f;
-		wav->speed= 0.5f;
-		wav->narrow= 1.5f;
-		wav->lifetime= 0.0f;
-		wav->damp= 10.0f;
-		
-		break;
 	}
 	
 	eff->type= eff->buttype= type;
@@ -1403,62 +1387,6 @@ void build_particle_system(Object *ob)
 	rng_free(rng);
 }
 
-/* ************* WAVE **************** */
-
-void init_wave_deform(WaveEff *wav) {
-	wav->minfac= (float)(1.0/exp(wav->width*wav->narrow*wav->width*wav->narrow));
-	if(wav->damp==0) wav->damp= 10.0f;
-}
-
-void calc_wave_deform(WaveEff *wav, float ctime, float *co)
-{
-	/* co is in local coords */
-	float lifefac, x, y, amplit;
-	
-	/* actually this should not happen */
-	if((wav->flag & (WAV_X+WAV_Y))==0) return;	
-
-	lifefac= wav->height;
-	
-	if( wav->lifetime!=0.0) {
-		x= ctime - wav->timeoffs;
-		if(x>wav->lifetime) {
-			
-			lifefac= x-wav->lifetime;
-			
-			if(lifefac > wav->damp) lifefac= 0.0;
-			else lifefac= (float)(wav->height*(1.0 - sqrt(lifefac/wav->damp)));
-		}
-	}
-	if(lifefac==0.0) return;
-
-	x= co[0]-wav->startx;
-	y= co[1]-wav->starty;
-
-	if(wav->flag & WAV_X) {
-		if(wav->flag & WAV_Y) amplit= (float)sqrt( (x*x + y*y));
-		else amplit= x;
-	}
-	else amplit= y;
-	
-	/* this way it makes nice circles */
-	amplit-= (ctime-wav->timeoffs)*wav->speed;
-
-	if(wav->flag & WAV_CYCL) {
-		amplit = (float)fmod(amplit-wav->width, 2.0*wav->width) + wav->width;
-	}
-
-	/* GAUSSIAN */
-	
-	if(amplit> -wav->width && amplit<wav->width) {
-	
-		amplit = amplit*wav->narrow;
-		amplit= (float)(1.0/exp(amplit*amplit) - wav->minfac);
-
-		co[2]+= lifefac*amplit;
-	}
-}
-
 int SoftBodyDetectCollision(float opco[3], float npco[3], float colco[3],
 							float facenormal[3], float *damp, float force[3], int mode,
 							float cur_time, unsigned int par_layer,struct Object *vertexowner)
diff --git a/source/blender/blenkernel/intern/mesh.c b/source/blender/blenkernel/intern/mesh.c
index 65ac43739da..41e9d0b4c70 100644
--- a/source/blender/blenkernel/intern/mesh.c
+++ b/source/blender/blenkernel/intern/mesh.c
@@ -236,8 +236,6 @@ Mesh *copy_mesh(Mesh *me)
 	men->key= copy_key(me->key);
 	if(men->key) men->key->from= (ID *)men;
 	
-	men->decimated = NULL;
-
 	return men;
 }
 
diff --git a/source/blender/blenkernel/intern/modifier.c b/source/blender/blenkernel/intern/modifier.c
index 064248611cd..f47cbae9455 100644
--- a/source/blender/blenkernel/intern/modifier.c
+++ b/source/blender/blenkernel/intern/modifier.c
@@ -1,4 +1,5 @@
 #include "string.h"
+#include "math.h"
 
 #include "BLI_blenlib.h"
 #include "BLI_rand.h"
@@ -9,6 +10,7 @@
 #include "DNA_meshdata_types.h"
 #include "DNA_modifier_types.h"
 #include "DNA_object_types.h"
+#include "DNA_effect_types.h"
 #include "DNA_scene_types.h"
 #include "BLI_editVert.h"
 
@@ -23,6 +25,9 @@
 #include "BKE_mesh.h"
 #include "depsgraph_private.h"
 
+#include "LOD_DependKludge.h"
+#include "LOD_decimation.h"
+
 #include "CCGSubSurf.h"
 
 /***/
@@ -704,6 +709,235 @@ static void *mirrorModifier_applyModifierEM(ModifierData *md, Object *ob, void *
 	}
 }
 
+/* Decimate */
+
+static void decimateModifier_initData(ModifierData *md)
+{
+	DecimateModifierData *dmd = (DecimateModifierData*) md;
+
+	dmd->percent = 1.0;
+}
+
+static void *decimateModifier_applyModifier(ModifierData *md, Object *ob, void *derivedData, float (*vertexCos)[3], int useRenderParams, int isFinalCalc)
+{
+	DecimateModifierData *dmd = (DecimateModifierData*) md;
+	DerivedMesh *dm = derivedData;
+	Mesh *me = ob->data;
+	MVert *mvert;
+	MFace *mface;
+	DispListMesh *ndlm=NULL, *dlm=NULL;
+	LOD_Decimation_Info lod;
+	int totvert, totface;
+	int *tib=NULL;
+	int a, numTris;
+
+	if (dm) {
+		dlm = dm->convertToDispListMesh(dm);
+		mvert = dlm->mvert;
+		mface = dlm->mface;
+		totvert = dlm->totvert;
+		totface = dlm->totface;
+	} else {
+		mvert = me->mvert;
+		mface = me->mface;
+		totvert = me->totvert;
+		totface = me->totface;
+	}
+
+	numTris = 0;
+	for (a=0; a<totface; a++) {
+		MFace *mf = &mface[a];
+		if (mf->v3) {
+			numTris++;
+			if (mf->v4) numTris++;
+		}
+	}
+
+	if(numTris<3) {
+		// ("You must have more than 3 input faces selected.");
+		return NULL;
+	}
+
+	lod.vertex_buffer= MEM_mallocN(3*sizeof(float)*totvert, "vertices");
+	lod.vertex_normal_buffer= MEM_mallocN(3*sizeof(float)*totvert, "normals");
+	lod.triangle_index_buffer= MEM_mallocN(3*sizeof(int)*numTris, "trias");
+	lod.vertex_num= me->totvert;
+	lod.face_num= numTris;
+
+	for(a=0; a<totvert; a++) {
+		MVert *mv = &mvert[a];
+		float *vbCo = &lod.vertex_buffer[a*3];
+		float *vbNo = &lod.vertex_normal_buffer[a*3];
+
+		if (vertexCos) { // XXX normals wrong
+			VECCOPY(vbCo, vertexCos[a]);
+		} else {
+			VECCOPY(vbCo, mv->co);
+		}
+
+		vbNo[0] = mv->no[0]/32767.0f;
+		vbNo[1] = mv->no[1]/32767.0f;
+		vbNo[2] = mv->no[2]/32767.0f;
+	}
+
+	numTris = 0;
+	for(a=0; a<totface; a++) {
+		MFace *mf = &mface[a];
+
+		if(mf->v3) {
+			int *tri = &lod.triangle_index_buffer[3*numTris++];
+			tri[0]= mf->v1;
+			tri[1]= mf->v2;
+			tri[2]= mf->v3;
+
+			if(mf->v4) {
+				tri = &lod.triangle_index_buffer[3*numTris++];
+				tri[0]= mf->v1;
+				tri[1]= mf->v3;
+				tri[2]= mf->v4;
+			}
+		}
+	}
+
+	dmd->faceCount = 0;
+	if(LOD_LoadMesh(&lod) ) {
+		if( LOD_PreprocessMesh(&lod) ) {
+
+			/* we assume the decim_faces tells how much to reduce */
+
+			while(lod.face_num > numTris*dmd->percent) {
+				if( LOD_CollapseEdge(&lod)==0) break;
+			}
+
+			ndlm= MEM_callocN(sizeof(DispListMesh), "dispmesh");
+			ndlm->mvert= MEM_callocN(lod.vertex_num*sizeof(MVert), "mvert");
+			ndlm->mface= MEM_callocN(lod.face_num*sizeof(MFace), "mface");
+			ndlm->totvert= lod.vertex_num;
+			ndlm->totface= dmd->faceCount = lod.face_num;
+
+			for(a=0; a<lod.vertex_num; a++) {
+				MVert *mv = &ndlm->mvert[a];
+				float *vbCo = &lod.vertex_buffer[a*3];
+				
+				VECCOPY(mv->co, vbCo);
+			}
+
+			for(a=0; a<lod.face_num; a++) {
+				MFace *mf = &ndlm->mface[a];
+				int *tri = &lod.triangle_index_buffer[a*3];
+				mf->v1 = tri[0];
+				mf->v2 = tri[1];
+				mf->v3 = tri[2];
+				test_index_mface(mf, 3);
+			}
+		}
+		else {
+			// No memory
+		}
+
+		LOD_FreeDecimationData(&lod);
+	}
+	else {
+		// Non-manifold mesh
+	}
+
+	MEM_freeN(lod.vertex_buffer);
+	MEM_freeN(lod.vertex_normal_buffer);
+	MEM_freeN(lod.triangle_index_buffer);
+
+	if (dlm) displistmesh_free(dlm);
+
+	if (ndlm) {
+		if (dm) dm->release(dm);
+
+		mesh_calc_normals(ndlm->mvert, ndlm->totvert, ndlm->mface, ndlm->totface, &ndlm->nors);
+
+		return derivedmesh_from_displistmesh(ndlm);
+	} else {
+		return NULL;
+	}
+}
+
+/* Wave */
+
+static void waveModifier_initData(ModifierData *md) 
+{
+	WaveModifierData *wmd = (WaveModifierData*) md; // whadya know, moved here from Iraq
+		
+	wmd->flag |= (WAV_X+WAV_Y+WAV_CYCL);
+	
+	wmd->height= 0.5f;
+	wmd->width= 1.5f;
+	wmd->speed= 0.5f;
+	wmd->narrow= 1.5f;
+	wmd->lifetime= 0.0f;
+	wmd->damp= 10.0f;
+}
+
+static int waveModifier_dependsOnTime(ModifierData *md)
+{
+	return 1;
+}
+
+static void waveModifier_deformVerts(ModifierData *md, Object *ob, void *derivedData, float (*vertexCos)[3], int numVerts)
+{
+	WaveModifierData *wmd = (WaveModifierData*) md;
+	float ctime = bsystem_time(ob, 0, (float)G.scene->r.cfra, 0.0);
+	float minfac = (float)(1.0/exp(wmd->width*wmd->narrow*wmd->width*wmd->narrow));
+	float lifefac = wmd->height;
+
+	if(wmd->damp==0) wmd->damp= 10.0f;
+
+	if(wmd->lifetime!=0.0) {
+		float x= ctime - wmd->timeoffs;
+
+		if(x>wmd->lifetime) {
+			lifefac= x-wmd->lifetime;
+			
+			if(lifefac > wmd->damp) lifefac= 0.0;
+			else lifefac= (float)(wmd->height*(1.0 - sqrt(lifefac/wmd->damp)));
+		}
+	}
+
+	if(lifefac!=0.0) {
+		int i;
+
+		for (i=0; i<numVerts; i++) {
+			float *co = vertexCos[i];
+			float x= co[0]-wmd->startx;
+			float y= co[1]-wmd->starty;
+			float amplit;
+
+			if(wmd->flag & WAV_X) {
+				if(wmd->flag & WAV_Y) amplit= (float)sqrt( (x*x + y*y));
+				else amplit= x;
+			}
+			else amplit= y;
+			
+			/* this way it makes nice circles */
+			amplit-= (ctime-wmd->timeoffs)*wmd->speed;
+
+			if(wmd->flag & WAV_CYCL) {
+				amplit = (float)fmod(amplit-wmd->width, 2.0*wmd->width) + wmd->width;
+			}
+
+				/* GAUSSIAN */
+			if(amplit> -wmd->width && amplit<wmd->width) {
+				amplit = amplit*wmd->narrow;
+				amplit= (float)(1.0/exp(amplit*amplit) - minfac);
+
+				co[2]+= lifefac*amplit;
+			}
+		}
+	}
+}
+
+static void waveModifier_deformVertsEM(ModifierData *md, Object *ob, void *editData, void *derivedData, float (*vertexCos)[3], int numVerts)
+{
+	waveModifier_deformVerts(md, ob, NULL, vertexCos, numVerts);
+}
+
+
 /***/
 
 static ModifierTypeInfo typeArr[NUM_MODIFIER_TYPES];
@@ -773,6 +1007,20 @@ ModifierTypeInfo *modifierType_get_info(ModifierType type)
 		mti->applyModifier = mirrorModifier_applyModifier;
 		mti->applyModifierEM = mirrorModifier_applyModifierEM;
 
+		mti = INIT_TYPE(Decimate);
+		mti->type = eModifierTypeType_Nonconstructive;
+		mti->flags = eModifierTypeFlag_AcceptsMesh;
+		mti->initData = decimateModifier_initData;
+		mti->applyModifier = decimateModifier_applyModifier;
+
+		mti = INIT_TYPE(Wave);
+		mti->type = eModifierTypeType_OnlyDeform;
+		mti->flags = eModifierTypeFlag_AcceptsCVs | eModifierTypeFlag_SupportsEditmode;
+		mti->initData = waveModifier_initData;
+		mti->dependsOnTime = waveModifier_dependsOnTime;
+		mti->deformVerts = waveModifier_deformVerts;
+		mti->deformVertsEM = waveModifier_deformVertsEM;
+
 		typeArrInit = 0;
 #undef INIT_TYPE
 	}