Reduce poly map memory usage (used by sculpt smooth brush.)

Changed the create_vert_poly_map function to return a more compact
structure. Memory saved will vary depending on the mesh, but typically
it should be about one third of the old size.

9 files changed, 83 insertions, 64 deletions

diff --git a/source/blender/blenkernel/BKE_DerivedMesh.h b/source/blender/blenkernel/BKE_DerivedMesh.h
index 0416e217168..e90646c72ee 100644
--- a/source/blender/blenkernel/BKE_DerivedMesh.h
+++ b/source/blender/blenkernel/BKE_DerivedMesh.h
@@ -301,7 +301,7 @@ struct DerivedMesh {
 
 	/* Get a map of vertices to faces
 	 */
-	struct ListBase *(*getPolyMap)(struct Object *ob, DerivedMesh *dm);
+	const struct MeshElemMap *(*getPolyMap)(struct Object *ob, DerivedMesh *dm);
 
 	/* Get the BVH used for paint modes
 	 */
diff --git a/source/blender/blenkernel/BKE_mesh.h b/source/blender/blenkernel/BKE_mesh.h
index 63d3a1f309a..c5d137b086f 100644
--- a/source/blender/blenkernel/BKE_mesh.h
+++ b/source/blender/blenkernel/BKE_mesh.h
@@ -251,13 +251,20 @@ UvMapVert *get_uv_map_vert(UvVertMap *vmap, unsigned int v);
 void free_uv_vert_map(UvVertMap *vmap);
 
 /* Connectivity data */
+typedef struct MeshElemMap {
+	int *indices;
+	int count;
+} MeshElemMap;
+	
 typedef struct IndexNode {
 	struct IndexNode *next, *prev;
 	int index;
 } IndexNode;
-void create_vert_poly_map(struct ListBase **map, IndexNode **mem,
-                          struct MPoly *mface, struct MLoop *mloop,
-                          const int totvert, const int totface, const int totloop);
+
+void create_vert_poly_map(MeshElemMap **map, int **mem,
+                          const struct MPoly *mface, const struct MLoop *mloop,
+                          int totvert, int totface, int totloop);
+	
 void create_vert_edge_map(struct ListBase **map, IndexNode **mem, const struct MEdge *medge,
                           const int totvert, const int totedge);
 
diff --git a/source/blender/blenkernel/BKE_paint.h b/source/blender/blenkernel/BKE_paint.h
index ff3e3c81724..acf39d83370 100644
--- a/source/blender/blenkernel/BKE_paint.h
+++ b/source/blender/blenkernel/BKE_paint.h
@@ -34,6 +34,7 @@
 
 struct Brush;
 struct MDisps;
+struct MeshElemMap;
 struct MFace;
 struct MultireModifierData;
 struct MVert;
@@ -80,7 +81,7 @@ typedef struct SculptSession {
 	struct KeyBlock *kb;
 	
 	/* Mesh connectivity */
-	struct ListBase *pmap;
+	const struct MeshElemMap *pmap;
 
 	/* PBVH acceleration structure */
 	struct PBVH *pbvh;
diff --git a/source/blender/blenkernel/BKE_subsurf.h b/source/blender/blenkernel/BKE_subsurf.h
index 10254545d3e..7f9881926a6 100644
--- a/source/blender/blenkernel/BKE_subsurf.h
+++ b/source/blender/blenkernel/BKE_subsurf.h
@@ -38,8 +38,7 @@ struct DMFlagMat;
 struct DMGridAdjacency;
 struct DMGridData;
 struct DerivedMesh;
-struct IndexNode;
-struct ListBase;
+struct MeshElemMap;
 struct Mesh;
 struct MPoly;
 struct MultiresSubsurf;
@@ -105,11 +104,9 @@ typedef struct CCGDerivedMesh {
 	int *reverseFaceMap;
 
 	struct PBVH *pbvh;
-	struct ListBase *fmap;
-	struct IndexNode *fmap_mem;
 
-	struct ListBase *pmap;
-	struct IndexNode *pmap_mem;
+	struct MeshElemMap *pmap;
+	int *pmap_mem;
 
 	struct DMGridData **gridData;
 	struct DMGridAdjacency *gridAdjacency;
diff --git a/source/blender/blenkernel/intern/cdderivedmesh.c b/source/blender/blenkernel/intern/cdderivedmesh.c
index 54f7fc1e483..615d646a476 100644
--- a/source/blender/blenkernel/intern/cdderivedmesh.c
+++ b/source/blender/blenkernel/intern/cdderivedmesh.c
@@ -91,11 +91,8 @@ typedef struct {
 	int pbvh_draw;
 
 	/* Mesh connectivity */
-	struct ListBase *fmap;
-	struct IndexNode *fmap_mem;
-
-	struct ListBase *pmap;
-	struct IndexNode *pmap_mem;
+	MeshElemMap *pmap;
+	int *pmap_mem;
 } CDDerivedMesh;
 
 /**************** DerivedMesh interface functions ****************/
@@ -215,7 +212,7 @@ static void cdDM_getVertNo(DerivedMesh *dm, int index, float no_r[3])
 	normal_short_to_float_v3(no_r, cddm->mvert[index].no);
 }
 
-static ListBase *cdDM_getPolyMap(Object *ob, DerivedMesh *dm)
+const static MeshElemMap *cdDM_getPolyMap(Object *ob, DerivedMesh *dm)
 {
 	CDDerivedMesh *cddm = (CDDerivedMesh*) dm;
 
@@ -1530,9 +1527,6 @@ void CDDM_recalc_tessellation(DerivedMesh *dm)
 
 static void cdDM_free_internal(CDDerivedMesh *cddm)
 {
-	if(cddm->fmap) MEM_freeN(cddm->fmap);
-	if(cddm->fmap_mem) MEM_freeN(cddm->fmap_mem);
-
 	if(cddm->pmap) MEM_freeN(cddm->pmap);
 	if(cddm->pmap_mem) MEM_freeN(cddm->pmap_mem);
 }
diff --git a/source/blender/blenkernel/intern/mesh.c b/source/blender/blenkernel/intern/mesh.c
index a824cd11c6a..253541ea20a 100644
--- a/source/blender/blenkernel/intern/mesh.c
+++ b/source/blender/blenkernel/intern/mesh.c
@@ -2189,25 +2189,49 @@ void free_uv_vert_map(UvVertMap *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 create_vert_poly_map(ListBase **map, IndexNode **mem,
-                          MPoly *mpoly, MLoop *mloop,
-                          const int totvert, const int totpoly, const int totloop)
+void create_vert_poly_map(MeshElemMap **map, int **mem,
+                          const MPoly *mpoly, const MLoop *mloop,
+                          int totvert, int totpoly, int totloop)
 {
-	int i,j;
-	IndexNode *node = NULL;
-	MPoly *mp;
-	MLoop *ml;
+	int i, j;
+	int *indices;
 
-	(*map) = MEM_callocN(sizeof(ListBase) * totvert, "vert face map");
-	(*mem) = MEM_callocN(sizeof(IndexNode) * totloop, "vert poly map mem");
-	node = *mem;
+	(*map) = MEM_callocN(sizeof(MeshElemMap) * totvert, "vert poly map");
+	(*mem) = MEM_mallocN(sizeof(int) * totloop, "vert poly map mem");
+
+	printf("pmap old=%f, new=%f\n",
+		   (sizeof(ListBase) * totvert +
+			sizeof(IndexNode) * totloop) / 1024.0f / 1024.0f,
+		   (sizeof(MeshElemMap) * totvert +
+			sizeof(int) * totloop) / 1024.0f / 1024.0f);
 
+	/* 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 */
+	indices = (*mem);
+	for (i = 0; i < totvert; i++) {
+		(*map)[i].indices = indices;
+		indices += (*map)[i].count;
+
+		/* Reset 'count' for use as index in last loop */
+		(*map)[i].count = 0;
+	}
+		
 	/* Find the users */
-	for (i = 0, mp = mpoly; i < totpoly; ++i, ++mp) {
-		ml = &mloop[mp->loopstart];
-		for (j = 0; j < mp->totloop; ++j, ++node, ++ml) {
-			node->index = i;
-			BLI_addtail(&(*map)[ml->v], node);
+	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++;
 		}
 	}
 }
diff --git a/source/blender/blenkernel/intern/multires.c b/source/blender/blenkernel/intern/multires.c
index a363d7ad72b..102f1cc335d 100644
--- a/source/blender/blenkernel/intern/multires.c
+++ b/source/blender/blenkernel/intern/multires.c
@@ -691,9 +691,9 @@ void multiresModifier_base_apply(MultiresModifierData *mmd, Object *ob)
 {
 	DerivedMesh *cddm, *dispdm, *origdm;
 	Mesh *me;
-	ListBase *pmap;
+	const MeshElemMap *pmap;
 	float (*origco)[3];
-	int i, j, offset, totlvl;
+	int i, j, k, offset, totlvl;
 
 	multires_force_update(ob);
 
@@ -727,22 +727,21 @@ void multiresModifier_base_apply(MultiresModifierData *mmd, Object *ob)
 		copy_v3_v3(origco[i], me->mvert[i].co);
 
 	for (i = 0; i < me->totvert; ++i) {
-		IndexNode *n;
 		float avg_no[3] = {0,0,0}, center[3] = {0,0,0}, push[3];
 		float dist;
 		int tot;
 
 		/* don't adjust verts not used by at least one poly */
-		if (!pmap[i].first)
+		if (!pmap[i].count)
 			continue;
 
 		/* find center */
-		for (n = pmap[i].first, tot = 0; n; n = n->next) {
-			const MPoly *p = &me->mpoly[n->index];
+		for (j = 0; j < pmap[i].count; j++) {
+			const MPoly *p = &me->mpoly[pmap[i].indices[j]];
 			
 			/* this double counts, not sure if that's bad or good */
-			for (j = 0; j < p->totloop; ++j) {
-				int vndx = me->mloop[p->loopstart + j].v;
+			for (k = 0; k < p->totloop; ++k) {
+				int vndx = me->mloop[p->loopstart + k].v;
 				if (vndx != i) {
 					add_v3_v3(center, origco[vndx]);
 					++tot;
@@ -752,8 +751,8 @@ void multiresModifier_base_apply(MultiresModifierData *mmd, Object *ob)
 		mul_v3_fl(center, 1.0f / tot);
 
 		/* find normal */
-		for (n = pmap[i].first; n; n = n->next) {
-			const MPoly *p = &me->mpoly[n->index];
+		for (j = 0; j < pmap[i].count; j++) {
+			const MPoly *p = &me->mpoly[pmap[i].indices[j]];
 			MPoly fake_poly;
 			MLoop *fake_loops;
 			float (*fake_co)[3];
@@ -766,15 +765,15 @@ void multiresModifier_base_apply(MultiresModifierData *mmd, Object *ob)
 			fake_loops = MEM_mallocN(sizeof(MLoop) * p->totloop, "fake_loops");
 			fake_co = MEM_mallocN(sizeof(float) * 3 * p->totloop, "fake_co");
 			
-			for (j = 0; j < p->totloop; ++j) {
-				int vndx = me->mloop[p->loopstart + j].v;
+			for (k = 0; k < p->totloop; ++k) {
+				int vndx = me->mloop[p->loopstart + k].v;
 				
-				fake_loops[j].v = j;
+				fake_loops[k].v = k;
 				
 				if (vndx == i)
-					copy_v3_v3(fake_co[j], center);
+					copy_v3_v3(fake_co[k], center);
 				else
-					copy_v3_v3(fake_co[j], origco[vndx]);
+					copy_v3_v3(fake_co[k], origco[vndx]);
 			}
 			
 			mesh_calc_poly_normal_coords(&fake_poly, fake_loops,
diff --git a/source/blender/blenkernel/intern/subsurf_ccg.c b/source/blender/blenkernel/intern/subsurf_ccg.c
index 46c52b76c9e..1c07e77ffad 100644
--- a/source/blender/blenkernel/intern/subsurf_ccg.c
+++ b/source/blender/blenkernel/intern/subsurf_ccg.c
@@ -2411,8 +2411,6 @@ static void ccgDM_release(DerivedMesh *dm)
 			MEM_freeN(ccgdm->gridHidden);
 		}
 		if(ccgdm->freeSS) ccgSubSurf_free(ccgdm->ss);
-		if(ccgdm->fmap) MEM_freeN(ccgdm->fmap);
-		if(ccgdm->fmap_mem) MEM_freeN(ccgdm->fmap_mem);
 		if(ccgdm->pmap) MEM_freeN(ccgdm->pmap);
 		if(ccgdm->pmap_mem) MEM_freeN(ccgdm->pmap_mem);
 		MEM_freeN(ccgdm->edgeFlags);
@@ -2790,7 +2788,7 @@ static BLI_bitmap *ccgDM_getGridHidden(DerivedMesh *dm)
 	return ccgdm->gridHidden;
 }
 
-static ListBase *ccgDM_getPolyMap(Object *ob, DerivedMesh *dm)
+const static MeshElemMap *ccgDM_getPolyMap(Object *ob, DerivedMesh *dm)
 {
 	CCGDerivedMesh *ccgdm= (CCGDerivedMesh*)dm;
 
diff --git a/source/blender/editors/sculpt_paint/sculpt.c b/source/blender/editors/sculpt_paint/sculpt.c
index 48c54b8c3a5..8e717312219 100644
--- a/source/blender/editors/sculpt_paint/sculpt.c
+++ b/source/blender/editors/sculpt_paint/sculpt.c
@@ -904,28 +904,27 @@ static void calc_sculpt_normal(Sculpt *sd, Object *ob, float an[3], PBVHNode **n
  * polygon.) */
 static void neighbor_average(SculptSession *ss, float avg[3], unsigned vert)
 {
-	const int ncount = BLI_countlist(&ss->pmap[vert]);
+	const MeshElemMap *vert_map = &ss->pmap[vert];
 	const MVert *mvert = ss->mvert;
 	float (*deform_co)[3] = ss->deform_cos;
 
 	zero_v3(avg);
 		
 	/* Don't modify corner vertices */
-	if(ncount != 1) {
-		IndexNode *node;
-		int total = 0;
+	if(vert_map->count > 1) {
+		int i, total = 0;
 
-		for(node = ss->pmap[vert].first; node; node = node->next) {
-			const MPoly *p= &ss->mpoly[node->index];
+		for(i = 0; i < vert_map->count; i++) {
+			const MPoly *p= &ss->mpoly[vert_map->indices[i]];
 			unsigned f_adj_v[3];
 
 			if(poly_get_adj_loops_from_vert(f_adj_v, p, ss->mloop, vert) != -1) {
-				int i;
+				int j;
 			
-				for (i = 0; i < 3; i++) {
-					if (ncount != 2 || BLI_countlist(&ss->pmap[f_adj_v[i]]) <= 2) {
-						add_v3_v3(avg, deform_co ? deform_co[f_adj_v[i]] :
-												       mvert[f_adj_v[i]].co);
+				for (j = 0; j < 3; j++) {
+					if (vert_map->count != 2 || ss->pmap[f_adj_v[j]].count <= 2) {
+						add_v3_v3(avg, deform_co ? deform_co[f_adj_v[j]] :
+								                   mvert[f_adj_v[j]].co);
 
 						total++;
 					}