2 * Copyright © 2012 Collabora, Ltd.
3 * Copyright © 2012 Rob Clark
5 * Permission to use, copy, modify, distribute, and sell this software and its
6 * documentation for any purpose is hereby granted without fee, provided that
7 * the above copyright notice appear in all copies and that both that copyright
8 * notice and this permission notice appear in supporting documentation, and
9 * that the name of the copyright holders not be used in advertising or
10 * publicity pertaining to distribution of the software without specific,
11 * written prior permission. The copyright holders make no representations
12 * about the suitability of this software for any purpose. It is provided "as
13 * is" without express or implied warranty.
15 * THE COPYRIGHT HOLDERS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
16 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
17 * EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY SPECIAL, INDIRECT OR
18 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
19 * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
20 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
24 /* cliptest: for debugging calculate_edges() function, which is copied
27 * clip box position: mouse left drag, keys: w a s d
28 * clip box size: mouse right drag, keys: i j k l
29 * surface orientation: mouse wheel, keys: n m
30 * surface transform disable key: r
47 #include <linux/input.h>
48 #include <wayland-client.h>
52 typedef float GLfloat;
58 float s; /* sin phi */
59 float c; /* cos phi */
63 struct weston_surface {
68 struct geometry *geometry;
72 weston_surface_to_global_float(struct weston_surface *surface,
73 GLfloat sx, GLfloat sy, GLfloat *x, GLfloat *y)
75 struct geometry *g = surface->geometry;
77 /* pure rotation around origin by sine and cosine */
78 *x = g->c * sx + g->s * sy;
79 *y = -g->s * sx + g->c * sy;
82 /* ---------------------- copied begins -----------------------*/
108 float_difference(GLfloat a, GLfloat b)
110 /* http://www.altdevblogaday.com/2012/02/22/comparing-floating-point-numbers-2012-edition/ */
111 static const GLfloat max_diff = 4.0f * FLT_MIN;
112 static const GLfloat max_rel_diff = 4.0e-5;
113 GLfloat diff = a - b;
114 GLfloat adiff = fabsf(diff);
116 if (adiff <= max_diff)
121 if (adiff <= (a > b ? a : b) * max_rel_diff)
127 /* A line segment (p1x, p1y)-(p2x, p2y) intersects the line x = x_arg.
128 * Compute the y coordinate of the intersection.
131 clip_intersect_y(GLfloat p1x, GLfloat p1y, GLfloat p2x, GLfloat p2y,
135 GLfloat diff = float_difference(p1x, p2x);
137 /* Practically vertical line segment, yet the end points have already
138 * been determined to be on different sides of the line. Therefore
139 * the line segment is part of the line and intersects everywhere.
140 * Return the end point, so we use the whole line segment.
145 a = (x_arg - p2x) / diff;
146 return p2y + (p1y - p2y) * a;
149 /* A line segment (p1x, p1y)-(p2x, p2y) intersects the line y = y_arg.
150 * Compute the x coordinate of the intersection.
153 clip_intersect_x(GLfloat p1x, GLfloat p1y, GLfloat p2x, GLfloat p2y,
157 GLfloat diff = float_difference(p1y, p2y);
159 /* Practically horizontal line segment, yet the end points have already
160 * been determined to be on different sides of the line. Therefore
161 * the line segment is part of the line and intersects everywhere.
162 * Return the end point, so we use the whole line segment.
167 a = (y_arg - p2y) / diff;
168 return p2x + (p1x - p2x) * a;
171 enum path_transition {
172 PATH_TRANSITION_OUT_TO_OUT = 0,
173 PATH_TRANSITION_OUT_TO_IN = 1,
174 PATH_TRANSITION_IN_TO_OUT = 2,
175 PATH_TRANSITION_IN_TO_IN = 3,
179 clip_append_vertex(struct clip_context *ctx, GLfloat x, GLfloat y)
181 *ctx->vertices.x++ = x;
182 *ctx->vertices.y++ = y;
185 static enum path_transition
186 path_transition_left_edge(struct clip_context *ctx, GLfloat x, GLfloat y)
188 return ((ctx->prev.x >= ctx->clip.x1) << 1) | (x >= ctx->clip.x1);
191 static enum path_transition
192 path_transition_right_edge(struct clip_context *ctx, GLfloat x, GLfloat y)
194 return ((ctx->prev.x < ctx->clip.x2) << 1) | (x < ctx->clip.x2);
197 static enum path_transition
198 path_transition_top_edge(struct clip_context *ctx, GLfloat x, GLfloat y)
200 return ((ctx->prev.y >= ctx->clip.y1) << 1) | (y >= ctx->clip.y1);
203 static enum path_transition
204 path_transition_bottom_edge(struct clip_context *ctx, GLfloat x, GLfloat y)
206 return ((ctx->prev.y < ctx->clip.y2) << 1) | (y < ctx->clip.y2);
210 clip_polygon_leftright(struct clip_context *ctx,
211 enum path_transition transition,
212 GLfloat x, GLfloat y, GLfloat clip_x)
216 switch (transition) {
217 case PATH_TRANSITION_IN_TO_IN:
218 clip_append_vertex(ctx, x, y);
220 case PATH_TRANSITION_IN_TO_OUT:
221 yi = clip_intersect_y(ctx->prev.x, ctx->prev.y, x, y, clip_x);
222 clip_append_vertex(ctx, clip_x, yi);
224 case PATH_TRANSITION_OUT_TO_IN:
225 yi = clip_intersect_y(ctx->prev.x, ctx->prev.y, x, y, clip_x);
226 clip_append_vertex(ctx, clip_x, yi);
227 clip_append_vertex(ctx, x, y);
229 case PATH_TRANSITION_OUT_TO_OUT:
233 assert(0 && "bad enum path_transition");
241 clip_polygon_topbottom(struct clip_context *ctx,
242 enum path_transition transition,
243 GLfloat x, GLfloat y, GLfloat clip_y)
247 switch (transition) {
248 case PATH_TRANSITION_IN_TO_IN:
249 clip_append_vertex(ctx, x, y);
251 case PATH_TRANSITION_IN_TO_OUT:
252 xi = clip_intersect_x(ctx->prev.x, ctx->prev.y, x, y, clip_y);
253 clip_append_vertex(ctx, xi, clip_y);
255 case PATH_TRANSITION_OUT_TO_IN:
256 xi = clip_intersect_x(ctx->prev.x, ctx->prev.y, x, y, clip_y);
257 clip_append_vertex(ctx, xi, clip_y);
258 clip_append_vertex(ctx, x, y);
260 case PATH_TRANSITION_OUT_TO_OUT:
264 assert(0 && "bad enum path_transition");
272 clip_context_prepare(struct clip_context *ctx, const struct polygon8 *src,
273 GLfloat *dst_x, GLfloat *dst_y)
275 ctx->prev.x = src->x[src->n - 1];
276 ctx->prev.y = src->y[src->n - 1];
277 ctx->vertices.x = dst_x;
278 ctx->vertices.y = dst_y;
282 clip_polygon_left(struct clip_context *ctx, const struct polygon8 *src,
283 GLfloat *dst_x, GLfloat *dst_y)
285 enum path_transition trans;
288 clip_context_prepare(ctx, src, dst_x, dst_y);
289 for (i = 0; i < src->n; i++) {
290 trans = path_transition_left_edge(ctx, src->x[i], src->y[i]);
291 clip_polygon_leftright(ctx, trans, src->x[i], src->y[i],
294 return ctx->vertices.x - dst_x;
298 clip_polygon_right(struct clip_context *ctx, const struct polygon8 *src,
299 GLfloat *dst_x, GLfloat *dst_y)
301 enum path_transition trans;
304 clip_context_prepare(ctx, src, dst_x, dst_y);
305 for (i = 0; i < src->n; i++) {
306 trans = path_transition_right_edge(ctx, src->x[i], src->y[i]);
307 clip_polygon_leftright(ctx, trans, src->x[i], src->y[i],
310 return ctx->vertices.x - dst_x;
314 clip_polygon_top(struct clip_context *ctx, const struct polygon8 *src,
315 GLfloat *dst_x, GLfloat *dst_y)
317 enum path_transition trans;
320 clip_context_prepare(ctx, src, dst_x, dst_y);
321 for (i = 0; i < src->n; i++) {
322 trans = path_transition_top_edge(ctx, src->x[i], src->y[i]);
323 clip_polygon_topbottom(ctx, trans, src->x[i], src->y[i],
326 return ctx->vertices.x - dst_x;
330 clip_polygon_bottom(struct clip_context *ctx, const struct polygon8 *src,
331 GLfloat *dst_x, GLfloat *dst_y)
333 enum path_transition trans;
336 clip_context_prepare(ctx, src, dst_x, dst_y);
337 for (i = 0; i < src->n; i++) {
338 trans = path_transition_bottom_edge(ctx, src->x[i], src->y[i]);
339 clip_polygon_topbottom(ctx, trans, src->x[i], src->y[i],
342 return ctx->vertices.x - dst_x;
345 #define max(a, b) (((a) > (b)) ? (a) : (b))
346 #define min(a, b) (((a) > (b)) ? (b) : (a))
347 #define clip(x, a, b) min(max(x, a), b)
350 * Compute the boundary vertices of the intersection of the global coordinate
351 * aligned rectangle 'rect', and an arbitrary quadrilateral produced from
352 * 'surf_rect' when transformed from surface coordinates into global coordinates.
353 * The vertices are written to 'ex' and 'ey', and the return value is the
354 * number of vertices. Vertices are produced in clockwise winding order.
355 * Guarantees to produce either zero vertices, or 3-8 vertices with non-zero
359 calculate_edges(struct weston_surface *es, pixman_box32_t *rect,
360 pixman_box32_t *surf_rect, GLfloat *ex, GLfloat *ey)
362 struct polygon8 polygon;
363 struct clip_context ctx;
365 GLfloat min_x, max_x, min_y, max_y;
366 struct polygon8 surf = {
367 { surf_rect->x1, surf_rect->x2, surf_rect->x2, surf_rect->x1 },
368 { surf_rect->y1, surf_rect->y1, surf_rect->y2, surf_rect->y2 },
372 ctx.clip.x1 = rect->x1;
373 ctx.clip.y1 = rect->y1;
374 ctx.clip.x2 = rect->x2;
375 ctx.clip.y2 = rect->y2;
377 /* transform surface to screen space: */
378 for (i = 0; i < surf.n; i++)
379 weston_surface_to_global_float(es, surf.x[i], surf.y[i],
380 &surf.x[i], &surf.y[i]);
382 /* find bounding box: */
383 min_x = max_x = surf.x[0];
384 min_y = max_y = surf.y[0];
386 for (i = 1; i < surf.n; i++) {
387 min_x = min(min_x, surf.x[i]);
388 max_x = max(max_x, surf.x[i]);
389 min_y = min(min_y, surf.y[i]);
390 max_y = max(max_y, surf.y[i]);
393 /* First, simple bounding box check to discard early transformed
394 * surface rects that do not intersect with the clip region:
396 if ((min_x >= ctx.clip.x2) || (max_x <= ctx.clip.x1) ||
397 (min_y >= ctx.clip.y2) || (max_y <= ctx.clip.y1))
400 /* Simple case, bounding box edges are parallel to surface edges,
401 * there will be only four edges. We just need to clip the surface
402 * vertices to the clip rect bounds:
404 if (!es->transform.enabled) {
405 for (i = 0; i < surf.n; i++) {
406 ex[i] = clip(surf.x[i], ctx.clip.x1, ctx.clip.x2);
407 ey[i] = clip(surf.y[i], ctx.clip.y1, ctx.clip.y2);
412 /* Transformed case: use a general polygon clipping algorithm to
413 * clip the surface rectangle with each side of 'rect'.
414 * The algorithm is Sutherland-Hodgman, as explained in
415 * http://www.codeguru.com/cpp/misc/misc/graphics/article.php/c8965/Polygon-Clipping.htm
416 * but without looking at any of that code.
418 polygon.n = clip_polygon_left(&ctx, &surf, polygon.x, polygon.y);
419 surf.n = clip_polygon_right(&ctx, &polygon, surf.x, surf.y);
420 polygon.n = clip_polygon_top(&ctx, &surf, polygon.x, polygon.y);
421 surf.n = clip_polygon_bottom(&ctx, &polygon, surf.x, surf.y);
423 /* Get rid of duplicate vertices */
427 for (i = 1; i < surf.n; i++) {
428 if (float_difference(ex[n - 1], surf.x[i]) == 0.0f &&
429 float_difference(ey[n - 1], surf.y[i]) == 0.0f)
435 if (float_difference(ex[n - 1], surf.x[0]) == 0.0f &&
436 float_difference(ey[n - 1], surf.y[0]) == 0.0f)
446 /* ---------------------- copied ends -----------------------*/
449 geometry_set_phi(struct geometry *g, float phi)
457 geometry_init(struct geometry *g)
469 geometry_set_phi(g, 0.0);
477 struct geometry geometry;
481 struct window *window;
482 struct widget *widget;
483 struct display *display;
488 struct geometry geometry;
489 struct weston_surface surface;
493 draw_polygon_closed(cairo_t *cr, GLfloat *x, GLfloat *y, int n)
497 cairo_move_to(cr, x[0], y[0]);
498 for (i = 1; i < n; i++)
499 cairo_line_to(cr, x[i], y[i]);
500 cairo_line_to(cr, x[0], y[0]);
504 draw_polygon_labels(cairo_t *cr, GLfloat *x, GLfloat *y, int n)
509 for (i = 0; i < n; i++) {
510 snprintf(str, 16, "%d", i);
511 cairo_move_to(cr, x[i], y[i]);
512 cairo_show_text(cr, str);
517 draw_coordinates(cairo_t *cr, double ox, double oy, GLfloat *x, GLfloat *y, int n)
521 cairo_font_extents_t ext;
523 cairo_font_extents(cr, &ext);
524 for (i = 0; i < n; i++) {
525 snprintf(str, 64, "%d: %14.9f, %14.9f", i, x[i], y[i]);
526 cairo_move_to(cr, ox, oy + ext.height * (i + 1));
527 cairo_show_text(cr, str);
532 draw_box(cairo_t *cr, pixman_box32_t *box, struct weston_surface *surface)
537 weston_surface_to_global_float(surface, box->x1, box->y1, &x[0], &y[0]);
538 weston_surface_to_global_float(surface, box->x2, box->y1, &x[1], &y[1]);
539 weston_surface_to_global_float(surface, box->x2, box->y2, &x[2], &y[2]);
540 weston_surface_to_global_float(surface, box->x1, box->y2, &x[3], &y[3]);
542 x[0] = box->x1; y[0] = box->y1;
543 x[1] = box->x2; y[1] = box->y1;
544 x[2] = box->x2; y[2] = box->y2;
545 x[3] = box->x1; y[3] = box->y2;
548 draw_polygon_closed(cr, x, y, 4);
552 draw_geometry(cairo_t *cr, struct weston_surface *surface,
553 GLfloat *ex, GLfloat *ey, int n)
555 struct geometry *g = surface->geometry;
558 draw_box(cr, &g->surf, surface);
559 cairo_set_source_rgba(cr, 1.0, 0.0, 0.0, 0.4);
561 weston_surface_to_global_float(surface, g->surf.x1 - 4, g->surf.y1 - 4, &cx, &cy);
562 cairo_arc(cr, cx, cy, 1.5, 0.0, 2.0 * M_PI);
563 if (surface->transform.enabled == 0)
564 cairo_set_source_rgba(cr, 1.0, 0.0, 0.0, 0.8);
567 draw_box(cr, &g->clip, NULL);
568 cairo_set_source_rgba(cr, 0.0, 0.0, 1.0, 0.4);
571 draw_polygon_closed(cr, ex, ey, n);
572 cairo_set_source_rgb(cr, 0.0, 1.0, 0.0);
575 cairo_set_source_rgba(cr, 0.0, 1.0, 0.0, 0.5);
576 draw_polygon_labels(cr, ex, ey, n);
580 redraw_handler(struct widget *widget, void *data)
582 struct cliptest *cliptest = data;
583 struct geometry *g = cliptest->surface.geometry;
584 struct rectangle allocation;
586 cairo_surface_t *surface;
591 n = calculate_edges(&cliptest->surface, &g->clip, &g->surf, ex, ey);
593 widget_get_allocation(cliptest->widget, &allocation);
595 surface = window_get_surface(cliptest->window);
596 cr = cairo_create(surface);
597 widget_get_allocation(cliptest->widget, &allocation);
598 cairo_rectangle(cr, allocation.x, allocation.y,
599 allocation.width, allocation.height);
602 cairo_set_operator(cr, CAIRO_OPERATOR_SOURCE);
603 cairo_set_source_rgba(cr, 0, 0, 0, 1);
606 cairo_translate(cr, allocation.x, allocation.y);
607 cairo_set_line_width(cr, 1.0);
608 cairo_move_to(cr, allocation.width / 2.0, 0.0);
609 cairo_line_to(cr, allocation.width / 2.0, allocation.height);
610 cairo_move_to(cr, 0.0, allocation.height / 2.0);
611 cairo_line_to(cr, allocation.width, allocation.height / 2.0);
612 cairo_set_source_rgba(cr, 0.5, 0.5, 0.5, 1.0);
615 cairo_set_operator(cr, CAIRO_OPERATOR_OVER);
616 cairo_push_group(cr);
617 cairo_translate(cr, allocation.width / 2.0,
618 allocation.height / 2.0);
619 cairo_scale(cr, 4.0, 4.0);
620 cairo_set_line_width(cr, 0.5);
621 cairo_set_line_join(cr, CAIRO_LINE_JOIN_BEVEL);
622 cairo_select_font_face(cr, "Sans", CAIRO_FONT_SLANT_NORMAL,
623 CAIRO_FONT_WEIGHT_BOLD);
624 cairo_set_font_size(cr, 5.0);
625 draw_geometry(cr, &cliptest->surface, ex, ey, n);
626 cairo_pop_group_to_source(cr);
629 cairo_set_source_rgba(cr, 0.0, 1.0, 0.0, 1.0);
630 cairo_select_font_face(cr, "monospace", CAIRO_FONT_SLANT_NORMAL,
631 CAIRO_FONT_WEIGHT_NORMAL);
632 cairo_set_font_size(cr, 12.0);
633 draw_coordinates(cr, 10.0, 10.0, ex, ey, n);
637 cairo_surface_destroy(surface);
641 motion_handler(struct widget *widget, struct input *input,
642 uint32_t time, float x, float y, void *data)
644 struct cliptest *cliptest = data;
645 struct ui_state *ui = &cliptest->ui;
646 struct geometry *ref = &ui->geometry;
647 struct geometry *geom = &cliptest->geometry;
651 return CURSOR_LEFT_PTR;
653 dx = (x - ui->down_pos[0]) * 0.25;
654 dy = (y - ui->down_pos[1]) * 0.25;
656 switch (ui->button) {
658 geom->clip.x1 = ref->clip.x1 + dx;
659 geom->clip.y1 = ref->clip.y1 + dy;
662 geom->clip.x2 = ref->clip.x2 + dx;
663 geom->clip.y2 = ref->clip.y2 + dy;
666 return CURSOR_LEFT_PTR;
669 widget_schedule_redraw(cliptest->widget);
674 button_handler(struct widget *widget, struct input *input,
675 uint32_t time, uint32_t button,
676 enum wl_pointer_button_state state, void *data)
678 struct cliptest *cliptest = data;
679 struct ui_state *ui = &cliptest->ui;
683 if (state == WL_POINTER_BUTTON_STATE_PRESSED) {
685 input_get_position(input, &ui->down_pos[0], &ui->down_pos[1]);
688 ui->geometry = cliptest->geometry;
693 axis_handler(struct widget *widget, struct input *input, uint32_t time,
694 uint32_t axis, wl_fixed_t value, void *data)
696 struct cliptest *cliptest = data;
697 struct geometry *geom = &cliptest->geometry;
699 if (axis != WL_POINTER_AXIS_VERTICAL_SCROLL)
702 geometry_set_phi(geom, geom->phi +
703 (M_PI / 12.0) * wl_fixed_to_double(value));
704 cliptest->surface.transform.enabled = 1;
706 widget_schedule_redraw(cliptest->widget);
710 key_handler(struct window *window, struct input *input, uint32_t time,
711 uint32_t key, uint32_t sym,
712 enum wl_keyboard_key_state state, void *data)
714 struct cliptest *cliptest = data;
715 struct geometry *g = &cliptest->geometry;
717 if (state == WL_KEYBOARD_KEY_STATE_RELEASED)
722 display_exit(cliptest->display);
753 geometry_set_phi(g, g->phi + (M_PI / 24.0));
754 cliptest->surface.transform.enabled = 1;
757 geometry_set_phi(g, g->phi - (M_PI / 24.0));
758 cliptest->surface.transform.enabled = 1;
761 geometry_set_phi(g, 0.0);
762 cliptest->surface.transform.enabled = 0;
768 widget_schedule_redraw(cliptest->widget);
772 keyboard_focus_handler(struct window *window,
773 struct input *device, void *data)
775 struct cliptest *cliptest = data;
777 window_schedule_redraw(cliptest->window);
781 fullscreen_handler(struct window *window, void *data)
783 struct cliptest *cliptest = data;
785 cliptest->fullscreen ^= 1;
786 window_set_fullscreen(window, cliptest->fullscreen);
789 static struct cliptest *
790 cliptest_create(struct display *display)
792 struct cliptest *cliptest;
794 cliptest = xzalloc(sizeof *cliptest);
795 cliptest->surface.geometry = &cliptest->geometry;
796 cliptest->surface.transform.enabled = 0;
797 geometry_init(&cliptest->geometry);
798 geometry_init(&cliptest->ui.geometry);
800 cliptest->window = window_create(display);
801 cliptest->widget = window_frame_create(cliptest->window, cliptest);
802 window_set_title(cliptest->window, "cliptest");
803 cliptest->display = display;
805 window_set_user_data(cliptest->window, cliptest);
806 widget_set_redraw_handler(cliptest->widget, redraw_handler);
807 widget_set_button_handler(cliptest->widget, button_handler);
808 widget_set_motion_handler(cliptest->widget, motion_handler);
809 widget_set_axis_handler(cliptest->widget, axis_handler);
811 window_set_keyboard_focus_handler(cliptest->window,
812 keyboard_focus_handler);
813 window_set_key_handler(cliptest->window, key_handler);
814 window_set_fullscreen_handler(cliptest->window, fullscreen_handler);
816 /* set minimum size */
817 widget_schedule_resize(cliptest->widget, 200, 100);
819 /* set current size */
820 widget_schedule_resize(cliptest->widget, 500, 400);
825 static struct timespec begin_time;
830 clock_gettime(CLOCK_MONOTONIC, &begin_time);
838 clock_gettime(CLOCK_MONOTONIC, &t);
839 return (double)(t.tv_sec - begin_time.tv_sec) +
840 1e-9 * (t.tv_nsec - begin_time.tv_nsec);
846 struct weston_surface surface;
847 struct geometry geom;
848 GLfloat ex[8], ey[8];
851 const int N = 1000000;
863 geometry_set_phi(&geom, 0.0);
865 surface.transform.enabled = 1;
866 surface.geometry = &geom;
869 for (i = 0; i < N; i++) {
870 geometry_set_phi(&geom, (float)i / 360.0f);
871 calculate_edges(&surface, &geom.clip, &geom.surf, ex, ey);
875 printf("%d calls took %g s, average %g us/call\n", N, t, t / N * 1e6);
881 main(int argc, char *argv[])
884 struct cliptest *cliptest;
889 d = display_create(&argc, argv);
891 fprintf(stderr, "failed to create display: %m\n");
895 cliptest = cliptest_create(d);
898 widget_destroy(cliptest->widget);
899 window_destroy(cliptest->window);