Allegro.cc Forums » Game Design & Concepts » Voronoi Tesselation & Delaunay Graph

 This thread is locked; no one can reply to it.
 Voronoi Tesselation & Delaunay Graph
 Evert Member #794 November 2000 For a game I'm planning to work on I want to have a playing field (2D) that is build up out of a simple tiling. Don't ask me why but for this game I want to generate the tiling from a set of vertices using Voronoi tesselation to generate the polygons. After a few hours of thinking and typing I ended up with the following piece of (ugly and somewhat lengthy) code as a first draft: [code]#include #include typedef struct { double x, y; } SITE; typedef struct { double xc, yc; double x1, y1; double x2, y2; double dx, dy; } EDGE; typedef struct { EDGE *edges; int num_edges; int max_edges; } EDGE_LIST; double scale = 50; SITE sites[] = { {1.2, 0.0}, {-1.1, 0.0}, {0.0,0.0},{1.0, 2.0}, {-1.0, -2.0} }; int red, white, blue, green, black; void draw_sites(SITE *sites, int num_sites) { int n; for (n=0; nnum_edges >= edge_list->max_edges) { edge_list->max_edges = 2*edge_list->max_edges + 1; edge_list->edges = realloc(edge_list->edges, edge_list->max_edges*sizeof *(edge_list->edges)); } edge_list->edges[edge_list->num_edges] = *edge; edge_list->num_edges++; } void compute_edges(SITE *sites, int num_sites, EDGE_LIST *edge_list, int *num_nn, int **site_nn) { EDGE edge; int n, n2; int c; /* Compute edges for each pair of vertices */ for (n=0; nnum_edges; n++) { for (c=0; cnum_edges; c++) if (c!=n) { double t1 = 0.0, t2 = 0.0; double x, y, dx, dy, dx2, dy2; double vx, vy, wx, wy; double wvx, wvy, rx, ry; double det, invdet; /* Find intersection point */ vx = edge_list->edges[n].dx; vy = edge_list->edges[n].dy; wx = edge_list->edges[c].dx; wy = edge_list->edges[c].dy; rx = edge_list->edges[c].xc - edge_list->edges[n].xc; ry = edge_list->edges[c].yc - edge_list->edges[n].yc; /* Make sure that the direction vectors point to a common point */ if (vx*rx + vy*ry < 0) { vx = -vx; vy = -vy; } if (wx*rx + wy*ry > 0) { wx = -wx; wy = -wy; } /* Determinant of the matrix for (t t'); nescessary to invert the * matrix */ det = wx*vy - wy*vx; if (fabs(det) > 0.0) { invdet = 1.0/det; t2 = -(vy*rx - vx*ry) * invdet; t1 = -(wy*rx - wx*ry) * invdet; } else { t1 = t2 = 0; } x = edge_list->edges[n].xc + t1*vx; y = edge_list->edges[n].yc + t1*vy; /* Determine where to intersect */ dx = edge_list->edges[n].x1 - edge_list->edges[n].xc; dy = edge_list->edges[n].y1 - edge_list->edges[n].yc; dx2 = x - edge_list->edges[n].xc; dy2 = y - edge_list->edges[n].yc; if ( dx2 * dx + dy2 * dy > 0) { if ( dx2*dx2 + dy2*dy2 < dx*dx + dy*dy) { edge_list->edges[n].x1 = x; edge_list->edges[n].y1 = y; } } else { dx = edge_list->edges[n].x2 - edge_list->edges[n].xc; dy = edge_list->edges[n].y2 - edge_list->edges[n].yc; if ( dx2*dx2 + dy2*dy2 < dx*dx + dy*dy) { edge_list->edges[n].x2 = x; edge_list->edges[n].y2 = y; } } dx = edge_list->edges[c].x1 - edge_list->edges[c].xc; dy = edge_list->edges[c].y1 - edge_list->edges[c].yc; } } } void draw_edges(EDGE_LIST *edge_list) { EDGE edge; int n; for (n=0; nnum_edges; n++) { edge = edge_list->edges[n]; line(screen, SCREEN_W/2 + scale * edge.x1, SCREEN_H/2 + scale * edge.y1, SCREEN_W/2 + scale * edge.x2, SCREEN_H/2 + scale * edge.y2, green); } for (n=0; nnum_edges; n++) { edge = edge_list->edges[n]; putpixel(screen, SCREEN_W/2 + scale * edge.xc, SCREEN_H/2 + scale * edge.yc, blue); putpixel(screen, SCREEN_W/2 + scale * edge.x1, SCREEN_H/2 + scale * edge.y1, black); putpixel(screen, SCREEN_W/2 + scale * edge.x2, SCREEN_H/2 + scale * edge.y2, black); } } /* Find nearest neighbours (points in a Dalaunay graph). * Idea: two points are nearest neighbours iff there is a circle through both * of them that does not has any other sites in its interior */ void find_neighbours(SITE *sites, int num_sites, int *num_nn, int **site_nn) { int a, b, n; double r, r1, r2, q1, q2; double x, y; double cx, cy; double nx, ny; double dx, dy; /* Clear lists of nearest neighbours */ memset(num_nn, 0, num_sites * sizeof *num_nn); for (n=0; n
 Rash Member #2,374 May 2002 I'm convinced that if Allegro.cc ever gets an official FAQ, it should make prominent mention of the comp.graphics.algorithms FAQ, as it often holds the solution to many of the complex questions asked here. In your case there is the following entry:http://cgafaq.info/wiki/Voronoi_and_Delaunay_Triangulation
 Inphernic Member #1,111 March 2001 Check out Triangle.If the triangle data is static, you could be cheap and just feed the executable your vertices and get triangles back. --ĸoтёнoк
 Go to: Allegro Development Installation, Setup & Configuration Allegro.cc Comments Off-Topic Ordeals The Depot Game Design & Concepts Programming Questions Recent Threads