blender
/
blender
136
406
Fork 590
Code Issues 6.2k Pull Requests 760 Projects 19 Wiki Activity

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).
This commit is contained in:
Sergey Sharybin 2020-05-26 10:54:46 +02:00
parent c971731b8f
commit 42cb1e3a2c
4 changed files with 126 additions and 63 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

64
intern/opensubdiv/internal/topology/mesh_topology.cc
View File

@ -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<int> &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<int> &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<int *>(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

81
intern/opensubdiv/internal/topology/mesh_topology.h
View File

@ -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<int> &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<int> &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<int> vertex_indices;
};
int num_vertices_;
vector<VertexTag> vertex_tags_;
@ -158,7 +166,14 @@ class MeshTopology {
vector<EdgeTag> edge_tags_;
int num_faces_;
vector<Face> 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<int> 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<int> faces_first_vertex_index_;
MEM_CXX_CLASS_ALLOC_FUNCS("MeshTopology");
};

39
intern/opensubdiv/internal/topology/mesh_topology_test.cc
View File

@ -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);
int vertex_indices[] = {0, 1, 2, 3};
mesh_topology.setFaceVertexIndices(0, vertex_indices);
}
{
mesh_topology.setNumFaceVertices(1, 3);
int vertex_indices[] = {4, 5, 6};
mesh_topology.setFaceVertexIndices(1, vertex_indices);
}
{
mesh_topology.setNumFaceVertices(2, 5);
int vertex_indices[] = {7, 8, 9, 10, 11};
mesh_topology.setFaceVertexIndices(2, vertex_indices);
}
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);
{
int vertex_indices[] = {0, 1, 2, 3};
mesh_topology.setFaceVertexIndices(0, 4, vertex_indices);
}
{
int vertex_indices[] = {4, 5, 6};
mesh_topology.setFaceVertexIndices(1, 3, vertex_indices);
}
{
int vertex_indices[] = {7, 8, 9, 10, 11};
mesh_topology.setFaceVertexIndices(2, 5, vertex_indices);
}
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}}));

5
intern/opensubdiv/internal/topology/topology_refiner_factory.cc
View File

@ -94,6 +94,7 @@ inline bool TopologyRefinerFactory<TopologyRefinerData>::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<TopologyRefinerData>::resizeComponentTopology
setNumBaseVertexFaces(refiner, vertex_index, num_vert_faces);
}
base_mesh_topology->finishResizeTopology();
return true;
}
@ -149,7 +151,8 @@ inline bool TopologyRefinerFactory<TopologyRefinerData>::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.