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
49 #include <linux/input.h>
50 #include <wayland-client.h>
54 typedef float GLfloat;
60 float s; /* sin phi */
61 float c; /* cos phi */
65 struct weston_surface {
70 struct geometry *geometry;
74 weston_surface_to_global_float(struct weston_surface *surface,
75 GLfloat sx, GLfloat sy, GLfloat *x, GLfloat *y)
77 struct geometry *g = surface->geometry;
79 /* pure rotation around origin by sine and cosine */
80 *x = g->c * sx + g->s * sy;
81 *y = -g->s * sx + g->c * sy;
84 /* ---------------------- copied begins -----------------------*/
110 float_difference(GLfloat a, GLfloat b)
112 /* http://www.altdevblogaday.com/2012/02/22/comparing-floating-point-numbers-2012-edition/ */
113 static const GLfloat max_diff = 4.0f * FLT_MIN;
114 static const GLfloat max_rel_diff = 4.0e-5;
115 GLfloat diff = a - b;
116 GLfloat adiff = fabsf(diff);
118 if (adiff <= max_diff)
123 if (adiff <= (a > b ? a : b) * max_rel_diff)
129 /* A line segment (p1x, p1y)-(p2x, p2y) intersects the line x = x_arg.
130 * Compute the y coordinate of the intersection.
133 clip_intersect_y(GLfloat p1x, GLfloat p1y, GLfloat p2x, GLfloat p2y,
137 GLfloat diff = float_difference(p1x, p2x);
139 /* Practically vertical line segment, yet the end points have already
140 * been determined to be on different sides of the line. Therefore
141 * the line segment is part of the line and intersects everywhere.
142 * Return the end point, so we use the whole line segment.
147 a = (x_arg - p2x) / diff;
148 return p2y + (p1y - p2y) * a;
151 /* A line segment (p1x, p1y)-(p2x, p2y) intersects the line y = y_arg.
152 * Compute the x coordinate of the intersection.
155 clip_intersect_x(GLfloat p1x, GLfloat p1y, GLfloat p2x, GLfloat p2y,
159 GLfloat diff = float_difference(p1y, p2y);
161 /* Practically horizontal line segment, yet the end points have already
162 * been determined to be on different sides of the line. Therefore
163 * the line segment is part of the line and intersects everywhere.
164 * Return the end point, so we use the whole line segment.
169 a = (y_arg - p2y) / diff;
170 return p2x + (p1x - p2x) * a;
173 enum path_transition {
174 PATH_TRANSITION_OUT_TO_OUT = 0,
175 PATH_TRANSITION_OUT_TO_IN = 1,
176 PATH_TRANSITION_IN_TO_OUT = 2,
177 PATH_TRANSITION_IN_TO_IN = 3,
181 clip_append_vertex(struct clip_context *ctx, GLfloat x, GLfloat y)
183 *ctx->vertices.x++ = x;
184 *ctx->vertices.y++ = y;
187 static enum path_transition
188 path_transition_left_edge(struct clip_context *ctx, GLfloat x, GLfloat y)
190 return ((ctx->prev.x >= ctx->clip.x1) << 1) | (x >= ctx->clip.x1);
193 static enum path_transition
194 path_transition_right_edge(struct clip_context *ctx, GLfloat x, GLfloat y)
196 return ((ctx->prev.x < ctx->clip.x2) << 1) | (x < ctx->clip.x2);
199 static enum path_transition
200 path_transition_top_edge(struct clip_context *ctx, GLfloat x, GLfloat y)
202 return ((ctx->prev.y >= ctx->clip.y1) << 1) | (y >= ctx->clip.y1);
205 static enum path_transition
206 path_transition_bottom_edge(struct clip_context *ctx, GLfloat x, GLfloat y)
208 return ((ctx->prev.y < ctx->clip.y2) << 1) | (y < ctx->clip.y2);
212 clip_polygon_leftright(struct clip_context *ctx,
213 enum path_transition transition,
214 GLfloat x, GLfloat y, GLfloat clip_x)
218 switch (transition) {
219 case PATH_TRANSITION_IN_TO_IN:
220 clip_append_vertex(ctx, x, y);
222 case PATH_TRANSITION_IN_TO_OUT:
223 yi = clip_intersect_y(ctx->prev.x, ctx->prev.y, x, y, clip_x);
224 clip_append_vertex(ctx, clip_x, yi);
226 case PATH_TRANSITION_OUT_TO_IN:
227 yi = clip_intersect_y(ctx->prev.x, ctx->prev.y, x, y, clip_x);
228 clip_append_vertex(ctx, clip_x, yi);
229 clip_append_vertex(ctx, x, y);
231 case PATH_TRANSITION_OUT_TO_OUT:
235 assert(0 && "bad enum path_transition");
243 clip_polygon_topbottom(struct clip_context *ctx,
244 enum path_transition transition,
245 GLfloat x, GLfloat y, GLfloat clip_y)
249 switch (transition) {
250 case PATH_TRANSITION_IN_TO_IN:
251 clip_append_vertex(ctx, x, y);
253 case PATH_TRANSITION_IN_TO_OUT:
254 xi = clip_intersect_x(ctx->prev.x, ctx->prev.y, x, y, clip_y);
255 clip_append_vertex(ctx, xi, clip_y);
257 case PATH_TRANSITION_OUT_TO_IN:
258 xi = clip_intersect_x(ctx->prev.x, ctx->prev.y, x, y, clip_y);
259 clip_append_vertex(ctx, xi, clip_y);
260 clip_append_vertex(ctx, x, y);
262 case PATH_TRANSITION_OUT_TO_OUT:
266 assert(0 && "bad enum path_transition");
274 clip_context_prepare(struct clip_context *ctx, const struct polygon8 *src,
275 GLfloat *dst_x, GLfloat *dst_y)
277 ctx->prev.x = src->x[src->n - 1];
278 ctx->prev.y = src->y[src->n - 1];
279 ctx->vertices.x = dst_x;
280 ctx->vertices.y = dst_y;
284 clip_polygon_left(struct clip_context *ctx, const struct polygon8 *src,
285 GLfloat *dst_x, GLfloat *dst_y)
287 enum path_transition trans;
290 clip_context_prepare(ctx, src, dst_x, dst_y);
291 for (i = 0; i < src->n; i++) {
292 trans = path_transition_left_edge(ctx, src->x[i], src->y[i]);
293 clip_polygon_leftright(ctx, trans, src->x[i], src->y[i],
296 return ctx->vertices.x - dst_x;
300 clip_polygon_right(struct clip_context *ctx, const struct polygon8 *src,
301 GLfloat *dst_x, GLfloat *dst_y)
303 enum path_transition trans;
306 clip_context_prepare(ctx, src, dst_x, dst_y);
307 for (i = 0; i < src->n; i++) {
308 trans = path_transition_right_edge(ctx, src->x[i], src->y[i]);
309 clip_polygon_leftright(ctx, trans, src->x[i], src->y[i],
312 return ctx->vertices.x - dst_x;
316 clip_polygon_top(struct clip_context *ctx, const struct polygon8 *src,
317 GLfloat *dst_x, GLfloat *dst_y)
319 enum path_transition trans;
322 clip_context_prepare(ctx, src, dst_x, dst_y);
323 for (i = 0; i < src->n; i++) {
324 trans = path_transition_top_edge(ctx, src->x[i], src->y[i]);
325 clip_polygon_topbottom(ctx, trans, src->x[i], src->y[i],
328 return ctx->vertices.x - dst_x;
332 clip_polygon_bottom(struct clip_context *ctx, const struct polygon8 *src,
333 GLfloat *dst_x, GLfloat *dst_y)
335 enum path_transition trans;
338 clip_context_prepare(ctx, src, dst_x, dst_y);
339 for (i = 0; i < src->n; i++) {
340 trans = path_transition_bottom_edge(ctx, src->x[i], src->y[i]);
341 clip_polygon_topbottom(ctx, trans, src->x[i], src->y[i],
344 return ctx->vertices.x - dst_x;
347 #define max(a, b) (((a) > (b)) ? (a) : (b))
348 #define min(a, b) (((a) > (b)) ? (b) : (a))
349 #define clip(x, a, b) min(max(x, a), b)
352 * Compute the boundary vertices of the intersection of the global coordinate
353 * aligned rectangle 'rect', and an arbitrary quadrilateral produced from
354 * 'surf_rect' when transformed from surface coordinates into global coordinates.
355 * The vertices are written to 'ex' and 'ey', and the return value is the
356 * number of vertices. Vertices are produced in clockwise winding order.
357 * Guarantees to produce either zero vertices, or 3-8 vertices with non-zero
361 calculate_edges(struct weston_surface *es, pixman_box32_t *rect,
362 pixman_box32_t *surf_rect, GLfloat *ex, GLfloat *ey)
364 struct polygon8 polygon;
365 struct clip_context ctx;
367 GLfloat min_x, max_x, min_y, max_y;
368 struct polygon8 surf = {
369 { surf_rect->x1, surf_rect->x2, surf_rect->x2, surf_rect->x1 },
370 { surf_rect->y1, surf_rect->y1, surf_rect->y2, surf_rect->y2 },
374 ctx.clip.x1 = rect->x1;
375 ctx.clip.y1 = rect->y1;
376 ctx.clip.x2 = rect->x2;
377 ctx.clip.y2 = rect->y2;
379 /* transform surface to screen space: */
380 for (i = 0; i < surf.n; i++)
381 weston_surface_to_global_float(es, surf.x[i], surf.y[i],
382 &surf.x[i], &surf.y[i]);
384 /* find bounding box: */
385 min_x = max_x = surf.x[0];
386 min_y = max_y = surf.y[0];
388 for (i = 1; i < surf.n; i++) {
389 min_x = min(min_x, surf.x[i]);
390 max_x = max(max_x, surf.x[i]);
391 min_y = min(min_y, surf.y[i]);
392 max_y = max(max_y, surf.y[i]);
395 /* First, simple bounding box check to discard early transformed
396 * surface rects that do not intersect with the clip region:
398 if ((min_x >= ctx.clip.x2) || (max_x <= ctx.clip.x1) ||
399 (min_y >= ctx.clip.y2) || (max_y <= ctx.clip.y1))
402 /* Simple case, bounding box edges are parallel to surface edges,
403 * there will be only four edges. We just need to clip the surface
404 * vertices to the clip rect bounds:
406 if (!es->transform.enabled) {
407 for (i = 0; i < surf.n; i++) {
408 ex[i] = clip(surf.x[i], ctx.clip.x1, ctx.clip.x2);
409 ey[i] = clip(surf.y[i], ctx.clip.y1, ctx.clip.y2);
414 /* Transformed case: use a general polygon clipping algorithm to
415 * clip the surface rectangle with each side of 'rect'.
416 * The algorithm is Sutherland-Hodgman, as explained in
417 * http://www.codeguru.com/cpp/misc/misc/graphics/article.php/c8965/Polygon-Clipping.htm
418 * but without looking at any of that code.
420 polygon.n = clip_polygon_left(&ctx, &surf, polygon.x, polygon.y);
421 surf.n = clip_polygon_right(&ctx, &polygon, surf.x, surf.y);
422 polygon.n = clip_polygon_top(&ctx, &surf, polygon.x, polygon.y);
423 surf.n = clip_polygon_bottom(&ctx, &polygon, surf.x, surf.y);
425 /* Get rid of duplicate vertices */
429 for (i = 1; i < surf.n; i++) {
430 if (float_difference(ex[n - 1], surf.x[i]) == 0.0f &&
431 float_difference(ey[n - 1], surf.y[i]) == 0.0f)
437 if (float_difference(ex[n - 1], surf.x[0]) == 0.0f &&
438 float_difference(ey[n - 1], surf.y[0]) == 0.0f)
448 /* ---------------------- copied ends -----------------------*/
451 geometry_set_phi(struct geometry *g, float phi)
459 geometry_init(struct geometry *g)
471 geometry_set_phi(g, 0.0);
479 struct geometry geometry;
483 struct window *window;
484 struct widget *widget;
485 struct display *display;
490 struct geometry geometry;
491 struct weston_surface surface;
495 draw_polygon_closed(cairo_t *cr, GLfloat *x, GLfloat *y, int n)
499 cairo_move_to(cr, x[0], y[0]);
500 for (i = 1; i < n; i++)
501 cairo_line_to(cr, x[i], y[i]);
502 cairo_line_to(cr, x[0], y[0]);
506 draw_polygon_labels(cairo_t *cr, GLfloat *x, GLfloat *y, int n)
511 for (i = 0; i < n; i++) {
512 snprintf(str, 16, "%d", i);
513 cairo_move_to(cr, x[i], y[i]);
514 cairo_show_text(cr, str);
519 draw_coordinates(cairo_t *cr, double ox, double oy, GLfloat *x, GLfloat *y, int n)
523 cairo_font_extents_t ext;
525 cairo_font_extents(cr, &ext);
526 for (i = 0; i < n; i++) {
527 snprintf(str, 64, "%d: %14.9f, %14.9f", i, x[i], y[i]);
528 cairo_move_to(cr, ox, oy + ext.height * (i + 1));
529 cairo_show_text(cr, str);
534 draw_box(cairo_t *cr, pixman_box32_t *box, struct weston_surface *surface)
539 weston_surface_to_global_float(surface, box->x1, box->y1, &x[0], &y[0]);
540 weston_surface_to_global_float(surface, box->x2, box->y1, &x[1], &y[1]);
541 weston_surface_to_global_float(surface, box->x2, box->y2, &x[2], &y[2]);
542 weston_surface_to_global_float(surface, box->x1, box->y2, &x[3], &y[3]);
544 x[0] = box->x1; y[0] = box->y1;
545 x[1] = box->x2; y[1] = box->y1;
546 x[2] = box->x2; y[2] = box->y2;
547 x[3] = box->x1; y[3] = box->y2;
550 draw_polygon_closed(cr, x, y, 4);
554 draw_geometry(cairo_t *cr, struct weston_surface *surface,
555 GLfloat *ex, GLfloat *ey, int n)
557 struct geometry *g = surface->geometry;
560 draw_box(cr, &g->surf, surface);
561 cairo_set_source_rgba(cr, 1.0, 0.0, 0.0, 0.4);
563 weston_surface_to_global_float(surface, g->surf.x1 - 4, g->surf.y1 - 4, &cx, &cy);
564 cairo_arc(cr, cx, cy, 1.5, 0.0, 2.0 * M_PI);
565 if (surface->transform.enabled == 0)
566 cairo_set_source_rgba(cr, 1.0, 0.0, 0.0, 0.8);
569 draw_box(cr, &g->clip, NULL);
570 cairo_set_source_rgba(cr, 0.0, 0.0, 1.0, 0.4);
573 draw_polygon_closed(cr, ex, ey, n);
574 cairo_set_source_rgb(cr, 0.0, 1.0, 0.0);
577 cairo_set_source_rgba(cr, 0.0, 1.0, 0.0, 0.5);
578 draw_polygon_labels(cr, ex, ey, n);
582 redraw_handler(struct widget *widget, void *data)
584 struct cliptest *cliptest = data;
585 struct geometry *g = cliptest->surface.geometry;
586 struct rectangle allocation;
588 cairo_surface_t *surface;
593 n = calculate_edges(&cliptest->surface, &g->clip, &g->surf, ex, ey);
595 widget_get_allocation(cliptest->widget, &allocation);
597 surface = window_get_surface(cliptest->window);
598 cr = cairo_create(surface);
599 widget_get_allocation(cliptest->widget, &allocation);
600 cairo_rectangle(cr, allocation.x, allocation.y,
601 allocation.width, allocation.height);
604 cairo_set_operator(cr, CAIRO_OPERATOR_SOURCE);
605 cairo_set_source_rgba(cr, 0, 0, 0, 1);
608 cairo_translate(cr, allocation.x, allocation.y);
609 cairo_set_line_width(cr, 1.0);
610 cairo_move_to(cr, allocation.width / 2.0, 0.0);
611 cairo_line_to(cr, allocation.width / 2.0, allocation.height);
612 cairo_move_to(cr, 0.0, allocation.height / 2.0);
613 cairo_line_to(cr, allocation.width, allocation.height / 2.0);
614 cairo_set_source_rgba(cr, 0.5, 0.5, 0.5, 1.0);
617 cairo_set_operator(cr, CAIRO_OPERATOR_OVER);
618 cairo_push_group(cr);
619 cairo_translate(cr, allocation.width / 2.0,
620 allocation.height / 2.0);
621 cairo_scale(cr, 4.0, 4.0);
622 cairo_set_line_width(cr, 0.5);
623 cairo_set_line_join(cr, CAIRO_LINE_JOIN_BEVEL);
624 cairo_select_font_face(cr, "Sans", CAIRO_FONT_SLANT_NORMAL,
625 CAIRO_FONT_WEIGHT_BOLD);
626 cairo_set_font_size(cr, 5.0);
627 draw_geometry(cr, &cliptest->surface, ex, ey, n);
628 cairo_pop_group_to_source(cr);
631 cairo_set_source_rgba(cr, 0.0, 1.0, 0.0, 1.0);
632 cairo_select_font_face(cr, "monospace", CAIRO_FONT_SLANT_NORMAL,
633 CAIRO_FONT_WEIGHT_NORMAL);
634 cairo_set_font_size(cr, 12.0);
635 draw_coordinates(cr, 10.0, 10.0, ex, ey, n);
639 cairo_surface_destroy(surface);
643 motion_handler(struct widget *widget, struct input *input,
644 uint32_t time, float x, float y, void *data)
646 struct cliptest *cliptest = data;
647 struct ui_state *ui = &cliptest->ui;
648 struct geometry *ref = &ui->geometry;
649 struct geometry *geom = &cliptest->geometry;
653 return CURSOR_LEFT_PTR;
655 dx = (x - ui->down_pos[0]) * 0.25;
656 dy = (y - ui->down_pos[1]) * 0.25;
658 switch (ui->button) {
660 geom->clip.x1 = ref->clip.x1 + dx;
661 geom->clip.y1 = ref->clip.y1 + dy;
664 geom->clip.x2 = ref->clip.x2 + dx;
665 geom->clip.y2 = ref->clip.y2 + dy;
668 return CURSOR_LEFT_PTR;
671 widget_schedule_redraw(cliptest->widget);
676 button_handler(struct widget *widget, struct input *input,
677 uint32_t time, uint32_t button,
678 enum wl_pointer_button_state state, void *data)
680 struct cliptest *cliptest = data;
681 struct ui_state *ui = &cliptest->ui;
685 if (state == WL_POINTER_BUTTON_STATE_PRESSED) {
687 input_get_position(input, &ui->down_pos[0], &ui->down_pos[1]);
690 ui->geometry = cliptest->geometry;
695 axis_handler(struct widget *widget, struct input *input, uint32_t time,
696 uint32_t axis, wl_fixed_t value, void *data)
698 struct cliptest *cliptest = data;
699 struct geometry *geom = &cliptest->geometry;
701 if (axis != WL_POINTER_AXIS_VERTICAL_SCROLL)
704 geometry_set_phi(geom, geom->phi +
705 (M_PI / 12.0) * wl_fixed_to_double(value));
706 cliptest->surface.transform.enabled = 1;
708 widget_schedule_redraw(cliptest->widget);
712 key_handler(struct window *window, struct input *input, uint32_t time,
713 uint32_t key, uint32_t sym,
714 enum wl_keyboard_key_state state, void *data)
716 struct cliptest *cliptest = data;
717 struct geometry *g = &cliptest->geometry;
719 if (state == WL_KEYBOARD_KEY_STATE_RELEASED)
724 display_exit(cliptest->display);
755 geometry_set_phi(g, g->phi + (M_PI / 24.0));
756 cliptest->surface.transform.enabled = 1;
759 geometry_set_phi(g, g->phi - (M_PI / 24.0));
760 cliptest->surface.transform.enabled = 1;
763 geometry_set_phi(g, 0.0);
764 cliptest->surface.transform.enabled = 0;
770 widget_schedule_redraw(cliptest->widget);
774 keyboard_focus_handler(struct window *window,
775 struct input *device, void *data)
777 struct cliptest *cliptest = data;
779 window_schedule_redraw(cliptest->window);
783 fullscreen_handler(struct window *window, void *data)
785 struct cliptest *cliptest = data;
787 cliptest->fullscreen ^= 1;
788 window_set_fullscreen(window, cliptest->fullscreen);
791 static struct cliptest *
792 cliptest_create(struct display *display)
794 struct cliptest *cliptest;
796 cliptest = xzalloc(sizeof *cliptest);
797 cliptest->surface.geometry = &cliptest->geometry;
798 cliptest->surface.transform.enabled = 0;
799 geometry_init(&cliptest->geometry);
800 geometry_init(&cliptest->ui.geometry);
802 cliptest->window = window_create(display);
803 cliptest->widget = window_frame_create(cliptest->window, cliptest);
804 window_set_title(cliptest->window, "cliptest");
805 cliptest->display = display;
807 window_set_user_data(cliptest->window, cliptest);
808 widget_set_redraw_handler(cliptest->widget, redraw_handler);
809 widget_set_button_handler(cliptest->widget, button_handler);
810 widget_set_motion_handler(cliptest->widget, motion_handler);
811 widget_set_axis_handler(cliptest->widget, axis_handler);
813 window_set_keyboard_focus_handler(cliptest->window,
814 keyboard_focus_handler);
815 window_set_key_handler(cliptest->window, key_handler);
816 window_set_fullscreen_handler(cliptest->window, fullscreen_handler);
818 /* set minimum size */
819 widget_schedule_resize(cliptest->widget, 200, 100);
821 /* set current size */
822 widget_schedule_resize(cliptest->widget, 500, 400);
827 static struct timespec begin_time;
832 clock_gettime(CLOCK_MONOTONIC, &begin_time);
840 clock_gettime(CLOCK_MONOTONIC, &t);
841 return (double)(t.tv_sec - begin_time.tv_sec) +
842 1e-9 * (t.tv_nsec - begin_time.tv_nsec);
848 struct weston_surface surface;
849 struct geometry geom;
850 GLfloat ex[8], ey[8];
853 const int N = 1000000;
865 geometry_set_phi(&geom, 0.0);
867 surface.transform.enabled = 1;
868 surface.geometry = &geom;
871 for (i = 0; i < N; i++) {
872 geometry_set_phi(&geom, (float)i / 360.0f);
873 calculate_edges(&surface, &geom.clip, &geom.surf, ex, ey);
877 printf("%d calls took %g s, average %g us/call\n", N, t, t / N * 1e6);
883 main(int argc, char *argv[])
886 struct cliptest *cliptest;
891 d = display_create(&argc, argv);
893 fprintf(stderr, "failed to create display: %m\n");
897 cliptest = cliptest_create(d);
900 widget_destroy(cliptest->widget);
901 window_destroy(cliptest->window);