move bmesh array lookup data and utility functions from editmesh into bmesh,

since enough bmesh operations can also take advantage of direct index lookups on verts/edges/faces.

developers note:
- EDBM_index_arrays_init/ensure/free -> BM_mesh_elem_table_ensure/init/free
- EDBM_vert/edge/face_at_index -> BM_vert/edge/face_at_index
- EDBM_uv_element_map_create/free -> BM_uv_element_map_create/free
- ED_uv_element_get -> BM_uv_element_get

3 files changed, 206 insertions, 20 deletions

diff --git a/source/blender/bmesh/intern/bmesh_core.c b/source/blender/bmesh/intern/bmesh_core.c
index 8441a6ec75f..0726af4b641 100644
--- a/source/blender/bmesh/intern/bmesh_core.c
+++ b/source/blender/bmesh/intern/bmesh_core.c
@@ -70,7 +70,9 @@ BMVert *BM_vert_create(BMesh *bm, const float co[3],
 	/* disallow this flag for verts - its meaningless */
 	BLI_assert((create_flag & BM_CREATE_NO_DOUBLE) == 0);
 
-	bm->elem_index_dirty |= BM_VERT; /* may add to middle of the pool */
+	/* may add to middle of the pool */
+	bm->elem_index_dirty |= BM_VERT;
+	bm->elem_table_dirty |= BM_VERT;
 
 	bm->totvert++;
 
@@ -130,7 +132,9 @@ BMEdge *BM_edge_create(BMesh *bm, BMVert *v1, BMVert *v2,
 	BM_elem_index_set(e, -1); /* set_ok_invalid */
 #endif
 
-	bm->elem_index_dirty |= BM_EDGE; /* may add to middle of the pool */
+	/* may add to middle of the pool */
+	bm->elem_index_dirty |= BM_EDGE;
+	bm->elem_table_dirty |= BM_EDGE;
 
 	bm->totedge++;
 
@@ -292,7 +296,9 @@ BLI_INLINE BMFace *bm_face_create__internal(BMesh *bm, const eBMCreateFlag creat
 	BM_elem_index_set(f, -1); /* set_ok_invalid */
 #endif
 
-	bm->elem_index_dirty |= BM_FACE; /* may add to middle of the pool */
+	/* may add to middle of the pool */
+	bm->elem_index_dirty |= BM_FACE;
+	bm->elem_table_dirty |= BM_FACE;
 
 	bm->totface++;
 
@@ -562,6 +568,7 @@ static void bm_kill_only_vert(BMesh *bm, BMVert *v)
 {
 	bm->totvert--;
 	bm->elem_index_dirty |= BM_VERT;
+	bm->elem_table_dirty |= BM_VERT;
 
 	BM_select_history_remove(bm, v);
 
@@ -582,6 +589,7 @@ static void bm_kill_only_edge(BMesh *bm, BMEdge *e)
 {
 	bm->totedge--;
 	bm->elem_index_dirty |= BM_EDGE;
+	bm->elem_table_dirty |= BM_EDGE;
 
 	BM_select_history_remove(bm, (BMElem *)e);
 
@@ -605,6 +613,7 @@ static void bm_kill_only_face(BMesh *bm, BMFace *f)
 
 	bm->totface--;
 	bm->elem_index_dirty |= BM_FACE;
+	bm->elem_table_dirty |= BM_FACE;
 
 	BM_select_history_remove(bm, (BMElem *)f);
 
diff --git a/source/blender/bmesh/intern/bmesh_mesh.c b/source/blender/bmesh/intern/bmesh_mesh.c
index d6d846e44e4..033a31daae7 100644
--- a/source/blender/bmesh/intern/bmesh_mesh.c
+++ b/source/blender/bmesh/intern/bmesh_mesh.c
@@ -213,6 +213,10 @@ void BM_mesh_data_free(BMesh *bm)
 	BLI_mempool_destroy(bm->lpool);
 	BLI_mempool_destroy(bm->fpool);
 
+	if (bm->vtable) MEM_freeN(bm->vtable);
+	if (bm->etable) MEM_freeN(bm->etable);
+	if (bm->ftable) MEM_freeN(bm->ftable);
+
 	/* destroy flag pool */
 	BM_mesh_elem_toolflags_clear(bm);
 
@@ -623,6 +627,179 @@ void BM_mesh_elem_index_validate(BMesh *bm, const char *location, const char *fu
 
 }
 
+/* debug check only - no need to optimize */
+#ifndef NDEBUG
+bool BM_mesh_elem_table_check(BMesh *bm)
+{
+	BMIter iter;
+	BMElem *ele;
+	int i;
+
+	if (bm->vtable && ((bm->elem_table_dirty & BM_VERT) == 0)) {
+		BM_ITER_MESH_INDEX (ele, &iter, bm, BM_VERTS_OF_MESH, i) {
+			if (ele != (BMElem *)bm->vtable[i]) {
+				return false;
+			}
+		}
+	}
+
+	if (bm->etable && ((bm->elem_table_dirty & BM_EDGE) == 0)) {
+		BM_ITER_MESH_INDEX (ele, &iter, bm, BM_EDGES_OF_MESH, i) {
+			if (ele != (BMElem *)bm->etable[i]) {
+				return false;
+			}
+		}
+	}
+
+	if (bm->ftable && ((bm->elem_table_dirty & BM_FACE) == 0)) {
+		BM_ITER_MESH_INDEX (ele, &iter, bm, BM_FACES_OF_MESH, i) {
+			if (ele != (BMElem *)bm->ftable[i]) {
+				return false;
+			}
+		}
+	}
+
+	return true;
+}
+#endif
+
+
+
+void BM_mesh_elem_table_ensure(BMesh *bm, const char htype)
+{
+	/* assume if the array is non-null then its valid and no need to recalc */
+	const char htype_needed = (((bm->vtable && ((bm->elem_table_dirty & BM_VERT) == 0)) ? 0 : BM_VERT) |
+	                           ((bm->etable && ((bm->elem_table_dirty & BM_EDGE) == 0)) ? 0 : BM_EDGE) |
+	                           ((bm->ftable && ((bm->elem_table_dirty & BM_FACE) == 0)) ? 0 : BM_FACE)) & htype;
+
+	BLI_assert((htype & ~BM_ALL_NOLOOP) == 0);
+
+	/* in debug mode double check we didn't need to recalculate */
+	BLI_assert(BM_mesh_elem_table_check(bm) == true);
+
+	if (htype_needed & BM_VERT) {
+		if (bm->vtable && bm->totvert <= bm->vtable_tot && bm->totvert * 2 >= bm->vtable_tot) {
+			/* pass (re-use the array) */
+		}
+		else {
+			if (bm->vtable)
+				MEM_freeN(bm->vtable);
+			bm->vtable = MEM_mallocN(sizeof(void **) * bm->totvert, "bm->vtable");
+			bm->vtable_tot = bm->totvert;
+		}
+		bm->elem_table_dirty &= ~BM_VERT;
+	}
+	if (htype_needed & BM_EDGE) {
+		if (bm->etable && bm->totedge <= bm->etable_tot && bm->totedge * 2 >= bm->etable_tot) {
+			/* pass (re-use the array) */
+		}
+		else {
+			if (bm->etable)
+				MEM_freeN(bm->etable);
+			bm->etable = MEM_mallocN(sizeof(void **) * bm->totedge, "bm->etable");
+			bm->etable_tot = bm->totedge;
+		}
+		bm->elem_table_dirty &= ~BM_EDGE;
+	}
+	if (htype_needed & BM_FACE) {
+		if (bm->ftable && bm->totface <= bm->ftable_tot && bm->totface * 2 >= bm->ftable_tot) {
+			/* pass (re-use the array) */
+		}
+		else {
+			if (bm->ftable)
+				MEM_freeN(bm->ftable);
+			bm->ftable = MEM_mallocN(sizeof(void **) * bm->totface, "bm->ftable");
+			bm->ftable_tot = bm->totface;
+		}
+		bm->elem_table_dirty &= ~BM_FACE;
+	}
+
+#pragma omp parallel sections if (bm->totvert + bm->totedge + bm->totface >= BM_OMP_LIMIT)
+	{
+#pragma omp section
+		{
+			if (htype_needed & BM_VERT) {
+				BM_iter_as_array(bm, BM_VERTS_OF_MESH, NULL, (void **)bm->vtable, bm->totvert);
+			}
+		}
+#pragma omp section
+		{
+			if (htype_needed & BM_EDGE) {
+				BM_iter_as_array(bm, BM_EDGES_OF_MESH, NULL, (void **)bm->etable, bm->totedge);
+			}
+		}
+#pragma omp section
+		{
+			if (htype_needed & BM_FACE) {
+				BM_iter_as_array(bm, BM_FACES_OF_MESH, NULL, (void **)bm->ftable, bm->totface);
+			}
+		}
+	}
+}
+
+/* use BM_mesh_elem_table_ensure where possible to avoid full rebuild */
+void BM_mesh_elem_table_init(BMesh *bm, const char htype)
+{
+	BLI_assert((htype & ~BM_ALL_NOLOOP) == 0);
+
+	/* force recalc */
+	BM_mesh_elem_table_free(bm, BM_ALL_NOLOOP);
+	BM_mesh_elem_table_ensure(bm, htype);
+}
+
+void BM_mesh_elem_table_free(BMesh *bm, const char htype)
+{
+	if (htype & BM_VERT) {
+		MEM_SAFE_FREE(bm->vtable);
+	}
+
+	if (htype & BM_EDGE) {
+		MEM_SAFE_FREE(bm->etable);
+	}
+
+	if (htype & BM_FACE) {
+		MEM_SAFE_FREE(bm->ftable);
+	}
+}
+
+BMVert *BM_vert_at_index(BMesh *bm, int index)
+{
+	BLI_assert((index >= 0) && (index < bm->totvert));
+	BLI_assert((bm->elem_table_dirty & BM_VERT) == 0);
+	return bm->vtable[index];
+}
+
+BMEdge *BM_edge_at_index(BMesh *bm, int index)
+{
+	BLI_assert((index >= 0) && (index < bm->totedge));
+	BLI_assert((bm->elem_table_dirty & BM_EDGE) == 0);
+	return bm->etable[index];
+}
+
+BMFace *BM_face_at_index(BMesh *bm, int index)
+{
+	BLI_assert((index >= 0) && (index < bm->totface));
+	BLI_assert((bm->elem_table_dirty & BM_FACE) == 0);
+	return bm->ftable[index];
+}
+
+
+BMVert *BM_vert_at_index_find(BMesh *bm, const int index)
+{
+	return BLI_mempool_findelem(bm->vpool, index);
+}
+
+BMEdge *BM_edge_at_index_find(BMesh *bm, const int index)
+{
+	return BLI_mempool_findelem(bm->epool, index);
+}
+
+BMFace *BM_face_at_index_find(BMesh *bm, const int index)
+{
+	return BLI_mempool_findelem(bm->fpool, index);
+}
+
+
 /**
  * Return the amount of element of type 'type' in a given bmesh.
  */
@@ -828,18 +1005,3 @@ void BM_mesh_remap(BMesh *bm, int *vert_idx, int *edge_idx, int *face_idx)
 	if (fptr_map)
 		BLI_ghash_free(fptr_map, NULL, NULL);
 }
-
-BMVert *BM_vert_at_index_find(BMesh *bm, const int index)
-{
-	return BLI_mempool_findelem(bm->vpool, index);
-}
-
-BMEdge *BM_edge_at_index_find(BMesh *bm, const int index)
-{
-	return BLI_mempool_findelem(bm->epool, index);
-}
-
-BMFace *BM_face_at_index_find(BMesh *bm, const int index)
-{
-	return BLI_mempool_findelem(bm->fpool, index);
-}
diff --git a/source/blender/bmesh/intern/bmesh_mesh.h b/source/blender/bmesh/intern/bmesh_mesh.h
index 23429ec3252..33431714660 100644
--- a/source/blender/bmesh/intern/bmesh_mesh.h
+++ b/source/blender/bmesh/intern/bmesh_mesh.h
@@ -45,14 +45,29 @@ void bmesh_edit_end(BMesh *bm, const BMOpTypeFlag type_flag);
 void BM_mesh_elem_index_ensure(BMesh *bm, const char hflag);
 void BM_mesh_elem_index_validate(BMesh *bm, const char *location, const char *func,
                                  const char *msg_a, const char *msg_b);
-int  BM_mesh_elem_count(BMesh *bm, const char htype);
 
-void BM_mesh_remap(BMesh *bm, int *vert_idx, int *edge_idx, int *face_idx);
+#ifndef NDEBUG
+bool BM_mesh_elem_table_check(BMesh *em);
+#endif
+
+void           BM_mesh_elem_table_ensure(BMesh *bm, const char htype);
+void           BM_mesh_elem_table_init(BMesh *bm, const char htype);
+void           BM_mesh_elem_table_free(BMesh *bm, const char htype);
+
+BMVert *BM_vert_at_index(BMesh *bm, const int index);
+BMEdge *BM_edge_at_index(BMesh *bm, const int index);
+BMFace *BM_face_at_index(BMesh *bm, const int index);
 
 BMVert *BM_vert_at_index_find(BMesh *bm, const int index);
 BMEdge *BM_edge_at_index_find(BMesh *bm, const int index);
 BMFace *BM_face_at_index_find(BMesh *bm, const int index);
 
+// XXX
+
+int  BM_mesh_elem_count(BMesh *bm, const char htype);
+
+void BM_mesh_remap(BMesh *bm, int *vert_idx, int *edge_idx, int *face_idx);
+
 typedef struct BMAllocTemplate {
 	int totvert, totedge, totloop, totface;
 } BMAllocTemplate;