diff options
author | Sergey Sharybin <sergey.vfx@gmail.com> | 2018-09-20 15:01:35 +0300 |
---|---|---|
committer | Sergey Sharybin <sergey.vfx@gmail.com> | 2018-09-20 16:39:41 +0300 |
commit | d3aafbddd9e44438c3a95f8e92b3870dfa5f7eb5 (patch) | |
tree | a70f61d002ae1c2d1c77e3799524d5f8315d1828 /source | |
parent | d511c7205675abdfbe83341aa6409af5d6dee625 (diff) |
Subdiv: CCG, store vertex adjacency information
Similar to previous commit, but for vertices.
Diffstat (limited to 'source')
-rw-r--r-- | source/blender/blenkernel/BKE_subdiv_ccg.h | 16 | ||||
-rw-r--r-- | source/blender/blenkernel/intern/subdiv_ccg.c | 99 |
2 files changed, 111 insertions, 4 deletions
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); } |