Integration of the Google Summer of Code Modifier Stack Upgrade project. The

main features are:
* Modifiers can now be in any order in the modifier stack
* DerivedMesh now has a standard framework for custom element data to be passed
  through the stack with mesh data (being copied and interpolated as
  appropriate), so modifiers can access whatever data they need
* The modifier stack code has been refactored and a number of bugs have been
  removed
* The EdgeSplit modifier has been added:
  http://mediawiki.blender.org/index.php/BlenderDev/EdgeSplitModifier
* The DerivedMesh modifier has been added:
  http://mediawiki.blender.org/index.php/BlenderDev/DisplaceModifier
* The UVProject modifier has been added:
  http://mediawiki.blender.org/index.php/BlenderDev/UVProjectModifier

For more info, see:
http://mediawiki.blender.org/index.php/User:Artificer/ModifierStackUpgrade
(currently undergoing reorganisation)

1 files changed, 294 insertions, 94 deletions

diff --git a/source/blender/blenkernel/BKE_DerivedMesh.h b/source/blender/blenkernel/BKE_DerivedMesh.h
index 8b2882ca4e6..fe371c32529 100644
--- a/source/blender/blenkernel/BKE_DerivedMesh.h
+++ b/source/blender/blenkernel/BKE_DerivedMesh.h
@@ -45,142 +45,342 @@
  *    conversion to DLM.
  */
 
+#include "BKE_customdata.h"
+
 struct MVert;
+struct MEdge;
+struct MFace;
 struct TFace;
 struct Object;
+struct Mesh;
 struct EditMesh;
 struct DispListMesh;
 struct ModifierData;
 
