1 /* -*- mode: c; c-basic-offset: 2 -*-
4 * gcc -Wall -g $(pkg-config --cflags --libs gtk+-2.0 cairo) \
9 * http://en.wikipedia.org/wiki/Verlet_integration
10 * http://www.teknikus.dk/tj/gdc2001.htm
14 * - Add code to add boxes
16 * - Try out this idea: make constraint solver take mean of all
17 * corrections at the end instead of meaning as it goes.
22 #include <cairo-xlib.h>
29 const double ground_level = 500;
30 const double elasticity = 0.7;
32 typedef struct _xy_pair Point;
33 typedef struct _xy_pair Vector;
38 typedef struct _Object Object;
39 typedef struct _Stick Stick;
40 typedef struct _String String;
41 typedef struct _Polygon Polygon;
42 typedef struct _Offset Offset;
43 typedef struct _Model Model;
49 Point previous_position;
93 Object *anchor_object;
94 Vector anchor_position;
100 polygon_init (Polygon *p, int num_points, ...)
102 double dx, dy, length;
106 /* Polygons are defined counter-clock-wise in a coordinate system
107 * with the y-axis pointing down. */
109 va_start (ap, num_points);
110 p->num_points = num_points;
111 p->points = g_new (Point, num_points);
113 for (i = 0; i < num_points; i++) {
114 p->points[i].x = va_arg (ap, double);
115 p->points[i].y = va_arg (ap, double);
119 p->normals = g_new (Vector, p->num_points);
120 /* Compute outward pointing normals. p->normals[i] is the normal
121 * for the edged between p->points[i] and p->points[i + 1]. */
122 for (i = 0; i < p->num_points; i++) {
123 j = (i + 1) % p->num_points;
124 dx = p->points[j].x - p->points[i].x;
125 dy = p->points[j].y - p->points[i].y;
126 length = sqrt (dx * dx + dy * dy);
127 p->normals[i].x = -dy / length;
128 p->normals[i].y = dx / length;
133 polygon_init_diamond (Polygon *polygon, double x, double y)
135 return polygon_init (polygon, 5,
144 polygon_init_rectangle (Polygon *polygon, double x0, double y0,
145 double x1, double y1)
147 return polygon_init (polygon, 4, x0, y0, x0, y1, x1, y1, x1, y0);
151 model_init_polygons (Model *model)
153 const int num_polygons = 5;
155 model->polygons = g_new (Polygon, num_polygons);
156 polygon_init_diamond (&model->polygons[0], 250, 300);
157 polygon_init_diamond (&model->polygons[1], 400, 150);
158 polygon_init_rectangle (&model->polygons[2], -100, 200, 200, 250);
159 polygon_init_rectangle (&model->polygons[3], -200, ground_level,
160 1200, ground_level + 400);
162 polygon_init_rectangle (&model->polygons[4], 300, 320, 400, 350);
165 model->num_polygons = num_polygons;
169 model_init_snake (Model *model)
171 const int num_objects = 20;
172 const int num_sticks = num_objects * 2 - 3;
175 memset (model, 0, sizeof *model);
176 model->objects = g_new (Object, num_objects);
177 model->num_objects = num_objects;
178 model->sticks = g_new (Stick, num_sticks);
179 model->num_sticks = num_sticks;
180 model_init_polygons (model);
182 for (i = 0; i < num_objects; i++) {
183 model->objects[i].position.x = random() % 200 + 20;
184 model->objects[i].position.y = random() % 200 + 20;
185 model->objects[i].previous_position.x = random() % 200 + 20;
186 model->objects[i].previous_position.y = random() % 200 + 20;
188 if (i + 1 < num_objects) {
189 model->sticks[i * 2].a = &model->objects[i];
190 model->sticks[i * 2].b = &model->objects[i + 1];
191 model->sticks[i * 2].length = random() % 20 + 20;
193 if (i + 2 < num_objects) {
194 model->sticks[i * 2 + 1].a = &model->objects[i];
195 model->sticks[i * 2 + 1].b = &model->objects[i + 2];
196 model->sticks[i * 2 + 1].length = random() % 20 + 20;
200 model->anchor_object = NULL;
204 model_init_rope (Model *model)
206 const int num_objects = 20;
207 const int num_sticks = num_objects - 1;
208 const int stick_length = 10;
211 memset (model, 0, sizeof *model);
212 model->objects = g_new (Object, num_objects);
213 model->num_objects = num_objects;
214 model->sticks = g_new (Stick, num_sticks);
215 model->num_sticks = num_sticks;
216 model_init_polygons (model);
218 for (i = 0; i < num_objects; i++) {
219 model->objects[i].position.x = 200;
220 model->objects[i].position.y = 40 + i * stick_length;
221 model->objects[i].previous_position.x = 200;
222 model->objects[i].previous_position.y = 40 + i * stick_length;
224 if (i + 1 < num_objects) {
225 model->sticks[i].a = &model->objects[i];
226 model->sticks[i].b = &model->objects[i + 1];
227 model->sticks[i].length = stick_length;
231 model->anchor_object = NULL;
235 model_init_curtain (Model *model)
237 const int num_ropes = 5;
238 const int num_rope_objects = 15;
239 const int num_objects = num_ropes * num_rope_objects;
240 const int num_sticks = num_ropes * (num_rope_objects - 1);
241 const int stick_length = 10;
242 const int rope_offset = 30;
244 int i, j, index, stick_index;
246 memset (model, 0, sizeof *model);
247 model->objects = g_new (Object, num_objects);
248 model->num_objects = num_objects;
249 model->sticks = g_new (Stick, num_sticks);
250 model->num_sticks = num_sticks;
251 model->offsets = g_new (Offset, 1);
252 model->num_offsets = 1;
253 model_init_polygons (model);
255 model->offsets[0].num_objects = num_ropes;
256 model->offsets[0].objects = g_new (Object *, num_ropes);
257 model->offsets[0].dx = rope_offset;
258 model->offsets[0].dy = 0;
260 for (i = 0; i < num_ropes; i++) {
261 for (j = 0; j < num_rope_objects; j++) {
262 x = 200 + i * rope_offset;
263 y = 40 + j * stick_length;
264 index = i * num_rope_objects + j;
265 model->objects[index].position.x = x;
266 model->objects[index].position.y = y;
267 model->objects[index].previous_position.x = x;
268 model->objects[index].previous_position.y = y;
270 if (j + 1 < num_rope_objects) {
271 stick_index = i * (num_rope_objects - 1) + j;
272 model->sticks[stick_index].a = &model->objects[index];
273 model->sticks[stick_index].b = &model->objects[index + 1];
274 model->sticks[stick_index].length = stick_length;
278 model->offsets[0].objects[i] = &model->objects[i * num_rope_objects];
281 model->anchor_object = NULL;
285 model_init_grid (Model *model)
287 const int num_ropes = 10;
288 const int num_rope_objects = 10;
289 const int num_objects = num_ropes * num_rope_objects;
290 const int num_strings = num_ropes * (num_rope_objects - 1) +
291 (num_ropes - 1) * num_rope_objects;
292 const int string_length = 10;
293 const int rope_offset = 10;
295 int i, j, index, string_index;
297 memset (model, 0, sizeof *model);
298 model->objects = g_new (Object, num_objects);
299 model->num_objects = num_objects;
300 model->strings = g_new (String, num_strings);
301 model->num_strings = num_strings;
302 model->offsets = g_new (Offset, 1);
303 model->num_offsets = 1;
304 model_init_polygons (model);
306 model->offsets[0].num_objects = num_ropes;
307 model->offsets[0].objects = g_new (Object *, num_ropes);
308 model->offsets[0].dx = rope_offset;
309 model->offsets[0].dy = 0;
311 for (i = 0; i < num_ropes; i++) {
312 for (j = 0; j < num_rope_objects; j++) {
313 x = 200 + i * rope_offset;
314 y = 40 + j * string_length;
315 index = i * num_rope_objects + j;
316 model->objects[index].position.x = x;
317 model->objects[index].position.y = y;
318 model->objects[index].previous_position.x = x;
319 model->objects[index].previous_position.y = y;
321 if (i + 1 < num_ropes) {
322 string_index = i * num_rope_objects + j;
323 model->strings[string_index].a = &model->objects[index];
324 model->strings[string_index].b = &model->objects[index + num_rope_objects];
325 model->strings[string_index].length = string_length;
328 if (j + 1 < num_rope_objects) {
330 (num_ropes - 1) * num_rope_objects + i * (num_rope_objects - 1) + j;
331 model->strings[string_index].a = &model->objects[index];
332 model->strings[string_index].b = &model->objects[index + 1];
333 model->strings[string_index].length = string_length;
337 model->offsets[0].objects[i] = &model->objects[i * num_rope_objects];
340 model->anchor_object = NULL;
344 model_fini (Model *model)
346 g_free (model->objects);
347 g_free (model->sticks);
348 g_free (model->strings);
349 g_free (model->offsets);
350 memset (model, 0, sizeof *model);
354 model_accumulate_forces (Model *model)
358 for (i = 0; i < model->num_objects; i++) {
359 model->objects[i].force.x = 0;
360 model->objects[i].force.y = 3;
365 model_integrate (Model *model, double step)
371 for (i = 0; i < model->num_objects; i++) {
372 o = &model->objects[i];
377 x + 0.9 * (x - o->previous_position.x) + o->force.x * step * step;
379 y + 0.9 * (y - o->previous_position.y) + o->force.y * step * step;
381 o->previous_position.x = x;
382 o->previous_position.y = y;
386 /* The square root in the distance computation for the string and
387 * stick constraints can be aproximated using Newton:
390 * (model->sticks[i].length +
391 * (dx * dx + dy * dy) / model->sticks[i].length) / 2;
393 * This works really well, since the constraints aren't typically
394 * violated much. Thus, the distance is really close to the stick
395 * length, which then makes a good initial guess. However, the
396 * approximation seems to be slower that just calling sqrt()...
400 estimate_distance (double dx, double dy, double r)
402 #ifdef APPROXIMATE_SQUARE_ROOTS
403 return (r + (dx * dx + dy * dy) / r) / 2;
405 return sqrt (dx * dx + dy * dy);
410 polygon_contains_point (Polygon *polygon, Point *point)
415 for (i = 0; i < polygon->num_points; i++) {
416 dx = point->x - polygon->points[i].x;
417 dy = point->y - polygon->points[i].y;
419 if (polygon->normals[i].x * dx + polygon->normals[i].y * dy >= 0)
427 polygon_reflect_object (Polygon *polygon, Object *object)
434 for (i = 0; i < polygon->num_points; i++) {
435 d = polygon->normals[i].x * (object->position.x - polygon->points[i].x) +
436 polygon->normals[i].y * (object->position.y - polygon->points[i].y);
442 n = &polygon->normals[i];
446 object->position.x -= (1 + elasticity) * distance * n->x;
447 object->position.y -= (1 + elasticity) * distance * n->y;
450 n->x * (object->previous_position.x - polygon->points[edge].x) +
451 n->y * (object->previous_position.y - polygon->points[edge].y);
453 object->previous_position.x -= (1 + elasticity) * distance * n->x;
454 object->previous_position.y -= (1 + elasticity) * distance * n->y;
458 model_constrain_polygon (Model *model, Polygon *polygon)
462 for (i = 0; i < model->num_objects; i++) {
463 if (polygon_contains_point (polygon, &model->objects[i].position))
464 polygon_reflect_object (polygon, &model->objects[i]);
469 model_constrain_offset (Model *model, Offset *offset)
476 for (i = 0; i < offset->num_objects; i++) {
477 x += offset->objects[i]->position.x;
478 y += offset->objects[i]->position.y;
481 x = x / offset->num_objects - offset->dx * (offset->num_objects - 1) / 2;
482 y = y / offset->num_objects - offset->dy * (offset->num_objects - 1) / 2;
484 for (i = 0; i < offset->num_objects; i++) {
485 offset->objects[i]->position.x = x + offset->dx * i;
486 offset->objects[i]->position.y = y + offset->dy * i;
491 model_constrain (Model *model)
493 double dx, dy, x, y, distance, fraction;
496 /* Anchor object constraint. */
497 if (model->anchor_object != NULL) {
498 model->anchor_object->position.x = model->anchor_position.x;
499 model->anchor_object->position.y = model->anchor_position.y;
500 model->anchor_object->previous_position.x = model->anchor_position.x;
501 model->anchor_object->previous_position.y = model->anchor_position.y;
504 /* String constraints. */
505 for (i = 0; i < model->num_strings; i++) {
506 x = model->strings[i].a->position.x;
507 y = model->strings[i].a->position.y;
508 dx = model->strings[i].b->position.x - x;
509 dy = model->strings[i].b->position.y - y;
510 distance = estimate_distance (dx, dy, model->strings[i].length);
511 if (distance < model->strings[i].length)
513 fraction = (distance - model->strings[i].length) / distance / 2;
514 model->strings[i].a->position.x = x + dx * fraction;
515 model->strings[i].a->position.y = y + dy * fraction;
516 model->strings[i].b->position.x = x + dx * (1 - fraction);
517 model->strings[i].b->position.y = y + dy * (1 - fraction);
520 /* Stick constraints. */
521 for (i = 0; i < model->num_sticks; i++) {
522 x = model->sticks[i].a->position.x;
523 y = model->sticks[i].a->position.y;
524 dx = model->sticks[i].b->position.x - x;
525 dy = model->sticks[i].b->position.y - y;
526 distance = estimate_distance (dx, dy, model->sticks[i].length);
527 fraction = (distance - model->sticks[i].length) / distance / 2;
528 model->sticks[i].a->position.x = x + dx * fraction;
529 model->sticks[i].a->position.y = y + dy * fraction;
530 model->sticks[i].b->position.x = x + dx * (1 - fraction);
531 model->sticks[i].b->position.y = y + dy * (1 - fraction);
534 /* Offset constraints. */
535 for (i = 0; i < model->num_offsets; i++)
536 model_constrain_offset (model, &model->offsets[i]);
538 /* Polygon constraints. */
539 for (i = 0; i < model->num_polygons; i++)
540 model_constrain_polygon (model, &model->polygons[i]);
544 model_step (Model *model, double delta_t)
548 model_accumulate_forces (model);
549 model_integrate (model, delta_t);
551 for (i = 0; i < 500; i++)
552 model_constrain (model);
554 model->theta += delta_t;
558 object_distance (Object *object, double x, double y)
562 dx = object->position.x - x;
563 dy = object->position.y - y;
565 return sqrt (dx*dx + dy*dy);
569 model_find_nearest (Model *model, double x, double y)
572 double distance, min_distance;
575 for (i = 0; i < model->num_objects; i++) {
576 distance = object_distance (&model->objects[i], x, y);
577 if (i == 0 || distance < min_distance) {
578 min_distance = distance;
579 object = &model->objects[i];
586 typedef struct _Color Color;
588 double red, green, blue;
592 draw_sticks (cairo_t *cr,
598 cairo_set_source_rgba (cr, color->red, color->green, color->blue, 1);
600 cairo_set_line_width (cr, 2);
601 cairo_set_line_join (cr, CAIRO_LINE_JOIN_ROUND);
602 cairo_set_line_cap (cr, CAIRO_LINE_CAP_ROUND);
604 for (i = 0; i < model->num_sticks; i++) {
606 model->sticks[i].a->position.x,
607 model->sticks[i].a->position.y);
609 model->sticks[i].b->position.x,
610 model->sticks[i].b->position.y);
617 draw_strings (cairo_t *cr,
623 cairo_set_source_rgba (cr, color->red, color->green, color->blue, 1);
625 cairo_set_line_width (cr, 1);
626 cairo_set_line_join (cr, CAIRO_LINE_JOIN_ROUND);
627 cairo_set_line_cap (cr, CAIRO_LINE_CAP_ROUND);
629 for (i = 0; i < model->num_strings; i++) {
631 model->strings[i].a->position.x,
632 model->strings[i].a->position.y);
634 model->strings[i].b->position.x,
635 model->strings[i].b->position.y);
642 draw_offsets (cairo_t *cr,
648 cairo_set_source_rgba (cr, color->red, color->green, color->blue, 0.5);
650 cairo_set_line_width (cr, 4);
651 cairo_set_line_join (cr, CAIRO_LINE_JOIN_ROUND);
652 cairo_set_line_cap (cr, CAIRO_LINE_CAP_ROUND);
654 for (i = 0; i < model->num_offsets; i++) {
655 for (j = 0; j < model->offsets[i].num_objects; j++) {
657 model->offsets[i].objects[j]->position.x,
658 model->offsets[i].objects[j]->position.y);
666 draw_polygons (cairo_t *cr, Model *model, Color *color)
671 for (i = 0; i < model->num_polygons; i++) {
672 p = &model->polygons[i];
673 cairo_set_source_rgba (cr, color->red, color->green, color->blue, 0.4);
676 for (j = 0; j < p->num_points; j++)
677 cairo_line_to (cr, p->points[j].x, p->points[j].y);
678 cairo_close_path (cr);
685 draw_objects (cairo_t *cr, Model *model, Color *color)
689 for (i = 0; i < model->num_objects; i++) {
693 static Color blue = { 0, 0, 1 };
694 static Color green = { 0, 1, 0 };
695 static Color red = { 1, 0, 0 };
696 static Color black = { 0, 0, 0 };
697 static Color white = { 1, 1, 1 };
699 typedef struct _Closure Closure;
701 GtkWidget *drawing_area;
702 GtkWidget *fps_label;
706 struct timeval start;
710 draw_model (GtkWidget *widget, Model *model)
714 cr = gdk_cairo_create (widget->window);
716 cairo_set_source_rgb (cr, 1, 1, 1);
719 draw_polygons (cr, model, &blue);
720 draw_sticks (cr, model, &black);
721 draw_strings (cr, model, &green);
722 draw_offsets (cr, model, &blue);
723 draw_objects (cr, model, &white);
729 expose_event (GtkWidget *widget,
730 GdkEventExpose *event,
733 Closure *closure = data;
735 draw_model (widget, closure->model);
741 button_press_event (GtkWidget *widget,
742 GdkEventButton *event,
745 Closure *closure = data;
747 if (event->button != 1)
750 closure->model->anchor_position.x = event->x;
751 closure->model->anchor_position.y = event->y;
752 closure->model->anchor_object = model_find_nearest (closure->model,
759 button_release_event (GtkWidget *widget,
760 GdkEventButton *event,
763 Closure *closure = data;
765 if ((event->state & GDK_BUTTON1_MASK) == 0)
768 closure->model->anchor_object = NULL;
774 motion_notify_event (GtkWidget *widget,
775 GdkEventMotion *event,
778 Closure *closure = data;
780 GdkModifierType state;
782 gdk_window_get_pointer (event->window, &x, &y, &state);
784 closure->model->anchor_position.x = x + 0.5;
785 closure->model->anchor_position.y = y + 0.5;
790 typedef void (*ModelInitFunc) (Model *model);
793 model_changed (GtkComboBox *combo, gpointer user_data)
795 Closure *closure = user_data;
797 GtkTreeModel *tree_model;
801 tree_model = gtk_combo_box_get_model (combo);
802 if (!gtk_combo_box_get_active_iter (combo, &iter))
805 gtk_tree_model_get (tree_model, &iter, 0, &name, 1, &init, -1);
807 model_fini (closure->model);
808 (*init) (closure->model);
811 static GtkTreeModel *
812 create_model_store (void)
818 { "Rope", model_init_rope },
819 { "Snake", model_init_snake },
820 { "Curtain", model_init_curtain },
821 { "Grid", model_init_grid }
828 store = gtk_tree_store_new (2, G_TYPE_STRING, G_TYPE_POINTER);
830 for (i = 0; i < G_N_ELEMENTS(models); i++) {
831 gtk_tree_store_append (store, &iter, NULL);
832 gtk_tree_store_set (store, &iter,
833 0, models[i].name, 1, models[i].init, -1);
836 return GTK_TREE_MODEL (store);
841 create_model_combo (Closure *closure)
844 GtkWidget *combo, *label;
846 GtkCellRenderer *renderer;
848 hbox = gtk_hbox_new (FALSE, 8);
850 label = gtk_label_new_with_mnemonic ("_Model:");
851 gtk_box_pack_start (GTK_BOX (hbox), label, FALSE, FALSE, 0);
853 store = create_model_store ();
854 combo = gtk_combo_box_new_with_model (store);
855 gtk_combo_box_set_active (GTK_COMBO_BOX (combo), 0);
856 g_object_unref (store);
858 renderer = gtk_cell_renderer_text_new ();
859 gtk_cell_layout_pack_start (GTK_CELL_LAYOUT (combo), renderer, TRUE);
860 gtk_cell_layout_set_attributes (GTK_CELL_LAYOUT (combo), renderer,
864 gtk_label_set_mnemonic_widget (GTK_LABEL (label), combo);
865 gtk_box_pack_start (GTK_BOX (hbox), combo, FALSE, FALSE, 0);
866 g_signal_connect (combo, "changed",
867 G_CALLBACK (model_changed), closure);
869 label = gtk_label_new ("Frames per second: 0");
870 gtk_box_pack_start (GTK_BOX (hbox), label, FALSE, FALSE, 0);
872 closure->fps_label = label;
878 create_window (Closure *closure)
884 GtkWidget *model_combo;
886 window = gtk_window_new (GTK_WINDOW_TOPLEVEL);
887 gtk_window_set_title (GTK_WINDOW (window), "Akamaru");
889 g_signal_connect (window, "destroy",
890 G_CALLBACK (gtk_main_quit), &window);
892 gtk_container_set_border_width (GTK_CONTAINER (window), 8);
894 vbox = gtk_vbox_new (FALSE, 8);
895 gtk_container_set_border_width (GTK_CONTAINER (vbox), 8);
896 gtk_container_add (GTK_CONTAINER (window), vbox);
899 * Create the drawing area
902 frame = gtk_frame_new (NULL);
903 gtk_frame_set_shadow_type (GTK_FRAME (frame), GTK_SHADOW_IN);
904 gtk_box_pack_start (GTK_BOX (vbox), frame, TRUE, TRUE, 0);
906 da = gtk_drawing_area_new ();
907 /* set a minimum size */
908 gtk_widget_set_size_request (da, 200, 200);
910 gtk_container_add (GTK_CONTAINER (frame), da);
912 /* Signals used to handle backing pixmap */
914 g_signal_connect (da, "expose_event",
915 G_CALLBACK (expose_event), closure);
919 g_signal_connect (da, "motion_notify_event",
920 G_CALLBACK (motion_notify_event), closure);
921 g_signal_connect (da, "button_press_event",
922 G_CALLBACK (button_press_event), closure);
923 g_signal_connect (da, "button_release_event",
924 G_CALLBACK (button_release_event), closure);
926 /* Ask to receive events the drawing area doesn't normally
929 gtk_widget_set_events (da, gtk_widget_get_events (da)
930 | GDK_LEAVE_NOTIFY_MASK
931 | GDK_BUTTON_PRESS_MASK
932 | GDK_BUTTON_RELEASE_MASK
933 | GDK_POINTER_MOTION_MASK
934 | GDK_POINTER_MOTION_HINT_MASK);
936 model_combo = create_model_combo (closure);
937 gtk_box_pack_start (GTK_BOX (vbox), model_combo, FALSE, FALSE, 0);
939 closure->drawing_area = da;
943 timeout_callback (gpointer data)
945 Closure *closure = data;
947 model_step (closure->model, 1);
950 if (closure->i == 1) {
951 gtk_widget_queue_draw (closure->drawing_area);
953 closure->frame_count++;
956 if (closure->frame_count == 200) {
957 struct timeval end, elapsed;
961 closure->frame_count = 0;
962 gettimeofday (&end, NULL);
963 if (closure->start.tv_usec > end.tv_usec) {
964 end.tv_usec += 1000000;
968 elapsed.tv_usec = end.tv_usec - closure->start.tv_usec;
969 elapsed.tv_sec = end.tv_sec - closure->start.tv_sec;
971 total = elapsed.tv_sec + ((double) elapsed.tv_usec / 1e6);
975 closure->start = end;
976 snprintf (text, sizeof text, "Frames per second: %.2f", 200 / total);
977 gtk_label_set_text (GTK_LABEL (closure->fps_label), text);
984 main (int argc, char *argv[])
989 gtk_init (&argc, &argv);
990 model_init_rope (&model);
991 create_window (&closure);
993 gtk_widget_show_all (gtk_widget_get_toplevel (closure.drawing_area));
994 closure.model = &model;
995 closure.frame_count = 0;
996 gettimeofday (&closure.start, NULL);
997 g_timeout_add (100, timeout_callback, &closure);