X-Git-Url: https://git.cworth.org/git?p=akamaru;a=blobdiff_plain;f=akamaru.c;h=d158f3e2da5b3728882025fb3ce9c3598def2aef;hp=f6375e8438666566e0e0b0c1a3d9443c0ff4c4d5;hb=4ea6cfd18613d299d62dc95a4d53161d89745935;hpb=3f5cdf3d255b9c1a5d96bb93b5e481787efe5547 diff --git a/akamaru.c b/akamaru.c index f6375e8..d158f3e 100644 --- a/akamaru.c +++ b/akamaru.c @@ -1,9 +1,4 @@ /* -*- mode: c; c-basic-offset: 2 -*- - * To compile: - * - * gcc -Wall -g $(pkg-config --cflags --libs gtk+-2.0 cairo) \ - * akamaru.c -o akamaru - * * See: * * http://en.wikipedia.org/wiki/Verlet_integration @@ -11,102 +6,184 @@ * * TODO: * - * - Fix box collision test - * - Add stick objects instead of hardcoding sticks - * - 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 -#include -#include -#include +#include +#include +#include +#include #include -const double stick_length = 30; -const double ground_friction = 0.1, ground_level = 400; -const double box_left = 200, box_top = 200, box_bottom = 210; +#include "akamaru.h" + const double elasticity = 0.7; -const double edge_fuzz = 1; +const double friction = 1; +const double gravity = 20; -typedef struct _xy_pair Point; -typedef struct _xy_pair Vector; -struct _xy_pair { - double x, y; -}; +void +object_init (Object *object, double x, double y, double mass) +{ + object->position.x = x; + object->position.y = y; + object->previous_position.x = x; + object->previous_position.y = y; + object->mass = mass; +} -typedef struct _Object Object; -typedef struct _Stick Stick; -typedef struct _Model Model; +void +spring_init (Spring *spring, Object *a, Object *b, double length) +{ + spring->a = a; + spring->b = b; + spring->length = length; +} -struct _Object { - Vector force; +void +offset_spring_init (OffsetSpring *spring, Object *a, Object *b, + double dx, double dy) +{ + spring->a = a; + spring->b = b; + spring->dx = dx; + spring->dy = dy; +} - Point position; - Point previous_position; - Vector velocity; +void +polygon_init (Polygon *p, int num_points, ...) +{ + double dx, dy, length; + int i, j; + va_list ap; - double mass; - double theta; -}; + /* Polygons are defined counter-clock-wise in a coordinate system + * with the y-axis pointing down. */ -struct _Stick { - Object *a, *b; -}; + va_start (ap, num_points); + p->num_points = num_points; + p->points = g_new (Point, num_points); -struct _Model { - int num_objects; - Object *objects; - int num_sticks; - Stick *sticks; - double k; - double friction; + 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; + } +} - Object *anchor_object; - Vector anchor_position; +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); +} - double theta; -}; +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 (Model *model) +void +model_fini (Model *model) { - const int num_objects = 20; - const int num_sticks = 40 - 3; int i; - model->objects = g_new (Object, num_objects); - model->num_objects = num_objects; - model->sticks = g_new (Stick, num_sticks); - model->num_sticks = num_sticks; - - for (i = 0; i < num_objects; i++) { - model->objects[i].position.x = 200; - model->objects[i].position.y = i * stick_length + 40; - model->objects[i].previous_position.x = 200; - model->objects[i].previous_position.y = i * stick_length + 40; - - if (i + 1 < num_objects) { - model->sticks[i * 2].a = &model->objects[i]; - model->sticks[i * 2].b = &model->objects[i + 1]; - } - if (i + 2 < num_objects) { - model->sticks[i * 2 + 1].a = &model->objects[i]; - model->sticks[i * 2 + 1].b = &model->objects[i + 2]; - } - } - - model->anchor_object = NULL; + g_free (model->objects); + g_free (model->sticks); + g_free (model->strings); + for (i = 0; i < model->num_offsets; i++) + g_free (model->offsets[i].objects); + g_free (model->springs); + g_free (model->offset_springs); + for (i = 0; i < model->num_polygons; i++) + g_free (model->polygons[i].points); + g_free (model->polygons); + + memset (model, 0, sizeof *model); } static void model_accumulate_forces (Model *model) { int i; + double x, y, dx, dy, distance, displacement; + Point middle; + Vector u, v; for (i = 0; i < model->num_objects; i++) { + /* Gravity */ model->objects[i].force.x = 0; - model->objects[i].force.y = 3; + model->objects[i].force.y = gravity * model->objects[i].mass; + + /* Friction */ + v.x = model->objects[i].position.x - model->objects[i].previous_position.x; + v.y = model->objects[i].position.y - model->objects[i].previous_position.y; + model->objects[i].force.x -= v.x * friction; + model->objects[i].force.y -= v.y * friction; + } + + for (i = 0; i < model->num_springs; i++) { + x = model->springs[i].a->position.x; + y = model->springs[i].a->position.y; + dx = model->springs[i].b->position.x - x; + dy = model->springs[i].b->position.y - y; + distance = sqrt (dx * dx + dy * dy); + u.x = dx / distance; + u.y = dy / distance; + displacement = distance - model->springs[i].length; + model->springs[i].a->force.x += u.x * model->k * displacement; + model->springs[i].a->force.y += u.y * model->k * displacement; + model->springs[i].b->force.x -= u.x * model->k * displacement; + model->springs[i].b->force.y -= u.y * model->k * displacement; + } + + for (i = 0; i < model->num_offset_springs; i++) { + middle.x = + (model->offset_springs[i].a->position.x + + model->offset_springs[i].b->position.x) / 2; + middle.y = + (model->offset_springs[i].a->position.y + + model->offset_springs[i].b->position.y) / 2; + + x = middle.x - model->offset_springs[i].dx / 2; + y = middle.y - model->offset_springs[i].dy / 2; + + dx = x - model->offset_springs[i].a->position.x; + dy = y - model->offset_springs[i].a->position.y; + + model->offset_springs[i].a->force.x += dx * model->k; + model->offset_springs[i].a->force.y += dy * model->k; + model->offset_springs[i].b->force.x -= dx * model->k; + model->offset_springs[i].b->force.y -= dy * model->k; + } + + for (i = 0; i < model->num_objects; i++) { + double f = + model->objects[i].force.x * model->objects[i].force.x + + model->objects[i].force.y * model->objects[i].force.y; + + if (f > 100000000) + abort(); } } @@ -132,10 +209,114 @@ model_integrate (Model *model, double step) } } +/* The square root in the distance computation for the string and + * stick constraints can be aproximated using Newton: + * + * distance = + * (model->sticks[i].length + + * (dx * dx + dy * dy) / model->sticks[i].length) / 2; + * + * This works really well, since the constraints aren't typically + * violated much. Thus, the distance is really close to the stick + * length, which then makes a good initial guess. However, the + * approximation seems to be slower that just calling sqrt()... + */ + +static inline double +estimate_distance (double dx, double dy, double r) +{ +#ifdef APPROXIMATE_SQUARE_ROOTS + return (r + (dx * dx + dy * dy) / r) / 2; +#else + return sqrt (dx * dx + dy * dy); +#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) { - double dx, dy, x, y, distance, fraction, squared; + 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_offset (Model *model, Offset *offset) +{ + double x, y; + int i; + + x = 0; + y = 0; + for (i = 0; i < offset->num_objects; i++) { + x += offset->objects[i]->position.x; + y += offset->objects[i]->position.y; + } + + x = x / offset->num_objects - offset->dx * (offset->num_objects - 1) / 2; + y = y / offset->num_objects - offset->dy * (offset->num_objects - 1) / 2; + + for (i = 0; i < offset->num_objects; i++) { + offset->objects[i]->position.x = x + offset->dx * i; + offset->objects[i]->position.y = y + offset->dy * i; + } +} + +static void +model_constrain (Model *model) +{ + double dx, dy, x, y, distance, fraction; int i; /* Anchor object constraint. */ @@ -146,82 +327,54 @@ 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; - } + /* String constraints. */ + for (i = 0; i < model->num_strings; i++) { + x = model->strings[i].a->position.x; + y = model->strings[i].a->position.y; + dx = model->strings[i].b->position.x - x; + dy = model->strings[i].b->position.y - y; + distance = estimate_distance (dx, dy, model->strings[i].length); + if (distance < model->strings[i].length) + continue; + fraction = (distance - model->strings[i].length) / distance / 2; + model->strings[i].a->position.x = x + dx * fraction; + model->strings[i].a->position.y = y + dy * fraction; + model->strings[i].b->position.x = x + dx * (1 - fraction); + model->strings[i].b->position.y = y + dy * (1 - fraction); } - /* 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; - } - } - -#if 1 /* Stick constraints. */ for (i = 0; i < model->num_sticks; i++) { x = model->sticks[i].a->position.x; y = model->sticks[i].a->position.y; dx = model->sticks[i].b->position.x - x; dy = model->sticks[i].b->position.y - y; - distance = sqrt (dx * dx + dy * dy); - fraction = (distance - stick_length) / distance / 2; + distance = estimate_distance (dx, dy, model->sticks[i].length); + fraction = (distance - model->sticks[i].length) / distance / 2; model->sticks[i].a->position.x = x + dx * fraction; model->sticks[i].a->position.y = y + dy * fraction; model->sticks[i].b->position.x = x + dx * (1 - fraction); model->sticks[i].b->position.y = y + dy * (1 - fraction); } -#else - /* Stick constraints, without square roots. */ - squared = stick_length * stick_length; - for (i = 0; i < model->num_objects - 1; i++) { - j = i + 1; - x = model->objects[i].position.x; - y = model->objects[i].position.y; - dx = model->objects[j].position.x - x; - dy = model->objects[j].position.y - y; - fraction = squared / (dx * dx + dy * dy + squared) - 0.5; - model->objects[i].position.x = x + dx * fraction; - model->objects[i].position.y = y + dy * fraction; - model->objects[j].position.x = x + dx * (1 - fraction); - model->objects[j].position.y = y + dy * (1 - fraction); - } -#endif + + /* Offset constraints. */ + for (i = 0; i < model->num_offsets; i++) + model_constrain_offset (model, &model->offsets[i]); + + /* Polygon constraints. */ + for (i = 0; i < model->num_polygons; i++) + model_constrain_polygon (model, &model->polygons[i]); } -static void +void model_step (Model *model, double delta_t) { int i; model_accumulate_forces (model); model_integrate (model, delta_t); - for (i = 0; i < 50; i++) - model_constrain (model, delta_t); + model_constrain (model); model->theta += delta_t; } @@ -237,7 +390,7 @@ object_distance (Object *object, double x, double y) return sqrt (dx*dx + dy*dy); } -static Object * +Object * model_find_nearest (Model *model, double x, double y) { Object *object; @@ -254,317 +407,3 @@ model_find_nearest (Model *model, double x, double y) return object; } - -typedef struct _Color Color; -struct _Color { - double red, green, blue; -}; - -static void -draw_star (cairo_t *cr, - gdouble cx, - gdouble cy, - double theta, - Color *color) -{ - const int spike_count = 5; - const int inner_radius = 2; - const int outer_radius = 4; - double x, y; - int i; - - cairo_set_source_rgba (cr, color->red, color->green, color->blue, 0.5); - cairo_new_path (cr); - for (i = 0; i < spike_count; i++) { - x = cx + cos ((i * 2) * M_PI / spike_count + theta) * inner_radius; - y = cy + sin ((i * 2) * M_PI / spike_count + theta) * inner_radius; - - if (i == 0) - cairo_move_to (cr, x, y); - else - cairo_line_to (cr, x, y); - - x = cx + cos ((i * 2 + 1) * M_PI / spike_count + theta) * outer_radius; - y = cy + sin ((i * 2 + 1) * M_PI / spike_count + theta) * outer_radius; - - cairo_line_to (cr, x, y); - } - cairo_fill (cr); -} - -static void -draw_lines (cairo_t *cr, - Model *model, - Color *color) -{ - int i; - - cairo_set_source_rgba (cr, color->red, color->green, color->blue, 0.5); - cairo_new_path (cr); - cairo_set_line_width (cr, 4); - cairo_set_line_join (cr, CAIRO_LINE_JOIN_ROUND); - cairo_set_line_cap (cr, CAIRO_LINE_CAP_ROUND); - - for (i = 0; i < model->num_objects; i++) { - cairo_line_to (cr, - model->objects[i].position.x, - model->objects[i].position.y); - } - - cairo_stroke (cr); -} - -static void -draw_constraints (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); - - 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); - - cairo_fill (cr); -} - -static Color blue = { 0, 0, 1 }; -static Color red = { 1, 0, 0 }; - -static gboolean -sproing_expose_event (GtkWidget *widget, - GdkEventExpose *event, - gpointer data) -{ - Model *model = data; - cairo_t *cr; - - cr = gdk_cairo_create (widget->window); - - cairo_set_source_rgb (cr, 1, 1, 1); - cairo_paint (cr); - - draw_constraints (cr, model, &red); - draw_lines (cr, model, &blue); - -#if 0 - for (i = 0; i < model->num_objects; i++) { - draw_star (widget, model->objects[i].position.x, - model->objects[i].position.y, model->objects[i].theta, &blue); - } -#endif - - cairo_destroy (cr); - - return TRUE; -} - -static gboolean -sproing_button_press_event (GtkWidget *widget, - GdkEventButton *event, - gpointer data) -{ - Model *model = data; - - if (event->button != 1) - return TRUE; - - model->anchor_position.x = event->x; - model->anchor_position.y = event->y; - model->anchor_object = model_find_nearest (model, event->x, event->y); - - return TRUE; -} - -static gboolean -sproing_button_release_event (GtkWidget *widget, - GdkEventButton *event, - gpointer data) -{ - Model *model = data; - - if ((event->state & GDK_BUTTON1_MASK) == 0) - return TRUE; - - model->anchor_object = NULL; - - return TRUE; -} - -static gboolean -sproing_motion_notify_event (GtkWidget *widget, - GdkEventMotion *event, - gpointer data) -{ - Model *model = data; - int x, y; - GdkModifierType state; - - gdk_window_get_pointer (event->window, &x, &y, &state); - - model->anchor_position.x = x + 0.5; - model->anchor_position.y = y + 0.5; - - return TRUE; -} - -static void -spring_constant_changed (GtkSpinButton *spinbutton, gpointer user_data) -{ - Model *model = user_data; - - model->k = gtk_spin_button_get_value (spinbutton); -} - -static void -friction_changed (GtkSpinButton *spinbutton, gpointer user_data) -{ - Model *model = user_data; - - model->friction = gtk_spin_button_get_value (spinbutton); -} - -static GtkWidget * -create_spinners (Model *model) -{ - GtkWidget *hbox; - GtkWidget *spinner, *label; - - hbox = gtk_hbox_new (FALSE, 8); - - label = gtk_label_new_with_mnemonic ("_Spring constant:"); - gtk_box_pack_start (GTK_BOX (hbox), label, FALSE, FALSE, 0); - spinner = gtk_spin_button_new_with_range (0.05, 30.00, 0.05); - gtk_label_set_mnemonic_widget (GTK_LABEL (label), spinner); - gtk_box_pack_start (GTK_BOX (hbox), spinner, FALSE, FALSE, 0); - gtk_spin_button_set_value (GTK_SPIN_BUTTON (spinner), model->k); - g_signal_connect (spinner, "value-changed", - G_CALLBACK (spring_constant_changed), model); - - label = gtk_label_new_with_mnemonic ("_Friction:"); - gtk_box_pack_start (GTK_BOX (hbox), label, FALSE, FALSE, 0); - spinner = gtk_spin_button_new_with_range (0.05, 15.00, 0.05); - gtk_label_set_mnemonic_widget (GTK_LABEL (label), spinner); - gtk_box_pack_start (GTK_BOX (hbox), spinner, FALSE, FALSE, 0); - gtk_spin_button_set_value (GTK_SPIN_BUTTON (spinner), model->friction); - g_signal_connect (spinner, "value-changed", - G_CALLBACK (friction_changed), model); - - return hbox; -} - -static GtkWidget * -create_window (Model *model) -{ - GtkWidget *window; - GtkWidget *frame; - GtkWidget *vbox; - GtkWidget *da; - GtkWidget *spinners; - - window = gtk_window_new (GTK_WINDOW_TOPLEVEL); - gtk_window_set_title (GTK_WINDOW (window), "Drawing Area"); - - g_signal_connect (window, "destroy", - G_CALLBACK (gtk_main_quit), &window); - - gtk_container_set_border_width (GTK_CONTAINER (window), 8); - - vbox = gtk_vbox_new (FALSE, 8); - gtk_container_set_border_width (GTK_CONTAINER (vbox), 8); - gtk_container_add (GTK_CONTAINER (window), vbox); - - /* - * Create the drawing area - */ - - frame = gtk_frame_new (NULL); - gtk_frame_set_shadow_type (GTK_FRAME (frame), GTK_SHADOW_IN); - gtk_box_pack_start (GTK_BOX (vbox), frame, TRUE, TRUE, 0); - - da = gtk_drawing_area_new (); - /* set a minimum size */ - gtk_widget_set_size_request (da, 600, 500); - - gtk_container_add (GTK_CONTAINER (frame), da); - - /* Signals used to handle backing pixmap */ - - g_signal_connect (da, "expose_event", - G_CALLBACK (sproing_expose_event), model); - - /* Event signals */ - - g_signal_connect (da, "motion_notify_event", - G_CALLBACK (sproing_motion_notify_event), model); - g_signal_connect (da, "button_press_event", - G_CALLBACK (sproing_button_press_event), model); - g_signal_connect (da, "button_release_event", - G_CALLBACK (sproing_button_release_event), model); - - /* Ask to receive events the drawing area doesn't normally - * subscribe to - */ - gtk_widget_set_events (da, gtk_widget_get_events (da) - | GDK_LEAVE_NOTIFY_MASK - | GDK_BUTTON_PRESS_MASK - | GDK_BUTTON_RELEASE_MASK - | GDK_POINTER_MOTION_MASK - | GDK_POINTER_MOTION_HINT_MASK); - - spinners = create_spinners (model); - gtk_box_pack_start (GTK_BOX (vbox), spinners, FALSE, FALSE, 0); - - return da; -} - -typedef struct _Closure Closure; -struct _Closure { - GtkWidget *drawing_area; - Model *model; - int i; -}; - -static gint -timeout_callback (gpointer data) -{ - Closure *closure = data; - int i; - - for (i = 0; i < 3; i++) - model_step (closure->model, 0.5); - - closure->i++; - if (closure->i == 1) { - gtk_widget_queue_draw (closure->drawing_area); - closure->i = 0; - } - - return TRUE; -} - -int -main (int argc, char *argv[]) -{ - Closure closure; - Model model; - - gtk_init (&argc, &argv); - model_init (&model); - closure.drawing_area = create_window (&model); - closure.i = 0; - gtk_widget_show_all (gtk_widget_get_toplevel (closure.drawing_area)); - closure.model = &model; - g_timeout_add (100, timeout_callback, &closure); - gtk_main (); - - return 0; -}