Paste P756

Faster volume mesh generation
ActivePublic

Authored by Stefan Werner (swerner) on Tue, Jul 24, 11:06 AM.
1diff --git a/intern/cycles/render/mesh_volume.cpp b/intern/cycles/render/mesh_volume.cpp
2index d1c49b456ff..6eb2a54c8ed 100644
3--- a/intern/cycles/render/mesh_volume.cpp
4+++ b/intern/cycles/render/mesh_volume.cpp
5@@ -43,7 +43,7 @@ static size_t compute_voxel_index(const int3 &resolution, size_t x, size_t y, si
6​ }
7
8​ struct QuadData {
9- int v0, v1, v2, v3;
10+ size_t v0, v1, v2, v3;
11
12​ float3 normal;
13​ };
14@@ -87,23 +87,32 @@ const float3 quads_normals[6] = {
15​ make_float3(0.0f, 0.0f, 1.0f),
16​ };
17
18-static void create_quad(int3 corners[8], vector<int3> &vertices, vector<QuadData> &quads, int face_index)
19+static size_t add_vertex(int3 v, vector<int3> &vertices, int3 res, unordered_map<size_t, size_t> &used_verts)
20​ {
21- size_t vertex_offset = vertices.size();
22+ size_t vert_key = v.x + v.y * (res.x+1) + v.z * (res.x+1)*(res.y+1);
23+ if(used_verts.find(vert_key) != used_verts.end()) {
24+ return used_verts[vert_key];
25+ }
26+ else {
27+ size_t vertex_offset = vertices.size();
28+ used_verts[vert_key] = vertex_offset;
29+ vertices.push_back(v);
30+ return vertex_offset;
31+ }
32+}
33+
34+static void create_quad(int3 corners[8], vector<int3> &vertices, vector<QuadData> &quads, int3 res, unordered_map<size_t, size_t> &used_verts, int face_index)
35+{
36+
37
38​ QuadData quad;
39- quad.v0 = vertex_offset + 0;
40- quad.v1 = vertex_offset + 1;
41- quad.v2 = vertex_offset + 2;
42- quad.v3 = vertex_offset + 3;
43+ quad.v0 = add_vertex(corners[quads_indices[face_index][0]], vertices, res, used_verts);
44+ quad.v1 = add_vertex(corners[quads_indices[face_index][1]], vertices, res, used_verts);
45+ quad.v2 = add_vertex(corners[quads_indices[face_index][2]], vertices, res, used_verts);
46+ quad.v3 = add_vertex(corners[quads_indices[face_index][3]], vertices, res, used_verts);
47​ quad.normal = quads_normals[face_index];
48
49​ quads.push_back(quad);
50-
51- vertices.push_back(corners[quads_indices[face_index][0]]);
52- vertices.push_back(corners[quads_indices[face_index][1]]);
53- vertices.push_back(corners[quads_indices[face_index][2]]);
54- vertices.push_back(corners[quads_indices[face_index][3]]);
55​ }
56
57​ struct VolumeParams {
58@@ -158,10 +167,7 @@ public:
59​ private:
60​ void generate_vertices_and_quads(vector<int3> &vertices_is,
61​ vector<QuadData> &quads);
62-
63- void deduplicate_vertices(vector<int3> &vertices,
64- vector<QuadData> &quads);
65-
66+
67​ void convert_object_space(const vector<int3> &vertices,
68​ vector<float3> &out_vertices);
69
70@@ -234,8 +240,6 @@ void VolumeMeshBuilder::create_mesh(vector<float3> &vertices,
71
72​ generate_vertices_and_quads(vertices_is, quads);
73
74- deduplicate_vertices(vertices_is, quads);
75-
76​ convert_object_space(vertices_is, vertices);
77
78​ convert_quads_to_tris(quads, indices, face_normals);
79@@ -245,10 +249,7 @@ void VolumeMeshBuilder::generate_vertices_and_quads(
80​ vector<ccl::int3> &vertices_is,
81​ vector<QuadData> &quads)
82​ {
83- /* Overallocation, we could count the number of quads and vertices to create
84- * in a pre-pass if memory becomes an issue. */
85- vertices_is.reserve(number_of_nodes*8);
86- quads.reserve(number_of_nodes*6);
87+ unordered_map<size_t, size_t> used_verts;
88
89​ for(int z = 0; z < res.z; ++z) {
90​ for(int y = 0; y < res.y; ++y) {
91@@ -283,77 +284,38 @@ void VolumeMeshBuilder::generate_vertices_and_quads(
92
93​ voxel_index = compute_voxel_index(res, x - 1, y, z);
94​ if(voxel_index == -1 || grid[voxel_index] == 0) {
95- create_quad(corners, vertices_is, quads, QUAD_X_MIN);
96+ create_quad(corners, vertices_is, quads, res, used_verts, QUAD_X_MIN);
97​ }
98
99​ voxel_index = compute_voxel_index(res, x + 1, y, z);
100​ if(voxel_index == -1 || grid[voxel_index] == 0) {
101- create_quad(corners, vertices_is, quads, QUAD_X_MAX);
102+ create_quad(corners, vertices_is, quads, res, used_verts, QUAD_X_MAX);
103​ }
104
105​ voxel_index = compute_voxel_index(res, x, y - 1, z);
106​ if(voxel_index == -1 || grid[voxel_index] == 0) {
107- create_quad(corners, vertices_is, quads, QUAD_Y_MIN);
108+ create_quad(corners, vertices_is, quads, res, used_verts, QUAD_Y_MIN);
109​ }
110
111​ voxel_index = compute_voxel_index(res, x, y + 1, z);
112​ if(voxel_index == -1 || grid[voxel_index] == 0) {
113- create_quad(corners, vertices_is, quads, QUAD_Y_MAX);
114+ create_quad(corners, vertices_is, quads, res, used_verts, QUAD_Y_MAX);
115​ }
116
117​ voxel_index = compute_voxel_index(res, x, y, z - 1);
118​ if(voxel_index == -1 || grid[voxel_index] == 0) {
119- create_quad(corners, vertices_is, quads, QUAD_Z_MIN);
120+ create_quad(corners, vertices_is, quads, res, used_verts, QUAD_Z_MIN);
121​ }
122
123​ voxel_index = compute_voxel_index(res, x, y, z + 1);
124​ if(voxel_index == -1 || grid[voxel_index] == 0) {
125- create_quad(corners, vertices_is, quads, QUAD_Z_MAX);
126+ create_quad(corners, vertices_is, quads, res, used_verts, QUAD_Z_MAX);
127​ }
128​ }
129​ }
130​ }
131​ }
132
133-void VolumeMeshBuilder::deduplicate_vertices(vector<int3> &vertices,
134- vector<QuadData> &quads)
135-{
136- vector<int3> sorted_vertices = vertices;
137- std::sort(sorted_vertices.begin(), sorted_vertices.end());
138- vector<int3>::iterator it = std::unique(sorted_vertices.begin(), sorted_vertices.end());
139- sorted_vertices.resize(std::distance(sorted_vertices.begin(), it));
140-
141- vector<QuadData> new_quads = quads;
142-
143- for(size_t i = 0; i < vertices.size(); ++i) {
144- for(size_t j = 0; j < sorted_vertices.size(); ++j) {
145- if(vertices[i] != sorted_vertices[j]) {
146- continue;
147- }
148-
149- for(int k = 0; k < quads.size(); ++k) {
150- if(quads[k].v0 == i) {
151- new_quads[k].v0 = j;
152- }
153- else if(quads[k].v1 == i) {
154- new_quads[k].v1 = j;
155- }
156- else if(quads[k].v2 == i) {
157- new_quads[k].v2 = j;
158- }
159- else if(quads[k].v3 == i) {
160- new_quads[k].v3 = j;
161- }
162- }
163-
164- break;
165- }
166- }
167-
168- vertices = sorted_vertices;
169- quads = new_quads;
170-}
171-
172​ void VolumeMeshBuilder::convert_object_space(const vector<int3> &vertices,
173​ vector<float3> &out_vertices)
174​ {