Subdiv: Initial implementation of topology cache

This commit makes it so OpenSubdiv's topology refiner is kept
in memory and reused for until topology changes. There are the
following modifications which causes topology refiner to become
invalid:

- Change in a mesh topology (for example, vertices, edges, and
  faces connectivity).
- Change in UV islands (adding new islands, merging them and
  so on),
- Change in UV smoothing options.
- Change in creases.
- Change in Catmull-Clark / Simple subdivisions.

The following limitations are known:

- CPU evaluator is not yet cached.
- UV islands topology is not checked.

The UV limitation is currently a stopper for making this cache
enabled by default.

source/blender/blenkernel/BKE_subdiv.h

@@ -79,6 +79,7 @@ typedef enum eSubdivStatsValue {
 	SUBDIV_STATS_EVALUATOR_REFINE,
 	SUBDIV_STATS_SUBDIV_TO_CCG,
 	SUBDIV_STATS_SUBDIV_TO_CCG_ELEMENTS,
+	SUBDIV_STATS_TOPOLOGY_COMPARE,
 
 	NUM_SUBDIV_STATS_VALUES,
 } eSubdivStatsValue;
@@ -102,6 +103,8 @@ typedef struct SubdivStats {
 			double subdiv_to_ccg_time;
 			/* Time spent on CCG elements evaluation/initialization. */
 			double subdiv_to_ccg_elements_time;
+			/* Time spent on CCG elements evaluation/initialization. */
+			double topology_compare_time;
 		};
 		double values_[NUM_SUBDIV_STATS_VALUES];
 	};
@@ -187,14 +190,37 @@ void BKE_subdiv_stats_end(SubdivStats *stats, eSubdivStatsValue value);
 
 void BKE_subdiv_stats_print(const SubdivStats *stats);
 
+/* ================================ SETTINGS ================================ */
+
+bool BKE_subdiv_settings_equal(const SubdivSettings *settings_a,
+                               const SubdivSettings *settings_b);
+
 /* ============================== CONSTRUCTION ============================== */
 
+/* Construct new subdivision surface descriptor, from scratch, using given
+ * settings and topology. */
 Subdiv *BKE_subdiv_new_from_converter(const SubdivSettings *settings,
                                       struct OpenSubdiv_Converter *converter);
-
 Subdiv *BKE_subdiv_new_from_mesh(const SubdivSettings *settings,
                                  const struct Mesh *mesh);
 
+/* Similar to above, but will not re-create descriptor if it was created for the
+ * same settings and topology.
+ * If settings or topology did change, the existing descriptor is freed and a
+ * new one is created from scratch.
+ *
+ * NOTE: It is allowed to pass NULL as an existing subdivision surface
+ * descriptor. This will create enw descriptor without any extra checks.
+ */
+Subdiv *BKE_subdiv_update_from_converter(
+        Subdiv *subdiv,
+        const SubdivSettings *settings,
+        struct OpenSubdiv_Converter *converter);
+Subdiv *BKE_subdiv_update_from_mesh(
+        Subdiv *subdiv,
+        const SubdivSettings *settings,
+        const struct Mesh *mesh);
+
 void BKE_subdiv_free(Subdiv *subdiv);
 
 /* ============================ DISPLACEMENT API ============================ */

source/blender/blenkernel/intern/subdiv.c

@@ -66,8 +66,25 @@ BKE_subdiv_fvar_interpolation_from_uv_smooth(int uv_smooth)
 	return SUBDIV_FVAR_LINEAR_INTERPOLATION_ALL;
 }
 
+/* ================================ SETTINGS ================================ */
+
+bool BKE_subdiv_settings_equal(const SubdivSettings *settings_a,
+                               const SubdivSettings *settings_b)
+{
+	return
+	        (settings_a->is_simple == settings_b->is_simple &&
+	         settings_a->is_adaptive == settings_b->is_adaptive &&
+	         settings_a->level == settings_b->level &&
+	         settings_a->vtx_boundary_interpolation ==
+	                 settings_b->vtx_boundary_interpolation &&
+	         settings_a->fvar_linear_interpolation ==
+	                 settings_b->fvar_linear_interpolation);
+}
+
 /* ============================== CONSTRUCTION ============================== */
 