+/* number of sub-elements each mesh element has (for interpolation) */
+#define SUB_ELEMS_VERT 0
+#define SUB_ELEMS_EDGE 2
+#define SUB_ELEMS_FACE 4
+
 typedef struct DerivedMesh DerivedMesh;
 struct DerivedMesh {
+	/* custom data for verts, edges & faces */
+	CustomData vertData, edgeData, faceData;
+
 	/* Misc. Queries */
 
-		/* Also called in Editmode */
+	/* Also called in Editmode */
 	int (*getNumVerts)(DerivedMesh *dm);
-		/* Also called in Editmode */
+	/* Also called in Editmode */
 	int (*getNumFaces)(DerivedMesh *dm);
 
-		/* Iterate over each mapped vertex in the derived mesh, calling the
-		 * given function with the original vert and the mapped vert's new
-		 * coordinate and normal. For historical reasons the normal can be
-		 * passed as a float or short array, only one should be non-NULL.
-		 */
-	void (*foreachMappedVert)(DerivedMesh *dm, void (*func)(void *userData, int index, float *co, float *no_f, short *no_s), void *userData);
-
-		/* Iterate over each mapped vertex in the derived mesh, calling the
-		 * given function with the original vert and the mapped edge's new
-		 * coordinates.
-		 */
-	void (*foreachMappedEdge)(DerivedMesh *dm, void (*func)(void *userData, int index, float *v0co, float *v1co), void *userData);
-
-		/* Iterate over each mapped face in the derived mesh, calling the
-		 * given function with the original face and the mapped face's (or
-		 * faces') center and normal.
-		 */
-	void (*foreachMappedFaceCenter)(DerivedMesh *dm, void (*func)(void *userData, int index, float *cent, float *no), void *userData);
-
-		/* Convert to new DispListMesh, should be free'd by caller.
-		 *
-		 * If allowShared is true then the caller is committing to not free'ng
-		 * the DerivedMesh before free'ng the DispListMesh, which means that
-		 * certain fields of the returned DispListMesh can safely be share with
-		 * the DerivedMesh's internal data.
-		 */
-	struct DispListMesh* (*convertToDispListMesh)(DerivedMesh *dm, int allowShared);
-
-		/* Iterate over all vertex points, calling DO_MINMAX with given args.
-		 *
-		 * Also called in Editmode
-		 */
+	int (*getNumEdges)(DerivedMesh *dm);
+
+	/* copy a single vert/edge/face from the derived mesh into
+	 * *{vert/edge/face}_r
+	 */
+	void (*getVert)(DerivedMesh *dm, int index, struct MVert *vert_r);
+	void (*getEdge)(DerivedMesh *dm, int index, struct MEdge *edge_r);
+	void (*getFace)(DerivedMesh *dm, int index, struct MFace *face_r);
+
+	/* copy all verts/edges/faces from the derived mesh into
+	 * *{vert/edge/face}_r (must point to a buffer large enough)
+	 */
+	void (*getVertArray)(DerivedMesh *dm, struct MVert *vert_r);
+	void (*getEdgeArray)(DerivedMesh *dm, struct MEdge *edge_r);
+	void (*getFaceArray)(DerivedMesh *dm, struct MFace *face_r);
+
+	/* return a copy of all verts/edges/faces from the derived mesh
+	 * it is the caller's responsibility to free the returned pointer
+	 */
+	struct MVert *(*dupVertArray)(DerivedMesh *dm);
+	struct MEdge *(*dupEdgeArray)(DerivedMesh *dm);
+	struct MFace *(*dupFaceArray)(DerivedMesh *dm);
+
+	/* return a pointer to a single element of vert/edge/face custom data
+	 * from the derived mesh (this gives a pointer to the actual data, not
+	 * a copy)
+	 */
+	void *(*getVertData)(DerivedMesh *dm, int index, int type);
+	void *(*getEdgeData)(DerivedMesh *dm, int index, int type);
+	void *(*getFaceData)(DerivedMesh *dm, int index, int type);
+
+	/* return a pointer to the entire array of vert/edge/face custom data
+	 * from the derived mesh (this gives a pointer to the actual data, not
+	 * a copy)
+	 */
+	void *(*getVertDataArray)(DerivedMesh *dm, int type);
+	void *(*getEdgeDataArray)(DerivedMesh *dm, int type);
+	void *(*getFaceDataArray)(DerivedMesh *dm, int type);
+
+	/* Iterate over each mapped vertex in the derived mesh, calling the
+	 * given function with the original vert and the mapped vert's new
+	 * coordinate and normal. For historical reasons the normal can be
+	 * passed as a float or short array, only one should be non-NULL.
+	 */
+	void (*foreachMappedVert)(
+	                      DerivedMesh *dm,
+	                      void (*func)(void *userData, int index, float *co,
+	                                   float *no_f, short *no_s),
+	                      void *userData);
+
+	/* Iterate over each mapped edge in the derived mesh, calling the
+	 * given function with the original edge and the mapped edge's new
+	 * coordinates.
+	 */
+	void (*foreachMappedEdge)(DerivedMesh *dm,
+	                          void (*func)(void *userData, int index,
+	                                       float *v0co, float *v1co),
+	                          void *userData);
+
+	/* Iterate over each mapped face in the derived mesh, calling the
+	 * given function with the original face and the mapped face's (or
+	 * faces') center and normal.
+	 */
+	void (*foreachMappedFaceCenter)(DerivedMesh *dm,
+	                                void (*func)(void *userData, int index,
+	                                             float *cent, float *no),
+	                                void *userData);
+
+	/* Convert to new DispListMesh, should be free'd by caller.
+	 *
+	 * If allowShared is true then the caller is committing to not free'ng
+	 * the DerivedMesh before free'ng the DispListMesh, which means that
+	 * certain fields of the returned DispListMesh can safely be share with
+	 * the DerivedMesh's internal data.
+	 */
+	struct DispListMesh* (*convertToDispListMesh)(DerivedMesh *dm,
+	                                              int allowShared);
+
+	/* Iterate over all vertex points, calling DO_MINMAX with given args.
+	 *
+	 * Also called in Editmode
+	 */
 	void (*getMinMax)(DerivedMesh *dm, float min_r[3], float max_r[3]);
 
 	/* Direct Access Operations */
 	/*  o Can be undefined */
 	/*  o Must be defined for modifiers that only deform however */
-			
-		/* Get vertex location, undefined if index is not valid */
+
+	/* Get vertex location, undefined if index is not valid */
 	void (*getVertCo)(DerivedMesh *dm, int index, float co_r[3]);
 
-		/* Fill the array (of length .getNumVerts()) with all vertex locations  */
+	/* Fill the array (of length .getNumVerts()) with all vertex locations */
 	void (*getVertCos)(DerivedMesh *dm, float (*cos_r)[3]);
 
-		/* Get vertex normal, undefined if index is not valid */
+	/* Get vertex normal, undefined if index is not valid */
 	void (*getVertNo)(DerivedMesh *dm, int index, float no_r[3]);
 
 	/* Drawing Operations */
 
-			/* Draw all vertices as bgl points (no options) */
+	/* Draw all vertices as bgl points (no options) */
 	void (*drawVerts)(DerivedMesh *dm);
 
-			/* Draw edges in the UV mesh (if exists) */
+	/* Draw edges in the UV mesh (if exists) */
 	void (*drawUVEdges)(DerivedMesh *dm);
 
-			/* Draw all edges as lines (no options) 
-			 *
-			 * Also called for *final* editmode DerivedMeshes
-			 */
+	/* Draw all edges as lines (no options) 
+	 *
+	 * Also called for *final* editmode DerivedMeshes
+	 */
 	void (*drawEdges)(DerivedMesh *dm, int drawLooseEdges);
 	
-			/* Draw all loose edges (edges w/ no adjoining faces) */
+	/* Draw all loose edges (edges w/ no adjoining faces) */
 	void (*drawLooseEdges)(DerivedMesh *dm);
 
-			/* Draw all faces
-			 *  o Set face normal or vertex normal based on inherited face flag
-			 *  o Use inherited face material index to call setMaterial
-			 *  o Only if setMaterial returns true
-			 *
-			 * Also called for *final* editmode DerivedMeshes
-			 */
+	/* Draw all faces
+	 *  o Set face normal or vertex normal based on inherited face flag
+	 *  o Use inherited face material index to call setMaterial
+	 *  o Only if setMaterial returns true
+	 *
+	 * Also called for *final* editmode DerivedMeshes
+	 */
 	void (*drawFacesSolid)(DerivedMesh *dm, int (*setMaterial)(int));
 
-			/* Draw all faces
-			 *  o If useTwoSided, draw front and back using col arrays
-			 *  o col1,col2 are arrays of length numFace*4 of 4 component colors
-			 *    in ABGR format, and should be passed as per-face vertex color.
-			 */
-	void (*drawFacesColored)(DerivedMesh *dm, int useTwoSided, unsigned char *col1, unsigned char *col2);
-
-			/* Draw all faces using TFace 
-			 *  o Drawing options too complicated to enumerate, look at code.
-			 */
-	void (*drawFacesTex)(DerivedMesh *dm, int (*setDrawOptions)(struct TFace *tface, int matnr));
-
-			/* Draw mapped faces (no color, or texture)
-			 *  o Only if !setDrawOptions or setDrawOptions(userData, mapped-face-index, drawSmooth_r) returns true
-			 *
-			 * If drawSmooth is set to true then vertex normals should be set and glShadeModel
-			 * called with GL_SMOOTH. Otherwise the face normal should be set and glShadeModel
-			 * called with GL_FLAT.
-			 *
-			 * The setDrawOptions is allowed to not set drawSmooth (for example, when lighting
-			 * is disabled), in which case the implementation should draw as smooth shaded.
-			 */
-	void (*drawMappedFaces)(DerivedMesh *dm, int (*setDrawOptions)(void *userData, int index, int *drawSmooth_r), void *userData, int useColors);
-
-			/* Draw mapped faces using TFace 
-			 *  o Drawing options too complicated to enumerate, look at code.
-			 */
-	void (*drawMappedFacesTex)(DerivedMesh *dm, int (*setDrawOptions)(void *userData, int index), void *userData);
-
-			/* Draw mapped edges as lines
-			 *  o Only if !setDrawOptions or setDrawOptions(userData, mapped-edge) returns true
-			 */
-	void (*drawMappedEdges)(DerivedMesh *dm, int (*setDrawOptions)(void *userData, int index), void *userData);
-
-			/* Draw mapped edges as lines with interpolation values
-			 *  o Only if !setDrawOptions or setDrawOptions(userData, mapped-edge, mapped-v0, mapped-v1, t) returns true
-			 *
-			 * NOTE: This routine is optional!
-			 */
+	/* Draw all faces
+	 *  o If useTwoSided, draw front and back using col arrays
+	 *  o col1,col2 are arrays of length numFace*4 of 4 component colors
+	 *    in ABGR format, and should be passed as per-face vertex color.
+	 */
+	void (*drawFacesColored)(DerivedMesh *dm, int useTwoSided,
+	                         unsigned char *col1, unsigned char *col2);
+
+	/* Draw all faces using TFace 
+	 *  o Drawing options too complicated to enumerate, look at code.
+	 */
+	void (*drawFacesTex)(DerivedMesh *dm,
+	                     int (*setDrawOptions)(struct TFace *tface, int matnr));
+
+	/* Draw mapped faces (no color, or texture)
+	 *  o Only if !setDrawOptions or
+	 *    setDrawOptions(userData, mapped-face-index, drawSmooth_r)
+	 *    returns true
+	 *
+	 * If drawSmooth is set to true then vertex normals should be set and
+	 * glShadeModel called with GL_SMOOTH. Otherwise the face normal should
+	 * be set and glShadeModel called with GL_FLAT.
+	 *
+	 * The setDrawOptions is allowed to not set drawSmooth (for example, when
+	 * lighting is disabled), in which case the implementation should draw as
+	 * smooth shaded.
+	 */
+	void (*drawMappedFaces)(DerivedMesh *dm,
+	                        int (*setDrawOptions)(void *userData, int index,
+	                                              int *drawSmooth_r),
+	                        void *userData, int useColors);
+
+	/* Draw mapped faces using TFace 
+	 *  o Drawing options too complicated to enumerate, look at code.
+	 */
+	void (*drawMappedFacesTex)(DerivedMesh *dm,
+	                           int (*setDrawOptions)(void *userData,
+	                                                 int index),
+	                           void *userData);
+
+	/* Draw mapped edges as lines
+	 *  o Only if !setDrawOptions or setDrawOptions(userData, mapped-edge)
+	 *    returns true
+	 */
+	void (*drawMappedEdges)(DerivedMesh *dm,
+	                        int (*setDrawOptions)(void *userData, int index),
+	                        void *userData);
+
+	/* Draw mapped edges as lines with interpolation values
+	 *  o Only if !setDrawOptions or
+	 *    setDrawOptions(userData, mapped-edge, mapped-v0, mapped-v1, t)
+	 *    returns true
+	 *
+	 * NOTE: This routine is optional!
+	 */
 	void (*drawMappedEdgesInterp)(DerivedMesh *dm, 
-									int (*setDrawOptions)(void *userData, int index), 
-									void (*setDrawInterpOptions)(void *userData, int index, float t),
-									void *userData);
+	                              int (*setDrawOptions)(void *userData,
+	                                                    int index), 
+	                              void (*setDrawInterpOptions)(void *userData,
+	                                                           int index,
+	                                                           float t),
+	                              void *userData);
 
 	void (*release)(DerivedMesh *dm);
 };
 
