From 3d25488c0dcb5aada993d309c2bf3ffef8407425 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Kristian=20H=C3=B8gsberg?= Date: Mon, 22 May 2006 20:17:26 -0400 Subject: [PATCH] Implement general polygon constraints. Also, replace ad-hoc ledge and ground constraints with polygons. --- akamaru.c | 254 +++++++++++++++++++++++++++++++++++++----------------- 1 file changed, 175 insertions(+), 79 deletions(-) diff --git a/akamaru.c b/akamaru.c index 14d0601..af0a0f1 100644 --- a/akamaru.c +++ b/akamaru.c @@ -11,8 +11,10 @@ * * TODO: * - * - Add code to add boxes - * - Add circle object + * - Add code to add boxes + * - Add circle object + * - Try out this idea: make constraint solver take mean of all + * corrections at the end instead of meaning as it goes. */ #include @@ -20,6 +22,7 @@ #include #include #include +#include #include #include @@ -37,6 +40,7 @@ struct _xy_pair { typedef struct _Object Object; typedef struct _Stick Stick; typedef struct _String String; +typedef struct _Polygon Polygon; typedef struct _Offset Offset; typedef struct _Model Model; @@ -66,6 +70,13 @@ struct _Offset { int dx, dy; }; +struct _Polygon { + int num_points; + Point *points; + Vector *normals; + int edge; +}; + struct _Model { int num_objects; Object *objects; @@ -75,6 +86,8 @@ struct _Model { String *strings; int num_offsets; Offset *offsets; + int num_polygons; + Polygon *polygons; double k; double friction; @@ -84,6 +97,75 @@ struct _Model { double theta; }; +static void +polygon_init (Polygon *p, int num_points, ...) +{ + double dx, dy, length; + int i, j; + va_list ap; + + /* Polygons are defined counter-clock-wise in a coordinate system + * with the y-axis pointing down. */ + + va_start (ap, num_points); + p->num_points = num_points; + p->points = g_new (Point, num_points); + + for (i = 0; i < num_points; i++) { + p->points[i].x = va_arg (ap, double); + p->points[i].y = va_arg (ap, double); + } + va_end (ap); + + p->normals = g_new (Vector, p->num_points); + /* Compute outward pointing normals. p->normals[i] is the normal + * for the edged between p->points[i] and p->points[i + 1]. */ + for (i = 0; i < p->num_points; i++) { + j = (i + 1) % p->num_points; + dx = p->points[j].x - p->points[i].x; + dy = p->points[j].y - p->points[i].y; + length = sqrt (dx * dx + dy * dy); + p->normals[i].x = -dy / length; + p->normals[i].y = dx / length; + } +} + +static void +polygon_init_diamond (Polygon *polygon, double x, double y) +{ + return polygon_init (polygon, 5, + x, y, + x + 10, y + 40, + x + 90, y + 40, + x + 100, y, + x + 50, y - 20); +} + +static void +polygon_init_rectangle (Polygon *polygon, double x0, double y0, + double x1, double y1) +{ + return polygon_init (polygon, 4, x0, y0, x0, y1, x1, y1, x1, y0); +} + +static void +model_init_polygons (Model *model) +{ + const int num_polygons = 5; + + model->polygons = g_new (Polygon, num_polygons); + polygon_init_diamond (&model->polygons[0], 250, 300); + polygon_init_diamond (&model->polygons[1], 400, 150); + polygon_init_rectangle (&model->polygons[2], -100, 200, 200, 250); + polygon_init_rectangle (&model->polygons[3], -200, ground_level, + 1200, ground_level + 400); + + polygon_init_rectangle (&model->polygons[4], 300, 320, 400, 350); + + + model->num_polygons = num_polygons; +} + static void model_init_snake (Model *model) { @@ -91,14 +173,12 @@ model_init_snake (Model *model) const int num_sticks = num_objects * 2 - 3; int i; + memset (model, 0, sizeof *model); model->objects = g_new (Object, num_objects); model->num_objects = num_objects; model->sticks = g_new (Stick, num_sticks); model->num_sticks = num_sticks; - model->strings = NULL; - model->num_strings = 0; - model->offsets = NULL; - model->num_offsets = 0; + model_init_polygons (model); for (i = 0; i < num_objects; i++) { model->objects[i].position.x = random() % 200 + 20; @@ -126,17 +206,15 @@ model_init_rope (Model *model) { const int num_objects = 20; const int num_sticks = num_objects - 1; - const int stick_length = 5; + const int stick_length = 10; int i; + memset (model, 0, sizeof *model); model->objects = g_new (Object, num_objects); model->num_objects = num_objects; model->sticks = g_new (Stick, num_sticks); model->num_sticks = num_sticks; - model->strings = NULL; - model->num_strings = 0; - model->offsets = NULL; - model->num_offsets = 0; + model_init_polygons (model); for (i = 0; i < num_objects; i++) { model->objects[i].position.x = 200; @@ -166,14 +244,14 @@ model_init_curtain (Model *model) double x, y; int i, j, index, stick_index; + memset (model, 0, sizeof *model); model->objects = g_new (Object, num_objects); model->num_objects = num_objects; model->sticks = g_new (Stick, num_sticks); model->num_sticks = num_sticks; - model->strings = NULL; - model->num_strings = 0; model->offsets = g_new (Offset, num_ropes - 1); model->num_offsets = num_ropes - 1; + model_init_polygons (model); for (i = 0; i < num_ropes; i++) { for (j = 0; j < num_rope_objects; j++) { @@ -217,14 +295,14 @@ model_init_grid (Model *model) double x, y; int i, j, index, string_index; + memset (model, 0, sizeof *model); model->objects = g_new (Object, num_objects); model->num_objects = num_objects; - model->sticks = NULL; - model->num_sticks = 0; model->strings = g_new (String, num_strings); model->num_strings = num_strings; model->offsets = g_new (Offset, num_ropes - 1); model->num_offsets = num_ropes - 1; + model_init_polygons (model); for (i = 0; i < num_ropes; i++) { for (j = 0; j < num_rope_objects; j++) { @@ -267,17 +345,10 @@ static void model_fini (Model *model) { g_free (model->objects); - model->objects = NULL; - model->num_objects = 0; g_free (model->sticks); - model->sticks = NULL; - model->sticks = 0; g_free (model->strings); - model->strings = NULL; - model->strings = 0; g_free (model->offsets); - model->offsets = NULL; - model->num_offsets = 0; + memset (model, 0, sizeof *model); } static void @@ -304,9 +375,9 @@ model_integrate (Model *model, double step) y = o->position.y; o->position.x = - x + (x - o->previous_position.x) + o->force.x * step * step; + x + 0.9 * (x - o->previous_position.x) + o->force.x * step * step; o->position.y = - y + (y - o->previous_position.y) + o->force.y * step * step; + y + 0.9 * (y - o->previous_position.y) + o->force.y * step * step; o->previous_position.x = x; o->previous_position.y = y; @@ -336,8 +407,67 @@ estimate_distance (double dx, double dy, double r) #endif } +static int +polygon_contains_point (Polygon *polygon, Point *point) +{ + int i; + double dx, dy; + + for (i = 0; i < polygon->num_points; i++) { + dx = point->x - polygon->points[i].x; + dy = point->y - polygon->points[i].y; + + if (polygon->normals[i].x * dx + polygon->normals[i].y * dy >= 0) + return FALSE; + } + + return TRUE; +} + +static void +polygon_reflect_object (Polygon *polygon, Object *object) +{ + int i, edge; + double d, distance; + Vector *n; + + distance = -1000; + for (i = 0; i < polygon->num_points; i++) { + d = polygon->normals[i].x * (object->position.x - polygon->points[i].x) + + polygon->normals[i].y * (object->position.y - polygon->points[i].y); + + if (d > distance) { + distance = d; + edge = i; + polygon->edge = i; + n = &polygon->normals[i]; + } + } + + object->position.x -= (1 + elasticity) * distance * n->x; + object->position.y -= (1 + elasticity) * distance * n->y; + + distance = + n->x * (object->previous_position.x - polygon->points[edge].x) + + n->y * (object->previous_position.y - polygon->points[edge].y); + + object->previous_position.x -= (1 + elasticity) * distance * n->x; + object->previous_position.y -= (1 + elasticity) * distance * n->y; +} + static void -model_constrain (Model *model, double step) +model_constrain_polygon (Model *model, Polygon *polygon) +{ + int i; + + for (i = 0; i < model->num_objects; i++) { + if (polygon_contains_point (polygon, &model->objects[i].position)) + polygon_reflect_object (polygon, &model->objects[i]); + } +} + +static void +model_constrain (Model *model) { double dx, dy, x, y, distance, fraction; int i; @@ -350,40 +480,6 @@ model_constrain (Model *model, double step) model->anchor_object->previous_position.y = model->anchor_position.y; } - /* FIXME: this should be "is point inside box" test instead. Figure - * out from previous_position which edge the point has passed - * through and reflect in that. */ - for (i = 0; i < model->num_objects; i++) { - x = model->objects[i].position.x; - y = model->objects[i].position.y; - if (box_top - edge_fuzz <= y && - model->objects[i].previous_position.y <= box_top + edge_fuzz && - x < box_left) { - model->objects[i].position.y = box_top - (y - box_top) * elasticity; - model->objects[i].previous_position.y = - box_top - (model->objects[i].previous_position.y - box_top) * elasticity; - } - } - - /* Ground collision detection constraints. This puts a ground level - * in to make sure the points don't fall off the screen. */ - for (i = 0; i < model->num_objects; i++) { - x = model->objects[i].position.x; - y = model->objects[i].position.y; - - if (model->objects[i].position.y > ground_level) { - model->objects[i].position.y = - ground_level - (model->objects[i].position.y - ground_level) * elasticity; - model->objects[i].previous_position.y = - ground_level - (model->objects[i].previous_position.y - ground_level) * elasticity; - - /* Friction on impact */ - model->objects[i].position.x = - model->objects[i].position.x * (1 - ground_friction) + - model->objects[i].previous_position.x * ground_friction; - } - } - /* Offset constraints. */ for (i = 0; i < model->num_offsets; i++) { x = (model->offsets[i].a->position.x + model->offsets[i].b->position.x) / 2; @@ -423,6 +519,10 @@ model_constrain (Model *model, double step) model->sticks[i].b->position.x = x + dx * (1 - fraction); model->sticks[i].b->position.y = y + dy * (1 - fraction); } + + /* Polygon constraints. */ + for (i = 0; i < model->num_polygons; i++) + model_constrain_polygon (model, &model->polygons[i]); } static void @@ -434,7 +534,7 @@ model_step (Model *model, double delta_t) model_integrate (model, delta_t); for (i = 0; i < 100; i++) - model_constrain (model, delta_t); + model_constrain (model); model->theta += delta_t; } @@ -549,25 +649,22 @@ draw_offsets (cairo_t *cr, } static void -draw_constraints (cairo_t *cr, - Model *model, - Color *color) +draw_polygons (cairo_t *cr, Model *model, Color *color) { - cairo_set_source_rgba (cr, color->red, color->green, color->blue, 0.5); - - cairo_move_to (cr, 0, ground_level); - cairo_line_to (cr, 1500, ground_level); - cairo_line_to (cr, 1500, ground_level + 10); - cairo_line_to (cr, 0, ground_level + 10); - cairo_close_path (cr); + Polygon *p; + int i, j; - cairo_move_to (cr, 0, box_top); - cairo_line_to (cr, box_left, box_top); - cairo_line_to (cr, box_left, box_bottom); - cairo_line_to (cr, 0, box_bottom); - cairo_close_path (cr); + for (i = 0; i < model->num_polygons; i++) { + p = &model->polygons[i]; + cairo_set_source_rgba (cr, color->red, color->green, color->blue, 0.4); + + for (j = 0; j < p->num_points; j++) + cairo_line_to (cr, p->points[j].x, p->points[j].y); + cairo_close_path (cr); + } cairo_fill (cr); + } static void @@ -608,7 +705,7 @@ expose_event (GtkWidget *widget, cairo_set_source_rgb (cr, 1, 1, 1); cairo_paint (cr); - draw_constraints (cr, closure->model, &red); + draw_polygons (cr, closure->model, &blue); draw_sticks (cr, closure->model, &black); draw_strings (cr, closure->model, &green); draw_offsets (cr, closure->model, &blue); @@ -825,7 +922,6 @@ static gint timeout_callback (gpointer data) { Closure *closure = data; - int i; model_step (closure->model, 1); @@ -877,7 +973,7 @@ main (int argc, char *argv[]) closure.model = &model; closure.frame_count = 0; gettimeofday (&closure.start, NULL); - g_timeout_add (40, timeout_callback, &closure); + g_timeout_add (50, timeout_callback, &closure); gtk_main (); return 0; -- 2.43.0