Disques de Poisson avec triangulation de Delaunay
Disques de poisson, distance pondérée avec un bruit de perlin
Erosion avec midpoint displacement et flou gaussien
Génération aléatoire de rues d'une petite ville
Bases de l'animation squelettale sous blender
Génération de l'intérieur d'un immeuble/batiment/maison
Zoning of online game world server
Génération de carte de jeu Dobble
Outil de recherche et de visualisation d'emoji UTF8
Catégorisation de comptabilité personnelle à partir de fichier banquaire CSV
Génération de carte de jeu Dobble
Labground est une collection de proof-of-concept et expériences concernant la programmation orientée jeu vidéo, sur lequel j'ai travaillé indépendamment avant ma période d'alternance. J’utilise principalement C++ 11/14/17, avec SFML pour l’audio et l’affichage, et box2d pour la physique.
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)
Zonas.free.fr est mon petit site personnel que j'entretiens depuis maintenant bientôt 10 ans.
Hébergé sur ftpperso chez free, l’accès y est totalement gratuit, et inclut 1 giga octet d'espace disque, un serveur web avec php5 et perl, et une base de données MySQL.
La mise en page est très épurée, et ne contient qu'un menu et un footer. Il n'y a pas (ou peu) de javascript et une police monospace est utilisée. Le site se charge très rapidement sur un smartphone.
J'y héberge des petits gadget:
La mise en page utilise parfois textile, une alternative a markdown qui permet de faire de la mise en page simple en texte brut.
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.
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 plutot réaliste. J'ai également pu exécuter cet algorithme dans un shader GLSL via OpenGL, afin de grandement accélerer son exécution.
C++, SFML
Afin de mieux simuler l'érosion des sols lors de la création de donnée d'altitude, j'ai trouvé un article sur cette méthode. Le midpoint diplacement est un point aléatoire entre 2 points. On crée plusieurs de ces points de facon récursive. On applique ensuite plusieurs flou gaussien, en combinant plusieurs "couches", avec des pondérations. Les différentes couches sont des flous gaussien, avec une taille de matrice de plus en plus grande (de plus en plus flou).
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
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)
C/C++
Utilisation de OpenGL 3.3, GLFW, Bullet Physics, GLSL, Freetype
Création du "character controller"
Python, pySFML
A partir d'une gestion matricielle et d'emojis, j'ai généré 2 jeux de cartes dobble.
Le premier jeu a 14 symboles par carte et contient 150 cartes.
Le deuxième jeu a 29 symboles par carte et contient 800 cartes mais je n'ai imprimé que les 50 premières.
Outil de gestion et de catégorisation d'image et de vidéo.
C++/Python/JS/HTML/Flask
2 versions existent, une version python SFML et une version web brython+flask. La version web est plus fastidieuse à mettre en place à cause de la gestion serveur et de brython, mais permet de lire les vidéo. La version SFML est plus flexible, ne peut pas lire de vidéo.
Python/JS/HTML
Recherche parmi les 1700 emoji standardisé UTF8 android/apple/etc
Python/HTML
Cet outil permet de résumer rapidement les entrées et sorties d'argent par mois
Lors de mon alternance j’ai implémenté un éditeur simplifié de circuit de gestion de dossier. J’ai utilise SVG.js, python+Flask, et javascript. Ces circuits sont exportables en BPMN pour une édition plus approfondie si c’est le désir du client.
(Une version HTML de ce fichier permet de visualiser les vidéos)
Dans le but de réaliser un jeu vidéo à géométrie procédurale, j'ai exploré différents algorithmes et développé des outils, dans le but d'apprendre et d'expérimenter la faisabilité technique du projet.