[Bf-blender-cvs] [d3aafbddd9e] blender2.8: Subdiv: CCG, store vertex adjacency information
Sergey Sharybin
noreply at git.blender.org
Thu Sep 20 16:11:32 CEST 2018
Commit: d3aafbddd9e44438c3a95f8e92b3870dfa5f7eb5
Author: Sergey Sharybin
Date: Thu Sep 20 14:01:35 2018 +0200
Branches: blender2.8
https://developer.blender.org/rBd3aafbddd9e44438c3a95f8e92b3870dfa5f7eb5
Subdiv: CCG, store vertex adjacency information
Similar to previous commit, but for vertices.
===================================================================
M source/blender/blenkernel/BKE_subdiv_ccg.h
M source/blender/blenkernel/intern/subdiv_ccg.c
===================================================================
diff --git a/source/blender/blenkernel/BKE_subdiv_ccg.h b/source/blender/blenkernel/BKE_subdiv_ccg.h
index f8dbd2092f1..ac90c5f7db3 100644
--- a/source/blender/blenkernel/BKE_subdiv_ccg.h
+++ b/source/blender/blenkernel/BKE_subdiv_ccg.h
@@ -79,6 +79,16 @@ typedef struct SubdivCCGAdjacentEdge {
struct CCGElem ***boundary_elements;
} SubdivCCGAdjacentEdge;
+/* Definition of a vertex which is adjacent to at least one of the faces. */
+typedef struct SubdivCCGAdjacentVertex {
+ int num_adjacent_faces;
+ /* Indexed by adjacent face index. */
+ SubdivCCGFace **faces;
+ /* Indexed by adjacent face index, points to a grid element.
+ */
+ struct CCGElem **corner_elements;
+} SubdivCCGAdjacentVertex;
+
/* Representation of subdivision surface which uses CCG grids. */
typedef struct SubdivCCG {
/* This is a subdivision surface this CCG was created for.
@@ -140,6 +150,12 @@ typedef struct SubdivCCG {
int num_adjacent_edges;
SubdivCCGAdjacentEdge *adjacent_edges;
+ /* Vertices which are adjacent to faces
+ * Used for faster grid stitching, in the cost of extra memory.
+ */
+ int num_adjacent_vertices;;
+ SubdivCCGAdjacentVertex *adjacent_vertices;
+
struct DMFlagMat *grid_flag_mats;
BLI_bitmap **grid_hidden;
diff --git a/source/blender/blenkernel/intern/subdiv_ccg.c b/source/blender/blenkernel/intern/subdiv_ccg.c
index 06ccffa4583..30766730819 100644
--- a/source/blender/blenkernel/intern/subdiv_ccg.c
+++ b/source/blender/blenkernel/intern/subdiv_ccg.c
@@ -434,10 +434,8 @@ static CCGElem **subdiv_ccg_adjacent_edge_add_face(
return adjacent_edge->boundary_elements[adjacent_face_index];
}
-static void subdiv_ccg_init_faces_neighborhood(SubdivCCG *subdiv_ccg)
+static void subdiv_ccg_init_faces_edge_neighborhood(SubdivCCG *subdiv_ccg)
{
-#define NUM_STATIC_EDGES 64
-
Subdiv *subdiv = subdiv_ccg->subdiv;
SubdivCCGFace *faces = subdiv_ccg->faces;
OpenSubdiv_TopologyRefiner *topology_refiner = subdiv->topology_refiner;
@@ -532,8 +530,92 @@ static void subdiv_ccg_init_faces_neighborhood(SubdivCCG *subdiv_ccg)
/* Free possibly heap-allocated storage. */
static_or_heap_storage_free(&face_vertices_storage);
static_or_heap_storage_free(&face_edges_storage);
+}
+
+static void subdiv_ccg_allocate_adjacent_vertices(SubdivCCG *subdiv_ccg,
+ const int num_vertices)
+{
+ subdiv_ccg->num_adjacent_vertices = num_vertices;
+ subdiv_ccg->adjacent_vertices = MEM_calloc_arrayN(
+ subdiv_ccg->num_adjacent_vertices,
+ sizeof(*subdiv_ccg->adjacent_vertices),
+ "ccg adjacent vertices");
+}
+
+/* Returns storage where corner elements are to be stored. This is a pointer
+ * to the actual storage.
+ */
+static CCGElem **subdiv_ccg_adjacent_vertex_add_face(
+ SubdivCCGAdjacentVertex *adjacent_vertex,
+ SubdivCCGFace *face)
+{
+ const int adjacent_face_index = adjacent_vertex->num_adjacent_faces;
+ ++adjacent_vertex->num_adjacent_faces;
+ /* Store new adjacent face. */
+ adjacent_vertex->faces = MEM_reallocN(
+ adjacent_vertex->faces,
+ adjacent_vertex->num_adjacent_faces *
+ sizeof(*adjacent_vertex->faces));
+ adjacent_vertex->faces[adjacent_face_index] = face;
+ /* Allocate memory for the boundary elements. */
+ adjacent_vertex->corner_elements = MEM_reallocN(
+ adjacent_vertex->corner_elements,
+ adjacent_vertex->num_adjacent_faces *
+ sizeof(*adjacent_vertex->corner_elements));
+ return &adjacent_vertex->corner_elements[adjacent_face_index];
+}
-#undef NUM_STATIC_EDGES
+static void subdiv_ccg_init_faces_vertex_neighborhood(SubdivCCG *subdiv_ccg)
+{
+ Subdiv *subdiv = subdiv_ccg->subdiv;
+ SubdivCCGFace *faces = subdiv_ccg->faces;
+ OpenSubdiv_TopologyRefiner *topology_refiner = subdiv->topology_refiner;
+ const int num_vertices =
+ topology_refiner->getNumVertices(topology_refiner);
+ const int grid_size = subdiv_ccg->grid_size;
+ if (num_vertices == 0) {
+ /* Early output, nothing to do in this case. */
+ return;
+ }
+ subdiv_ccg_allocate_adjacent_vertices(subdiv_ccg, num_vertices);
+ /* Initialize storage. */
+ StaticOrHeapIntStorage face_vertices_storage;
+ static_or_heap_storage_init(&face_vertices_storage);
+ /* Key to access elements. */
+ CCGKey key;
+ BKE_subdiv_ccg_key_top_level(&key, subdiv_ccg);
+ /* Store adjacency for all faces. */
+ const int num_faces = subdiv_ccg->num_faces;
+ for (int face_index = 0; face_index < num_faces; face_index++) {
+ SubdivCCGFace *face = &faces[face_index];
+ const int num_face_grids = face->num_grids;
+ const int num_face_edges = num_face_grids;
+ int *face_vertices = static_or_heap_storage_get(
+ &face_vertices_storage, num_face_edges);
+ topology_refiner->getFaceVertices(
+ topology_refiner, face_index, face_vertices);
+ for (int corner = 0; corner < num_face_edges; corner++) {
+ const int vertex_index = face_vertices[corner];
+ /* Grid which is adjacent to the current corner. */
+ const int grid_index = face->start_grid_index + corner;
+ CCGElem *grid = subdiv_ccg->grids[grid_index];
+ /* Add new face to the adjacent edge. */
+ SubdivCCGAdjacentVertex *adjacent_vertex =
+ &subdiv_ccg->adjacent_vertices[vertex_index];
+ CCGElem **corner_element = subdiv_ccg_adjacent_vertex_add_face(
+ adjacent_vertex, face);
+ *corner_element = CCG_grid_elem(
+ &key, grid, grid_size - 1, grid_size - 1);
+ }
+ }
+ /* Free possibly heap-allocated storage. */
+ static_or_heap_storage_free(&face_vertices_storage);
+}
+
+static void subdiv_ccg_init_faces_neighborhood(SubdivCCG *subdiv_ccg)
+{
+ subdiv_ccg_init_faces_edge_neighborhood(subdiv_ccg);
+ subdiv_ccg_init_faces_vertex_neighborhood(subdiv_ccg);
}
/* =============================================================================
@@ -605,6 +687,7 @@ void BKE_subdiv_ccg_destroy(SubdivCCG *subdiv_ccg)
}
MEM_SAFE_FREE(subdiv_ccg->faces);
MEM_SAFE_FREE(subdiv_ccg->grid_faces);
+ /* Free map of adjacent edges. */
for (int i = 0; i < subdiv_ccg->num_adjacent_edges; i++) {
SubdivCCGAdjacentEdge *adjacent_edge = &subdiv_ccg->adjacent_edges[i];
for (int face_index = 0;
@@ -617,6 +700,14 @@ void BKE_subdiv_ccg_destroy(SubdivCCG *subdiv_ccg)
MEM_SAFE_FREE(adjacent_edge->boundary_elements);
}
MEM_SAFE_FREE(subdiv_ccg->adjacent_edges);
+ /* Free map of adjacent vertices. */
+ for (int i = 0; i < subdiv_ccg->num_adjacent_vertices; i++) {
+ SubdivCCGAdjacentVertex *adjacent_vertex =
+ &subdiv_ccg->adjacent_vertices[i];
+ MEM_SAFE_FREE(adjacent_vertex->faces);
+ MEM_SAFE_FREE(adjacent_vertex->corner_elements);
+ }
+ MEM_SAFE_FREE(subdiv_ccg->adjacent_vertices);
MEM_freeN(subdiv_ccg);
}
More information about the Bf-blender-cvs
mailing list