+/* Creation from scratch. */
+
 Subdiv *BKE_subdiv_new_from_converter(const SubdivSettings *settings,
                                       struct OpenSubdiv_Converter *converter)
 {
@@ -82,7 +99,6 @@ Subdiv *BKE_subdiv_new_from_converter(const SubdivSettings *settings,
 		osd_topology_refiner =
 		        openSubdiv_createTopologyRefinerFromConverter(
 		                converter, &topology_refiner_settings);
-
 	}
 	else {
 		/* TODO(sergey): Check whether original geometry had any vertices.
@@ -112,6 +128,53 @@ Subdiv *BKE_subdiv_new_from_mesh(const SubdivSettings *settings,
 	return subdiv;
 }
 
+/* Creation with cached-aware semantic. */
+
+Subdiv *BKE_subdiv_update_from_converter(Subdiv *subdiv,
+                                         const SubdivSettings *settings,
+                                         OpenSubdiv_Converter *converter)
+{
+	/* Check if the existing descriptor can be re-used. */
+	bool can_reuse_subdiv = true;
+	if (subdiv != NULL && subdiv->topology_refiner != NULL) {
+		if (!BKE_subdiv_settings_equal(&subdiv->settings, settings)) {
+			can_reuse_subdiv = false;
+		}
+		else {
+			BKE_subdiv_stats_begin(
+			        &subdiv->stats, SUBDIV_STATS_TOPOLOGY_COMPARE);
+			can_reuse_subdiv = openSubdiv_topologyRefinerCompareWithConverter(
+			        subdiv->topology_refiner, converter);
+			BKE_subdiv_stats_end(
+			        &subdiv->stats, SUBDIV_STATS_TOPOLOGY_COMPARE);
+		}
+	}
+	else {
+		can_reuse_subdiv = false;
+	}
+	if (can_reuse_subdiv) {
+		return subdiv;
+	}
+	/* Create new subdiv. */
+	if (subdiv != NULL) {
+		BKE_subdiv_free(subdiv);
+	}
+	return BKE_subdiv_new_from_converter(settings, converter);
+}
+
+Subdiv *BKE_subdiv_update_from_mesh(Subdiv *subdiv,
+                                    const SubdivSettings *settings,
+                                    const Mesh *mesh)
+{
+	OpenSubdiv_Converter converter;
+	BKE_subdiv_converter_init_for_mesh(&converter, settings, mesh);
+	subdiv = BKE_subdiv_update_from_converter(subdiv, settings, &converter);
+	BKE_subdiv_converter_free(&converter);
+	return subdiv;
+}
+
+/* Memory release. */
+
 void BKE_subdiv_free(Subdiv *subdiv)
 {
 	if (subdiv->evaluator != NULL) {

source/blender/blenkernel/intern/subdiv_converter.h

@@ -33,8 +33,7 @@
 #include "BKE_subdiv.h"
 
 /* NOTE: Was initially used to get proper enumerator types, but this makes
- * it tricky to compile without OpenSubdiv.
- */
+ * it tricky to compile without OpenSubdiv. */
 /* #include "opensubdiv_converter_capi.h" */
 
 struct Mesh;
@@ -46,21 +45,18 @@ void BKE_subdiv_converter_init_for_mesh(struct OpenSubdiv_Converter *converter,
                                         const struct Mesh *mesh);
 
 /* NOTE: Frees converter data, but not converter itself. This means, that if
- * converter was allocated on heap, it is up to the user to free that memory.
- */
+ * converter was allocated on heap, it is up to the user to free that memory. */
 void BKE_subdiv_converter_free(struct OpenSubdiv_Converter *converter);
 
 /* ============================ INTERNAL HELPERS ============================ */
 
 /* TODO(sergey): Find a way to make it OpenSubdiv_VtxBoundaryInterpolation,
- * without breaking compilation without OpenSubdiv.
- */
+ * without breaking compilation without OpenSubdiv. */
 int BKE_subdiv_converter_vtx_boundary_interpolation_from_settings(
         const SubdivSettings *settings);
 
 /* TODO(sergey): Find a way to make it OpenSubdiv_FVarLinearInterpolation,
- * without breaking compilation without OpenSubdiv.
- */
+ * without breaking compilation without OpenSubdiv. */
 int BKE_subdiv_converter_fvar_linear_from_settings(
         const SubdivSettings *settings);
 

source/blender/blenkernel/intern/subdiv_stats.c

@@ -42,6 +42,7 @@ void BKE_subdiv_stats_init(SubdivStats *stats)
 	stats->evaluator_refine_time = 0.0;
 	stats->subdiv_to_ccg_time = 0.0;
 	stats->subdiv_to_ccg_elements_time = 0.0;
+	stats->topology_compare_time = 0.0;
 }
 
 void BKE_subdiv_stats_begin(SubdivStats *stats, eSubdivStatsValue value)
@@ -87,6 +88,9 @@ void BKE_subdiv_stats_print(const SubdivStats *stats)
 	STATS_PRINT_TIME(stats,
 	                 subdiv_to_ccg_elements_time,
 	                 "    Elements time");
+	STATS_PRINT_TIME(stats,
+	                 topology_compare_time,
+	                 "Topology comparison time");
 
 #undef STATS_PRINT_TIME
 }

source/blender/blenloader/intern/readfile.c

@@ -5073,6 +5073,7 @@ static void direct_link_modifiers(FileData *fd, ListBase *lb)
 			SubsurfModifierData *smd = (SubsurfModifierData *)md;
 
 			smd->emCache = smd->mCache = NULL;
+			smd->subdiv = NULL;
 		}
 		else if (md->type == eModifierType_Armature) {
 			ArmatureModifierData *amd = (ArmatureModifierData *)md;

source/blender/makesdna/DNA_modifier_types.h

@@ -34,6 +34,7 @@
 
 struct Mesh;
 struct Scene;
+struct Subdiv;
 
 typedef enum ModifierType {
 	eModifierType_None              = 0,
@@ -167,7 +168,10 @@ typedef struct SubsurfModifierData {
 	short quality;
 	short pad[2];
 
+	/* TODO(sergey): Get rid of those with the old CCG subdivision code. */
 	void *emCache, *mCache;
+	/* Cached subdivision surface descriptor, with topology and settings. */
+	struct Subdiv *subdiv;
 } SubsurfModifierData;
 
 typedef struct LatticeModifierData {

source/blender/modifiers/intern/MOD_subsurf.c

@@ -89,6 +89,9 @@ static void freeData(ModifierData *md)
 		ccgSubSurf_free(smd->emCache);
 		smd->emCache = NULL;
 	}
+	if (smd->subdiv != NULL) {
+		BKE_subdiv_free(smd->subdiv);
+	}
 }
 
 static bool isDisabled(const Scene *scene, ModifierData *md, bool useRenderParams)
@@ -122,6 +125,20 @@ static void subdiv_settings_init(SubdivSettings *settings,
 	        BKE_subdiv_fvar_interpolation_from_uv_smooth(smd->uv_smooth);
 }
 
+/* Main goal of this function is to give usable subdivision surface descriptor
+ * which matches settings and topology. */
+static Subdiv *subdiv_descriptor_ensure(SubsurfModifierData *smd,
+                                        const SubdivSettings *subdiv_settings,
+                                        const Mesh *mesh)
+{
+	Subdiv *subdiv = BKE_subdiv_update_from_mesh(
+	        smd->subdiv, subdiv_settings, mesh);
+	if (false) {
+		smd->subdiv = subdiv;
+	}
+	return subdiv;
+}
+
 /* Subdivide into fully qualified mesh. */
 
 static void subdiv_mesh_settings_init(SubdivToMeshSettings *settings,
@@ -189,24 +206,23 @@ static Mesh *applyModifier(ModifierData *md,
 	if (subdiv_settings.level == 0) {
 		return result;
 	}
-	/* TODO(sergey): Try to re-use subdiv when possible. */
-	Subdiv *subdiv = BKE_subdiv_new_from_mesh(&subdiv_settings, mesh);
+	Subdiv *subdiv = subdiv_descriptor_ensure(smd, &subdiv_settings, mesh);
 	if (subdiv == NULL) {
-		/* Happens on bad topology, ut also on empty input mesh. */
+		/* Happens on bad topology, but also on empty input mesh. */
 		return result;
 	}
 	/* TODO(sergey): Decide whether we ever want to use CCG for subsurf,
-	 * maybe when it is a last modifier in the stack?
-	 */
+	 * maybe when it is a last modifier in the stack? */
 	if (true) {
 		result = subdiv_as_mesh(smd, ctx, mesh, subdiv);
 	}
 	else {
 		result = subdiv_as_ccg(smd, ctx, mesh, subdiv);
 	}
-	/* TODO(sergey): Cache subdiv somehow. */
 	// BKE_subdiv_stats_print(&subdiv->stats);
-	BKE_subdiv_free(subdiv);
+	if (subdiv != smd->subdiv) {
+		BKE_subdiv_free(subdiv);
+	}
 	return result;
 }