optimization.hh 5.41 KB
Newer Older
1
2
3
4
5
6
#pragma once

#include "../Mesh.hh"

#include "../detail/permutation.hh"
#include "../detail/random.hh"
Philip Trettner's avatar
Philip Trettner committed
7
#include "../detail/union_find.hh"
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

namespace polymesh
{
/// Optimizes mesh layout for face traversals
// TODO: half-edge iteration should be cache local
void optimize_for_face_traversal(Mesh& m);

/// Optimizes mesh layout for vertex traversals
// TODO: half-edge iteration should be cache local
void optimize_for_vertex_traversal(Mesh& m);

/// Optimizes mesh layout for indexed face rendering
void optimize_for_rendering(Mesh& m);

/// optimizes edge indices for a given face neighborhood
void optimize_edges_for_faces(Mesh& m);
/// optimizes vertex indices for a given face neighborhood
void optimize_vertices_for_faces(Mesh& m);

/// optimizes edge indices for a given vertex neighborhood
void optimize_edges_for_vertices(Mesh& m);
/// optimizes face indices for a given vertex neighborhood
void optimize_faces_for_vertices(Mesh& m);

/// Calculates a cache-coherent face layout in O(n log n) time
/// Can be applied using m.faces().permute(...)
/// Returns remapping [curr_idx] = new_idx
std::vector<int> cache_coherent_face_layout(Mesh const& m);

/// Calculates a cache-coherent vertex layout in O(n log n) time
/// Can be applied using m.vertices().permute(...)
/// Returns remapping [curr_idx] = new_idx
std::vector<int> cache_coherent_vertex_layout(Mesh const& m);

/// ======== IMPLEMENTATION ========

inline void optimize_for_face_traversal(Mesh& m)
{
    m.faces().permute(cache_coherent_face_layout(m));
    optimize_edges_for_faces(m);
    optimize_vertices_for_faces(m);
}

inline void optimize_for_vertex_traversal(Mesh& m)
{
    m.vertices().permute(cache_coherent_vertex_layout(m));
    optimize_edges_for_vertices(m);
    optimize_faces_for_vertices(m);
}

inline void optimize_for_rendering(Mesh& m)
{
    // TODO
    assert(0 && "TODO");
}

inline std::vector<int> cache_coherent_face_layout(Mesh const& m)
{
Philip Trettner's avatar
Philip Trettner committed
66
67
68
69
70
71
72
73
74
75
76
    // build binary tree
    // - approx min cut
    // - refine approx
    // - split

    std::vector<std::pair<int, int>> edges;
    for (auto e : m.edges())
        edges.emplace_back((int)e.faceA(), (int)e.faceB());

    // TODO

77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
    std::vector<int> id;
    for (auto i = 0u; i < m.faces().size(); ++i)
        id.push_back(i);
    // TODO
    return id;
}

inline std::vector<int> cache_coherent_vertex_layout(Mesh const& m)
{
    assert(0 && "TODO");
    return {};
}

inline void optimize_edges_for_faces(Mesh& m)
{
    uint64_t rng = 1;

    std::vector<std::pair<int, int>> face_edge_indices;
    for (auto e : m.edges())
    {
        auto fA = e.faceA();
        auto fB = e.faceB();
        auto f = fA.is_invalid() ? fB : fB.is_invalid() ? fA : detail::xorshift64star(rng) % 2 ? fA : fB;
        face_edge_indices.emplace_back(f.idx.value, e.idx.value);
    }

    // sort by face idx
    sort(face_edge_indices.begin(), face_edge_indices.end());

    // extract edge indices
    std::vector<int> permutation(face_edge_indices.size());
    for (auto i = 0u; i < face_edge_indices.size(); ++i)
        permutation[i] = face_edge_indices[i].second;

    // apply permutation
    m.edges().permute(permutation);
}

inline void optimize_edges_for_vertices(Mesh& m)
{
    uint64_t rng = 1;

    std::vector<std::pair<int, int>> vertex_edge_indices;
    for (auto e : m.edges())
    {
        auto r = detail::xorshift64star(rng);
        vertex_edge_indices.emplace_back(r % 2 ? e.vertexA().idx.value : e.vertexB().idx.value, e.idx.value);
    }

    // sort by vertex idx
    sort(vertex_edge_indices.begin(), vertex_edge_indices.end());

    // extract edge indices
    std::vector<int> permutation(vertex_edge_indices.size());
    for (auto i = 0u; i < vertex_edge_indices.size(); ++i)
        permutation[i] = vertex_edge_indices[i].second;

    // apply permutation
    m.edges().permute(permutation);
}

inline void optimize_faces_for_vertices(Mesh& m)
{
    uint64_t rng = 1;

    std::vector<std::pair<int, int>> vertex_face_indices;
    for (auto f : m.faces())
    {
        vertex_handle vv;
        auto cnt = 0;
        for (auto v : f.vertices())
        {
            ++cnt;
            if (detail::xorshift64star(rng) % cnt == 0)
                vv = v;
        }
        vertex_face_indices.emplace_back(vv.idx.value, f.idx.value);
    }

    // sort by vertex idx
    sort(vertex_face_indices.begin(), vertex_face_indices.end());

    // extract face indices
    std::vector<int> permutation(vertex_face_indices.size());
    for (auto i = 0u; i < vertex_face_indices.size(); ++i)
        permutation[i] = vertex_face_indices[i].second;

    // apply permutation
    m.faces().permute(permutation);
}

inline void optimize_vertices_for_faces(Mesh& m)
{
    uint64_t rng = 1;

    std::vector<std::pair<int, int>> face_vertex_indices;
    for (auto v : m.vertices())
    {
        face_handle ff;
        auto cnt = 0;
        for (auto f : v.faces())
        {
            if (f.is_invalid())
                continue;

            ++cnt;
            if (detail::xorshift64star(rng) % cnt == 0)
                ff = f;
        }
        face_vertex_indices.emplace_back(ff.idx.value, v.idx.value);
    }

    // sort by face idx
    sort(face_vertex_indices.begin(), face_vertex_indices.end());

    // extract vertex indices
    std::vector<int> permutation(face_vertex_indices.size());
    for (auto i = 0u; i < face_vertex_indices.size(); ++i)
        permutation[i] = face_vertex_indices[i].second;

    // apply permutation
    m.vertices().permute(permutation);
}
}