+/* utility function to initialise a DerivedMesh's function pointers to
+ * the default implementation (for those functions which have a default)
+ */
+void DM_init_funcs(DerivedMesh *dm);
+
+/* utility function to initialise a DerivedMesh for the desired number
+ * of vertices, edges and faces (doesn't allocate memory for them, just
+ * sets up the custom data layers)
+ */
+void DM_init(DerivedMesh *dm, int numVerts, int numEdges, int numFaces);
+
+/* utility function to initialise a DerivedMesh for the desired number
+ * of vertices, edges and faces, with a layer setup copied from source
+ */
+void DM_from_template(DerivedMesh *dm, DerivedMesh *source,
+                      int numVerts, int numEdges, int numFaces);
+
+/* utility function to release a DerivedMesh's layers
+ */
+void DM_release(DerivedMesh *dm);
+
+/* utility function to convert a DerivedMesh to a Mesh
+ */
+void DM_to_mesh(DerivedMesh *dm, struct Mesh *me);
+
+/* adds a vertex/edge/face custom data layer to a DerivedMesh, optionally
+ * backed by an external data array
+ * if layer != NULL, it is used as the layer data array, otherwise new memory
+ * is allocated
+ * the layer data will be freed by dm->release unless
+ * (flag & LAYERFLAG_NOFREE) is true
+ */
+void DM_add_vert_layer(struct DerivedMesh *dm, int type, int flag,
+                       void *layer);
+void DM_add_edge_layer(struct DerivedMesh *dm, int type, int flag,
+                       void *layer);
+void DM_add_face_layer(struct DerivedMesh *dm, int type, int flag,
+                       void *layer);
+
+/* custom data access functions
+ * return pointer to data from first layer which matches type
+ * if they return NULL for valid indices, data doesn't exist
+ * note these return pointers - any change modifies the internals of the mesh
+ */
+void *DM_get_vert_data(struct DerivedMesh *dm, int index, int type);
+void *DM_get_edge_data(struct DerivedMesh *dm, int index, int type);
+void *DM_get_face_data(struct DerivedMesh *dm, int index, int type);
+
+/* custom data layer access functions
+ * return pointer to first data layer which matches type (a flat array)
+ * if they return NULL, data doesn't exist
+ * note these return pointers - any change modifies the internals of the mesh
+ */
+void *DM_get_vert_data_layer(struct DerivedMesh *dm, int type);
+void *DM_get_edge_data_layer(struct DerivedMesh *dm, int type);
+void *DM_get_face_data_layer(struct DerivedMesh *dm, int type);
+
+/* custom data setting functions
+ * copy supplied data into first layer of type using layer's copy function
+ * (deep copy if appropriate)
+ */
+void DM_set_vert_data(struct DerivedMesh *dm, int index, int type, void *data);
+void DM_set_edge_data(struct DerivedMesh *dm, int index, int type, void *data);
+void DM_set_face_data(struct DerivedMesh *dm, int index, int type, void *data);
+
+/* custom data copy functions
+ * copy count elements from source_index in source to dest_index in dest
+ * these copy all layers for which the LAYERFLAG_NOCOPY flag is not set
+ */
+void DM_copy_vert_data(struct DerivedMesh *source, struct DerivedMesh *dest,
+                       int source_index, int dest_index, int count);
+void DM_copy_edge_data(struct DerivedMesh *source, struct DerivedMesh *dest,
+                       int source_index, int dest_index, int count);
+void DM_copy_face_data(struct DerivedMesh *source, struct DerivedMesh *dest,
+                       int source_index, int dest_index, int count);
+
+/* custom data free functions
+ * free count elements, starting at index
+ * they free all layers for which the LAYERFLAG_NOFREE flag is not set
+ */
+void DM_free_vert_data(struct DerivedMesh *dm, int index, int count);
+void DM_free_edge_data(struct DerivedMesh *dm, int index, int count);
+void DM_free_face_data(struct DerivedMesh *dm, int index, int count);
+
+/* interpolates vertex data from the vertices indexed by src_indices in the
+ * source mesh using the given weights and stores the result in the vertex
+ * indexed by dest_index in the dest mesh
+ */
+void DM_interp_vert_data(struct DerivedMesh *source, struct DerivedMesh *dest,
+                         int *src_indices, float *weights,
+                         int count, int dest_index);
+
+/* interpolates edge data from the edges indexed by src_indices in the
+ * source mesh using the given weights and stores the result in the edge indexed
+ * by dest_index in the dest mesh.
+ * if weights is NULL, all weights default to 1.
+ * if vert_weights is non-NULL, any per-vertex edge data is interpolated using
+ * vert_weights[i] multiplied by weights[i].
+ */
+typedef float EdgeVertWeight[SUB_ELEMS_EDGE][SUB_ELEMS_EDGE];
+void DM_interp_edge_data(struct DerivedMesh *source, struct DerivedMesh *dest,
+                         int *src_indices,
+                         float *weights, EdgeVertWeight *vert_weights,
+                         int count, int dest_index);
+
+/* interpolates face data from the faces indexed by src_indices in the
+ * source mesh using the given weights and stores the result in the face indexed
+ * by dest_index in the dest mesh.
+ * if weights is NULL, all weights default to 1.
+ * if vert_weights is non-NULL, any per-vertex face data is interpolated using
+ * vert_weights[i] multiplied by weights[i].
+ */
+typedef float FaceVertWeight[SUB_ELEMS_FACE][SUB_ELEMS_FACE];
+void DM_interp_face_data(struct DerivedMesh *source, struct DerivedMesh *dest,
+                         int *src_indices,
+                         float *weights, FaceVertWeight *vert_weights,
+                         int count, int dest_index);
+
     /* Simple function to get me->totvert amount of vertices/normals,
        correctly deformed and subsurfered. Needed especially when vertexgroups are involved.
        In use now by vertex/weigt paint and particles */