From 42cb1e3a2c4c708df4506b735d29b5841c07d960 Mon Sep 17 00:00:00 2001 From: Sergey Sharybin Date: Tue, 26 May 2020 10:54:46 +0200 Subject: OpenSubdiv: Optimize faces storage in mesh topology Avoid per-face pointer and allocation: store everything as continuous arrays. Memory footprint for 1.5M faces: - Theoretical worst case (all vertices and edges have crease) memory goes down from 114 MiB to 96 MiB (15% improvement). This case is not currently achievable since Blender does not expose vertex crease yet. - Current real life worst case (all edges have crease) memory goes down from 108 MiB to 90 MiB (17% improvement). - Best case (no creases at all) memory goes down from 96 MiB to 78 MiB (19% improvement). --- .../opensubdiv/internal/topology/mesh_topology.cc | 64 ++++++++++++++--- .../opensubdiv/internal/topology/mesh_topology.h | 81 +++++++++++++--------- .../internal/topology/mesh_topology_test.cc | 23 +++--- .../internal/topology/topology_refiner_factory.cc | 5 +- 4 files changed, 118 insertions(+), 55 deletions(-) diff --git a/intern/opensubdiv/internal/topology/mesh_topology.cc b/intern/opensubdiv/internal/topology/mesh_topology.cc index 5fb06744e83..4ff168cc508 100644 --- a/intern/opensubdiv/internal/topology/mesh_topology.cc +++ b/intern/opensubdiv/internal/topology/mesh_topology.cc @@ -183,7 +183,9 @@ void MeshTopology::setNumFaces(int num_faces) { num_faces_ = num_faces; - faces_.resize(num_faces); + // NOTE: Extra element to store fake face past the last real one to make it + // possible to calculate number of verticies in the last face. + faces_first_vertex_index_.resize(num_faces + 1, 0); } int MeshTopology::getNumFaces() const @@ -196,8 +198,8 @@ void MeshTopology::setNumFaceVertices(int face_index, int num_face_vertices) assert(face_index >= 0); assert(face_index < getNumFaces()); - Face &face = faces_[face_index]; - face.setNumVertices(num_face_vertices); + faces_first_vertex_index_[face_index + 1] = faces_first_vertex_index_[face_index] + + num_face_vertices; } int MeshTopology::getNumFaceVertices(int face_index) const @@ -205,27 +207,67 @@ int MeshTopology::getNumFaceVertices(int face_index) const assert(face_index >= 0); assert(face_index < getNumFaces()); - const Face &face = faces_[face_index]; - return face.getNumVertices(); + return faces_first_vertex_index_[face_index + 1] - faces_first_vertex_index_[face_index]; } -void MeshTopology::setFaceVertexIndices(int face_index, int *face_vertex_indices) +void MeshTopology::setFaceVertexIndices(int face_index, + int num_face_vertex_indices, + const int *face_vertex_indices) { assert(face_index >= 0); assert(face_index < getNumFaces()); + assert(num_face_vertex_indices == getNumFaceVertices(face_index)); - Face &face = faces_[face_index]; - face.setVertexIndices(face_vertex_indices); + int *face_vertex_indices_storage = getFaceVertexIndicesStorage(face_index); + memcpy(face_vertex_indices_storage, face_vertex_indices, sizeof(int) * num_face_vertex_indices); } bool MeshTopology::isFaceVertexIndicesEqual(int face_index, - const vector &expected_vertices_of_face) const + int num_expected_face_vertex_indices, + const int *expected_face_vertex_indices) const { assert(face_index >= 0); assert(face_index < getNumFaces()); - const Face &face = faces_[face_index]; - return face.vertex_indices == expected_vertices_of_face; + if (getNumFaceVertices(face_index) != num_expected_face_vertex_indices) { + return false; + } + + const int *face_vertex_indices_storage = getFaceVertexIndicesStorage(face_index); + return memcmp(face_vertex_indices_storage, + expected_face_vertex_indices, + sizeof(int) * num_expected_face_vertex_indices) == 0; +} + +bool MeshTopology::isFaceVertexIndicesEqual(int face_index, + const vector &expected_face_vertex_indices) const +{ + return isFaceVertexIndicesEqual( + face_index, expected_face_vertex_indices.size(), expected_face_vertex_indices.data()); +} + +int *MeshTopology::getFaceVertexIndicesStorage(int face_index) +{ + const MeshTopology *const_this = this; + return const_cast(const_this->getFaceVertexIndicesStorage(face_index)); +} +const int *MeshTopology::getFaceVertexIndicesStorage(int face_index) const +{ + assert(face_index >= 0); + assert(face_index < getNumFaces()); + + const int offset = faces_first_vertex_index_[face_index]; + return face_vertex_indices_.data() + offset; +} + +//////////////////////////////////////////////////////////////////////////////// +// Pipeline related. + +void MeshTopology::finishResizeTopology() +{ + if (!faces_first_vertex_index_.empty()) { + face_vertex_indices_.resize(faces_first_vertex_index_.back()); + } } } // namespace opensubdiv diff --git a/intern/opensubdiv/internal/topology/mesh_topology.h b/intern/opensubdiv/internal/topology/mesh_topology.h index aef521fbd44..fd3267df38b 100644 --- a/intern/opensubdiv/internal/topology/mesh_topology.h +++ b/intern/opensubdiv/internal/topology/mesh_topology.h @@ -32,6 +32,25 @@ namespace opensubdiv { // Simplified representation of mesh topology. // Only includes parts of actual mesh topology which is needed to perform // comparison between Application side and OpenSubddiv side. +// +// NOTE: It is an optimized storage which requires special order of topology +// specification. Basically, counters is to be set prior to anything else, in +// the following manner: +// +// MeshTopology mesh_topology; +// +// mesh_topology.setNumVertices(...); +// mesh_topology.setNumEdges(...); +// mesh_topology.setNumFaces(...); +// +// for (...) { +// mesh_topology.setNumFaceVertices(...); +// } +// +// mesh_topology.finishResizeTopology(); +// +// /* it is now possible to set vertices of edge, vertices of face, and +// * sharpness. */ class MeshTopology { public: MeshTopology(); @@ -78,10 +97,25 @@ class MeshTopology { void setNumFaceVertices(int face_index, int num_face_vertices); int getNumFaceVertices(int face_index) const; - void setFaceVertexIndices(int face_index, int *face_vertex_indices); + void setFaceVertexIndices(int face_index, + int num_face_vertex_indices, + const int *face_vertex_indices); bool isFaceVertexIndicesEqual(int face_index, - const vector &expected_vertices_of_face) const; + int num_expected_face_vertex_indices, + const int *expected_face_vertex_indices) const; + bool isFaceVertexIndicesEqual(int face_index, + const vector &expected_face_vertex_indices) const; + + ////////////////////////////////////////////////////////////////////////////// + // Pipeline related. + + // This function is to be called when number of vertices, edges, faces, and + // face-verticies are known. + // + // Usually is called from the end of topology refiner factory's + // resizeComponentTopology(). + void finishResizeTopology(); ////////////////////////////////////////////////////////////////////////////// // Comparison. @@ -102,6 +136,10 @@ class MeshTopology { void ensureVertexTagsSize(int num_vertices); void ensureEdgeTagsSize(int num_edges); + // Get pointer to the memory where face vertex indices are stored. + int *getFaceVertexIndicesStorage(int face_index); + const int *getFaceVertexIndicesStorage(int face_index) const; + struct VertexTag { float sharpness = 0.0f; }; @@ -120,36 +158,6 @@ class MeshTopology { float sharpness = 0.0f; }; - struct Face { - void setNumVertices(int num_vertices) - { - vertex_indices.resize(num_vertices, -1); - } - - void setVertexIndices(int *face_vertex_indices) - { - memcpy(vertex_indices.data(), face_vertex_indices, sizeof(int) * vertex_indices.size()); - } - - bool isValid() const - { - for (int vertex_index : vertex_indices) { - if (vertex_index < 0) { - return false; - } - } - - return true; - } - - int getNumVertices() const - { - return vertex_indices.size(); - } - - vector vertex_indices; - }; - int num_vertices_; vector vertex_tags_; @@ -158,7 +166,14 @@ class MeshTopology { vector edge_tags_; int num_faces_; - vector faces_; + + // Continuous array of all verticies of all faces: + // [vertex indices of face 0][vertex indices of face 1] .. [vertex indices of face n]. + vector face_vertex_indices_; + + // Indexed by face contains index within face_vertex_indices_ which corresponds + // to the element which contains first vertex of the face. + vector faces_first_vertex_index_; MEM_CXX_CLASS_ALLOC_FUNCS("MeshTopology"); }; diff --git a/intern/opensubdiv/internal/topology/mesh_topology_test.cc b/intern/opensubdiv/internal/topology/mesh_topology_test.cc index e80dab38fa3..5fb58c37add 100644 --- a/intern/opensubdiv/internal/topology/mesh_topology_test.cc +++ b/intern/opensubdiv/internal/topology/mesh_topology_test.cc @@ -27,6 +27,7 @@ TEST(MeshTopology, TrivialVertexSharpness) MeshTopology mesh_topology; mesh_topology.setNumVertices(3); + mesh_topology.finishResizeTopology(); mesh_topology.setVertexSharpness(0, 0.1f); mesh_topology.setVertexSharpness(1, 0.2f); @@ -42,6 +43,7 @@ TEST(MeshTopology, TrivialEdgeSharpness) mesh_topology.setNumVertices(8); mesh_topology.setNumEdges(3); + mesh_topology.finishResizeTopology(); mesh_topology.setEdgeVertexIndices(0, 0, 1); mesh_topology.setEdgeVertexIndices(1, 1, 2); @@ -60,29 +62,30 @@ TEST(MeshTopology, TrivialFaceTopology) MeshTopology mesh_topology; mesh_topology.setNumFaces(3); + mesh_topology.setNumFaceVertices(0, 4); + mesh_topology.setNumFaceVertices(1, 3); + mesh_topology.setNumFaceVertices(2, 5); + mesh_topology.finishResizeTopology(); + + EXPECT_EQ(mesh_topology.getNumFaceVertices(0), 4); + EXPECT_EQ(mesh_topology.getNumFaceVertices(1), 3); + EXPECT_EQ(mesh_topology.getNumFaceVertices(2), 5); { - mesh_topology.setNumFaceVertices(0, 4); int vertex_indices[] = {0, 1, 2, 3}; - mesh_topology.setFaceVertexIndices(0, vertex_indices); + mesh_topology.setFaceVertexIndices(0, 4, vertex_indices); } { - mesh_topology.setNumFaceVertices(1, 3); int vertex_indices[] = {4, 5, 6}; - mesh_topology.setFaceVertexIndices(1, vertex_indices); + mesh_topology.setFaceVertexIndices(1, 3, vertex_indices); } { - mesh_topology.setNumFaceVertices(2, 5); int vertex_indices[] = {7, 8, 9, 10, 11}; - mesh_topology.setFaceVertexIndices(2, vertex_indices); + mesh_topology.setFaceVertexIndices(2, 5, vertex_indices); } - EXPECT_EQ(mesh_topology.getNumFaceVertices(0), 4); - EXPECT_EQ(mesh_topology.getNumFaceVertices(1), 3); - EXPECT_EQ(mesh_topology.getNumFaceVertices(2), 5); - EXPECT_TRUE(mesh_topology.isFaceVertexIndicesEqual(0, {{0, 1, 2, 3}})); EXPECT_FALSE(mesh_topology.isFaceVertexIndicesEqual(0, {{10, 1, 2, 3}})); EXPECT_FALSE(mesh_topology.isFaceVertexIndicesEqual(0, {{0, 1, 2}})); diff --git a/intern/opensubdiv/internal/topology/topology_refiner_factory.cc b/intern/opensubdiv/internal/topology/topology_refiner_factory.cc index 5a84c45101b..e0c5e18e504 100644 --- a/intern/opensubdiv/internal/topology/topology_refiner_factory.cc +++ b/intern/opensubdiv/internal/topology/topology_refiner_factory.cc @@ -94,6 +94,7 @@ inline bool TopologyRefinerFactory::resizeComponentTopology // The rest is needed to define relations between faces-of-edge and // edges-of-vertex, which is not available for partially specified mesh. if (!converter->specifiesFullTopology(converter)) { + base_mesh_topology->finishResizeTopology(); return true; } @@ -113,6 +114,7 @@ inline bool TopologyRefinerFactory::resizeComponentTopology setNumBaseVertexFaces(refiner, vertex_index, num_vert_faces); } + base_mesh_topology->finishResizeTopology(); return true; } @@ -149,7 +151,8 @@ inline bool TopologyRefinerFactory::assignComponentTopology IndexArray dst_face_verts = getBaseFaceVertices(refiner, face_index); converter->getFaceVertices(converter, face_index, &dst_face_verts[0]); - base_mesh_topology->setFaceVertexIndices(face_index, &dst_face_verts[0]); + base_mesh_topology->setFaceVertexIndices( + face_index, dst_face_verts.size(), &dst_face_verts[0]); } // If converter does not provide full topology, we are done. -- cgit v1.2.3