procedurals
Procedural generation building blocks
Loading...
Searching...
No Matches
TinyKeepDev.hpp
Go to the documentation of this file.
1
11#include "Deterministic.hpp"
12#include <vector>
13#include <cmath>
14#include <algorithm>
15#include <cstdint>
16#include <vector>
17#include <stdio.h>
18#include "Type.hpp"
19#include "graph.hpp"
20
22 private:
23 static bool circumcircleContains(const Trianglef& tri, const Vector2f& p) {
24 //p become the origin (0,0)
25 Vector2f a = {tri.p1.x - p.x, tri.p1.y - p.y};
26 Vector2f b = {tri.p2.x - p.x, tri.p2.y - p.y};
27 Vector2f c = {tri.p3.x - p.x, tri.p3.y - p.y};
28
29 //geometric condition (squared distances from P to each vertex)
30 double a2 = a.square_magnitude(); // ||A'||^2
31 double b2 = b.square_magnitude(); // ||B'||^2
32 double c2 = c.square_magnitude(); // ||C'||^2
33
34 double term1 = a.x * (b.y * c2 - c.y * b2); // contribution de la coordonnée x de A
35 double term2 = - a.y * (b.x * c2 - c.x * b2); // contribution de la coordonnée y de A
36 double term3 = a2 * b.cross(c); // contribution de la distance au carré de A (z) combinée à B et C // B' × C'
37 double det = term1 + term2 + term3; // La somme (det) nous dit si P est au-dessus ou en dessous du plan → donc à l’intérieur ou à l’extérieur du cercle.
38
39 return det < epsilonf;
40 }
41
42 static bool isCollidingOrClose(const Rectf &a, const Rectf &b, float margin = 0.0f) {
43 return !(a.x + a.w/2 + margin < b.x - b.w/2 ||
44 a.x - a.w/2 - margin > b.x + b.w/2 ||
45 a.y + a.h/2 + margin < b.y - b.h/2 ||
46 a.y - a.h/2 - margin > b.y + b.h/2);
47 }
48 //mst
49 struct EqV2 {
50 bool operator()(const Vector2f& a, const Vector2f& b) const {
51 return a.same(b);
52 }
53 };
54 struct DistV2 {
55 double operator()(const Vector2f& a, const Vector2f& b) const {
56 double dx = a.x - b.x, dy = a.y - b.y;
57 return std::sqrt(dx * dx + dy * dy);
58 }
59 };
60
61
62 public:
63
74 template<int nbRects>
75 static std::vector<Rectf> generateRects(float radius, float maxRectRatio = 0.5, std::pair<float, float> radiusRatios = {0.1f, 1.f} , uint64_t seed = 0) {
76 std::vector<Rectf> result;
77
78 // 1. Ratio largeur/hauteur
79 float denominator = 1 / maxRectRatio; //maxRectRatio = 0.5, inv.. = 2;
80
81 // 2. Taille (diagonale)
82 float diagMin = radius * radiusRatios.first;
83 float diagMax = radius * radiusRatios.second;
84
85 uint64_t next = seed;
86
87 for (int i = 0; i < nbRects; ++i) {
88
89 // 1. Ratio largeur/hauteur
90 float ratio = maxRectRatio + random0D(next) * (denominator - maxRectRatio);
91 next = mix64(next);
92 // 2. Taille (diagonale)
93 float diagonal = diagMin + random0D(next) * (diagMax - diagMin);
94 next = mix64(next);
95
96 // 3. Largeur / Hauteur
97 float w = diagonal * ratio / std::sqrt(1.0f + ratio * ratio);
98 float h = diagonal / std::sqrt(1.0f + ratio * ratio);
99
100 // 4. Rayon réduit pour que le rectangle reste dans le cercle
101 float reducedRadius = radius - diagonal / 2.0f;
102
103 // 5. Position aléatoire uniforme dans le disque
104 float theta = random0D(next) * 2.0f * M_PI;
105 next = mix64(next);
106 float r = reducedRadius * std::sqrt(random0D(next));
107 next = mix64(next);
108
109 float x = r * std::cos(theta);
110 float y = r * std::sin(theta);
111
112 // Convertir en coin supérieur gauche
113 //x -= w * 0.5f;
114 //y -= h * 0.5f;
115
116 // 6. Enregistrement du rectangle
117 result.push_back({x, y, w, h});
118
119 //next seed
120 }
121 return result;
122 }
123
124 template<int its = 50>
125 static void relaxRects(std::vector<Rectf>& rects) {
126
127 for (int i = 0; i < its; ++i) {
128 for (size_t i = 0; i < rects.size(); ++i) {
129 for (size_t j = i + 1; j < rects.size(); ++j) {
130
131 if (isCollidingOrClose(rects[i], rects[j])) {
132 float dx = rects[j].x - rects[i].x;
133 float dy = rects[j].y - rects[i].y;
134 float dist = sqrtf(dx*dx + dy*dy) + 0.001f; // éviter division par 0
135 float nx = dx / dist;
136 float ny = dy / dist;
137
138 float overlapX = (rects[i].w + rects[j].w)/2 - fabs(dx);
139 float overlapY = (rects[i].h + rects[j].h)/2 - fabs(dy);
140 float overlap = fminf(overlapX, overlapY);
141
142 float attractionRange = 50.0f; // distance max pour attraction
143 if (overlap > 0) {
144 // Repulsion
145 rects[i].x -= nx * overlap * 0.5f;
146 rects[i].y -= ny * overlap * 0.5f;
147 rects[j].x += nx * overlap * 0.5f;
148 rects[j].y += ny * overlap * 0.5f;
149 } else if (dist < attractionRange) {
150 // Attraction proportionnelle à la distance
151 float attractionStrength = (attractionRange - dist) * 0.05f; // ajustable
152 rects[i].x += nx * attractionStrength;
153 rects[i].y += ny * attractionStrength;
154 rects[j].x -= nx * attractionStrength;
155 rects[j].y -= ny * attractionStrength;
156 }
157 }
158 }
159 }
160 }
161 }
162
163 // --------------------------------------------------
164 // Algorithme de Bowyer–Watson
165 // --------------------------------------------------
166 static std::vector<Linef> bowyerWatson(const std::vector<Rectf>& rects) {
167 //1. Points
168 std::vector<Vector2f> points(rects.size());
169 points.reserve(rects.size());
170
171 //2. Super Triangle
172 double minX = rects[0].x, maxX = rects[0].x;
173 double minY = rects[0].y, maxY = rects[0].y;
174 for (auto& r : rects) {
175 minX = std::min(minX, r.x);
176 maxX = std::max(maxX, r.x);
177 minY = std::min(minY, r.y);
178 maxY = std::max(maxY, r.y);
179 }
180
181 double dx = maxX - minX;
182 double dy = maxY - minY;
183 double deltaMax = std::max(dx, dy) * 10.0f;
184
185 Vector2f p1 = {minX - deltaMax, minY - deltaMax};
186 Vector2f p2 = {minX + 0.5f * dx, maxY + deltaMax};
187 Vector2f p3 = {maxX + deltaMax, minY - deltaMax};
188
189 std::vector<Trianglef> triangles;
190 triangles.push_back({p1, p2, p3});
191
192 //3. Insert points 1 by 1:
193
194 for (auto &p: rects) {
195 std::vector<Trianglef> badTriangles; //.a
196 std::vector<Linef> polygonEdges; //.b
197
198 points.push_back({p.x, p.y});
199
200 // a. Identifier les mauvais triangles
201 // • Pour chaque triangle t dans triangles :
202 // • Si p est à l’intérieur du cercle circonscrit de t → ajoute t à badTriangles.
203 for (auto t: triangles) {
204 if (circumcircleContains(t, {p.x, p.y})) {
205 badTriangles.push_back(t);
206 }
207 }
208
209 // b. Construire le polygone de la cavité
210 // • Pour chaque triangle bt dans badTriangles :
211 // • Pour chaque arête e de bt :
212 // • Si aucun autre triangle dans badTriangles ne partage e → ajoute e à polygonEdges.
213 // • Résultat : polygonEdges = contour extérieur des triangles à supprimer.
214 for (auto bt: badTriangles) {
215 std::vector<Linef> btedges = {
216 { bt.p1, bt.p2 },
217 { bt.p2, bt.p3 },
218 { bt.p3, bt.p1 }
219 };
220
221 for (const Linef& e : btedges) {
222 bool shared = false;
223
224 // Check if this edge is shared with another bad triangle
225 for (const Trianglef other : badTriangles) {
226 if (bt.same(other)) continue; // skip self
227 std::vector<Linef> otherEdges = {
228 { other.p1, other.p2 },
229 { other.p2, other.p3 },
230 { other.p3, other.p1 }
231 };
232
233 for (const Linef& oe : otherEdges) {
234 if (e.same(oe)) {
235 shared = true;
236 break;
237 }
238 }
239 if (shared) break;
240 }
241
242 // If no other triangle shares this edge, it belongs to the polygon boundary
243 if (!shared) {
244 polygonEdges.push_back(e);
245 }
246 }
247 }
248
249 // c. Suprime les mauvais triangles
250 // • Retire tous les triangles de badTriangles de la liste triangles.
251 for (const Trianglef& bad : badTriangles) {
252 auto it = std::remove_if(triangles.begin(), triangles.end(),
253 [&](const Trianglef& t) {
254 return (t.same(bad));
255 });
256 triangles.erase(it, triangles.end());
257 }
258
259 // d. – Ajouter de nouveaux triangles
260 // • Pour chaque arête e dans polygonEdges :
261 // • Crée un triangle avec p et e → newTriangle = (e.a, e.b, p)
262 // • Ajoute newTriangle à triangles.
263 for (auto& e : polygonEdges) {
264 triangles.push_back({e.p1, e.p2, {p.x, p.y}});
265 }
266 }
267
268 //4. Nettoyage final
269 // a. Supprime tous les triangles qui contiennent un sommet du super-triangle → ces triangles sont artificiels.
270 triangles.erase(std::remove_if(triangles.begin(), triangles.end(),
271 [&](const Trianglef& t) {
272 auto usesSuperVertex = [&](const Vector2f& v) {
273 return (fabs(v.x - p1.x) < 1e-12 && fabs(v.y - p1.y) < 1e-12) ||
274 (fabs(v.x - p2.x) < 1e-12 && fabs(v.y - p2.y) < 1e-12) ||
275 (fabs(v.x - p3.x) < 1e-12 && fabs(v.y - p3.y) < 1e-12);
276 };
277 return usesSuperVertex(t.p1) || usesSuperVertex(t.p2) || usesSuperVertex(t.p3);
278 }),
279 triangles.end()
280 );
281
282 // b. Les triangles restants sont ta triangulation Delaunay.
283
284 // c. Extrais les arêtes finales pour relier les rectangles :
285 // • Pour chaque triangle, ajoute (p1,p2), (p2,p3), (p3,p1) à ta liste edges.
286 std::vector<Linef> edges;
287 for (auto& t : triangles) {
288 edges.push_back({t.p1, t.p2});
289 edges.push_back({t.p2, t.p3});
290 edges.push_back({t.p3, t.p1});
291 }
292
293 return edges;
294 }
295
296 // mst
297 static std::vector<Linef> mst(const std::vector<Linef>& edges) {
298 std::vector<std::pair<Vector2f, Vector2f>> pairs;
299 pairs.reserve(edges.size());
300 for (const auto& e : edges) pairs.emplace_back(e.p1, e.p2);
301
302 auto g = Graph<Vector2f, EqV2>::fromPairs<DistV2>(pairs);
303 auto mst = g.mst();
304
305 std::vector<Linef> result;
306 result.reserve(mst.edgeCount());
307 for (const auto& link : mst.edges())
308 result.push_back({mst.node(link.from), mst.node(link.to)});
309 return result;
310 }
311
312 static std::vector<Linef> shortenLine(const std::vector<Rectf>& rects,
313 const std::vector<Linef>& edges) {
314 auto findRect = [&](const Vector2f& p) -> const Rectf* {
315 for (const auto& r : rects) {
316 Vector2f c{r.x, r.y};
317 if (c.same(p)) return &r;
318 }
319 return nullptr;
320 };
321
322 auto exitPoint = [](const Rectf& r, const Vector2f& other) -> Vector2f {
323 double dx = other.x - r.x;
324 double dy = other.y - r.y;
325 constexpr double INF = std::numeric_limits<double>::infinity();
326 double tx = (std::abs(dx) > epsilond) ? (r.w * 0.5) / std::abs(dx) : INF;
327 double ty = (std::abs(dy) > epsilond) ? (r.h * 0.5) / std::abs(dy) : INF;
328 double t = std::min(tx, ty);
329 return {r.x + t * dx, r.y + t * dy};
330 };
331
332 std::vector<Linef> result;
333 result.reserve(edges.size());
334
335 for (const auto& e : edges) {
336 const Rectf* ra = findRect(e.p1);
337 const Rectf* rb = findRect(e.p2);
338 if (!ra || !rb) { result.push_back(e); continue; } // can't match → keep as-is
339
340 Vector2f a = exitPoint(*ra, e.p2); // exit ra toward p2
341 Vector2f b = exitPoint(*rb, e.p1); // exit rb toward p1
342 result.push_back({a, b});
343 }
344 return result;
345 }
346};
Definition TinyKeepDev.hpp:21
static std::vector< Linef > shortenLine(const std::vector< Rectf > &rects, const std::vector< Linef > &edges)
Definition TinyKeepDev.hpp:312
static std::vector< Linef > bowyerWatson(const std::vector< Rectf > &rects)
Definition TinyKeepDev.hpp:166
static std::vector< Rectf > generateRects(float radius, float maxRectRatio=0.5, std::pair< float, float > radiusRatios={0.1f, 1.f}, uint64_t seed=0)
Definition TinyKeepDev.hpp:75
static std::vector< Linef > mst(const std::vector< Linef > &edges)
Definition TinyKeepDev.hpp:297
static void relaxRects(std::vector< Rectf > &rects)
Definition TinyKeepDev.hpp:125
float random0D(uint64_t seed=0) noexcept
Definition Deterministic.hpp:57
uint64_t mix64(uint64_t x) noexcept
Definition Deterministic.hpp:40