Subsurf: Support subdivision of loose elements

Applies to vertices and edges. Biggest annoyance here is that OpenSubdiv's
topology converter expects that there is no loose geometry, otherwise it
is getting confused.

For now solution is to create some sort of mapping from real Mesh vertex
and edge index to a non-loose-index. Now the annoying part is that this
is an extra step to calculate before we can compare topology, meaning FPS
will not be as great as if we knew for sure that topology didn't change.

Loose edges subdivision is different from what it used to be with old
subdivision code, but probably nice feature now is that endpoints of loose
edges are stay at the coarse vertex locations. This allows to have things
like plane with hair strands, without need to duplicate edge vertices at
endpoints.

All this required some re-work of topology refiner creation, which is now
only passing edges and vertices which are adjacent to face. This is how
topology refiner is supposed to be used, and this is how its validator
also works. Vertices which are adjacent to loose edges are marked as
infinite sharp. This seems to be good-enough approximation for now. In the
future we might tweaks things a bit and push such vertices in average
direction of loose edges, to match old subdivision code closer.

1 files changed, 246 insertions, 84 deletions

diff --git a/source/blender/blenkernel/intern/subdiv_converter_mesh.c b/source/blender/blenkernel/intern/subdiv_converter_mesh.c
index 1a2c26b3564..50143dd46e1 100644
--- a/source/blender/blenkernel/intern/subdiv_converter_mesh.c
+++ b/source/blender/blenkernel/intern/subdiv_converter_mesh.c
@@ -31,6 +31,7 @@
 #include "DNA_meshdata_types.h"
 
 #include "BLI_utildefines.h"
+#include "BLI_bitmap.h"
 #include "BLI_math_vector.h"
 
 #include "BKE_customdata.h"
