Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
1892 | serge | 1 | /* cairo - a vector graphics library with display and print output |
2 | * |
||
3 | * Copyright © 2003 University of Southern California |
||
4 | * |
||
5 | * This library is free software; you can redistribute it and/or |
||
6 | * modify it either under the terms of the GNU Lesser General Public |
||
7 | * License version 2.1 as published by the Free Software Foundation |
||
8 | * (the "LGPL") or, at your option, under the terms of the Mozilla |
||
9 | * Public License Version 1.1 (the "MPL"). If you do not alter this |
||
10 | * notice, a recipient may use your version of this file under either |
||
11 | * the MPL or the LGPL. |
||
12 | * |
||
13 | * You should have received a copy of the LGPL along with this library |
||
14 | * in the file COPYING-LGPL-2.1; if not, write to the Free Software |
||
15 | * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA |
||
16 | * You should have received a copy of the MPL along with this library |
||
17 | * in the file COPYING-MPL-1.1 |
||
18 | * |
||
19 | * The contents of this file are subject to the Mozilla Public License |
||
20 | * Version 1.1 (the "License"); you may not use this file except in |
||
21 | * compliance with the License. You may obtain a copy of the License at |
||
22 | * http://www.mozilla.org/MPL/ |
||
23 | * |
||
24 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY |
||
25 | * OF ANY KIND, either express or implied. See the LGPL or the MPL for |
||
26 | * the specific language governing rights and limitations. |
||
27 | * |
||
28 | * The Original Code is the cairo graphics library. |
||
29 | * |
||
30 | * The Initial Developer of the Original Code is University of Southern |
||
31 | * California. |
||
32 | * |
||
33 | * Contributor(s): |
||
34 | * Carl D. Worth |
||
35 | */ |
||
36 | |||
37 | #include "cairoint.h" |
||
38 | |||
39 | #include "cairo-error-private.h" |
||
40 | #include "cairo-slope-private.h" |
||
41 | |||
42 | typedef struct cairo_hull { |
||
43 | cairo_point_t point; |
||
44 | cairo_slope_t slope; |
||
45 | int discard; |
||
46 | int id; |
||
47 | } cairo_hull_t; |
||
48 | |||
49 | static void |
||
50 | _cairo_hull_init (cairo_hull_t *hull, |
||
51 | cairo_pen_vertex_t *vertices, |
||
52 | int num_vertices) |
||
53 | { |
||
54 | cairo_point_t *p, *extremum, tmp; |
||
55 | int i; |
||
56 | |||
57 | extremum = &vertices[0].point; |
||
58 | for (i = 1; i < num_vertices; i++) { |
||
59 | p = &vertices[i].point; |
||
60 | if (p->y < extremum->y || (p->y == extremum->y && p->x < extremum->x)) |
||
61 | extremum = p; |
||
62 | } |
||
63 | /* Put the extremal point at the beginning of the array */ |
||
64 | tmp = *extremum; |
||
65 | *extremum = vertices[0].point; |
||
66 | vertices[0].point = tmp; |
||
67 | |||
68 | for (i = 0; i < num_vertices; i++) { |
||
69 | hull[i].point = vertices[i].point; |
||
70 | _cairo_slope_init (&hull[i].slope, &hull[0].point, &hull[i].point); |
||
71 | |||
72 | /* give each point a unique id for later comparison */ |
||
73 | hull[i].id = i; |
||
74 | |||
75 | /* Don't discard by default */ |
||
76 | hull[i].discard = 0; |
||
77 | |||
78 | /* Discard all points coincident with the extremal point */ |
||
79 | if (i != 0 && hull[i].slope.dx == 0 && hull[i].slope.dy == 0) |
||
80 | hull[i].discard = 1; |
||
81 | } |
||
82 | } |
||
83 | |||
84 | static inline cairo_int64_t |
||
85 | _slope_length (cairo_slope_t *slope) |
||
86 | { |
||
87 | return _cairo_int64_add (_cairo_int32x32_64_mul (slope->dx, slope->dx), |
||
88 | _cairo_int32x32_64_mul (slope->dy, slope->dy)); |
||
89 | } |
||
90 | |||
91 | static int |
||
92 | _cairo_hull_vertex_compare (const void *av, const void *bv) |
||
93 | { |
||
94 | cairo_hull_t *a = (cairo_hull_t *) av; |
||
95 | cairo_hull_t *b = (cairo_hull_t *) bv; |
||
96 | int ret; |
||
97 | |||
98 | /* Some libraries are reported to actually compare identical |
||
99 | * pointers and require the result to be 0. This is the crazy world we |
||
100 | * have to live in. |
||
101 | */ |
||
102 | if (a == b) |
||
103 | return 0; |
||
104 | |||
105 | ret = _cairo_slope_compare (&a->slope, &b->slope); |
||
106 | |||
107 | /* |
||
108 | * In the case of two vertices with identical slope from the |
||
109 | * extremal point discard the nearer point. |
||
110 | */ |
||
111 | if (ret == 0) { |
||
112 | int cmp; |
||
113 | |||
114 | cmp = _cairo_int64_cmp (_slope_length (&a->slope), |
||
115 | _slope_length (&b->slope)); |
||
116 | |||
117 | /* |
||
118 | * Use the points' ids to ensure a well-defined ordering, |
||
119 | * and avoid setting discard on both points. |
||
120 | */ |
||
121 | if (cmp < 0 || (cmp == 0 && a->id < b->id)) { |
||
122 | a->discard = 1; |
||
123 | ret = -1; |
||
124 | } else { |
||
125 | b->discard = 1; |
||
126 | ret = 1; |
||
127 | } |
||
128 | } |
||
129 | |||
130 | return ret; |
||
131 | } |
||
132 | |||
133 | static int |
||
134 | _cairo_hull_prev_valid (cairo_hull_t *hull, int num_hull, int index) |
||
135 | { |
||
136 | /* hull[0] is always valid, and we never need to wraparound, (if |
||
137 | * we are passed an index of 0 here, then the calling loop is just |
||
138 | * about to terminate). */ |
||
139 | if (index == 0) |
||
140 | return 0; |
||
141 | |||
142 | do { |
||
143 | index--; |
||
144 | } while (hull[index].discard); |
||
145 | |||
146 | return index; |
||
147 | } |
||
148 | |||
149 | static int |
||
150 | _cairo_hull_next_valid (cairo_hull_t *hull, int num_hull, int index) |
||
151 | { |
||
152 | do { |
||
153 | index = (index + 1) % num_hull; |
||
154 | } while (hull[index].discard); |
||
155 | |||
156 | return index; |
||
157 | } |
||
158 | |||
159 | static void |
||
160 | _cairo_hull_eliminate_concave (cairo_hull_t *hull, int num_hull) |
||
161 | { |
||
162 | int i, j, k; |
||
163 | cairo_slope_t slope_ij, slope_jk; |
||
164 | |||
165 | i = 0; |
||
166 | j = _cairo_hull_next_valid (hull, num_hull, i); |
||
167 | k = _cairo_hull_next_valid (hull, num_hull, j); |
||
168 | |||
169 | do { |
||
170 | _cairo_slope_init (&slope_ij, &hull[i].point, &hull[j].point); |
||
171 | _cairo_slope_init (&slope_jk, &hull[j].point, &hull[k].point); |
||
172 | |||
173 | /* Is the angle formed by ij and jk concave? */ |
||
174 | if (_cairo_slope_compare (&slope_ij, &slope_jk) >= 0) { |
||
175 | if (i == k) |
||
176 | return; |
||
177 | hull[j].discard = 1; |
||
178 | j = i; |
||
179 | i = _cairo_hull_prev_valid (hull, num_hull, j); |
||
180 | } else { |
||
181 | i = j; |
||
182 | j = k; |
||
183 | k = _cairo_hull_next_valid (hull, num_hull, j); |
||
184 | } |
||
185 | } while (j != 0); |
||
186 | } |
||
187 | |||
188 | static void |
||
189 | _cairo_hull_to_pen (cairo_hull_t *hull, cairo_pen_vertex_t *vertices, int *num_vertices) |
||
190 | { |
||
191 | int i, j = 0; |
||
192 | |||
193 | for (i = 0; i < *num_vertices; i++) { |
||
194 | if (hull[i].discard) |
||
195 | continue; |
||
196 | vertices[j++].point = hull[i].point; |
||
197 | } |
||
198 | |||
199 | *num_vertices = j; |
||
200 | } |
||
201 | |||
202 | /* Given a set of vertices, compute the convex hull using the Graham |
||
203 | scan algorithm. */ |
||
204 | cairo_status_t |
||
205 | _cairo_hull_compute (cairo_pen_vertex_t *vertices, int *num_vertices) |
||
206 | { |
||
207 | cairo_hull_t hull_stack[CAIRO_STACK_ARRAY_LENGTH (cairo_hull_t)]; |
||
208 | cairo_hull_t *hull; |
||
209 | int num_hull = *num_vertices; |
||
210 | |||
211 | if (CAIRO_INJECT_FAULT ()) |
||
212 | return _cairo_error (CAIRO_STATUS_NO_MEMORY); |
||
213 | |||
214 | if (num_hull > ARRAY_LENGTH (hull_stack)) { |
||
215 | hull = _cairo_malloc_ab (num_hull, sizeof (cairo_hull_t)); |
||
216 | if (unlikely (hull == NULL)) |
||
217 | return _cairo_error (CAIRO_STATUS_NO_MEMORY); |
||
218 | } else { |
||
219 | hull = hull_stack; |
||
220 | } |
||
221 | |||
222 | _cairo_hull_init (hull, vertices, num_hull); |
||
223 | |||
224 | qsort (hull + 1, num_hull - 1, |
||
225 | sizeof (cairo_hull_t), _cairo_hull_vertex_compare); |
||
226 | |||
227 | _cairo_hull_eliminate_concave (hull, num_hull); |
||
228 | |||
229 | _cairo_hull_to_pen (hull, vertices, num_vertices); |
||
230 | |||
231 | if (hull != hull_stack) |
||
232 | free (hull); |
||
233 | |||
234 | return CAIRO_STATUS_SUCCESS; |
||
235 | }>>>>>>> |