src/polygoncache.cpp

Sat, 11 Jun 2022 15:20:24 +0300

author
Teemu Piippo <teemu.s.piippo@gmail.com>
date
Sat, 11 Jun 2022 15:20:24 +0300
changeset 213
ee5758ddb6d2
parent 211
b27b90fb993f
child 232
8efa3a33172e
permissions
-rw-r--r--

Rewrite prune to use graphs rather than O(n²) searches

150
b6cbba6e29a1 extract polygon cache out of Model
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
1 #include "polygoncache.h"
b6cbba6e29a1 extract polygon cache out of Model
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
2 #include "documentmanager.h"
200
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
3 #include "invert.h"
150
b6cbba6e29a1 extract polygon cache out of Model
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
4
200
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
5 Model* resolve(const QString& name, const ModelId callingModelId, DocumentManager* documents)
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
6 {
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
7 return documents->findDependencyByName(callingModelId, name);
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
8 }
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
9
210
232e7634cc8a more refactoring, dosn't build yet
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 205
diff changeset
10 static PolygonElement transformed(
232e7634cc8a more refactoring, dosn't build yet
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 205
diff changeset
11 PolygonElement element,
232e7634cc8a more refactoring, dosn't build yet
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 205
diff changeset
12 const glm::mat4& transform)
200
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
13 {
211
b27b90fb993f Now builds again
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 210
diff changeset
14 visitPoints([&transform](glm::vec3& p) {
210
232e7634cc8a more refactoring, dosn't build yet
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 205
diff changeset
15 p = transform * glm::vec4{p, 1};
211
b27b90fb993f Now builds again
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 210
diff changeset
16 }, element);
210
232e7634cc8a more refactoring, dosn't build yet
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 205
diff changeset
17 return element;
232e7634cc8a more refactoring, dosn't build yet
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 205
diff changeset
18 }
232e7634cc8a more refactoring, dosn't build yet
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 205
diff changeset
19
211
b27b90fb993f Now builds again
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 210
diff changeset
20 PolygonCache* findPolygonCacheForModel(Model* model, DocumentManager* context)
b27b90fb993f Now builds again
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 210
diff changeset
21 {
b27b90fb993f Now builds again
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 210
diff changeset
22 std::optional<ModelId> modelId = context->findIdForModel(model);
b27b90fb993f Now builds again
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 210
diff changeset
23 if (modelId.has_value()) {
b27b90fb993f Now builds again
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 210
diff changeset
24 return context->getPolygonCacheForModel(modelId.value());
b27b90fb993f Now builds again
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 210
diff changeset
25 }
b27b90fb993f Now builds again
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 210
diff changeset
26 else {
b27b90fb993f Now builds again
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 210
diff changeset
27 return nullptr;
b27b90fb993f Now builds again
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 210
diff changeset
28 }
b27b90fb993f Now builds again
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 210
diff changeset
29 }
b27b90fb993f Now builds again
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 210
diff changeset
30
210
232e7634cc8a more refactoring, dosn't build yet
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 205
diff changeset
31 static std::vector<WithId<PolygonElement>> getPolygonsAt(
232e7634cc8a more refactoring, dosn't build yet
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 205
diff changeset
32 const Model* model,
232e7634cc8a more refactoring, dosn't build yet
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 205
diff changeset
33 GetPolygonsContext* context)
232e7634cc8a more refactoring, dosn't build yet
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 205
diff changeset
34 {
232e7634cc8a more refactoring, dosn't build yet
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 205
diff changeset
35 std::vector<WithId<PolygonElement>> result;
200
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
36 for (int i = 0; i < model->size(); i += 1)
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
37 {
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
38 const ModelElement& element = (*model)[i];
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
39 const ModelId id = model->idAt(i);
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
40 std::visit<void>(overloaded{
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
41 [&](const Colored<LineSegment>& edge) {
210
232e7634cc8a more refactoring, dosn't build yet
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 205
diff changeset
42 result.push_back({{edge, edge.color}, id});
200
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
43 },
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
44 [&](const Colored<Triangle>& triangle) {
210
232e7634cc8a more refactoring, dosn't build yet
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 205
diff changeset
45 result.push_back({{triangle, triangle.color}, id});
200
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
46 },
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
47 [&](const Colored<Quadrilateral>& quad) {
210
232e7634cc8a more refactoring, dosn't build yet
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 205
diff changeset
48 result.push_back({{quad, quad.color}, id});
200
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
49 },
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
50 [&](const Colored<ConditionalEdge>& cedge) {
210
232e7634cc8a more refactoring, dosn't build yet
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 205
diff changeset
51 result.push_back({{cedge, cedge.color}, id});
200
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
52 },
211
b27b90fb993f Now builds again
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 210
diff changeset
53 [&result, &id, context](const Colored<SubfileReference>& ref) {
200
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
54 Model* dependency = context->documents->findDependencyByName(context->modelId, ref.name);
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
55 PolygonCache* cache = nullptr;
211
b27b90fb993f Now builds again
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 210
diff changeset
56 if (dependency != nullptr) {
b27b90fb993f Now builds again
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 210
diff changeset
57 cache = findPolygonCacheForModel(dependency, context->documents);
200
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
58 }
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
59 if (cache != nullptr) {
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
60 const bool needInverting = glm::determinant(ref.transformation) < 0;
211
b27b90fb993f Now builds again
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 210
diff changeset
61 const PolygonCache::vector_type* modelPolygons = getCachedPolygons(
200
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
62 cache,
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
63 dependency,
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
64 context->documents);
211
b27b90fb993f Now builds again
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 210
diff changeset
65 reserveMore(result, modelPolygons->size());
b27b90fb993f Now builds again
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 210
diff changeset
66 for (WithId<PolygonElement> polygon : *modelPolygons) {
210
232e7634cc8a more refactoring, dosn't build yet
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 205
diff changeset
67 polygon = {transformed(polygon, ref.transformation), polygon.id};
232e7634cc8a more refactoring, dosn't build yet
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 205
diff changeset
68 if (needInverting != ref.inverted) {
200
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
69 gl::invert(polygon);
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
70 }
210
232e7634cc8a more refactoring, dosn't build yet
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 205
diff changeset
71 if (polygon.color == MAIN_COLOR) {
200
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
72 polygon.color = ref.color;
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
73 }
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
74 polygon.id = id;
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
75 result.push_back(polygon);
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
76 }
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
77 }
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
78 },
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
79 [](const ModelElement&) {}
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
80 }, element);
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
81 }
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
82 return result;
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
83 }
150
b6cbba6e29a1 extract polygon cache out of Model
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
84
b6cbba6e29a1 extract polygon cache out of Model
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
85 /**
b6cbba6e29a1 extract polygon cache out of Model
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
86 * @brief Gets a list of GL polygons that are used to represent this model.
b6cbba6e29a1 extract polygon cache out of Model
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
87 * @details Will build polygons if polygons are outdated.
b6cbba6e29a1 extract polygon cache out of Model
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
88 * @param documents Documents to use to resolve subfile references
b6cbba6e29a1 extract polygon cache out of Model
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
89 * @return vector of GL polygons
b6cbba6e29a1 extract polygon cache out of Model
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
90 */
211
b27b90fb993f Now builds again
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 210
diff changeset
91 const PolygonCache::vector_type* getCachedPolygons(
193
b4beff48bb7a Simplify PolygonCache
Teemu Piippo <teemu@hecknology.net>
parents: 183
diff changeset
92 PolygonCache *cache,
b4beff48bb7a Simplify PolygonCache
Teemu Piippo <teemu@hecknology.net>
parents: 183
diff changeset
93 Model *model,
b4beff48bb7a Simplify PolygonCache
Teemu Piippo <teemu@hecknology.net>
parents: 183
diff changeset
94 DocumentManager *documents)
150
b6cbba6e29a1 extract polygon cache out of Model
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
95 {
193
b4beff48bb7a Simplify PolygonCache
Teemu Piippo <teemu@hecknology.net>
parents: 183
diff changeset
96 if (cache->needRecache)
150
b6cbba6e29a1 extract polygon cache out of Model
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
97 {
193
b4beff48bb7a Simplify PolygonCache
Teemu Piippo <teemu@hecknology.net>
parents: 183
diff changeset
98 cache->cachedPolygons.clear();
b4beff48bb7a Simplify PolygonCache
Teemu Piippo <teemu@hecknology.net>
parents: 183
diff changeset
99 const std::optional<ModelId> modelId = documents->findIdForModel(model);
150
b6cbba6e29a1 extract polygon cache out of Model
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
100 if (modelId.has_value())
b6cbba6e29a1 extract polygon cache out of Model
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
101 {
200
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
102 GetPolygonsContext context{modelId.value(), documents};
ca23936b455b Giant refactor
Teemu Piippo <teemu@hecknology.net>
parents: 193
diff changeset
103 cache->cachedPolygons = getPolygonsAt(model, &context);
150
b6cbba6e29a1 extract polygon cache out of Model
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
104 }
193
b4beff48bb7a Simplify PolygonCache
Teemu Piippo <teemu@hecknology.net>
parents: 183
diff changeset
105 cache->needRecache = false;
150
b6cbba6e29a1 extract polygon cache out of Model
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
106 }
211
b27b90fb993f Now builds again
Teemu Piippo <teemu.s.piippo@gmail.com>
parents: 210
diff changeset
107 return &cache->cachedPolygons;
150
b6cbba6e29a1 extract polygon cache out of Model
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
108 }

mercurial