@@ -68,6 +69,26 @@ typedef struct ConverterStorage {
 	 */
 	int *loop_uv_indices;
 	int num_uv_coordinates;
+
+	/* Indexed by coarse mesh elements, gives index of corresponding element
+	 * with ignoring all non-manifold entities.
+	 *
+	 * NOTE: This isn't strictly speaking manifold, this is more like non-loose
+	 * geometry index. As in, index of element as if there were no loose edges
+	 * or vertices in the mesh.
+	 */
+	int *manifold_vertex_index;
+	int *manifold_edge_index;
+	/* Indexed by vertex index from mesh, corresponds to whether this vertex has
+	 * infinite sharpness due to non-manifol topology.
+	 */
+	BLI_bitmap *infinite_sharp_vertices_map;
+	/* Reverse mapping to above. */
+	int *manifold_vertex_index_reverse;
+	int *manifold_edge_index_reverse;
+	/* Number of non-loose elements. */
+	int num_manifold_vertices;
+	int num_manifold_edges;
 } ConverterStorage;
 
 static OpenSubdiv_SchemeType get_scheme_type(
@@ -98,70 +119,81 @@ static int get_num_faces(const OpenSubdiv_Converter *converter)
 static int get_num_edges(const OpenSubdiv_Converter *converter)
 {
 	ConverterStorage *storage = converter->user_data;
-	return storage->mesh->totedge;
+	return storage->num_manifold_edges;
 }
 
-static int get_num_verts(const OpenSubdiv_Converter *converter)
+static int get_num_vertices(const OpenSubdiv_Converter *converter)
 {
 	ConverterStorage *storage = converter->user_data;
-	return storage->mesh->totvert;
+	return storage->num_manifold_vertices;
 }
 
-static int get_num_face_verts(const OpenSubdiv_Converter *converter, int face)
+static int get_num_face_vertices(const OpenSubdiv_Converter *converter,
+                                 int manifold_face_index)
 {
 	ConverterStorage *storage = converter->user_data;
-	return storage->mesh->mpoly[face].totloop;
+	return storage->mesh->mpoly[manifold_face_index].totloop;
 }
 
-static void get_face_verts(const OpenSubdiv_Converter *converter,
-                           int face,
-                           int *face_verts)
+static void get_face_vertices(const OpenSubdiv_Converter *converter,
+                              int manifold_face_index,
+                              int *manifold_face_vertices)
 {
 	ConverterStorage *storage = converter->user_data;
-	const MPoly *mp = &storage->mesh->mpoly[face];
+	const MPoly *poly = &storage->mesh->mpoly[manifold_face_index];
 	const MLoop *mloop = storage->mesh->mloop;
-	for (int loop = 0; loop < mp->totloop; loop++) {
-		face_verts[loop] = mloop[mp->loopstart + loop].v;
+	for (int corner = 0; corner < poly->totloop; corner++) {
+		manifold_face_vertices[corner] = storage->manifold_vertex_index[
+		        mloop[poly->loopstart + corner].v];
 	}
 }
 
 static void get_face_edges(const OpenSubdiv_Converter *converter,
-                           int face,
-                           int *face_edges)
+                           int manifold_face_index,
+                           int *manifold_face_edges)
 {
 	ConverterStorage *storage = converter->user_data;
-	const MPoly *mp = &storage->mesh->mpoly[face];
+	const MPoly *poly = &storage->mesh->mpoly[manifold_face_index];
 	const MLoop *mloop = storage->mesh->mloop;
-	for (int loop = 0; loop < mp->totloop; loop++) {
-		face_edges[loop] = mloop[mp->loopstart + loop].e;
+	for (int corner = 0; corner < poly->totloop; corner++) {
+		manifold_face_edges[corner] =
+		        storage->manifold_edge_index[mloop[poly->loopstart + corner].e];
 	}
 }
 
-static void get_edge_verts(const OpenSubdiv_Converter *converter,
-                           int edge,
-                           int *edge_verts)
+static void get_edge_vertices(const OpenSubdiv_Converter *converter,
+                              int manifold_edge_index,
+                              int *manifold_edge_vertices)
 {
 	ConverterStorage *storage = converter->user_data;
-	const MEdge *me = &storage->mesh->medge[edge];
-	edge_verts[0] = me->v1;
-	edge_verts[1] = me->v2;
+	const int edge_index =
+	        storage->manifold_edge_index_reverse[manifold_edge_index];
+	const MEdge *edge = &storage->mesh->medge[edge_index];
+	manifold_edge_vertices[0] = storage->manifold_vertex_index[edge->v1];
+	manifold_edge_vertices[1] = storage->manifold_vertex_index[edge->v2];
 }
 
-static int get_num_edge_faces(const OpenSubdiv_Converter *converter, int edge)
+static int get_num_edge_faces(const OpenSubdiv_Converter *converter,
+                              int manifold_edge_index)
 {
 	ConverterStorage *storage = converter->user_data;
+	const int edge_index =
+	        storage->manifold_edge_index_reverse[manifold_edge_index];
 #ifdef USE_MESH_ELEMENT_MAPPING
-	return storage->edge_poly_map[edge].count;
+	return storage->edge_poly_map[edge_index].count;
 #else
 	const Mesh *mesh = storage->mesh;
 	const MPoly *mpoly = mesh->mpoly;
 	const MLoop *mloop = mesh->mloop;
 	int num = 0;
-	for (int poly = 0; poly < mesh->totpoly; poly++) {
-		const MPoly *mp = &mpoly[poly];
-		for (int loop = 0; loop < mp->totloop; loop++) {
-			const MLoop *ml = &mloop[mp->loopstart + loop];
-			if (ml->e == edge) {
+	for (int poly_index = 0; poly_index < mesh->totpoly; poly_index++) {
+		const MPoly *poly = &mpoly[poly_index];
+		for (int corner = 0; corner < poly->totloop; corner++) {
+			const MLoop *loop = &mloop[poly->loopstart + corner];
+			if (storage->manifold_edge_index[loop->e] == -1) {
+				continue;
+			}
+			if (loop->e == edge_index) {
 				++num;
 				break;
 			}
@@ -172,25 +204,30 @@ static int get_num_edge_faces(const OpenSubdiv_Converter *converter, int edge)
 }
 
 static void get_edge_faces(const OpenSubdiv_Converter *converter,
-                           int edge,
-                           int *edge_faces)
+                           int manifold_edge_index,
+                           int *manifold_edge_faces)
 {
 	ConverterStorage *storage = converter->user_data;
+	const int edge_index =
+	        storage->manifold_edge_index_reverse[manifold_edge_index];
 #ifdef USE_MESH_ELEMENT_MAPPING
-	memcpy(edge_faces,
-	       storage->edge_poly_map[edge].indices,
-	       sizeof(int) * storage->edge_poly_map[edge].count);
+	memcpy(manifold_edge_faces,
+	       storage->edge_poly_map[edge_index].indices,
+	       sizeof(int) * storage->edge_poly_map[edge_index].count);
 #else
 	const Mesh *mesh = storage->mesh;
 	const MPoly *mpoly = mesh->mpoly;
 	const MLoop *mloop = mesh->mloop;
 	int num = 0;
-	for (int poly = 0; poly < mesh->totpoly; poly++) {
-		const MPoly *mp = &mpoly[poly];
-		for (int loop = 0; loop < mpoly->totloop; loop++) {
-			const MLoop *ml = &mloop[mp->loopstart + loop];
-			if (ml->e == edge) {
-				edge_faces[num++] = poly;
+	for (int poly_index = 0; poly_index < mesh->totpoly; poly_index++) {
+		const MPoly *poly = &mpoly[poly_index];
+		for (int corner = 0; corner < mpoly->totloop; corner++) {
+			const MLoop *loop = &mloop[poly->loopstart + corner];
+			if (storage->manifold_edge_index[loop->e] == -1) {
+				continue;
+			}
+			if (loop->e == edge_index) {
+				manifold_edge_faces[num++] = poly_index;
 				break;
 			}
 		}
@@ -198,26 +235,46 @@ static void get_edge_faces(const OpenSubdiv_Converter *converter,
 #endif
 }
 
-static float get_edge_sharpness(const OpenSubdiv_Converter *converter, int edge)
+static float get_edge_sharpness(const OpenSubdiv_Converter *converter,
+                                int manifold_edge_index)
 {
 	ConverterStorage *storage = converter->user_data;
+	const int edge_index =
+	        storage->manifold_edge_index_reverse[manifold_edge_index];
 	const MEdge *medge = storage->mesh->medge;
-	const float edge_crease =  (float)medge[edge].crease / 255.0f;
+	const float edge_crease =  (float)medge[edge_index].crease / 255.0f;
 	return edge_crease * storage->settings.level;
 }
 
-static int get_num_vert_edges(const OpenSubdiv_Converter *converter, int vert)
+static int get_num_vertex_edges(const OpenSubdiv_Converter *converter,
+                                int manifold_vertex_index)
 {
 	ConverterStorage *storage = converter->user_data;
+	const int vertex_index =
+	        storage->manifold_vertex_index_reverse[manifold_vertex_index];
 #ifdef USE_MESH_ELEMENT_MAPPING
-	return storage->vert_edge_map[vert].count;
+	const int num_vertex_edges = storage->vert_edge_map[vertex_index].count;
+	int num_manifold_vertex_edges = 0;
+	for (int i = 0; i < num_vertex_edges; i++) {
+		const int edge_index = storage->vert_edge_map[vertex_index].indices[i];
+		const int manifold_edge_index =
+		        storage->manifold_edge_index[edge_index];
+		if (manifold_edge_index == -1) {
+			continue;
+		}
+		num_manifold_vertex_edges++;
+	}
+	return num_manifold_vertex_edges;
 #else
 	const Mesh *mesh = storage->mesh;
 	const MEdge *medge = mesh->medge;
 	int num = 0;
-	for (int edge = 0; edge < mesh->totedge; edge++) {
-		const MEdge *me = &medge[edge];
-		if (me->v1 == vert || me->v2 == vert) {
+	for (int edge_index = 0; edge_index < mesh->totedge; edge_index++) {
+		const MEdge *edge = &medge[edge_index];
+		if (storage->manifold_edge_index[edge_index] == -1) {
+			continue;
+		}
+		if (edge->v1 == vertex_index || edge->v2 == vertex_index) {
 			++num;
 		}
 	}
@@ -225,43 +282,61 @@ static int get_num_vert_edges(const OpenSubdiv_Converter *converter, int vert)
 #endif
 }
 
-static void get_vert_edges(const OpenSubdiv_Converter *converter,
-                           int vert,
-                           int *vert_edges)
+static void get_vertex_edges(const OpenSubdiv_Converter *converter,
+                             int manifold_vertex_index,
+                             int *manifold_vertex_edges)
 {
 	ConverterStorage *storage = converter->user_data;
+	const int vertex_index =
+	        storage->manifold_vertex_index_reverse[manifold_vertex_index];
 #ifdef USE_MESH_ELEMENT_MAPPING
-	memcpy(vert_edges,
-	       storage->vert_edge_map[vert].indices,
-	       sizeof(int) * storage->vert_edge_map[vert].count);
+	const int num_vertex_edges = storage->vert_edge_map[vertex_index].count;
+	int num_manifold_vertex_edges = 0;
+	for (int i = 0; i < num_vertex_edges; i++) {
+		const int edge_index = storage->vert_edge_map[vertex_index].indices[i];
+		const int manifold_edge_index =
+		        storage->manifold_edge_index[edge_index];
+		if (manifold_edge_index == -1) {
+			continue;
+		}
+		manifold_vertex_edges[num_manifold_vertex_edges] = manifold_edge_index;
+		num_manifold_vertex_edges++;
+	}
 #else
 	const Mesh *mesh = storage->mesh;
 	const MEdge *medge = mesh->medge;
 	int num = 0;
-	for (int edge = 0; edge < mesh->totedge; edge++) {
-		const MEdge *me = &medge[edge];
-		if (me->v1 == vert || me->v2 == vert) {
-			vert_edges[num++] = edge;
+	for (int edge_index = 0; edge_index < mesh->totedge; edge_index++) {
+		const MEdge *edge = &medge[edge_index];
+		if (storage->manifold_edge_index[edge_index] == -1) {
+			continue;
+		}
+		if (edge->v1 == vertex_index || edge->v2 == vertex_index) {
+			manifold_vertex_edges[num++] =
+			        storage->manifold_edge_index[edge_index];
 		}
 	}
 #endif
 }
 
-static int get_num_vert_faces(const OpenSubdiv_Converter *converter, int vert)
+static int get_num_vertex_faces(const OpenSubdiv_Converter *converter,
+                                int manifold_vertex_index)
 {
 	ConverterStorage *storage = converter->user_data;
+	const int vertex_index =
+	        storage->manifold_vertex_index_reverse[manifold_vertex_index];
 #ifdef USE_MESH_ELEMENT_MAPPING
-	return storage->vert_poly_map[vert].count;
+	return storage->vert_poly_map[vertex_index].count;
 #else
 	const Mesh *mesh = storage->mesh;
 	const MPoly *mpoly = mesh->mpoly;
 	const MLoop *mloop = mesh->mloop;
 	int num = 0;
-	for (int poly = 0; poly < mesh->totpoly; poly++) {
-		const MPoly *mp = &mpoly[poly];
-		for (int loop = 0; loop < mpoly->totloop; loop++) {
-			const MLoop *ml = &mloop[mp->loopstart + loop];
-			if (ml->v == vert) {
+	for (int poly_index = 0; poly_index < mesh->totpoly; poly_index++) {
+		const MPoly *poly = &mpoly[poly_index];
+		for (int corner = 0; corner < mpoly->totloop; corner++) {
+			const MLoop *loop = &mloop[poly->loopstart + corner];
+			if (loop->v == vertex_index) {
 				++num;
 				break;
 			}
@@ -271,26 +346,28 @@ static int get_num_vert_faces(const OpenSubdiv_Converter *converter, int vert)
 #endif
 }
 
-static void get_vert_faces(const OpenSubdiv_Converter *converter,
-                           int vert,
-                           int *vert_faces)
+static void get_vertex_faces(const OpenSubdiv_Converter *converter,
+                            int manifold_vertex_index,
+                            int *manifold_vertex_faces)
 {
 	ConverterStorage *storage = converter->user_data;
+	const int vertex_index =
+	        storage->manifold_vertex_index_reverse[manifold_vertex_index];
 #ifdef USE_MESH_ELEMENT_MAPPING
-	memcpy(vert_faces,
-	       storage->vert_poly_map[vert].indices,
-	       sizeof(int) * storage->vert_poly_map[vert].count);
+	memcpy(manifold_vertex_faces,
+	       storage->vert_poly_map[vertex_index].indices,
+	       sizeof(int) * storage->vert_poly_map[vertex_index].count);
 #else
 	const Mesh *mesh = storage->mesh;
 	const MPoly *mpoly = mesh->mpoly;
 	const MLoop *mloop = mesh->mloop;
 	int num = 0;
-	for (int poly = 0; poly < mesh->totpoly; poly++) {
-		const MPoly *mp = &mpoly[poly];
-		for (int loop = 0; loop < mpoly->totloop; loop++) {
-			const MLoop *ml = &mloop[mp->loopstart + loop];
-			if (ml->v == vert) {
-				vert_faces[num++] = poly;
+	for (int poly_index = 0; poly_index < mesh->totpoly; poly_index++) {
+		const MPoly *poly = &mpoly[poly_index];
+		for (int corner = 0; corner < mpoly->totloop; corner++) {
+			const MLoop *loop = &mloop[poly->loopstart + corner];
+			if (loop->v == vertex_index) {
+				manifold_vertex_faces[num++] = poly_index;
 				break;
 			}
 		}
@@ -298,6 +375,16 @@ static void get_vert_faces(const OpenSubdiv_Converter *converter,
 #endif
 }
 
+static bool is_infinite_sharp_vertex(const OpenSubdiv_Converter *converter,
+                                     int manifold_vertex_index)
+{
+	ConverterStorage *storage = converter->user_data;
+	const int vertex_index =
+	        storage->manifold_vertex_index_reverse[manifold_vertex_index];
+	return BLI_BITMAP_TEST_BOOL(storage->infinite_sharp_vertices_map,
+	                            vertex_index);
+}
+
 static int get_num_uv_layers(const OpenSubdiv_Converter *converter)
 {
 	ConverterStorage *storage = converter->user_data;
@@ -382,6 +469,11 @@ static void free_user_data(const OpenSubdiv_Converter *converter)
 	MEM_freeN(user_data->edge_poly_map);
 	MEM_freeN(user_data->edge_poly_mem);
 #endif
+	MEM_freeN(user_data->manifold_vertex_index);
+	MEM_freeN(user_data->manifold_edge_index);
+	MEM_freeN(user_data->infinite_sharp_vertices_map);
+	MEM_freeN(user_data->manifold_vertex_index_reverse);
+	MEM_freeN(user_data->manifold_edge_index_reverse);
 	MEM_freeN(user_data);
 }
 
@@ -393,21 +485,22 @@ static void init_functions(OpenSubdiv_Converter *converter)
 
 	converter->getNumFaces = get_num_faces;
 	converter->getNumEdges = get_num_edges;
-	converter->getNumVertices = get_num_verts;
+	converter->getNumVertices = get_num_vertices;
 
-	converter->getNumFaceVertices = get_num_face_verts;
-	converter->getFaceVertices = get_face_verts;
+	converter->getNumFaceVertices = get_num_face_vertices;
+	converter->getFaceVertices = get_face_vertices;
 	converter->getFaceEdges = get_face_edges;
 
-	converter->getEdgeVertices = get_edge_verts;
+	converter->getEdgeVertices = get_edge_vertices;
 	converter->getNumEdgeFaces = get_num_edge_faces;
 	converter->getEdgeFaces = get_edge_faces;
 	converter->getEdgeSharpness = get_edge_sharpness;
 
-	converter->getNumVertexEdges = get_num_vert_edges;
-	converter->getVertexEdges = get_vert_edges;
-	converter->getNumVertexFaces = get_num_vert_faces;
-	converter->getVertexFaces = get_vert_faces;
+	converter->getNumVertexEdges = get_num_vertex_edges;
+	converter->getVertexEdges = get_vertex_edges;
+	converter->getNumVertexFaces = get_num_vertex_faces;
+	converter->getVertexFaces = get_vertex_faces;
+	converter->isInfiniteSharpVertex = is_infinite_sharp_vertex;
 
 	converter->getNumUVLayers = get_num_uv_layers;
 	converter->precalcUVLayer = precalc_uv_layer;
@@ -444,6 +537,74 @@ static void create_element_maps_if_needed(ConverterStorage *storage)
 #endif
 }
 
+static void initialize_manifold_index_array(const BLI_bitmap *used_map,
+                                            const int num_elements,
+                                            int **indices_r,
+                                            int **indices_reverse_r,
+                                            int *num_manifold_elements_r)
+{
+	int *indices = MEM_malloc_arrayN(
+	        num_elements, sizeof(int), "manifold indices");
+	int *indices_reverse = MEM_malloc_arrayN(
+	        num_elements, sizeof(int), "manifold indices reverse");
+	int offset = 0;
+	for (int i = 0; i < num_elements; i++) {
+		if (BLI_BITMAP_TEST_BOOL(used_map, i)) {
+			indices[i] = i - offset;
+			indices_reverse[i - offset] = i;
+		}
+		else {
+			indices[i] = -1;
+			offset++;
+		}
+	}
+	*indices_r = indices;
+	*indices_reverse_r = indices_reverse;
+	*num_manifold_elements_r = num_elements - offset;
+}
+
+static void initialize_manifold_indices(ConverterStorage *storage)
+{
+	const Mesh *mesh = storage->mesh;
+	const MEdge *medge = mesh->medge;
+	const MLoop *mloop = mesh->mloop;
+	const MPoly *mpoly = mesh->mpoly;
+	/* Set bits of elements which are not loose. */
+	BLI_bitmap *vert_used_map = BLI_BITMAP_NEW(mesh->totvert, "vert used map");
+	BLI_bitmap *edge_used_map = BLI_BITMAP_NEW(mesh->totedge, "edge used map");
+	for (int poly_index = 0; poly_index < mesh->totpoly; poly_index++) {
+		const MPoly *poly = &mpoly[poly_index];
+		for (int corner = 0; corner < poly->totloop; corner++) {
+			const MLoop *loop = &mloop[poly->loopstart + corner];
+			BLI_BITMAP_ENABLE(vert_used_map, loop->v);
+			BLI_BITMAP_ENABLE(edge_used_map, loop->e);
+		}
+	}
+	initialize_manifold_index_array(vert_used_map,
+	                                mesh->totvert,
+	                                &storage->manifold_vertex_index,
+	                                &storage->manifold_vertex_index_reverse,
+	                                &storage->num_manifold_vertices);
+	initialize_manifold_index_array(edge_used_map,
+	                                mesh->totedge,
+	                                &storage->manifold_edge_index,
+	                                &storage->manifold_edge_index_reverse,
+	                                &storage->num_manifold_edges);
+	/* Initialize infinite sharp mapping. */
+	storage->infinite_sharp_vertices_map =
+	        BLI_BITMAP_NEW(mesh->totvert, "vert used map");
+	for (int edge_index = 0; edge_index < mesh->totedge; edge_index++) {
+		if (!BLI_BITMAP_TEST_BOOL(edge_used_map, edge_index)) {
+			const MEdge *edge = &medge[edge_index];
+			BLI_BITMAP_ENABLE(storage->infinite_sharp_vertices_map, edge->v1);
+			BLI_BITMAP_ENABLE(storage->infinite_sharp_vertices_map, edge->v2);
+		}
+	}
+	/* Free working variables. */
+	MEM_freeN(vert_used_map);
+	MEM_freeN(edge_used_map);
+}
+
 static void init_user_data(OpenSubdiv_Converter *converter,
                            const SubdivSettings *settings,
                            const Mesh *mesh)
@@ -454,6 +615,7 @@ static void init_user_data(OpenSubdiv_Converter *converter,
 	user_data->mesh = mesh;
 	user_data->loop_uv_indices = NULL;
 	create_element_maps_if_needed(user_data);
+	initialize_manifold_indices(user_data);
 	converter->user_data = user_data;
 }
 #endif