2 * Copyright 2015 Henri Verbeet for CodeWeavers
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2.1 of the License, or (at your option) any later version.
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
20 #include "wine/port.h"
22 #include "d2d1_private.h"
27 WINE_DEFAULT_DEBUG_CHANNEL(d2d
);
29 #define D2D_CDT_EDGE_FLAG_FREED 0x80000000u
30 #define D2D_CDT_EDGE_FLAG_VISITED(r) (1u << (r))
32 #define D2D_FP_EPS (1.0f / (1 << FLT_MANT_DIG))
34 static const D2D1_MATRIX_3X2_F identity
=
41 enum d2d_cdt_edge_next
43 D2D_EDGE_NEXT_ORIGIN
= 0,
44 D2D_EDGE_NEXT_ROT
= 1,
45 D2D_EDGE_NEXT_SYM
= 2,
46 D2D_EDGE_NEXT_TOR
= 3,
53 D2D_VERTEX_TYPE_BEZIER
,
58 D2D1_POINT_2F
*vertices
;
60 enum d2d_vertex_type
*vertex_types
;
61 size_t vertex_types_size
;
64 D2D1_POINT_2F
*bezier_controls
;
65 size_t bezier_controls_size
;
66 size_t bezier_control_count
;
71 struct d2d_cdt_edge_ref
74 enum d2d_cdt_edge_next r
;
79 struct d2d_cdt_edge_ref next
[4];
86 struct d2d_cdt_edge
*edges
;
91 const D2D1_POINT_2F
*vertices
;
94 struct d2d_geometry_intersection
102 struct d2d_geometry_intersections
104 struct d2d_geometry_intersection
*intersections
;
105 size_t intersections_size
;
106 size_t intersection_count
;
109 struct d2d_fp_two_vec2
121 static void d2d_bezier_vertex_set(struct d2d_bezier_vertex
*b
,
122 const D2D1_POINT_2F
*p
, float u
, float v
, float sign
)
127 b
->texcoord
.sign
= sign
;
130 static void d2d_fp_two_sum(float *out
, float a
, float b
)
132 float a_virt
, a_round
, b_virt
, b_round
;
136 a_virt
= out
[1] - b_virt
;
137 b_round
= b
- b_virt
;
138 a_round
= a
- a_virt
;
139 out
[0] = a_round
+ b_round
;
142 static void d2d_fp_fast_two_sum(float *out
, float a
, float b
)
151 static void d2d_fp_two_two_sum(float *out
, const float *a
, const float *b
)
155 d2d_fp_two_sum(out
, a
[0], b
[0]);
156 d2d_fp_two_sum(sum
, a
[1], out
[1]);
157 d2d_fp_two_sum(&out
[1], sum
[0], b
[1]);
158 d2d_fp_two_sum(&out
[2], sum
[1], out
[2]);
161 static void d2d_fp_two_diff_tail(float *out
, float a
, float b
, float x
)
163 float a_virt
, a_round
, b_virt
, b_round
;
167 b_round
= b_virt
- b
;
168 a_round
= a
- a_virt
;
169 *out
= a_round
+ b_round
;
172 static void d2d_fp_two_two_diff(float *out
, const float *a
, const float *b
)
177 d2d_fp_two_diff_tail(out
, a
[0], b
[0], diff
);
178 d2d_fp_two_sum(sum
, a
[1], diff
);
179 diff
= sum
[0] - b
[1];
180 d2d_fp_two_diff_tail(&out
[1], sum
[0], b
[1], diff
);
181 d2d_fp_two_sum(&out
[2], sum
[1], diff
);
184 static void d2d_fp_split(float *out
, float a
)
188 c
= a
* ((1 << (FLT_MANT_DIG
/ 2)) + 1.0f
);
194 static void d2d_fp_two_product_presplit(float *out
, float a
, float b
, const float *b_split
)
196 float a_split
[2], err1
, err2
, err3
;
199 d2d_fp_split(a_split
, a
);
200 err1
= out
[1] - (a_split
[1] * b_split
[1]);
201 err2
= err1
- (a_split
[0] * b_split
[1]);
202 err3
= err2
- (a_split
[1] * b_split
[0]);
203 out
[0] = (a_split
[0] * b_split
[0]) - err3
;
206 static void d2d_fp_two_product(float *out
, float a
, float b
)
210 d2d_fp_split(b_split
, b
);
211 d2d_fp_two_product_presplit(out
, a
, b
, b_split
);
214 static void d2d_fp_square(float *out
, float a
)
216 float a_split
[2], err1
, err2
;
219 d2d_fp_split(a_split
, a
);
220 err1
= out
[1] - (a_split
[1] * a_split
[1]);
221 err2
= err1
- ((a_split
[1] + a_split
[1]) * a_split
[0]);
222 out
[0] = (a_split
[0] * a_split
[0]) - err2
;
225 static float d2d_fp_estimate(float *a
, size_t len
)
236 static void d2d_fp_fast_expansion_sum_zeroelim(float *out
, size_t *out_len
,
237 const float *a
, size_t a_len
, const float *b
, size_t b_len
)
239 float sum
[2], q
, a_curr
, b_curr
;
240 size_t a_idx
, b_idx
, out_idx
;
245 if ((b_curr
> a_curr
) == (b_curr
> -a_curr
))
256 if (a_idx
< a_len
&& b_idx
< b_len
)
258 if ((b_curr
> a_curr
) == (b_curr
> -a_curr
))
260 d2d_fp_fast_two_sum(sum
, a_curr
, q
);
265 d2d_fp_fast_two_sum(sum
, b_curr
, q
);
269 out
[out_idx
++] = sum
[0];
271 while (a_idx
< a_len
&& b_idx
< b_len
)
273 if ((b_curr
> a_curr
) == (b_curr
> -a_curr
))
275 d2d_fp_two_sum(sum
, q
, a_curr
);
280 d2d_fp_two_sum(sum
, q
, b_curr
);
284 out
[out_idx
++] = sum
[0];
288 while (a_idx
< a_len
)
290 d2d_fp_two_sum(sum
, q
, a_curr
);
293 out
[out_idx
++] = sum
[0];
296 while (b_idx
< b_len
)
298 d2d_fp_two_sum(sum
, q
, b_curr
);
301 out
[out_idx
++] = sum
[0];
304 if (q
!= 0.0f
|| !out_idx
)
310 static void d2d_fp_scale_expansion_zeroelim(float *out
, size_t *out_len
, const float *a
, size_t a_len
, float b
)
312 float product
[2], sum
[2], b_split
[2], q
[2], a_curr
;
313 size_t a_idx
, out_idx
;
315 d2d_fp_split(b_split
, b
);
316 d2d_fp_two_product_presplit(q
, a
[0], b
, b_split
);
319 out
[out_idx
++] = q
[0];
320 for (a_idx
= 1; a_idx
< a_len
; ++a_idx
)
323 d2d_fp_two_product_presplit(product
, a_curr
, b
, b_split
);
324 d2d_fp_two_sum(sum
, q
[1], product
[0]);
326 out
[out_idx
++] = sum
[0];
327 d2d_fp_fast_two_sum(q
, product
[1], sum
[1]);
329 out
[out_idx
++] = q
[0];
331 if (q
[1] != 0.0f
|| !out_idx
)
332 out
[out_idx
++] = q
[1];
337 static void d2d_point_subtract(D2D1_POINT_2F
*out
,
338 const D2D1_POINT_2F
*a
, const D2D1_POINT_2F
*b
)
340 out
->x
= a
->x
- b
->x
;
341 out
->y
= a
->y
- b
->y
;
344 /* This implementation is based on the paper "Adaptive Precision
345 * Floating-Point Arithmetic and Fast Robust Geometric Predicates" and
346 * associated (Public Domain) code by Jonathan Richard Shewchuk. */
347 static float d2d_point_ccw(const D2D1_POINT_2F
*a
, const D2D1_POINT_2F
*b
, const D2D1_POINT_2F
*c
)
349 static const float err_bound_result
= (3.0f
+ 8.0f
* D2D_FP_EPS
) * D2D_FP_EPS
;
350 static const float err_bound_a
= (3.0f
+ 16.0f
* D2D_FP_EPS
) * D2D_FP_EPS
;
351 static const float err_bound_b
= (2.0f
+ 12.0f
* D2D_FP_EPS
) * D2D_FP_EPS
;
352 static const float err_bound_c
= (9.0f
+ 64.0f
* D2D_FP_EPS
) * D2D_FP_EPS
* D2D_FP_EPS
;
353 float det_d
[16], det_c2
[12], det_c1
[8], det_b
[4], temp4
[4], temp2a
[2], temp2b
[2], abxacy
[2], abyacx
[2];
354 size_t det_d_len
, det_c2_len
, det_c1_len
;
355 float det
, det_sum
, err_bound
;
356 struct d2d_fp_two_vec2 ab
, ac
;
358 ab
.x
[1] = b
->x
- a
->x
;
359 ab
.y
[1] = b
->y
- a
->y
;
360 ac
.x
[1] = c
->x
- a
->x
;
361 ac
.y
[1] = c
->y
- a
->y
;
363 abxacy
[1] = ab
.x
[1] * ac
.y
[1];
364 abyacx
[1] = ab
.y
[1] * ac
.x
[1];
365 det
= abxacy
[1] - abyacx
[1];
367 if (abxacy
[1] > 0.0f
)
369 if (abyacx
[1] <= 0.0f
)
371 det_sum
= abxacy
[1] + abyacx
[1];
373 else if (abxacy
[1] < 0.0f
)
375 if (abyacx
[1] >= 0.0f
)
377 det_sum
= -abxacy
[1] - abyacx
[1];
384 err_bound
= err_bound_a
* det_sum
;
385 if (det
>= err_bound
|| -det
>= err_bound
)
388 d2d_fp_two_product(abxacy
, ab
.x
[1], ac
.y
[1]);
389 d2d_fp_two_product(abyacx
, ab
.y
[1], ac
.x
[1]);
390 d2d_fp_two_two_diff(det_b
, abxacy
, abyacx
);
392 det
= d2d_fp_estimate(det_b
, 4);
393 err_bound
= err_bound_b
* det_sum
;
394 if (det
>= err_bound
|| -det
>= err_bound
)
397 d2d_fp_two_diff_tail(&ab
.x
[0], b
->x
, a
->x
, ab
.x
[1]);
398 d2d_fp_two_diff_tail(&ab
.y
[0], b
->y
, a
->y
, ab
.y
[1]);
399 d2d_fp_two_diff_tail(&ac
.x
[0], c
->x
, a
->x
, ac
.x
[1]);
400 d2d_fp_two_diff_tail(&ac
.y
[0], c
->y
, a
->y
, ac
.y
[1]);
402 if (ab
.x
[0] == 0.0f
&& ab
.y
[0] == 0.0f
&& ac
.x
[0] == 0.0f
&& ac
.y
[0] == 0.0f
)
405 err_bound
= err_bound_c
* det_sum
+ err_bound_result
* fabsf(det
);
406 det
+= (ab
.x
[1] * ac
.y
[0] + ac
.y
[1] * ab
.x
[0]) - (ab
.y
[1] * ac
.x
[0] + ac
.x
[1] * ab
.y
[0]);
407 if (det
>= err_bound
|| -det
>= err_bound
)
410 d2d_fp_two_product(temp2a
, ab
.x
[0], ac
.y
[1]);
411 d2d_fp_two_product(temp2b
, ab
.y
[0], ac
.x
[1]);
412 d2d_fp_two_two_diff(temp4
, temp2a
, temp2b
);
413 d2d_fp_fast_expansion_sum_zeroelim(det_c1
, &det_c1_len
, det_b
, 4, temp4
, 4);
415 d2d_fp_two_product(temp2a
, ab
.x
[1], ac
.y
[0]);
416 d2d_fp_two_product(temp2b
, ab
.y
[1], ac
.x
[0]);
417 d2d_fp_two_two_diff(temp4
, temp2a
, temp2b
);
418 d2d_fp_fast_expansion_sum_zeroelim(det_c2
, &det_c2_len
, det_c1
, det_c1_len
, temp4
, 4);
420 d2d_fp_two_product(temp2a
, ab
.x
[0], ac
.y
[0]);
421 d2d_fp_two_product(temp2b
, ab
.y
[0], ac
.x
[0]);
422 d2d_fp_two_two_diff(temp4
, temp2a
, temp2b
);
423 d2d_fp_fast_expansion_sum_zeroelim(det_d
, &det_d_len
, det_c2
, det_c2_len
, temp4
, 4);
425 return det_d
[det_d_len
- 1];
428 static BOOL
d2d_array_reserve(void **elements
, size_t *capacity
, size_t element_count
, size_t element_size
)
430 size_t new_capacity
, max_capacity
;
433 if (element_count
<= *capacity
)
436 max_capacity
= ~(size_t)0 / element_size
;
437 if (max_capacity
< element_count
)
440 new_capacity
= max(*capacity
, 4);
441 while (new_capacity
< element_count
&& new_capacity
<= max_capacity
/ 2)
444 if (new_capacity
< element_count
)
445 new_capacity
= max_capacity
;
448 new_elements
= HeapReAlloc(GetProcessHeap(), 0, *elements
, new_capacity
* element_size
);
450 new_elements
= HeapAlloc(GetProcessHeap(), 0, new_capacity
* element_size
);
455 *elements
= new_elements
;
456 *capacity
= new_capacity
;
460 static void d2d_figure_update_bounds(struct d2d_figure
*figure
, D2D1_POINT_2F vertex
)
462 if (vertex
.x
< figure
->bounds
.left
)
463 figure
->bounds
.left
= vertex
.x
;
464 if (vertex
.x
> figure
->bounds
.right
)
465 figure
->bounds
.right
= vertex
.x
;
466 if (vertex
.y
< figure
->bounds
.top
)
467 figure
->bounds
.top
= vertex
.y
;
468 if (vertex
.y
> figure
->bounds
.bottom
)
469 figure
->bounds
.bottom
= vertex
.y
;
472 static BOOL
d2d_figure_insert_vertex(struct d2d_figure
*figure
, size_t idx
, D2D1_POINT_2F vertex
)
474 if (!d2d_array_reserve((void **)&figure
->vertices
, &figure
->vertices_size
,
475 figure
->vertex_count
+ 1, sizeof(*figure
->vertices
)))
477 ERR("Failed to grow vertices array.\n");
481 if (!d2d_array_reserve((void **)&figure
->vertex_types
, &figure
->vertex_types_size
,
482 figure
->vertex_count
+ 1, sizeof(*figure
->vertex_types
)))
484 ERR("Failed to grow vertex types array.\n");
488 memmove(&figure
->vertices
[idx
+ 1], &figure
->vertices
[idx
],
489 (figure
->vertex_count
- idx
) * sizeof(*figure
->vertices
));
490 memmove(&figure
->vertex_types
[idx
+ 1], &figure
->vertex_types
[idx
],
491 (figure
->vertex_count
- idx
) * sizeof(*figure
->vertex_types
));
492 figure
->vertices
[idx
] = vertex
;
493 figure
->vertex_types
[idx
] = D2D_VERTEX_TYPE_NONE
;
494 d2d_figure_update_bounds(figure
, vertex
);
495 ++figure
->vertex_count
;
499 static BOOL
d2d_figure_add_vertex(struct d2d_figure
*figure
, D2D1_POINT_2F vertex
)
501 if (!d2d_array_reserve((void **)&figure
->vertices
, &figure
->vertices_size
,
502 figure
->vertex_count
+ 1, sizeof(*figure
->vertices
)))
504 ERR("Failed to grow vertices array.\n");
508 if (!d2d_array_reserve((void **)&figure
->vertex_types
, &figure
->vertex_types_size
,
509 figure
->vertex_count
+ 1, sizeof(*figure
->vertex_types
)))
511 ERR("Failed to grow vertex types array.\n");
515 figure
->vertices
[figure
->vertex_count
] = vertex
;
516 figure
->vertex_types
[figure
->vertex_count
] = D2D_VERTEX_TYPE_NONE
;
517 d2d_figure_update_bounds(figure
, vertex
);
518 ++figure
->vertex_count
;
522 static BOOL
d2d_figure_add_bezier_control(struct d2d_figure
*figure
, const D2D1_POINT_2F
*p
)
524 if (!d2d_array_reserve((void **)&figure
->bezier_controls
, &figure
->bezier_controls_size
,
525 figure
->bezier_control_count
+ 1, sizeof(*figure
->bezier_controls
)))
527 ERR("Failed to grow bezier controls array.\n");
531 figure
->bezier_controls
[figure
->bezier_control_count
++] = *p
;
536 static void d2d_cdt_edge_rot(struct d2d_cdt_edge_ref
*dst
, const struct d2d_cdt_edge_ref
*src
)
539 dst
->r
= (src
->r
+ D2D_EDGE_NEXT_ROT
) & 3;
542 static void d2d_cdt_edge_sym(struct d2d_cdt_edge_ref
*dst
, const struct d2d_cdt_edge_ref
*src
)
545 dst
->r
= (src
->r
+ D2D_EDGE_NEXT_SYM
) & 3;
548 static void d2d_cdt_edge_tor(struct d2d_cdt_edge_ref
*dst
, const struct d2d_cdt_edge_ref
*src
)
551 dst
->r
= (src
->r
+ D2D_EDGE_NEXT_TOR
) & 3;
554 static void d2d_cdt_edge_next_left(const struct d2d_cdt
*cdt
,
555 struct d2d_cdt_edge_ref
*dst
, const struct d2d_cdt_edge_ref
*src
)
557 d2d_cdt_edge_rot(dst
, &cdt
->edges
[src
->idx
].next
[(src
->r
+ D2D_EDGE_NEXT_TOR
) & 3]);
560 static void d2d_cdt_edge_next_origin(const struct d2d_cdt
*cdt
,
561 struct d2d_cdt_edge_ref
*dst
, const struct d2d_cdt_edge_ref
*src
)
563 *dst
= cdt
->edges
[src
->idx
].next
[src
->r
];
566 static void d2d_cdt_edge_prev_origin(const struct d2d_cdt
*cdt
,
567 struct d2d_cdt_edge_ref
*dst
, const struct d2d_cdt_edge_ref
*src
)
569 d2d_cdt_edge_rot(dst
, &cdt
->edges
[src
->idx
].next
[(src
->r
+ D2D_EDGE_NEXT_ROT
) & 3]);
572 static size_t d2d_cdt_edge_origin(const struct d2d_cdt
*cdt
, const struct d2d_cdt_edge_ref
*e
)
574 return cdt
->edges
[e
->idx
].vertex
[e
->r
>> 1];
577 static size_t d2d_cdt_edge_destination(const struct d2d_cdt
*cdt
, const struct d2d_cdt_edge_ref
*e
)
579 return cdt
->edges
[e
->idx
].vertex
[!(e
->r
>> 1)];
582 static void d2d_cdt_edge_set_origin(const struct d2d_cdt
*cdt
,
583 const struct d2d_cdt_edge_ref
*e
, size_t vertex
)
585 cdt
->edges
[e
->idx
].vertex
[e
->r
>> 1] = vertex
;
588 static void d2d_cdt_edge_set_destination(const struct d2d_cdt
*cdt
,
589 const struct d2d_cdt_edge_ref
*e
, size_t vertex
)
591 cdt
->edges
[e
->idx
].vertex
[!(e
->r
>> 1)] = vertex
;
594 static float d2d_cdt_ccw(const struct d2d_cdt
*cdt
, size_t a
, size_t b
, size_t c
)
596 return d2d_point_ccw(&cdt
->vertices
[a
], &cdt
->vertices
[b
], &cdt
->vertices
[c
]);
599 static BOOL
d2d_cdt_rightof(const struct d2d_cdt
*cdt
, size_t p
, const struct d2d_cdt_edge_ref
*e
)
601 return d2d_cdt_ccw(cdt
, p
, d2d_cdt_edge_destination(cdt
, e
), d2d_cdt_edge_origin(cdt
, e
)) > 0.0f
;
604 static BOOL
d2d_cdt_leftof(const struct d2d_cdt
*cdt
, size_t p
, const struct d2d_cdt_edge_ref
*e
)
606 return d2d_cdt_ccw(cdt
, p
, d2d_cdt_edge_origin(cdt
, e
), d2d_cdt_edge_destination(cdt
, e
)) > 0.0f
;
611 static void d2d_fp_four_det2x2(float *out
, float ax
, float ay
, float bx
, float by
)
613 float axby
[2], aybx
[2];
615 d2d_fp_two_product(axby
, ax
, by
);
616 d2d_fp_two_product(aybx
, ay
, bx
);
617 d2d_fp_two_two_diff(out
, axby
, aybx
);
620 /* (a->x² + a->y²) * det2x2 */
621 static void d2d_fp_sub_det3x3(float *out
, size_t *out_len
, const struct d2d_fp_two_vec2
*a
, const float *det2x2
)
623 size_t axd_len
, ayd_len
, axxd_len
, ayyd_len
;
624 float axd
[8], ayd
[8], axxd
[16], ayyd
[16];
626 d2d_fp_scale_expansion_zeroelim(axd
, &axd_len
, det2x2
, 4, a
->x
[1]);
627 d2d_fp_scale_expansion_zeroelim(axxd
, &axxd_len
, axd
, axd_len
, a
->x
[1]);
628 d2d_fp_scale_expansion_zeroelim(ayd
, &ayd_len
, det2x2
, 4, a
->y
[1]);
629 d2d_fp_scale_expansion_zeroelim(ayyd
, &ayyd_len
, ayd
, ayd_len
, a
->y
[1]);
630 d2d_fp_fast_expansion_sum_zeroelim(out
, out_len
, axxd
, axxd_len
, ayyd
, ayyd_len
);
633 /* det_abt = det_ab * c[0]
634 * fin += c[0] * (az * b - bz * a + c[1] * det_ab * 2.0f) */
635 static void d2d_cdt_incircle_refine1(struct d2d_fp_fin
*fin
, float *det_abt
, size_t *det_abt_len
,
636 const float *det_ab
, float a
, const float *az
, float b
, const float *bz
, const float *c
)
638 size_t temp48_len
, temp32_len
, temp16a_len
, temp16b_len
, temp16c_len
, temp8_len
;
639 float temp48
[48], temp32
[32], temp16a
[16], temp16b
[16], temp16c
[16], temp8
[8];
642 d2d_fp_scale_expansion_zeroelim(det_abt
, det_abt_len
, det_ab
, 4, c
[0]);
643 d2d_fp_scale_expansion_zeroelim(temp16a
, &temp16a_len
, det_abt
, *det_abt_len
, 2.0f
* c
[1]);
644 d2d_fp_scale_expansion_zeroelim(temp8
, &temp8_len
, az
, 4, c
[0]);
645 d2d_fp_scale_expansion_zeroelim(temp16b
, &temp16b_len
, temp8
, temp8_len
, b
);
646 d2d_fp_scale_expansion_zeroelim(temp8
, &temp8_len
, bz
, 4, c
[0]);
647 d2d_fp_scale_expansion_zeroelim(temp16c
, &temp16c_len
, temp8
, temp8_len
, -a
);
648 d2d_fp_fast_expansion_sum_zeroelim(temp32
, &temp32_len
, temp16a
, temp16a_len
, temp16b
, temp16b_len
);
649 d2d_fp_fast_expansion_sum_zeroelim(temp48
, &temp48_len
, temp16c
, temp16c_len
, temp32
, temp32_len
);
650 d2d_fp_fast_expansion_sum_zeroelim(fin
->other
, &fin
->length
, fin
->now
, fin
->length
, temp48
, temp48_len
);
651 swap
= fin
->now
; fin
->now
= fin
->other
; fin
->other
= swap
;
654 static void d2d_cdt_incircle_refine2(struct d2d_fp_fin
*fin
, const struct d2d_fp_two_vec2
*a
,
655 const struct d2d_fp_two_vec2
*b
, const float *bz
, const struct d2d_fp_two_vec2
*c
, const float *cz
,
656 const float *axt_det_bc
, size_t axt_det_bc_len
, const float *ayt_det_bc
, size_t ayt_det_bc_len
)
658 size_t temp64_len
, temp48_len
, temp32a_len
, temp32b_len
, temp16a_len
, temp16b_len
, temp8_len
;
659 float temp64
[64], temp48
[48], temp32a
[32], temp32b
[32], temp16a
[16], temp16b
[16], temp8
[8];
660 float bct
[8], bctt
[4], temp4a
[4], temp4b
[4], temp2a
[2], temp2b
[2];
661 size_t bct_len
, bctt_len
;
664 /* bct = (b->x[0] * c->y[1] + b->x[1] * c->y[0]) - (c->x[0] * b->y[1] + c->x[1] * b->y[0]) */
665 /* bctt = b->x[0] * c->y[0] + c->x[0] * b->y[0] */
666 if (b
->x
[0] != 0.0f
|| b
->y
[0] != 0.0f
|| c
->x
[0] != 0.0f
|| c
->y
[0] != 0.0f
)
668 d2d_fp_two_product(temp2a
, b
->x
[0], c
->y
[1]);
669 d2d_fp_two_product(temp2b
, b
->x
[1], c
->y
[0]);
670 d2d_fp_two_two_sum(temp4a
, temp2a
, temp2b
);
671 d2d_fp_two_product(temp2a
, c
->x
[0], -b
->y
[1]);
672 d2d_fp_two_product(temp2b
, c
->x
[1], -b
->y
[0]);
673 d2d_fp_two_two_sum(temp4b
, temp2a
, temp2b
);
674 d2d_fp_fast_expansion_sum_zeroelim(bct
, &bct_len
, temp4a
, 4, temp4b
, 4);
676 d2d_fp_two_product(temp2a
, b
->x
[0], c
->y
[0]);
677 d2d_fp_two_product(temp2b
, c
->x
[0], b
->y
[0]);
678 d2d_fp_two_two_diff(bctt
, temp2a
, temp2b
);
691 size_t axt_bct_len
, axt_bctt_len
;
692 float axt_bct
[16], axt_bctt
[8];
694 /* fin += a->x[0] * (axt_det_bc + bct * 2.0f * a->x[1]) */
695 d2d_fp_scale_expansion_zeroelim(temp16a
, &temp16a_len
, axt_det_bc
, axt_det_bc_len
, a
->x
[0]);
696 d2d_fp_scale_expansion_zeroelim(axt_bct
, &axt_bct_len
, bct
, bct_len
, a
->x
[0]);
697 d2d_fp_scale_expansion_zeroelim(temp32a
, &temp32a_len
, axt_bct
, axt_bct_len
, 2.0f
* a
->x
[1]);
698 d2d_fp_fast_expansion_sum_zeroelim(temp48
, &temp48_len
, temp16a
, temp16a_len
, temp32a
, temp32a_len
);
699 d2d_fp_fast_expansion_sum_zeroelim(fin
->other
, &fin
->length
, fin
->now
, fin
->length
, temp48
, temp48_len
);
700 swap
= fin
->now
; fin
->now
= fin
->other
; fin
->other
= swap
;
704 /* fin += a->x[0] * cz * b->y[0] */
705 d2d_fp_scale_expansion_zeroelim(temp8
, &temp8_len
, cz
, 4, a
->x
[0]);
706 d2d_fp_scale_expansion_zeroelim(temp16a
, &temp16a_len
, temp8
, temp8_len
, b
->y
[0]);
707 d2d_fp_fast_expansion_sum_zeroelim(fin
->other
, &fin
->length
, fin
->now
, fin
->length
, temp16a
, temp16a_len
);
708 swap
= fin
->now
; fin
->now
= fin
->other
; fin
->other
= swap
;
713 /* fin -= a->x[0] * bz * c->y[0] */
714 d2d_fp_scale_expansion_zeroelim(temp8
, &temp8_len
, bz
, 4, -a
->x
[0]);
715 d2d_fp_scale_expansion_zeroelim(temp16a
, &temp16a_len
, temp8
, temp8_len
, c
->y
[0]);
716 d2d_fp_fast_expansion_sum_zeroelim(fin
->other
, &fin
->length
, fin
->now
, fin
->length
, temp16a
, temp16a_len
);
717 swap
= fin
->now
; fin
->now
= fin
->other
; fin
->other
= swap
;
720 /* fin += a->x[0] * (bct * a->x[0] + bctt * (2.0f * a->x[1] + a->x[0])) */
721 d2d_fp_scale_expansion_zeroelim(temp32a
, &temp32a_len
, axt_bct
, axt_bct_len
, a
->x
[0]);
722 d2d_fp_scale_expansion_zeroelim(axt_bctt
, &axt_bctt_len
, bctt
, bctt_len
, a
->x
[0]);
723 d2d_fp_scale_expansion_zeroelim(temp16a
, &temp16a_len
, axt_bctt
, axt_bctt_len
, 2.0f
* a
->x
[1]);
724 d2d_fp_scale_expansion_zeroelim(temp16b
, &temp16b_len
, axt_bctt
, axt_bctt_len
, a
->x
[0]);
725 d2d_fp_fast_expansion_sum_zeroelim(temp32b
, &temp32b_len
, temp16a
, temp16a_len
, temp16b
, temp16b_len
);
726 d2d_fp_fast_expansion_sum_zeroelim(temp64
, &temp64_len
, temp32a
, temp32a_len
, temp32b
, temp32b_len
);
727 d2d_fp_fast_expansion_sum_zeroelim(fin
->other
, &fin
->length
, fin
->now
, fin
->length
, temp64
, temp64_len
);
728 swap
= fin
->now
; fin
->now
= fin
->other
; fin
->other
= swap
;
733 size_t ayt_bct_len
, ayt_bctt_len
;
734 float ayt_bct
[16], ayt_bctt
[8];
736 /* fin += a->y[0] * (ayt_det_bc + bct * 2.0f * a->y[1]) */
737 d2d_fp_scale_expansion_zeroelim(temp16a
, &temp16a_len
, ayt_det_bc
, ayt_det_bc_len
, a
->y
[0]);
738 d2d_fp_scale_expansion_zeroelim(ayt_bct
, &ayt_bct_len
, bct
, bct_len
, a
->y
[0]);
739 d2d_fp_scale_expansion_zeroelim(temp32a
, &temp32a_len
, ayt_bct
, ayt_bct_len
, 2.0f
* a
->y
[1]);
740 d2d_fp_fast_expansion_sum_zeroelim(temp48
, &temp48_len
, temp16a
, temp16a_len
, temp32a
, temp32a_len
);
741 d2d_fp_fast_expansion_sum_zeroelim(fin
->other
, &fin
->length
, fin
->now
, fin
->length
, temp48
, temp48_len
);
742 swap
= fin
->now
; fin
->now
= fin
->other
; fin
->other
= swap
;
744 /* fin += a->y[0] * (bct * a->y[0] + bctt * (2.0f * a->y[1] + a->y[0])) */
745 d2d_fp_scale_expansion_zeroelim(temp32a
, &temp32a_len
, ayt_bct
, ayt_bct_len
, a
->y
[0]);
746 d2d_fp_scale_expansion_zeroelim(ayt_bctt
, &ayt_bctt_len
, bctt
, bctt_len
, a
->y
[0]);
747 d2d_fp_scale_expansion_zeroelim(temp16a
, &temp16a_len
, ayt_bctt
, ayt_bctt_len
, 2.0f
* a
->y
[1]);
748 d2d_fp_scale_expansion_zeroelim(temp16b
, &temp16b_len
, ayt_bctt
, ayt_bctt_len
, a
->y
[0]);
749 d2d_fp_fast_expansion_sum_zeroelim(temp32b
, &temp32b_len
, temp16a
, temp16a_len
, temp16b
, temp16b_len
);
750 d2d_fp_fast_expansion_sum_zeroelim(temp64
, &temp64_len
, temp32a
, temp32a_len
, temp32b
, temp32b_len
);
751 d2d_fp_fast_expansion_sum_zeroelim(fin
->other
, &fin
->length
, fin
->now
, fin
->length
, temp64
, temp64_len
);
752 swap
= fin
->now
; fin
->now
= fin
->other
; fin
->other
= swap
;
756 /* Determine if point D is inside or outside the circle defined by points A,
757 * B, C. As explained in the paper by Guibas and Stolfi, this is equivalent to
758 * calculating the signed volume of the tetrahedron defined by projecting the
759 * points onto the paraboloid of revolution x = x² + y²,
760 * λ:(x, y) → (x, y, x² + y²). I.e., D is inside the cirlce if
767 * After translating D to the origin, that becomes:
773 * This implementation is based on the paper "Adaptive Precision
774 * Floating-Point Arithmetic and Fast Robust Geometric Predicates" and
775 * associated (Public Domain) code by Jonathan Richard Shewchuk. */
776 static BOOL
d2d_cdt_incircle(const struct d2d_cdt
*cdt
, size_t a
, size_t b
, size_t c
, size_t d
)
778 static const float err_bound_result
= (3.0f
+ 8.0f
* D2D_FP_EPS
) * D2D_FP_EPS
;
779 static const float err_bound_a
= (10.0f
+ 96.0f
* D2D_FP_EPS
) * D2D_FP_EPS
;
780 static const float err_bound_b
= (4.0f
+ 48.0f
* D2D_FP_EPS
) * D2D_FP_EPS
;
781 static const float err_bound_c
= (44.0f
+ 576.0f
* D2D_FP_EPS
) * D2D_FP_EPS
* D2D_FP_EPS
;
783 size_t axt_det_bc_len
, ayt_det_bc_len
, bxt_det_ca_len
, byt_det_ca_len
, cxt_det_ab_len
, cyt_det_ab_len
;
784 float axt_det_bc
[8], ayt_det_bc
[8], bxt_det_ca
[8], byt_det_ca
[8], cxt_det_ab
[8], cyt_det_ab
[8];
785 float fin1
[1152], fin2
[1152], temp64
[64], sub_det_a
[32], sub_det_b
[32], sub_det_c
[32];
786 float det_bc
[4], det_ca
[4], det_ab
[4], daz
[4], dbz
[4], dcz
[4], temp2a
[2], temp2b
[2];
787 size_t temp64_len
, sub_det_a_len
, sub_det_b_len
, sub_det_c_len
;
788 float dbxdcy
, dbydcx
, dcxday
, dcydax
, daxdby
, daydbx
;
789 const D2D1_POINT_2F
*p
= cdt
->vertices
;
790 struct d2d_fp_two_vec2 da
, db
, dc
;
791 float permanent
, err_bound
, det
;
792 struct d2d_fp_fin fin
;
794 da
.x
[1] = p
[a
].x
- p
[d
].x
;
795 da
.y
[1] = p
[a
].y
- p
[d
].y
;
796 db
.x
[1] = p
[b
].x
- p
[d
].x
;
797 db
.y
[1] = p
[b
].y
- p
[d
].y
;
798 dc
.x
[1] = p
[c
].x
- p
[d
].x
;
799 dc
.y
[1] = p
[c
].y
- p
[d
].y
;
801 daz
[3] = da
.x
[1] * da
.x
[1] + da
.y
[1] * da
.y
[1];
802 dbxdcy
= db
.x
[1] * dc
.y
[1];
803 dbydcx
= db
.y
[1] * dc
.x
[1];
805 dbz
[3] = db
.x
[1] * db
.x
[1] + db
.y
[1] * db
.y
[1];
806 dcxday
= dc
.x
[1] * da
.y
[1];
807 dcydax
= dc
.y
[1] * da
.x
[1];
809 dcz
[3] = dc
.x
[1] * dc
.x
[1] + dc
.y
[1] * dc
.y
[1];
810 daxdby
= da
.x
[1] * db
.y
[1];
811 daydbx
= da
.y
[1] * db
.x
[1];
813 det
= daz
[3] * (dbxdcy
- dbydcx
) + dbz
[3] * (dcxday
- dcydax
) + dcz
[3] * (daxdby
- daydbx
);
814 permanent
= daz
[3] * (fabsf(dbxdcy
) + fabsf(dbydcx
))
815 + dbz
[3] * (fabsf(dcxday
) + fabsf(dcydax
))
816 + dcz
[3] * (fabsf(daxdby
) + fabsf(daydbx
));
817 err_bound
= err_bound_a
* permanent
;
818 if (det
> err_bound
|| -det
> err_bound
)
824 d2d_fp_four_det2x2(det_bc
, db
.x
[1], db
.y
[1], dc
.x
[1], dc
.y
[1]);
825 d2d_fp_sub_det3x3(sub_det_a
, &sub_det_a_len
, &da
, det_bc
);
827 d2d_fp_four_det2x2(det_ca
, dc
.x
[1], dc
.y
[1], da
.x
[1], da
.y
[1]);
828 d2d_fp_sub_det3x3(sub_det_b
, &sub_det_b_len
, &db
, det_ca
);
830 d2d_fp_four_det2x2(det_ab
, da
.x
[1], da
.y
[1], db
.x
[1], db
.y
[1]);
831 d2d_fp_sub_det3x3(sub_det_c
, &sub_det_c_len
, &dc
, det_ab
);
833 d2d_fp_fast_expansion_sum_zeroelim(temp64
, &temp64_len
, sub_det_a
, sub_det_a_len
, sub_det_b
, sub_det_b_len
);
834 d2d_fp_fast_expansion_sum_zeroelim(fin
.now
, &fin
.length
, temp64
, temp64_len
, sub_det_c
, sub_det_c_len
);
835 det
= d2d_fp_estimate(fin
.now
, fin
.length
);
836 err_bound
= err_bound_b
* permanent
;
837 if (det
>= err_bound
|| -det
>= err_bound
)
840 d2d_fp_two_diff_tail(&da
.x
[0], p
[a
].x
, p
[d
].x
, da
.x
[1]);
841 d2d_fp_two_diff_tail(&da
.y
[0], p
[a
].y
, p
[d
].y
, da
.y
[1]);
842 d2d_fp_two_diff_tail(&db
.x
[0], p
[b
].x
, p
[d
].x
, db
.x
[1]);
843 d2d_fp_two_diff_tail(&db
.y
[0], p
[b
].y
, p
[d
].y
, db
.y
[1]);
844 d2d_fp_two_diff_tail(&dc
.x
[0], p
[c
].x
, p
[d
].x
, dc
.x
[1]);
845 d2d_fp_two_diff_tail(&dc
.y
[0], p
[c
].y
, p
[d
].y
, dc
.y
[1]);
846 if (da
.x
[0] == 0.0f
&& db
.x
[0] == 0.0f
&& dc
.x
[0] == 0.0f
847 && da
.y
[0] == 0.0f
&& db
.y
[0] == 0.0f
&& dc
.y
[0] == 0.0f
)
850 err_bound
= err_bound_c
* permanent
+ err_bound_result
* fabsf(det
);
851 det
+= (daz
[3] * ((db
.x
[1] * dc
.y
[0] + dc
.y
[1] * db
.x
[0]) - (db
.y
[1] * dc
.x
[0] + dc
.x
[1] * db
.y
[0]))
852 + 2.0f
* (da
.x
[1] * da
.x
[0] + da
.y
[1] * da
.y
[0]) * (db
.x
[1] * dc
.y
[1] - db
.y
[1] * dc
.x
[1]))
853 + (dbz
[3] * ((dc
.x
[1] * da
.y
[0] + da
.y
[1] * dc
.x
[0]) - (dc
.y
[1] * da
.x
[0] + da
.x
[1] * dc
.y
[0]))
854 + 2.0f
* (db
.x
[1] * db
.x
[0] + db
.y
[1] * db
.y
[0]) * (dc
.x
[1] * da
.y
[1] - dc
.y
[1] * da
.x
[1]))
855 + (dcz
[3] * ((da
.x
[1] * db
.y
[0] + db
.y
[1] * da
.x
[0]) - (da
.y
[1] * db
.x
[0] + db
.x
[1] * da
.y
[0]))
856 + 2.0f
* (dc
.x
[1] * dc
.x
[0] + dc
.y
[1] * dc
.y
[0]) * (da
.x
[1] * db
.y
[1] - da
.y
[1] * db
.x
[1]));
857 if (det
>= err_bound
|| -det
>= err_bound
)
860 if (db
.x
[0] != 0.0f
|| db
.y
[0] != 0.0f
|| dc
.x
[0] != 0.0f
|| dc
.y
[0] != 0.0f
)
862 d2d_fp_square(temp2a
, da
.x
[1]);
863 d2d_fp_square(temp2b
, da
.y
[1]);
864 d2d_fp_two_two_sum(daz
, temp2a
, temp2b
);
866 if (dc
.x
[0] != 0.0f
|| dc
.y
[0] != 0.0f
|| da
.x
[0] != 0.0f
|| da
.y
[0] != 0.0f
)
868 d2d_fp_square(temp2a
, db
.x
[1]);
869 d2d_fp_square(temp2b
, db
.y
[1]);
870 d2d_fp_two_two_sum(dbz
, temp2a
, temp2b
);
872 if (da
.x
[0] != 0.0f
|| da
.y
[0] != 0.0f
|| db
.x
[0] != 0.0f
|| db
.y
[0] != 0.0f
)
874 d2d_fp_square(temp2a
, dc
.x
[1]);
875 d2d_fp_square(temp2b
, dc
.y
[1]);
876 d2d_fp_two_two_sum(dcz
, temp2a
, temp2b
);
880 d2d_cdt_incircle_refine1(&fin
, axt_det_bc
, &axt_det_bc_len
, det_bc
, dc
.y
[1], dcz
, db
.y
[1], dbz
, da
.x
);
882 d2d_cdt_incircle_refine1(&fin
, ayt_det_bc
, &ayt_det_bc_len
, det_bc
, db
.x
[1], dbz
, dc
.x
[1], dcz
, da
.y
);
884 d2d_cdt_incircle_refine1(&fin
, bxt_det_ca
, &bxt_det_ca_len
, det_ca
, da
.y
[1], daz
, dc
.y
[1], dcz
, db
.x
);
886 d2d_cdt_incircle_refine1(&fin
, byt_det_ca
, &byt_det_ca_len
, det_ca
, dc
.x
[1], dcz
, da
.x
[1], daz
, db
.y
);
888 d2d_cdt_incircle_refine1(&fin
, cxt_det_ab
, &cxt_det_ab_len
, det_ab
, db
.y
[1], dbz
, da
.y
[1], daz
, dc
.x
);
890 d2d_cdt_incircle_refine1(&fin
, cyt_det_ab
, &cyt_det_ab_len
, det_ab
, da
.x
[1], daz
, db
.x
[1], dbz
, dc
.y
);
892 if (da
.x
[0] != 0.0f
|| da
.y
[0] != 0.0f
)
893 d2d_cdt_incircle_refine2(&fin
, &da
, &db
, dbz
, &dc
, dcz
,
894 axt_det_bc
, axt_det_bc_len
, ayt_det_bc
, ayt_det_bc_len
);
895 if (db
.x
[0] != 0.0f
|| db
.y
[0] != 0.0f
)
896 d2d_cdt_incircle_refine2(&fin
, &db
, &dc
, dcz
, &da
, daz
,
897 bxt_det_ca
, bxt_det_ca_len
, byt_det_ca
, byt_det_ca_len
);
898 if (dc
.x
[0] != 0.0f
|| dc
.y
[0] != 0.0f
)
899 d2d_cdt_incircle_refine2(&fin
, &dc
, &da
, daz
, &db
, dbz
,
900 cxt_det_ab
, cxt_det_ab_len
, cyt_det_ab
, cyt_det_ab_len
);
902 return fin
.now
[fin
.length
- 1] > 0.0f
;
905 static void d2d_cdt_splice(const struct d2d_cdt
*cdt
, const struct d2d_cdt_edge_ref
*a
,
906 const struct d2d_cdt_edge_ref
*b
)
908 struct d2d_cdt_edge_ref ta
, tb
, alpha
, beta
;
910 ta
= cdt
->edges
[a
->idx
].next
[a
->r
];
911 tb
= cdt
->edges
[b
->idx
].next
[b
->r
];
912 cdt
->edges
[a
->idx
].next
[a
->r
] = tb
;
913 cdt
->edges
[b
->idx
].next
[b
->r
] = ta
;
915 d2d_cdt_edge_rot(&alpha
, &ta
);
916 d2d_cdt_edge_rot(&beta
, &tb
);
918 ta
= cdt
->edges
[alpha
.idx
].next
[alpha
.r
];
919 tb
= cdt
->edges
[beta
.idx
].next
[beta
.r
];
920 cdt
->edges
[alpha
.idx
].next
[alpha
.r
] = tb
;
921 cdt
->edges
[beta
.idx
].next
[beta
.r
] = ta
;
924 static BOOL
d2d_cdt_create_edge(struct d2d_cdt
*cdt
, struct d2d_cdt_edge_ref
*e
)
926 struct d2d_cdt_edge
*edge
;
928 if (cdt
->free_edge
!= ~0u)
930 e
->idx
= cdt
->free_edge
;
931 cdt
->free_edge
= cdt
->edges
[e
->idx
].next
[D2D_EDGE_NEXT_ORIGIN
].idx
;
935 if (!d2d_array_reserve((void **)&cdt
->edges
, &cdt
->edges_size
, cdt
->edge_count
+ 1, sizeof(*cdt
->edges
)))
937 ERR("Failed to grow edges array.\n");
940 e
->idx
= cdt
->edge_count
++;
944 edge
= &cdt
->edges
[e
->idx
];
945 edge
->next
[D2D_EDGE_NEXT_ORIGIN
] = *e
;
946 d2d_cdt_edge_tor(&edge
->next
[D2D_EDGE_NEXT_ROT
], e
);
947 d2d_cdt_edge_sym(&edge
->next
[D2D_EDGE_NEXT_SYM
], e
);
948 d2d_cdt_edge_rot(&edge
->next
[D2D_EDGE_NEXT_TOR
], e
);
954 static void d2d_cdt_destroy_edge(struct d2d_cdt
*cdt
, const struct d2d_cdt_edge_ref
*e
)
956 struct d2d_cdt_edge_ref next
, sym
, prev
;
958 d2d_cdt_edge_next_origin(cdt
, &next
, e
);
959 if (next
.idx
!= e
->idx
|| next
.r
!= e
->r
)
961 d2d_cdt_edge_prev_origin(cdt
, &prev
, e
);
962 d2d_cdt_splice(cdt
, e
, &prev
);
965 d2d_cdt_edge_sym(&sym
, e
);
967 d2d_cdt_edge_next_origin(cdt
, &next
, &sym
);
968 if (next
.idx
!= sym
.idx
|| next
.r
!= sym
.r
)
970 d2d_cdt_edge_prev_origin(cdt
, &prev
, &sym
);
971 d2d_cdt_splice(cdt
, &sym
, &prev
);
974 cdt
->edges
[e
->idx
].flags
|= D2D_CDT_EDGE_FLAG_FREED
;
975 cdt
->edges
[e
->idx
].next
[D2D_EDGE_NEXT_ORIGIN
].idx
= cdt
->free_edge
;
976 cdt
->free_edge
= e
->idx
;
979 static BOOL
d2d_cdt_connect(struct d2d_cdt
*cdt
, struct d2d_cdt_edge_ref
*e
,
980 const struct d2d_cdt_edge_ref
*a
, const struct d2d_cdt_edge_ref
*b
)
982 struct d2d_cdt_edge_ref tmp
;
984 if (!d2d_cdt_create_edge(cdt
, e
))
986 d2d_cdt_edge_set_origin(cdt
, e
, d2d_cdt_edge_destination(cdt
, a
));
987 d2d_cdt_edge_set_destination(cdt
, e
, d2d_cdt_edge_origin(cdt
, b
));
988 d2d_cdt_edge_next_left(cdt
, &tmp
, a
);
989 d2d_cdt_splice(cdt
, e
, &tmp
);
990 d2d_cdt_edge_sym(&tmp
, e
);
991 d2d_cdt_splice(cdt
, &tmp
, b
);
996 static BOOL
d2d_cdt_merge(struct d2d_cdt
*cdt
, struct d2d_cdt_edge_ref
*left_outer
,
997 struct d2d_cdt_edge_ref
*left_inner
, struct d2d_cdt_edge_ref
*right_inner
,
998 struct d2d_cdt_edge_ref
*right_outer
)
1000 struct d2d_cdt_edge_ref base_edge
, tmp
;
1002 /* Create the base edge between both parts. */
1005 if (d2d_cdt_leftof(cdt
, d2d_cdt_edge_origin(cdt
, right_inner
), left_inner
))
1007 d2d_cdt_edge_next_left(cdt
, left_inner
, left_inner
);
1009 else if (d2d_cdt_rightof(cdt
, d2d_cdt_edge_origin(cdt
, left_inner
), right_inner
))
1011 d2d_cdt_edge_sym(&tmp
, right_inner
);
1012 d2d_cdt_edge_next_origin(cdt
, right_inner
, &tmp
);
1020 d2d_cdt_edge_sym(&tmp
, right_inner
);
1021 if (!d2d_cdt_connect(cdt
, &base_edge
, &tmp
, left_inner
))
1023 if (d2d_cdt_edge_origin(cdt
, left_inner
) == d2d_cdt_edge_origin(cdt
, left_outer
))
1024 d2d_cdt_edge_sym(left_outer
, &base_edge
);
1025 if (d2d_cdt_edge_origin(cdt
, right_inner
) == d2d_cdt_edge_origin(cdt
, right_outer
))
1026 *right_outer
= base_edge
;
1030 struct d2d_cdt_edge_ref left_candidate
, right_candidate
, sym_base_edge
;
1031 BOOL left_valid
, right_valid
;
1033 /* Find the left candidate. */
1034 d2d_cdt_edge_sym(&sym_base_edge
, &base_edge
);
1035 d2d_cdt_edge_next_origin(cdt
, &left_candidate
, &sym_base_edge
);
1036 if ((left_valid
= d2d_cdt_leftof(cdt
, d2d_cdt_edge_destination(cdt
, &left_candidate
), &sym_base_edge
)))
1038 d2d_cdt_edge_next_origin(cdt
, &tmp
, &left_candidate
);
1039 while (d2d_cdt_edge_destination(cdt
, &tmp
) != d2d_cdt_edge_destination(cdt
, &sym_base_edge
)
1040 && d2d_cdt_incircle(cdt
,
1041 d2d_cdt_edge_origin(cdt
, &sym_base_edge
), d2d_cdt_edge_destination(cdt
, &sym_base_edge
),
1042 d2d_cdt_edge_destination(cdt
, &left_candidate
), d2d_cdt_edge_destination(cdt
, &tmp
)))
1044 d2d_cdt_destroy_edge(cdt
, &left_candidate
);
1045 left_candidate
= tmp
;
1046 d2d_cdt_edge_next_origin(cdt
, &tmp
, &left_candidate
);
1049 d2d_cdt_edge_sym(&left_candidate
, &left_candidate
);
1051 /* Find the right candidate. */
1052 d2d_cdt_edge_prev_origin(cdt
, &right_candidate
, &base_edge
);
1053 if ((right_valid
= d2d_cdt_rightof(cdt
, d2d_cdt_edge_destination(cdt
, &right_candidate
), &base_edge
)))
1055 d2d_cdt_edge_prev_origin(cdt
, &tmp
, &right_candidate
);
1056 while (d2d_cdt_edge_destination(cdt
, &tmp
) != d2d_cdt_edge_destination(cdt
, &base_edge
)
1057 && d2d_cdt_incircle(cdt
,
1058 d2d_cdt_edge_origin(cdt
, &sym_base_edge
), d2d_cdt_edge_destination(cdt
, &sym_base_edge
),
1059 d2d_cdt_edge_destination(cdt
, &right_candidate
), d2d_cdt_edge_destination(cdt
, &tmp
)))
1061 d2d_cdt_destroy_edge(cdt
, &right_candidate
);
1062 right_candidate
= tmp
;
1063 d2d_cdt_edge_prev_origin(cdt
, &tmp
, &right_candidate
);
1067 if (!left_valid
&& !right_valid
)
1070 /* Connect the appropriate candidate with the base edge. */
1071 if (!left_valid
|| (right_valid
&& d2d_cdt_incircle(cdt
,
1072 d2d_cdt_edge_origin(cdt
, &left_candidate
), d2d_cdt_edge_destination(cdt
, &left_candidate
),
1073 d2d_cdt_edge_origin(cdt
, &right_candidate
), d2d_cdt_edge_destination(cdt
, &right_candidate
))))
1075 if (!d2d_cdt_connect(cdt
, &base_edge
, &right_candidate
, &sym_base_edge
))
1080 if (!d2d_cdt_connect(cdt
, &base_edge
, &sym_base_edge
, &left_candidate
))
1088 /* Create a Delaunay triangulation from a set of vertices. This is an
1089 * implementation of the divide-and-conquer algorithm described by Guibas and
1090 * Stolfi. Should be called with at least two vertices. */
1091 static BOOL
d2d_cdt_triangulate(struct d2d_cdt
*cdt
, size_t start_vertex
, size_t vertex_count
,
1092 struct d2d_cdt_edge_ref
*left_edge
, struct d2d_cdt_edge_ref
*right_edge
)
1094 struct d2d_cdt_edge_ref left_inner
, left_outer
, right_inner
, right_outer
, tmp
;
1097 /* Only two vertices, create a single edge. */
1098 if (vertex_count
== 2)
1100 struct d2d_cdt_edge_ref a
;
1102 if (!d2d_cdt_create_edge(cdt
, &a
))
1104 d2d_cdt_edge_set_origin(cdt
, &a
, start_vertex
);
1105 d2d_cdt_edge_set_destination(cdt
, &a
, start_vertex
+ 1);
1108 d2d_cdt_edge_sym(right_edge
, &a
);
1113 /* Three vertices, create a triangle. */
1114 if (vertex_count
== 3)
1116 struct d2d_cdt_edge_ref a
, b
, c
;
1119 if (!d2d_cdt_create_edge(cdt
, &a
))
1121 if (!d2d_cdt_create_edge(cdt
, &b
))
1123 d2d_cdt_edge_sym(&tmp
, &a
);
1124 d2d_cdt_splice(cdt
, &tmp
, &b
);
1126 d2d_cdt_edge_set_origin(cdt
, &a
, start_vertex
);
1127 d2d_cdt_edge_set_destination(cdt
, &a
, start_vertex
+ 1);
1128 d2d_cdt_edge_set_origin(cdt
, &b
, start_vertex
+ 1);
1129 d2d_cdt_edge_set_destination(cdt
, &b
, start_vertex
+ 2);
1131 det
= d2d_cdt_ccw(cdt
, start_vertex
, start_vertex
+ 1, start_vertex
+ 2);
1132 if (det
!= 0.0f
&& !d2d_cdt_connect(cdt
, &c
, &b
, &a
))
1137 d2d_cdt_edge_sym(left_edge
, &c
);
1143 d2d_cdt_edge_sym(right_edge
, &b
);
1149 /* More than tree vertices, divide. */
1150 cut
= vertex_count
/ 2;
1151 if (!d2d_cdt_triangulate(cdt
, start_vertex
, cut
, &left_outer
, &left_inner
))
1153 if (!d2d_cdt_triangulate(cdt
, start_vertex
+ cut
, vertex_count
- cut
, &right_inner
, &right_outer
))
1155 /* Merge the left and right parts. */
1156 if (!d2d_cdt_merge(cdt
, &left_outer
, &left_inner
, &right_inner
, &right_outer
))
1159 *left_edge
= left_outer
;
1160 *right_edge
= right_outer
;
1164 static int d2d_cdt_compare_vertices(const void *a
, const void *b
)
1166 const D2D1_POINT_2F
*p0
= a
;
1167 const D2D1_POINT_2F
*p1
= b
;
1168 float diff
= p0
->x
- p1
->x
;
1171 diff
= p0
->y
- p1
->y
;
1173 return diff
== 0.0f
? 0 : (diff
> 0.0f
? 1 : -1);
1176 /* Determine whether a given point is inside the geometry, using the current
1177 * fill mode rule. */
1178 static BOOL
d2d_path_geometry_point_inside(const struct d2d_geometry
*geometry
,
1179 const D2D1_POINT_2F
*probe
, BOOL triangles_only
)
1181 const D2D1_POINT_2F
*p0
, *p1
;
1182 D2D1_POINT_2F v_p
, v_probe
;
1186 for (i
= 0, score
= 0; i
< geometry
->u
.path
.figure_count
; ++i
)
1188 const struct d2d_figure
*figure
= &geometry
->u
.path
.figures
[i
];
1190 if (probe
->x
< figure
->bounds
.left
|| probe
->x
> figure
->bounds
.right
1191 || probe
->y
< figure
->bounds
.top
|| probe
->y
> figure
->bounds
.bottom
)
1194 p0
= &figure
->vertices
[figure
->vertex_count
- 1];
1195 for (j
= 0; j
< figure
->vertex_count
; ++j
)
1197 if (!triangles_only
&& figure
->vertex_types
[j
] == D2D_VERTEX_TYPE_NONE
)
1200 p1
= &figure
->vertices
[j
];
1201 d2d_point_subtract(&v_p
, p1
, p0
);
1202 d2d_point_subtract(&v_probe
, probe
, p0
);
1204 if ((probe
->y
< p0
->y
) != (probe
->y
< p1
->y
) && v_probe
.x
< v_p
.x
* (v_probe
.y
/ v_p
.y
))
1206 if (geometry
->u
.path
.fill_mode
== D2D1_FILL_MODE_ALTERNATE
|| (probe
->y
< p0
->y
))
1216 return geometry
->u
.path
.fill_mode
== D2D1_FILL_MODE_ALTERNATE
? score
& 1 : score
;
1219 static BOOL
d2d_path_geometry_add_fill_face(struct d2d_geometry
*geometry
, const struct d2d_cdt
*cdt
,
1220 const struct d2d_cdt_edge_ref
*base_edge
)
1222 struct d2d_cdt_edge_ref tmp
;
1223 struct d2d_face
*face
;
1224 D2D1_POINT_2F probe
;
1226 if (cdt
->edges
[base_edge
->idx
].flags
& D2D_CDT_EDGE_FLAG_VISITED(base_edge
->r
))
1229 if (!d2d_array_reserve((void **)&geometry
->fill
.faces
, &geometry
->fill
.faces_size
,
1230 geometry
->fill
.face_count
+ 1, sizeof(*geometry
->fill
.faces
)))
1232 ERR("Failed to grow faces array.\n");
1236 face
= &geometry
->fill
.faces
[geometry
->fill
.face_count
];
1238 /* It may seem tempting to use the center of the face as probe origin, but
1239 * multiplying by powers of two works much better for preserving accuracy. */
1242 cdt
->edges
[tmp
.idx
].flags
|= D2D_CDT_EDGE_FLAG_VISITED(tmp
.r
);
1243 face
->v
[0] = d2d_cdt_edge_origin(cdt
, &tmp
);
1244 probe
.x
= cdt
->vertices
[d2d_cdt_edge_origin(cdt
, &tmp
)].x
* 0.25f
;
1245 probe
.y
= cdt
->vertices
[d2d_cdt_edge_origin(cdt
, &tmp
)].y
* 0.25f
;
1247 d2d_cdt_edge_next_left(cdt
, &tmp
, &tmp
);
1248 cdt
->edges
[tmp
.idx
].flags
|= D2D_CDT_EDGE_FLAG_VISITED(tmp
.r
);
1249 face
->v
[1] = d2d_cdt_edge_origin(cdt
, &tmp
);
1250 probe
.x
+= cdt
->vertices
[d2d_cdt_edge_origin(cdt
, &tmp
)].x
* 0.25f
;
1251 probe
.y
+= cdt
->vertices
[d2d_cdt_edge_origin(cdt
, &tmp
)].y
* 0.25f
;
1253 d2d_cdt_edge_next_left(cdt
, &tmp
, &tmp
);
1254 cdt
->edges
[tmp
.idx
].flags
|= D2D_CDT_EDGE_FLAG_VISITED(tmp
.r
);
1255 face
->v
[2] = d2d_cdt_edge_origin(cdt
, &tmp
);
1256 probe
.x
+= cdt
->vertices
[d2d_cdt_edge_origin(cdt
, &tmp
)].x
* 0.50f
;
1257 probe
.y
+= cdt
->vertices
[d2d_cdt_edge_origin(cdt
, &tmp
)].y
* 0.50f
;
1259 if (d2d_cdt_leftof(cdt
, face
->v
[2], base_edge
) && d2d_path_geometry_point_inside(geometry
, &probe
, TRUE
))
1260 ++geometry
->fill
.face_count
;
1265 static BOOL
d2d_cdt_generate_faces(const struct d2d_cdt
*cdt
, struct d2d_geometry
*geometry
)
1267 struct d2d_cdt_edge_ref base_edge
;
1270 for (i
= 0; i
< cdt
->edge_count
; ++i
)
1272 if (cdt
->edges
[i
].flags
& D2D_CDT_EDGE_FLAG_FREED
)
1277 if (!d2d_path_geometry_add_fill_face(geometry
, cdt
, &base_edge
))
1279 d2d_cdt_edge_sym(&base_edge
, &base_edge
);
1280 if (!d2d_path_geometry_add_fill_face(geometry
, cdt
, &base_edge
))
1287 HeapFree(GetProcessHeap(), 0, geometry
->fill
.faces
);
1288 geometry
->fill
.faces
= NULL
;
1289 geometry
->fill
.faces_size
= 0;
1290 geometry
->fill
.face_count
= 0;
1294 static BOOL
d2d_cdt_fixup(struct d2d_cdt
*cdt
, const struct d2d_cdt_edge_ref
*base_edge
)
1296 struct d2d_cdt_edge_ref candidate
, next
, new_base
;
1297 unsigned int count
= 0;
1299 d2d_cdt_edge_next_left(cdt
, &next
, base_edge
);
1300 if (next
.idx
== base_edge
->idx
)
1302 ERR("Degenerate face.\n");
1307 while (d2d_cdt_edge_destination(cdt
, &next
) != d2d_cdt_edge_origin(cdt
, base_edge
))
1309 if (d2d_cdt_incircle(cdt
, d2d_cdt_edge_origin(cdt
, base_edge
), d2d_cdt_edge_destination(cdt
, base_edge
),
1310 d2d_cdt_edge_destination(cdt
, &candidate
), d2d_cdt_edge_destination(cdt
, &next
)))
1312 d2d_cdt_edge_next_left(cdt
, &next
, &next
);
1318 d2d_cdt_edge_next_left(cdt
, &next
, &candidate
);
1319 if (d2d_cdt_edge_destination(cdt
, &next
) == d2d_cdt_edge_origin(cdt
, base_edge
))
1320 d2d_cdt_edge_next_left(cdt
, &next
, base_edge
);
1323 if (!d2d_cdt_connect(cdt
, &new_base
, &candidate
, &next
))
1325 if (!d2d_cdt_fixup(cdt
, &new_base
))
1327 d2d_cdt_edge_sym(&new_base
, &new_base
);
1328 if (!d2d_cdt_fixup(cdt
, &new_base
))
1335 static void d2d_cdt_cut_edges(struct d2d_cdt
*cdt
, struct d2d_cdt_edge_ref
*end_edge
,
1336 const struct d2d_cdt_edge_ref
*base_edge
, size_t start_vertex
, size_t end_vertex
)
1338 struct d2d_cdt_edge_ref next
;
1341 d2d_cdt_edge_next_left(cdt
, &next
, base_edge
);
1342 if (d2d_cdt_edge_destination(cdt
, &next
) == end_vertex
)
1348 ccw
= d2d_cdt_ccw(cdt
, d2d_cdt_edge_destination(cdt
, &next
), end_vertex
, start_vertex
);
1356 d2d_cdt_edge_next_left(cdt
, &next
, &next
);
1358 d2d_cdt_edge_sym(&next
, &next
);
1359 d2d_cdt_cut_edges(cdt
, end_edge
, &next
, start_vertex
, end_vertex
);
1360 d2d_cdt_destroy_edge(cdt
, &next
);
1363 static BOOL
d2d_cdt_insert_segment(struct d2d_cdt
*cdt
, struct d2d_geometry
*geometry
,
1364 const struct d2d_cdt_edge_ref
*origin
, struct d2d_cdt_edge_ref
*edge
, size_t end_vertex
)
1366 struct d2d_cdt_edge_ref base_edge
, current
, new_origin
, next
, target
;
1367 size_t current_destination
, current_origin
;
1369 for (current
= *origin
;; current
= next
)
1371 d2d_cdt_edge_next_origin(cdt
, &next
, ¤t
);
1373 current_destination
= d2d_cdt_edge_destination(cdt
, ¤t
);
1374 if (current_destination
== end_vertex
)
1376 d2d_cdt_edge_sym(edge
, ¤t
);
1380 current_origin
= d2d_cdt_edge_origin(cdt
, ¤t
);
1381 if (d2d_cdt_ccw(cdt
, end_vertex
, current_origin
, current_destination
) == 0.0f
1382 && (cdt
->vertices
[current_destination
].x
> cdt
->vertices
[current_origin
].x
)
1383 == (cdt
->vertices
[end_vertex
].x
> cdt
->vertices
[current_origin
].x
)
1384 && (cdt
->vertices
[current_destination
].y
> cdt
->vertices
[current_origin
].y
)
1385 == (cdt
->vertices
[end_vertex
].y
> cdt
->vertices
[current_origin
].y
))
1387 d2d_cdt_edge_sym(&new_origin
, ¤t
);
1388 return d2d_cdt_insert_segment(cdt
, geometry
, &new_origin
, edge
, end_vertex
);
1391 if (d2d_cdt_rightof(cdt
, end_vertex
, &next
) && d2d_cdt_leftof(cdt
, end_vertex
, ¤t
))
1393 d2d_cdt_edge_next_left(cdt
, &base_edge
, ¤t
);
1395 d2d_cdt_edge_sym(&base_edge
, &base_edge
);
1396 d2d_cdt_cut_edges(cdt
, &target
, &base_edge
, d2d_cdt_edge_origin(cdt
, origin
), end_vertex
);
1397 d2d_cdt_destroy_edge(cdt
, &base_edge
);
1399 if (!d2d_cdt_connect(cdt
, &base_edge
, &target
, ¤t
))
1402 if (!d2d_cdt_fixup(cdt
, &base_edge
))
1404 d2d_cdt_edge_sym(&base_edge
, &base_edge
);
1405 if (!d2d_cdt_fixup(cdt
, &base_edge
))
1408 if (d2d_cdt_edge_origin(cdt
, edge
) == end_vertex
)
1411 return d2d_cdt_insert_segment(cdt
, geometry
, &new_origin
, edge
, end_vertex
);
1414 if (next
.idx
== origin
->idx
)
1416 ERR("Triangle not found.\n");
1422 static BOOL
d2d_cdt_insert_segments(struct d2d_cdt
*cdt
, struct d2d_geometry
*geometry
)
1424 size_t start_vertex
, end_vertex
, i
, j
, k
;
1425 struct d2d_cdt_edge_ref edge
, new_edge
;
1426 const struct d2d_figure
*figure
;
1427 const D2D1_POINT_2F
*p
;
1430 for (i
= 0; i
< geometry
->u
.path
.figure_count
; ++i
)
1432 figure
= &geometry
->u
.path
.figures
[i
];
1434 p
= bsearch(&figure
->vertices
[figure
->vertex_count
- 1], cdt
->vertices
,
1435 geometry
->fill
.vertex_count
, sizeof(*p
), d2d_cdt_compare_vertices
);
1436 start_vertex
= p
- cdt
->vertices
;
1438 for (k
= 0, found
= FALSE
; k
< cdt
->edge_count
; ++k
)
1440 if (cdt
->edges
[k
].flags
& D2D_CDT_EDGE_FLAG_FREED
)
1446 if (d2d_cdt_edge_origin(cdt
, &edge
) == start_vertex
)
1451 d2d_cdt_edge_sym(&edge
, &edge
);
1452 if (d2d_cdt_edge_origin(cdt
, &edge
) == start_vertex
)
1461 ERR("Edge not found.\n");
1465 for (j
= 0; j
< figure
->vertex_count
; start_vertex
= end_vertex
, ++j
)
1467 p
= bsearch(&figure
->vertices
[j
], cdt
->vertices
,
1468 geometry
->fill
.vertex_count
, sizeof(*p
), d2d_cdt_compare_vertices
);
1469 end_vertex
= p
- cdt
->vertices
;
1471 if (start_vertex
== end_vertex
)
1474 if (!d2d_cdt_insert_segment(cdt
, geometry
, &edge
, &new_edge
, end_vertex
))
1483 static BOOL
d2d_geometry_intersections_add(struct d2d_geometry_intersections
*i
,
1484 size_t figure_idx
, size_t segment_idx
, float t
, D2D1_POINT_2F p
)
1486 struct d2d_geometry_intersection
*intersection
;
1488 if (!d2d_array_reserve((void **)&i
->intersections
, &i
->intersections_size
,
1489 i
->intersection_count
+ 1, sizeof(*i
->intersections
)))
1491 ERR("Failed to grow intersections array.\n");
1495 intersection
= &i
->intersections
[i
->intersection_count
++];
1496 intersection
->figure_idx
= figure_idx
;
1497 intersection
->segment_idx
= segment_idx
;
1498 intersection
->t
= t
;
1499 intersection
->p
= p
;
1504 static int d2d_geometry_intersections_compare(const void *a
, const void *b
)
1506 const struct d2d_geometry_intersection
*i0
= a
;
1507 const struct d2d_geometry_intersection
*i1
= b
;
1509 if (i0
->figure_idx
!= i1
->figure_idx
)
1510 return i0
->figure_idx
- i1
->figure_idx
;
1511 if (i0
->segment_idx
!= i1
->segment_idx
)
1512 return i0
->segment_idx
- i1
->segment_idx
;
1514 return i0
->t
> i1
->t
? 1 : -1;
1518 /* Intersect the geometry's segments with themselves. This uses the
1519 * straightforward approach of testing everything against everything, but
1520 * there certainly exist more scalable algorithms for this. */
1521 /* FIXME: Beziers can't currently self-intersect. */
1522 static BOOL
d2d_geometry_intersect_self(struct d2d_geometry
*geometry
)
1524 D2D1_POINT_2F p0
, p1
, q0
, q1
, v_p
, v_q
, v_qp
, intersection
;
1525 struct d2d_geometry_intersections intersections
= {0};
1526 struct d2d_figure
*figure_p
, *figure_q
;
1527 size_t i
, j
, k
, l
, max_l
;
1531 for (i
= 0; i
< geometry
->u
.path
.figure_count
; ++i
)
1533 figure_p
= &geometry
->u
.path
.figures
[i
];
1534 p0
= figure_p
->vertices
[figure_p
->vertex_count
- 1];
1535 for (k
= 0; k
< figure_p
->vertex_count
; p0
= p1
, ++k
)
1537 p1
= figure_p
->vertices
[k
];
1538 d2d_point_subtract(&v_p
, &p1
, &p0
);
1539 for (j
= 0; j
< i
|| (j
== i
&& k
); ++j
)
1541 figure_q
= &geometry
->u
.path
.figures
[j
];
1543 if (figure_p
->bounds
.left
> figure_q
->bounds
.right
1544 || figure_q
->bounds
.left
> figure_p
->bounds
.right
1545 || figure_p
->bounds
.top
> figure_q
->bounds
.bottom
1546 || figure_q
->bounds
.top
> figure_p
->bounds
.bottom
)
1549 max_l
= j
== i
? k
- 1 : figure_q
->vertex_count
;
1550 q0
= figure_q
->vertices
[figure_q
->vertex_count
- 1];
1551 for (l
= 0; l
< max_l
; q0
= q1
, ++l
)
1553 q1
= figure_q
->vertices
[l
];
1554 d2d_point_subtract(&v_q
, &q1
, &q0
);
1555 d2d_point_subtract(&v_qp
, &p0
, &q0
);
1557 det
= v_p
.x
* v_q
.y
- v_p
.y
* v_q
.x
;
1561 s
= (v_q
.x
* v_qp
.y
- v_q
.y
* v_qp
.x
) / det
;
1562 t
= (v_p
.x
* v_qp
.y
- v_p
.y
* v_qp
.x
) / det
;
1564 if (s
< 0.0f
|| s
> 1.0f
|| t
< 0.0f
|| t
> 1.0f
)
1567 intersection
.x
= p0
.x
+ v_p
.x
* s
;
1568 intersection
.y
= p0
.y
+ v_p
.y
* s
;
1570 if (t
> 0.0f
&& t
< 1.0f
1571 && !d2d_geometry_intersections_add(&intersections
, j
, l
, t
, intersection
))
1574 if (s
> 0.0f
&& s
< 1.0f
1575 && !d2d_geometry_intersections_add(&intersections
, i
, k
, s
, intersection
))
1582 qsort(intersections
.intersections
, intersections
.intersection_count
,
1583 sizeof(*intersections
.intersections
), d2d_geometry_intersections_compare
);
1584 for (i
= 0; i
< intersections
.intersection_count
; ++i
)
1586 const struct d2d_geometry_intersection
*inter
= &intersections
.intersections
[i
];
1588 if (!i
|| inter
->figure_idx
!= intersections
.intersections
[i
- 1].figure_idx
)
1591 if (!d2d_figure_insert_vertex(&geometry
->u
.path
.figures
[inter
->figure_idx
],
1592 inter
->segment_idx
+ j
, inter
->p
))
1600 HeapFree(GetProcessHeap(), 0, intersections
.intersections
);
1604 static HRESULT
d2d_path_geometry_triangulate(struct d2d_geometry
*geometry
)
1606 struct d2d_cdt_edge_ref left_edge
, right_edge
;
1607 size_t vertex_count
, i
, j
;
1608 struct d2d_cdt cdt
= {0};
1609 D2D1_POINT_2F
*vertices
;
1611 for (i
= 0, vertex_count
= 0; i
< geometry
->u
.path
.figure_count
; ++i
)
1613 vertex_count
+= geometry
->u
.path
.figures
[i
].vertex_count
;
1616 if (vertex_count
< 3)
1618 WARN("Geometry has %lu vertices.\n", (long)vertex_count
);
1622 if (!(vertices
= HeapAlloc(GetProcessHeap(), 0, vertex_count
* sizeof(*vertices
))))
1623 return E_OUTOFMEMORY
;
1625 for (i
= 0, j
= 0; i
< geometry
->u
.path
.figure_count
; ++i
)
1627 memcpy(&vertices
[j
], geometry
->u
.path
.figures
[i
].vertices
,
1628 geometry
->u
.path
.figures
[i
].vertex_count
* sizeof(*vertices
));
1629 j
+= geometry
->u
.path
.figures
[i
].vertex_count
;
1632 /* Sort vertices, eliminate duplicates. */
1633 qsort(vertices
, vertex_count
, sizeof(*vertices
), d2d_cdt_compare_vertices
);
1634 for (i
= 1; i
< vertex_count
; ++i
)
1636 if (!memcmp(&vertices
[i
- 1], &vertices
[i
], sizeof(*vertices
)))
1639 memmove(&vertices
[i
], &vertices
[i
+ 1], (vertex_count
- i
) * sizeof(*vertices
));
1644 geometry
->fill
.vertices
= vertices
;
1645 geometry
->fill
.vertex_count
= vertex_count
;
1647 cdt
.free_edge
= ~0u;
1648 cdt
.vertices
= vertices
;
1649 if (!d2d_cdt_triangulate(&cdt
, 0, vertex_count
, &left_edge
, &right_edge
))
1651 if (!d2d_cdt_insert_segments(&cdt
, geometry
))
1653 if (!d2d_cdt_generate_faces(&cdt
, geometry
))
1656 HeapFree(GetProcessHeap(), 0, cdt
.edges
);
1660 geometry
->fill
.vertices
= NULL
;
1661 geometry
->fill
.vertex_count
= 0;
1662 HeapFree(GetProcessHeap(), 0, vertices
);
1663 HeapFree(GetProcessHeap(), 0, cdt
.edges
);
1667 static BOOL
d2d_path_geometry_add_figure(struct d2d_geometry
*geometry
)
1669 struct d2d_figure
*figure
;
1671 if (!d2d_array_reserve((void **)&geometry
->u
.path
.figures
, &geometry
->u
.path
.figures_size
,
1672 geometry
->u
.path
.figure_count
+ 1, sizeof(*geometry
->u
.path
.figures
)))
1674 ERR("Failed to grow figures array.\n");
1678 figure
= &geometry
->u
.path
.figures
[geometry
->u
.path
.figure_count
];
1679 memset(figure
, 0, sizeof(*figure
));
1680 figure
->bounds
.left
= FLT_MAX
;
1681 figure
->bounds
.top
= FLT_MAX
;
1682 figure
->bounds
.right
= -FLT_MAX
;
1683 figure
->bounds
.bottom
= -FLT_MAX
;
1685 ++geometry
->u
.path
.figure_count
;
1689 static void d2d_geometry_cleanup(struct d2d_geometry
*geometry
)
1691 HeapFree(GetProcessHeap(), 0, geometry
->fill
.bezier_vertices
);
1692 HeapFree(GetProcessHeap(), 0, geometry
->fill
.faces
);
1693 HeapFree(GetProcessHeap(), 0, geometry
->fill
.vertices
);
1694 ID2D1Factory_Release(geometry
->factory
);
1697 static void d2d_geometry_init(struct d2d_geometry
*geometry
, ID2D1Factory
*factory
,
1698 const D2D1_MATRIX_3X2_F
*transform
, const struct ID2D1GeometryVtbl
*vtbl
)
1700 geometry
->ID2D1Geometry_iface
.lpVtbl
= vtbl
;
1701 geometry
->refcount
= 1;
1702 ID2D1Factory_AddRef(geometry
->factory
= factory
);
1703 geometry
->transform
= *transform
;
1706 static inline struct d2d_geometry
*impl_from_ID2D1GeometrySink(ID2D1GeometrySink
*iface
)
1708 return CONTAINING_RECORD(iface
, struct d2d_geometry
, u
.path
.ID2D1GeometrySink_iface
);
1711 static HRESULT STDMETHODCALLTYPE
d2d_geometry_sink_QueryInterface(ID2D1GeometrySink
*iface
, REFIID iid
, void **out
)
1713 TRACE("iface %p, iid %s, out %p.\n", iface
, debugstr_guid(iid
), out
);
1715 if (IsEqualGUID(iid
, &IID_ID2D1GeometrySink
)
1716 || IsEqualGUID(iid
, &IID_ID2D1SimplifiedGeometrySink
)
1717 || IsEqualGUID(iid
, &IID_IUnknown
))
1719 ID2D1GeometrySink_AddRef(iface
);
1724 WARN("%s not implemented, returning E_NOINTERFACE.\n", debugstr_guid(iid
));
1727 return E_NOINTERFACE
;
1730 static ULONG STDMETHODCALLTYPE
d2d_geometry_sink_AddRef(ID2D1GeometrySink
*iface
)
1732 struct d2d_geometry
*geometry
= impl_from_ID2D1GeometrySink(iface
);
1734 TRACE("iface %p.\n", iface
);
1736 return ID2D1Geometry_AddRef(&geometry
->ID2D1Geometry_iface
);
1739 static ULONG STDMETHODCALLTYPE
d2d_geometry_sink_Release(ID2D1GeometrySink
*iface
)
1741 struct d2d_geometry
*geometry
= impl_from_ID2D1GeometrySink(iface
);
1743 TRACE("iface %p.\n", iface
);
1745 return ID2D1Geometry_Release(&geometry
->ID2D1Geometry_iface
);
1748 static void STDMETHODCALLTYPE
d2d_geometry_sink_SetFillMode(ID2D1GeometrySink
*iface
, D2D1_FILL_MODE mode
)
1750 struct d2d_geometry
*geometry
= impl_from_ID2D1GeometrySink(iface
);
1752 TRACE("iface %p, mode %#x.\n", iface
, mode
);
1754 geometry
->u
.path
.fill_mode
= mode
;
1757 static void STDMETHODCALLTYPE
d2d_geometry_sink_SetSegmentFlags(ID2D1GeometrySink
*iface
, D2D1_PATH_SEGMENT flags
)
1759 FIXME("iface %p, flags %#x stub!\n", iface
, flags
);
1762 static void STDMETHODCALLTYPE
d2d_geometry_sink_BeginFigure(ID2D1GeometrySink
*iface
,
1763 D2D1_POINT_2F start_point
, D2D1_FIGURE_BEGIN figure_begin
)
1765 struct d2d_geometry
*geometry
= impl_from_ID2D1GeometrySink(iface
);
1767 TRACE("iface %p, start_point {%.8e, %.8e}, figure_begin %#x.\n",
1768 iface
, start_point
.x
, start_point
.y
, figure_begin
);
1770 if (geometry
->u
.path
.state
!= D2D_GEOMETRY_STATE_OPEN
)
1772 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_ERROR
;
1776 if (figure_begin
!= D2D1_FIGURE_BEGIN_FILLED
)
1777 FIXME("Ignoring figure_begin %#x.\n", figure_begin
);
1779 if (!d2d_path_geometry_add_figure(geometry
))
1781 ERR("Failed to add figure.\n");
1782 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_ERROR
;
1786 if (!d2d_figure_add_vertex(&geometry
->u
.path
.figures
[geometry
->u
.path
.figure_count
- 1], start_point
))
1788 ERR("Failed to add vertex.\n");
1789 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_ERROR
;
1793 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_FIGURE
;
1794 ++geometry
->u
.path
.segment_count
;
1797 static void STDMETHODCALLTYPE
d2d_geometry_sink_AddLines(ID2D1GeometrySink
*iface
,
1798 const D2D1_POINT_2F
*points
, UINT32 count
)
1800 struct d2d_geometry
*geometry
= impl_from_ID2D1GeometrySink(iface
);
1801 struct d2d_figure
*figure
= &geometry
->u
.path
.figures
[geometry
->u
.path
.figure_count
- 1];
1804 TRACE("iface %p, points %p, count %u.\n", iface
, points
, count
);
1806 if (geometry
->u
.path
.state
!= D2D_GEOMETRY_STATE_FIGURE
)
1808 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_ERROR
;
1812 for (i
= 0; i
< count
; ++i
)
1814 figure
->vertex_types
[figure
->vertex_count
- 1] = D2D_VERTEX_TYPE_LINE
;
1815 if (!d2d_figure_add_vertex(figure
, points
[i
]))
1817 ERR("Failed to add vertex.\n");
1822 geometry
->u
.path
.segment_count
+= count
;
1825 static void STDMETHODCALLTYPE
d2d_geometry_sink_AddBeziers(ID2D1GeometrySink
*iface
,
1826 const D2D1_BEZIER_SEGMENT
*beziers
, UINT32 count
)
1828 struct d2d_geometry
*geometry
= impl_from_ID2D1GeometrySink(iface
);
1829 struct d2d_figure
*figure
= &geometry
->u
.path
.figures
[geometry
->u
.path
.figure_count
- 1];
1833 TRACE("iface %p, beziers %p, count %u.\n", iface
, beziers
, count
);
1835 if (geometry
->u
.path
.state
!= D2D_GEOMETRY_STATE_FIGURE
)
1837 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_ERROR
;
1841 for (i
= 0; i
< count
; ++i
)
1843 /* FIXME: This tries to approximate a cubic bezier with a quadratic one. */
1844 p
.x
= (beziers
[i
].point1
.x
+ beziers
[i
].point2
.x
) * 0.75f
;
1845 p
.y
= (beziers
[i
].point1
.y
+ beziers
[i
].point2
.y
) * 0.75f
;
1846 p
.x
-= (figure
->vertices
[figure
->vertex_count
- 1].x
+ beziers
[i
].point3
.x
) * 0.25f
;
1847 p
.y
-= (figure
->vertices
[figure
->vertex_count
- 1].y
+ beziers
[i
].point3
.y
) * 0.25f
;
1848 figure
->vertex_types
[figure
->vertex_count
- 1] = D2D_VERTEX_TYPE_BEZIER
;
1850 if (!d2d_figure_add_bezier_control(figure
, &p
))
1852 ERR("Failed to add bezier control.\n");
1853 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_ERROR
;
1857 if (!d2d_figure_add_vertex(figure
, beziers
[i
].point3
))
1859 ERR("Failed to add bezier vertex.\n");
1860 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_ERROR
;
1865 geometry
->u
.path
.segment_count
+= count
;
1868 static void STDMETHODCALLTYPE
d2d_geometry_sink_EndFigure(ID2D1GeometrySink
*iface
, D2D1_FIGURE_END figure_end
)
1870 struct d2d_geometry
*geometry
= impl_from_ID2D1GeometrySink(iface
);
1871 struct d2d_figure
*figure
;
1873 TRACE("iface %p, figure_end %#x.\n", iface
, figure_end
);
1875 if (geometry
->u
.path
.state
!= D2D_GEOMETRY_STATE_FIGURE
)
1877 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_ERROR
;
1881 figure
= &geometry
->u
.path
.figures
[geometry
->u
.path
.figure_count
- 1];
1882 figure
->vertex_types
[figure
->vertex_count
- 1] = D2D_VERTEX_TYPE_LINE
;
1883 if (figure_end
!= D2D1_FIGURE_END_CLOSED
)
1884 FIXME("Ignoring figure_end %#x.\n", figure_end
);
1886 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_OPEN
;
1889 static void d2d_path_geometry_free_figures(struct d2d_geometry
*geometry
)
1893 if (!geometry
->u
.path
.figures
)
1896 for (i
= 0; i
< geometry
->u
.path
.figure_count
; ++i
)
1898 HeapFree(GetProcessHeap(), 0, geometry
->u
.path
.figures
[i
].bezier_controls
);
1899 HeapFree(GetProcessHeap(), 0, geometry
->u
.path
.figures
[i
].vertices
);
1901 HeapFree(GetProcessHeap(), 0, geometry
->u
.path
.figures
);
1902 geometry
->u
.path
.figures
= NULL
;
1903 geometry
->u
.path
.figures_size
= 0;
1906 static HRESULT
d2d_geometry_resolve_beziers(struct d2d_geometry
*geometry
)
1908 size_t bezier_idx
, control_idx
, i
, j
;
1910 for (i
= 0; i
< geometry
->u
.path
.figure_count
; ++i
)
1912 geometry
->fill
.bezier_vertex_count
+= 3 * geometry
->u
.path
.figures
[i
].bezier_control_count
;
1915 if (!(geometry
->fill
.bezier_vertices
= HeapAlloc(GetProcessHeap(), 0,
1916 geometry
->fill
.bezier_vertex_count
* sizeof(*geometry
->fill
.bezier_vertices
))))
1918 ERR("Failed to allocate bezier vertices array.\n");
1919 geometry
->fill
.bezier_vertex_count
= 0;
1920 return E_OUTOFMEMORY
;
1923 for (i
= 0, bezier_idx
= 0; i
< geometry
->u
.path
.figure_count
; ++i
)
1925 struct d2d_figure
*figure
= &geometry
->u
.path
.figures
[i
];
1926 if (figure
->bezier_control_count
)
1928 for (j
= 0, control_idx
= 0; j
< figure
->vertex_count
; ++j
)
1930 const D2D1_POINT_2F
*p0
, *p1
, *p2
;
1931 struct d2d_bezier_vertex
*b
;
1934 if (figure
->vertex_types
[j
] != D2D_VERTEX_TYPE_BEZIER
)
1937 b
= &geometry
->fill
.bezier_vertices
[bezier_idx
* 3];
1938 p0
= &figure
->vertices
[j
];
1939 p1
= &figure
->bezier_controls
[control_idx
++];
1941 if (d2d_path_geometry_point_inside(geometry
, p1
, FALSE
))
1944 d2d_figure_insert_vertex(figure
, j
+ 1, *p1
);
1945 /* Inserting a vertex potentially invalidates p0. */
1946 p0
= &figure
->vertices
[j
];
1950 if (j
== figure
->vertex_count
- 1)
1951 p2
= &figure
->vertices
[0];
1953 p2
= &figure
->vertices
[j
+ 1];
1955 d2d_bezier_vertex_set(&b
[0], p0
, 0.0f
, 0.0f
, sign
);
1956 d2d_bezier_vertex_set(&b
[1], p1
, 0.5f
, 0.0f
, sign
);
1957 d2d_bezier_vertex_set(&b
[2], p2
, 1.0f
, 1.0f
, sign
);
1966 static HRESULT STDMETHODCALLTYPE
d2d_geometry_sink_Close(ID2D1GeometrySink
*iface
)
1968 struct d2d_geometry
*geometry
= impl_from_ID2D1GeometrySink(iface
);
1969 HRESULT hr
= E_FAIL
;
1971 TRACE("iface %p.\n", iface
);
1973 if (geometry
->u
.path
.state
!= D2D_GEOMETRY_STATE_OPEN
)
1975 if (geometry
->u
.path
.state
!= D2D_GEOMETRY_STATE_CLOSED
)
1976 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_ERROR
;
1977 return D2DERR_WRONG_STATE
;
1979 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_CLOSED
;
1981 if (!d2d_geometry_intersect_self(geometry
))
1983 if (FAILED(hr
= d2d_geometry_resolve_beziers(geometry
)))
1985 if (FAILED(hr
= d2d_path_geometry_triangulate(geometry
)))
1991 HeapFree(GetProcessHeap(), 0, geometry
->fill
.bezier_vertices
);
1992 geometry
->fill
.bezier_vertex_count
= 0;
1993 d2d_path_geometry_free_figures(geometry
);
1994 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_ERROR
;
1999 static void STDMETHODCALLTYPE
d2d_geometry_sink_AddLine(ID2D1GeometrySink
*iface
, D2D1_POINT_2F point
)
2001 TRACE("iface %p, point {%.8e, %.8e}.\n", iface
, point
.x
, point
.y
);
2003 d2d_geometry_sink_AddLines(iface
, &point
, 1);
2006 static void STDMETHODCALLTYPE
d2d_geometry_sink_AddBezier(ID2D1GeometrySink
*iface
, const D2D1_BEZIER_SEGMENT
*bezier
)
2008 TRACE("iface %p, bezier %p.\n", iface
, bezier
);
2010 d2d_geometry_sink_AddBeziers(iface
, bezier
, 1);
2013 static void STDMETHODCALLTYPE
d2d_geometry_sink_AddQuadraticBezier(ID2D1GeometrySink
*iface
,
2014 const D2D1_QUADRATIC_BEZIER_SEGMENT
*bezier
)
2016 TRACE("iface %p, bezier %p.\n", iface
, bezier
);
2018 ID2D1GeometrySink_AddQuadraticBeziers(iface
, bezier
, 1);
2021 static void STDMETHODCALLTYPE
d2d_geometry_sink_AddQuadraticBeziers(ID2D1GeometrySink
*iface
,
2022 const D2D1_QUADRATIC_BEZIER_SEGMENT
*beziers
, UINT32 bezier_count
)
2024 struct d2d_geometry
*geometry
= impl_from_ID2D1GeometrySink(iface
);
2025 struct d2d_figure
*figure
= &geometry
->u
.path
.figures
[geometry
->u
.path
.figure_count
- 1];
2028 TRACE("iface %p, beziers %p, bezier_count %u.\n", iface
, beziers
, bezier_count
);
2030 if (geometry
->u
.path
.state
!= D2D_GEOMETRY_STATE_FIGURE
)
2032 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_ERROR
;
2036 for (i
= 0; i
< bezier_count
; ++i
)
2038 figure
->vertex_types
[figure
->vertex_count
- 1] = D2D_VERTEX_TYPE_BEZIER
;
2039 if (!d2d_figure_add_bezier_control(figure
, &beziers
[i
].point1
))
2041 ERR("Failed to add bezier.\n");
2042 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_ERROR
;
2046 if (!d2d_figure_add_vertex(figure
, beziers
[i
].point2
))
2048 ERR("Failed to add bezier vertex.\n");
2049 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_ERROR
;
2054 geometry
->u
.path
.segment_count
+= bezier_count
;
2057 static void STDMETHODCALLTYPE
d2d_geometry_sink_AddArc(ID2D1GeometrySink
*iface
, const D2D1_ARC_SEGMENT
*arc
)
2059 struct d2d_geometry
*geometry
= impl_from_ID2D1GeometrySink(iface
);
2061 FIXME("iface %p, arc %p stub!\n", iface
, arc
);
2063 if (geometry
->u
.path
.state
!= D2D_GEOMETRY_STATE_FIGURE
)
2065 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_ERROR
;
2069 if (!d2d_figure_add_vertex(&geometry
->u
.path
.figures
[geometry
->u
.path
.figure_count
- 1], arc
->point
))
2071 ERR("Failed to add vertex.\n");
2075 ++geometry
->u
.path
.segment_count
;
2078 static const struct ID2D1GeometrySinkVtbl d2d_geometry_sink_vtbl
=
2080 d2d_geometry_sink_QueryInterface
,
2081 d2d_geometry_sink_AddRef
,
2082 d2d_geometry_sink_Release
,
2083 d2d_geometry_sink_SetFillMode
,
2084 d2d_geometry_sink_SetSegmentFlags
,
2085 d2d_geometry_sink_BeginFigure
,
2086 d2d_geometry_sink_AddLines
,
2087 d2d_geometry_sink_AddBeziers
,
2088 d2d_geometry_sink_EndFigure
,
2089 d2d_geometry_sink_Close
,
2090 d2d_geometry_sink_AddLine
,
2091 d2d_geometry_sink_AddBezier
,
2092 d2d_geometry_sink_AddQuadraticBezier
,
2093 d2d_geometry_sink_AddQuadraticBeziers
,
2094 d2d_geometry_sink_AddArc
,
2097 static inline struct d2d_geometry
*impl_from_ID2D1PathGeometry(ID2D1PathGeometry
*iface
)
2099 return CONTAINING_RECORD(iface
, struct d2d_geometry
, ID2D1Geometry_iface
);
2102 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_QueryInterface(ID2D1PathGeometry
*iface
, REFIID iid
, void **out
)
2104 TRACE("iface %p, iid %s, out %p.\n", iface
, debugstr_guid(iid
), out
);
2106 if (IsEqualGUID(iid
, &IID_ID2D1PathGeometry
)
2107 || IsEqualGUID(iid
, &IID_ID2D1Geometry
)
2108 || IsEqualGUID(iid
, &IID_ID2D1Resource
)
2109 || IsEqualGUID(iid
, &IID_IUnknown
))
2111 ID2D1PathGeometry_AddRef(iface
);
2116 WARN("%s not implemented, returning E_NOINTERFACE.\n", debugstr_guid(iid
));
2119 return E_NOINTERFACE
;
2122 static ULONG STDMETHODCALLTYPE
d2d_path_geometry_AddRef(ID2D1PathGeometry
*iface
)
2124 struct d2d_geometry
*geometry
= impl_from_ID2D1PathGeometry(iface
);
2125 ULONG refcount
= InterlockedIncrement(&geometry
->refcount
);
2127 TRACE("%p increasing refcount to %u.\n", iface
, refcount
);
2132 static ULONG STDMETHODCALLTYPE
d2d_path_geometry_Release(ID2D1PathGeometry
*iface
)
2134 struct d2d_geometry
*geometry
= impl_from_ID2D1PathGeometry(iface
);
2135 ULONG refcount
= InterlockedDecrement(&geometry
->refcount
);
2137 TRACE("%p decreasing refcount to %u.\n", iface
, refcount
);
2141 d2d_path_geometry_free_figures(geometry
);
2142 d2d_geometry_cleanup(geometry
);
2143 HeapFree(GetProcessHeap(), 0, geometry
);
2149 static void STDMETHODCALLTYPE
d2d_path_geometry_GetFactory(ID2D1PathGeometry
*iface
, ID2D1Factory
**factory
)
2151 struct d2d_geometry
*geometry
= impl_from_ID2D1PathGeometry(iface
);
2153 TRACE("iface %p, factory %p.\n", iface
, factory
);
2155 ID2D1Factory_AddRef(*factory
= geometry
->factory
);
2158 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_GetBounds(ID2D1PathGeometry
*iface
,
2159 const D2D1_MATRIX_3X2_F
*transform
, D2D1_RECT_F
*bounds
)
2161 FIXME("iface %p, transform %p, bounds %p stub!\n", iface
, transform
, bounds
);
2166 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_GetWidenedBounds(ID2D1PathGeometry
*iface
, float stroke_width
,
2167 ID2D1StrokeStyle
*stroke_style
, const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, D2D1_RECT_F
*bounds
)
2169 FIXME("iface %p, stroke_width %.8e, stroke_style %p, transform %p, tolerance %.8e, bounds %p stub!\n",
2170 iface
, stroke_width
, stroke_style
, transform
, tolerance
, bounds
);
2175 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_StrokeContainsPoint(ID2D1PathGeometry
*iface
,
2176 D2D1_POINT_2F point
, float stroke_width
, ID2D1StrokeStyle
*stroke_style
, const D2D1_MATRIX_3X2_F
*transform
,
2177 float tolerance
, BOOL
*contains
)
2179 FIXME("iface %p, point {%.8e, %.8e}, stroke_width %.8e, stroke_style %p, "
2180 "transform %p, tolerance %.8e, contains %p stub!\n",
2181 iface
, point
.x
, point
.y
, stroke_width
, stroke_style
, transform
, tolerance
, contains
);
2186 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_FillContainsPoint(ID2D1PathGeometry
*iface
,
2187 D2D1_POINT_2F point
, const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, BOOL
*contains
)
2189 struct d2d_geometry
*geometry
= impl_from_ID2D1PathGeometry(iface
);
2190 D2D1_MATRIX_3X2_F g_i
;
2192 TRACE("iface %p, point {%.8e, %.8e}, transform %p, tolerance %.8e, contains %p.\n",
2193 iface
, point
.x
, point
.y
, transform
, tolerance
, contains
);
2197 if (!d2d_matrix_invert(&g_i
, transform
))
2198 return D2DERR_UNSUPPORTED_OPERATION
;
2199 d2d_point_transform(&point
, &g_i
, point
.x
, point
.y
);
2202 *contains
= !!d2d_path_geometry_point_inside(geometry
, &point
, FALSE
);
2204 TRACE("-> %#x.\n", *contains
);
2209 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_CompareWithGeometry(ID2D1PathGeometry
*iface
,
2210 ID2D1Geometry
*geometry
, const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, D2D1_GEOMETRY_RELATION
*relation
)
2212 FIXME("iface %p, geometry %p, transform %p, tolerance %.8e, relation %p stub!\n",
2213 iface
, geometry
, transform
, tolerance
, relation
);
2218 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_Simplify(ID2D1PathGeometry
*iface
,
2219 D2D1_GEOMETRY_SIMPLIFICATION_OPTION option
, const D2D1_MATRIX_3X2_F
*transform
, float tolerance
,
2220 ID2D1SimplifiedGeometrySink
*sink
)
2222 FIXME("iface %p, option %#x, transform %p, tolerance %.8e, sink %p stub!\n",
2223 iface
, option
, transform
, tolerance
, sink
);
2228 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_Tessellate(ID2D1PathGeometry
*iface
,
2229 const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, ID2D1TessellationSink
*sink
)
2231 FIXME("iface %p, transform %p, tolerance %.8e, sink %p stub!\n", iface
, transform
, tolerance
, sink
);
2236 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_CombineWithGeometry(ID2D1PathGeometry
*iface
,
2237 ID2D1Geometry
*geometry
, D2D1_COMBINE_MODE combine_mode
, const D2D1_MATRIX_3X2_F
*transform
,
2238 float tolerance
, ID2D1SimplifiedGeometrySink
*sink
)
2240 FIXME("iface %p, geometry %p, combine_mode %#x, transform %p, tolerance %.8e, sink %p stub!\n",
2241 iface
, geometry
, combine_mode
, transform
, tolerance
, sink
);
2246 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_Outline(ID2D1PathGeometry
*iface
,
2247 const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, ID2D1SimplifiedGeometrySink
*sink
)
2249 FIXME("iface %p, transform %p, tolerance %.8e, sink %p stub!\n", iface
, transform
, tolerance
, sink
);
2254 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_ComputeArea(ID2D1PathGeometry
*iface
,
2255 const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, float *area
)
2257 FIXME("iface %p, transform %p, tolerance %.8e, area %p stub!\n", iface
, transform
, tolerance
, area
);
2262 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_ComputeLength(ID2D1PathGeometry
*iface
,
2263 const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, float *length
)
2265 FIXME("iface %p, transform %p, tolerance %.8e, length %p stub!\n", iface
, transform
, tolerance
, length
);
2270 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_ComputePointAtLength(ID2D1PathGeometry
*iface
, float length
,
2271 const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, D2D1_POINT_2F
*point
, D2D1_POINT_2F
*tangent
)
2273 FIXME("iface %p, length %.8e, transform %p, tolerance %.8e, point %p, tangent %p stub!\n",
2274 iface
, length
, transform
, tolerance
, point
, tangent
);
2279 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_Widen(ID2D1PathGeometry
*iface
, float stroke_width
,
2280 ID2D1StrokeStyle
*stroke_style
, const D2D1_MATRIX_3X2_F
*transform
, float tolerance
,
2281 ID2D1SimplifiedGeometrySink
*sink
)
2283 FIXME("iface %p, stroke_width %.8e, stroke_style %p, transform %p, tolerance %.8e, sink %p stub!\n",
2284 iface
, stroke_width
, stroke_style
, transform
, tolerance
, sink
);
2289 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_Open(ID2D1PathGeometry
*iface
, ID2D1GeometrySink
**sink
)
2291 struct d2d_geometry
*geometry
= impl_from_ID2D1PathGeometry(iface
);
2293 TRACE("iface %p, sink %p.\n", iface
, sink
);
2295 if (geometry
->u
.path
.state
!= D2D_GEOMETRY_STATE_INITIAL
)
2296 return D2DERR_WRONG_STATE
;
2298 *sink
= &geometry
->u
.path
.ID2D1GeometrySink_iface
;
2299 ID2D1GeometrySink_AddRef(*sink
);
2301 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_OPEN
;
2306 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_Stream(ID2D1PathGeometry
*iface
, ID2D1GeometrySink
*sink
)
2308 FIXME("iface %p, sink %p stub!\n", iface
, sink
);
2313 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_GetSegmentCount(ID2D1PathGeometry
*iface
, UINT32
*count
)
2315 struct d2d_geometry
*geometry
= impl_from_ID2D1PathGeometry(iface
);
2317 TRACE("iface %p, count %p.\n", iface
, count
);
2319 if (geometry
->u
.path
.state
!= D2D_GEOMETRY_STATE_CLOSED
)
2320 return D2DERR_WRONG_STATE
;
2322 *count
= geometry
->u
.path
.segment_count
;
2327 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_GetFigureCount(ID2D1PathGeometry
*iface
, UINT32
*count
)
2329 struct d2d_geometry
*geometry
= impl_from_ID2D1PathGeometry(iface
);
2331 TRACE("iface %p, count %p.\n", iface
, count
);
2333 if (geometry
->u
.path
.state
!= D2D_GEOMETRY_STATE_CLOSED
)
2334 return D2DERR_WRONG_STATE
;
2336 *count
= geometry
->u
.path
.figure_count
;
2341 static const struct ID2D1PathGeometryVtbl d2d_path_geometry_vtbl
=
2343 d2d_path_geometry_QueryInterface
,
2344 d2d_path_geometry_AddRef
,
2345 d2d_path_geometry_Release
,
2346 d2d_path_geometry_GetFactory
,
2347 d2d_path_geometry_GetBounds
,
2348 d2d_path_geometry_GetWidenedBounds
,
2349 d2d_path_geometry_StrokeContainsPoint
,
2350 d2d_path_geometry_FillContainsPoint
,
2351 d2d_path_geometry_CompareWithGeometry
,
2352 d2d_path_geometry_Simplify
,
2353 d2d_path_geometry_Tessellate
,
2354 d2d_path_geometry_CombineWithGeometry
,
2355 d2d_path_geometry_Outline
,
2356 d2d_path_geometry_ComputeArea
,
2357 d2d_path_geometry_ComputeLength
,
2358 d2d_path_geometry_ComputePointAtLength
,
2359 d2d_path_geometry_Widen
,
2360 d2d_path_geometry_Open
,
2361 d2d_path_geometry_Stream
,
2362 d2d_path_geometry_GetSegmentCount
,
2363 d2d_path_geometry_GetFigureCount
,
2366 void d2d_path_geometry_init(struct d2d_geometry
*geometry
, ID2D1Factory
*factory
)
2368 d2d_geometry_init(geometry
, factory
, &identity
, (ID2D1GeometryVtbl
*)&d2d_path_geometry_vtbl
);
2369 geometry
->u
.path
.ID2D1GeometrySink_iface
.lpVtbl
= &d2d_geometry_sink_vtbl
;
2372 static inline struct d2d_geometry
*impl_from_ID2D1RectangleGeometry(ID2D1RectangleGeometry
*iface
)
2374 return CONTAINING_RECORD(iface
, struct d2d_geometry
, ID2D1Geometry_iface
);
2377 static HRESULT STDMETHODCALLTYPE
d2d_rectangle_geometry_QueryInterface(ID2D1RectangleGeometry
*iface
,
2378 REFIID iid
, void **out
)
2380 TRACE("iface %p, iid %s, out %p.\n", iface
, debugstr_guid(iid
), out
);
2382 if (IsEqualGUID(iid
, &IID_ID2D1RectangleGeometry
)
2383 || IsEqualGUID(iid
, &IID_ID2D1Geometry
)
2384 || IsEqualGUID(iid
, &IID_ID2D1Resource
)
2385 || IsEqualGUID(iid
, &IID_IUnknown
))
2387 ID2D1RectangleGeometry_AddRef(iface
);
2392 WARN("%s not implemented, returning E_NOINTERFACE.\n", debugstr_guid(iid
));
2395 return E_NOINTERFACE
;
2398 static ULONG STDMETHODCALLTYPE
d2d_rectangle_geometry_AddRef(ID2D1RectangleGeometry
*iface
)
2400 struct d2d_geometry
*geometry
= impl_from_ID2D1RectangleGeometry(iface
);
2401 ULONG refcount
= InterlockedIncrement(&geometry
->refcount
);
2403 TRACE("%p increasing refcount to %u.\n", iface
, refcount
);
2408 static ULONG STDMETHODCALLTYPE
d2d_rectangle_geometry_Release(ID2D1RectangleGeometry
*iface
)
2410 struct d2d_geometry
*geometry
= impl_from_ID2D1RectangleGeometry(iface
);
2411 ULONG refcount
= InterlockedDecrement(&geometry
->refcount
);
2413 TRACE("%p decreasing refcount to %u.\n", iface
, refcount
);
2417 d2d_geometry_cleanup(geometry
);
2418 HeapFree(GetProcessHeap(), 0, geometry
);
2424 static void STDMETHODCALLTYPE
d2d_rectangle_geometry_GetFactory(ID2D1RectangleGeometry
*iface
, ID2D1Factory
**factory
)
2426 struct d2d_geometry
*geometry
= impl_from_ID2D1RectangleGeometry(iface
);
2428 TRACE("iface %p, factory %p.\n", iface
, factory
);
2430 ID2D1Factory_AddRef(*factory
= geometry
->factory
);
2433 static HRESULT STDMETHODCALLTYPE
d2d_rectangle_geometry_GetBounds(ID2D1RectangleGeometry
*iface
,
2434 const D2D1_MATRIX_3X2_F
*transform
, D2D1_RECT_F
*bounds
)
2436 FIXME("iface %p, transform %p, bounds %p stub!\n", iface
, transform
, bounds
);
2441 static HRESULT STDMETHODCALLTYPE
d2d_rectangle_geometry_GetWidenedBounds(ID2D1RectangleGeometry
*iface
,
2442 float stroke_width
, ID2D1StrokeStyle
*stroke_style
, const D2D1_MATRIX_3X2_F
*transform
,
2443 float tolerance
, D2D1_RECT_F
*bounds
)
2445 FIXME("iface %p, stroke_width %.8e, stroke_style %p, transform %p, tolerance %.8e, bounds %p stub!\n",
2446 iface
, stroke_width
, stroke_style
, transform
, tolerance
, bounds
);
2451 static HRESULT STDMETHODCALLTYPE
d2d_rectangle_geometry_StrokeContainsPoint(ID2D1RectangleGeometry
*iface
,
2452 D2D1_POINT_2F point
, float stroke_width
, ID2D1StrokeStyle
*stroke_style
, const D2D1_MATRIX_3X2_F
*transform
,
2453 float tolerance
, BOOL
*contains
)
2455 FIXME("iface %p, point {%.8e, %.8e}, stroke_width %.8e, stroke_style %p, "
2456 "transform %p, tolerance %.8e, contains %p stub!\n",
2457 iface
, point
.x
, point
.y
, stroke_width
, stroke_style
, transform
, tolerance
, contains
);
2462 static HRESULT STDMETHODCALLTYPE
d2d_rectangle_geometry_FillContainsPoint(ID2D1RectangleGeometry
*iface
,
2463 D2D1_POINT_2F point
, const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, BOOL
*contains
)
2465 struct d2d_geometry
*geometry
= impl_from_ID2D1RectangleGeometry(iface
);
2466 D2D1_RECT_F
*rect
= &geometry
->u
.rectangle
.rect
;
2469 TRACE("iface %p, point {%.8e, %.8e}, transform %p, tolerance %.8e, contains %p.\n",
2470 iface
, point
.x
, point
.y
, transform
, tolerance
, contains
);
2474 D2D1_MATRIX_3X2_F g_i
;
2476 if (!d2d_matrix_invert(&g_i
, transform
))
2477 return D2DERR_UNSUPPORTED_OPERATION
;
2478 d2d_point_transform(&point
, &g_i
, point
.x
, point
.y
);
2481 if (tolerance
== 0.0f
)
2482 tolerance
= D2D1_DEFAULT_FLATTENING_TOLERANCE
;
2484 dx
= max(fabsf((rect
->right
+ rect
->left
) / 2.0f
- point
.x
) - (rect
->right
- rect
->left
) / 2.0f
, 0.0f
);
2485 dy
= max(fabsf((rect
->bottom
+ rect
->top
) / 2.0f
- point
.y
) - (rect
->bottom
- rect
->top
) / 2.0f
, 0.0f
);
2487 *contains
= tolerance
* tolerance
> (dx
* dx
+ dy
* dy
);
2491 static HRESULT STDMETHODCALLTYPE
d2d_rectangle_geometry_CompareWithGeometry(ID2D1RectangleGeometry
*iface
,
2492 ID2D1Geometry
*geometry
, const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, D2D1_GEOMETRY_RELATION
*relation
)
2494 FIXME("iface %p, geometry %p, transform %p, tolerance %.8e, relation %p stub!\n",
2495 iface
, geometry
, transform
, tolerance
, relation
);
2500 static HRESULT STDMETHODCALLTYPE
d2d_rectangle_geometry_Simplify(ID2D1RectangleGeometry
*iface
,
2501 D2D1_GEOMETRY_SIMPLIFICATION_OPTION option
, const D2D1_MATRIX_3X2_F
*transform
, float tolerance
,
2502 ID2D1SimplifiedGeometrySink
*sink
)
2504 FIXME("iface %p, option %#x, transform %p, tolerance %.8e, sink %p stub!\n",
2505 iface
, option
, transform
, tolerance
, sink
);
2510 static HRESULT STDMETHODCALLTYPE
d2d_rectangle_geometry_Tessellate(ID2D1RectangleGeometry
*iface
,
2511 const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, ID2D1TessellationSink
*sink
)
2513 FIXME("iface %p, transform %p, tolerance %.8e, sink %p stub!\n", iface
, transform
, tolerance
, sink
);
2518 static HRESULT STDMETHODCALLTYPE
d2d_rectangle_geometry_CombineWithGeometry(ID2D1RectangleGeometry
*iface
,
2519 ID2D1Geometry
*geometry
, D2D1_COMBINE_MODE combine_mode
, const D2D1_MATRIX_3X2_F
*transform
,
2520 float tolerance
, ID2D1SimplifiedGeometrySink
*sink
)
2522 FIXME("iface %p, geometry %p, combine_mode %#x, transform %p, tolerance %.8e, sink %p stub!\n",
2523 iface
, geometry
, combine_mode
, transform
, tolerance
, sink
);
2528 static HRESULT STDMETHODCALLTYPE
d2d_rectangle_geometry_Outline(ID2D1RectangleGeometry
*iface
,
2529 const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, ID2D1SimplifiedGeometrySink
*sink
)
2531 FIXME("iface %p, transform %p, tolerance %.8e, sink %p stub!\n", iface
, transform
, tolerance
, sink
);
2536 static HRESULT STDMETHODCALLTYPE
d2d_rectangle_geometry_ComputeArea(ID2D1RectangleGeometry
*iface
,
2537 const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, float *area
)
2539 FIXME("iface %p, transform %p, tolerance %.8e, area %p stub!\n", iface
, transform
, tolerance
, area
);
2544 static HRESULT STDMETHODCALLTYPE
d2d_rectangle_geometry_ComputeLength(ID2D1RectangleGeometry
*iface
,
2545 const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, float *length
)
2547 FIXME("iface %p, transform %p, tolerance %.8e, length %p stub!\n", iface
, transform
, tolerance
, length
);
2552 static HRESULT STDMETHODCALLTYPE
d2d_rectangle_geometry_ComputePointAtLength(ID2D1RectangleGeometry
*iface
,
2553 float length
, const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, D2D1_POINT_2F
*point
,
2554 D2D1_POINT_2F
*tangent
)
2556 FIXME("iface %p, length %.8e, transform %p, tolerance %.8e, point %p, tangent %p stub!\n",
2557 iface
, length
, transform
, tolerance
, point
, tangent
);
2562 static HRESULT STDMETHODCALLTYPE
d2d_rectangle_geometry_Widen(ID2D1RectangleGeometry
*iface
, float stroke_width
,
2563 ID2D1StrokeStyle
*stroke_style
, const D2D1_MATRIX_3X2_F
*transform
, float tolerance
,
2564 ID2D1SimplifiedGeometrySink
*sink
)
2566 FIXME("iface %p, stroke_width %.8e, stroke_style %p, transform %p, tolerance %.8e, sink %p stub!\n",
2567 iface
, stroke_width
, stroke_style
, transform
, tolerance
, sink
);
2572 static void STDMETHODCALLTYPE
d2d_rectangle_geometry_GetRect(ID2D1RectangleGeometry
*iface
, D2D1_RECT_F
*rect
)
2574 struct d2d_geometry
*geometry
= impl_from_ID2D1RectangleGeometry(iface
);
2576 TRACE("iface %p, rect %p.\n", iface
, rect
);
2578 *rect
= geometry
->u
.rectangle
.rect
;
2581 static const struct ID2D1RectangleGeometryVtbl d2d_rectangle_geometry_vtbl
=
2583 d2d_rectangle_geometry_QueryInterface
,
2584 d2d_rectangle_geometry_AddRef
,
2585 d2d_rectangle_geometry_Release
,
2586 d2d_rectangle_geometry_GetFactory
,
2587 d2d_rectangle_geometry_GetBounds
,
2588 d2d_rectangle_geometry_GetWidenedBounds
,
2589 d2d_rectangle_geometry_StrokeContainsPoint
,
2590 d2d_rectangle_geometry_FillContainsPoint
,
2591 d2d_rectangle_geometry_CompareWithGeometry
,
2592 d2d_rectangle_geometry_Simplify
,
2593 d2d_rectangle_geometry_Tessellate
,
2594 d2d_rectangle_geometry_CombineWithGeometry
,
2595 d2d_rectangle_geometry_Outline
,
2596 d2d_rectangle_geometry_ComputeArea
,
2597 d2d_rectangle_geometry_ComputeLength
,
2598 d2d_rectangle_geometry_ComputePointAtLength
,
2599 d2d_rectangle_geometry_Widen
,
2600 d2d_rectangle_geometry_GetRect
,
2603 HRESULT
d2d_rectangle_geometry_init(struct d2d_geometry
*geometry
, ID2D1Factory
*factory
, const D2D1_RECT_F
*rect
)
2608 d2d_geometry_init(geometry
, factory
, &identity
, (ID2D1GeometryVtbl
*)&d2d_rectangle_geometry_vtbl
);
2609 geometry
->u
.rectangle
.rect
= *rect
;
2611 if (!(geometry
->fill
.vertices
= HeapAlloc(GetProcessHeap(), 0, 4 * sizeof(*geometry
->fill
.vertices
))))
2613 d2d_geometry_cleanup(geometry
);
2614 return E_OUTOFMEMORY
;
2616 geometry
->fill
.vertex_count
= 4;
2617 if (!d2d_array_reserve((void **)&geometry
->fill
.faces
,
2618 &geometry
->fill
.faces_size
, 2, sizeof(*geometry
->fill
.faces
)))
2620 d2d_geometry_cleanup(geometry
);
2621 return E_OUTOFMEMORY
;
2623 geometry
->fill
.face_count
= 2;
2625 l
= min(rect
->left
, rect
->right
);
2626 r
= max(rect
->left
, rect
->right
);
2627 t
= min(rect
->top
, rect
->bottom
);
2628 b
= max(rect
->top
, rect
->bottom
);
2630 fv
= geometry
->fill
.vertices
;
2631 d2d_point_set(&fv
[0], l
, t
);
2632 d2d_point_set(&fv
[1], l
, b
);
2633 d2d_point_set(&fv
[2], r
, t
);
2634 d2d_point_set(&fv
[3], r
, b
);
2636 geometry
->fill
.faces
[0].v
[0] = 0;
2637 geometry
->fill
.faces
[0].v
[1] = 2;
2638 geometry
->fill
.faces
[0].v
[2] = 1;
2639 geometry
->fill
.faces
[1].v
[0] = 1;
2640 geometry
->fill
.faces
[1].v
[1] = 2;
2641 geometry
->fill
.faces
[1].v
[2] = 3;
2646 static inline struct d2d_geometry
*impl_from_ID2D1TransformedGeometry(ID2D1TransformedGeometry
*iface
)
2648 return CONTAINING_RECORD(iface
, struct d2d_geometry
, ID2D1Geometry_iface
);
2651 static HRESULT STDMETHODCALLTYPE
d2d_transformed_geometry_QueryInterface(ID2D1TransformedGeometry
*iface
,
2652 REFIID iid
, void **out
)
2654 TRACE("iface %p, iid %s, out %p.\n", iface
, debugstr_guid(iid
), out
);
2656 if (IsEqualGUID(iid
, &IID_ID2D1TransformedGeometry
)
2657 || IsEqualGUID(iid
, &IID_ID2D1Geometry
)
2658 || IsEqualGUID(iid
, &IID_ID2D1Resource
)
2659 || IsEqualGUID(iid
, &IID_IUnknown
))
2661 ID2D1TransformedGeometry_AddRef(iface
);
2666 WARN("%s not implemented, returning E_NOINTERFACE.\n", debugstr_guid(iid
));
2669 return E_NOINTERFACE
;
2672 static ULONG STDMETHODCALLTYPE
d2d_transformed_geometry_AddRef(ID2D1TransformedGeometry
*iface
)
2674 struct d2d_geometry
*geometry
= impl_from_ID2D1TransformedGeometry(iface
);
2675 ULONG refcount
= InterlockedIncrement(&geometry
->refcount
);
2677 TRACE("%p increasing refcount to %u.\n", iface
, refcount
);
2682 static ULONG STDMETHODCALLTYPE
d2d_transformed_geometry_Release(ID2D1TransformedGeometry
*iface
)
2684 struct d2d_geometry
*geometry
= impl_from_ID2D1TransformedGeometry(iface
);
2685 ULONG refcount
= InterlockedDecrement(&geometry
->refcount
);
2687 TRACE("%p decreasing refcount to %u.\n", iface
, refcount
);
2691 geometry
->fill
.bezier_vertices
= NULL
;
2692 geometry
->fill
.faces
= NULL
;
2693 geometry
->fill
.vertices
= NULL
;
2694 ID2D1Geometry_Release(geometry
->u
.transformed
.src_geometry
);
2695 d2d_geometry_cleanup(geometry
);
2696 HeapFree(GetProcessHeap(), 0, geometry
);
2702 static void STDMETHODCALLTYPE
d2d_transformed_geometry_GetFactory(ID2D1TransformedGeometry
*iface
,
2703 ID2D1Factory
**factory
)
2705 struct d2d_geometry
*geometry
= impl_from_ID2D1TransformedGeometry(iface
);
2707 TRACE("iface %p, factory %p.\n", iface
, factory
);
2709 ID2D1Factory_AddRef(*factory
= geometry
->factory
);
2712 static HRESULT STDMETHODCALLTYPE
d2d_transformed_geometry_GetBounds(ID2D1TransformedGeometry
*iface
,
2713 const D2D1_MATRIX_3X2_F
*transform
, D2D1_RECT_F
*bounds
)
2715 FIXME("iface %p, transform %p, bounds %p stub!\n", iface
, transform
, bounds
);
2720 static HRESULT STDMETHODCALLTYPE
d2d_transformed_geometry_GetWidenedBounds(ID2D1TransformedGeometry
*iface
,
2721 float stroke_width
, ID2D1StrokeStyle
*stroke_style
, const D2D1_MATRIX_3X2_F
*transform
,
2722 float tolerance
, D2D1_RECT_F
*bounds
)
2724 FIXME("iface %p, stroke_width %.8e, stroke_style %p, transform %p, tolerance %.8e, bounds %p stub!\n",
2725 iface
, stroke_width
, stroke_style
, transform
, tolerance
, bounds
);
2730 static HRESULT STDMETHODCALLTYPE
d2d_transformed_geometry_StrokeContainsPoint(ID2D1TransformedGeometry
*iface
,
2731 D2D1_POINT_2F point
, float stroke_width
, ID2D1StrokeStyle
*stroke_style
, const D2D1_MATRIX_3X2_F
*transform
,
2732 float tolerance
, BOOL
*contains
)
2734 struct d2d_geometry
*geometry
= impl_from_ID2D1TransformedGeometry(iface
);
2735 D2D1_MATRIX_3X2_F g
;
2737 TRACE("iface %p, point {%.8e, %.8e}, stroke_width %.8e, stroke_style %p, "
2738 "transform %p, tolerance %.8e, contains %p.\n",
2739 iface
, point
.x
, point
.y
, stroke_width
, stroke_style
, transform
, tolerance
, contains
);
2741 g
= geometry
->transform
;
2743 d2d_matrix_multiply(&g
, transform
);
2745 return ID2D1Geometry_StrokeContainsPoint(geometry
->u
.transformed
.src_geometry
, point
, stroke_width
, stroke_style
,
2746 &g
, tolerance
, contains
);
2749 static HRESULT STDMETHODCALLTYPE
d2d_transformed_geometry_FillContainsPoint(ID2D1TransformedGeometry
*iface
,
2750 D2D1_POINT_2F point
, const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, BOOL
*contains
)
2752 struct d2d_geometry
*geometry
= impl_from_ID2D1TransformedGeometry(iface
);
2753 D2D1_MATRIX_3X2_F g
;
2755 TRACE("iface %p, point {%.8e, %.8e}, transform %p, tolerance %.8e, contains %p.\n",
2756 iface
, point
.x
, point
.y
, transform
, tolerance
, contains
);
2758 g
= geometry
->transform
;
2760 d2d_matrix_multiply(&g
, transform
);
2762 return ID2D1Geometry_FillContainsPoint(geometry
->u
.transformed
.src_geometry
, point
, &g
, tolerance
, contains
);
2765 static HRESULT STDMETHODCALLTYPE
d2d_transformed_geometry_CompareWithGeometry(ID2D1TransformedGeometry
*iface
,
2766 ID2D1Geometry
*geometry
, const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, D2D1_GEOMETRY_RELATION
*relation
)
2768 FIXME("iface %p, geometry %p, transform %p, tolerance %.8e, relation %p stub!\n",
2769 iface
, geometry
, transform
, tolerance
, relation
);
2774 static HRESULT STDMETHODCALLTYPE
d2d_transformed_geometry_Simplify(ID2D1TransformedGeometry
*iface
,
2775 D2D1_GEOMETRY_SIMPLIFICATION_OPTION option
, const D2D1_MATRIX_3X2_F
*transform
, float tolerance
,
2776 ID2D1SimplifiedGeometrySink
*sink
)
2778 FIXME("iface %p, option %#x, transform %p, tolerance %.8e, sink %p stub!\n",
2779 iface
, option
, transform
, tolerance
, sink
);
2784 static HRESULT STDMETHODCALLTYPE
d2d_transformed_geometry_Tessellate(ID2D1TransformedGeometry
*iface
,
2785 const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, ID2D1TessellationSink
*sink
)
2787 FIXME("iface %p, transform %p, tolerance %.8e, sink %p stub!\n", iface
, transform
, tolerance
, sink
);
2792 static HRESULT STDMETHODCALLTYPE
d2d_transformed_geometry_CombineWithGeometry(ID2D1TransformedGeometry
*iface
,
2793 ID2D1Geometry
*geometry
, D2D1_COMBINE_MODE combine_mode
, const D2D1_MATRIX_3X2_F
*transform
,
2794 float tolerance
, ID2D1SimplifiedGeometrySink
*sink
)
2796 FIXME("iface %p, geometry %p, combine_mode %#x, transform %p, tolerance %.8e, sink %p stub!\n",
2797 iface
, geometry
, combine_mode
, transform
, tolerance
, sink
);
2802 static HRESULT STDMETHODCALLTYPE
d2d_transformed_geometry_Outline(ID2D1TransformedGeometry
*iface
,
2803 const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, ID2D1SimplifiedGeometrySink
*sink
)
2805 FIXME("iface %p, transform %p, tolerance %.8e, sink %p stub!\n", iface
, transform
, tolerance
, sink
);
2810 static HRESULT STDMETHODCALLTYPE
d2d_transformed_geometry_ComputeArea(ID2D1TransformedGeometry
*iface
,
2811 const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, float *area
)
2813 FIXME("iface %p, transform %p, tolerance %.8e, area %p stub!\n", iface
, transform
, tolerance
, area
);
2818 static HRESULT STDMETHODCALLTYPE
d2d_transformed_geometry_ComputeLength(ID2D1TransformedGeometry
*iface
,
2819 const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, float *length
)
2821 FIXME("iface %p, transform %p, tolerance %.8e, length %p stub!\n", iface
, transform
, tolerance
, length
);
2826 static HRESULT STDMETHODCALLTYPE
d2d_transformed_geometry_ComputePointAtLength(ID2D1TransformedGeometry
*iface
,
2827 float length
, const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, D2D1_POINT_2F
*point
,
2828 D2D1_POINT_2F
*tangent
)
2830 FIXME("iface %p, length %.8e, transform %p, tolerance %.8e, point %p, tangent %p stub!\n",
2831 iface
, length
, transform
, tolerance
, point
, tangent
);
2836 static HRESULT STDMETHODCALLTYPE
d2d_transformed_geometry_Widen(ID2D1TransformedGeometry
*iface
, float stroke_width
,
2837 ID2D1StrokeStyle
*stroke_style
, const D2D1_MATRIX_3X2_F
*transform
, float tolerance
,
2838 ID2D1SimplifiedGeometrySink
*sink
)
2840 FIXME("iface %p, stroke_width %.8e, stroke_style %p, transform %p, tolerance %.8e, sink %p stub!\n",
2841 iface
, stroke_width
, stroke_style
, transform
, tolerance
, sink
);
2846 static void STDMETHODCALLTYPE
d2d_transformed_geometry_GetSourceGeometry(ID2D1TransformedGeometry
*iface
,
2847 ID2D1Geometry
**src_geometry
)
2849 struct d2d_geometry
*geometry
= impl_from_ID2D1TransformedGeometry(iface
);
2851 TRACE("iface %p, src_geometry %p.\n", iface
, src_geometry
);
2853 ID2D1Geometry_AddRef(*src_geometry
= geometry
->u
.transformed
.src_geometry
);
2856 static void STDMETHODCALLTYPE
d2d_transformed_geometry_GetTransform(ID2D1TransformedGeometry
*iface
,
2857 D2D1_MATRIX_3X2_F
*transform
)
2859 struct d2d_geometry
*geometry
= impl_from_ID2D1TransformedGeometry(iface
);
2861 TRACE("iface %p, transform %p.\n", iface
, transform
);
2863 *transform
= geometry
->transform
;
2866 static const struct ID2D1TransformedGeometryVtbl d2d_transformed_geometry_vtbl
=
2868 d2d_transformed_geometry_QueryInterface
,
2869 d2d_transformed_geometry_AddRef
,
2870 d2d_transformed_geometry_Release
,
2871 d2d_transformed_geometry_GetFactory
,
2872 d2d_transformed_geometry_GetBounds
,
2873 d2d_transformed_geometry_GetWidenedBounds
,
2874 d2d_transformed_geometry_StrokeContainsPoint
,
2875 d2d_transformed_geometry_FillContainsPoint
,
2876 d2d_transformed_geometry_CompareWithGeometry
,
2877 d2d_transformed_geometry_Simplify
,
2878 d2d_transformed_geometry_Tessellate
,
2879 d2d_transformed_geometry_CombineWithGeometry
,
2880 d2d_transformed_geometry_Outline
,
2881 d2d_transformed_geometry_ComputeArea
,
2882 d2d_transformed_geometry_ComputeLength
,
2883 d2d_transformed_geometry_ComputePointAtLength
,
2884 d2d_transformed_geometry_Widen
,
2885 d2d_transformed_geometry_GetSourceGeometry
,
2886 d2d_transformed_geometry_GetTransform
,
2889 void d2d_transformed_geometry_init(struct d2d_geometry
*geometry
, ID2D1Factory
*factory
,
2890 ID2D1Geometry
*src_geometry
, const D2D_MATRIX_3X2_F
*transform
)
2892 struct d2d_geometry
*src_impl
;
2894 d2d_geometry_init(geometry
, factory
, transform
, (ID2D1GeometryVtbl
*)&d2d_transformed_geometry_vtbl
);
2895 ID2D1Geometry_AddRef(geometry
->u
.transformed
.src_geometry
= src_geometry
);
2896 src_impl
= unsafe_impl_from_ID2D1Geometry(src_geometry
);
2897 geometry
->fill
= src_impl
->fill
;
2900 struct d2d_geometry
*unsafe_impl_from_ID2D1Geometry(ID2D1Geometry
*iface
)
2904 assert(iface
->lpVtbl
== (const ID2D1GeometryVtbl
*)&d2d_path_geometry_vtbl
2905 || iface
->lpVtbl
== (const ID2D1GeometryVtbl
*)&d2d_rectangle_geometry_vtbl
2906 || iface
->lpVtbl
== (const ID2D1GeometryVtbl
*)&d2d_transformed_geometry_vtbl
);
2907 return CONTAINING_RECORD(iface
, struct d2d_geometry
, ID2D1Geometry_iface
);