(La version PDF de ce document ne permet pas de visualiser des vidéos)
Disques de Poisson avec triangulation de Delaunay
Disques de poisson, distance pondérée avec un bruit de perlin
Création d'un jeu de carte de jeu Dobble à 14 et 30 symboles
Bruit de perlin en "octaves" avec GPU"
Génération aléatoire de rues d'une petite ville
Blender: modélisation rétro "low poly"
Blender: animation squelettale
Génération de l'intérieur d'un immeuble/batiment/maison
Outil de tri d'images par label
import sur godot engine
A star pathfinfing implementation | A étoile, implémentation d'algorithme de recherche de chemin le plus court
L'algorithme A* permet de trouver le plus court chemin avec un minimum de temps. Cet algorithme utilise une structure de donnée "tas" ou file de priorité.
J'ai travaillé sur cette application indépendamment.
Video demontrant l'application:
Image:
C++
void astar_contained::step(){
++stepcount;
Vec2i
end = end_global,
start = start_global;
if (start == end) { msg("start == end, exiting"); return; }
auto current = pq.top();
pq.pop();
if (current.node == end) {
build_path();
return;
}
for (auto&a : surnd)
{
auto next = a + current.node;
float new_cost = cost_so_far[current.node] + 1;
//colorized[next]=closed;
colorize(next, closed);
if ((!cost_so_far.count(next) || new_cost < cost_so_far[next])
&& !obstacles.count(next))
{
//colorized[next]=opened;
colorize(next, opened);
cost_so_far[next] = new_cost;
float priority = new_cost + abs(next.x - end.x) + abs(next.y - end.y);
pq.push(prioritized_node(next, priority));
came_from[next] = current.node;
}
}
}
Structure de donnée pour du partitionnement spatial en temps réel
Un quadtree est une structure d'indexation spatiale en arbre dans un espace a 2 dimensions. Elle permet une plus grande rapidité lors de la recherche d'objets situés dans l'espace. On peut aussi étendre cette technique en 3 dimensions avec l'octree.
J'ai travaillé sur cette application indépendamment.
Plusieurs fonctionnalités sont désirées: l'insertion, la recherche et l'équilibrage.
namespace quadtree {
vector<size_t> lookup; // offsets for quad ids, indexed by depth/resolution
multimap<size_t, size_t> flat_tree;
set<size_t> has_children;
map<size_t,size_t> child_count;
unsigned int max_items_per_quad;
map<size_t, Vec2> positions; // matters only for rebalancing
L'algorithme des disques de poisson permet de générer des points 2D ou 3D aléatoires et espacés. la technique est la suivante:
Voici mon implémentation des disques de poisson.
int paused_distr::pick_with_variable_distance(Vec2 & ret,
float radius_coeff,
vector<vector<float>>& grid,
int cell_searched
)
{
if (notfull.empty()) return 0;
int attempt = 0;
int current = *(notfull.begin());
msgs("");
while (attempt<attempts)
{
// generate a point in a "annulus" (2d doughnut)
string diagnose;
diagnose+= to_str("attempt", attempt);
float scaled_radius1 = radius / radius_coeff;
float scaled_radius2 = radius * radius_coeff*(pick_altitude(pts[current], grid));
msg(scaled_radius2);
ret = rand_polar(pts[current], scaled_radius2, dist(mt), dist(mt));
// check if point has neighbor, and if it's in screen
vector<Vec2> res;
grid_search_nearest::buckets;
grid_search_nearest::swirl_search_nearest(cell_searched, ret, res, 1);
diagnose += to_str(" results:", res.size());
if (res.size())
{
float nearest = vectlen(ret - res[0]);
diagnose += to_str(" nearest:", nearest);
}
msgs(diagnose);
if(res.size() == 0 || vectlen(ret-res[0]) > scaled_radius2
&& ret.x > 0.f && ret.y > 0.f && ret.x < 1.f && ret.y < 1.f)
{
pts.push_back(ret);
has_pt.insert(which(ret));
grid_search_nearest::add(ret);
notfull.insert(pts.size() - 1);
radiuses[ret] = scaled_radius2;
return 1;// ok, generated a point
}
else
++attempt;
}
notfull.erase(current);
msgs("[FAIL]");
++failed_attempts;
return 2; // must try again
}
Afin de générer des triangles avec un nuage de point, on utilise cette triangulation. Le probleme est le suivant:
Chargement et rendu de donnée cartographique Openstreetmap-XML, transformée de Mercator | Loading and rendering of cartographic data Openstreetmap-XML, mercator transform.
J'ai travaillé sur cette application indépendamment.
Cette application charge de la donnée openstreetmap, obtenue grâce a la fonctionnalité d'export du site:
Le site offre un fichier XML contenant toutes les donnees contenues dans le rectangle choisi.
Afin d’éviter un étirement étrange de la carte, il convient d'appliquer la projection de Mercator:
double merc_x(double lon) {
return R_MAJOR * deg_rad(lon);
}
double merc_y(double lat) {
lat = fmin(89.5, fmax(lat, -89.5));
double phi = deg_rad(lat);
double sinphi = sin(phi);
double con = ECCENT * sinphi;
con = pow((1.0 - con) / (1.0 + con), COM);
double ts = tan(0.5 * (M_PI * 0.5 - phi)) / con;
return 0 - R_MAJOR * log(ts);
}
Une video demontrant l'application:
(video)
J'ai travaillé sur cette application indépendamment.
Le bruit de perlin est un bruit aleatoire, resultant du produit vectoriel de 4 vecteurs, interpole selon la position du pixel.
Appliqué aux disques de poisson, on peut moduler la distance minimum pour obtenir des "forets" plus ou moins denses.
Python, pySFML
A partir d'une gestion matricielle et d'emojis NotoEmoji, j'ai généré 2 jeux de cartes Dobble.
Règles: les joueurs doivent trouver un symbole en commun entre leur carte et la carte sur la table. Le gagnant est celui qui n'a plus de cartes.
Le premier jeu a 14 symboles par carte et contient 183 cartes.
Le deuxième jeu a 29 symboles par carte et contient ~800 cartes mais je n'ai imprimé que les 50 premières.
Sudoku solver | Solveur sudoku | via brython (python interpreter inside the browser via javascript
Développé avec Brython (interpréteur python écrit en js, exécuté coté client)
Réalisé en python, ce script génère un calendrier HTML aligné à la semaine, à partir d'un fichier texte
Untangle / démêleur | but du jeu: aucune ligne ne doit se croiser
Python et pySFML
python+pysfsml
Partitionnement spatial via courbe Z-order | Spatial partitionning via Z-order curve
Une courbe Z-order ou courbe de Morton est une transformation 1D-2D (bijective en mathématique), qui permet d'indexer un nuage de points 2D en mémoire. Couplé a une std::map ou std::multimap (arbre trié), c'est une méthode modeste mais suffisamment rapide et fonctionnelle. C'est une alternative simple à un quadtree qui peut être trop difficilement linéarisé en mémoire (appels fréquents a malloc()). L'indexation permet de gérer des grandes quanatité de donnée dans l'espace 2D ou 3D.
Une requête parmis une grand collection de points. Les 6 carrés sont les index dans la courbe de Morton, le rectangle est la zone de requête.
uint32_t calcZOrder(uint16_t xPos, uint16_t yPos) {
static const uint32_t MASKS[] = { 0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF };
static const uint32_t SHIFTS[] = { 1, 2, 4, 8 };
uint32_t x = xPos; // Interleave lower 16 bits of x and y, so the bits of x
uint32_t y = yPos; // are in the even positions and bits from y in the odd;
x = (x | (x << SHIFTS[3])) & MASKS[3];
x = (x | (x << SHIFTS[2])) & MASKS[2];
x = (x | (x << SHIFTS[1])) & MASKS[1];
x = (x | (x << SHIFTS[0])) & MASKS[0];
y = (y | (y << SHIFTS[3])) & MASKS[3];
y = (y | (y << SHIFTS[2])) & MASKS[2];
y = (y | (y << SHIFTS[1])) & MASKS[1];
y = (y | (y << SHIFTS[0])) & MASKS[0];
const uint32_t result = x | (y << 1);
return result;
}
Bruit de perlin à couche en octave, pour la génération de terrain 3D en relief | Octave-layered perlin noise for generating 3D terrain.
Le bruit de perlin, utilisé en plusieurs "octaves" de différentes tailles et amplitudes, permet de générer une heightmap réaliste.
Meme principe, mais utilisation du GPU avec un shader GLSL et export en float 32bit | Same thing, but using GPU through a GLSL shader with 32 bit float output
J'ai également pu exécuter cet algorithme dans un shader GLSL via OpenGL, afin de grandement accélérer son exécution.
Ci dessous, une visualisation en 3D de la heightmap
Génération procédurale de villes et rues | Procedural generation of streets
C++, SFML
Plusieurs paramètres sont disponibles: densité des rues, graine, longueur, etc
Modélisation 3D de personnage avec peu de polygones/triangles sous Blender
Bases de l'animation squelettale sous blender | Basics of skeletal animation with Blender
C++, SFML
Procedural generation of house interior and exterior | Génération de géométrie procédurale d'intérieur et extérieur de maison
A partir d'un court fichier de paramètres, on génére un plan de batiment avec extérieur et intérieur. Cet algorithme sera adapté à la 3D.
HTML/JS, Python/Flask, SQLite/SpatiaLite
Usage of leaflet + spatialite, digital cartographic tools | Utilisation de leafleat et spatialite, outils d'édition et de manipulation de données cartographiques
Vidéo:
Flappy est une application web écrite en python et javascript, qui expérimente les capacités d'une base de données cartographiques SpatiaLite. J'ai travaillé sur cette application indépendamment, pour me former sur la technologie GIS (Geographic Information System) de base de donnée cartographique. L’affichage utilise leaflet.js (voir plus loin).
Il faut rappeler que les bases de données classiques ne gèrent pas nativement l'indexation spatiale. Une base de donnée comme spatialite ou PostGIS utilisent des structures de données optimisées pour l'indexation spatiale. En l'occurence, spatialite utilise un R-tree. Une illustration permet de se faire une rapide idée:
J'ai également mené des tests d'importation de données cartographiques brutes obtenues sur le site geofabrik. Ces données, au format SHP, sont des archives, segmentées par région de chaque pays, contenant différents segments: routes, parcs, lieu dits, bâtiments, etc. L'outil de ligne de commande ogr2ogr permet l'importation directe depuis ces fichiers vers une base de donnée spatialite ou PostGIS. Je n'ai pas encore trouvé d'utilisation concrète pour cet outil, mais il est nécessaire pour la création d'un service de covoiturage par exemple, ou pour importer la liste de boutique ou services publics environnants, ou meme pour créer un terrain en 3D.
Pour vérifier que Spatialite offre un gain de performances lors de requêtes spatiale, j'ai utilisé cette méthode:
select2 = lambda lng, lat, dist: "select id, AsText(geom) from points "+where2(lng, lat, dist)
where2 = lambda lng, lat, dist: " where PtDistWithin(geom, GeomFromText('POINT(%f %f)', 4326), %f, 0)"%(lng, lat, dist)
J'ai pu remarquer que ces requêtes retournent les points présents dans un petit cercle avec un temps de réponse rapide, malgré la quantité importante de points présents dans la table.
python
from random import random as rd
interp = lambda a, b, f: (b - a) * f + a # interp interpole entre 3.8 et 3.9
insert_this = [
(interp(3.8, 3.9, rd()), # rd() retourne un float entre 0 et 1
interp(43.5, 43.7, rd())
) for i in range (100000)] # 100k points
insert_this3 = ', '.join(["(GeomFromText('POINT(%f %f)',4326))"%a for a in insert_this])
print(insert_this3[:20])
with spatialite.connect('db.sqlite') as db:
db.execute("insert into points (geom) values "+insert_this3)
[SQL]
-- activer le SRID
UPDATE geometry_columns SET srid = 4326 WHERE f_table_name = 'points';
-- Creation de l'index spatial
select CreateSpatialIndex('points', 'geom')
[python]
# SELECT
# procédure spatialite pour la recherche de point contenus dans un cercle
where2 = lambda lng, lat, dist: " where PtDistWithin(geom, GeomFromText('POINT(%f %f)', 4326), %f, 0)"%(lng, lat, dist)
# Finalisation de la requete
select2 = lambda lng, lat, dist: "select id, AsText(geom) from points "+where2(lng, lat, dist)
Utilisation de OpenGL 3.3, GLFW, Bullet Physics, GLSL, Freetype
Création du "character controller"
C/C++
Outil de gestion et de catégorisation d'image et de vidéo.
Python/Pure JavaScript/SQLite/HTML
Utilisation des modules Flask et Dataset
Outil de catégorisation d'images et vidéo par catégorie.
Cet ouil me permet de retrouver rapidement des images et vidéos, afin de réaliser des montages d'impression et de repartager des vidéos sur les réseaux sociaux.
Utilisation d'OCR.
