move mesh evaluation functions (normal, mapping, smooth group... etc, calculations...
authorCampbell Barton <ideasman42@gmail.com>
Mon, 9 Sep 2013 02:11:44 +0000 (02:11 +0000)
committerCampbell Barton <ideasman42@gmail.com>
Mon, 9 Sep 2013 02:11:44 +0000 (02:11 +0000)
mesh.c was over 4k lines and complex functions mixed in with general library management.

source/blender/blenkernel/BKE_mesh.h
source/blender/blenkernel/CMakeLists.txt
source/blender/blenkernel/intern/mesh.c
source/blender/blenkernel/intern/mesh_evaluate.c [new file with mode: 0644]
source/blender/blenkernel/intern/mesh_validate.c
source/blender/blenkernel/intern/multires.c
source/blender/blenloader/intern/versioning_legacy.c

index 3d443cbe38c9e2f827ab0ada48d2c8dcb0074004..43e425b5ce17b83e079d8026043868316e8b8d55 100644 (file)
@@ -31,8 +31,6 @@
  *  \ingroup bke
  */
 
-/***/
-
 struct ID;
 struct BoundBox;
 struct DispList;
@@ -60,108 +58,25 @@ struct UvVertMap;
 struct UvMapVert;
 struct UvElementMap;
 struct UvElement;
+
 #ifdef __cplusplus
 extern "C" {
 #endif
 
-struct BMesh *BKE_mesh_to_bmesh(struct Mesh *me, struct Object *ob);
-
-/*
- * this function recreates a tessellation.
- * returns number of tessellation faces.
- *
- * use_poly_origindex sets whether or not the tessellation faces' origindex
- * layer should point to original poly indices or real poly indices.
- *
- * use_face_origindex sets the tessellation faces' origindex layer
- * to point to the tessellation faces themselves, not the polys.
- *
- * if both of the above are 0, it'll use the indices of the mpolys of the MPoly
- * data in pdata, and ignore the origindex layer altogether.
- */
-int BKE_mesh_recalc_tessellation(struct CustomData *fdata, struct CustomData *ldata, struct CustomData *pdata,
-                                 struct MVert *mvert,
-                                 int totface, int totloop, int totpoly,
-                                 const bool do_face_normals);
-
-/* for forwards compat only quad->tri polys to mface, skip ngons.
- */
-int BKE_mesh_mpoly_to_mface(struct CustomData *fdata, struct CustomData *ldata,
-                            struct CustomData *pdata, int totface, int totloop, int totpoly);
-
-/*calculates a face normal.*/
-void BKE_mesh_calc_poly_normal(struct MPoly *mpoly, struct MLoop *loopstart,
-                               struct MVert *mvarray, float no[3]);
-
-void BKE_mesh_calc_poly_normal_coords(struct MPoly *mpoly, struct MLoop *loopstart,
-                                      const float (*vertex_coords)[3], float no[3]);
-
-void BKE_mesh_calc_poly_center(struct MPoly *mpoly, struct MLoop *loopstart,
-                               struct MVert *mvarray, float cent[3]);
-
-float BKE_mesh_calc_poly_area(struct MPoly *mpoly, struct MLoop *loopstart,
-                              struct MVert *mvarray, const float polynormal[3]);
-
-void BKE_mesh_calc_poly_angles(struct MPoly *mpoly, struct MLoop *loopstart,
-                               struct MVert *mvarray, float angles[]);
 
-int *BKE_mesh_calc_smoothgroups(const struct MEdge *medge, const int totedge,
-                                const struct MPoly *mpoly, const int totpoly,
-                                const struct MLoop *mloop, const int totloop,
-                                int *r_totgroup, const bool use_bitflags);
+/* *** mesh.c *** */
 
-void BKE_mesh_calc_relative_deform(
-        const struct MPoly *mpoly, const int totpoly,
-        const struct MLoop *mloop, const int totvert,
-
-        const float (*vert_cos_src)[3],
-        const float (*vert_cos_dst)[3],
-
-        const float (*vert_cos_org)[3],
-              float (*vert_cos_new)[3]);
+struct BMesh *BKE_mesh_to_bmesh(struct Mesh *me, struct Object *ob);
 
-/* Find the index of the loop in 'poly' which references vertex,
- * returns -1 if not found */
 int poly_find_loop_from_vert(const struct MPoly *poly,
                              const struct MLoop *loopstart,
                              unsigned vert);
 
-/* Fill 'adj_r' with the loop indices in 'poly' adjacent to the
- * vertex. Returns the index of the loop matching vertex, or -1 if the
- * vertex is not in 'poly' */
 int poly_get_adj_loops_from_vert(unsigned adj_r[3], const struct MPoly *poly,
                                  const struct MLoop *mloop, unsigned vert);
 
-/* Return the index of the edge vert that is not equal to 'v'. If
- * neither edge vertex is equal to 'v', returns -1. */
 int BKE_mesh_edge_other_vert(const struct MEdge *e, int v);
 
-/* update the hide flag for edges and polys from the corresponding
- * flag in verts */
-void BKE_mesh_flush_hidden_from_verts_ex(const struct MVert *mvert,
-                                         const struct MLoop *mloop,
-                                         struct MEdge *medge, const int totedge,
-                                         struct MPoly *mpoly, const int totpoly);
-void BKE_mesh_flush_hidden_from_verts(struct Mesh *me);
-
-void BKE_mesh_flush_hidden_from_polys_ex(struct MVert *mvert,
-                                         const struct MLoop *mloop,
-                                         struct MEdge *medge, const int totedge,
-                                         const struct MPoly *mpoly, const int totpoly);
-void BKE_mesh_flush_hidden_from_polys(struct Mesh *me);
-
-
-void BKE_mesh_flush_select_from_polys_ex(struct MVert *mvert,       const int totvert,
-                                         const struct MLoop *mloop,
-                                         struct MEdge *medge,       const int totedge,
-                                         const struct MPoly *mpoly, const int totpoly);
-void BKE_mesh_flush_select_from_polys(struct Mesh *me);
-void BKE_mesh_flush_select_from_verts_ex(const struct MVert *mvert, const int totvert,
-                                         const struct MLoop *mloop,
-                                         struct MEdge *medge,       const int totedge,
-                                         struct MPoly *mpoly,       const int totpoly);
-void BKE_mesh_flush_select_from_verts(struct Mesh *me);
-
 void BKE_mesh_unlink(struct Mesh *me);
 void BKE_mesh_free(struct Mesh *me, int unlink);
 struct Mesh *BKE_mesh_add(struct Main *bmain, const char *name);
@@ -191,64 +106,92 @@ void BKE_mesh_to_curve(struct Scene *scene, struct Object *ob);
 void BKE_mesh_material_index_remove(struct Mesh *me, short index);
 void BKE_mesh_material_index_clear(struct Mesh *me);
 void BKE_mesh_smooth_flag_set(struct Object *meshOb, int enableSmooth);
-void BKE_mesh_convert_mfaces_to_mpolys(struct Mesh *mesh);
-void BKE_mesh_do_versions_convert_mfaces_to_mpolys(struct Mesh *mesh);
-void BKE_mesh_convert_mfaces_to_mpolys_ex(struct ID *id,
-                                          struct CustomData *fdata, struct CustomData *ldata, struct CustomData *pdata,
-                                          int totedge_i, int totface_i, int totloop_i, int totpoly_i,
-                                          struct MEdge *medge, struct MFace *mface,
-                                          int *totloop_r, int *totpoly_r,
-                                          struct MLoop **mloop_r, struct MPoly **mpoly_r);
-
-void BKE_mesh_calc_normals_tessface(struct MVert *mverts, int numVerts, struct MFace *mfaces, int numFaces, float (*faceNors_r)[3]);
-
-/* used for unit testing; compares two meshes, checking only
- * differences we care about.  should be usable with leaf's
- * testing framework I get RNA work done, will use hackish
- * testing code for now.*/
+
 const char *BKE_mesh_cmp(struct Mesh *me1, struct Mesh *me2, float thresh);
 
 struct BoundBox *BKE_mesh_boundbox_get(struct Object *ob);
 void BKE_mesh_texspace_get(struct Mesh *me, float r_loc[3], float r_rot[3], float r_size[3]);
 void BKE_mesh_texspace_copy_from_object(struct Mesh *me, struct Object *ob);
 
-/* if old, it converts mface->edcode to edge drawflags */
-void BKE_mesh_make_edges(struct Mesh *me, const bool use_old);
+float (*BKE_mesh_vertexCos_get(struct Mesh *me, int *r_numVerts))[3];
 
-void BKE_mesh_strip_loose_faces(struct Mesh *me); /* Needed for compatibility (some old read code). */
-void BKE_mesh_strip_loose_polysloops(struct Mesh *me);
-void BKE_mesh_strip_loose_edges(struct Mesh *me);
+/* vertex level transformations & checks (no derived mesh) */
+
+bool BKE_mesh_minmax(struct Mesh *me, float r_min[3], float r_max[3]);
+void BKE_mesh_translate(struct Mesh *me, const float offset[3], const bool do_keys);
+
+void BKE_mesh_ensure_navmesh(struct Mesh *me);
+
+void BKE_mesh_tessface_calc(struct Mesh *mesh);
+void BKE_mesh_tessface_ensure(struct Mesh *mesh);
+void BKE_mesh_tessface_clear(struct Mesh *mesh);
+
+void BKE_mesh_do_versions_cd_flag_init(struct Mesh *mesh);
+
+
+void BKE_mesh_mselect_clear(struct Mesh *me);
+void BKE_mesh_mselect_validate(struct Mesh *me);
+int  BKE_mesh_mselect_find(struct Mesh *me, int index, int type);
+int  BKE_mesh_mselect_active_get(struct Mesh *me, int type);
+void BKE_mesh_mselect_active_set(struct Mesh *me, int index, int type);
+
+
+
+/* *** mesh_evaluate.c *** */
 
-/* Calculate vertex and face normals, face normals are returned in *faceNors_r if non-NULL
- * and vertex normals are stored in actual mverts.
- */
 void BKE_mesh_calc_normals_mapping(
         struct MVert *mverts, int numVerts,
         struct MLoop *mloop, struct MPoly *mpolys, int numLoops, int numPolys, float (*polyNors_r)[3],
         struct MFace *mfaces, int numFaces, int *origIndexFace, float (*faceNors_r)[3]);
-/* extended version of 'BKE_mesh_calc_normals_poly' with option not to calc vertex normals */
 void BKE_mesh_calc_normals_mapping_ex(
         struct MVert *mverts, int numVerts,
         struct MLoop *mloop, struct MPoly *mpolys, int numLoops, int numPolys, float (*polyNors_r)[3],
         struct MFace *mfaces, int numFaces, int *origIndexFace, float (*faceNors_r)[3],
         const bool only_face_normals);
-
 void BKE_mesh_calc_normals_poly(
         struct MVert *mverts, int numVerts,
         struct MLoop *mloop, struct MPoly *mpolys,
         int numLoops, int numPolys, float (*polyNors_r)[3],
         const bool only_face_normals);
-
 void BKE_mesh_calc_normals(struct Mesh *me);
+void BKE_mesh_calc_normals_tessface(
+        struct MVert *mverts, int numVerts,
+        struct MFace *mfaces, int numFaces,
+        float (*faceNors_r)[3]);
+
+
+void BKE_mesh_calc_poly_normal(
+        struct MPoly *mpoly, struct MLoop *loopstart,
+        struct MVert *mvarray, float no[3]);
+void BKE_mesh_calc_poly_normal_coords(
+        struct MPoly *mpoly, struct MLoop *loopstart,
+        const float (*vertex_coords)[3], float no[3]);
+void BKE_mesh_calc_poly_center(
+        struct MPoly *mpoly, struct MLoop *loopstart,
+        struct MVert *mvarray, float cent[3]);
+float BKE_mesh_calc_poly_area(
+        struct MPoly *mpoly, struct MLoop *loopstart,
+        struct MVert *mvarray, const float polynormal[3]);
+void BKE_mesh_calc_poly_angles(
+        struct MPoly *mpoly, struct MLoop *loopstart,
+        struct MVert *mvarray, float angles[]);
+
+void BKE_mesh_poly_edgehash_insert(
+        struct EdgeHash *ehash,
+        const struct MPoly *mp, const struct MLoop *mloop);
+void BKE_mesh_poly_edgebitmap_insert(
+        unsigned int *edge_bitmap,
+        const struct MPoly *mp, const struct MLoop *mloop);
+
+
+bool BKE_mesh_center_median(struct Mesh *me, float cent[3]);
+bool BKE_mesh_center_bounds(struct Mesh *me, float cent[3]);
+bool BKE_mesh_center_centroid(struct Mesh *me, float cent[3]);
 
-/* Return a newly MEM_malloc'd array of all the mesh vertex locations
- * (_numVerts_r_ may be NULL) */
-float (*BKE_mesh_vertexCos_get(struct Mesh *me, int *r_numVerts))[3];
 
 /* map from uv vertex to face (for select linked, stitch, uv suburf) */
 
 /* UvVertMap */
-
 #define STD_UV_CONNECT_LIMIT  0.0001f
 
 typedef struct UvVertMap {
@@ -302,45 +245,107 @@ typedef struct UvElementMap {
  * to make that many islands, he can bite me :p */
 #define INVALID_ISLAND 0xFFFF
 
-UvVertMap *BKE_mesh_uv_vert_map_create(struct MPoly *mpoly, struct MLoop *mloop, struct MLoopUV *mloopuv,
-                                     unsigned int totpoly, unsigned int totvert, int selected, float *limit);
-UvMapVert *BKE_mesh_uv_vert_map_get_vert(UvVertMap *vmap, unsigned int v);
-void       BKE_mesh_uv_vert_map_free(UvVertMap *vmap);
-
 /* Connectivity data */
 typedef struct MeshElemMap {
        int *indices;
        int count;
 } MeshElemMap;
-       
-typedef struct IndexNode {
-       struct IndexNode *next, *prev;
-       int index;
-} IndexNode;
 
-void BKE_mesh_vert_poly_map_create(MeshElemMap **r_map, int **r_mem,
-                                   const struct MPoly *mface, const struct MLoop *mloop,
-                                   int totvert, int totface, int totloop);
+/* mapping */
+UvVertMap *BKE_mesh_uv_vert_map_create(
+        struct MPoly *mpoly, struct MLoop *mloop, struct MLoopUV *mloopuv,
+        unsigned int totpoly, unsigned int totvert, int selected, float *limit);
+UvMapVert *BKE_mesh_uv_vert_map_get_vert(UvVertMap *vmap, unsigned int v);
+void       BKE_mesh_uv_vert_map_free(UvVertMap *vmap);
 
-void BKE_mesh_vert_edge_map_create(MeshElemMap **r_map, int **r_mem,
-                                   const struct MEdge *medge, int totvert, int totedge);
+void BKE_mesh_vert_poly_map_create(
+        MeshElemMap **r_map, int **r_mem,
+        const struct MPoly *mface, const struct MLoop *mloop,
+        int totvert, int totface, int totloop);
+void BKE_mesh_vert_edge_map_create(
+        MeshElemMap **r_map, int **r_mem,
+        const struct MEdge *medge, int totvert, int totedge);
+void BKE_mesh_edge_poly_map_create(
+        MeshElemMap **r_map, int **r_mem,
+        const struct MEdge *medge, const int totedge,
+        const struct MPoly *mpoly, const int totpoly,
+        const struct MLoop *mloop, const int totloop);
+
+/* tessface */
+void BKE_mesh_loops_to_mface_corners(
+        struct CustomData *fdata, struct CustomData *ldata,
+        struct CustomData *pdata, int lindex[4], int findex,
+        const int polyindex, const int mf_len,
+        const int numTex, const int numCol,
+        const bool hasPCol, const bool hasOrigSpace);
+int BKE_mesh_recalc_tessellation(
+        struct CustomData *fdata, struct CustomData *ldata, struct CustomData *pdata,
+        struct MVert *mvert,
+        int totface, int totloop, int totpoly,
+        const bool do_face_normals);
+int BKE_mesh_mpoly_to_mface(
+        struct CustomData *fdata, struct CustomData *ldata,
+        struct CustomData *pdata, int totface, int totloop, int totpoly);
+void BKE_mesh_convert_mfaces_to_mpolys(struct Mesh *mesh);
+void BKE_mesh_do_versions_convert_mfaces_to_mpolys(struct Mesh *mesh);
+void BKE_mesh_convert_mfaces_to_mpolys_ex(
+        struct ID *id,
+        struct CustomData *fdata, struct CustomData *ldata, struct CustomData *pdata,
+        int totedge_i, int totface_i, int totloop_i, int totpoly_i,
+        struct MEdge *medge, struct MFace *mface,
+        int *totloop_r, int *totpoly_r,
+        struct MLoop **mloop_r, struct MPoly **mpoly_r);
+
+/* flush flags */
+void BKE_mesh_flush_hidden_from_verts_ex(
+        const struct MVert *mvert,
+        const struct MLoop *mloop,
+        struct MEdge *medge, const int totedge,
+        struct MPoly *mpoly, const int totpoly);
+void BKE_mesh_flush_hidden_from_verts(struct Mesh *me);
+void BKE_mesh_flush_hidden_from_polys_ex(
+        struct MVert *mvert,
+        const struct MLoop *mloop,
+        struct MEdge *medge, const int totedge,
+        const struct MPoly *mpoly, const int totpoly);
+void BKE_mesh_flush_hidden_from_polys(struct Mesh *me);
+void BKE_mesh_flush_select_from_polys_ex(
+        struct MVert *mvert,       const int totvert,
+        const struct MLoop *mloop,
+        struct MEdge *medge,       const int totedge,
+        const struct MPoly *mpoly, const int totpoly);
+void BKE_mesh_flush_select_from_polys(struct Mesh *me);
+void BKE_mesh_flush_select_from_verts_ex(
+        const struct MVert *mvert, const int totvert,
+        const struct MLoop *mloop,
+        struct MEdge *medge,       const int totedge,
+        struct MPoly *mpoly,       const int totpoly);
+void BKE_mesh_flush_select_from_verts(struct Mesh *me);
 
-void BKE_mesh_edge_poly_map_create(MeshElemMap **r_map, int **r_mem,
-                                   const struct MEdge *medge, const int totedge,
-                                   const struct MPoly *mpoly, const int totpoly,
-                                   const struct MLoop *mloop, const int totloop);
+/* smoothgroups */
+int *BKE_mesh_calc_smoothgroups(
+        const struct MEdge *medge, const int totedge,
+        const struct MPoly *mpoly, const int totpoly,
+        const struct MLoop *mloop, const int totloop,
+        int *r_totgroup, const bool use_bitflags);
+
+/* spatial evaluation */
+void BKE_mesh_calc_relative_deform(
+        const struct MPoly *mpoly, const int totpoly,
+        const struct MLoop *mloop, const int totvert,
+
+        const float (*vert_cos_src)[3],
+        const float (*vert_cos_dst)[3],
+
+        const float (*vert_cos_org)[3],
+              float (*vert_cos_new)[3]);
 
-/* vertex level transformations & checks (no derived mesh) */
 
-bool BKE_mesh_minmax(struct Mesh *me, float r_min[3], float r_max[3]);
-bool BKE_mesh_center_median(struct Mesh *me, float cent[3]);
-bool BKE_mesh_center_bounds(struct Mesh *me, float cent[3]);
-bool BKE_mesh_center_centroid(struct Mesh *me, float cent[3]);
-void BKE_mesh_translate(struct Mesh *me, const float offset[3], const bool do_keys);
 
-/* mesh_validate.c */
-/* XXX Loop v/e are unsigned, so using max uint_32 value as invalid marker... */
-#define INVALID_LOOP_EDGE_MARKER 4294967295u
+/* *** mesh_validate.c *** */
+
+int BKE_mesh_validate(struct Mesh *me, const int do_verbose);
+
 bool BKE_mesh_validate_arrays(
         struct Mesh *me,
         struct MVert *mverts, unsigned int totvert,
@@ -359,34 +364,13 @@ bool BKE_mesh_validate_all_customdata(
         const bool do_verbose, const bool do_fixes,
         bool *r_change);
 
-int BKE_mesh_validate(struct Mesh *me, const int do_verbose);
+void BKE_mesh_strip_loose_faces(struct Mesh *me);
+void BKE_mesh_strip_loose_polysloops(struct Mesh *me);
+void BKE_mesh_strip_loose_edges(struct Mesh *me);
 
+void BKE_mesh_calc_edges_legacy(struct Mesh *me, const bool use_old);
 void BKE_mesh_calc_edges(struct Mesh *mesh, bool update, const bool select);
 
-void BKE_mesh_ensure_navmesh(struct Mesh *me);
-
-void BKE_mesh_tessface_calc(struct Mesh *mesh);
-void BKE_mesh_tessface_ensure(struct Mesh *mesh);
-void BKE_mesh_tessface_clear(struct Mesh *mesh);
-
-/* Convert a triangle or quadrangle of loop/poly data to tessface data */
-void BKE_mesh_loops_to_mface_corners(struct CustomData *fdata, struct CustomData *ldata,
-                                     struct CustomData *pdata, int lindex[4], int findex,
-                                     const int polyindex, const int mf_len,
-                                     const int numTex, const int numCol, const int hasPCol, const int hasOrigSpace);
-
-void BKE_mesh_poly_edgehash_insert(struct EdgeHash *ehash, const struct MPoly *mp, const struct MLoop *mloop);
-void BKE_mesh_poly_edgebitmap_insert(unsigned int *edge_bitmap, const struct MPoly *mp, const struct MLoop *mloop);
-
-void BKE_mesh_do_versions_cd_flag_init(struct Mesh *mesh);
-
-
-void BKE_mesh_mselect_clear(struct Mesh *me);
-void BKE_mesh_mselect_validate(struct Mesh *me);
-int  BKE_mesh_mselect_find(struct Mesh *me, int index, int type);
-int  BKE_mesh_mselect_active_get(struct Mesh *me, int type);
-void BKE_mesh_mselect_active_set(struct Mesh *me, int index, int type);
-
 #ifdef __cplusplus
 }
 #endif
index e9142ef1abdaada2b2b3b264c42ad696013fad77..0ac3737b6a258349e8cea0fc67daf9af1a082d9d 100644 (file)
@@ -115,6 +115,7 @@ set(SRC
        intern/material.c
        intern/mball.c
        intern/mesh.c
+       intern/mesh_evaluate.c
        intern/mesh_validate.c
        intern/modifier.c
        intern/modifiers_bmesh.c
index 459f7216d002a018933e6143242f99ab2d23bfb2..63a7b8cd982cdcf43f8fc297a2e62f4301287330 100644 (file)
  *  \ingroup bke
  */
 
-
-#include <stdlib.h>
-#include <string.h>
-#include <stdio.h>
-#include <math.h>
-
 #include "MEM_guardedalloc.h"
 
 #include "DNA_scene_types.h"
 #include "DNA_object_types.h"
 #include "DNA_key_types.h"
 #include "DNA_mesh_types.h"
-#include "DNA_meshdata_types.h"
 #include "DNA_ipo_types.h"
-#include "DNA_customdata_types.h"
 
 #include "BLI_utildefines.h"
-#include "BLI_blenlib.h"
-#include "BLI_memarena.h"
 #include "BLI_math.h"
+#include "BLI_listbase.h"
 #include "BLI_edgehash.h"
-#include "BLI_bitmap.h"
-#include "BLI_scanfill.h"
-#include "BLI_array.h"
-#include "BLI_alloca.h"
 
 #include "BKE_animsys.h"
 #include "BKE_main.h"
-#include "BKE_customdata.h"
 #include "BKE_DerivedMesh.h"
 #include "BKE_global.h"
 #include "BKE_mesh.h"
@@ -71,9 +57,7 @@
 /* -- */
 #include "BKE_object.h"
 #include "BKE_editmesh.h"
-#include "BLI_edgehash.h"
 
-#include "bmesh.h"
 
 enum {
        MESHCMP_DVERT_WEIGHTMISMATCH = 1,
@@ -275,7 +259,12 @@ static int customdata_compare(CustomData *c1, CustomData *c2, Mesh *m1, Mesh *m2
        return 0;
 }
 
-/*used for testing.  returns an error string the two meshes don't match*/
+/**
+ * Used for unit testing; compares two meshes, checking only
+ * differences we care about.  should be usable with leaf's
+ * testing framework I get RNA work done, will use hackish
+ * testing code for now.
+ */
 const char *BKE_mesh_cmp(Mesh *me1, Mesh *me2, float thresh)
 {
        int c;
@@ -866,309 +855,6 @@ void BKE_mesh_assign_object(Object *ob, Mesh *me)
        test_object_modifiers(ob);
 }
 
-/* ************** make edges in a Mesh, for outside of editmode */
-
-struct EdgeSort {
-       unsigned int v1, v2;
-       char is_loose, is_draw;
-};
-
-/* edges have to be added with lowest index first for sorting */
-static void to_edgesort(struct EdgeSort *ed,
-                        unsigned int v1, unsigned int v2,
-                        char is_loose, short is_draw)
-{
-       if (v1 < v2) {
-               ed->v1 = v1; ed->v2 = v2;
-       }
-       else {
-               ed->v1 = v2; ed->v2 = v1;
-       }
-       ed->is_loose = is_loose;
-       ed->is_draw = is_draw;
-}
-
-static int vergedgesort(const void *v1, const void *v2)
-{
-       const struct EdgeSort *x1 = v1, *x2 = v2;
-
-       if (x1->v1 > x2->v1) return 1;
-       else if (x1->v1 < x2->v1) return -1;
-       else if (x1->v2 > x2->v2) return 1;
-       else if (x1->v2 < x2->v2) return -1;
-       
-       return 0;
-}
-
-
-/* Create edges based on known verts and faces,
- * this function is only used when loading very old blend files */
-
-static void make_edges_mdata(MVert *UNUSED(allvert), MFace *allface, MLoop *allloop,
-                             MPoly *allpoly, int UNUSED(totvert), int totface, int UNUSED(totloop), int totpoly,
-                             const bool use_old,
-                             MEdge **r_medge, int *r_totedge)
-{
-       MPoly *mpoly;
-       MFace *mface;
-       MEdge *medge, *med;
-       EdgeHash *hash;
-       struct EdgeSort *edsort, *ed;
-       int a, totedge = 0;
-       unsigned int totedge_final = 0;
-       unsigned int edge_index;
-
-       /* we put all edges in array, sort them, and detect doubles that way */
-
-       for (a = totface, mface = allface; a > 0; a--, mface++) {
-               if (mface->v4) totedge += 4;
-               else if (mface->v3) totedge += 3;
-               else totedge += 1;
-       }
-
-       if (totedge == 0) {
-               /* flag that mesh has edges */
-               (*r_medge) = MEM_callocN(0, __func__);
-               (*r_totedge) = 0;
-               return;
-       }
-
-       ed = edsort = MEM_mallocN(totedge * sizeof(struct EdgeSort), "EdgeSort");
-
-       for (a = totface, mface = allface; a > 0; a--, mface++) {
-               to_edgesort(ed++, mface->v1, mface->v2, !mface->v3, mface->edcode & ME_V1V2);
-               if (mface->v4) {
-                       to_edgesort(ed++, mface->v2, mface->v3, 0, mface->edcode & ME_V2V3);
-                       to_edgesort(ed++, mface->v3, mface->v4, 0, mface->edcode & ME_V3V4);
-                       to_edgesort(ed++, mface->v4, mface->v1, 0, mface->edcode & ME_V4V1);
-               }
-               else if (mface->v3) {
-                       to_edgesort(ed++, mface->v2, mface->v3, 0, mface->edcode & ME_V2V3);
-                       to_edgesort(ed++, mface->v3, mface->v1, 0, mface->edcode & ME_V3V1);
-               }
-       }
-
-       qsort(edsort, totedge, sizeof(struct EdgeSort), vergedgesort);
-
-       /* count final amount */
-       for (a = totedge, ed = edsort; a > 1; a--, ed++) {
-               /* edge is unique when it differs from next edge, or is last */
-               if (ed->v1 != (ed + 1)->v1 || ed->v2 != (ed + 1)->v2) totedge_final++;
-       }
-       totedge_final++;
-
-       medge = MEM_callocN(sizeof(MEdge) * totedge_final, __func__);
-
-       for (a = totedge, med = medge, ed = edsort; a > 1; a--, ed++) {
-               /* edge is unique when it differs from next edge, or is last */
-               if (ed->v1 != (ed + 1)->v1 || ed->v2 != (ed + 1)->v2) {
-                       med->v1 = ed->v1;
-                       med->v2 = ed->v2;
-                       if (use_old == false || ed->is_draw) med->flag = ME_EDGEDRAW | ME_EDGERENDER;
-                       if (ed->is_loose) med->flag |= ME_LOOSEEDGE;
-
-                       /* order is swapped so extruding this edge as a surface wont flip face normals
-                        * with cyclic curves */
-                       if (ed->v1 + 1 != ed->v2) {
-                               SWAP(unsigned int, med->v1, med->v2);
-                       }
-                       med++;
-               }
-               else {
-                       /* equal edge, we merge the drawflag */
-                       (ed + 1)->is_draw |= ed->is_draw;
-               }
-       }
-       /* last edge */
-       med->v1 = ed->v1;
-       med->v2 = ed->v2;
-       med->flag = ME_EDGEDRAW;
-       if (ed->is_loose) med->flag |= ME_LOOSEEDGE;
-       med->flag |= ME_EDGERENDER;
-
-       MEM_freeN(edsort);
-       
-       /* set edge members of mloops */
-       hash = BLI_edgehash_new_ex(__func__, totedge_final);
-       for (edge_index = 0, med = medge; edge_index < totedge_final; edge_index++, med++) {
-               BLI_edgehash_insert(hash, med->v1, med->v2, SET_UINT_IN_POINTER(edge_index));
-       }
-       
-       mpoly = allpoly;
-       for (a = 0; a < totpoly; a++, mpoly++) {
-               MLoop *ml, *ml_next;
-               int i = mpoly->totloop;
-
-               ml_next = allloop + mpoly->loopstart;  /* first loop */
-               ml = &ml_next[i - 1];                  /* last loop */
-
-               while (i-- != 0) {
-                       ml->e = GET_UINT_FROM_POINTER(BLI_edgehash_lookup(hash, ml->v, ml_next->v));
-                       ml = ml_next;
-                       ml_next++;
-               }
-       }
-       
-       BLI_edgehash_free(hash, NULL);
-
-       *r_medge = medge;
-       *r_totedge = totedge_final;
-}
-
-void BKE_mesh_make_edges(Mesh *me, const bool use_old)
-{
-       MEdge *medge;
-       int totedge = 0;
-
-       make_edges_mdata(me->mvert, me->mface, me->mloop, me->mpoly,
-                        me->totvert, me->totface, me->totloop, me->totpoly,
-                        use_old, &medge, &totedge);
-
-       if (totedge == 0) {
-               /* flag that mesh has edges */
-               me->medge = medge;
-               me->totedge = 0;
-               return;
-       }
-
-       medge = CustomData_add_layer(&me->edata, CD_MEDGE, CD_ASSIGN, medge, totedge);
-       me->medge = medge;
-       me->totedge = totedge;
-
-       BKE_mesh_strip_loose_faces(me);
-}
-
-/* We need to keep this for edge creation (for now?), and some old readfile code... */
-void BKE_mesh_strip_loose_faces(Mesh *me)
-{
-       MFace *f;
-       int a, b;
-
-       for (a = b = 0, f = me->mface; a < me->totface; a++, f++) {
-               if (f->v3) {
-                       if (a != b) {
-                               memcpy(&me->mface[b], f, sizeof(me->mface[b]));
-                               CustomData_copy_data(&me->fdata, &me->fdata, a, b, 1);
-                       }
-                       b++;
-               }
-       }
-       if (a != b) {
-               CustomData_free_elem(&me->fdata, b, a - b);
-               me->totface = b;
-       }
-}
-
-/* Works on both loops and polys! */
-/* Note: It won't try to guess which loops of an invalid poly to remove!
- *       this is the work of the caller, to mark those loops...
- *       See e.g. BKE_mesh_validate_arrays(). */
-void BKE_mesh_strip_loose_polysloops(Mesh *me)
-{
-       MPoly *p;
-       MLoop *l;
-       int a, b;
-       /* New loops idx! */
-       int *new_idx = MEM_mallocN(sizeof(int) * me->totloop, __func__);
-
-       for (a = b = 0, p = me->mpoly; a < me->totpoly; a++, p++) {
-               int invalid = FALSE;
-               int i = p->loopstart;
-               int stop = i + p->totloop;
-
-               if (stop > me->totloop || stop < i) {
-                       invalid = TRUE;
-               }
-               else {
-                       l = &me->mloop[i];
-                       i = stop - i;
-                       /* If one of the poly's loops is invalid, the whole poly is invalid! */
-                       for (; i--; l++) {
-                               if (l->e == INVALID_LOOP_EDGE_MARKER) {
-                                       invalid = TRUE;
-                                       break;
-                               }
-                       }
-               }
-
-               if (p->totloop >= 3 && !invalid) {
-                       if (a != b) {
-                               memcpy(&me->mpoly[b], p, sizeof(me->mpoly[b]));
-                               CustomData_copy_data(&me->pdata, &me->pdata, a, b, 1);
-                       }
-                       b++;
-               }
-       }
-       if (a != b) {
-               CustomData_free_elem(&me->pdata, b, a - b);
-               me->totpoly = b;
-       }
-
-       /* And now, get rid of invalid loops. */
-       for (a = b = 0, l = me->mloop; a < me->totloop; a++, l++) {
-               if (l->e != INVALID_LOOP_EDGE_MARKER) {
-                       if (a != b) {
-                               memcpy(&me->mloop[b], l, sizeof(me->mloop[b]));
-                               CustomData_copy_data(&me->ldata, &me->ldata, a, b, 1);
-                       }
-                       new_idx[a] = b;
-                       b++;
-               }
-               else {
-                       /* XXX Theoretically, we should be able to not do this, as no remaining poly
-                        *     should use any stripped loop. But for security's sake... */
-                       new_idx[a] = -a;
-               }
-       }
-       if (a != b) {
-               CustomData_free_elem(&me->ldata, b, a - b);
-               me->totloop = b;
-       }
-
-       /* And now, update polys' start loop index. */
-       /* Note: At this point, there should never be any poly using a striped loop! */
-       for (a = 0, p = me->mpoly; a < me->totpoly; a++, p++) {
-               p->loopstart = new_idx[p->loopstart];
-       }
-
-       MEM_freeN(new_idx);
-}
-
-void BKE_mesh_strip_loose_edges(Mesh *me)
-{
-       MEdge *e;
-       MLoop *l;
-       int a, b;
-       unsigned int *new_idx = MEM_mallocN(sizeof(int) * me->totedge, __func__);
-
-       for (a = b = 0, e = me->medge; a < me->totedge; a++, e++) {
-               if (e->v1 != e->v2) {
-                       if (a != b) {
-                               memcpy(&me->medge[b], e, sizeof(me->medge[b]));
-                               CustomData_copy_data(&me->edata, &me->edata, a, b, 1);
-                       }
-                       new_idx[a] = b;
-                       b++;
-               }
-               else {
-                       new_idx[a] = INVALID_LOOP_EDGE_MARKER;
-               }
-       }
-       if (a != b) {
-               CustomData_free_elem(&me->edata, b, a - b);
-               me->totedge = b;
-       }
-
-       /* And now, update loops' edge indices. */
-       /* XXX We hope no loop was pointing to a striped edge!
-        *     Else, its e will be set to INVALID_LOOP_EDGE_MARKER :/ */
-       for (a = 0, l = me->mloop; a < me->totloop; a++, l++) {
-               l->e = new_idx[l->e];
-       }
-
-       MEM_freeN(new_idx);
-}
-
 void BKE_mesh_from_metaball(ListBase *lb, Mesh *me)
 {
        DispList *dl;
@@ -1933,2023 +1619,143 @@ void BKE_mesh_smooth_flag_set(Object *meshOb, int enableSmooth)
 }
 
 /**
- * Call when there are no polygons.
+ * Return a newly MEM_malloc'd array of all the mesh vertex locations
+ * \note \a numVerts_r may be NULL
  */
-static void mesh_calc_normals_vert_fallback(MVert *mverts, int numVerts)
+float (*BKE_mesh_vertexCos_get(Mesh *me, int *r_numVerts))[3]
 {
-       int i;
-       for (i = 0; i < numVerts; i++) {
-               MVert *mv = &mverts[i];
-               float no[3];
+       int i, numVerts = me->totvert;
+       float (*cos)[3] = MEM_mallocN(sizeof(*cos) * numVerts, "vertexcos1");
 
-               normalize_v3_v3(no, mv->co);
-               normal_float_to_short_v3(mv->no, no);
-       }
-}
+       if (r_numVerts) *r_numVerts = numVerts;
+       for (i = 0; i < numVerts; i++)
+               copy_v3_v3(cos[i], me->mvert[i].co);
 
-void BKE_mesh_calc_normals_mapping(MVert *mverts, int numVerts,
-                                   MLoop *mloop, MPoly *mpolys, int numLoops, int numPolys, float (*polyNors_r)[3],
-                                   MFace *mfaces, int numFaces, int *origIndexFace, float (*faceNors_r)[3])
-{
-       BKE_mesh_calc_normals_mapping_ex(mverts, numVerts, mloop, mpolys,
-                                        numLoops, numPolys, polyNors_r, mfaces, numFaces,
-                                        origIndexFace, faceNors_r, FALSE);
+       return cos;
 }
 
-void BKE_mesh_calc_normals_mapping_ex(MVert *mverts, int numVerts,
-                                      MLoop *mloop, MPoly *mpolys,
-                                      int numLoops, int numPolys, float (*polyNors_r)[3],
-                                      MFace *mfaces, int numFaces, int *origIndexFace, float (*faceNors_r)[3],
-                                      const bool only_face_normals)
+/**
+ * Find the index of the loop in 'poly' which references vertex,
+ * returns -1 if not found
+ */
+int poly_find_loop_from_vert(const MPoly *poly, const MLoop *loopstart,
+                             unsigned vert)
 {
-       float (*pnors)[3] = polyNors_r, (*fnors)[3] = faceNors_r;
-       int i;
-       MFace *mf;
-       MPoly *mp;
-
-       if (numPolys == 0) {
-               if (only_face_normals == FALSE) {
-                       mesh_calc_normals_vert_fallback(mverts, numVerts);
-               }
-               return;
-       }
-
-       /* if we are not calculating verts and no verts were passes then we have nothing to do */
-       if ((only_face_normals == TRUE) && (polyNors_r == NULL) && (faceNors_r == NULL)) {
-               printf("%s: called with nothing to do\n", __func__);
-               return;
-       }
-
-       if (!pnors) pnors = MEM_callocN(sizeof(float) * 3 * numPolys, "poly_nors mesh.c");
-       /* if (!fnors) fnors = MEM_callocN(sizeof(float) * 3 * numFaces, "face nors mesh.c"); */ /* NO NEED TO ALLOC YET */
-
-
-       if (only_face_normals == FALSE) {
-               /* vertex normals are optional, they require some extra calculations,
-                * so make them optional */
-               BKE_mesh_calc_normals_poly(mverts, numVerts, mloop, mpolys, numLoops, numPolys, pnors, false);
-       }
-       else {
-               /* only calc poly normals */
-               mp = mpolys;
-               for (i = 0; i < numPolys; i++, mp++) {
-                       BKE_mesh_calc_poly_normal(mp, mloop + mp->loopstart, mverts, pnors[i]);
-               }
-       }
-
-       if (origIndexFace &&
-           /* fnors == faceNors_r */ /* NO NEED TO ALLOC YET */
-           fnors != NULL &&
-           numFaces)
-       {
-               mf = mfaces;
-               for (i = 0; i < numFaces; i++, mf++, origIndexFace++) {
-                       if (*origIndexFace < numPolys) {
-                               copy_v3_v3(fnors[i], pnors[*origIndexFace]);
-                       }
-                       else {
-                               /* eek, we're not corresponding to polys */
-                               printf("error in %s: tessellation face indices are incorrect.  normals may look bad.\n", __func__);
-                       }
-               }
+       int j;
+       for (j = 0; j < poly->totloop; j++, loopstart++) {
+               if (loopstart->v == vert)
+                       return j;
        }
-
-       if (pnors != polyNors_r) MEM_freeN(pnors);
-       /* if (fnors != faceNors_r) MEM_freeN(fnors); */ /* NO NEED TO ALLOC YET */
-
-       fnors = pnors = NULL;
        
+       return -1;
 }
 
-static void mesh_calc_normals_poly_accum(MPoly *mp, MLoop *ml,
-                                         MVert *mvert, float polyno[3], float (*tnorms)[3])
+/**
+ * Fill \a adj_r with the loop indices in \a poly adjacent to the
+ * vertex. Returns the index of the loop matching vertex, or -1 if the
+ * vertex is not in \a poly
+ */
+int poly_get_adj_loops_from_vert(unsigned adj_r[3], const MPoly *poly,
+                                 const MLoop *mloop, unsigned vert)
 {
-       const int nverts = mp->totloop;
-       float (*edgevecbuf)[3] = BLI_array_alloca(edgevecbuf, nverts);
-       int i;
-
-       /* Polygon Normal and edge-vector */
-       /* inline version of #BKE_mesh_calc_poly_normal, also does edge-vectors */
-       {
-               int i_prev = nverts - 1;
-               float const *v_prev = mvert[ml[i_prev].v].co;
-               float const *v_curr;
-
-               zero_v3(polyno);
-               /* Newell's Method */
-               for (i = 0; i < nverts; i++) {
-                       v_curr = mvert[ml[i].v].co;
-                       add_newell_cross_v3_v3v3(polyno, v_prev, v_curr);
-
-                       /* Unrelated to normalize, calcualte edge-vector */
-                       sub_v3_v3v3(edgevecbuf[i_prev], v_prev, v_curr);
-                       normalize_v3(edgevecbuf[i_prev]);
-                       i_prev = i;
-
-                       v_prev = v_curr;
-               }
-               if (UNLIKELY(normalize_v3(polyno) == 0.0f)) {
-                       polyno[2] = 1.0f; /* other axis set to 0.0 */
-               }
-       }
-
-       /* accumulate angle weighted face normal */
-       /* inline version of #accumulate_vertex_normals_poly */
-       {
-               const float *prev_edge = edgevecbuf[nverts - 1];
-
-               for (i = 0; i < nverts; i++) {
-                       const float *cur_edge = edgevecbuf[i];
-
-                       /* calculate angle between the two poly edges incident on
-                        * this vertex */
-                       const float fac = saacos(-dot_v3v3(cur_edge, prev_edge));
+       int corner = poly_find_loop_from_vert(poly,
+                                             &mloop[poly->loopstart],
+                                             vert);
+               
+       if (corner != -1) {
+               const MLoop *ml = &mloop[poly->loopstart + corner];
 
-                       /* accumulate */
-                       madd_v3_v3fl(tnorms[ml[i].v], polyno, fac);
-                       prev_edge = cur_edge;
-               }
+               /* vertex was found */
+               adj_r[0] = ME_POLY_LOOP_PREV(mloop, poly, corner)->v;
+               adj_r[1] = ml->v;
+               adj_r[2] = ME_POLY_LOOP_NEXT(mloop, poly, corner)->v;
        }
 
+       return corner;
 }
 
-void BKE_mesh_calc_normals_poly(MVert *mverts, int numVerts, MLoop *mloop, MPoly *mpolys,
-                                int UNUSED(numLoops), int numPolys, float (*r_polynors)[3],
-                                const bool only_face_normals)
+/**
+ * Return the index of the edge vert that is not equal to \a v. If
+ * neither edge vertex is equal to \a v, returns -1.
+ */
+int BKE_mesh_edge_other_vert(const MEdge *e, int v)
 {
-       float (*pnors)[3] = r_polynors;
-       float (*tnorms)[3];
-       int i;
-       MPoly *mp;
-
-       if (only_face_normals) {
-               BLI_assert(pnors != NULL);
+       if (e->v1 == v)
+               return e->v2;
+       else if (e->v2 == v)
+               return e->v1;
+       else
+               return -1;
+}
 
-#pragma omp parallel for if (numPolys > BM_OMP_LIMIT)
-               for (i = 0; i < numPolys; i++) {
-                       BKE_mesh_calc_poly_normal(&mpolys[i], mloop + mpolys[i].loopstart, mverts, pnors[i]);
-               }
-               return;
+/* basic vertex data functions */
+bool BKE_mesh_minmax(Mesh *me, float r_min[3], float r_max[3])
+{
+       int i = me->totvert;
+       MVert *mvert;
+       for (mvert = me->mvert; i--; mvert++) {
+               minmax_v3v3_v3(r_min, r_max, mvert->co);
        }
+       
+       return (me->totvert != 0);
+}
 
-       /* first go through and calculate normals for all the polys */
-       tnorms = MEM_callocN(sizeof(*tnorms) * numVerts, __func__);
-
-       if (pnors) {
-               mp = mpolys;
-               for (i = 0; i < numPolys; i++, mp++) {
-                       mesh_calc_normals_poly_accum(mp, mloop + mp->loopstart, mverts, pnors[i], tnorms);
-               }
+void BKE_mesh_translate(Mesh *me, const float offset[3], const bool do_keys)
+{
+       int i = me->totvert;
+       MVert *mvert;
+       for (mvert = me->mvert; i--; mvert++) {
+               add_v3_v3(mvert->co, offset);
        }
-       else {
-               float tpnor[3];  /* temp poly normal */
-               mp = mpolys;
-               for (i = 0; i < numPolys; i++, mp++) {
-                       mesh_calc_normals_poly_accum(mp, mloop + mp->loopstart, mverts, tpnor, tnorms);
+       
+       if (do_keys && me->key) {
+               KeyBlock *kb;
+               for (kb = me->key->block.first; kb; kb = kb->next) {
+                       float *fp = kb->data;
+                       for (i = kb->totelem; i--; fp += 3) {
+                               add_v3_v3(fp, offset);
+                       }
                }
        }
+}
 
-       /* following Mesh convention; we use vertex coordinate itself for normal in this case */
-       for (i = 0; i < numVerts; i++) {
-               MVert *mv = &mverts[i];
-               float *no = tnorms[i];
-
-               if (UNLIKELY(normalize_v3(no) == 0.0f)) {
-                       normalize_v3_v3(no, mv->co);
+void BKE_mesh_ensure_navmesh(Mesh *me)
+{
+       if (!CustomData_has_layer(&me->pdata, CD_RECAST)) {
+               int i;
+               int numFaces = me->totpoly;
+               int *recastData;
+               recastData = (int *)MEM_mallocN(numFaces * sizeof(int), __func__);
+               for (i = 0; i < numFaces; i++) {
+                       recastData[i] = i + 1;
                }
-
-               normal_float_to_short_v3(mv->no, no);
+               CustomData_add_layer_named(&me->pdata, CD_RECAST, CD_ASSIGN, recastData, numFaces, "recastData");
        }
-
-       MEM_freeN(tnorms);
 }
 
-void BKE_mesh_calc_normals(Mesh *mesh)
+void BKE_mesh_tessface_calc(Mesh *mesh)
 {
-       BKE_mesh_calc_normals_poly(mesh->mvert, mesh->totvert,
-                                  mesh->mloop, mesh->mpoly, mesh->totloop, mesh->totpoly,
-                                  NULL, false);
+       mesh->totface = BKE_mesh_recalc_tessellation(&mesh->fdata, &mesh->ldata, &mesh->pdata,
+                                                    mesh->mvert,
+                                                    mesh->totface, mesh->totloop, mesh->totpoly,
+                                                    /* calc normals right after, don't copy from polys here */
+                                                    false);
+
+       BKE_mesh_update_customdata_pointers(mesh, true);
 }
 
-void BKE_mesh_calc_normals_tessface(MVert *mverts, int numVerts, MFace *mfaces, int numFaces, float (*faceNors_r)[3])
+void BKE_mesh_tessface_ensure(Mesh *mesh)
 {
-       float (*tnorms)[3] = MEM_callocN(numVerts * sizeof(*tnorms), "tnorms");
-       float (*fnors)[3] = (faceNors_r) ? faceNors_r : MEM_callocN(sizeof(*fnors) * numFaces, "meshnormals");
-       int i;
-
-       for (i = 0; i < numFaces; i++) {
-               MFace *mf = &mfaces[i];
-               float *f_no = fnors[i];
-               float *n4 = (mf->v4) ? tnorms[mf->v4] : NULL;
-               float *c4 = (mf->v4) ? mverts[mf->v4].co : NULL;
-
-               if (mf->v4)
-                       normal_quad_v3(f_no, mverts[mf->v1].co, mverts[mf->v2].co, mverts[mf->v3].co, mverts[mf->v4].co);
-               else
-                       normal_tri_v3(f_no, mverts[mf->v1].co, mverts[mf->v2].co, mverts[mf->v3].co);
-
-               accumulate_vertex_normals(tnorms[mf->v1], tnorms[mf->v2], tnorms[mf->v3], n4,
-                                         f_no, mverts[mf->v1].co, mverts[mf->v2].co, mverts[mf->v3].co, c4);
-       }
-
-       /* following Mesh convention; we use vertex coordinate itself for normal in this case */
-       for (i = 0; i < numVerts; i++) {
-               MVert *mv = &mverts[i];
-               float *no = tnorms[i];
-               
-               if (UNLIKELY(normalize_v3(no) == 0.0f)) {
-                       normalize_v3_v3(no, mv->co);
-               }
-
-               normal_float_to_short_v3(mv->no, no);
+       if (mesh->totpoly && mesh->totface == 0) {
+               BKE_mesh_tessface_calc(mesh);
        }
-       
-       MEM_freeN(tnorms);
-
-       if (fnors != faceNors_r)
-               MEM_freeN(fnors);
 }
 
-static void bm_corners_to_loops_ex(ID *id, CustomData *fdata, CustomData *ldata, CustomData *pdata,
-                                   MFace *mface, int totloop, int findex, int loopstart, int numTex, int numCol)
-{
-       MTFace *texface;
-       MTexPoly *texpoly;
-       MCol *mcol;
-       MLoopCol *mloopcol;
-       MLoopUV *mloopuv;
-       MFace *mf;
-       int i;
-
-       mf = mface + findex;
-
-       for (i = 0; i < numTex; i++) {
-               texface = CustomData_get_n(fdata, CD_MTFACE, findex, i);
-               texpoly = CustomData_get_n(pdata, CD_MTEXPOLY, findex, i);
-
-               ME_MTEXFACE_CPY(texpoly, texface);
-
-               mloopuv = CustomData_get_n(ldata, CD_MLOOPUV, loopstart, i);
-               copy_v2_v2(mloopuv->uv, texface->uv[0]); mloopuv++;
-               copy_v2_v2(mloopuv->uv, texface->uv[1]); mloopuv++;
-               copy_v2_v2(mloopuv->uv, texface->uv[2]); mloopuv++;
-
-               if (mf->v4) {
-                       copy_v2_v2(mloopuv->uv, texface->uv[3]); mloopuv++;
-               }
-       }
-
-       for (i = 0; i < numCol; i++) {
-               mloopcol = CustomData_get_n(ldata, CD_MLOOPCOL, loopstart, i);
-               mcol = CustomData_get_n(fdata, CD_MCOL, findex, i);
-
-               MESH_MLOOPCOL_FROM_MCOL(mloopcol, &mcol[0]); mloopcol++;
-               MESH_MLOOPCOL_FROM_MCOL(mloopcol, &mcol[1]); mloopcol++;
-               MESH_MLOOPCOL_FROM_MCOL(mloopcol, &mcol[2]); mloopcol++;
-               if (mf->v4) {
-                       MESH_MLOOPCOL_FROM_MCOL(mloopcol, &mcol[3]); mloopcol++;
-               }
-       }
-
-       if (CustomData_has_layer(fdata, CD_MDISPS)) {
-               MDisps *ld = CustomData_get(ldata, loopstart, CD_MDISPS);
-               MDisps *fd = CustomData_get(fdata, findex, CD_MDISPS);
-               float (*disps)[3] = fd->disps;
-               int tot = mf->v4 ? 4 : 3;
-               int side, corners;
-
-               if (CustomData_external_test(fdata, CD_MDISPS)) {
-                       if (id && fdata->external) {
-                               CustomData_external_add(ldata, id, CD_MDISPS,
-                                                       totloop, fdata->external->filename);
-                       }
-               }
-
-               corners = multires_mdisp_corners(fd);
-
-               if (corners == 0) {
-                       /* Empty MDisp layers appear in at least one of the sintel.blend files.
-                        * Not sure why this happens, but it seems fine to just ignore them here.
-                        * If (corners == 0) for a non-empty layer though, something went wrong. */
-                       BLI_assert(fd->totdisp == 0);
-               }
-               else {
-                       side = sqrt(fd->totdisp / corners);
-
-                       for (i = 0; i < tot; i++, disps += side * side, ld++) {
-                               ld->totdisp = side * side;
-                               ld->level = (int)(logf(side - 1.0f) / (float)M_LN2) + 1;
-
-                               if (ld->disps)
-                                       MEM_freeN(ld->disps);
-
-                               ld->disps = MEM_mallocN(sizeof(float) * 3 * side * side, "converted loop mdisps");
-                               if (fd->disps) {
-                                       memcpy(ld->disps, disps, sizeof(float) * 3 * side * side);
-                               }
-                               else {
-                                       memset(ld->disps, 0, sizeof(float) * 3 * side * side);
-                               }
-                       }
-               }
-       }
-}
-
-void BKE_mesh_convert_mfaces_to_mpolys(Mesh *mesh)
-{
-       BKE_mesh_convert_mfaces_to_mpolys_ex(&mesh->id, &mesh->fdata, &mesh->ldata, &mesh->pdata,
-                                            mesh->totedge, mesh->totface, mesh->totloop, mesh->totpoly,
-                                            mesh->medge, mesh->mface,
-                                            &mesh->totloop, &mesh->totpoly, &mesh->mloop, &mesh->mpoly);
-
-       BKE_mesh_update_customdata_pointers(mesh, true);
-}
-
-/* the same as BKE_mesh_convert_mfaces_to_mpolys but oriented to be used in do_versions from readfile.c
- * the difference is how active/render/clone/stencil indices are handled here
- *
- * normally thay're being set from pdata which totally makes sense for meshes which are already
- * converted to bmesh structures, but when loading older files indices shall be updated in other
- * way around, so newly added pdata and ldata would have this indices set based on fdata layer
- *
- * this is normally only needed when reading older files, in all other cases BKE_mesh_convert_mfaces_to_mpolys
- * shall be always used
- */
-void BKE_mesh_do_versions_convert_mfaces_to_mpolys(Mesh *mesh)
-{
-       BKE_mesh_convert_mfaces_to_mpolys_ex(&mesh->id, &mesh->fdata, &mesh->ldata, &mesh->pdata,
-                                            mesh->totedge, mesh->totface, mesh->totloop, mesh->totpoly,
-                                            mesh->medge, mesh->mface,
-                                            &mesh->totloop, &mesh->totpoly, &mesh->mloop, &mesh->mpoly);
-
-       CustomData_bmesh_do_versions_update_active_layers(&mesh->fdata, &mesh->pdata, &mesh->ldata);
-
-       BKE_mesh_update_customdata_pointers(mesh, true);
-}
-
-void BKE_mesh_convert_mfaces_to_mpolys_ex(ID *id, CustomData *fdata, CustomData *ldata, CustomData *pdata,
-                                          int totedge_i, int totface_i, int totloop_i, int totpoly_i,
-                                          MEdge *medge, MFace *mface,
-                                          int *totloop_r, int *totpoly_r,
-                                          MLoop **mloop_r, MPoly **mpoly_r)
-{
-       MFace *mf;
-       MLoop *ml, *mloop;
-       MPoly *mp, *mpoly;
-       MEdge *me;
-       EdgeHash *eh;
-       int numTex, numCol;
-       int i, j, totloop, totpoly, *polyindex;
-
-       /* just in case some of these layers are filled in (can happen with python created meshes) */
-       CustomData_free(ldata, totloop_i);
-       CustomData_free(pdata, totpoly_i);
-
-       totpoly = totface_i;
-       mpoly = MEM_callocN(sizeof(MPoly) * totpoly, "mpoly converted");
-       CustomData_add_layer(pdata, CD_MPOLY, CD_ASSIGN, mpoly, totpoly);
-
-       numTex = CustomData_number_of_layers(fdata, CD_MTFACE);
-       numCol = CustomData_number_of_layers(fdata, CD_MCOL);
-
-       totloop = 0;
-       mf = mface;
-       for (i = 0; i < totface_i; i++, mf++) {
-               totloop += mf->v4 ? 4 : 3;
-       }
-
-       mloop = MEM_callocN(sizeof(MLoop) * totloop, "mloop converted");
-
-       CustomData_add_layer(ldata, CD_MLOOP, CD_ASSIGN, mloop, totloop);
-
-       CustomData_to_bmeshpoly(fdata, pdata, ldata, totloop, totpoly);
-
-       if (id) {
-               /* ensure external data is transferred */
-               CustomData_external_read(fdata, id, CD_MASK_MDISPS, totface_i);
-       }
-
-       eh = BLI_edgehash_new_ex(__func__, totedge_i);
-
-       /* build edge hash */
-       me = medge;
-       for (i = 0; i < totedge_i; i++, me++) {
-               BLI_edgehash_insert(eh, me->v1, me->v2, SET_INT_IN_POINTER(i));
-
-               /* unrelated but avoid having the FGON flag enabled, so we can reuse it later for something else */
-               me->flag &= ~ME_FGON;
-       }
-
-       polyindex = CustomData_get_layer(fdata, CD_ORIGINDEX);
-
-       j = 0; /* current loop index */
-       ml = mloop;
-       mf = mface;
-       mp = mpoly;
-       for (i = 0; i < totface_i; i++, mf++, mp++) {
-               mp->loopstart = j;
-
-               mp->totloop = mf->v4 ? 4 : 3;
-
-               mp->mat_nr = mf->mat_nr;
-               mp->flag = mf->flag;
-
-#       define ML(v1, v2) { \
-                       ml->v = mf->v1; ml->e = GET_INT_FROM_POINTER(BLI_edgehash_lookup(eh, mf->v1, mf->v2)); ml++; j++; \
-               } (void)0
-
-               ML(v1, v2);
-               ML(v2, v3);
-               if (mf->v4) {
-                       ML(v3, v4);
-                       ML(v4, v1);
-               }
-               else {
-                       ML(v3, v1);
-               }
-
-#       undef ML
-
-               bm_corners_to_loops_ex(id, fdata, ldata, pdata, mface, totloop, i, mp->loopstart, numTex, numCol);
-
-               if (polyindex) {
-                       *polyindex = i;
-                       polyindex++;
-               }
-       }
-
-       /* note, we don't convert NGons at all, these are not even real ngons,
-        * they have their own UV's, colors etc - its more an editing feature. */
-
-       BLI_edgehash_free(eh, NULL);
-
-       *totpoly_r = totpoly;
-       *totloop_r = totloop;
-       *mpoly_r = mpoly;
-       *mloop_r = mloop;
-}
-
-float (*BKE_mesh_vertexCos_get(Mesh *me, int *r_numVerts))[3]
-{
-       int i, numVerts = me->totvert;
-       float (*cos)[3] = MEM_mallocN(sizeof(*cos) * numVerts, "vertexcos1");
-
-       if (r_numVerts) *r_numVerts = numVerts;
-       for (i = 0; i < numVerts; i++)
-               copy_v3_v3(cos[i], me->mvert[i].co);
-
-       return cos;
-}
-
-
-/* ngon version wip, based on EDBM_uv_vert_map_create */
-/* this replaces the non bmesh function (in trunk) which takes MTFace's, if we ever need it back we could
- * but for now this replaces it because its unused. */
-
-UvVertMap *BKE_mesh_uv_vert_map_create(struct MPoly *mpoly, struct MLoop *mloop, struct MLoopUV *mloopuv,
-                                       unsigned int totpoly, unsigned int totvert, int selected, float *limit)
-{
-       UvVertMap *vmap;
-       UvMapVert *buf;
-       MPoly *mp;
-       unsigned int a;
-       int i, totuv, nverts;
-
-       totuv = 0;
-
-       /* generate UvMapVert array */
-       mp = mpoly;
-       for (a = 0; a < totpoly; a++, mp++)
-               if (!selected || (!(mp->flag & ME_HIDE) && (mp->flag & ME_FACE_SEL)))
-                       totuv += mp->totloop;
-
-       if (totuv == 0)
-               return NULL;
-       
-       vmap = (UvVertMap *)MEM_callocN(sizeof(*vmap), "UvVertMap");
-       if (!vmap)
-               return NULL;
-
-       vmap->vert = (UvMapVert **)MEM_callocN(sizeof(*vmap->vert) * totvert, "UvMapVert*");
-       buf = vmap->buf = (UvMapVert *)MEM_callocN(sizeof(*vmap->buf) * totuv, "UvMapVert");
-
-       if (!vmap->vert || !vmap->buf) {
-               BKE_mesh_uv_vert_map_free(vmap);
-               return NULL;
-       }
-
-       mp = mpoly;
-       for (a = 0; a < totpoly; a++, mp++) {
-               if (!selected || (!(mp->flag & ME_HIDE) && (mp->flag & ME_FACE_SEL))) {
-                       nverts = mp->totloop;
-
-                       for (i = 0; i < nverts; i++) {
-                               buf->tfindex = i;
-                               buf->f = a;
-                               buf->separate = 0;
-                               buf->next = vmap->vert[mloop[mp->loopstart + i].v];
-                               vmap->vert[mloop[mp->loopstart + i].v] = buf;
-                               buf++;
-                       }
-               }
-       }
-       
-       /* sort individual uvs for each vert */
-       for (a = 0; a < totvert; a++) {
-               UvMapVert *newvlist = NULL, *vlist = vmap->vert[a];
-               UvMapVert *iterv, *v, *lastv, *next;
-               float *uv, *uv2, uvdiff[2];
-
-               while (vlist) {
-                       v = vlist;
-                       vlist = vlist->next;
-                       v->next = newvlist;
-                       newvlist = v;
-
-                       uv = mloopuv[mpoly[v->f].loopstart + v->tfindex].uv;
-                       lastv = NULL;
-                       iterv = vlist;
-
-                       while (iterv) {
-                               next = iterv->next;
-
-                               uv2 = mloopuv[mpoly[iterv->f].loopstart + iterv->tfindex].uv;
-                               sub_v2_v2v2(uvdiff, uv2, uv);
-
-
-                               if (fabsf(uv[0] - uv2[0]) < limit[0] && fabsf(uv[1] - uv2[1]) < limit[1]) {
-                                       if (lastv) lastv->next = next;
-                                       else vlist = next;
-                                       iterv->next = newvlist;
-                                       newvlist = iterv;
-                               }
-                               else
-                                       lastv = iterv;
-
-                               iterv = next;
-                       }
-
-                       newvlist->separate = 1;
-               }
-
-               vmap->vert[a] = newvlist;
-       }
-       
-       return vmap;
-}
-
-UvMapVert *BKE_mesh_uv_vert_map_get_vert(UvVertMap *vmap, unsigned int v)
-{
-       return vmap->vert[v];
-}
-
-void BKE_mesh_uv_vert_map_free(UvVertMap *vmap)
-{
-       if (vmap) {
-               if (vmap->vert) MEM_freeN(vmap->vert);
-               if (vmap->buf) MEM_freeN(vmap->buf);
-               MEM_freeN(vmap);
-       }
-}
-
-/* Generates a map where the key is the vertex and the value is a list
- * of polys that use that vertex as a corner. The lists are allocated
- * from one memory pool. */
-void BKE_mesh_vert_poly_map_create(MeshElemMap **r_map, int **r_mem,
-                                   const MPoly *mpoly, const MLoop *mloop,
-                                   int totvert, int totpoly, int totloop)
-{
-       MeshElemMap *map = MEM_callocN(sizeof(MeshElemMap) * totvert, "vert poly map");
-       int *indices, *index_iter;
-       int i, j;
-
-       indices = index_iter = MEM_mallocN(sizeof(int) * totloop, "vert poly map mem");
-
-       /* Count number of polys for each vertex */
-       for (i = 0; i < totpoly; i++) {
-               const MPoly *p = &mpoly[i];
-               
-               for (j = 0; j < p->totloop; j++)
-                       map[mloop[p->loopstart + j].v].count++;
-       }
-
-       /* Assign indices mem */
-       for (i = 0; i < totvert; i++) {
-               map[i].indices = index_iter;
-               index_iter += map[i].count;
-
-               /* Reset 'count' for use as index in last loop */
-               map[i].count = 0;
-       }
-               
-       /* Find the users */
-       for (i = 0; i < totpoly; i++) {
-               const MPoly *p = &mpoly[i];
-               
-               for (j = 0; j < p->totloop; j++) {
-                       int v = mloop[p->loopstart + j].v;
-                       
-                       map[v].indices[map[v].count] = i;
-                       map[v].count++;
-               }
-       }
-
-       *r_map = map;
-       *r_mem = indices;
-}
-
-/* Generates a map where the key is the vertex and the value is a list
- * of edges that use that vertex as an endpoint. The lists are allocated
- * from one memory pool. */
-void BKE_mesh_vert_edge_map_create(MeshElemMap **r_map, int **r_mem,
-                                   const MEdge *medge, int totvert, int totedge)
-{
-       MeshElemMap *map = MEM_callocN(sizeof(MeshElemMap) * totvert, "vert-edge map");
-       int *indices = MEM_mallocN(sizeof(int) * totedge * 2, "vert-edge map mem");
-       int *i_pt = indices;
-
-       int i;
-
-       /* Count number of edges for each vertex */
-       for (i = 0; i < totedge; i++) {
-               map[medge[i].v1].count++;
-               map[medge[i].v2].count++;
-       }
-
-       /* Assign indices mem */
-       for (i = 0; i < totvert; i++) {
-               map[i].indices = i_pt;
-               i_pt += map[i].count;
-
-               /* Reset 'count' for use as index in last loop */
-               map[i].count = 0;
-       }
-               
-       /* Find the users */
-       for (i = 0; i < totedge; i++) {
-               const int v[2] = {medge[i].v1, medge[i].v2};
-
-               map[v[0]].indices[map[v[0]].count] = i;
-               map[v[1]].indices[map[v[1]].count] = i;
-               
-               map[v[0]].count++;
-               map[v[1]].count++;
-       }
-
-       *r_map = map;
-       *r_mem = indices;
-}
-
-void BKE_mesh_edge_poly_map_create(MeshElemMap **r_map, int **r_mem,
-                                   const MEdge *UNUSED(medge), const int totedge,
-                                   const MPoly *mpoly, const int totpoly,
-                                   const MLoop *mloop, const int totloop)
-{
-       MeshElemMap *map = MEM_callocN(sizeof(MeshElemMap) * totedge, "edge-poly map");
-       int *indices = MEM_mallocN(sizeof(int) * totloop, "edge-poly map mem");
-       int *index_step;
-       const MPoly *mp;
-       int i;
-
-       /* count face users */
-       for (i = 0, mp = mpoly; i < totpoly; mp++, i++) {
-               const MLoop *ml;
-               int j = mp->totloop;
-               for (ml = &mloop[mp->loopstart]; j--; ml++) {
-                       map[ml->e].count++;
-               }
-       }
-
-       /* create offsets */
-       index_step = indices;
-       for (i = 0; i < totedge; i++) {
-               map[i].indices = index_step;
-               index_step += map[i].count;
-
-               /* re-count, using this as an index below */
-               map[i].count = 0;
-
-       }
-
-       /* assign poly-edge users */
-       for (i = 0, mp = mpoly; i < totpoly; mp++, i++) {
-               const MLoop *ml;
-               int j = mp->totloop;
-               for (ml = &mloop[mp->loopstart]; j--; ml++) {
-                       MeshElemMap *map_ele = &map[ml->e];
-                       map_ele->indices[map_ele->count++] = i;
-               }
-       }
-
-       *r_map = map;
-       *r_mem = indices;
-}
-
-void BKE_mesh_loops_to_mface_corners(CustomData *fdata, CustomData *ldata,
-                                     CustomData *pdata, int lindex[4], int findex,
-                                     const int polyindex,
-                                     const int mf_len, /* 3 or 4 */
-
-                                     /* cache values to avoid lookups every time */
-                                     const int numTex, /* CustomData_number_of_layers(pdata, CD_MTEXPOLY) */
-                                     const int numCol, /* CustomData_number_of_layers(ldata, CD_MLOOPCOL) */
-                                     const int hasPCol, /* CustomData_has_layer(ldata, CD_PREVIEW_MLOOPCOL) */
-                                     const int hasOrigSpace /* CustomData_has_layer(ldata, CD_ORIGSPACE_MLOOP) */
-                                     )
-{
-       MTFace *texface;
-       MTexPoly *texpoly;
-       MCol *mcol;
-       MLoopCol *mloopcol;
-       MLoopUV *mloopuv;
-       int i, j;
-       
-       for (i = 0; i < numTex; i++) {
-               texface = CustomData_get_n(fdata, CD_MTFACE, findex, i);
-               texpoly = CustomData_get_n(pdata, CD_MTEXPOLY, polyindex, i);
-
-               ME_MTEXFACE_CPY(texface, texpoly);
-
-               for (j = 0; j < mf_len; j++) {
-                       mloopuv = CustomData_get_n(ldata, CD_MLOOPUV, lindex[j], i);
-                       copy_v2_v2(texface->uv[j], mloopuv->uv);
-               }
-       }
-
-       for (i = 0; i < numCol; i++) {
-               mcol = CustomData_get_n(fdata, CD_MCOL, findex, i);
-
-               for (j = 0; j < mf_len; j++) {
-                       mloopcol = CustomData_get_n(ldata, CD_MLOOPCOL, lindex[j], i);
-                       MESH_MLOOPCOL_TO_MCOL(mloopcol, &mcol[j]);
-               }
-       }
-
-       if (hasPCol) {
-               mcol = CustomData_get(fdata,  findex, CD_PREVIEW_MCOL);
-
-               for (j = 0; j < mf_len; j++) {
-                       mloopcol = CustomData_get(ldata, lindex[j], CD_PREVIEW_MLOOPCOL);
-                       MESH_MLOOPCOL_TO_MCOL(mloopcol, &mcol[j]);
-               }
-       }
-
-       if (hasOrigSpace) {
-               OrigSpaceFace *of = CustomData_get(fdata, findex, CD_ORIGSPACE);
-               OrigSpaceLoop *lof;
-
-               for (j = 0; j < mf_len; j++) {
-                       lof = CustomData_get(ldata, lindex[j], CD_ORIGSPACE_MLOOP);
-                       copy_v2_v2(of->uv[j], lof->uv);
-               }
-       }
-}
-
-/*
- * this function recreates a tessellation.
- * returns number of tessellation faces.
- */
-int BKE_mesh_recalc_tessellation(CustomData *fdata,
-                                 CustomData *ldata, CustomData *pdata,
-                                 MVert *mvert, int totface, int totloop,
-                                 int totpoly,
-                                 /* when tessellating to recalculate normals after
-                                  * we can skip copying here */
-                                 const bool do_face_nor_cpy)
-{
-       /* use this to avoid locking pthread for _every_ polygon
-        * and calling the fill function */
-
-#define USE_TESSFACE_SPEEDUP
-#define USE_TESSFACE_QUADS // NEEDS FURTHER TESTING
-
-#define TESSFACE_SCANFILL (1 << 0)
-#define TESSFACE_IS_QUAD  (1 << 1)
-
-       const int looptris_tot = poly_to_tri_count(totpoly, totloop);
-
-       MPoly *mp, *mpoly;
-       MLoop *ml, *mloop;
-       MFace *mface, *mf;
-       ScanFillContext sf_ctx;
-       ScanFillVert *sf_vert, *sf_vert_last, *sf_vert_first;
-       ScanFillFace *sf_tri;
-       MemArena *sf_arena = NULL;
-       int *mface_to_poly_map;
-       int lindex[4]; /* only ever use 3 in this case */
-       int poly_index, j, mface_index;
-
-       const int numTex = CustomData_number_of_layers(pdata, CD_MTEXPOLY);
-       const int numCol = CustomData_number_of_layers(ldata, CD_MLOOPCOL);
-       const int hasPCol = CustomData_has_layer(ldata, CD_PREVIEW_MLOOPCOL);
-       const int hasOrigSpace = CustomData_has_layer(ldata, CD_ORIGSPACE_MLOOP);
-
-       mpoly = CustomData_get_layer(pdata, CD_MPOLY);
-       mloop = CustomData_get_layer(ldata, CD_MLOOP);
-
-       /* allocate the length of totfaces, avoid many small reallocs,
-        * if all faces are tri's it will be correct, quads == 2x allocs */
-       /* take care. we are _not_ calloc'ing so be sure to initialize each field */
-       mface_to_poly_map = MEM_mallocN(sizeof(*mface_to_poly_map) * looptris_tot, __func__);
-       mface             = MEM_mallocN(sizeof(*mface) *             looptris_tot, __func__);
-
-       mface_index = 0;
-       mp = mpoly;
-       for (poly_index = 0; poly_index < totpoly; poly_index++, mp++) {
-               if (mp->totloop < 3) {
-                       /* do nothing */
-               }
-
-#ifdef USE_TESSFACE_SPEEDUP
-
-#define ML_TO_MF(i1, i2, i3)                                                  \
-               mface_to_poly_map[mface_index] = poly_index;                          \
-               mf = &mface[mface_index];                                             \
-               /* set loop indices, transformed to vert indices later */             \
-               mf->v1 = mp->loopstart + i1;                                          \
-               mf->v2 = mp->loopstart + i2;                                          \
-               mf->v3 = mp->loopstart + i3;                                          \
-               mf->v4 = 0;                                                           \
-               mf->mat_nr = mp->mat_nr;                                              \
-               mf->flag = mp->flag;                                                  \
-               mf->edcode = 0;                                                       \
-               (void)0
-
-/* ALMOST IDENTICAL TO DEFINE ABOVE (see EXCEPTION) */
-#define ML_TO_MF_QUAD()                                                       \
-               mface_to_poly_map[mface_index] = poly_index;                          \
-               mf = &mface[mface_index];                                             \
-               /* set loop indices, transformed to vert indices later */             \
-               mf->v1 = mp->loopstart + 0; /* EXCEPTION */                           \
-               mf->v2 = mp->loopstart + 1; /* EXCEPTION */                           \
-               mf->v3 = mp->loopstart + 2; /* EXCEPTION */                           \
-               mf->v4 = mp->loopstart + 3; /* EXCEPTION */                           \
-               mf->mat_nr = mp->mat_nr;                                              \
-               mf->flag = mp->flag;                                                  \
-               mf->edcode = TESSFACE_IS_QUAD; /* EXCEPTION */                        \
-               (void)0
-
-
-               else if (mp->totloop == 3) {
-                       ML_TO_MF(0, 1, 2);
-                       mface_index++;
-               }
-               else if (mp->totloop == 4) {
-#ifdef USE_TESSFACE_QUADS
-                       ML_TO_MF_QUAD();
-                       mface_index++;
-#else
-                       ML_TO_MF(0, 1, 2);
-                       mface_index++;
-                       ML_TO_MF(0, 2, 3);
-                       mface_index++;
-#endif
-               }
-#endif /* USE_TESSFACE_SPEEDUP */
-               else {
-#define USE_TESSFACE_CALCNORMAL
-
-                       int totfilltri;
-
-#ifdef USE_TESSFACE_CALCNORMAL
-                       float normal[3];
-                       zero_v3(normal);
-#endif
-                       ml = mloop + mp->loopstart;
-                       
-                       if (UNLIKELY(sf_arena == NULL)) {
-                               sf_arena = BLI_memarena_new(BLI_SCANFILL_ARENA_SIZE, __func__);
-                       }
-
-                       BLI_scanfill_begin_arena(&sf_ctx, sf_arena);
-                       sf_vert_first = NULL;
-                       sf_vert_last = NULL;
-                       for (j = 0; j < mp->totloop; j++, ml++) {
-                               sf_vert = BLI_scanfill_vert_add(&sf_ctx, mvert[ml->v].co);
-       
-                               sf_vert->keyindex = mp->loopstart + j;
-       
-                               if (sf_vert_last) {
-                                       BLI_scanfill_edge_add(&sf_ctx, sf_vert_last, sf_vert);
-#ifdef USE_TESSFACE_CALCNORMAL
-                                       add_newell_cross_v3_v3v3(normal, sf_vert_last->co, sf_vert->co);
-#endif
-                               }
-       
-                               if (!sf_vert_first)
-                                       sf_vert_first = sf_vert;
-                               sf_vert_last = sf_vert;
-                       }
-                       BLI_scanfill_edge_add(&sf_ctx, sf_vert_last, sf_vert_first);
-#ifdef USE_TESSFACE_CALCNORMAL
-                       add_newell_cross_v3_v3v3(normal, sf_vert_last->co, sf_vert_first->co);
-                       if (UNLIKELY(normalize_v3(normal) == 0.0f)) {
-                               normal[2] = 1.0f;
-                       }
-                       totfilltri = BLI_scanfill_calc_ex(&sf_ctx, 0, normal);
-#else
-                       totfilltri = BLI_scanfill_calc(&sf_ctx, 0);
-#endif
-                       BLI_assert(totfilltri <= mp->totloop - 2);
-                       (void)totfilltri;
-
-                       for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next, mf++) {
-                               mface_to_poly_map[mface_index] = poly_index;
-                               mf = &mface[mface_index];
-
-                               /* set loop indices, transformed to vert indices later */
-                               mf->v1 = sf_tri->v1->keyindex;
-                               mf->v2 = sf_tri->v2->keyindex;
-                               mf->v3 = sf_tri->v3->keyindex;
-                               mf->v4 = 0;
-
-                               mf->mat_nr = mp->mat_nr;
-                               mf->flag = mp->flag;
-
-#ifdef USE_TESSFACE_SPEEDUP
-                               mf->edcode = TESSFACE_SCANFILL; /* tag for sorting loop indices */
-#endif
-
-                               mface_index++;
-                       }
-       
-                       BLI_scanfill_end_arena(&sf_ctx, sf_arena);
-
-#undef USE_TESSFACE_CALCNORMAL
-               }
-       }
-
-       if (sf_arena) {
-               BLI_memarena_free(sf_arena);
-               sf_arena = NULL;
-       }
-
-       CustomData_free(fdata, totface);
-       totface = mface_index;
-
-       BLI_assert(totface <= looptris_tot);
-
-       /* not essential but without this we store over-alloc'd memory in the CustomData layers */
-       if (LIKELY(looptris_tot != totface)) {
-               mface = MEM_reallocN(mface, sizeof(*mface) * totface);
-               mface_to_poly_map = MEM_reallocN(mface_to_poly_map, sizeof(*mface_to_poly_map) * totface);
-       }
-
-       CustomData_add_layer(fdata, CD_MFACE, CD_ASSIGN, mface, totface);
-
-       /* CD_ORIGINDEX will contain an array of indices from tessfaces to the polygons
-        * they are directly tessellated from */
-       CustomData_add_layer(fdata, CD_ORIGINDEX, CD_ASSIGN, mface_to_poly_map, totface);
-       CustomData_from_bmeshpoly(fdata, pdata, ldata, totface);
-
-       if (do_face_nor_cpy) {
-               /* If polys have a normals layer, copying that to faces can help
-                * avoid the need to recalculate normals later */
-               if (CustomData_has_layer(pdata, CD_NORMAL)) {
-                       float (*pnors)[3] = CustomData_get_layer(pdata, CD_NORMAL);
-                       float (*fnors)[3] = CustomData_add_layer(fdata, CD_NORMAL, CD_CALLOC, NULL, totface);
-                       for (mface_index = 0; mface_index < totface; mface_index++) {
-                               copy_v3_v3(fnors[mface_index], pnors[mface_to_poly_map[mface_index]]);
-                       }
-               }
-       }
-
-       mf = mface;
-       for (mface_index = 0; mface_index < totface; mface_index++, mf++) {
-
-#ifdef USE_TESSFACE_QUADS
-               const int mf_len = mf->edcode & TESSFACE_IS_QUAD ? 4 : 3;
-#endif
-
-#ifdef USE_TESSFACE_SPEEDUP
-               /* skip sorting when not using ngons */
-               if (UNLIKELY(mf->edcode & TESSFACE_SCANFILL))
-#endif
-               {
-                       /* sort loop indices to ensure winding is correct */
-                       if (mf->v1 > mf->v2) SWAP(unsigned int, mf->v1, mf->v2);
-                       if (mf->v2 > mf->v3) SWAP(unsigned int, mf->v2, mf->v3);
-                       if (mf->v1 > mf->v2) SWAP(unsigned int, mf->v1, mf->v2);
-
-                       if (mf->v1 > mf->v2) SWAP(unsigned int, mf->v1, mf->v2);
-                       if (mf->v2 > mf->v3) SWAP(unsigned int, mf->v2, mf->v3);
-                       if (mf->v1 > mf->v2) SWAP(unsigned int, mf->v1, mf->v2);
-               }
-
-               /* end abusing the edcode */
-#if defined(USE_TESSFACE_QUADS) || defined(USE_TESSFACE_SPEEDUP)
-               mf->edcode = 0;
-#endif
-
-
-               lindex[0] = mf->v1;
-               lindex[1] = mf->v2;
-               lindex[2] = mf->v3;
-#ifdef USE_TESSFACE_QUADS
-               if (mf_len == 4) lindex[3] = mf->v4;
-#endif
-
-               /*transform loop indices to vert indices*/
-               mf->v1 = mloop[mf->v1].v;
-               mf->v2 = mloop[mf->v2].v;
-               mf->v3 = mloop[mf->v3].v;
-#ifdef USE_TESSFACE_QUADS
-               if (mf_len == 4) mf->v4 = mloop[mf->v4].v;
-#endif
-
-               BKE_mesh_loops_to_mface_corners(fdata, ldata, pdata,
-                                               lindex, mface_index, mface_to_poly_map[mface_index],
-#ifdef USE_TESSFACE_QUADS
-                                               mf_len,
-#else
-                                               3,
-#endif
-                                               numTex, numCol, hasPCol, hasOrigSpace);
-
-
-#ifdef USE_TESSFACE_QUADS
-               test_index_face(mf, fdata, mface_index, mf_len);
-#endif
-
-       }
-
-       return totface;
-
-#undef USE_TESSFACE_SPEEDUP
-
-}
-
-
-#ifdef USE_BMESH_SAVE_AS_COMPAT
-
-/*
- * this function recreates a tessellation.
- * returns number of tessellation faces.
- */
-int BKE_mesh_mpoly_to_mface(struct CustomData *fdata, struct CustomData *ldata,
-                            struct CustomData *pdata, int totface, int UNUSED(totloop), int totpoly)
-{
-       MLoop *mloop;
-
-       int lindex[4];
-       int i;
-       int k;
-
-       MPoly *mp, *mpoly;
-       MFace *mface = NULL, *mf;
-       BLI_array_declare(mface);
-
-       const int numTex = CustomData_number_of_layers(pdata, CD_MTEXPOLY);
-       const int numCol = CustomData_number_of_layers(ldata, CD_MLOOPCOL);
-       const int hasPCol = CustomData_has_layer(ldata, CD_PREVIEW_MLOOPCOL);
-       const int hasOrigSpace = CustomData_has_layer(ldata, CD_ORIGSPACE_MLOOP);
-
-       mpoly = CustomData_get_layer(pdata, CD_MPOLY);
-       mloop = CustomData_get_layer(ldata, CD_MLOOP);
-
-       mp = mpoly;
-       k = 0;
-       for (i = 0; i < totpoly; i++, mp++) {
-               if (ELEM(mp->totloop, 3, 4)) {
-                       BLI_array_grow_one(mface);
-                       mf = &mface[k];
-
-                       mf->mat_nr = mp->mat_nr;
-                       mf->flag = mp->flag;
-
-                       mf->v1 = mp->loopstart + 0;
-                       mf->v2 = mp->loopstart + 1;
-                       mf->v3 = mp->loopstart + 2;
-                       mf->v4 = (mp->totloop == 4) ? (mp->loopstart + 3) : 0;
-
-                       /* abuse edcode for temp storage and clear next loop */
-                       mf->edcode = (char)mp->totloop; /* only ever 3 or 4 */
-
-                       k++;
-               }
-       }
-
-       CustomData_free(fdata, totface);
-
-       totface = k;
-
-       CustomData_add_layer(fdata, CD_MFACE, CD_ASSIGN, mface, totface);
-
-       CustomData_from_bmeshpoly(fdata, pdata, ldata, totface);
-
-       mp = mpoly;
-       k = 0;
-       for (i = 0; i < totpoly; i++, mp++) {
-               if (ELEM(mp->totloop, 3, 4)) {
-                       mf = &mface[k];
-
-                       if (mf->edcode == 3) {
-                               /* sort loop indices to ensure winding is correct */
-                               /* NO SORT - looks like we can skip this */
-
-                               lindex[0] = mf->v1;
-                               lindex[1] = mf->v2;
-                               lindex[2] = mf->v3;
-                               lindex[3] = 0; /* unused */
-
-                               /* transform loop indices to vert indices */
-                               mf->v1 = mloop[mf->v1].v;
-                               mf->v2 = mloop[mf->v2].v;
-                               mf->v3 = mloop[mf->v3].v;
-
-                               BKE_mesh_loops_to_mface_corners(fdata, ldata, pdata,
-                                                               lindex, k, i, 3,
-                                                               numTex, numCol, hasPCol, hasOrigSpace);
-                               test_index_face(mf, fdata, k, 3);
-                       }
-                       else {
-                               /* sort loop indices to ensure winding is correct */
-                               /* NO SORT - looks like we can skip this */
-
-                               lindex[0] = mf->v1;
-                               lindex[1] = mf->v2;
-                               lindex[2] = mf->v3;
-                               lindex[3] = mf->v4;
-
-                               /* transform loop indices to vert indices */
-                               mf->v1 = mloop[mf->v1].v;
-                               mf->v2 = mloop[mf->v2].v;
-                               mf->v3 = mloop[mf->v3].v;
-                               mf->v4 = mloop[mf->v4].v;
-
-                               BKE_mesh_loops_to_mface_corners(fdata, ldata, pdata,
-                                                               lindex, k, i, 4,
-                                                               numTex, numCol, hasPCol, hasOrigSpace);
-                               test_index_face(mf, fdata, k, 4);
-                       }
-
-                       mf->edcode = 0;
-
-                       k++;
-               }
-       }
-
-       return k;
-}
-#endif /* USE_BMESH_SAVE_AS_COMPAT */
-
-/*
- * COMPUTE POLY NORMAL
- *
- * Computes the normal of a planar 
- * polygon See Graphics Gems for 
- * computing newell normal.
- *
- */
-static void mesh_calc_ngon_normal(MPoly *mpoly, MLoop *loopstart, 
-                                  MVert *mvert, float normal[3])
-{
-       const int nverts = mpoly->totloop;
-       float const *v_prev = mvert[loopstart[nverts - 1].v].co;
-       float const *v_curr;
-       int i;
-
-       zero_v3(normal);
-
-       /* Newell's Method */
-       for (i = 0; i < nverts; i++) {
-               v_curr = mvert[loopstart[i].v].co;
-               add_newell_cross_v3_v3v3(normal, v_prev, v_curr);
-               v_prev = v_curr;
-       }
-
-       if (UNLIKELY(normalize_v3(normal) == 0.0f)) {
-               normal[2] = 1.0f; /* other axis set to 0.0 */
-       }
-}
-
-void BKE_mesh_calc_poly_normal(MPoly *mpoly, MLoop *loopstart,
-                               MVert *mvarray, float no[3])
-{
-       if (mpoly->totloop > 4) {
-               mesh_calc_ngon_normal(mpoly, loopstart, mvarray, no);
-       }
-       else if (mpoly->totloop == 3) {
-               normal_tri_v3(no,
-                             mvarray[loopstart[0].v].co,
-                             mvarray[loopstart[1].v].co,
-                             mvarray[loopstart[2].v].co
-                             );
-       }
-       else if (mpoly->totloop == 4) {
-               normal_quad_v3(no,
-                              mvarray[loopstart[0].v].co,
-                              mvarray[loopstart[1].v].co,
-                              mvarray[loopstart[2].v].co,
-                              mvarray[loopstart[3].v].co
-                              );
-       }
-       else { /* horrible, two sided face! */
-               no[0] = 0.0;
-               no[1] = 0.0;
-               no[2] = 1.0;
-       }
-}
-/* duplicate of function above _but_ takes coords rather then mverts */
-static void mesh_calc_ngon_normal_coords(MPoly *mpoly, MLoop *loopstart,
-                                         const float (*vertex_coords)[3], float normal[3])
-{
-       const int nverts = mpoly->totloop;
-       float const *v_prev = vertex_coords[loopstart[nverts - 1].v];
-       float const *v_curr;
-       int i;
-
-       zero_v3(normal);
-
-       /* Newell's Method */
-       for (i = 0; i < nverts; i++) {
-               v_curr = vertex_coords[loopstart[i].v];
-               add_newell_cross_v3_v3v3(normal, v_prev, v_curr);
-               v_prev = v_curr;
-       }
-
-       if (UNLIKELY(normalize_v3(normal) == 0.0f)) {
-               normal[2] = 1.0f; /* other axis set to 0.0 */
-       }
-}
-
-void BKE_mesh_calc_poly_normal_coords(MPoly *mpoly, MLoop *loopstart,
-                                      const float (*vertex_coords)[3], float no[3])
-{
-       if (mpoly->totloop > 4) {
-               mesh_calc_ngon_normal_coords(mpoly, loopstart, vertex_coords, no);
-       }
-       else if (mpoly->totloop == 3) {
-               normal_tri_v3(no,
-                             vertex_coords[loopstart[0].v],
-                             vertex_coords[loopstart[1].v],
-                             vertex_coords[loopstart[2].v]
-                             );
-       }
-       else if (mpoly->totloop == 4) {
-               normal_quad_v3(no,
-                              vertex_coords[loopstart[0].v],
-                              vertex_coords[loopstart[1].v],
-                              vertex_coords[loopstart[2].v],
-                              vertex_coords[loopstart[3].v]
-                              );
-       }
-       else { /* horrible, two sided face! */
-               no[0] = 0.0;
-               no[1] = 0.0;
-               no[2] = 1.0;
-       }
-}
-
-static void mesh_calc_ngon_center(MPoly *mpoly, MLoop *loopstart,
-                                  MVert *mvert, float cent[3])
-{
-       const float w = 1.0f / (float)mpoly->totloop;
-       int i;
-
-       zero_v3(cent);
-
-       for (i = 0; i < mpoly->totloop; i++) {
-               madd_v3_v3fl(cent, mvert[(loopstart++)->v].co, w);
-       }
-}
-
-void BKE_mesh_calc_poly_center(MPoly *mpoly, MLoop *loopstart,
-                               MVert *mvarray, float cent[3])
-{
-       if (mpoly->totloop == 3) {
-               cent_tri_v3(cent,
-                           mvarray[loopstart[0].v].co,
-                           mvarray[loopstart[1].v].co,
-                           mvarray[loopstart[2].v].co
-                           );
-       }
-       else if (mpoly->totloop == 4) {
-               cent_quad_v3(cent,
-                            mvarray[loopstart[0].v].co,
-                            mvarray[loopstart[1].v].co,
-                            mvarray[loopstart[2].v].co,
-                            mvarray[loopstart[3].v].co
-                            );
-       }
-       else {
-               mesh_calc_ngon_center(mpoly, loopstart, mvarray, cent);
-       }
-}
-
-/* note, passing polynormal is only a speedup so we can skip calculating it */
-float BKE_mesh_calc_poly_area(MPoly *mpoly, MLoop *loopstart,
-                              MVert *mvarray, const float polynormal[3])
-{
-       if (mpoly->totloop == 3) {
-               return area_tri_v3(mvarray[loopstart[0].v].co,
-                                  mvarray[loopstart[1].v].co,
-                                  mvarray[loopstart[2].v].co
-                                  );
-       }
-       else if (mpoly->totloop == 4) {
-               return area_quad_v3(mvarray[loopstart[0].v].co,
-                                   mvarray[loopstart[1].v].co,
-                                   mvarray[loopstart[2].v].co,
-                                   mvarray[loopstart[3].v].co
-                                   );
-       }
-       else {
-               int i;
-               MLoop *l_iter = loopstart;
-               float area, polynorm_local[3];
-               float (*vertexcos)[3] = BLI_array_alloca(vertexcos, mpoly->totloop);
-               const float *no = polynormal ? polynormal : polynorm_local;
-
-               /* pack vertex cos into an array for area_poly_v3 */
-               for (i = 0; i < mpoly->totloop; i++, l_iter++) {
-                       copy_v3_v3(vertexcos[i], mvarray[l_iter->v].co);
-               }
-
-               /* need normal for area_poly_v3 as well */
-               if (polynormal == NULL) {
-                       BKE_mesh_calc_poly_normal(mpoly, loopstart, mvarray, polynorm_local);
-               }
-
-               /* finally calculate the area */
-               area = area_poly_v3(mpoly->totloop, vertexcos, no);
-
-               return area;
-       }
-}
-
-/* note, results won't be correct if polygon is non-planar */
-static float mesh_calc_poly_planar_area_centroid(MPoly *mpoly, MLoop *loopstart, MVert *mvarray, float cent[3])
-{
-       int i;
-       float tri_area;
-       float total_area = 0.0f;
-       float v1[3], v2[3], v3[3], normal[3], tri_cent[3];
-
-       BKE_mesh_calc_poly_normal(mpoly, loopstart, mvarray, normal);
-       copy_v3_v3(v1, mvarray[loopstart[0].v].co);
-       copy_v3_v3(v2, mvarray[loopstart[1].v].co);
-       zero_v3(cent);
-
-       for (i = 2; i < mpoly->totloop; i++) {
-               copy_v3_v3(v3, mvarray[loopstart[i].v].co);
-
-               tri_area = area_tri_signed_v3(v1, v2, v3, normal);
-               total_area += tri_area;
-
-               cent_tri_v3(tri_cent, v1, v2, v3);
-               madd_v3_v3fl(cent, tri_cent, tri_area);
-
-               copy_v3_v3(v2, v3);
-       }
-
-       mul_v3_fl(cent, 1.0f / total_area);
-
-       return total_area;
-}
-
-/**
- * Calculate smooth groups from sharp edges.
- *
- * \param r_totgroup The total number of groups, 1 or more.
- * \return Polygon aligned array of group index values (bitflags if use_bitflags is true), starting at 1.
- */
-int *BKE_mesh_calc_smoothgroups(const MEdge *medge, const int totedge,
-                                const MPoly *mpoly, const int totpoly,
-                                const MLoop *mloop, const int totloop,
-                                int *r_totgroup, const bool use_bitflags)
-{
-       int *poly_groups;
-       int *poly_stack;
-
-       int poly_prev = 0;
-       const int temp_poly_group_id = 3;  /* Placeholder value. */
-       const int poly_group_id_overflowed = 5;  /* Group we could not find any available bit, will be reset to 0 at end */
-       int tot_group = 0;
-       bool group_id_overflow = false;
-
-       /* map vars */
-       MeshElemMap *edge_poly_map;
-       int *edge_poly_mem;
-
-       if (totpoly == 0) {
-               *r_totgroup = 0;
-               return NULL;
-       }
-
-       BKE_mesh_edge_poly_map_create(&edge_poly_map, &edge_poly_mem,
-                                     medge, totedge,
-                                     mpoly, totpoly,
-                                     mloop, totloop);
-
-       poly_groups = MEM_callocN(sizeof(int) * totpoly, __func__);
-       poly_stack  = MEM_mallocN(sizeof(int) * totpoly, __func__);
-
-       while (true) {
-               int poly;
-               int bit_poly_group_mask = 0;
-               int poly_group_id;
-               int ps_curr_idx = 0, ps_end_idx = 0;  /* stack indices */
-
-               for (poly = poly_prev; poly < totpoly; poly++) {
-                       if (poly_groups[poly] == 0) {
-                               break;
-                       }
-               }
-
-               if (poly == totpoly) {
-                       /* all done */
-                       break;
-               }
-
-               poly_group_id = use_bitflags ? temp_poly_group_id : ++tot_group;
-
-               /* start searching from here next time */
-               poly_prev = poly + 1;
-
-               poly_groups[poly] = poly_group_id;
-               poly_stack[ps_end_idx++] = poly;
-
-               while (ps_curr_idx != ps_end_idx) {
-                       const MPoly *mp;
-                       const MLoop *ml;
-                       int j;
-
-                       poly = poly_stack[ps_curr_idx++];
-                       BLI_assert(poly_groups[poly] == poly_group_id);
-
-                       mp = &mpoly[poly];
-                       for (ml = &mloop[mp->loopstart], j = mp->totloop; j--; ml++) {
-                               /* loop over poly users */
-                               const MeshElemMap *map_ele = &edge_poly_map[ml->e];
-                               int *p = map_ele->indices;
-                               int i = map_ele->count;
-                               if (!(medge[ml->e].flag & ME_SHARP)) {
-                                       for (; i--; p++) {
-                                               /* if we meet other non initialized its a bug */
-                                               BLI_assert(ELEM(poly_groups[*p], 0, poly_group_id));
-
-                                               if (poly_groups[*p] == 0) {
-                                                       poly_groups[*p] = poly_group_id;
-                                                       poly_stack[ps_end_idx++] = *p;
-                                               }
-                                       }
-                               }
-                               else if (use_bitflags) {
-                                       /* Find contiguous smooth groups already assigned, these are the values we can't reuse! */
-                                       for (; i--; p++) {
-                                               int bit = poly_groups[*p];
-                                               if (!ELEM3(bit, 0, poly_group_id, poly_group_id_overflowed) &&
-                                                   !(bit_poly_group_mask & bit))
-                                               {
-                                                       bit_poly_group_mask |= bit;
-                                               }
-                                       }
-                               }
-                       }
-               }
-               /* And now, we have all our poly from current group in poly_stack (from 0 to (ps_end_idx - 1)), as well as
-                * all smoothgroups bits we can't use in bit_poly_group_mask.
-                */
-               if (use_bitflags) {
-                       int i, *p, gid_bit = 0;
-                       poly_group_id = 1;
-
-                       /* Find first bit available! */
-                       for (; (poly_group_id & bit_poly_group_mask) && (gid_bit < 32); gid_bit++) {
-                               poly_group_id <<= 1;  /* will 'overflow' on last possible iteration. */
-                       }
-                       if (UNLIKELY(gid_bit > 31)) {
-                               /* All bits used in contiguous smooth groups, we can't do much!
-                                * Note: this is *very* unlikely - theoretically, four groups are enough, I don't think we can reach
-                                *       this goal with such a simple algo, but I don't think either we'll never need all 32 groups!
-                                */
-                               printf("Warning, could not find an available id for current smooth group, faces will me marked "
-                                      "as out of any smooth group...\n");
-                               poly_group_id = poly_group_id_overflowed; /* Can't use 0, will have to set them to this value later. */
-                               group_id_overflow = true;
-                       }
-                       if (gid_bit > tot_group) {
-                               tot_group = gid_bit;
-                       }
-                       /* And assign the final smooth group id to that poly group! */
-                       for (i = ps_end_idx, p = poly_stack; i--; p++) {
-                               poly_groups[*p] = poly_group_id;
-                       }
-               }
-       }
-
-       if (UNLIKELY(group_id_overflow)) {
-               int i = totpoly, *gid = poly_groups;
-               for (; i--; gid++) {
-                       if (*gid == poly_group_id_overflowed) {
-                               *gid = 0;
-                       }
-               }
-       }
-
-       MEM_freeN(edge_poly_map);
-       MEM_freeN(edge_poly_mem);
-       MEM_freeN(poly_stack);
-
-       *r_totgroup = tot_group + 1;
-
-       return poly_groups;
-}
-
-
-
-/**
- * This function takes the difference between 2 vertex-coord-arrays
- * (\a vert_cos_src, \a vert_cos_dst),
- * and applies the difference to \a vert_cos_new relative to \a vert_cos_org.
- *
- * \param vert_cos_src reference deform source.
- * \param vert_cos_dst reference deform destination.
- *
- * \param vert_cos_org reference for the output location.
- * \param vert_cos_new resulting coords.
- */
-void BKE_mesh_calc_relative_deform(
-        const MPoly *mpoly, const int totpoly,
-        const MLoop *mloop, const int totvert,
-
-        const float (*vert_cos_src)[3],
-        const float (*vert_cos_dst)[3],
-
-        const float (*vert_cos_org)[3],
-              float (*vert_cos_new)[3])
-{
-       const MPoly *mp;
-       int i;
-
-       int *vert_accum = MEM_callocN(sizeof(*vert_accum) * totvert, __func__);
-
-       memset(vert_cos_new, '\0', sizeof(*vert_cos_new) * totvert);
-
-       for (i = 0, mp = mpoly; i < totpoly; i++, mp++) {
-               const MLoop *loopstart = mloop + mp->loopstart;
-               int j;
-
-               for (j = 0; j < mp->totloop; j++) {
-                       int v_prev = (loopstart + ((mp->totloop + (j - 1)) % mp->totloop))->v;
-                       int v_curr = (loopstart + j)->v;
-                       int v_next = (loopstart + ((j + 1) % mp->totloop))->v;
-
-                       float tvec[3];
-
-                       barycentric_transform(
-                                   tvec, vert_cos_dst[v_curr],
-                                   vert_cos_org[v_prev], vert_cos_org[v_curr], vert_cos_org[v_next],
-                                   vert_cos_src[v_prev], vert_cos_src[v_curr], vert_cos_src[v_next]
-                                   );
-
-                       add_v3_v3(vert_cos_new[v_curr], tvec);
-                       vert_accum[v_curr] += 1;
-               }
-       }
-
-       for (i = 0; i < totvert; i++) {
-               if (vert_accum[i]) {
-                       mul_v3_fl(vert_cos_new[i], 1.0f / (float)vert_accum[i]);
-               }
-               else {
-                       copy_v3_v3(vert_cos_new[i], vert_cos_org[i]);
-               }
-       }
-
-       MEM_freeN(vert_accum);
-}
-
-/* Find the index of the loop in 'poly' which references vertex,
- * returns -1 if not found */
-int poly_find_loop_from_vert(const MPoly *poly, const MLoop *loopstart,
-                             unsigned vert)
-{
-       int j;
-       for (j = 0; j < poly->totloop; j++, loopstart++) {
-               if (loopstart->v == vert)
-                       return j;
-       }
-       
-       return -1;
-}
-
-/* Fill 'adj_r' with the loop indices in 'poly' adjacent to the
- * vertex. Returns the index of the loop matching vertex, or -1 if the
- * vertex is not in 'poly' */
-int poly_get_adj_loops_from_vert(unsigned adj_r[3], const MPoly *poly,
-                                 const MLoop *mloop, unsigned vert)
-{
-       int corner = poly_find_loop_from_vert(poly,
-                                             &mloop[poly->loopstart],
-                                             vert);
-               
-       if (corner != -1) {
-               const MLoop *ml = &mloop[poly->loopstart + corner];
-
-               /* vertex was found */
-               adj_r[0] = ME_POLY_LOOP_PREV(mloop, poly, corner)->v;
-               adj_r[1] = ml->v;
-               adj_r[2] = ME_POLY_LOOP_NEXT(mloop, poly, corner)->v;
-       }
-
-       return corner;
-}
-
-/* Return the index of the edge vert that is not equal to 'v'. If
- * neither edge vertex is equal to 'v', returns -1. */
-int BKE_mesh_edge_other_vert(const MEdge *e, int v)
-{
-       if (e->v1 == v)
-               return e->v2;
-       else if (e->v2 == v)
-               return e->v1;
-       else
-               return -1;
-}
-
-/* update the hide flag for edges and faces from the corresponding
- * flag in verts */
-void BKE_mesh_flush_hidden_from_verts_ex(const MVert *mvert,
-                                         const MLoop *mloop,
-                                         MEdge *medge, const int totedge,
-                                         MPoly *mpoly, const int totpoly)
-{
-       int i, j;
-       
-       for (i = 0; i < totedge; i++) {
-               MEdge *e = &medge[i];
-               if (mvert[e->v1].flag & ME_HIDE ||
-                   mvert[e->v2].flag & ME_HIDE)
-               {
-                       e->flag |= ME_HIDE;
-               }
-               else {
-                       e->flag &= ~ME_HIDE;
-               }
-       }
-       for (i = 0; i < totpoly; i++) {
-               MPoly *p = &mpoly[i];
-               p->flag &= ~ME_HIDE;
-               for (j = 0; j < p->totloop; j++) {
-                       if (mvert[mloop[p->loopstart + j].v].flag & ME_HIDE)
-                               p->flag |= ME_HIDE;
-               }
-       }
-}
-void BKE_mesh_flush_hidden_from_verts(Mesh *me)
-{
-       BKE_mesh_flush_hidden_from_verts_ex(me->mvert, me->mloop,
-                                           me->medge, me->totedge,
-                                           me->mpoly, me->totpoly);
-}
-
-void BKE_mesh_flush_hidden_from_polys_ex(MVert *mvert,
-                                         const MLoop *mloop,
-                                         MEdge *medge, const int UNUSED(totedge),
-                                         const MPoly *mpoly, const int totpoly)
-{
-       const MPoly *mp;
-       int i;
-
-       i = totpoly;
-       for (mp = mpoly; i--; mp++) {
-               if (mp->flag & ME_HIDE) {
-                       const MLoop *ml;
-                       int j;
-                       j = mp->totloop;
-                       for (ml = &mloop[mp->loopstart]; j--; ml++) {
-                               mvert[ml->v].flag |= ME_HIDE;
-                               medge[ml->e].flag |= ME_HIDE;
-                       }
-               }
-       }
-
-       i = totpoly;
-       for (mp = mpoly; i--; mp++) {
-               if ((mp->flag & ME_HIDE) == 0) {
-                       const MLoop *ml;
-                       int j;
-                       j = mp->totloop;
-                       for (ml = &mloop[mp->loopstart]; j--; ml++) {
-                               mvert[ml->v].flag &= ~ME_HIDE;
-                               medge[ml->e].flag &= ~ME_HIDE;
-                       }
-               }
-       }
-}
-void BKE_mesh_flush_hidden_from_polys(Mesh *me)
-{
-       BKE_mesh_flush_hidden_from_polys_ex(me->mvert, me->mloop,
-                                           me->medge, me->totedge,
-                                           me->mpoly, me->totpoly);
-}
-
-/**
- * simple poly -> vert/edge selection.
- */
-void BKE_mesh_flush_select_from_polys_ex(MVert *mvert,       const int totvert,
-                                         const MLoop *mloop,
-                                         MEdge *medge,       const int totedge,
-                                         const MPoly *mpoly, const int totpoly)
-{
-       MVert *mv;
-       MEdge *med;
-       const MPoly *mp;
-       int i;
-
-       i = totvert;
-       for (mv = mvert; i--; mv++) {
-               mv->flag &= ~SELECT;
-       }
-
-       i = totedge;
-       for (med = medge; i--; med++) {
-               med->flag &= ~SELECT;
-       }
-
-       i = totpoly;
-       for (mp = mpoly; i--; mp++) {
-               /* assume if its selected its not hidden and none of its verts/edges are hidden
-                * (a common assumption)*/
-               if (mp->flag & ME_FACE_SEL) {
-                       const MLoop *ml;
-                       int j;
-                       j = mp->totloop;
-                       for (ml = &mloop[mp->loopstart]; j--; ml++) {
-                               mvert[ml->v].flag |= SELECT;
-                               medge[ml->e].flag |= SELECT;
-                       }
-               }
-       }
-}
-void BKE_mesh_flush_select_from_polys(Mesh *me)
-{
-       BKE_mesh_flush_select_from_polys_ex(me->mvert, me->totvert,
-                                        me->mloop,
-                                        me->medge, me->totedge,
-                                        me->mpoly, me->totpoly);
-}
-
-void BKE_mesh_flush_select_from_verts_ex(const MVert *mvert, const int UNUSED(totvert),
-                                         const MLoop *mloop,
-                                         MEdge *medge,       const int totedge,
-                                         MPoly *mpoly,       const int totpoly)
-{
-       MEdge *med;
-       MPoly *mp;
-       int i;
-
-       /* edges */
-       i = totedge;
-       for (med = medge; i--; med++) {
-               if ((med->flag & ME_HIDE) == 0) {
-                       if ((mvert[med->v1].flag & SELECT) && (mvert[med->v2].flag & SELECT)) {
-                               med->flag |= SELECT;
-                       }
-                       else {
-                               med->flag &= ~SELECT;
-                       }
-               }
-       }
-
-       /* polys */
-       i = totpoly;
-       for (mp = mpoly; i--; mp++) {
-               if ((mp->flag & ME_HIDE) == 0) {
-                       int ok = TRUE;
-                       const MLoop *ml;
-                       int j;
-                       j = mp->totloop;
-                       for (ml = &mloop[mp->loopstart]; j--; ml++) {
-                               if ((mvert[ml->v].flag & SELECT) == 0) {
-                                       ok = FALSE;
-                                       break;
-                               }
-                       }
-
-                       if (ok) {
-                               mp->flag |= ME_FACE_SEL;
-                       }
-                       else {
-                               mp->flag &= ~ME_FACE_SEL;
-                       }
-               }
-       }
-}
-void BKE_mesh_flush_select_from_verts(Mesh *me)
-{
-       BKE_mesh_flush_select_from_verts_ex(me->mvert, me->totvert,
-                                           me->mloop,
-                                           me->medge, me->totedge,
-                                           me->mpoly, me->totpoly);
-}
-
-
-/* basic vertex data functions */
-bool BKE_mesh_minmax(Mesh *me, float r_min[3], float r_max[3])
-{
-       int i = me->totvert;
-       MVert *mvert;
-       for (mvert = me->mvert; i--; mvert++) {
-               minmax_v3v3_v3(r_min, r_max, mvert->co);
-       }
-       
-       return (me->totvert != 0);
-}
-
-bool BKE_mesh_center_median(Mesh *me, float cent[3])
-{
-       int i = me->totvert;
-       MVert *mvert;
-       zero_v3(cent);
-       for (mvert = me->mvert; i--; mvert++) {
-               add_v3_v3(cent, mvert->co);
-       }
-       /* otherwise we get NAN for 0 verts */
-       if (me->totvert) {
-               mul_v3_fl(cent, 1.0f / (float)me->totvert);
-       }
-
-       return (me->totvert != 0);
-}
-
-bool BKE_mesh_center_bounds(Mesh *me, float cent[3])
-{
-       float min[3], max[3];
-       INIT_MINMAX(min, max);
-       if (BKE_mesh_minmax(me, min, max)) {
-               mid_v3_v3v3(cent, min, max);
-               return true;
-       }
-
-       return false;
-}
-
-bool BKE_mesh_center_centroid(Mesh *me, float cent[3])
-{
-       int i = me->totpoly;
-       MPoly *mpoly;
-       float poly_area;
-       float total_area = 0.0f;
-       float poly_cent[3];
-       
-       zero_v3(cent);
-       
-       /* calculate a weighted average of polygon centroids */
-       for (mpoly = me->mpoly; i--; mpoly++) {
-               poly_area = mesh_calc_poly_planar_area_centroid(mpoly, me->mloop + mpoly->loopstart, me->mvert, poly_cent);
-
-               madd_v3_v3fl(cent, poly_cent, poly_area);
-               total_area += poly_area;
-       }
-       /* otherwise we get NAN for 0 polys */
-       if (me->totpoly) {
-               mul_v3_fl(cent, 1.0f / total_area);
-       }
-
-       /* zero area faces cause this, fallback to median */
-       if (UNLIKELY(!is_finite_v3(cent))) {
-               return BKE_mesh_center_median(me, cent);
-       }
-
-       return (me->totpoly != 0);
-}
-
-void BKE_mesh_translate(Mesh *me, const float offset[3], const bool do_keys)
-{
-       int i = me->totvert;
-       MVert *mvert;
-       for (mvert = me->mvert; i--; mvert++) {
-               add_v3_v3(mvert->co, offset);
-       }
-       
-       if (do_keys && me->key) {
-               KeyBlock *kb;
-               for (kb = me->key->block.first; kb; kb = kb->next) {
-                       float *fp = kb->data;
-                       for (i = kb->totelem; i--; fp += 3) {
-                               add_v3_v3(fp, offset);
-                       }
-               }
-       }
-}
-
-void BKE_mesh_ensure_navmesh(Mesh *me)
-{
-       if (!CustomData_has_layer(&me->pdata, CD_RECAST)) {
-               int i;
-               int numFaces = me->totpoly;
-               int *recastData;
-               recastData = (int *)MEM_mallocN(numFaces * sizeof(int), __func__);
-               for (i = 0; i < numFaces; i++) {
-                       recastData[i] = i + 1;
-               }
-               CustomData_add_layer_named(&me->pdata, CD_RECAST, CD_ASSIGN, recastData, numFaces, "recastData");
-       }
-}
-
-void BKE_mesh_tessface_calc(Mesh *mesh)
-{
-       mesh->totface = BKE_mesh_recalc_tessellation(&mesh->fdata, &mesh->ldata, &mesh->pdata,
-                                                    mesh->mvert,
-                                                    mesh->totface, mesh->totloop, mesh->totpoly,
-                                                    /* calc normals right after, don't copy from polys here */
-                                                    false);
-
-       BKE_mesh_update_customdata_pointers(mesh, true);
-}
-
-void BKE_mesh_tessface_ensure(Mesh *mesh)
-{
-       if (mesh->totpoly && mesh->totface == 0) {
-               BKE_mesh_tessface_calc(mesh);
-       }
-}
-
-void BKE_mesh_tessface_clear(Mesh *mesh)
+void BKE_mesh_tessface_clear(Mesh *mesh)
 {
        mesh_tessface_clear_intern(mesh, TRUE);
 }
 
-#if 0 /* slow version of the function below */
-void BKE_mesh_calc_poly_angles(MPoly *mpoly, MLoop *loopstart,
-                               MVert *mvarray, float angles[])
-{
-       MLoop *ml;
-       MLoop *mloop = &loopstart[-mpoly->loopstart];
-
-       int j;
-       for (j = 0, ml = loopstart; j < mpoly->totloop; j++, ml++) {
-               MLoop *ml_prev = ME_POLY_LOOP_PREV(mloop, mpoly, j);
-               MLoop *ml_next = ME_POLY_LOOP_NEXT(mloop, mpoly, j);
-
-               float e1[3], e2[3];
-
-               sub_v3_v3v3(e1, mvarray[ml_next->v].co, mvarray[ml->v].co);
-               sub_v3_v3v3(e2, mvarray[ml_prev->v].co, mvarray[ml->v].co);
-
-               angles[j] = (float)M_PI - angle_v3v3(e1, e2);
-       }
-}
-
-#else /* equivalent the function above but avoid multiple subtractions + normalize */
-
-void BKE_mesh_calc_poly_angles(MPoly *mpoly, MLoop *loopstart,
-                               MVert *mvarray, float angles[])
-{
-       float nor_prev[3];
-       float nor_next[3];
-
-       int i_this = mpoly->totloop - 1;
-       int i_next = 0;
-
-       sub_v3_v3v3(nor_prev, mvarray[loopstart[i_this - 1].v].co, mvarray[loopstart[i_this].v].co);
-       normalize_v3(nor_prev);
-
-       while (i_next < mpoly->totloop) {
-               sub_v3_v3v3(nor_next, mvarray[loopstart[i_this].v].co, mvarray[loopstart[i_next].v].co);
-               normalize_v3(nor_next);
-               angles[i_this] = angle_normalized_v3v3(nor_prev, nor_next);
-
-               /* step */
-               copy_v3_v3(nor_prev, nor_next);
-               i_this = i_next;
-               i_next++;
-       }
-}
-#endif
-
-void BKE_mesh_poly_edgehash_insert(EdgeHash *ehash, const MPoly *mp, const MLoop *mloop)
-{
-       const MLoop *ml, *ml_next;
-       int i = mp->totloop;
-
-       ml_next = mloop;       /* first loop */
-       ml = &ml_next[i - 1];  /* last loop */
-
-       while (i-- != 0) {
-               BLI_edgehash_reinsert(ehash, ml->v, ml_next->v, NULL);
-
-               ml = ml_next;
-               ml_next++;
-       }
-}
-
-void BKE_mesh_poly_edgebitmap_insert(unsigned int *edge_bitmap, const MPoly *mp, const MLoop *mloop)
-{
-       const MLoop *ml;
-       int i = mp->totloop;
-
-       ml = mloop;
-
-       while (i-- != 0) {
-               BLI_BITMAP_SET(edge_bitmap, ml->e);
-               ml++;
-       }
-}
-
 void BKE_mesh_do_versions_cd_flag_init(Mesh *mesh)
 {
        if (UNLIKELY(mesh->cd_flag)) {
diff --git a/source/blender/blenkernel/intern/mesh_evaluate.c b/source/blender/blenkernel/intern/mesh_evaluate.c
new file mode 100644 (file)
index 0000000..d35d91c
--- /dev/null
@@ -0,0 +1,2017 @@
+/*
+ * ***** 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.
+ *
+ * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
+ * All rights reserved.
+ *
+ * Contributor(s): Blender Foundation
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/blenkernel/intern/mesh_evaluate.c
+ *  \ingroup bke
+ *
+ * Functions to evaluate mesh data.
+ */
+
+#include "MEM_guardedalloc.h"
+
+#include "DNA_object_types.h"
+#include "DNA_mesh_types.h"
+#include "DNA_meshdata_types.h"
+
+#include "BLI_utildefines.h"
+#include "BLI_memarena.h"
+#include "BLI_math.h"
+#include "BLI_edgehash.h"
+#include "BLI_bitmap.h"
+#include "BLI_scanfill.h"
+#include "BLI_alloca.h"
+#include "BLI_array.h"
+
+#include "BKE_customdata.h"
+#include "BKE_mesh.h"
+#include "BKE_multires.h"
+
+
+/* -------------------------------------------------------------------- */
+
+/** \name Mesh Normal Calculation
+ * \{ */
+
+/**
+ * Call when there are no polygons.
+ */
+static void mesh_calc_normals_vert_fallback(MVert *mverts, int numVerts)
+{
+       int i;
+       for (i = 0; i < numVerts; i++) {
+               MVert *mv = &mverts[i];
+               float no[3];
+
+               normalize_v3_v3(no, mv->co);
+               normal_float_to_short_v3(mv->no, no);
+       }
+}
+
+/* Calculate vertex and face normals, face normals are returned in *faceNors_r if non-NULL
+ * and vertex normals are stored in actual mverts.
+ */
+void BKE_mesh_calc_normals_mapping(MVert *mverts, int numVerts,
+                                   MLoop *mloop, MPoly *mpolys, int numLoops, int numPolys, float (*polyNors_r)[3],
+                                   MFace *mfaces, int numFaces, int *origIndexFace, float (*faceNors_r)[3])
+{
+       BKE_mesh_calc_normals_mapping_ex(mverts, numVerts, mloop, mpolys,
+                                        numLoops, numPolys, polyNors_r, mfaces, numFaces,
+                                        origIndexFace, faceNors_r, FALSE);
+}
+/* extended version of 'BKE_mesh_calc_normals_poly' with option not to calc vertex normals */
+void BKE_mesh_calc_normals_mapping_ex(
+        MVert *mverts, int numVerts,
+        MLoop *mloop, MPoly *mpolys,
+        int numLoops, int numPolys, float (*polyNors_r)[3],
+        MFace *mfaces, int numFaces, int *origIndexFace, float (*faceNors_r)[3],
+        const bool only_face_normals)
+{
+       float (*pnors)[3] = polyNors_r, (*fnors)[3] = faceNors_r;
+       int i;
+       MFace *mf;
+       MPoly *mp;
+
+       if (numPolys == 0) {
+               if (only_face_normals == FALSE) {
+                       mesh_calc_normals_vert_fallback(mverts, numVerts);
+               }
+               return;
+       }
+
+       /* if we are not calculating verts and no verts were passes then we have nothing to do */
+       if ((only_face_normals == TRUE) && (polyNors_r == NULL) && (faceNors_r == NULL)) {
+               printf("%s: called with nothing to do\n", __func__);
+               return;
+       }
+
+       if (!pnors) pnors = MEM_callocN(sizeof(float) * 3 * numPolys, "poly_nors mesh.c");
+       /* if (!fnors) fnors = MEM_callocN(sizeof(float) * 3 * numFaces, "face nors mesh.c"); */ /* NO NEED TO ALLOC YET */
+
+
+       if (only_face_normals == FALSE) {
+               /* vertex normals are optional, they require some extra calculations,
+                * so make them optional */
+               BKE_mesh_calc_normals_poly(mverts, numVerts, mloop, mpolys, numLoops, numPolys, pnors, false);
+       }
+       else {
+               /* only calc poly normals */
+               mp = mpolys;
+               for (i = 0; i < numPolys; i++, mp++) {
+                       BKE_mesh_calc_poly_normal(mp, mloop + mp->loopstart, mverts, pnors[i]);
+               }
+       }
+
+       if (origIndexFace &&
+           /* fnors == faceNors_r */ /* NO NEED TO ALLOC YET */
+           fnors != NULL &&
+           numFaces)
+       {
+               mf = mfaces;
+               for (i = 0; i < numFaces; i++, mf++, origIndexFace++) {
+                       if (*origIndexFace < numPolys) {
+                               copy_v3_v3(fnors[i], pnors[*origIndexFace]);
+                       }
+                       else {
+                               /* eek, we're not corresponding to polys */
+                               printf("error in %s: tessellation face indices are incorrect.  normals may look bad.\n", __func__);
+                       }
+               }
+       }
+
+       if (pnors != polyNors_r) MEM_freeN(pnors);
+       /* if (fnors != faceNors_r) MEM_freeN(fnors); */ /* NO NEED TO ALLOC YET */
+
+       fnors = pnors = NULL;
+       
+}
+
+static void mesh_calc_normals_poly_accum(MPoly *mp, MLoop *ml,
+                                         MVert *mvert, float polyno[3], float (*tnorms)[3])
+{
+       const int nverts = mp->totloop;
+       float (*edgevecbuf)[3] = BLI_array_alloca(edgevecbuf, nverts);
+       int i;
+
+       /* Polygon Normal and edge-vector */
+       /* inline version of #BKE_mesh_calc_poly_normal, also does edge-vectors */
+       {
+               int i_prev = nverts - 1;
+               float const *v_prev = mvert[ml[i_prev].v].co;
+               float const *v_curr;
+
+               zero_v3(polyno);
+               /* Newell's Method */
+               for (i = 0; i < nverts; i++) {
+                       v_curr = mvert[ml[i].v].co;
+                       add_newell_cross_v3_v3v3(polyno, v_prev, v_curr);
+
+                       /* Unrelated to normalize, calcualte edge-vector */
+                       sub_v3_v3v3(edgevecbuf[i_prev], v_prev, v_curr);
+                       normalize_v3(edgevecbuf[i_prev]);
+                       i_prev = i;
+
+                       v_prev = v_curr;
+               }
+               if (UNLIKELY(normalize_v3(polyno) == 0.0f)) {
+                       polyno[2] = 1.0f; /* other axis set to 0.0 */
+               }
+       }
+
+       /* accumulate angle weighted face normal */
+       /* inline version of #accumulate_vertex_normals_poly */
+       {
+               const float *prev_edge = edgevecbuf[nverts - 1];
+
+               for (i = 0; i < nverts; i++) {
+                       const float *cur_edge = edgevecbuf[i];
+
+                       /* calculate angle between the two poly edges incident on
+                        * this vertex */
+                       const float fac = saacos(-dot_v3v3(cur_edge, prev_edge));
+
+                       /* accumulate */
+                       madd_v3_v3fl(tnorms[ml[i].v], polyno, fac);
+                       prev_edge = cur_edge;
+               }
+       }
+
+}
+
+void BKE_mesh_calc_normals_poly(MVert *mverts, int numVerts, MLoop *mloop, MPoly *mpolys,
+                                int UNUSED(numLoops), int numPolys, float (*r_polynors)[3],
+                                const bool only_face_normals)
+{
+       float (*pnors)[3] = r_polynors;
+       float (*tnorms)[3];
+       int i;
+       MPoly *mp;
+
+       if (only_face_normals) {
+               BLI_assert(pnors != NULL);
+
+#pragma omp parallel for if (numPolys > BM_OMP_LIMIT)
+               for (i = 0; i < numPolys; i++) {
+                       BKE_mesh_calc_poly_normal(&mpolys[i], mloop + mpolys[i].loopstart, mverts, pnors[i]);
+               }
+               return;
+       }
+
+       /* first go through and calculate normals for all the polys */
+       tnorms = MEM_callocN(sizeof(*tnorms) * numVerts, __func__);
+
+       if (pnors) {
+               mp = mpolys;
+               for (i = 0; i < numPolys; i++, mp++) {
+                       mesh_calc_normals_poly_accum(mp, mloop + mp->loopstart, mverts, pnors[i], tnorms);
+               }
+       }
+       else {
+               float tpnor[3];  /* temp poly normal */
+               mp = mpolys;
+               for (i = 0; i < numPolys; i++, mp++) {
+                       mesh_calc_normals_poly_accum(mp, mloop + mp->loopstart, mverts, tpnor, tnorms);
+               }
+       }
+
+       /* following Mesh convention; we use vertex coordinate itself for normal in this case */
+       for (i = 0; i < numVerts; i++) {
+               MVert *mv = &mverts[i];
+               float *no = tnorms[i];
+
+               if (UNLIKELY(normalize_v3(no) == 0.0f)) {
+                       normalize_v3_v3(no, mv->co);
+               }
+
+               normal_float_to_short_v3(mv->no, no);
+       }
+
+       MEM_freeN(tnorms);
+}
+
+void BKE_mesh_calc_normals(Mesh *mesh)
+{
+       BKE_mesh_calc_normals_poly(mesh->mvert, mesh->totvert,
+                                  mesh->mloop, mesh->mpoly, mesh->totloop, mesh->totpoly,
+                                  NULL, false);
+}
+
+void BKE_mesh_calc_normals_tessface(MVert *mverts, int numVerts, MFace *mfaces, int numFaces, float (*faceNors_r)[3])
+{
+       float (*tnorms)[3] = MEM_callocN(numVerts * sizeof(*tnorms), "tnorms");
+       float (*fnors)[3] = (faceNors_r) ? faceNors_r : MEM_callocN(sizeof(*fnors) * numFaces, "meshnormals");
+       int i;
+
+       for (i = 0; i < numFaces; i++) {
+               MFace *mf = &mfaces[i];
+               float *f_no = fnors[i];
+               float *n4 = (mf->v4) ? tnorms[mf->v4] : NULL;
+               float *c4 = (mf->v4) ? mverts[mf->v4].co : NULL;
+
+               if (mf->v4)
+                       normal_quad_v3(f_no, mverts[mf->v1].co, mverts[mf->v2].co, mverts[mf->v3].co, mverts[mf->v4].co);
+               else
+                       normal_tri_v3(f_no, mverts[mf->v1].co, mverts[mf->v2].co, mverts[mf->v3].co);
+
+               accumulate_vertex_normals(tnorms[mf->v1], tnorms[mf->v2], tnorms[mf->v3], n4,
+                                         f_no, mverts[mf->v1].co, mverts[mf->v2].co, mverts[mf->v3].co, c4);
+       }
+
+       /* following Mesh convention; we use vertex coordinate itself for normal in this case */
+       for (i = 0; i < numVerts; i++) {
+               MVert *mv = &mverts[i];
+               float *no = tnorms[i];
+               
+               if (UNLIKELY(normalize_v3(no) == 0.0f)) {
+                       normalize_v3_v3(no, mv->co);
+               }
+
+               normal_float_to_short_v3(mv->no, no);
+       }
+       
+       MEM_freeN(tnorms);
+
+       if (fnors != faceNors_r)
+               MEM_freeN(fnors);
+}
+/** \} */
+
+
+/* -------------------------------------------------------------------- */
+
+/** \name Polygon Calculations
+ * \{ */
+
+/*
+ * COMPUTE POLY NORMAL
+ *
+ * Computes the normal of a planar
+ * polygon See Graphics Gems for
+ * computing newell normal.
+ *
+ */
+static void mesh_calc_ngon_normal(MPoly *mpoly, MLoop *loopstart,
+                                  MVert *mvert, float normal[3])
+{
+       const int nverts = mpoly->totloop;
+       float const *v_prev = mvert[loopstart[nverts - 1].v].co;
+       float const *v_curr;
+       int i;
+
+       zero_v3(normal);
+
+       /* Newell's Method */
+       for (i = 0; i < nverts; i++) {
+               v_curr = mvert[loopstart[i].v].co;
+               add_newell_cross_v3_v3v3(normal, v_prev, v_curr);
+               v_prev = v_curr;
+       }
+
+       if (UNLIKELY(normalize_v3(normal) == 0.0f)) {
+               normal[2] = 1.0f; /* other axis set to 0.0 */
+       }
+}
+
+void BKE_mesh_calc_poly_normal(MPoly *mpoly, MLoop *loopstart,
+                               MVert *mvarray, float no[3])
+{
+       if (mpoly->totloop > 4) {
+               mesh_calc_ngon_normal(mpoly, loopstart, mvarray, no);
+       }
+       else if (mpoly->totloop == 3) {
+               normal_tri_v3(no,
+                             mvarray[loopstart[0].v].co,
+                             mvarray[loopstart[1].v].co,
+                             mvarray[loopstart[2].v].co
+                             );
+       }
+       else if (mpoly->totloop == 4) {
+               normal_quad_v3(no,
+                              mvarray[loopstart[0].v].co,
+                              mvarray[loopstart[1].v].co,
+                              mvarray[loopstart[2].v].co,
+                              mvarray[loopstart[3].v].co
+                              );
+       }
+       else { /* horrible, two sided face! */
+               no[0] = 0.0;
+               no[1] = 0.0;
+               no[2] = 1.0;
+       }
+}
+/* duplicate of function above _but_ takes coords rather then mverts */
+static void mesh_calc_ngon_normal_coords(MPoly *mpoly, MLoop *loopstart,
+                                         const float (*vertex_coords)[3], float normal[3])
+{
+       const int nverts = mpoly->totloop;
+       float const *v_prev = vertex_coords[loopstart[nverts - 1].v];
+       float const *v_curr;
+       int i;
+
+       zero_v3(normal);
+
+       /* Newell's Method */
+       for (i = 0; i < nverts; i++) {
+               v_curr = vertex_coords[loopstart[i].v];
+               add_newell_cross_v3_v3v3(normal, v_prev, v_curr);
+               v_prev = v_curr;
+       }
+
+       if (UNLIKELY(normalize_v3(normal) == 0.0f)) {
+               normal[2] = 1.0f; /* other axis set to 0.0 */
+       }
+}
+
+void BKE_mesh_calc_poly_normal_coords(MPoly *mpoly, MLoop *loopstart,
+                                      const float (*vertex_coords)[3], float no[3])
+{
+       if (mpoly->totloop > 4) {
+               mesh_calc_ngon_normal_coords(mpoly, loopstart, vertex_coords, no);
+       }
+       else if (mpoly->totloop == 3) {
+               normal_tri_v3(no,
+                             vertex_coords[loopstart[0].v],
+                             vertex_coords[loopstart[1].v],
+                             vertex_coords[loopstart[2].v]
+                             );
+       }
+       else if (mpoly->totloop == 4) {
+               normal_quad_v3(no,
+                              vertex_coords[loopstart[0].v],
+                              vertex_coords[loopstart[1].v],
+                              vertex_coords[loopstart[2].v],
+                              vertex_coords[loopstart[3].v]
+                              );
+       }
+       else { /* horrible, two sided face! */
+               no[0] = 0.0;
+               no[1] = 0.0;
+               no[2] = 1.0;
+       }
+}
+
+static void mesh_calc_ngon_center(MPoly *mpoly, MLoop *loopstart,
+                                  MVert *mvert, float cent[3])
+{
+       const float w = 1.0f / (float)mpoly->totloop;
+       int i;
+
+       zero_v3(cent);
+
+       for (i = 0; i < mpoly->totloop; i++) {
+               madd_v3_v3fl(cent, mvert[(loopstart++)->v].co, w);
+       }
+}
+
+void BKE_mesh_calc_poly_center(MPoly *mpoly, MLoop *loopstart,
+                               MVert *mvarray, float cent[3])
+{
+       if (mpoly->totloop == 3) {
+               cent_tri_v3(cent,
+                           mvarray[loopstart[0].v].co,
+                           mvarray[loopstart[1].v].co,
+                           mvarray[loopstart[2].v].co
+                           );
+       }
+       else if (mpoly->totloop == 4) {
+               cent_quad_v3(cent,
+                            mvarray[loopstart[0].v].co,
+                            mvarray[loopstart[1].v].co,
+                            mvarray[loopstart[2].v].co,
+                            mvarray[loopstart[3].v].co
+                            );
+       }
+       else {
+               mesh_calc_ngon_center(mpoly, loopstart, mvarray, cent);
+       }
+}
+
+/* note, passing polynormal is only a speedup so we can skip calculating it */
+float BKE_mesh_calc_poly_area(MPoly *mpoly, MLoop *loopstart,
+                              MVert *mvarray, const float polynormal[3])
+{
+       if (mpoly->totloop == 3) {
+               return area_tri_v3(mvarray[loopstart[0].v].co,
+                                  mvarray[loopstart[1].v].co,
+                                  mvarray[loopstart[2].v].co
+                                  );
+       }
+       else if (mpoly->totloop == 4) {
+               return area_quad_v3(mvarray[loopstart[0].v].co,
+                                   mvarray[loopstart[1].v].co,
+                                   mvarray[loopstart[2].v].co,
+                                   mvarray[loopstart[3].v].co
+                                   );
+       }
+       else {
+               int i;
+               MLoop *l_iter = loopstart;
+               float area, polynorm_local[3];
+               float (*vertexcos)[3] = BLI_array_alloca(vertexcos, mpoly->totloop);
+               const float *no = polynormal ? polynormal : polynorm_local;
+
+               /* pack vertex cos into an array for area_poly_v3 */
+               for (i = 0; i < mpoly->totloop; i++, l_iter++) {
+                       copy_v3_v3(vertexcos[i], mvarray[l_iter->v].co);
+               }
+
+               /* need normal for area_poly_v3 as well */
+               if (polynormal == NULL) {
+                       BKE_mesh_calc_poly_normal(mpoly, loopstart, mvarray, polynorm_local);
+               }
+
+               /* finally calculate the area */
+               area = area_poly_v3(mpoly->totloop, vertexcos, no);
+
+               return area;
+       }
+}
+
+/* note, results won't be correct if polygon is non-planar */
+static float mesh_calc_poly_planar_area_centroid(MPoly *mpoly, MLoop *loopstart, MVert *mvarray, float cent[3])
+{
+       int i;
+       float tri_area;
+       float total_area = 0.0f;
+       float v1[3], v2[3], v3[3], normal[3], tri_cent[3];
+
+       BKE_mesh_calc_poly_normal(mpoly, loopstart, mvarray, normal);
+       copy_v3_v3(v1, mvarray[loopstart[0].v].co);
+       copy_v3_v3(v2, mvarray[loopstart[1].v].co);
+       zero_v3(cent);
+
+       for (i = 2; i < mpoly->totloop; i++) {
+               copy_v3_v3(v3, mvarray[loopstart[i].v].co);
+
+               tri_area = area_tri_signed_v3(v1, v2, v3, normal);
+               total_area += tri_area;
+
+               cent_tri_v3(tri_cent, v1, v2, v3);
+               madd_v3_v3fl(cent, tri_cent, tri_area);
+
+               copy_v3_v3(v2, v3);
+       }
+
+       mul_v3_fl(cent, 1.0f / total_area);
+
+       return total_area;
+}
+
+#if 0 /* slow version of the function below */
+void BKE_mesh_calc_poly_angles(MPoly *mpoly, MLoop *loopstart,
+                               MVert *mvarray, float angles[])
+{
+       MLoop *ml;
+       MLoop *mloop = &loopstart[-mpoly->loopstart];
+
+       int j;
+       for (j = 0, ml = loopstart; j < mpoly->totloop; j++, ml++) {
+               MLoop *ml_prev = ME_POLY_LOOP_PREV(mloop, mpoly, j);
+               MLoop *ml_next = ME_POLY_LOOP_NEXT(mloop, mpoly, j);
+
+               float e1[3], e2[3];
+
+               sub_v3_v3v3(e1, mvarray[ml_next->v].co, mvarray[ml->v].co);
+               sub_v3_v3v3(e2, mvarray[ml_prev->v].co, mvarray[ml->v].co);
+
+               angles[j] = (float)M_PI - angle_v3v3(e1, e2);
+       }
+}
+
+#else /* equivalent the function above but avoid multiple subtractions + normalize */
+
+void BKE_mesh_calc_poly_angles(MPoly *mpoly, MLoop *loopstart,
+                               MVert *mvarray, float angles[])
+{
+       float nor_prev[3];
+       float nor_next[3];
+
+       int i_this = mpoly->totloop - 1;
+       int i_next = 0;
+
+       sub_v3_v3v3(nor_prev, mvarray[loopstart[i_this - 1].v].co, mvarray[loopstart[i_this].v].co);
+       normalize_v3(nor_prev);
+
+       while (i_next < mpoly->totloop) {
+               sub_v3_v3v3(nor_next, mvarray[loopstart[i_this].v].co, mvarray[loopstart[i_next].v].co);
+               normalize_v3(nor_next);
+               angles[i_this] = angle_normalized_v3v3(nor_prev, nor_next);
+
+               /* step */
+               copy_v3_v3(nor_prev, nor_next);
+               i_this = i_next;
+               i_next++;
+       }
+}
+#endif
+
+void BKE_mesh_poly_edgehash_insert(EdgeHash *ehash, const MPoly *mp, const MLoop *mloop)
+{
+       const MLoop *ml, *ml_next;
+       int i = mp->totloop;
+
+       ml_next = mloop;       /* first loop */
+       ml = &ml_next[i - 1];  /* last loop */
+
+       while (i-- != 0) {
+               BLI_edgehash_reinsert(ehash, ml->v, ml_next->v, NULL);
+
+               ml = ml_next;
+               ml_next++;
+       }
+}
+
+void BKE_mesh_poly_edgebitmap_insert(unsigned int *edge_bitmap, const MPoly *mp, const MLoop *mloop)
+{
+       const MLoop *ml;
+       int i = mp->totloop;
+
+       ml = mloop;
+
+       while (i-- != 0) {
+               BLI_BITMAP_SET(edge_bitmap, ml->e);
+               ml++;
+       }
+}
+
+/** \} */
+
+
+/* -------------------------------------------------------------------- */
+
+/** \name Mesh Center Calculation
+ * \{ */
+
+bool BKE_mesh_center_median(Mesh *me, float cent[3])
+{
+       int i = me->totvert;
+       MVert *mvert;
+       zero_v3(cent);
+       for (mvert = me->mvert; i--; mvert++) {
+               add_v3_v3(cent, mvert->co);
+       }
+       /* otherwise we get NAN for 0 verts */
+       if (me->totvert) {
+               mul_v3_fl(cent, 1.0f / (float)me->totvert);
+       }
+
+       return (me->totvert != 0);
+}
+
+bool BKE_mesh_center_bounds(Mesh *me, float cent[3])
+{
+       float min[3], max[3];
+       INIT_MINMAX(min, max);
+       if (BKE_mesh_minmax(me, min, max)) {
+               mid_v3_v3v3(cent, min, max);
+               return true;
+       }
+
+       return false;
+}
+
+bool BKE_mesh_center_centroid(Mesh *me, float cent[3])
+{
+       int i = me->totpoly;
+       MPoly *mpoly;
+       float poly_area;
+       float total_area = 0.0f;
+       float poly_cent[3];
+
+       zero_v3(cent);
+
+       /* calculate a weighted average of polygon centroids */
+       for (mpoly = me->mpoly; i--; mpoly++) {
+               poly_area = mesh_calc_poly_planar_area_centroid(mpoly, me->mloop + mpoly->loopstart, me->mvert, poly_cent);
+
+               madd_v3_v3fl(cent, poly_cent, poly_area);
+               total_area += poly_area;
+       }
+       /* otherwise we get NAN for 0 polys */
+       if (me->totpoly) {
+               mul_v3_fl(cent, 1.0f / total_area);
+       }
+
+       /* zero area faces cause this, fallback to median */
+       if (UNLIKELY(!is_finite_v3(cent))) {
+               return BKE_mesh_center_median(me, cent);
+       }
+
+       return (me->totpoly != 0);
+}
+/** \} */
+
+
+/* -------------------------------------------------------------------- */
+
+/** \name Mesh Connectivity Mapping
+ * \{ */
+
+
+/* ngon version wip, based on EDBM_uv_vert_map_create */
+/* this replaces the non bmesh function (in trunk) which takes MTFace's, if we ever need it back we could
+ * but for now this replaces it because its unused. */
+
+UvVertMap *BKE_mesh_uv_vert_map_create(struct MPoly *mpoly, struct MLoop *mloop, struct MLoopUV *mloopuv,
+                                       unsigned int totpoly, unsigned int totvert, int selected, float *limit)
+{
+       UvVertMap *vmap;
+       UvMapVert *buf;
+       MPoly *mp;
+       unsigned int a;
+       int i, totuv, nverts;
+
+       totuv = 0;
+
+       /* generate UvMapVert array */
+       mp = mpoly;
+       for (a = 0; a < totpoly; a++, mp++)
+               if (!selected || (!(mp->flag & ME_HIDE) && (mp->flag & ME_FACE_SEL)))
+                       totuv += mp->totloop;
+
+       if (totuv == 0)
+               return NULL;
+
+       vmap = (UvVertMap *)MEM_callocN(sizeof(*vmap), "UvVertMap");
+       if (!vmap)
+               return NULL;
+
+       vmap->vert = (UvMapVert **)MEM_callocN(sizeof(*vmap->vert) * totvert, "UvMapVert*");
+       buf = vmap->buf = (UvMapVert *)MEM_callocN(sizeof(*vmap->buf) * totuv, "UvMapVert");
+
+       if (!vmap->vert || !vmap->buf) {
+               BKE_mesh_uv_vert_map_free(vmap);
+               return NULL;
+       }
+
+       mp = mpoly;
+       for (a = 0; a < totpoly; a++, mp++) {
+               if (!selected || (!(mp->flag & ME_HIDE) && (mp->flag & ME_FACE_SEL))) {
+                       nverts = mp->totloop;
+
+                       for (i = 0; i < nverts; i++) {
+                               buf->tfindex = i;
+                               buf->f = a;
+                               buf->separate = 0;
+                               buf->next = vmap->vert[mloop[mp->loopstart + i].v];
+                               vmap->vert[mloop[mp->loopstart + i].v] = buf;
+                               buf++;
+                       }
+               }
+       }
+
+       /* sort individual uvs for each vert */
+       for (a = 0; a < totvert; a++) {
+               UvMapVert *newvlist = NULL, *vlist = vmap->vert[a];
+               UvMapVert *iterv, *v, *lastv, *next;
+               float *uv, *uv2, uvdiff[2];
+
+               while (vlist) {
+                       v = vlist;
+                       vlist = vlist->next;
+                       v->next = newvlist;
+                       newvlist = v;
+
+                       uv = mloopuv[mpoly[v->f].loopstart + v->tfindex].uv;
+                       lastv = NULL;
+                       iterv = vlist;
+
+                       while (iterv) {
+                               next = iterv->next;
+
+                               uv2 = mloopuv[mpoly[iterv->f].loopstart + iterv->tfindex].uv;
+                               sub_v2_v2v2(uvdiff, uv2, uv);
+
+
+                               if (fabsf(uv[0] - uv2[0]) < limit[0] && fabsf(uv[1] - uv2[1]) < limit[1]) {
+                                       if (lastv) lastv->next = next;
+                                       else vlist = next;
+                                       iterv->next = newvlist;
+                                       newvlist = iterv;
+                               }
+                               else
+                                       lastv = iterv;
+
+                               iterv = next;
+                       }
+
+                       newvlist->separate = 1;
+               }
+
+               vmap->vert[a] = newvlist;
+       }
+
+       return vmap;
+}
+
+UvMapVert *BKE_mesh_uv_vert_map_get_vert(UvVertMap *vmap, unsigned int v)
+{
+       return vmap->vert[v];
+}
+
+void BKE_mesh_uv_vert_map_free(UvVertMap *vmap)
+{
+       if (vmap) {
+               if (vmap->vert) MEM_freeN(vmap->vert);
+               if (vmap->buf) MEM_freeN(vmap->buf);
+               MEM_freeN(vmap);
+       }
+}
+
+/* Generates a map where the key is the vertex and the value is a list
+ * of polys that use that vertex as a corner. The lists are allocated
+ * from one memory pool. */
+void BKE_mesh_vert_poly_map_create(MeshElemMap **r_map, int **r_mem,
+                                   const MPoly *mpoly, const MLoop *mloop,
+                                   int totvert, int totpoly, int totloop)
+{
+       MeshElemMap *map = MEM_callocN(sizeof(MeshElemMap) * totvert, "vert poly map");
+       int *indices, *index_iter;
+       int i, j;
+
+       indices = index_iter = MEM_mallocN(sizeof(int) * totloop, "vert poly map mem");
+
+       /* Count number of polys for each vertex */
+       for (i = 0; i < totpoly; i++) {
+               const MPoly *p = &mpoly[i];
+
+               for (j = 0; j < p->totloop; j++)
+                       map[mloop[p->loopstart + j].v].count++;
+       }
+
+       /* Assign indices mem */
+       for (i = 0; i < totvert; i++) {
+               map[i].indices = index_iter;
+               index_iter += map[i].count;
+
+               /* Reset 'count' for use as index in last loop */
+               map[i].count = 0;
+       }
+
+       /* Find the users */
+       for (i = 0; i < totpoly; i++) {
+               const MPoly *p = &mpoly[i];
+
+               for (j = 0; j < p->totloop; j++) {
+                       int v = mloop[p->loopstart + j].v;
+
+                       map[v].indices[map[v].count] = i;
+                       map[v].count++;
+               }
+       }
+
+       *r_map = map;
+       *r_mem = indices;
+}
+
+/* Generates a map where the key is the vertex and the value is a list
+ * of edges that use that vertex as an endpoint. The lists are allocated
+ * from one memory pool. */
+void BKE_mesh_vert_edge_map_create(MeshElemMap **r_map, int **r_mem,
+                                   const MEdge *medge, int totvert, int totedge)
+{
+       MeshElemMap *map = MEM_callocN(sizeof(MeshElemMap) * totvert, "vert-edge map");
+       int *indices = MEM_mallocN(sizeof(int) * totedge * 2, "vert-edge map mem");
+       int *i_pt = indices;
+
+       int i;
+
+       /* Count number of edges for each vertex */
+       for (i = 0; i < totedge; i++) {
+               map[medge[i].v1].count++;
+               map[medge[i].v2].count++;
+       }
+
+       /* Assign indices mem */
+       for (i = 0; i < totvert; i++) {
+               map[i].indices = i_pt;
+               i_pt += map[i].count;
+
+               /* Reset 'count' for use as index in last loop */
+               map[i].count = 0;
+       }
+
+       /* Find the users */
+       for (i = 0; i < totedge; i++) {
+               const int v[2] = {medge[i].v1, medge[i].v2};
+
+               map[v[0]].indices[map[v[0]].count] = i;
+               map[v[1]].indices[map[v[1]].count] = i;
+
+               map[v[0]].count++;
+               map[v[1]].count++;
+       }
+
+       *r_map = map;
+       *r_mem = indices;
+}
+
+void BKE_mesh_edge_poly_map_create(MeshElemMap **r_map, int **r_mem,
+                                   const MEdge *UNUSED(medge), const int totedge,
+                                   const MPoly *mpoly, const int totpoly,
+                                   const MLoop *mloop, const int totloop)
+{
+       MeshElemMap *map = MEM_callocN(sizeof(MeshElemMap) * totedge, "edge-poly map");
+       int *indices = MEM_mallocN(sizeof(int) * totloop, "edge-poly map mem");
+       int *index_step;
+       const MPoly *mp;
+       int i;
+
+       /* count face users */
+       for (i = 0, mp = mpoly; i < totpoly; mp++, i++) {
+               const MLoop *ml;
+               int j = mp->totloop;
+               for (ml = &mloop[mp->loopstart]; j--; ml++) {
+                       map[ml->e].count++;
+               }
+       }
+
+       /* create offsets */
+       index_step = indices;
+       for (i = 0; i < totedge; i++) {
+               map[i].indices = index_step;
+               index_step += map[i].count;
+
+               /* re-count, using this as an index below */
+               map[i].count = 0;
+
+       }
+
+       /* assign poly-edge users */
+       for (i = 0, mp = mpoly; i < totpoly; mp++, i++) {
+               const MLoop *ml;
+               int j = mp->totloop;
+               for (ml = &mloop[mp->loopstart]; j--; ml++) {
+                       MeshElemMap *map_ele = &map[ml->e];
+                       map_ele->indices[map_ele->count++] = i;
+               }
+       }
+
+       *r_map = map;
+       *r_mem = indices;
+}
+
+
+/** \} */
+
+
+/* -------------------------------------------------------------------- */
+
+/** \name NGon Tessellation (NGon/Tessface Conversion)
+ * \{ */
+
+/**
+ * Convert a triangle or quadrangle of loop/poly data to tessface data
+ */
+void BKE_mesh_loops_to_mface_corners(
+        CustomData *fdata, CustomData *ldata,
+        CustomData *pdata, int lindex[4], int findex,
+        const int polyindex,
+        const int mf_len, /* 3 or 4 */
+
+        /* cache values to avoid lookups every time */
+        const int numTex, /* CustomData_number_of_layers(pdata, CD_MTEXPOLY) */
+        const int numCol, /* CustomData_number_of_layers(ldata, CD_MLOOPCOL) */
+        const bool hasPCol, /* CustomData_has_layer(ldata, CD_PREVIEW_MLOOPCOL) */
+        const bool hasOrigSpace /* CustomData_has_layer(ldata, CD_ORIGSPACE_MLOOP) */
+)
+{
+       MTFace *texface;
+       MTexPoly *texpoly;
+       MCol *mcol;
+       MLoopCol *mloopcol;
+       MLoopUV *mloopuv;
+       int i, j;
+
+       for (i = 0; i < numTex; i++) {
+               texface = CustomData_get_n(fdata, CD_MTFACE, findex, i);
+               texpoly = CustomData_get_n(pdata, CD_MTEXPOLY, polyindex, i);
+
+               ME_MTEXFACE_CPY(texface, texpoly);
+
+               for (j = 0; j < mf_len; j++) {
+                       mloopuv = CustomData_get_n(ldata, CD_MLOOPUV, lindex[j], i);
+                       copy_v2_v2(texface->uv[j], mloopuv->uv);
+               }
+       }
+
+       for (i = 0; i < numCol; i++) {
+               mcol = CustomData_get_n(fdata, CD_MCOL, findex, i);
+
+               for (j = 0; j < mf_len; j++) {
+                       mloopcol = CustomData_get_n(ldata, CD_MLOOPCOL, lindex[j], i);
+                       MESH_MLOOPCOL_TO_MCOL(mloopcol, &mcol[j]);
+               }
+       }
+
+       if (hasPCol) {
+               mcol = CustomData_get(fdata,  findex, CD_PREVIEW_MCOL);
+
+               for (j = 0; j < mf_len; j++) {
+                       mloopcol = CustomData_get(ldata, lindex[j], CD_PREVIEW_MLOOPCOL);
+                       MESH_MLOOPCOL_TO_MCOL(mloopcol, &mcol[j]);
+               }
+       }
+
+       if (hasOrigSpace) {
+               OrigSpaceFace *of = CustomData_get(fdata, findex, CD_ORIGSPACE);
+               OrigSpaceLoop *lof;
+
+               for (j = 0; j < mf_len; j++) {
+                       lof = CustomData_get(ldata, lindex[j], CD_ORIGSPACE_MLOOP);
+                       copy_v2_v2(of->uv[j], lof->uv);
+               }
+       }
+}
+
+/**
+ * Recreate tessellation.
+ *
+ * use_poly_origindex sets whether or not the tessellation faces' origindex
+ * layer should point to original poly indices or real poly indices.
+ *
+ * use_face_origindex sets the tessellation faces' origindex layer
+ * to point to the tessellation faces themselves, not the polys.
+ *
+ * if both of the above are 0, it'll use the indices of the mpolys of the MPoly
+ * data in pdata, and ignore the origindex layer altogether.
+ *
+ * \return number of tessellation faces.
+ */
+int BKE_mesh_recalc_tessellation(CustomData *fdata,
+                                 CustomData *ldata, CustomData *pdata,
+                                 MVert *mvert, int totface, int totloop,
+                                 int totpoly,
+                                 /* when tessellating to recalculate normals after
+                                  * we can skip copying here */
+                                 const bool do_face_nor_cpy)
+{
+       /* use this to avoid locking pthread for _every_ polygon
+        * and calling the fill function */
+
+#define USE_TESSFACE_SPEEDUP
+#define USE_TESSFACE_QUADS // NEEDS FURTHER TESTING
+
+#define TESSFACE_SCANFILL (1 << 0)
+#define TESSFACE_IS_QUAD  (1 << 1)
+
+       const int looptris_tot = poly_to_tri_count(totpoly, totloop);
+
+       MPoly *mp, *mpoly;
+       MLoop *ml, *mloop;
+       MFace *mface, *mf;
+       ScanFillContext sf_ctx;
+       ScanFillVert *sf_vert, *sf_vert_last, *sf_vert_first;
+       ScanFillFace *sf_tri;
+       MemArena *sf_arena = NULL;
+       int *mface_to_poly_map;
+       int lindex[4]; /* only ever use 3 in this case */
+       int poly_index, j, mface_index;
+
+       const int numTex = CustomData_number_of_layers(pdata, CD_MTEXPOLY);
+       const int numCol = CustomData_number_of_layers(ldata, CD_MLOOPCOL);
+       const bool hasPCol = CustomData_has_layer(ldata, CD_PREVIEW_MLOOPCOL);
+       const bool hasOrigSpace = CustomData_has_layer(ldata, CD_ORIGSPACE_MLOOP);
+
+       mpoly = CustomData_get_layer(pdata, CD_MPOLY);
+       mloop = CustomData_get_layer(ldata, CD_MLOOP);
+
+       /* allocate the length of totfaces, avoid many small reallocs,
+        * if all faces are tri's it will be correct, quads == 2x allocs */
+       /* take care. we are _not_ calloc'ing so be sure to initialize each field */
+       mface_to_poly_map = MEM_mallocN(sizeof(*mface_to_poly_map) * looptris_tot, __func__);
+       mface             = MEM_mallocN(sizeof(*mface) *             looptris_tot, __func__);
+
+       mface_index = 0;
+       mp = mpoly;
+       for (poly_index = 0; poly_index < totpoly; poly_index++, mp++) {
+               if (mp->totloop < 3) {
+                       /* do nothing */
+               }
+
+#ifdef USE_TESSFACE_SPEEDUP
+
+#define ML_TO_MF(i1, i2, i3)                                                  \
+               mface_to_poly_map[mface_index] = poly_index;                          \
+               mf = &mface[mface_index];                                             \
+               /* set loop indices, transformed to vert indices later */             \
+               mf->v1 = mp->loopstart + i1;                                          \
+               mf->v2 = mp->loopstart + i2;                                          \
+               mf->v3 = mp->loopstart + i3;                                          \
+               mf->v4 = 0;                                                           \
+               mf->mat_nr = mp->mat_nr;                                              \
+               mf->flag = mp->flag;                                                  \
+               mf->edcode = 0;                                                       \
+               (void)0
+
+/* ALMOST IDENTICAL TO DEFINE ABOVE (see EXCEPTION) */
+#define ML_TO_MF_QUAD()                                                       \
+               mface_to_poly_map[mface_index] = poly_index;                          \
+               mf = &mface[mface_index];                                             \
+               /* set loop indices, transformed to vert indices later */             \
+               mf->v1 = mp->loopstart + 0; /* EXCEPTION */                           \
+               mf->v2 = mp->loopstart + 1; /* EXCEPTION */                           \
+               mf->v3 = mp->loopstart + 2; /* EXCEPTION */                           \
+               mf->v4 = mp->loopstart + 3; /* EXCEPTION */                           \
+               mf->mat_nr = mp->mat_nr;                                              \
+               mf->flag = mp->flag;                                                  \
+               mf->edcode = TESSFACE_IS_QUAD; /* EXCEPTION */                        \
+               (void)0
+
+
+               else if (mp->totloop == 3) {
+                       ML_TO_MF(0, 1, 2);
+                       mface_index++;
+               }
+               else if (mp->totloop == 4) {
+#ifdef USE_TESSFACE_QUADS
+                       ML_TO_MF_QUAD();
+                       mface_index++;
+#else
+                       ML_TO_MF(0, 1, 2);
+                       mface_index++;
+                       ML_TO_MF(0, 2, 3);
+                       mface_index++;
+#endif
+               }
+#endif /* USE_TESSFACE_SPEEDUP */
+               else {
+#define USE_TESSFACE_CALCNORMAL
+
+                       int totfilltri;
+
+#ifdef USE_TESSFACE_CALCNORMAL
+                       float normal[3];
+                       zero_v3(normal);
+#endif
+                       ml = mloop + mp->loopstart;
+
+                       if (UNLIKELY(sf_arena == NULL)) {
+                               sf_arena = BLI_memarena_new(BLI_SCANFILL_ARENA_SIZE, __func__);
+                       }
+
+                       BLI_scanfill_begin_arena(&sf_ctx, sf_arena);
+                       sf_vert_first = NULL;
+                       sf_vert_last = NULL;
+                       for (j = 0; j < mp->totloop; j++, ml++) {
+                               sf_vert = BLI_scanfill_vert_add(&sf_ctx, mvert[ml->v].co);
+
+                               sf_vert->keyindex = mp->loopstart + j;
+
+                               if (sf_vert_last) {
+                                       BLI_scanfill_edge_add(&sf_ctx, sf_vert_last, sf_vert);
+#ifdef USE_TESSFACE_CALCNORMAL
+                                       add_newell_cross_v3_v3v3(normal, sf_vert_last->co, sf_vert->co);
+#endif
+                               }
+
+                               if (!sf_vert_first)
+                                       sf_vert_first = sf_vert;
+                               sf_vert_last = sf_vert;
+                       }
+                       BLI_scanfill_edge_add(&sf_ctx, sf_vert_last, sf_vert_first);
+#ifdef USE_TESSFACE_CALCNORMAL
+                       add_newell_cross_v3_v3v3(normal, sf_vert_last->co, sf_vert_first->co);
+                       if (UNLIKELY(normalize_v3(normal) == 0.0f)) {
+                               normal[2] = 1.0f;
+                       }
+                       totfilltri = BLI_scanfill_calc_ex(&sf_ctx, 0, normal);
+#else
+                       totfilltri = BLI_scanfill_calc(&sf_ctx, 0);
+#endif
+                       BLI_assert(totfilltri <= mp->totloop - 2);
+                       (void)totfilltri;
+
+                       for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next, mf++) {
+                               mface_to_poly_map[mface_index] = poly_index;
+                               mf = &mface[mface_index];
+
+                               /* set loop indices, transformed to vert indices later */
+                               mf->v1 = sf_tri->v1->keyindex;
+                               mf->v2 = sf_tri->v2->keyindex;
+                               mf->v3 = sf_tri->v3->keyindex;
+                               mf->v4 = 0;
+
+                               mf->mat_nr = mp->mat_nr;
+                               mf->flag = mp->flag;
+
+#ifdef USE_TESSFACE_SPEEDUP
+                               mf->edcode = TESSFACE_SCANFILL; /* tag for sorting loop indices */
+#endif
+
+                               mface_index++;
+                       }
+
+                       BLI_scanfill_end_arena(&sf_ctx, sf_arena);
+
+#undef USE_TESSFACE_CALCNORMAL
+               }
+       }
+
+       if (sf_arena) {
+               BLI_memarena_free(sf_arena);
+               sf_arena = NULL;
+       }
+
+       CustomData_free(fdata, totface);
+       totface = mface_index;
+
+       BLI_assert(totface <= looptris_tot);
+
+       /* not essential but without this we store over-alloc'd memory in the CustomData layers */
+       if (LIKELY(looptris_tot != totface)) {
+               mface = MEM_reallocN(mface, sizeof(*mface) * totface);
+               mface_to_poly_map = MEM_reallocN(mface_to_poly_map, sizeof(*mface_to_poly_map) * totface);
+       }
+
+       CustomData_add_layer(fdata, CD_MFACE, CD_ASSIGN, mface, totface);
+
+       /* CD_ORIGINDEX will contain an array of indices from tessfaces to the polygons
+        * they are directly tessellated from */
+       CustomData_add_layer(fdata, CD_ORIGINDEX, CD_ASSIGN, mface_to_poly_map, totface);
+       CustomData_from_bmeshpoly(fdata, pdata, ldata, totface);
+
+       if (do_face_nor_cpy) {
+               /* If polys have a normals layer, copying that to faces can help
+                * avoid the need to recalculate normals later */
+               if (CustomData_has_layer(pdata, CD_NORMAL)) {
+                       float (*pnors)[3] = CustomData_get_layer(pdata, CD_NORMAL);
+                       float (*fnors)[3] = CustomData_add_layer(fdata, CD_NORMAL, CD_CALLOC, NULL, totface);
+                       for (mface_index = 0; mface_index < totface; mface_index++) {
+                               copy_v3_v3(fnors[mface_index], pnors[mface_to_poly_map[mface_index]]);
+                       }
+               }
+       }
+
+       mf = mface;
+       for (mface_index = 0; mface_index < totface; mface_index++, mf++) {
+
+#ifdef USE_TESSFACE_QUADS
+               const int mf_len = mf->edcode & TESSFACE_IS_QUAD ? 4 : 3;
+#endif
+
+#ifdef USE_TESSFACE_SPEEDUP
+               /* skip sorting when not using ngons */
+               if (UNLIKELY(mf->edcode & TESSFACE_SCANFILL))
+#endif
+               {
+                       /* sort loop indices to ensure winding is correct */
+                       if (mf->v1 > mf->v2) SWAP(unsigned int, mf->v1, mf->v2);
+                       if (mf->v2 > mf->v3) SWAP(unsigned int, mf->v2, mf->v3);
+                       if (mf->v1 > mf->v2) SWAP(unsigned int, mf->v1, mf->v2);
+
+                       if (mf->v1 > mf->v2) SWAP(unsigned int, mf->v1, mf->v2);
+                       if (mf->v2 > mf->v3) SWAP(unsigned int, mf->v2, mf->v3);
+                       if (mf->v1 > mf->v2) SWAP(unsigned int, mf->v1, mf->v2);
+               }
+
+               /* end abusing the edcode */
+#if defined(USE_TESSFACE_QUADS) || defined(USE_TESSFACE_SPEEDUP)
+               mf->edcode = 0;
+#endif
+
+
+               lindex[0] = mf->v1;
+               lindex[1] = mf->v2;
+               lindex[2] = mf->v3;
+#ifdef USE_TESSFACE_QUADS
+               if (mf_len == 4) lindex[3] = mf->v4;
+#endif
+
+               /*transform loop indices to vert indices*/
+               mf->v1 = mloop[mf->v1].v;
+               mf->v2 = mloop[mf->v2].v;
+               mf->v3 = mloop[mf->v3].v;
+#ifdef USE_TESSFACE_QUADS
+               if (mf_len == 4) mf->v4 = mloop[mf->v4].v;
+#endif
+
+               BKE_mesh_loops_to_mface_corners(fdata, ldata, pdata,
+                                               lindex, mface_index, mface_to_poly_map[mface_index],
+#ifdef USE_TESSFACE_QUADS
+                                               mf_len,
+#else
+                                               3,
+#endif
+                                               numTex, numCol, hasPCol, hasOrigSpace);
+
+
+#ifdef USE_TESSFACE_QUADS
+               test_index_face(mf, fdata, mface_index, mf_len);
+#endif
+
+       }
+
+       return totface;
+
+#undef USE_TESSFACE_SPEEDUP
+
+}
+
+
+#ifdef USE_BMESH_SAVE_AS_COMPAT
+
+/**
+ * This function recreates a tessellation.
+ * returns number of tessellation faces.
+ *
+ * for forwards compat only quad->tri polys to mface, skip ngons.
+ */
+int BKE_mesh_mpoly_to_mface(struct CustomData *fdata, struct CustomData *ldata,
+                            struct CustomData *pdata, int totface, int UNUSED(totloop), int totpoly)
+{
+       MLoop *mloop;
+
+       int lindex[4];
+       int i;
+       int k;
+
+       MPoly *mp, *mpoly;
+       MFace *mface = NULL, *mf;
+       BLI_array_declare(mface);
+
+       const int numTex = CustomData_number_of_layers(pdata, CD_MTEXPOLY);
+       const int numCol = CustomData_number_of_layers(ldata, CD_MLOOPCOL);
+       const bool hasPCol = CustomData_has_layer(ldata, CD_PREVIEW_MLOOPCOL);
+       const bool hasOrigSpace = CustomData_has_layer(ldata, CD_ORIGSPACE_MLOOP);
+
+       mpoly = CustomData_get_layer(pdata, CD_MPOLY);
+       mloop = CustomData_get_layer(ldata, CD_MLOOP);
+
+       mp = mpoly;
+       k = 0;
+       for (i = 0; i < totpoly; i++, mp++) {
+               if (ELEM(mp->totloop, 3, 4)) {
+                       BLI_array_grow_one(mface);
+                       mf = &mface[k];
+
+                       mf->mat_nr = mp->mat_nr;
+                       mf->flag = mp->flag;
+
+                       mf->v1 = mp->loopstart + 0;
+                       mf->v2 = mp->loopstart + 1;
+                       mf->v3 = mp->loopstart + 2;
+                       mf->v4 = (mp->totloop == 4) ? (mp->loopstart + 3) : 0;
+
+                       /* abuse edcode for temp storage and clear next loop */
+                       mf->edcode = (char)mp->totloop; /* only ever 3 or 4 */
+
+                       k++;
+               }
+       }
+
+       CustomData_free(fdata, totface);
+
+       totface = k;
+
+       CustomData_add_layer(fdata, CD_MFACE, CD_ASSIGN, mface, totface);
+
+       CustomData_from_bmeshpoly(fdata, pdata, ldata, totface);
+
+       mp = mpoly;
+       k = 0;
+       for (i = 0; i < totpoly; i++, mp++) {
+               if (ELEM(mp->totloop, 3, 4)) {
+                       mf = &mface[k];
+
+                       if (mf->edcode == 3) {
+                               /* sort loop indices to ensure winding is correct */
+                               /* NO SORT - looks like we can skip this */
+
+                               lindex[0] = mf->v1;
+                               lindex[1] = mf->v2;
+                               lindex[2] = mf->v3;
+                               lindex[3] = 0; /* unused */
+
+                               /* transform loop indices to vert indices */
+                               mf->v1 = mloop[mf->v1].v;
+                               mf->v2 = mloop[mf->v2].v;
+                               mf->v3 = mloop[mf->v3].v;
+
+                               BKE_mesh_loops_to_mface_corners(fdata, ldata, pdata,
+                                                               lindex, k, i, 3,
+                                                               numTex, numCol, hasPCol, hasOrigSpace);
+                               test_index_face(mf, fdata, k, 3);
+                       }
+                       else {
+                               /* sort loop indices to ensure winding is correct */
+                               /* NO SORT - looks like we can skip this */
+
+                               lindex[0] = mf->v1;
+                               lindex[1] = mf->v2;
+                               lindex[2] = mf->v3;
+                               lindex[3] = mf->v4;
+
+                               /* transform loop indices to vert indices */
+                               mf->v1 = mloop[mf->v1].v;
+                               mf->v2 = mloop[mf->v2].v;
+                               mf->v3 = mloop[mf->v3].v;
+                               mf->v4 = mloop[mf->v4].v;
+
+                               BKE_mesh_loops_to_mface_corners(fdata, ldata, pdata,
+                                                               lindex, k, i, 4,
+                                                               numTex, numCol, hasPCol, hasOrigSpace);
+                               test_index_face(mf, fdata, k, 4);
+                       }
+
+                       mf->edcode = 0;
+
+                       k++;
+               }
+       }
+
+       return k;
+}
+#endif /* USE_BMESH_SAVE_AS_COMPAT */
+
+
+static void bm_corners_to_loops_ex(ID *id, CustomData *fdata, CustomData *ldata, CustomData *pdata,
+                                   MFace *mface, int totloop, int findex, int loopstart, int numTex, int numCol)
+{
+       MTFace *texface;
+       MTexPoly *texpoly;
+       MCol *mcol;
+       MLoopCol *mloopcol;
+       MLoopUV *mloopuv;
+       MFace *mf;
+       int i;
+
+       mf = mface + findex;
+
+       for (i = 0; i < numTex; i++) {
+               texface = CustomData_get_n(fdata, CD_MTFACE, findex, i);
+               texpoly = CustomData_get_n(pdata, CD_MTEXPOLY, findex, i);
+
+               ME_MTEXFACE_CPY(texpoly, texface);
+
+               mloopuv = CustomData_get_n(ldata, CD_MLOOPUV, loopstart, i);
+               copy_v2_v2(mloopuv->uv, texface->uv[0]); mloopuv++;
+               copy_v2_v2(mloopuv->uv, texface->uv[1]); mloopuv++;
+               copy_v2_v2(mloopuv->uv, texface->uv[2]); mloopuv++;
+
+               if (mf->v4) {
+                       copy_v2_v2(mloopuv->uv, texface->uv[3]); mloopuv++;
+               }
+       }
+
+       for (i = 0; i < numCol; i++) {
+               mloopcol = CustomData_get_n(ldata, CD_MLOOPCOL, loopstart, i);
+               mcol = CustomData_get_n(fdata, CD_MCOL, findex, i);
+
+               MESH_MLOOPCOL_FROM_MCOL(mloopcol, &mcol[0]); mloopcol++;
+               MESH_MLOOPCOL_FROM_MCOL(mloopcol, &mcol[1]); mloopcol++;
+               MESH_MLOOPCOL_FROM_MCOL(mloopcol, &mcol[2]); mloopcol++;
+               if (mf->v4) {
+                       MESH_MLOOPCOL_FROM_MCOL(mloopcol, &mcol[3]); mloopcol++;
+               }
+       }
+
+       if (CustomData_has_layer(fdata, CD_MDISPS)) {
+               MDisps *ld = CustomData_get(ldata, loopstart, CD_MDISPS);
+               MDisps *fd = CustomData_get(fdata, findex, CD_MDISPS);
+               float (*disps)[3] = fd->disps;
+               int tot = mf->v4 ? 4 : 3;
+               int side, corners;
+
+               if (CustomData_external_test(fdata, CD_MDISPS)) {
+                       if (id && fdata->external) {
+                               CustomData_external_add(ldata, id, CD_MDISPS,
+                                                       totloop, fdata->external->filename);
+                       }
+               }
+
+               corners = multires_mdisp_corners(fd);
+
+               if (corners == 0) {
+                       /* Empty MDisp layers appear in at least one of the sintel.blend files.
+                        * Not sure why this happens, but it seems fine to just ignore them here.
+                        * If (corners == 0) for a non-empty layer though, something went wrong. */
+                       BLI_assert(fd->totdisp == 0);
+               }
+               else {
+                       side = sqrt(fd->totdisp / corners);
+
+                       for (i = 0; i < tot; i++, disps += side * side, ld++) {
+                               ld->totdisp = side * side;
+                               ld->level = (int)(logf(side - 1.0f) / (float)M_LN2) + 1;
+
+                               if (ld->disps)
+                                       MEM_freeN(ld->disps);
+
+                               ld->disps = MEM_mallocN(sizeof(float) * 3 * side * side, "converted loop mdisps");
+                               if (fd->disps) {
+                                       memcpy(ld->disps, disps, sizeof(float) * 3 * side * side);
+                               }
+                               else {
+                                       memset(ld->disps, 0, sizeof(float) * 3 * side * side);
+                               }
+                       }
+               }
+       }
+}
+
+
+void BKE_mesh_convert_mfaces_to_mpolys(Mesh *mesh)
+{
+       BKE_mesh_convert_mfaces_to_mpolys_ex(&mesh->id, &mesh->fdata, &mesh->ldata, &mesh->pdata,
+                                            mesh->totedge, mesh->totface, mesh->totloop, mesh->totpoly,
+                                            mesh->medge, mesh->mface,
+                                            &mesh->totloop, &mesh->totpoly, &mesh->mloop, &mesh->mpoly);
+
+       BKE_mesh_update_customdata_pointers(mesh, true);
+}
+
+/* the same as BKE_mesh_convert_mfaces_to_mpolys but oriented to be used in do_versions from readfile.c
+ * the difference is how active/render/clone/stencil indices are handled here
+ *
+ * normally thay're being set from pdata which totally makes sense for meshes which are already
+ * converted to bmesh structures, but when loading older files indices shall be updated in other
+ * way around, so newly added pdata and ldata would have this indices set based on fdata layer
+ *
+ * this is normally only needed when reading older files, in all other cases BKE_mesh_convert_mfaces_to_mpolys
+ * shall be always used
+ */
+void BKE_mesh_do_versions_convert_mfaces_to_mpolys(Mesh *mesh)
+{
+       BKE_mesh_convert_mfaces_to_mpolys_ex(&mesh->id, &mesh->fdata, &mesh->ldata, &mesh->pdata,
+                                            mesh->totedge, mesh->totface, mesh->totloop, mesh->totpoly,
+                                            mesh->medge, mesh->mface,
+                                            &mesh->totloop, &mesh->totpoly, &mesh->mloop, &mesh->mpoly);
+
+       CustomData_bmesh_do_versions_update_active_layers(&mesh->fdata, &mesh->pdata, &mesh->ldata);
+
+       BKE_mesh_update_customdata_pointers(mesh, true);
+}
+
+void BKE_mesh_convert_mfaces_to_mpolys_ex(ID *id, CustomData *fdata, CustomData *ldata, CustomData *pdata,
+                                          int totedge_i, int totface_i, int totloop_i, int totpoly_i,
+                                          MEdge *medge, MFace *mface,
+                                          int *totloop_r, int *totpoly_r,
+                                          MLoop **mloop_r, MPoly **mpoly_r)
+{
+       MFace *mf;
+       MLoop *ml, *mloop;
+       MPoly *mp, *mpoly;
+       MEdge *me;
+       EdgeHash *eh;
+       int numTex, numCol;
+       int i, j, totloop, totpoly, *polyindex;
+
+       /* just in case some of these layers are filled in (can happen with python created meshes) */
+       CustomData_free(ldata, totloop_i);
+       CustomData_free(pdata, totpoly_i);
+
+       totpoly = totface_i;
+       mpoly = MEM_callocN(sizeof(MPoly) * totpoly, "mpoly converted");
+       CustomData_add_layer(pdata, CD_MPOLY, CD_ASSIGN, mpoly, totpoly);
+
+       numTex = CustomData_number_of_layers(fdata, CD_MTFACE);
+       numCol = CustomData_number_of_layers(fdata, CD_MCOL);
+
+       totloop = 0;
+       mf = mface;
+       for (i = 0; i < totface_i; i++, mf++) {
+               totloop += mf->v4 ? 4 : 3;
+       }
+
+       mloop = MEM_callocN(sizeof(MLoop) * totloop, "mloop converted");
+
+       CustomData_add_layer(ldata, CD_MLOOP, CD_ASSIGN, mloop, totloop);
+
+       CustomData_to_bmeshpoly(fdata, pdata, ldata, totloop, totpoly);
+
+       if (id) {
+               /* ensure external data is transferred */
+               CustomData_external_read(fdata, id, CD_MASK_MDISPS, totface_i);
+       }
+
+       eh = BLI_edgehash_new_ex(__func__, totedge_i);
+
+       /* build edge hash */
+       me = medge;
+       for (i = 0; i < totedge_i; i++, me++) {
+               BLI_edgehash_insert(eh, me->v1, me->v2, SET_INT_IN_POINTER(i));
+
+               /* unrelated but avoid having the FGON flag enabled, so we can reuse it later for something else */
+               me->flag &= ~ME_FGON;
+       }
+
+       polyindex = CustomData_get_layer(fdata, CD_ORIGINDEX);
+
+       j = 0; /* current loop index */
+       ml = mloop;
+       mf = mface;
+       mp = mpoly;
+       for (i = 0; i < totface_i; i++, mf++, mp++) {
+               mp->loopstart = j;
+
+               mp->totloop = mf->v4 ? 4 : 3;
+
+               mp->mat_nr = mf->mat_nr;
+               mp->flag = mf->flag;
+
+#       define ML(v1, v2) { \
+                       ml->v = mf->v1; ml->e = GET_INT_FROM_POINTER(BLI_edgehash_lookup(eh, mf->v1, mf->v2)); ml++; j++; \
+               } (void)0
+
+               ML(v1, v2);
+               ML(v2, v3);
+               if (mf->v4) {
+                       ML(v3, v4);
+                       ML(v4, v1);
+               }
+               else {
+                       ML(v3, v1);
+               }
+
+#       undef ML
+
+               bm_corners_to_loops_ex(id, fdata, ldata, pdata, mface, totloop, i, mp->loopstart, numTex, numCol);
+
+               if (polyindex) {
+                       *polyindex = i;
+                       polyindex++;
+               }
+       }
+
+       /* note, we don't convert NGons at all, these are not even real ngons,
+        * they have their own UV's, colors etc - its more an editing feature. */
+
+       BLI_edgehash_free(eh, NULL);
+
+       *totpoly_r = totpoly;
+       *totloop_r = totloop;
+       *mpoly_r = mpoly;
+       *mloop_r = mloop;
+}
+/** \} */
+
+
+/* -------------------------------------------------------------------- */
+
+/** \name Mesh Flag Flushing
+ * \{ */
+
+/* update the hide flag for edges and faces from the corresponding
+ * flag in verts */
+void BKE_mesh_flush_hidden_from_verts_ex(const MVert *mvert,
+                                         const MLoop *mloop,
+                                         MEdge *medge, const int totedge,
+                                         MPoly *mpoly, const int totpoly)
+{
+       int i, j;
+
+       for (i = 0; i < totedge; i++) {
+               MEdge *e = &medge[i];
+               if (mvert[e->v1].flag & ME_HIDE ||
+                   mvert[e->v2].flag & ME_HIDE)
+               {
+                       e->flag |= ME_HIDE;
+               }
+               else {
+                       e->flag &= ~ME_HIDE;
+               }
+       }
+       for (i = 0; i < totpoly; i++) {
+               MPoly *p = &mpoly[i];
+               p->flag &= ~ME_HIDE;
+               for (j = 0; j < p->totloop; j++) {
+                       if (mvert[mloop[p->loopstart + j].v].flag & ME_HIDE)
+                               p->flag |= ME_HIDE;
+               }
+       }
+}
+void BKE_mesh_flush_hidden_from_verts(Mesh *me)
+{
+       BKE_mesh_flush_hidden_from_verts_ex(me->mvert, me->mloop,
+                                           me->medge, me->totedge,
+                                           me->mpoly, me->totpoly);
+}
+
+void BKE_mesh_flush_hidden_from_polys_ex(MVert *mvert,
+                                         const MLoop *mloop,
+                                         MEdge *medge, const int UNUSED(totedge),
+                                         const MPoly *mpoly, const int totpoly)
+{
+       const MPoly *mp;
+       int i;
+
+       i = totpoly;
+       for (mp = mpoly; i--; mp++) {
+               if (mp->flag & ME_HIDE) {
+                       const MLoop *ml;
+                       int j;
+                       j = mp->totloop;
+                       for (ml = &mloop[mp->loopstart]; j--; ml++) {
+                               mvert[ml->v].flag |= ME_HIDE;
+                               medge[ml->e].flag |= ME_HIDE;
+                       }
+               }
+       }
+
+       i = totpoly;
+       for (mp = mpoly; i--; mp++) {
+               if ((mp->flag & ME_HIDE) == 0) {
+                       const MLoop *ml;
+                       int j;
+                       j = mp->totloop;
+                       for (ml = &mloop[mp->loopstart]; j--; ml++) {
+                               mvert[ml->v].flag &= ~ME_HIDE;
+                               medge[ml->e].flag &= ~ME_HIDE;
+                       }
+               }
+       }
+}
+void BKE_mesh_flush_hidden_from_polys(Mesh *me)
+{
+       BKE_mesh_flush_hidden_from_polys_ex(me->mvert, me->mloop,
+                                           me->medge, me->totedge,
+                                           me->mpoly, me->totpoly);
+}
+
+/**
+ * simple poly -> vert/edge selection.
+ */
+void BKE_mesh_flush_select_from_polys_ex(MVert *mvert,       const int totvert,
+                                         const MLoop *mloop,
+                                         MEdge *medge,       const int totedge,
+                                         const MPoly *mpoly, const int totpoly)
+{
+       MVert *mv;
+       MEdge *med;
+       const MPoly *mp;
+       int i;
+
+       i = totvert;
+       for (mv = mvert; i--; mv++) {
+               mv->flag &= ~SELECT;
+       }
+
+       i = totedge;
+       for (med = medge; i--; med++) {
+               med->flag &= ~SELECT;
+       }
+
+       i = totpoly;
+       for (mp = mpoly; i--; mp++) {
+               /* assume if its selected its not hidden and none of its verts/edges are hidden
+                * (a common assumption)*/
+               if (mp->flag & ME_FACE_SEL) {
+                       const MLoop *ml;
+                       int j;
+                       j = mp->totloop;
+                       for (ml = &mloop[mp->loopstart]; j--; ml++) {
+                               mvert[ml->v].flag |= SELECT;
+                               medge[ml->e].flag |= SELECT;
+                       }
+               }
+       }
+}
+void BKE_mesh_flush_select_from_polys(Mesh *me)
+{
+       BKE_mesh_flush_select_from_polys_ex(me->mvert, me->totvert,
+                                        me->mloop,
+                                        me->medge, me->totedge,
+                                        me->mpoly, me->totpoly);
+}
+
+void BKE_mesh_flush_select_from_verts_ex(const MVert *mvert, const int UNUSED(totvert),
+                                         const MLoop *mloop,
+                                         MEdge *medge,       const int totedge,
+                                         MPoly *mpoly,       const int totpoly)
+{
+       MEdge *med;
+       MPoly *mp;
+       int i;
+
+       /* edges */
+       i = totedge;
+       for (med = medge; i--; med++) {
+               if ((med->flag & ME_HIDE) == 0) {
+                       if ((mvert[med->v1].flag & SELECT) && (mvert[med->v2].flag & SELECT)) {
+                               med->flag |= SELECT;
+                       }
+                       else {
+                               med->flag &= ~SELECT;
+                       }
+               }
+       }
+
+       /* polys */
+       i = totpoly;
+       for (mp = mpoly; i--; mp++) {
+               if ((mp->flag & ME_HIDE) == 0) {
+                       int ok = TRUE;
+                       const MLoop *ml;
+                       int j;
+                       j = mp->totloop;
+                       for (ml = &mloop[mp->loopstart]; j--; ml++) {
+                               if ((mvert[ml->v].flag & SELECT) == 0) {
+                                       ok = FALSE;
+                                       break;
+                               }
+                       }
+
+                       if (ok) {
+                               mp->flag |= ME_FACE_SEL;
+                       }
+                       else {
+                               mp->flag &= ~ME_FACE_SEL;
+                       }
+               }
+       }
+}
+void BKE_mesh_flush_select_from_verts(Mesh *me)
+{
+       BKE_mesh_flush_select_from_verts_ex(me->mvert, me->totvert,
+                                           me->mloop,
+                                           me->medge, me->totedge,
+                                           me->mpoly, me->totpoly);
+}
+/** \} */
+
+
+/* -------------------------------------------------------------------- */
+
+/** \name Mesh Smooth Groups
+ * \{ */
+
+/**
+ * Calculate smooth groups from sharp edges.
+ *
+ * \param r_totgroup The total number of groups, 1 or more.
+ * \return Polygon aligned array of group index values (bitflags if use_bitflags is true), starting at 1.
+ */
+int *BKE_mesh_calc_smoothgroups(const MEdge *medge, const int totedge,
+                                const MPoly *mpoly, const int totpoly,
+                                const MLoop *mloop, const int totloop,
+                                int *r_totgroup, const bool use_bitflags)
+{
+       int *poly_groups;
+       int *poly_stack;
+
+       int poly_prev = 0;
+       const int temp_poly_group_id = 3;  /* Placeholder value. */
+       const int poly_group_id_overflowed = 5;  /* Group we could not find any available bit, will be reset to 0 at end */
+       int tot_group = 0;
+       bool group_id_overflow = false;
+
+       /* map vars */
+       MeshElemMap *edge_poly_map;
+       int *edge_poly_mem;
+
+       if (totpoly == 0) {
+               *r_totgroup = 0;
+               return NULL;
+       }
+
+       BKE_mesh_edge_poly_map_create(&edge_poly_map, &edge_poly_mem,
+                                     medge, totedge,
+                                     mpoly, totpoly,
+                                     mloop, totloop);
+
+       poly_groups = MEM_callocN(sizeof(int) * totpoly, __func__);
+       poly_stack  = MEM_mallocN(sizeof(int) * totpoly, __func__);
+
+       while (true) {
+               int poly;
+               int bit_poly_group_mask = 0;
+               int poly_group_id;
+               int ps_curr_idx = 0, ps_end_idx = 0;  /* stack indices */
+
+               for (poly = poly_prev; poly < totpoly; poly++) {
+                       if (poly_groups[poly] == 0) {
+                               break;
+                       }
+               }
+
+               if (poly == totpoly) {
+                       /* all done */
+                       break;
+               }
+
+               poly_group_id = use_bitflags ? temp_poly_group_id : ++tot_group;
+
+               /* start searching from here next time */
+               poly_prev = poly + 1;
+
+               poly_groups[poly] = poly_group_id;
+               poly_stack[ps_end_idx++] = poly;
+
+               while (ps_curr_idx != ps_end_idx) {
+                       const MPoly *mp;
+                       const MLoop *ml;
+                       int j;
+
+                       poly = poly_stack[ps_curr_idx++];
+                       BLI_assert(poly_groups[poly] == poly_group_id);
+
+                       mp = &mpoly[poly];
+                       for (ml = &mloop[mp->loopstart], j = mp->totloop; j--; ml++) {
+                               /* loop over poly users */
+                               const MeshElemMap *map_ele = &edge_poly_map[ml->e];
+                               int *p = map_ele->indices;
+                               int i = map_ele->count;
+                               if (!(medge[ml->e].flag & ME_SHARP)) {
+                                       for (; i--; p++) {
+                                               /* if we meet other non initialized its a bug */
+                                               BLI_assert(ELEM(poly_groups[*p], 0, poly_group_id));
+
+                                               if (poly_groups[*p] == 0) {
+                                                       poly_groups[*p] = poly_group_id;
+                                                       poly_stack[ps_end_idx++] = *p;
+                                               }
+                                       }
+                               }
+                               else if (use_bitflags) {
+                                       /* Find contiguous smooth groups already assigned, these are the values we can't reuse! */
+                                       for (; i--; p++) {
+                                               int bit = poly_groups[*p];
+                                               if (!ELEM3(bit, 0, poly_group_id, poly_group_id_overflowed) &&
+                                                   !(bit_poly_group_mask & bit))
+                                               {
+                                                       bit_poly_group_mask |= bit;
+                                               }
+                                       }
+                               }
+                       }
+               }
+               /* And now, we have all our poly from current group in poly_stack (from 0 to (ps_end_idx - 1)), as well as
+                * all smoothgroups bits we can't use in bit_poly_group_mask.
+                */
+               if (use_bitflags) {
+                       int i, *p, gid_bit = 0;
+                       poly_group_id = 1;
+
+                       /* Find first bit available! */
+                       for (; (poly_group_id & bit_poly_group_mask) && (gid_bit < 32); gid_bit++) {
+                               poly_group_id <<= 1;  /* will 'overflow' on last possible iteration. */
+                       }
+                       if (UNLIKELY(gid_bit > 31)) {
+                               /* All bits used in contiguous smooth groups, we can't do much!
+                                * Note: this is *very* unlikely - theoretically, four groups are enough, I don't think we can reach
+                                *       this goal with such a simple algo, but I don't think either we'll never need all 32 groups!
+                                */
+                               printf("Warning, could not find an available id for current smooth group, faces will me marked "
+                                      "as out of any smooth group...\n");
+                               poly_group_id = poly_group_id_overflowed; /* Can't use 0, will have to set them to this value later. */
+                               group_id_overflow = true;
+                       }
+                       if (gid_bit > tot_group) {
+                               tot_group = gid_bit;
+                       }
+                       /* And assign the final smooth group id to that poly group! */
+                       for (i = ps_end_idx, p = poly_stack; i--; p++) {
+                               poly_groups[*p] = poly_group_id;
+                       }
+               }
+       }
+
+       if (UNLIKELY(group_id_overflow)) {
+               int i = totpoly, *gid = poly_groups;
+               for (; i--; gid++) {
+                       if (*gid == poly_group_id_overflowed) {
+                               *gid = 0;
+                       }
+               }
+       }
+
+       MEM_freeN(edge_poly_map);
+       MEM_freeN(edge_poly_mem);
+       MEM_freeN(poly_stack);
+
+       *r_totgroup = tot_group + 1;
+
+       return poly_groups;
+}
+/** \} */
+
+
+/* -------------------------------------------------------------------- */
+
+/** \name Mesh Spatial Calculation
+ * \{ */
+
+/**
+ * This function takes the difference between 2 vertex-coord-arrays
+ * (\a vert_cos_src, \a vert_cos_dst),
+ * and applies the difference to \a vert_cos_new relative to \a vert_cos_org.
+ *
+ * \param vert_cos_src reference deform source.
+ * \param vert_cos_dst reference deform destination.
+ *
+ * \param vert_cos_org reference for the output location.
+ * \param vert_cos_new resulting coords.
+ */
+void BKE_mesh_calc_relative_deform(
+        const MPoly *mpoly, const int totpoly,
+        const MLoop *mloop, const int totvert,
+
+        const float (*vert_cos_src)[3],
+        const float (*vert_cos_dst)[3],
+
+        const float (*vert_cos_org)[3],
+              float (*vert_cos_new)[3])
+{
+       const MPoly *mp;
+       int i;
+
+       int *vert_accum = MEM_callocN(sizeof(*vert_accum) * totvert, __func__);
+
+       memset(vert_cos_new, '\0', sizeof(*vert_cos_new) * totvert);
+
+       for (i = 0, mp = mpoly; i < totpoly; i++, mp++) {
+               const MLoop *loopstart = mloop + mp->loopstart;
+               int j;
+
+               for (j = 0; j < mp->totloop; j++) {
+                       int v_prev = (loopstart + ((mp->totloop + (j - 1)) % mp->totloop))->v;
+                       int v_curr = (loopstart + j)->v;
+                       int v_next = (loopstart + ((j + 1) % mp->totloop))->v;
+
+                       float tvec[3];
+
+                       barycentric_transform(
+                                   tvec, vert_cos_dst[v_curr],
+                                   vert_cos_org[v_prev], vert_cos_org[v_curr], vert_cos_org[v_next],
+                                   vert_cos_src[v_prev], vert_cos_src[v_curr], vert_cos_src[v_next]
+                                   );
+
+                       add_v3_v3(vert_cos_new[v_curr], tvec);
+                       vert_accum[v_curr] += 1;
+               }
+       }
+
+       for (i = 0; i < totvert; i++) {
+               if (vert_accum[i]) {
+                       mul_v3_fl(vert_cos_new[i], 1.0f / (float)vert_accum[i]);
+               }
+               else {
+                       copy_v3_v3(vert_cos_new[i], vert_cos_org[i]);
+               }
+       }
+
+       MEM_freeN(vert_accum);
+}
+/** \} */
index b5056f75bf9b38fb83f21a32c5aa01a686ed2e26..6ec14add8a9c032ebb0fbfa8ef3c9fc3dc6c3be7 100644 (file)
 
 #include "MEM_guardedalloc.h"
 
-#define SELECT 1
+/* loop v/e are unsigned, so using max uint_32 value as invalid marker... */
+#define INVALID_LOOP_EDGE_MARKER 4294967295u
+
+
+/** \name Internal functions
+ * \{ */
 
 typedef union {
        uint32_t verts[2];
@@ -181,6 +186,14 @@ static int search_polyloop_cmp(const void *v1, const void *v2)
        /* Else, sort on loopstart. */
        return sp1->loopstart > sp2->loopstart ? 1 : sp1->loopstart < sp2->loopstart ? -1 : 0;
 }
+/** \} */
+
+
+
+/* -------------------------------------------------------------------- */
+
+/** \name Mesh Validation
+ * \{ */
 
 #define PRINT_MSG(...) (void) \
        ( \
@@ -960,6 +973,331 @@ int BKE_mesh_validate(Mesh *me, const int do_verbose)
                return false;
        }
 }
+/** \} */
+
+
+
+/* -------------------------------------------------------------------- */
+
+/** \name Mesh Stripping (removing invalid data)
+ * \{ */
+
+/* We need to keep this for edge creation (for now?), and some old readfile code... */
+void BKE_mesh_strip_loose_faces(Mesh *me)
+{
+       MFace *f;
+       int a, b;
+
+       for (a = b = 0, f = me->mface; a < me->totface; a++, f++) {
+               if (f->v3) {
+                       if (a != b) {
+                               memcpy(&me->mface[b], f, sizeof(me->mface[b]));
+                               CustomData_copy_data(&me->fdata, &me->fdata, a, b, 1);
+                       }
+                       b++;
+               }
+       }
+       if (a != b) {
+               CustomData_free_elem(&me->fdata, b, a - b);
+               me->totface = b;
+       }
+}
+
+/* Works on both loops and polys! */
+/* Note: It won't try to guess which loops of an invalid poly to remove!
+ *       this is the work of the caller, to mark those loops...
+ *       See e.g. BKE_mesh_validate_arrays(). */
+void BKE_mesh_strip_loose_polysloops(Mesh *me)
+{
+       MPoly *p;
+       MLoop *l;
+       int a, b;
+       /* New loops idx! */
+       int *new_idx = MEM_mallocN(sizeof(int) * me->totloop, __func__);
+
+       for (a = b = 0, p = me->mpoly; a < me->totpoly; a++, p++) {
+               int invalid = FALSE;
+               int i = p->loopstart;
+               int stop = i + p->totloop;
+
+               if (stop > me->totloop || stop < i) {
+                       invalid = TRUE;
+               }
+               else {
+                       l = &me->mloop[i];
+                       i = stop - i;
+                       /* If one of the poly's loops is invalid, the whole poly is invalid! */
+                       for (; i--; l++) {
+                               if (l->e == INVALID_LOOP_EDGE_MARKER) {
+                                       invalid = TRUE;
+                                       break;
+                               }
+                       }
+               }
+
+               if (p->totloop >= 3 && !invalid) {
+                       if (a != b) {
+                               memcpy(&me->mpoly[b], p, sizeof(me->mpoly[b]));
+                               CustomData_copy_data(&me->pdata, &me->pdata, a, b, 1);
+                       }
+                       b++;
+               }
+       }
+       if (a != b) {
+               CustomData_free_elem(&me->pdata, b, a - b);
+               me->totpoly = b;
+       }
+
+       /* And now, get rid of invalid loops. */
+       for (a = b = 0, l = me->mloop; a < me->totloop; a++, l++) {
+               if (l->e != INVALID_LOOP_EDGE_MARKER) {
+                       if (a != b) {
+                               memcpy(&me->mloop[b], l, sizeof(me->mloop[b]));
+                               CustomData_copy_data(&me->ldata, &me->ldata, a, b, 1);
+                       }
+                       new_idx[a] = b;
+                       b++;
+               }
+               else {
+                       /* XXX Theoretically, we should be able to not do this, as no remaining poly
+                        *     should use any stripped loop. But for security's sake... */
+                       new_idx[a] = -a;
+               }
+       }
+       if (a != b) {
+               CustomData_free_elem(&me->ldata, b, a - b);
+               me->totloop = b;
+       }
+
+       /* And now, update polys' start loop index. */
+       /* Note: At this point, there should never be any poly using a striped loop! */
+       for (a = 0, p = me->mpoly; a < me->totpoly; a++, p++) {
+               p->loopstart = new_idx[p->loopstart];
+       }
+
+       MEM_freeN(new_idx);
+}
+
+void BKE_mesh_strip_loose_edges(Mesh *me)
+{
+       MEdge *e;
+       MLoop *l;
+       int a, b;
+       unsigned int *new_idx = MEM_mallocN(sizeof(int) * me->totedge, __func__);
+
+       for (a = b = 0, e = me->medge; a < me->totedge; a++, e++) {
+               if (e->v1 != e->v2) {
+                       if (a != b) {
+                               memcpy(&me->medge[b], e, sizeof(me->medge[b]));
+                               CustomData_copy_data(&me->edata, &me->edata, a, b, 1);
+                       }
+                       new_idx[a] = b;
+                       b++;
+               }
+               else {
+                       new_idx[a] = INVALID_LOOP_EDGE_MARKER;
+               }
+       }
+       if (a != b) {
+               CustomData_free_elem(&me->edata, b, a - b);
+               me->totedge = b;
+       }
+
+       /* And now, update loops' edge indices. */
+       /* XXX We hope no loop was pointing to a striped edge!
+        *     Else, its e will be set to INVALID_LOOP_EDGE_MARKER :/ */
+       for (a = 0, l = me->mloop; a < me->totloop; a++, l++) {
+               l->e = new_idx[l->e];
+       }
+
+       MEM_freeN(new_idx);
+}
+/** \} */
+
+
+
+/* -------------------------------------------------------------------- */
+
+/** \name Mesh Edge Calculation
+ * \{ */
+
+/* make edges in a Mesh, for outside of editmode */
+
+struct EdgeSort {
+       unsigned int v1, v2;
+       char is_loose, is_draw;
+};
+
+/* edges have to be added with lowest index first for sorting */
+static void to_edgesort(struct EdgeSort *ed,
+                        unsigned int v1, unsigned int v2,
+                        char is_loose, short is_draw)
+{
+       if (v1 < v2) {
+               ed->v1 = v1; ed->v2 = v2;
+       }
+       else {
+               ed->v1 = v2; ed->v2 = v1;
+       }
+       ed->is_loose = is_loose;
+       ed->is_draw = is_draw;
+}
+
+static int vergedgesort(const void *v1, const void *v2)
+{
+       const struct EdgeSort *x1 = v1, *x2 = v2;
+
+       if (x1->v1 > x2->v1) return 1;
+       else if (x1->v1 < x2->v1) return -1;
+       else if (x1->v2 > x2->v2) return 1;
+       else if (x1->v2 < x2->v2) return -1;
+
+       return 0;
+}
+
+
+/* Create edges based on known verts and faces,
+ * this function is only used when loading very old blend files */
+
+static void mesh_calc_edges_mdata(
+        MVert *UNUSED(allvert), MFace *allface, MLoop *allloop,
+        MPoly *allpoly, int UNUSED(totvert), int totface, int UNUSED(totloop), int totpoly,
+        const bool use_old,
+        MEdge **r_medge, int *r_totedge)
+{
+       MPoly *mpoly;
+       MFace *mface;
+       MEdge *medge, *med;
+       EdgeHash *hash;
+       struct EdgeSort *edsort, *ed;
+       int a, totedge = 0;
+       unsigned int totedge_final = 0;
+       unsigned int edge_index;
+
+       /* we put all edges in array, sort them, and detect doubles that way */
+
+       for (a = totface, mface = allface; a > 0; a--, mface++) {
+               if (mface->v4) totedge += 4;
+               else if (mface->v3) totedge += 3;
+               else totedge += 1;
+       }
+
+       if (totedge == 0) {
+               /* flag that mesh has edges */
+               (*r_medge) = MEM_callocN(0, __func__);
+               (*r_totedge) = 0;
+               return;
+       }
+
+       ed = edsort = MEM_mallocN(totedge * sizeof(struct EdgeSort), "EdgeSort");
+
+       for (a = totface, mface = allface; a > 0; a--, mface++) {
+               to_edgesort(ed++, mface->v1, mface->v2, !mface->v3, mface->edcode & ME_V1V2);
+               if (mface->v4) {
+                       to_edgesort(ed++, mface->v2, mface->v3, 0, mface->edcode & ME_V2V3);
+                       to_edgesort(ed++, mface->v3, mface->v4, 0, mface->edcode & ME_V3V4);
+                       to_edgesort(ed++, mface->v4, mface->v1, 0, mface->edcode & ME_V4V1);
+               }
+               else if (mface->v3) {
+                       to_edgesort(ed++, mface->v2, mface->v3, 0, mface->edcode & ME_V2V3);
+                       to_edgesort(ed++, mface->v3, mface->v1, 0, mface->edcode & ME_V3V1);
+               }
+       }
+
+       qsort(edsort, totedge, sizeof(struct EdgeSort), vergedgesort);
+
+       /* count final amount */
+       for (a = totedge, ed = edsort; a > 1; a--, ed++) {
+               /* edge is unique when it differs from next edge, or is last */
+               if (ed->v1 != (ed + 1)->v1 || ed->v2 != (ed + 1)->v2) totedge_final++;
+       }
+       totedge_final++;
+
+       medge = MEM_callocN(sizeof(MEdge) * totedge_final, __func__);
+
+       for (a = totedge, med = medge, ed = edsort; a > 1; a--, ed++) {
+               /* edge is unique when it differs from next edge, or is last */
+               if (ed->v1 != (ed + 1)->v1 || ed->v2 != (ed + 1)->v2) {
+                       med->v1 = ed->v1;
+                       med->v2 = ed->v2;
+                       if (use_old == false || ed->is_draw) med->flag = ME_EDGEDRAW | ME_EDGERENDER;
+                       if (ed->is_loose) med->flag |= ME_LOOSEEDGE;
+
+                       /* order is swapped so extruding this edge as a surface wont flip face normals
+                        * with cyclic curves */
+                       if (ed->v1 + 1 != ed->v2) {
+                               SWAP(unsigned int, med->v1, med->v2);
+                       }
+                       med++;
+               }
+               else {
+                       /* equal edge, we merge the drawflag */
+                       (ed + 1)->is_draw |= ed->is_draw;
+               }
+       }
+       /* last edge */
+       med->v1 = ed->v1;
+       med->v2 = ed->v2;
+       med->flag = ME_EDGEDRAW;
+       if (ed->is_loose) med->flag |= ME_LOOSEEDGE;
+       med->flag |= ME_EDGERENDER;
+
+       MEM_freeN(edsort);
+
+       /* set edge members of mloops */
+       hash = BLI_edgehash_new_ex(__func__, totedge_final);
+       for (edge_index = 0, med = medge; edge_index < totedge_final; edge_index++, med++) {
+               BLI_edgehash_insert(hash, med->v1, med->v2, SET_UINT_IN_POINTER(edge_index));
+       }
+
+       mpoly = allpoly;
+       for (a = 0; a < totpoly; a++, mpoly++) {
+               MLoop *ml, *ml_next;
+               int i = mpoly->totloop;
+
+               ml_next = allloop + mpoly->loopstart;  /* first loop */
+               ml = &ml_next[i - 1];                  /* last loop */
+
+               while (i-- != 0) {
+                       ml->e = GET_UINT_FROM_POINTER(BLI_edgehash_lookup(hash, ml->v, ml_next->v));
+                       ml = ml_next;
+                       ml_next++;
+               }
+       }
+
+       BLI_edgehash_free(hash, NULL);
+
+       *r_medge = medge;
+       *r_totedge = totedge_final;
+}
+
+/**
+ * If the mesh is from a very old blender version,
+ * convert mface->edcode to edge drawflags
+ */
+void BKE_mesh_calc_edges_legacy(Mesh *me, const bool use_old)
+{
+       MEdge *medge;
+       int totedge = 0;
+
+       mesh_calc_edges_mdata(me->mvert, me->mface, me->mloop, me->mpoly,
+                             me->totvert, me->totface, me->totloop, me->totpoly,
+                             use_old, &medge, &totedge);
+
+       if (totedge == 0) {
+               /* flag that mesh has edges */
+               me->medge = medge;
+               me->totedge = 0;
+               return;
+       }
+
+       medge = CustomData_add_layer(&me->edata, CD_MEDGE, CD_ASSIGN, medge, totedge);
+       me->medge = medge;
+       me->totedge = totedge;
+
+       BKE_mesh_strip_loose_faces(me);
+}
+
 
 /**
  * Calculate edges from polygons
@@ -1055,3 +1393,4 @@ void BKE_mesh_calc_edges(Mesh *mesh, bool update, const bool select)
 
        BLI_edgehash_free(eh, NULL);
 }
+/** \} */
index 32ca3ea6d5a5845e4270eba43fd6753bd81cdb25..4519a116946b067c5c1992a9038a0d1878475a18 100644 (file)
@@ -1645,6 +1645,11 @@ void multires_free(Multires *mr)
        }
 }
 
+typedef struct IndexNode {
+       struct IndexNode *next, *prev;
+       int index;
+} IndexNode;
+
 static void create_old_vert_face_map(ListBase **map, IndexNode **mem, const MultiresFace *mface,
                                      const int totvert, const int totface)
 {
index dad132f45dfd0484703b7475ff60212d866c598d..f32215dbf03c8e818d6a28057bbf4a99f65b2d55 100644 (file)
@@ -2089,7 +2089,7 @@ void blo_do_versions_pre250(FileData *fd, Library *lib, Main *main)
 
                for (me = main->mesh.first; me; me = me->id.next) {
                        if (!me->medge) {
-                               BKE_mesh_make_edges(me, 1);     /* 1 = use mface->edcode */
+                               BKE_mesh_calc_edges_legacy(me, true);  /* true = use mface->edcode */
                        }
                        else {
                                BKE_mesh_strip_loose_faces(me);