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_FIGURE_FLAG_CLOSED 0x00000001u
30 #define D2D_FIGURE_FLAG_HOLLOW 0x00000002u
32 #define D2D_CDT_EDGE_FLAG_FREED 0x80000000u
33 #define D2D_CDT_EDGE_FLAG_VISITED(r) (1u << (r))
35 #define D2D_FP_EPS (1.0f / (1 << FLT_MANT_DIG))
37 static const D2D1_MATRIX_3X2_F identity
=
44 enum d2d_cdt_edge_next
46 D2D_EDGE_NEXT_ORIGIN
= 0,
47 D2D_EDGE_NEXT_ROT
= 1,
48 D2D_EDGE_NEXT_SYM
= 2,
49 D2D_EDGE_NEXT_TOR
= 3,
56 D2D_VERTEX_TYPE_BEZIER
,
57 D2D_VERTEX_TYPE_SPLIT_BEZIER
,
60 struct d2d_segment_idx
69 D2D1_POINT_2F
*vertices
;
71 enum d2d_vertex_type
*vertex_types
;
72 size_t vertex_types_size
;
75 D2D1_POINT_2F
*bezier_controls
;
76 size_t bezier_controls_size
;
77 size_t bezier_control_count
;
79 D2D1_POINT_2F
*original_bezier_controls
;
80 size_t original_bezier_control_count
;
86 struct d2d_cdt_edge_ref
89 enum d2d_cdt_edge_next r
;
94 struct d2d_cdt_edge_ref next
[4];
101 struct d2d_cdt_edge
*edges
;
106 const D2D1_POINT_2F
*vertices
;
109 struct d2d_geometry_intersection
118 struct d2d_geometry_intersections
120 struct d2d_geometry_intersection
*intersections
;
121 size_t intersections_size
;
122 size_t intersection_count
;
125 struct d2d_fp_two_vec2
137 static void d2d_bezier_vertex_set(struct d2d_bezier_vertex
*b
,
138 const D2D1_POINT_2F
*p
, float u
, float v
, float sign
)
143 b
->texcoord
.sign
= sign
;
146 static void d2d_face_set(struct d2d_face
*f
, UINT16 v0
, UINT16 v1
, UINT16 v2
)
153 static void d2d_outline_vertex_set(struct d2d_outline_vertex
*v
, float x
, float y
,
154 float prev_x
, float prev_y
, float next_x
, float next_y
)
156 d2d_point_set(&v
->position
, x
, y
);
157 d2d_point_set(&v
->prev
, prev_x
, prev_y
);
158 d2d_point_set(&v
->next
, next_x
, next_y
);
161 static void d2d_bezier_outline_vertex_set(struct d2d_bezier_outline_vertex
*b
, const D2D1_POINT_2F
*position
,
162 const D2D1_POINT_2F
*p0
, const D2D1_POINT_2F
*p1
, const D2D1_POINT_2F
*p2
,
163 float prev_x
, float prev_y
, float next_x
, float next_y
)
165 b
->position
= *position
;
169 d2d_point_set(&b
->prev
, prev_x
, prev_y
);
170 d2d_point_set(&b
->next
, next_x
, next_y
);
173 static void d2d_fp_two_sum(float *out
, float a
, float b
)
175 float a_virt
, a_round
, b_virt
, b_round
;
179 a_virt
= out
[1] - b_virt
;
180 b_round
= b
- b_virt
;
181 a_round
= a
- a_virt
;
182 out
[0] = a_round
+ b_round
;
185 static void d2d_fp_fast_two_sum(float *out
, float a
, float b
)
194 static void d2d_fp_two_two_sum(float *out
, const float *a
, const float *b
)
198 d2d_fp_two_sum(out
, a
[0], b
[0]);
199 d2d_fp_two_sum(sum
, a
[1], out
[1]);
200 d2d_fp_two_sum(&out
[1], sum
[0], b
[1]);
201 d2d_fp_two_sum(&out
[2], sum
[1], out
[2]);
204 static void d2d_fp_two_diff_tail(float *out
, float a
, float b
, float x
)
206 float a_virt
, a_round
, b_virt
, b_round
;
210 b_round
= b_virt
- b
;
211 a_round
= a
- a_virt
;
212 *out
= a_round
+ b_round
;
215 static void d2d_fp_two_two_diff(float *out
, const float *a
, const float *b
)
220 d2d_fp_two_diff_tail(out
, a
[0], b
[0], diff
);
221 d2d_fp_two_sum(sum
, a
[1], diff
);
222 diff
= sum
[0] - b
[1];
223 d2d_fp_two_diff_tail(&out
[1], sum
[0], b
[1], diff
);
224 d2d_fp_two_sum(&out
[2], sum
[1], diff
);
227 static void d2d_fp_split(float *out
, float a
)
231 c
= a
* ((1 << (FLT_MANT_DIG
/ 2)) + 1.0f
);
237 static void d2d_fp_two_product_presplit(float *out
, float a
, float b
, const float *b_split
)
239 float a_split
[2], err1
, err2
, err3
;
242 d2d_fp_split(a_split
, a
);
243 err1
= out
[1] - (a_split
[1] * b_split
[1]);
244 err2
= err1
- (a_split
[0] * b_split
[1]);
245 err3
= err2
- (a_split
[1] * b_split
[0]);
246 out
[0] = (a_split
[0] * b_split
[0]) - err3
;
249 static void d2d_fp_two_product(float *out
, float a
, float b
)
253 d2d_fp_split(b_split
, b
);
254 d2d_fp_two_product_presplit(out
, a
, b
, b_split
);
257 static void d2d_fp_square(float *out
, float a
)
259 float a_split
[2], err1
, err2
;
262 d2d_fp_split(a_split
, a
);
263 err1
= out
[1] - (a_split
[1] * a_split
[1]);
264 err2
= err1
- ((a_split
[1] + a_split
[1]) * a_split
[0]);
265 out
[0] = (a_split
[0] * a_split
[0]) - err2
;
268 static float d2d_fp_estimate(float *a
, size_t len
)
279 static void d2d_fp_fast_expansion_sum_zeroelim(float *out
, size_t *out_len
,
280 const float *a
, size_t a_len
, const float *b
, size_t b_len
)
282 float sum
[2], q
, a_curr
, b_curr
;
283 size_t a_idx
, b_idx
, out_idx
;
288 if ((b_curr
> a_curr
) == (b_curr
> -a_curr
))
299 if (a_idx
< a_len
&& b_idx
< b_len
)
301 if ((b_curr
> a_curr
) == (b_curr
> -a_curr
))
303 d2d_fp_fast_two_sum(sum
, a_curr
, q
);
308 d2d_fp_fast_two_sum(sum
, b_curr
, q
);
312 out
[out_idx
++] = sum
[0];
314 while (a_idx
< a_len
&& b_idx
< b_len
)
316 if ((b_curr
> a_curr
) == (b_curr
> -a_curr
))
318 d2d_fp_two_sum(sum
, q
, a_curr
);
323 d2d_fp_two_sum(sum
, q
, b_curr
);
327 out
[out_idx
++] = sum
[0];
331 while (a_idx
< a_len
)
333 d2d_fp_two_sum(sum
, q
, a_curr
);
336 out
[out_idx
++] = sum
[0];
339 while (b_idx
< b_len
)
341 d2d_fp_two_sum(sum
, q
, b_curr
);
344 out
[out_idx
++] = sum
[0];
347 if (q
!= 0.0f
|| !out_idx
)
353 static void d2d_fp_scale_expansion_zeroelim(float *out
, size_t *out_len
, const float *a
, size_t a_len
, float b
)
355 float product
[2], sum
[2], b_split
[2], q
[2], a_curr
;
356 size_t a_idx
, out_idx
;
358 d2d_fp_split(b_split
, b
);
359 d2d_fp_two_product_presplit(q
, a
[0], b
, b_split
);
362 out
[out_idx
++] = q
[0];
363 for (a_idx
= 1; a_idx
< a_len
; ++a_idx
)
366 d2d_fp_two_product_presplit(product
, a_curr
, b
, b_split
);
367 d2d_fp_two_sum(sum
, q
[1], product
[0]);
369 out
[out_idx
++] = sum
[0];
370 d2d_fp_fast_two_sum(q
, product
[1], sum
[1]);
372 out
[out_idx
++] = q
[0];
374 if (q
[1] != 0.0f
|| !out_idx
)
375 out
[out_idx
++] = q
[1];
380 static void d2d_point_subtract(D2D1_POINT_2F
*out
,
381 const D2D1_POINT_2F
*a
, const D2D1_POINT_2F
*b
)
383 out
->x
= a
->x
- b
->x
;
384 out
->y
= a
->y
- b
->y
;
387 static void d2d_point_scale(D2D1_POINT_2F
*p
, float scale
)
393 static void d2d_point_lerp(D2D1_POINT_2F
*out
,
394 const D2D1_POINT_2F
*a
, const D2D1_POINT_2F
*b
, float t
)
396 out
->x
= a
->x
* (1.0f
- t
) + b
->x
* t
;
397 out
->y
= a
->y
* (1.0f
- t
) + b
->y
* t
;
400 static void d2d_point_calculate_bezier(D2D1_POINT_2F
*out
, const D2D1_POINT_2F
*p0
,
401 const D2D1_POINT_2F
*p1
, const D2D1_POINT_2F
*p2
, float t
)
403 float t_c
= 1.0f
- t
;
405 out
->x
= t_c
* (t_c
* p0
->x
+ t
* p1
->x
) + t
* (t_c
* p1
->x
+ t
* p2
->x
);
406 out
->y
= t_c
* (t_c
* p0
->y
+ t
* p1
->y
) + t
* (t_c
* p1
->y
+ t
* p2
->y
);
409 static float d2d_point_dot(const D2D1_POINT_2F
*p0
, const D2D1_POINT_2F
*p1
)
411 return p0
->x
* p1
->x
+ p0
->y
* p1
->y
;
414 static void d2d_point_normalise(D2D1_POINT_2F
*p
)
418 if ((l
= sqrtf(d2d_point_dot(p
, p
))) != 0.0f
)
419 d2d_point_scale(p
, 1.0f
/ l
);
422 /* This implementation is based on the paper "Adaptive Precision
423 * Floating-Point Arithmetic and Fast Robust Geometric Predicates" and
424 * associated (Public Domain) code by Jonathan Richard Shewchuk. */
425 static float d2d_point_ccw(const D2D1_POINT_2F
*a
, const D2D1_POINT_2F
*b
, const D2D1_POINT_2F
*c
)
427 static const float err_bound_result
= (3.0f
+ 8.0f
* D2D_FP_EPS
) * D2D_FP_EPS
;
428 static const float err_bound_a
= (3.0f
+ 16.0f
* D2D_FP_EPS
) * D2D_FP_EPS
;
429 static const float err_bound_b
= (2.0f
+ 12.0f
* D2D_FP_EPS
) * D2D_FP_EPS
;
430 static const float err_bound_c
= (9.0f
+ 64.0f
* D2D_FP_EPS
) * D2D_FP_EPS
* D2D_FP_EPS
;
431 float det_d
[16], det_c2
[12], det_c1
[8], det_b
[4], temp4
[4], temp2a
[2], temp2b
[2], abxacy
[2], abyacx
[2];
432 size_t det_d_len
, det_c2_len
, det_c1_len
;
433 float det
, det_sum
, err_bound
;
434 struct d2d_fp_two_vec2 ab
, ac
;
436 ab
.x
[1] = b
->x
- a
->x
;
437 ab
.y
[1] = b
->y
- a
->y
;
438 ac
.x
[1] = c
->x
- a
->x
;
439 ac
.y
[1] = c
->y
- a
->y
;
441 abxacy
[1] = ab
.x
[1] * ac
.y
[1];
442 abyacx
[1] = ab
.y
[1] * ac
.x
[1];
443 det
= abxacy
[1] - abyacx
[1];
445 if (abxacy
[1] > 0.0f
)
447 if (abyacx
[1] <= 0.0f
)
449 det_sum
= abxacy
[1] + abyacx
[1];
451 else if (abxacy
[1] < 0.0f
)
453 if (abyacx
[1] >= 0.0f
)
455 det_sum
= -abxacy
[1] - abyacx
[1];
462 err_bound
= err_bound_a
* det_sum
;
463 if (det
>= err_bound
|| -det
>= err_bound
)
466 d2d_fp_two_product(abxacy
, ab
.x
[1], ac
.y
[1]);
467 d2d_fp_two_product(abyacx
, ab
.y
[1], ac
.x
[1]);
468 d2d_fp_two_two_diff(det_b
, abxacy
, abyacx
);
470 det
= d2d_fp_estimate(det_b
, 4);
471 err_bound
= err_bound_b
* det_sum
;
472 if (det
>= err_bound
|| -det
>= err_bound
)
475 d2d_fp_two_diff_tail(&ab
.x
[0], b
->x
, a
->x
, ab
.x
[1]);
476 d2d_fp_two_diff_tail(&ab
.y
[0], b
->y
, a
->y
, ab
.y
[1]);
477 d2d_fp_two_diff_tail(&ac
.x
[0], c
->x
, a
->x
, ac
.x
[1]);
478 d2d_fp_two_diff_tail(&ac
.y
[0], c
->y
, a
->y
, ac
.y
[1]);
480 if (ab
.x
[0] == 0.0f
&& ab
.y
[0] == 0.0f
&& ac
.x
[0] == 0.0f
&& ac
.y
[0] == 0.0f
)
483 err_bound
= err_bound_c
* det_sum
+ err_bound_result
* fabsf(det
);
484 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]);
485 if (det
>= err_bound
|| -det
>= err_bound
)
488 d2d_fp_two_product(temp2a
, ab
.x
[0], ac
.y
[1]);
489 d2d_fp_two_product(temp2b
, ab
.y
[0], ac
.x
[1]);
490 d2d_fp_two_two_diff(temp4
, temp2a
, temp2b
);
491 d2d_fp_fast_expansion_sum_zeroelim(det_c1
, &det_c1_len
, det_b
, 4, temp4
, 4);
493 d2d_fp_two_product(temp2a
, ab
.x
[1], ac
.y
[0]);
494 d2d_fp_two_product(temp2b
, ab
.y
[1], ac
.x
[0]);
495 d2d_fp_two_two_diff(temp4
, temp2a
, temp2b
);
496 d2d_fp_fast_expansion_sum_zeroelim(det_c2
, &det_c2_len
, det_c1
, det_c1_len
, temp4
, 4);
498 d2d_fp_two_product(temp2a
, ab
.x
[0], ac
.y
[0]);
499 d2d_fp_two_product(temp2b
, ab
.y
[0], ac
.x
[0]);
500 d2d_fp_two_two_diff(temp4
, temp2a
, temp2b
);
501 d2d_fp_fast_expansion_sum_zeroelim(det_d
, &det_d_len
, det_c2
, det_c2_len
, temp4
, 4);
503 return det_d
[det_d_len
- 1];
506 static void d2d_rect_union(D2D1_RECT_F
*l
, const D2D1_RECT_F
*r
)
508 l
->left
= min(l
->left
, r
->left
);
509 l
->top
= min(l
->top
, r
->top
);
510 l
->right
= max(l
->right
, r
->right
);
511 l
->bottom
= max(l
->bottom
, r
->bottom
);
514 static BOOL
d2d_rect_check_overlap(const D2D_RECT_F
*p
, const D2D_RECT_F
*q
)
516 return p
->left
< q
->right
&& p
->top
< q
->bottom
&& p
->right
> q
->left
&& p
->bottom
> q
->top
;
519 static void d2d_rect_get_bezier_bounds(D2D_RECT_F
*bounds
, const D2D1_POINT_2F
*p0
,
520 const D2D1_POINT_2F
*p1
, const D2D1_POINT_2F
*p2
)
525 bounds
->left
= p0
->x
;
527 bounds
->right
= p0
->x
;
528 bounds
->bottom
= p0
->y
;
530 d2d_rect_expand(bounds
, p2
);
532 /* f(t) = (1 - t)²P₀ + 2(1 - t)tP₁ + t²P₂
533 * f'(t) = 2(1 - t)(P₁ - P₀) + 2t(P₂ - P₁)
534 * = 2(P₂ - 2P₁ + P₀)t + 2(P₁ - P₀)
537 * t = (P₀ - P₁) / (P₂ - 2P₁ + P₀) */
538 root
= (p0
->x
- p1
->x
) / (p2
->x
- 2.0f
* p1
->x
+ p0
->x
);
539 if (root
> 0.0f
&& root
< 1.0f
)
541 d2d_point_calculate_bezier(&p
, p0
, p1
, p2
, root
);
542 d2d_rect_expand(bounds
, &p
);
545 root
= (p0
->y
- p1
->y
) / (p2
->y
- 2.0f
* p1
->y
+ p0
->y
);
546 if (root
> 0.0f
&& root
< 1.0f
)
548 d2d_point_calculate_bezier(&p
, p0
, p1
, p2
, root
);
549 d2d_rect_expand(bounds
, &p
);
553 static void d2d_rect_get_bezier_segment_bounds(D2D_RECT_F
*bounds
, const D2D1_POINT_2F
*p0
,
554 const D2D1_POINT_2F
*p1
, const D2D1_POINT_2F
*p2
, float start
, float end
)
556 D2D1_POINT_2F q
[3], r
[2];
558 d2d_point_lerp(&r
[0], p0
, p1
, start
);
559 d2d_point_lerp(&r
[1], p1
, p2
, start
);
560 d2d_point_lerp(&q
[0], &r
[0], &r
[1], start
);
562 end
= (end
- start
) / (1.0f
- start
);
563 d2d_point_lerp(&q
[1], &q
[0], &r
[1], end
);
564 d2d_point_lerp(&r
[0], &r
[1], p2
, end
);
565 d2d_point_lerp(&q
[2], &q
[1], &r
[0], end
);
567 d2d_rect_get_bezier_bounds(bounds
, &q
[0], &q
[1], &q
[2]);
570 static BOOL
d2d_array_reserve(void **elements
, size_t *capacity
, size_t element_count
, size_t element_size
)
572 size_t new_capacity
, max_capacity
;
575 if (element_count
<= *capacity
)
578 max_capacity
= ~(size_t)0 / element_size
;
579 if (max_capacity
< element_count
)
582 new_capacity
= max(*capacity
, 4);
583 while (new_capacity
< element_count
&& new_capacity
<= max_capacity
/ 2)
586 if (new_capacity
< element_count
)
587 new_capacity
= max_capacity
;
590 new_elements
= HeapReAlloc(GetProcessHeap(), 0, *elements
, new_capacity
* element_size
);
592 new_elements
= HeapAlloc(GetProcessHeap(), 0, new_capacity
* element_size
);
597 *elements
= new_elements
;
598 *capacity
= new_capacity
;
602 static BOOL
d2d_figure_insert_vertex(struct d2d_figure
*figure
, size_t idx
, D2D1_POINT_2F vertex
)
604 if (!d2d_array_reserve((void **)&figure
->vertices
, &figure
->vertices_size
,
605 figure
->vertex_count
+ 1, sizeof(*figure
->vertices
)))
607 ERR("Failed to grow vertices array.\n");
611 if (!d2d_array_reserve((void **)&figure
->vertex_types
, &figure
->vertex_types_size
,
612 figure
->vertex_count
+ 1, sizeof(*figure
->vertex_types
)))
614 ERR("Failed to grow vertex types array.\n");
618 memmove(&figure
->vertices
[idx
+ 1], &figure
->vertices
[idx
],
619 (figure
->vertex_count
- idx
) * sizeof(*figure
->vertices
));
620 memmove(&figure
->vertex_types
[idx
+ 1], &figure
->vertex_types
[idx
],
621 (figure
->vertex_count
- idx
) * sizeof(*figure
->vertex_types
));
622 figure
->vertices
[idx
] = vertex
;
623 figure
->vertex_types
[idx
] = D2D_VERTEX_TYPE_NONE
;
624 d2d_rect_expand(&figure
->bounds
, &vertex
);
625 ++figure
->vertex_count
;
629 static BOOL
d2d_figure_add_vertex(struct d2d_figure
*figure
, D2D1_POINT_2F vertex
)
631 size_t last
= figure
->vertex_count
- 1;
633 if (figure
->vertex_count
&& figure
->vertex_types
[last
] == D2D_VERTEX_TYPE_LINE
634 && !memcmp(&figure
->vertices
[last
], &vertex
, sizeof(vertex
)))
637 if (!d2d_array_reserve((void **)&figure
->vertices
, &figure
->vertices_size
,
638 figure
->vertex_count
+ 1, sizeof(*figure
->vertices
)))
640 ERR("Failed to grow vertices array.\n");
644 if (!d2d_array_reserve((void **)&figure
->vertex_types
, &figure
->vertex_types_size
,
645 figure
->vertex_count
+ 1, sizeof(*figure
->vertex_types
)))
647 ERR("Failed to grow vertex types array.\n");
651 figure
->vertices
[figure
->vertex_count
] = vertex
;
652 figure
->vertex_types
[figure
->vertex_count
] = D2D_VERTEX_TYPE_NONE
;
653 d2d_rect_expand(&figure
->bounds
, &vertex
);
654 ++figure
->vertex_count
;
658 static BOOL
d2d_figure_insert_bezier_control(struct d2d_figure
*figure
, size_t idx
, const D2D1_POINT_2F
*p
)
660 if (!d2d_array_reserve((void **)&figure
->bezier_controls
, &figure
->bezier_controls_size
,
661 figure
->bezier_control_count
+ 1, sizeof(*figure
->bezier_controls
)))
663 ERR("Failed to grow bezier controls array.\n");
667 memmove(&figure
->bezier_controls
[idx
+ 1], &figure
->bezier_controls
[idx
],
668 (figure
->bezier_control_count
- idx
) * sizeof(*figure
->bezier_controls
));
669 figure
->bezier_controls
[idx
] = *p
;
670 ++figure
->bezier_control_count
;
675 static BOOL
d2d_figure_add_bezier_control(struct d2d_figure
*figure
, const D2D1_POINT_2F
*p
)
677 if (!d2d_array_reserve((void **)&figure
->bezier_controls
, &figure
->bezier_controls_size
,
678 figure
->bezier_control_count
+ 1, sizeof(*figure
->bezier_controls
)))
680 ERR("Failed to grow bezier controls array.\n");
684 figure
->bezier_controls
[figure
->bezier_control_count
++] = *p
;
689 static void d2d_cdt_edge_rot(struct d2d_cdt_edge_ref
*dst
, const struct d2d_cdt_edge_ref
*src
)
692 dst
->r
= (src
->r
+ D2D_EDGE_NEXT_ROT
) & 3;
695 static void d2d_cdt_edge_sym(struct d2d_cdt_edge_ref
*dst
, const struct d2d_cdt_edge_ref
*src
)
698 dst
->r
= (src
->r
+ D2D_EDGE_NEXT_SYM
) & 3;
701 static void d2d_cdt_edge_tor(struct d2d_cdt_edge_ref
*dst
, const struct d2d_cdt_edge_ref
*src
)
704 dst
->r
= (src
->r
+ D2D_EDGE_NEXT_TOR
) & 3;
707 static void d2d_cdt_edge_next_left(const struct d2d_cdt
*cdt
,
708 struct d2d_cdt_edge_ref
*dst
, const struct d2d_cdt_edge_ref
*src
)
710 d2d_cdt_edge_rot(dst
, &cdt
->edges
[src
->idx
].next
[(src
->r
+ D2D_EDGE_NEXT_TOR
) & 3]);
713 static void d2d_cdt_edge_next_origin(const struct d2d_cdt
*cdt
,
714 struct d2d_cdt_edge_ref
*dst
, const struct d2d_cdt_edge_ref
*src
)
716 *dst
= cdt
->edges
[src
->idx
].next
[src
->r
];
719 static void d2d_cdt_edge_prev_origin(const struct d2d_cdt
*cdt
,
720 struct d2d_cdt_edge_ref
*dst
, const struct d2d_cdt_edge_ref
*src
)
722 d2d_cdt_edge_rot(dst
, &cdt
->edges
[src
->idx
].next
[(src
->r
+ D2D_EDGE_NEXT_ROT
) & 3]);
725 static size_t d2d_cdt_edge_origin(const struct d2d_cdt
*cdt
, const struct d2d_cdt_edge_ref
*e
)
727 return cdt
->edges
[e
->idx
].vertex
[e
->r
>> 1];
730 static size_t d2d_cdt_edge_destination(const struct d2d_cdt
*cdt
, const struct d2d_cdt_edge_ref
*e
)
732 return cdt
->edges
[e
->idx
].vertex
[!(e
->r
>> 1)];
735 static void d2d_cdt_edge_set_origin(const struct d2d_cdt
*cdt
,
736 const struct d2d_cdt_edge_ref
*e
, size_t vertex
)
738 cdt
->edges
[e
->idx
].vertex
[e
->r
>> 1] = vertex
;
741 static void d2d_cdt_edge_set_destination(const struct d2d_cdt
*cdt
,
742 const struct d2d_cdt_edge_ref
*e
, size_t vertex
)
744 cdt
->edges
[e
->idx
].vertex
[!(e
->r
>> 1)] = vertex
;
747 static float d2d_cdt_ccw(const struct d2d_cdt
*cdt
, size_t a
, size_t b
, size_t c
)
749 return d2d_point_ccw(&cdt
->vertices
[a
], &cdt
->vertices
[b
], &cdt
->vertices
[c
]);
752 static BOOL
d2d_cdt_rightof(const struct d2d_cdt
*cdt
, size_t p
, const struct d2d_cdt_edge_ref
*e
)
754 return d2d_cdt_ccw(cdt
, p
, d2d_cdt_edge_destination(cdt
, e
), d2d_cdt_edge_origin(cdt
, e
)) > 0.0f
;
757 static BOOL
d2d_cdt_leftof(const struct d2d_cdt
*cdt
, size_t p
, const struct d2d_cdt_edge_ref
*e
)
759 return d2d_cdt_ccw(cdt
, p
, d2d_cdt_edge_origin(cdt
, e
), d2d_cdt_edge_destination(cdt
, e
)) > 0.0f
;
764 static void d2d_fp_four_det2x2(float *out
, float ax
, float ay
, float bx
, float by
)
766 float axby
[2], aybx
[2];
768 d2d_fp_two_product(axby
, ax
, by
);
769 d2d_fp_two_product(aybx
, ay
, bx
);
770 d2d_fp_two_two_diff(out
, axby
, aybx
);
773 /* (a->x² + a->y²) * det2x2 */
774 static void d2d_fp_sub_det3x3(float *out
, size_t *out_len
, const struct d2d_fp_two_vec2
*a
, const float *det2x2
)
776 size_t axd_len
, ayd_len
, axxd_len
, ayyd_len
;
777 float axd
[8], ayd
[8], axxd
[16], ayyd
[16];
779 d2d_fp_scale_expansion_zeroelim(axd
, &axd_len
, det2x2
, 4, a
->x
[1]);
780 d2d_fp_scale_expansion_zeroelim(axxd
, &axxd_len
, axd
, axd_len
, a
->x
[1]);
781 d2d_fp_scale_expansion_zeroelim(ayd
, &ayd_len
, det2x2
, 4, a
->y
[1]);
782 d2d_fp_scale_expansion_zeroelim(ayyd
, &ayyd_len
, ayd
, ayd_len
, a
->y
[1]);
783 d2d_fp_fast_expansion_sum_zeroelim(out
, out_len
, axxd
, axxd_len
, ayyd
, ayyd_len
);
786 /* det_abt = det_ab * c[0]
787 * fin += c[0] * (az * b - bz * a + c[1] * det_ab * 2.0f) */
788 static void d2d_cdt_incircle_refine1(struct d2d_fp_fin
*fin
, float *det_abt
, size_t *det_abt_len
,
789 const float *det_ab
, float a
, const float *az
, float b
, const float *bz
, const float *c
)
791 size_t temp48_len
, temp32_len
, temp16a_len
, temp16b_len
, temp16c_len
, temp8_len
;
792 float temp48
[48], temp32
[32], temp16a
[16], temp16b
[16], temp16c
[16], temp8
[8];
795 d2d_fp_scale_expansion_zeroelim(det_abt
, det_abt_len
, det_ab
, 4, c
[0]);
796 d2d_fp_scale_expansion_zeroelim(temp16a
, &temp16a_len
, det_abt
, *det_abt_len
, 2.0f
* c
[1]);
797 d2d_fp_scale_expansion_zeroelim(temp8
, &temp8_len
, az
, 4, c
[0]);
798 d2d_fp_scale_expansion_zeroelim(temp16b
, &temp16b_len
, temp8
, temp8_len
, b
);
799 d2d_fp_scale_expansion_zeroelim(temp8
, &temp8_len
, bz
, 4, c
[0]);
800 d2d_fp_scale_expansion_zeroelim(temp16c
, &temp16c_len
, temp8
, temp8_len
, -a
);
801 d2d_fp_fast_expansion_sum_zeroelim(temp32
, &temp32_len
, temp16a
, temp16a_len
, temp16b
, temp16b_len
);
802 d2d_fp_fast_expansion_sum_zeroelim(temp48
, &temp48_len
, temp16c
, temp16c_len
, temp32
, temp32_len
);
803 d2d_fp_fast_expansion_sum_zeroelim(fin
->other
, &fin
->length
, fin
->now
, fin
->length
, temp48
, temp48_len
);
804 swap
= fin
->now
; fin
->now
= fin
->other
; fin
->other
= swap
;
807 static void d2d_cdt_incircle_refine2(struct d2d_fp_fin
*fin
, const struct d2d_fp_two_vec2
*a
,
808 const struct d2d_fp_two_vec2
*b
, const float *bz
, const struct d2d_fp_two_vec2
*c
, const float *cz
,
809 const float *axt_det_bc
, size_t axt_det_bc_len
, const float *ayt_det_bc
, size_t ayt_det_bc_len
)
811 size_t temp64_len
, temp48_len
, temp32a_len
, temp32b_len
, temp16a_len
, temp16b_len
, temp8_len
;
812 float temp64
[64], temp48
[48], temp32a
[32], temp32b
[32], temp16a
[16], temp16b
[16], temp8
[8];
813 float bct
[8], bctt
[4], temp4a
[4], temp4b
[4], temp2a
[2], temp2b
[2];
814 size_t bct_len
, bctt_len
;
817 /* 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]) */
818 /* bctt = b->x[0] * c->y[0] + c->x[0] * b->y[0] */
819 if (b
->x
[0] != 0.0f
|| b
->y
[0] != 0.0f
|| c
->x
[0] != 0.0f
|| c
->y
[0] != 0.0f
)
821 d2d_fp_two_product(temp2a
, b
->x
[0], c
->y
[1]);
822 d2d_fp_two_product(temp2b
, b
->x
[1], c
->y
[0]);
823 d2d_fp_two_two_sum(temp4a
, temp2a
, temp2b
);
824 d2d_fp_two_product(temp2a
, c
->x
[0], -b
->y
[1]);
825 d2d_fp_two_product(temp2b
, c
->x
[1], -b
->y
[0]);
826 d2d_fp_two_two_sum(temp4b
, temp2a
, temp2b
);
827 d2d_fp_fast_expansion_sum_zeroelim(bct
, &bct_len
, temp4a
, 4, temp4b
, 4);
829 d2d_fp_two_product(temp2a
, b
->x
[0], c
->y
[0]);
830 d2d_fp_two_product(temp2b
, c
->x
[0], b
->y
[0]);
831 d2d_fp_two_two_diff(bctt
, temp2a
, temp2b
);
844 size_t axt_bct_len
, axt_bctt_len
;
845 float axt_bct
[16], axt_bctt
[8];
847 /* fin += a->x[0] * (axt_det_bc + bct * 2.0f * a->x[1]) */
848 d2d_fp_scale_expansion_zeroelim(temp16a
, &temp16a_len
, axt_det_bc
, axt_det_bc_len
, a
->x
[0]);
849 d2d_fp_scale_expansion_zeroelim(axt_bct
, &axt_bct_len
, bct
, bct_len
, a
->x
[0]);
850 d2d_fp_scale_expansion_zeroelim(temp32a
, &temp32a_len
, axt_bct
, axt_bct_len
, 2.0f
* a
->x
[1]);
851 d2d_fp_fast_expansion_sum_zeroelim(temp48
, &temp48_len
, temp16a
, temp16a_len
, temp32a
, temp32a_len
);
852 d2d_fp_fast_expansion_sum_zeroelim(fin
->other
, &fin
->length
, fin
->now
, fin
->length
, temp48
, temp48_len
);
853 swap
= fin
->now
; fin
->now
= fin
->other
; fin
->other
= swap
;
857 /* fin += a->x[0] * cz * b->y[0] */
858 d2d_fp_scale_expansion_zeroelim(temp8
, &temp8_len
, cz
, 4, a
->x
[0]);
859 d2d_fp_scale_expansion_zeroelim(temp16a
, &temp16a_len
, temp8
, temp8_len
, b
->y
[0]);
860 d2d_fp_fast_expansion_sum_zeroelim(fin
->other
, &fin
->length
, fin
->now
, fin
->length
, temp16a
, temp16a_len
);
861 swap
= fin
->now
; fin
->now
= fin
->other
; fin
->other
= swap
;
866 /* fin -= a->x[0] * bz * c->y[0] */
867 d2d_fp_scale_expansion_zeroelim(temp8
, &temp8_len
, bz
, 4, -a
->x
[0]);
868 d2d_fp_scale_expansion_zeroelim(temp16a
, &temp16a_len
, temp8
, temp8_len
, c
->y
[0]);
869 d2d_fp_fast_expansion_sum_zeroelim(fin
->other
, &fin
->length
, fin
->now
, fin
->length
, temp16a
, temp16a_len
);
870 swap
= fin
->now
; fin
->now
= fin
->other
; fin
->other
= swap
;
873 /* fin += a->x[0] * (bct * a->x[0] + bctt * (2.0f * a->x[1] + a->x[0])) */
874 d2d_fp_scale_expansion_zeroelim(temp32a
, &temp32a_len
, axt_bct
, axt_bct_len
, a
->x
[0]);
875 d2d_fp_scale_expansion_zeroelim(axt_bctt
, &axt_bctt_len
, bctt
, bctt_len
, a
->x
[0]);
876 d2d_fp_scale_expansion_zeroelim(temp16a
, &temp16a_len
, axt_bctt
, axt_bctt_len
, 2.0f
* a
->x
[1]);
877 d2d_fp_scale_expansion_zeroelim(temp16b
, &temp16b_len
, axt_bctt
, axt_bctt_len
, a
->x
[0]);
878 d2d_fp_fast_expansion_sum_zeroelim(temp32b
, &temp32b_len
, temp16a
, temp16a_len
, temp16b
, temp16b_len
);
879 d2d_fp_fast_expansion_sum_zeroelim(temp64
, &temp64_len
, temp32a
, temp32a_len
, temp32b
, temp32b_len
);
880 d2d_fp_fast_expansion_sum_zeroelim(fin
->other
, &fin
->length
, fin
->now
, fin
->length
, temp64
, temp64_len
);
881 swap
= fin
->now
; fin
->now
= fin
->other
; fin
->other
= swap
;
886 size_t ayt_bct_len
, ayt_bctt_len
;
887 float ayt_bct
[16], ayt_bctt
[8];
889 /* fin += a->y[0] * (ayt_det_bc + bct * 2.0f * a->y[1]) */
890 d2d_fp_scale_expansion_zeroelim(temp16a
, &temp16a_len
, ayt_det_bc
, ayt_det_bc_len
, a
->y
[0]);
891 d2d_fp_scale_expansion_zeroelim(ayt_bct
, &ayt_bct_len
, bct
, bct_len
, a
->y
[0]);
892 d2d_fp_scale_expansion_zeroelim(temp32a
, &temp32a_len
, ayt_bct
, ayt_bct_len
, 2.0f
* a
->y
[1]);
893 d2d_fp_fast_expansion_sum_zeroelim(temp48
, &temp48_len
, temp16a
, temp16a_len
, temp32a
, temp32a_len
);
894 d2d_fp_fast_expansion_sum_zeroelim(fin
->other
, &fin
->length
, fin
->now
, fin
->length
, temp48
, temp48_len
);
895 swap
= fin
->now
; fin
->now
= fin
->other
; fin
->other
= swap
;
897 /* fin += a->y[0] * (bct * a->y[0] + bctt * (2.0f * a->y[1] + a->y[0])) */
898 d2d_fp_scale_expansion_zeroelim(temp32a
, &temp32a_len
, ayt_bct
, ayt_bct_len
, a
->y
[0]);
899 d2d_fp_scale_expansion_zeroelim(ayt_bctt
, &ayt_bctt_len
, bctt
, bctt_len
, a
->y
[0]);
900 d2d_fp_scale_expansion_zeroelim(temp16a
, &temp16a_len
, ayt_bctt
, ayt_bctt_len
, 2.0f
* a
->y
[1]);
901 d2d_fp_scale_expansion_zeroelim(temp16b
, &temp16b_len
, ayt_bctt
, ayt_bctt_len
, a
->y
[0]);
902 d2d_fp_fast_expansion_sum_zeroelim(temp32b
, &temp32b_len
, temp16a
, temp16a_len
, temp16b
, temp16b_len
);
903 d2d_fp_fast_expansion_sum_zeroelim(temp64
, &temp64_len
, temp32a
, temp32a_len
, temp32b
, temp32b_len
);
904 d2d_fp_fast_expansion_sum_zeroelim(fin
->other
, &fin
->length
, fin
->now
, fin
->length
, temp64
, temp64_len
);
905 swap
= fin
->now
; fin
->now
= fin
->other
; fin
->other
= swap
;
909 /* Determine if point D is inside or outside the circle defined by points A,
910 * B, C. As explained in the paper by Guibas and Stolfi, this is equivalent to
911 * calculating the signed volume of the tetrahedron defined by projecting the
912 * points onto the paraboloid of revolution x = x² + y²,
913 * λ:(x, y) → (x, y, x² + y²). I.e., D is inside the cirlce if
920 * After translating D to the origin, that becomes:
926 * This implementation is based on the paper "Adaptive Precision
927 * Floating-Point Arithmetic and Fast Robust Geometric Predicates" and
928 * associated (Public Domain) code by Jonathan Richard Shewchuk. */
929 static BOOL
d2d_cdt_incircle(const struct d2d_cdt
*cdt
, size_t a
, size_t b
, size_t c
, size_t d
)
931 static const float err_bound_result
= (3.0f
+ 8.0f
* D2D_FP_EPS
) * D2D_FP_EPS
;
932 static const float err_bound_a
= (10.0f
+ 96.0f
* D2D_FP_EPS
) * D2D_FP_EPS
;
933 static const float err_bound_b
= (4.0f
+ 48.0f
* D2D_FP_EPS
) * D2D_FP_EPS
;
934 static const float err_bound_c
= (44.0f
+ 576.0f
* D2D_FP_EPS
) * D2D_FP_EPS
* D2D_FP_EPS
;
936 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
;
937 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];
938 float fin1
[1152], fin2
[1152], temp64
[64], sub_det_a
[32], sub_det_b
[32], sub_det_c
[32];
939 float det_bc
[4], det_ca
[4], det_ab
[4], daz
[4], dbz
[4], dcz
[4], temp2a
[2], temp2b
[2];
940 size_t temp64_len
, sub_det_a_len
, sub_det_b_len
, sub_det_c_len
;
941 float dbxdcy
, dbydcx
, dcxday
, dcydax
, daxdby
, daydbx
;
942 const D2D1_POINT_2F
*p
= cdt
->vertices
;
943 struct d2d_fp_two_vec2 da
, db
, dc
;
944 float permanent
, err_bound
, det
;
945 struct d2d_fp_fin fin
;
947 da
.x
[1] = p
[a
].x
- p
[d
].x
;
948 da
.y
[1] = p
[a
].y
- p
[d
].y
;
949 db
.x
[1] = p
[b
].x
- p
[d
].x
;
950 db
.y
[1] = p
[b
].y
- p
[d
].y
;
951 dc
.x
[1] = p
[c
].x
- p
[d
].x
;
952 dc
.y
[1] = p
[c
].y
- p
[d
].y
;
954 daz
[3] = da
.x
[1] * da
.x
[1] + da
.y
[1] * da
.y
[1];
955 dbxdcy
= db
.x
[1] * dc
.y
[1];
956 dbydcx
= db
.y
[1] * dc
.x
[1];
958 dbz
[3] = db
.x
[1] * db
.x
[1] + db
.y
[1] * db
.y
[1];
959 dcxday
= dc
.x
[1] * da
.y
[1];
960 dcydax
= dc
.y
[1] * da
.x
[1];
962 dcz
[3] = dc
.x
[1] * dc
.x
[1] + dc
.y
[1] * dc
.y
[1];
963 daxdby
= da
.x
[1] * db
.y
[1];
964 daydbx
= da
.y
[1] * db
.x
[1];
966 det
= daz
[3] * (dbxdcy
- dbydcx
) + dbz
[3] * (dcxday
- dcydax
) + dcz
[3] * (daxdby
- daydbx
);
967 permanent
= daz
[3] * (fabsf(dbxdcy
) + fabsf(dbydcx
))
968 + dbz
[3] * (fabsf(dcxday
) + fabsf(dcydax
))
969 + dcz
[3] * (fabsf(daxdby
) + fabsf(daydbx
));
970 err_bound
= err_bound_a
* permanent
;
971 if (det
> err_bound
|| -det
> err_bound
)
977 d2d_fp_four_det2x2(det_bc
, db
.x
[1], db
.y
[1], dc
.x
[1], dc
.y
[1]);
978 d2d_fp_sub_det3x3(sub_det_a
, &sub_det_a_len
, &da
, det_bc
);
980 d2d_fp_four_det2x2(det_ca
, dc
.x
[1], dc
.y
[1], da
.x
[1], da
.y
[1]);
981 d2d_fp_sub_det3x3(sub_det_b
, &sub_det_b_len
, &db
, det_ca
);
983 d2d_fp_four_det2x2(det_ab
, da
.x
[1], da
.y
[1], db
.x
[1], db
.y
[1]);
984 d2d_fp_sub_det3x3(sub_det_c
, &sub_det_c_len
, &dc
, det_ab
);
986 d2d_fp_fast_expansion_sum_zeroelim(temp64
, &temp64_len
, sub_det_a
, sub_det_a_len
, sub_det_b
, sub_det_b_len
);
987 d2d_fp_fast_expansion_sum_zeroelim(fin
.now
, &fin
.length
, temp64
, temp64_len
, sub_det_c
, sub_det_c_len
);
988 det
= d2d_fp_estimate(fin
.now
, fin
.length
);
989 err_bound
= err_bound_b
* permanent
;
990 if (det
>= err_bound
|| -det
>= err_bound
)
993 d2d_fp_two_diff_tail(&da
.x
[0], p
[a
].x
, p
[d
].x
, da
.x
[1]);
994 d2d_fp_two_diff_tail(&da
.y
[0], p
[a
].y
, p
[d
].y
, da
.y
[1]);
995 d2d_fp_two_diff_tail(&db
.x
[0], p
[b
].x
, p
[d
].x
, db
.x
[1]);
996 d2d_fp_two_diff_tail(&db
.y
[0], p
[b
].y
, p
[d
].y
, db
.y
[1]);
997 d2d_fp_two_diff_tail(&dc
.x
[0], p
[c
].x
, p
[d
].x
, dc
.x
[1]);
998 d2d_fp_two_diff_tail(&dc
.y
[0], p
[c
].y
, p
[d
].y
, dc
.y
[1]);
999 if (da
.x
[0] == 0.0f
&& db
.x
[0] == 0.0f
&& dc
.x
[0] == 0.0f
1000 && da
.y
[0] == 0.0f
&& db
.y
[0] == 0.0f
&& dc
.y
[0] == 0.0f
)
1003 err_bound
= err_bound_c
* permanent
+ err_bound_result
* fabsf(det
);
1004 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]))
1005 + 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]))
1006 + (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]))
1007 + 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]))
1008 + (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]))
1009 + 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]));
1010 if (det
>= err_bound
|| -det
>= err_bound
)
1013 if (db
.x
[0] != 0.0f
|| db
.y
[0] != 0.0f
|| dc
.x
[0] != 0.0f
|| dc
.y
[0] != 0.0f
)
1015 d2d_fp_square(temp2a
, da
.x
[1]);
1016 d2d_fp_square(temp2b
, da
.y
[1]);
1017 d2d_fp_two_two_sum(daz
, temp2a
, temp2b
);
1019 if (dc
.x
[0] != 0.0f
|| dc
.y
[0] != 0.0f
|| da
.x
[0] != 0.0f
|| da
.y
[0] != 0.0f
)
1021 d2d_fp_square(temp2a
, db
.x
[1]);
1022 d2d_fp_square(temp2b
, db
.y
[1]);
1023 d2d_fp_two_two_sum(dbz
, temp2a
, temp2b
);
1025 if (da
.x
[0] != 0.0f
|| da
.y
[0] != 0.0f
|| db
.x
[0] != 0.0f
|| db
.y
[0] != 0.0f
)
1027 d2d_fp_square(temp2a
, dc
.x
[1]);
1028 d2d_fp_square(temp2b
, dc
.y
[1]);
1029 d2d_fp_two_two_sum(dcz
, temp2a
, temp2b
);
1032 if (da
.x
[0] != 0.0f
)
1033 d2d_cdt_incircle_refine1(&fin
, axt_det_bc
, &axt_det_bc_len
, det_bc
, dc
.y
[1], dcz
, db
.y
[1], dbz
, da
.x
);
1034 if (da
.y
[0] != 0.0f
)
1035 d2d_cdt_incircle_refine1(&fin
, ayt_det_bc
, &ayt_det_bc_len
, det_bc
, db
.x
[1], dbz
, dc
.x
[1], dcz
, da
.y
);
1036 if (db
.x
[0] != 0.0f
)
1037 d2d_cdt_incircle_refine1(&fin
, bxt_det_ca
, &bxt_det_ca_len
, det_ca
, da
.y
[1], daz
, dc
.y
[1], dcz
, db
.x
);
1038 if (db
.y
[0] != 0.0f
)
1039 d2d_cdt_incircle_refine1(&fin
, byt_det_ca
, &byt_det_ca_len
, det_ca
, dc
.x
[1], dcz
, da
.x
[1], daz
, db
.y
);
1040 if (dc
.x
[0] != 0.0f
)
1041 d2d_cdt_incircle_refine1(&fin
, cxt_det_ab
, &cxt_det_ab_len
, det_ab
, db
.y
[1], dbz
, da
.y
[1], daz
, dc
.x
);
1042 if (dc
.y
[0] != 0.0f
)
1043 d2d_cdt_incircle_refine1(&fin
, cyt_det_ab
, &cyt_det_ab_len
, det_ab
, da
.x
[1], daz
, db
.x
[1], dbz
, dc
.y
);
1045 if (da
.x
[0] != 0.0f
|| da
.y
[0] != 0.0f
)
1046 d2d_cdt_incircle_refine2(&fin
, &da
, &db
, dbz
, &dc
, dcz
,
1047 axt_det_bc
, axt_det_bc_len
, ayt_det_bc
, ayt_det_bc_len
);
1048 if (db
.x
[0] != 0.0f
|| db
.y
[0] != 0.0f
)
1049 d2d_cdt_incircle_refine2(&fin
, &db
, &dc
, dcz
, &da
, daz
,
1050 bxt_det_ca
, bxt_det_ca_len
, byt_det_ca
, byt_det_ca_len
);
1051 if (dc
.x
[0] != 0.0f
|| dc
.y
[0] != 0.0f
)
1052 d2d_cdt_incircle_refine2(&fin
, &dc
, &da
, daz
, &db
, dbz
,
1053 cxt_det_ab
, cxt_det_ab_len
, cyt_det_ab
, cyt_det_ab_len
);
1055 return fin
.now
[fin
.length
- 1] > 0.0f
;
1058 static void d2d_cdt_splice(const struct d2d_cdt
*cdt
, const struct d2d_cdt_edge_ref
*a
,
1059 const struct d2d_cdt_edge_ref
*b
)
1061 struct d2d_cdt_edge_ref ta
, tb
, alpha
, beta
;
1063 ta
= cdt
->edges
[a
->idx
].next
[a
->r
];
1064 tb
= cdt
->edges
[b
->idx
].next
[b
->r
];
1065 cdt
->edges
[a
->idx
].next
[a
->r
] = tb
;
1066 cdt
->edges
[b
->idx
].next
[b
->r
] = ta
;
1068 d2d_cdt_edge_rot(&alpha
, &ta
);
1069 d2d_cdt_edge_rot(&beta
, &tb
);
1071 ta
= cdt
->edges
[alpha
.idx
].next
[alpha
.r
];
1072 tb
= cdt
->edges
[beta
.idx
].next
[beta
.r
];
1073 cdt
->edges
[alpha
.idx
].next
[alpha
.r
] = tb
;
1074 cdt
->edges
[beta
.idx
].next
[beta
.r
] = ta
;
1077 static BOOL
d2d_cdt_create_edge(struct d2d_cdt
*cdt
, struct d2d_cdt_edge_ref
*e
)
1079 struct d2d_cdt_edge
*edge
;
1081 if (cdt
->free_edge
!= ~0u)
1083 e
->idx
= cdt
->free_edge
;
1084 cdt
->free_edge
= cdt
->edges
[e
->idx
].next
[D2D_EDGE_NEXT_ORIGIN
].idx
;
1088 if (!d2d_array_reserve((void **)&cdt
->edges
, &cdt
->edges_size
, cdt
->edge_count
+ 1, sizeof(*cdt
->edges
)))
1090 ERR("Failed to grow edges array.\n");
1093 e
->idx
= cdt
->edge_count
++;
1097 edge
= &cdt
->edges
[e
->idx
];
1098 edge
->next
[D2D_EDGE_NEXT_ORIGIN
] = *e
;
1099 d2d_cdt_edge_tor(&edge
->next
[D2D_EDGE_NEXT_ROT
], e
);
1100 d2d_cdt_edge_sym(&edge
->next
[D2D_EDGE_NEXT_SYM
], e
);
1101 d2d_cdt_edge_rot(&edge
->next
[D2D_EDGE_NEXT_TOR
], e
);
1107 static void d2d_cdt_destroy_edge(struct d2d_cdt
*cdt
, const struct d2d_cdt_edge_ref
*e
)
1109 struct d2d_cdt_edge_ref next
, sym
, prev
;
1111 d2d_cdt_edge_next_origin(cdt
, &next
, e
);
1112 if (next
.idx
!= e
->idx
|| next
.r
!= e
->r
)
1114 d2d_cdt_edge_prev_origin(cdt
, &prev
, e
);
1115 d2d_cdt_splice(cdt
, e
, &prev
);
1118 d2d_cdt_edge_sym(&sym
, e
);
1120 d2d_cdt_edge_next_origin(cdt
, &next
, &sym
);
1121 if (next
.idx
!= sym
.idx
|| next
.r
!= sym
.r
)
1123 d2d_cdt_edge_prev_origin(cdt
, &prev
, &sym
);
1124 d2d_cdt_splice(cdt
, &sym
, &prev
);
1127 cdt
->edges
[e
->idx
].flags
|= D2D_CDT_EDGE_FLAG_FREED
;
1128 cdt
->edges
[e
->idx
].next
[D2D_EDGE_NEXT_ORIGIN
].idx
= cdt
->free_edge
;
1129 cdt
->free_edge
= e
->idx
;
1132 static BOOL
d2d_cdt_connect(struct d2d_cdt
*cdt
, struct d2d_cdt_edge_ref
*e
,
1133 const struct d2d_cdt_edge_ref
*a
, const struct d2d_cdt_edge_ref
*b
)
1135 struct d2d_cdt_edge_ref tmp
;
1137 if (!d2d_cdt_create_edge(cdt
, e
))
1139 d2d_cdt_edge_set_origin(cdt
, e
, d2d_cdt_edge_destination(cdt
, a
));
1140 d2d_cdt_edge_set_destination(cdt
, e
, d2d_cdt_edge_origin(cdt
, b
));
1141 d2d_cdt_edge_next_left(cdt
, &tmp
, a
);
1142 d2d_cdt_splice(cdt
, e
, &tmp
);
1143 d2d_cdt_edge_sym(&tmp
, e
);
1144 d2d_cdt_splice(cdt
, &tmp
, b
);
1149 static BOOL
d2d_cdt_merge(struct d2d_cdt
*cdt
, struct d2d_cdt_edge_ref
*left_outer
,
1150 struct d2d_cdt_edge_ref
*left_inner
, struct d2d_cdt_edge_ref
*right_inner
,
1151 struct d2d_cdt_edge_ref
*right_outer
)
1153 struct d2d_cdt_edge_ref base_edge
, tmp
;
1155 /* Create the base edge between both parts. */
1158 if (d2d_cdt_leftof(cdt
, d2d_cdt_edge_origin(cdt
, right_inner
), left_inner
))
1160 d2d_cdt_edge_next_left(cdt
, left_inner
, left_inner
);
1162 else if (d2d_cdt_rightof(cdt
, d2d_cdt_edge_origin(cdt
, left_inner
), right_inner
))
1164 d2d_cdt_edge_sym(&tmp
, right_inner
);
1165 d2d_cdt_edge_next_origin(cdt
, right_inner
, &tmp
);
1173 d2d_cdt_edge_sym(&tmp
, right_inner
);
1174 if (!d2d_cdt_connect(cdt
, &base_edge
, &tmp
, left_inner
))
1176 if (d2d_cdt_edge_origin(cdt
, left_inner
) == d2d_cdt_edge_origin(cdt
, left_outer
))
1177 d2d_cdt_edge_sym(left_outer
, &base_edge
);
1178 if (d2d_cdt_edge_origin(cdt
, right_inner
) == d2d_cdt_edge_origin(cdt
, right_outer
))
1179 *right_outer
= base_edge
;
1183 struct d2d_cdt_edge_ref left_candidate
, right_candidate
, sym_base_edge
;
1184 BOOL left_valid
, right_valid
;
1186 /* Find the left candidate. */
1187 d2d_cdt_edge_sym(&sym_base_edge
, &base_edge
);
1188 d2d_cdt_edge_next_origin(cdt
, &left_candidate
, &sym_base_edge
);
1189 if ((left_valid
= d2d_cdt_leftof(cdt
, d2d_cdt_edge_destination(cdt
, &left_candidate
), &sym_base_edge
)))
1191 d2d_cdt_edge_next_origin(cdt
, &tmp
, &left_candidate
);
1192 while (d2d_cdt_edge_destination(cdt
, &tmp
) != d2d_cdt_edge_destination(cdt
, &sym_base_edge
)
1193 && d2d_cdt_incircle(cdt
,
1194 d2d_cdt_edge_origin(cdt
, &sym_base_edge
), d2d_cdt_edge_destination(cdt
, &sym_base_edge
),
1195 d2d_cdt_edge_destination(cdt
, &left_candidate
), d2d_cdt_edge_destination(cdt
, &tmp
)))
1197 d2d_cdt_destroy_edge(cdt
, &left_candidate
);
1198 left_candidate
= tmp
;
1199 d2d_cdt_edge_next_origin(cdt
, &tmp
, &left_candidate
);
1202 d2d_cdt_edge_sym(&left_candidate
, &left_candidate
);
1204 /* Find the right candidate. */
1205 d2d_cdt_edge_prev_origin(cdt
, &right_candidate
, &base_edge
);
1206 if ((right_valid
= d2d_cdt_rightof(cdt
, d2d_cdt_edge_destination(cdt
, &right_candidate
), &base_edge
)))
1208 d2d_cdt_edge_prev_origin(cdt
, &tmp
, &right_candidate
);
1209 while (d2d_cdt_edge_destination(cdt
, &tmp
) != d2d_cdt_edge_destination(cdt
, &base_edge
)
1210 && d2d_cdt_incircle(cdt
,
1211 d2d_cdt_edge_origin(cdt
, &sym_base_edge
), d2d_cdt_edge_destination(cdt
, &sym_base_edge
),
1212 d2d_cdt_edge_destination(cdt
, &right_candidate
), d2d_cdt_edge_destination(cdt
, &tmp
)))
1214 d2d_cdt_destroy_edge(cdt
, &right_candidate
);
1215 right_candidate
= tmp
;
1216 d2d_cdt_edge_prev_origin(cdt
, &tmp
, &right_candidate
);
1220 if (!left_valid
&& !right_valid
)
1223 /* Connect the appropriate candidate with the base edge. */
1224 if (!left_valid
|| (right_valid
&& d2d_cdt_incircle(cdt
,
1225 d2d_cdt_edge_origin(cdt
, &left_candidate
), d2d_cdt_edge_destination(cdt
, &left_candidate
),
1226 d2d_cdt_edge_origin(cdt
, &right_candidate
), d2d_cdt_edge_destination(cdt
, &right_candidate
))))
1228 if (!d2d_cdt_connect(cdt
, &base_edge
, &right_candidate
, &sym_base_edge
))
1233 if (!d2d_cdt_connect(cdt
, &base_edge
, &sym_base_edge
, &left_candidate
))
1241 /* Create a Delaunay triangulation from a set of vertices. This is an
1242 * implementation of the divide-and-conquer algorithm described by Guibas and
1243 * Stolfi. Should be called with at least two vertices. */
1244 static BOOL
d2d_cdt_triangulate(struct d2d_cdt
*cdt
, size_t start_vertex
, size_t vertex_count
,
1245 struct d2d_cdt_edge_ref
*left_edge
, struct d2d_cdt_edge_ref
*right_edge
)
1247 struct d2d_cdt_edge_ref left_inner
, left_outer
, right_inner
, right_outer
, tmp
;
1250 /* Only two vertices, create a single edge. */
1251 if (vertex_count
== 2)
1253 struct d2d_cdt_edge_ref a
;
1255 if (!d2d_cdt_create_edge(cdt
, &a
))
1257 d2d_cdt_edge_set_origin(cdt
, &a
, start_vertex
);
1258 d2d_cdt_edge_set_destination(cdt
, &a
, start_vertex
+ 1);
1261 d2d_cdt_edge_sym(right_edge
, &a
);
1266 /* Three vertices, create a triangle. */
1267 if (vertex_count
== 3)
1269 struct d2d_cdt_edge_ref a
, b
, c
;
1272 if (!d2d_cdt_create_edge(cdt
, &a
))
1274 if (!d2d_cdt_create_edge(cdt
, &b
))
1276 d2d_cdt_edge_sym(&tmp
, &a
);
1277 d2d_cdt_splice(cdt
, &tmp
, &b
);
1279 d2d_cdt_edge_set_origin(cdt
, &a
, start_vertex
);
1280 d2d_cdt_edge_set_destination(cdt
, &a
, start_vertex
+ 1);
1281 d2d_cdt_edge_set_origin(cdt
, &b
, start_vertex
+ 1);
1282 d2d_cdt_edge_set_destination(cdt
, &b
, start_vertex
+ 2);
1284 det
= d2d_cdt_ccw(cdt
, start_vertex
, start_vertex
+ 1, start_vertex
+ 2);
1285 if (det
!= 0.0f
&& !d2d_cdt_connect(cdt
, &c
, &b
, &a
))
1290 d2d_cdt_edge_sym(left_edge
, &c
);
1296 d2d_cdt_edge_sym(right_edge
, &b
);
1302 /* More than tree vertices, divide. */
1303 cut
= vertex_count
/ 2;
1304 if (!d2d_cdt_triangulate(cdt
, start_vertex
, cut
, &left_outer
, &left_inner
))
1306 if (!d2d_cdt_triangulate(cdt
, start_vertex
+ cut
, vertex_count
- cut
, &right_inner
, &right_outer
))
1308 /* Merge the left and right parts. */
1309 if (!d2d_cdt_merge(cdt
, &left_outer
, &left_inner
, &right_inner
, &right_outer
))
1312 *left_edge
= left_outer
;
1313 *right_edge
= right_outer
;
1317 static int d2d_cdt_compare_vertices(const void *a
, const void *b
)
1319 const D2D1_POINT_2F
*p0
= a
;
1320 const D2D1_POINT_2F
*p1
= b
;
1321 float diff
= p0
->x
- p1
->x
;
1324 diff
= p0
->y
- p1
->y
;
1326 return diff
== 0.0f
? 0 : (diff
> 0.0f
? 1 : -1);
1329 /* Determine whether a given point is inside the geometry, using the current
1330 * fill mode rule. */
1331 static BOOL
d2d_path_geometry_point_inside(const struct d2d_geometry
*geometry
,
1332 const D2D1_POINT_2F
*probe
, BOOL triangles_only
)
1334 const D2D1_POINT_2F
*p0
, *p1
;
1335 D2D1_POINT_2F v_p
, v_probe
;
1339 for (i
= 0, score
= 0; i
< geometry
->u
.path
.figure_count
; ++i
)
1341 const struct d2d_figure
*figure
= &geometry
->u
.path
.figures
[i
];
1343 if (probe
->x
< figure
->bounds
.left
|| probe
->x
> figure
->bounds
.right
1344 || probe
->y
< figure
->bounds
.top
|| probe
->y
> figure
->bounds
.bottom
)
1347 last
= figure
->vertex_count
- 1;
1348 if (!triangles_only
)
1350 while (last
&& figure
->vertex_types
[last
] == D2D_VERTEX_TYPE_NONE
)
1353 p0
= &figure
->vertices
[last
];
1354 for (j
= 0; j
<= last
; ++j
)
1356 if (!triangles_only
&& figure
->vertex_types
[j
] == D2D_VERTEX_TYPE_NONE
)
1359 p1
= &figure
->vertices
[j
];
1360 d2d_point_subtract(&v_p
, p1
, p0
);
1361 d2d_point_subtract(&v_probe
, probe
, p0
);
1363 if ((probe
->y
< p0
->y
) != (probe
->y
< p1
->y
) && v_probe
.x
< v_p
.x
* (v_probe
.y
/ v_p
.y
))
1365 if (geometry
->u
.path
.fill_mode
== D2D1_FILL_MODE_ALTERNATE
|| (probe
->y
< p0
->y
))
1375 return geometry
->u
.path
.fill_mode
== D2D1_FILL_MODE_ALTERNATE
? score
& 1 : score
;
1378 static BOOL
d2d_path_geometry_add_fill_face(struct d2d_geometry
*geometry
, const struct d2d_cdt
*cdt
,
1379 const struct d2d_cdt_edge_ref
*base_edge
)
1381 struct d2d_cdt_edge_ref tmp
;
1382 struct d2d_face
*face
;
1383 D2D1_POINT_2F probe
;
1385 if (cdt
->edges
[base_edge
->idx
].flags
& D2D_CDT_EDGE_FLAG_VISITED(base_edge
->r
))
1388 if (!d2d_array_reserve((void **)&geometry
->fill
.faces
, &geometry
->fill
.faces_size
,
1389 geometry
->fill
.face_count
+ 1, sizeof(*geometry
->fill
.faces
)))
1391 ERR("Failed to grow faces array.\n");
1395 face
= &geometry
->fill
.faces
[geometry
->fill
.face_count
];
1397 /* It may seem tempting to use the center of the face as probe origin, but
1398 * multiplying by powers of two works much better for preserving accuracy. */
1401 cdt
->edges
[tmp
.idx
].flags
|= D2D_CDT_EDGE_FLAG_VISITED(tmp
.r
);
1402 face
->v
[0] = d2d_cdt_edge_origin(cdt
, &tmp
);
1403 probe
.x
= cdt
->vertices
[d2d_cdt_edge_origin(cdt
, &tmp
)].x
* 0.25f
;
1404 probe
.y
= cdt
->vertices
[d2d_cdt_edge_origin(cdt
, &tmp
)].y
* 0.25f
;
1406 d2d_cdt_edge_next_left(cdt
, &tmp
, &tmp
);
1407 cdt
->edges
[tmp
.idx
].flags
|= D2D_CDT_EDGE_FLAG_VISITED(tmp
.r
);
1408 face
->v
[1] = d2d_cdt_edge_origin(cdt
, &tmp
);
1409 probe
.x
+= cdt
->vertices
[d2d_cdt_edge_origin(cdt
, &tmp
)].x
* 0.25f
;
1410 probe
.y
+= cdt
->vertices
[d2d_cdt_edge_origin(cdt
, &tmp
)].y
* 0.25f
;
1412 d2d_cdt_edge_next_left(cdt
, &tmp
, &tmp
);
1413 cdt
->edges
[tmp
.idx
].flags
|= D2D_CDT_EDGE_FLAG_VISITED(tmp
.r
);
1414 face
->v
[2] = d2d_cdt_edge_origin(cdt
, &tmp
);
1415 probe
.x
+= cdt
->vertices
[d2d_cdt_edge_origin(cdt
, &tmp
)].x
* 0.50f
;
1416 probe
.y
+= cdt
->vertices
[d2d_cdt_edge_origin(cdt
, &tmp
)].y
* 0.50f
;
1418 if (d2d_cdt_leftof(cdt
, face
->v
[2], base_edge
) && d2d_path_geometry_point_inside(geometry
, &probe
, TRUE
))
1419 ++geometry
->fill
.face_count
;
1424 static BOOL
d2d_cdt_generate_faces(const struct d2d_cdt
*cdt
, struct d2d_geometry
*geometry
)
1426 struct d2d_cdt_edge_ref base_edge
;
1429 for (i
= 0; i
< cdt
->edge_count
; ++i
)
1431 if (cdt
->edges
[i
].flags
& D2D_CDT_EDGE_FLAG_FREED
)
1436 if (!d2d_path_geometry_add_fill_face(geometry
, cdt
, &base_edge
))
1438 d2d_cdt_edge_sym(&base_edge
, &base_edge
);
1439 if (!d2d_path_geometry_add_fill_face(geometry
, cdt
, &base_edge
))
1446 HeapFree(GetProcessHeap(), 0, geometry
->fill
.faces
);
1447 geometry
->fill
.faces
= NULL
;
1448 geometry
->fill
.faces_size
= 0;
1449 geometry
->fill
.face_count
= 0;
1453 static BOOL
d2d_cdt_fixup(struct d2d_cdt
*cdt
, const struct d2d_cdt_edge_ref
*base_edge
)
1455 struct d2d_cdt_edge_ref candidate
, next
, new_base
;
1456 unsigned int count
= 0;
1458 d2d_cdt_edge_next_left(cdt
, &next
, base_edge
);
1459 if (next
.idx
== base_edge
->idx
)
1461 ERR("Degenerate face.\n");
1466 while (d2d_cdt_edge_destination(cdt
, &next
) != d2d_cdt_edge_origin(cdt
, base_edge
))
1468 if (d2d_cdt_incircle(cdt
, d2d_cdt_edge_origin(cdt
, base_edge
), d2d_cdt_edge_destination(cdt
, base_edge
),
1469 d2d_cdt_edge_destination(cdt
, &candidate
), d2d_cdt_edge_destination(cdt
, &next
)))
1471 d2d_cdt_edge_next_left(cdt
, &next
, &next
);
1477 d2d_cdt_edge_next_left(cdt
, &next
, &candidate
);
1478 if (d2d_cdt_edge_destination(cdt
, &next
) == d2d_cdt_edge_origin(cdt
, base_edge
))
1479 d2d_cdt_edge_next_left(cdt
, &next
, base_edge
);
1482 if (!d2d_cdt_connect(cdt
, &new_base
, &candidate
, &next
))
1484 if (!d2d_cdt_fixup(cdt
, &new_base
))
1486 d2d_cdt_edge_sym(&new_base
, &new_base
);
1487 if (!d2d_cdt_fixup(cdt
, &new_base
))
1494 static void d2d_cdt_cut_edges(struct d2d_cdt
*cdt
, struct d2d_cdt_edge_ref
*end_edge
,
1495 const struct d2d_cdt_edge_ref
*base_edge
, size_t start_vertex
, size_t end_vertex
)
1497 struct d2d_cdt_edge_ref next
;
1500 d2d_cdt_edge_next_left(cdt
, &next
, base_edge
);
1501 if (d2d_cdt_edge_destination(cdt
, &next
) == end_vertex
)
1507 ccw
= d2d_cdt_ccw(cdt
, d2d_cdt_edge_destination(cdt
, &next
), end_vertex
, start_vertex
);
1515 d2d_cdt_edge_next_left(cdt
, &next
, &next
);
1517 d2d_cdt_edge_sym(&next
, &next
);
1518 d2d_cdt_cut_edges(cdt
, end_edge
, &next
, start_vertex
, end_vertex
);
1519 d2d_cdt_destroy_edge(cdt
, &next
);
1522 static BOOL
d2d_cdt_insert_segment(struct d2d_cdt
*cdt
, struct d2d_geometry
*geometry
,
1523 const struct d2d_cdt_edge_ref
*origin
, struct d2d_cdt_edge_ref
*edge
, size_t end_vertex
)
1525 struct d2d_cdt_edge_ref base_edge
, current
, new_origin
, next
, target
;
1526 size_t current_destination
, current_origin
;
1528 for (current
= *origin
;; current
= next
)
1530 d2d_cdt_edge_next_origin(cdt
, &next
, ¤t
);
1532 current_destination
= d2d_cdt_edge_destination(cdt
, ¤t
);
1533 if (current_destination
== end_vertex
)
1535 d2d_cdt_edge_sym(edge
, ¤t
);
1539 current_origin
= d2d_cdt_edge_origin(cdt
, ¤t
);
1540 if (d2d_cdt_ccw(cdt
, end_vertex
, current_origin
, current_destination
) == 0.0f
1541 && (cdt
->vertices
[current_destination
].x
> cdt
->vertices
[current_origin
].x
)
1542 == (cdt
->vertices
[end_vertex
].x
> cdt
->vertices
[current_origin
].x
)
1543 && (cdt
->vertices
[current_destination
].y
> cdt
->vertices
[current_origin
].y
)
1544 == (cdt
->vertices
[end_vertex
].y
> cdt
->vertices
[current_origin
].y
))
1546 d2d_cdt_edge_sym(&new_origin
, ¤t
);
1547 return d2d_cdt_insert_segment(cdt
, geometry
, &new_origin
, edge
, end_vertex
);
1550 if (d2d_cdt_rightof(cdt
, end_vertex
, &next
) && d2d_cdt_leftof(cdt
, end_vertex
, ¤t
))
1552 d2d_cdt_edge_next_left(cdt
, &base_edge
, ¤t
);
1554 d2d_cdt_edge_sym(&base_edge
, &base_edge
);
1555 d2d_cdt_cut_edges(cdt
, &target
, &base_edge
, d2d_cdt_edge_origin(cdt
, origin
), end_vertex
);
1556 d2d_cdt_destroy_edge(cdt
, &base_edge
);
1558 if (!d2d_cdt_connect(cdt
, &base_edge
, &target
, ¤t
))
1561 if (!d2d_cdt_fixup(cdt
, &base_edge
))
1563 d2d_cdt_edge_sym(&base_edge
, &base_edge
);
1564 if (!d2d_cdt_fixup(cdt
, &base_edge
))
1567 if (d2d_cdt_edge_origin(cdt
, edge
) == end_vertex
)
1570 return d2d_cdt_insert_segment(cdt
, geometry
, &new_origin
, edge
, end_vertex
);
1573 if (next
.idx
== origin
->idx
)
1575 ERR("Triangle not found.\n");
1581 static BOOL
d2d_cdt_insert_segments(struct d2d_cdt
*cdt
, struct d2d_geometry
*geometry
)
1583 size_t start_vertex
, end_vertex
, i
, j
, k
;
1584 struct d2d_cdt_edge_ref edge
, new_edge
;
1585 const struct d2d_figure
*figure
;
1586 const D2D1_POINT_2F
*p
;
1589 for (i
= 0; i
< geometry
->u
.path
.figure_count
; ++i
)
1591 figure
= &geometry
->u
.path
.figures
[i
];
1593 /* Degenerate figure. */
1594 if (figure
->vertex_count
< 2)
1597 p
= bsearch(&figure
->vertices
[figure
->vertex_count
- 1], cdt
->vertices
,
1598 geometry
->fill
.vertex_count
, sizeof(*p
), d2d_cdt_compare_vertices
);
1599 start_vertex
= p
- cdt
->vertices
;
1601 for (k
= 0, found
= FALSE
; k
< cdt
->edge_count
; ++k
)
1603 if (cdt
->edges
[k
].flags
& D2D_CDT_EDGE_FLAG_FREED
)
1609 if (d2d_cdt_edge_origin(cdt
, &edge
) == start_vertex
)
1614 d2d_cdt_edge_sym(&edge
, &edge
);
1615 if (d2d_cdt_edge_origin(cdt
, &edge
) == start_vertex
)
1624 ERR("Edge not found.\n");
1628 for (j
= 0; j
< figure
->vertex_count
; start_vertex
= end_vertex
, ++j
)
1630 p
= bsearch(&figure
->vertices
[j
], cdt
->vertices
,
1631 geometry
->fill
.vertex_count
, sizeof(*p
), d2d_cdt_compare_vertices
);
1632 end_vertex
= p
- cdt
->vertices
;
1634 if (start_vertex
== end_vertex
)
1637 if (!d2d_cdt_insert_segment(cdt
, geometry
, &edge
, &new_edge
, end_vertex
))
1646 static BOOL
d2d_geometry_intersections_add(struct d2d_geometry_intersections
*i
,
1647 const struct d2d_segment_idx
*segment_idx
, float t
, D2D1_POINT_2F p
)
1649 struct d2d_geometry_intersection
*intersection
;
1651 if (!d2d_array_reserve((void **)&i
->intersections
, &i
->intersections_size
,
1652 i
->intersection_count
+ 1, sizeof(*i
->intersections
)))
1654 ERR("Failed to grow intersections array.\n");
1658 intersection
= &i
->intersections
[i
->intersection_count
++];
1659 intersection
->figure_idx
= segment_idx
->figure_idx
;
1660 intersection
->vertex_idx
= segment_idx
->vertex_idx
;
1661 intersection
->control_idx
= segment_idx
->control_idx
;
1662 intersection
->t
= t
;
1663 intersection
->p
= p
;
1668 static int d2d_geometry_intersections_compare(const void *a
, const void *b
)
1670 const struct d2d_geometry_intersection
*i0
= a
;
1671 const struct d2d_geometry_intersection
*i1
= b
;
1673 if (i0
->figure_idx
!= i1
->figure_idx
)
1674 return i0
->figure_idx
- i1
->figure_idx
;
1675 if (i0
->vertex_idx
!= i1
->vertex_idx
)
1676 return i0
->vertex_idx
- i1
->vertex_idx
;
1678 return i0
->t
> i1
->t
? 1 : -1;
1682 static BOOL
d2d_geometry_intersect_line_line(struct d2d_geometry
*geometry
,
1683 struct d2d_geometry_intersections
*intersections
, const struct d2d_segment_idx
*idx_p
,
1684 const struct d2d_segment_idx
*idx_q
)
1686 D2D1_POINT_2F v_p
, v_q
, v_qp
, intersection
;
1687 const D2D1_POINT_2F
*p
[2], *q
[2];
1688 const struct d2d_figure
*figure
;
1692 figure
= &geometry
->u
.path
.figures
[idx_p
->figure_idx
];
1693 p
[0] = &figure
->vertices
[idx_p
->vertex_idx
];
1694 next
= idx_p
->vertex_idx
+ 1;
1695 if (next
== figure
->vertex_count
)
1697 p
[1] = &figure
->vertices
[next
];
1699 figure
= &geometry
->u
.path
.figures
[idx_q
->figure_idx
];
1700 q
[0] = &figure
->vertices
[idx_q
->vertex_idx
];
1701 next
= idx_q
->vertex_idx
+ 1;
1702 if (next
== figure
->vertex_count
)
1704 q
[1] = &figure
->vertices
[next
];
1706 d2d_point_subtract(&v_p
, p
[1], p
[0]);
1707 d2d_point_subtract(&v_q
, q
[1], q
[0]);
1708 d2d_point_subtract(&v_qp
, p
[0], q
[0]);
1710 det
= v_p
.x
* v_q
.y
- v_p
.y
* v_q
.x
;
1714 s
= (v_q
.x
* v_qp
.y
- v_q
.y
* v_qp
.x
) / det
;
1715 t
= (v_p
.x
* v_qp
.y
- v_p
.y
* v_qp
.x
) / det
;
1717 if (s
< 0.0f
|| s
> 1.0f
|| t
< 0.0f
|| t
> 1.0f
)
1720 intersection
.x
= p
[0]->x
+ v_p
.x
* s
;
1721 intersection
.y
= p
[0]->y
+ v_p
.y
* s
;
1723 if (s
> 0.0f
&& s
< 1.0f
&& !d2d_geometry_intersections_add(intersections
, idx_p
, s
, intersection
))
1726 if (t
> 0.0f
&& t
< 1.0f
&& !d2d_geometry_intersections_add(intersections
, idx_q
, t
, intersection
))
1732 static BOOL
d2d_geometry_add_bezier_line_intersections(struct d2d_geometry
*geometry
,
1733 struct d2d_geometry_intersections
*intersections
, const struct d2d_segment_idx
*idx_p
,
1734 const D2D1_POINT_2F
**p
, const struct d2d_segment_idx
*idx_q
, const D2D1_POINT_2F
**q
, float s
)
1736 D2D1_POINT_2F intersection
;
1739 d2d_point_calculate_bezier(&intersection
, p
[0], p
[1], p
[2], s
);
1740 if (fabsf(q
[1]->x
- q
[0]->x
) > fabsf(q
[1]->y
- q
[0]->y
))
1741 t
= (intersection
.x
- q
[0]->x
) / (q
[1]->x
- q
[0]->x
);
1743 t
= (intersection
.y
- q
[0]->y
) / (q
[1]->y
- q
[0]->y
);
1744 if (t
< 0.0f
|| t
> 1.0f
)
1747 d2d_point_lerp(&intersection
, q
[0], q
[1], t
);
1749 if (s
> 0.0f
&& s
< 1.0f
&& !d2d_geometry_intersections_add(intersections
, idx_p
, s
, intersection
))
1752 if (t
> 0.0f
&& t
< 1.0f
&& !d2d_geometry_intersections_add(intersections
, idx_q
, t
, intersection
))
1758 static BOOL
d2d_geometry_intersect_bezier_line(struct d2d_geometry
*geometry
,
1759 struct d2d_geometry_intersections
*intersections
,
1760 const struct d2d_segment_idx
*idx_p
, const struct d2d_segment_idx
*idx_q
)
1762 const D2D1_POINT_2F
*p
[3], *q
[2];
1763 const struct d2d_figure
*figure
;
1764 float y
[3], root
, theta
, d
, e
;
1767 figure
= &geometry
->u
.path
.figures
[idx_p
->figure_idx
];
1768 p
[0] = &figure
->vertices
[idx_p
->vertex_idx
];
1769 p
[1] = &figure
->bezier_controls
[idx_p
->control_idx
];
1770 next
= idx_p
->vertex_idx
+ 1;
1771 if (next
== figure
->vertex_count
)
1773 p
[2] = &figure
->vertices
[next
];
1775 figure
= &geometry
->u
.path
.figures
[idx_q
->figure_idx
];
1776 q
[0] = &figure
->vertices
[idx_q
->vertex_idx
];
1777 next
= idx_q
->vertex_idx
+ 1;
1778 if (next
== figure
->vertex_count
)
1780 q
[1] = &figure
->vertices
[next
];
1782 /* Align the line with x-axis. */
1783 theta
= -atan2f(q
[1]->y
- q
[0]->y
, q
[1]->x
- q
[0]->x
);
1784 y
[0] = (p
[0]->x
- q
[0]->x
) * sinf(theta
) + (p
[0]->y
- q
[0]->y
) * cosf(theta
);
1785 y
[1] = (p
[1]->x
- q
[0]->x
) * sinf(theta
) + (p
[1]->y
- q
[0]->y
) * cosf(theta
);
1786 y
[2] = (p
[2]->x
- q
[0]->x
) * sinf(theta
) + (p
[2]->y
- q
[0]->y
) * cosf(theta
);
1788 /* Intersect the transformed curve with the x-axis.
1790 * f(t) = (1 - t)²P₀ + 2(1 - t)tP₁ + t²P₂
1791 * = (P₀ - 2P₁ + P₂)t² + 2(P₁ - P₀)t + P₀
1798 * t = (-b ± √(b² - 4ac)) / 2a
1799 * = (-2(P₁ - P₀) ± √((2(P₁ - P₀))² - 4((P₀ - 2P₁ + P₂)P₀))) / 2(P₀ - 2P₁ + P₂)
1800 * = (2P₀ - 2P₁ ± √(4P₀² + 4P₁² - 8P₀P₁ - 4P₀² + 8P₀P₁ - 4P₀P₂)) / (2P₀ - 4P₁ + 2P₂)
1801 * = (P₀ - P₁ ± √(P₁² - P₀P₂)) / (P₀ - 2P₁ + P₂) */
1803 d
= y
[0] - 2 * y
[1] + y
[2];
1806 /* P₀ - 2P₁ + P₂ = 0
1807 * f(t) = (P₀ - 2P₁ + P₂)t² + 2(P₁ - P₀)t + P₀ = 0
1808 * t = -P₀ / 2(P₁ - P₀) */
1809 root
= -y
[0] / (2.0f
* (y
[1] - y
[0]));
1810 if (root
< 0.0f
|| root
> 1.0f
)
1813 return d2d_geometry_add_bezier_line_intersections(geometry
, intersections
, idx_p
, p
, idx_q
, q
, root
);
1816 e
= y
[1] * y
[1] - y
[0] * y
[2];
1820 root
= (y
[0] - y
[1] + sqrtf(e
)) / d
;
1821 if (root
>= 0.0f
&& root
<= 1.0f
&& !d2d_geometry_add_bezier_line_intersections(geometry
,
1822 intersections
, idx_p
, p
, idx_q
, q
, root
))
1825 root
= (y
[0] - y
[1] - sqrtf(e
)) / d
;
1826 if (root
>= 0.0f
&& root
<= 1.0f
&& !d2d_geometry_add_bezier_line_intersections(geometry
,
1827 intersections
, idx_p
, p
, idx_q
, q
, root
))
1833 static BOOL
d2d_geometry_intersect_bezier_bezier(struct d2d_geometry
*geometry
,
1834 struct d2d_geometry_intersections
*intersections
,
1835 const struct d2d_segment_idx
*idx_p
, float start_p
, float end_p
,
1836 const struct d2d_segment_idx
*idx_q
, float start_q
, float end_q
)
1838 const D2D1_POINT_2F
*p
[3], *q
[3];
1839 const struct d2d_figure
*figure
;
1840 D2D_RECT_F p_bounds
, q_bounds
;
1841 D2D1_POINT_2F intersection
;
1842 float centre_p
, centre_q
;
1845 figure
= &geometry
->u
.path
.figures
[idx_p
->figure_idx
];
1846 p
[0] = &figure
->vertices
[idx_p
->vertex_idx
];
1847 p
[1] = &figure
->bezier_controls
[idx_p
->control_idx
];
1848 next
= idx_p
->vertex_idx
+ 1;
1849 if (next
== figure
->vertex_count
)
1851 p
[2] = &figure
->vertices
[next
];
1853 figure
= &geometry
->u
.path
.figures
[idx_q
->figure_idx
];
1854 q
[0] = &figure
->vertices
[idx_q
->vertex_idx
];
1855 q
[1] = &figure
->bezier_controls
[idx_q
->control_idx
];
1856 next
= idx_q
->vertex_idx
+ 1;
1857 if (next
== figure
->vertex_count
)
1859 q
[2] = &figure
->vertices
[next
];
1861 d2d_rect_get_bezier_segment_bounds(&p_bounds
, p
[0], p
[1], p
[2], start_p
, end_p
);
1862 d2d_rect_get_bezier_segment_bounds(&q_bounds
, q
[0], q
[1], q
[2], start_q
, end_q
);
1864 if (!d2d_rect_check_overlap(&p_bounds
, &q_bounds
))
1867 centre_p
= (start_p
+ end_p
) / 2.0f
;
1868 centre_q
= (start_q
+ end_q
) / 2.0f
;
1870 if (end_p
- start_p
< 1e-3f
)
1872 d2d_point_calculate_bezier(&intersection
, p
[0], p
[1], p
[2], centre_p
);
1873 if (start_p
> 0.0f
&& end_p
< 1.0f
&& !d2d_geometry_intersections_add(intersections
,
1874 idx_p
, centre_p
, intersection
))
1876 if (start_q
> 0.0f
&& end_q
< 1.0f
&& !d2d_geometry_intersections_add(intersections
,
1877 idx_q
, centre_q
, intersection
))
1882 if (!d2d_geometry_intersect_bezier_bezier(geometry
, intersections
,
1883 idx_p
, start_p
, centre_p
, idx_q
, start_q
, centre_q
))
1885 if (!d2d_geometry_intersect_bezier_bezier(geometry
, intersections
,
1886 idx_p
, start_p
, centre_p
, idx_q
, centre_q
, end_q
))
1888 if (!d2d_geometry_intersect_bezier_bezier(geometry
, intersections
,
1889 idx_p
, centre_p
, end_p
, idx_q
, start_q
, centre_q
))
1891 if (!d2d_geometry_intersect_bezier_bezier(geometry
, intersections
,
1892 idx_p
, centre_p
, end_p
, idx_q
, centre_q
, end_q
))
1898 static BOOL
d2d_geometry_apply_intersections(struct d2d_geometry
*geometry
,
1899 struct d2d_geometry_intersections
*intersections
)
1901 size_t vertex_offset
, control_offset
, next
, i
;
1902 struct d2d_geometry_intersection
*inter
;
1903 enum d2d_vertex_type vertex_type
;
1904 const D2D1_POINT_2F
*p
[3];
1905 struct d2d_figure
*figure
;
1909 for (i
= 0; i
< intersections
->intersection_count
; ++i
)
1911 inter
= &intersections
->intersections
[i
];
1912 if (!i
|| inter
->figure_idx
!= intersections
->intersections
[i
- 1].figure_idx
)
1913 vertex_offset
= control_offset
= 0;
1915 figure
= &geometry
->u
.path
.figures
[inter
->figure_idx
];
1916 vertex_type
= figure
->vertex_types
[inter
->vertex_idx
+ vertex_offset
];
1917 if (vertex_type
!= D2D_VERTEX_TYPE_BEZIER
&& vertex_type
!= D2D_VERTEX_TYPE_SPLIT_BEZIER
)
1919 if (!d2d_figure_insert_vertex(&geometry
->u
.path
.figures
[inter
->figure_idx
],
1920 inter
->vertex_idx
+ vertex_offset
+ 1, inter
->p
))
1927 if (i
&& inter
->figure_idx
== intersections
->intersections
[i
- 1].figure_idx
1928 && inter
->vertex_idx
== intersections
->intersections
[i
- 1].vertex_idx
)
1930 t_prev
= intersections
->intersections
[i
- 1].t
;
1931 if (t
- t_prev
< 1e-3f
)
1933 inter
->t
= intersections
->intersections
[i
- 1].t
;
1936 t
= (t
- t_prev
) / (1.0f
- t_prev
);
1939 p
[0] = &figure
->vertices
[inter
->vertex_idx
+ vertex_offset
];
1940 p
[1] = &figure
->bezier_controls
[inter
->control_idx
+ control_offset
];
1941 next
= inter
->vertex_idx
+ vertex_offset
+ 1;
1942 if (next
== figure
->vertex_count
)
1944 p
[2] = &figure
->vertices
[next
];
1946 d2d_point_lerp(&q
[0], p
[0], p
[1], t
);
1947 d2d_point_lerp(&q
[1], p
[1], p
[2], t
);
1949 figure
->bezier_controls
[inter
->control_idx
+ control_offset
] = q
[0];
1950 if (!(d2d_figure_insert_bezier_control(figure
, inter
->control_idx
+ control_offset
+ 1, &q
[1])))
1954 if (!(d2d_figure_insert_vertex(figure
, inter
->vertex_idx
+ vertex_offset
+ 1, inter
->p
)))
1956 figure
->vertex_types
[inter
->vertex_idx
+ vertex_offset
+ 1] = D2D_VERTEX_TYPE_SPLIT_BEZIER
;
1963 /* Intersect the geometry's segments with themselves. This uses the
1964 * straightforward approach of testing everything against everything, but
1965 * there certainly exist more scalable algorithms for this. */
1966 static BOOL
d2d_geometry_intersect_self(struct d2d_geometry
*geometry
)
1968 struct d2d_geometry_intersections intersections
= {0};
1969 const struct d2d_figure
*figure_p
, *figure_q
;
1970 struct d2d_segment_idx idx_p
, idx_q
;
1971 enum d2d_vertex_type type_p
, type_q
;
1975 if (!geometry
->u
.path
.figure_count
)
1978 for (idx_p
.figure_idx
= 0; idx_p
.figure_idx
< geometry
->u
.path
.figure_count
; ++idx_p
.figure_idx
)
1980 figure_p
= &geometry
->u
.path
.figures
[idx_p
.figure_idx
];
1981 idx_p
.control_idx
= 0;
1982 for (idx_p
.vertex_idx
= 0; idx_p
.vertex_idx
< figure_p
->vertex_count
; ++idx_p
.vertex_idx
)
1984 type_p
= figure_p
->vertex_types
[idx_p
.vertex_idx
];
1985 for (idx_q
.figure_idx
= 0; idx_q
.figure_idx
<= idx_p
.figure_idx
; ++idx_q
.figure_idx
)
1987 figure_q
= &geometry
->u
.path
.figures
[idx_q
.figure_idx
];
1988 if (idx_q
.figure_idx
!= idx_p
.figure_idx
)
1990 if (!d2d_rect_check_overlap(&figure_p
->bounds
, &figure_q
->bounds
))
1992 max_q
= figure_q
->vertex_count
;
1996 max_q
= idx_p
.vertex_idx
;
1999 idx_q
.control_idx
= 0;
2000 for (idx_q
.vertex_idx
= 0; idx_q
.vertex_idx
< max_q
; ++idx_q
.vertex_idx
)
2002 type_q
= figure_q
->vertex_types
[idx_q
.vertex_idx
];
2003 if (type_q
== D2D_VERTEX_TYPE_BEZIER
)
2005 if (type_p
== D2D_VERTEX_TYPE_BEZIER
)
2007 if (!d2d_geometry_intersect_bezier_bezier(geometry
, &intersections
,
2008 &idx_p
, 0.0f
, 1.0f
, &idx_q
, 0.0f
, 1.0f
))
2013 if (!d2d_geometry_intersect_bezier_line(geometry
, &intersections
, &idx_q
, &idx_p
))
2016 ++idx_q
.control_idx
;
2020 if (type_p
== D2D_VERTEX_TYPE_BEZIER
)
2022 if (!d2d_geometry_intersect_bezier_line(geometry
, &intersections
, &idx_p
, &idx_q
))
2027 if (!d2d_geometry_intersect_line_line(geometry
, &intersections
, &idx_p
, &idx_q
))
2033 if (type_p
== D2D_VERTEX_TYPE_BEZIER
)
2034 ++idx_p
.control_idx
;
2038 qsort(intersections
.intersections
, intersections
.intersection_count
,
2039 sizeof(*intersections
.intersections
), d2d_geometry_intersections_compare
);
2040 ret
= d2d_geometry_apply_intersections(geometry
, &intersections
);
2043 HeapFree(GetProcessHeap(), 0, intersections
.intersections
);
2047 static HRESULT
d2d_path_geometry_triangulate(struct d2d_geometry
*geometry
)
2049 struct d2d_cdt_edge_ref left_edge
, right_edge
;
2050 size_t vertex_count
, i
, j
;
2051 struct d2d_cdt cdt
= {0};
2052 D2D1_POINT_2F
*vertices
;
2054 for (i
= 0, vertex_count
= 0; i
< geometry
->u
.path
.figure_count
; ++i
)
2056 vertex_count
+= geometry
->u
.path
.figures
[i
].vertex_count
;
2059 if (vertex_count
< 3)
2061 WARN("Geometry has %lu vertices.\n", (long)vertex_count
);
2065 if (!(vertices
= HeapAlloc(GetProcessHeap(), 0, vertex_count
* sizeof(*vertices
))))
2066 return E_OUTOFMEMORY
;
2068 for (i
= 0, j
= 0; i
< geometry
->u
.path
.figure_count
; ++i
)
2070 memcpy(&vertices
[j
], geometry
->u
.path
.figures
[i
].vertices
,
2071 geometry
->u
.path
.figures
[i
].vertex_count
* sizeof(*vertices
));
2072 j
+= geometry
->u
.path
.figures
[i
].vertex_count
;
2075 /* Sort vertices, eliminate duplicates. */
2076 qsort(vertices
, vertex_count
, sizeof(*vertices
), d2d_cdt_compare_vertices
);
2077 for (i
= 1; i
< vertex_count
; ++i
)
2079 if (!memcmp(&vertices
[i
- 1], &vertices
[i
], sizeof(*vertices
)))
2082 memmove(&vertices
[i
], &vertices
[i
+ 1], (vertex_count
- i
) * sizeof(*vertices
));
2087 geometry
->fill
.vertices
= vertices
;
2088 geometry
->fill
.vertex_count
= vertex_count
;
2090 cdt
.free_edge
= ~0u;
2091 cdt
.vertices
= vertices
;
2092 if (!d2d_cdt_triangulate(&cdt
, 0, vertex_count
, &left_edge
, &right_edge
))
2094 if (!d2d_cdt_insert_segments(&cdt
, geometry
))
2096 if (!d2d_cdt_generate_faces(&cdt
, geometry
))
2099 HeapFree(GetProcessHeap(), 0, cdt
.edges
);
2103 geometry
->fill
.vertices
= NULL
;
2104 geometry
->fill
.vertex_count
= 0;
2105 HeapFree(GetProcessHeap(), 0, vertices
);
2106 HeapFree(GetProcessHeap(), 0, cdt
.edges
);
2110 static BOOL
d2d_path_geometry_add_figure(struct d2d_geometry
*geometry
)
2112 struct d2d_figure
*figure
;
2114 if (!d2d_array_reserve((void **)&geometry
->u
.path
.figures
, &geometry
->u
.path
.figures_size
,
2115 geometry
->u
.path
.figure_count
+ 1, sizeof(*geometry
->u
.path
.figures
)))
2117 ERR("Failed to grow figures array.\n");
2121 figure
= &geometry
->u
.path
.figures
[geometry
->u
.path
.figure_count
];
2122 memset(figure
, 0, sizeof(*figure
));
2123 figure
->bounds
.left
= FLT_MAX
;
2124 figure
->bounds
.top
= FLT_MAX
;
2125 figure
->bounds
.right
= -FLT_MAX
;
2126 figure
->bounds
.bottom
= -FLT_MAX
;
2128 ++geometry
->u
.path
.figure_count
;
2132 static BOOL
d2d_geometry_outline_add_join(struct d2d_geometry
*geometry
,
2133 const D2D1_POINT_2F
*prev
, const D2D1_POINT_2F
*p0
, const D2D1_POINT_2F
*next
)
2135 D2D1_POINT_2F q_prev
, q_next
;
2136 struct d2d_outline_vertex
*v
;
2141 if (!d2d_array_reserve((void **)&geometry
->outline
.vertices
, &geometry
->outline
.vertices_size
,
2142 geometry
->outline
.vertex_count
+ 4, sizeof(*geometry
->outline
.vertices
)))
2144 ERR("Failed to grow outline vertices array.\n");
2147 base_idx
= geometry
->outline
.vertex_count
;
2148 v
= &geometry
->outline
.vertices
[base_idx
];
2150 if (!d2d_array_reserve((void **)&geometry
->outline
.faces
, &geometry
->outline
.faces_size
,
2151 geometry
->outline
.face_count
+ 2, sizeof(*geometry
->outline
.faces
)))
2153 ERR("Failed to grow outline faces array.\n");
2156 f
= &geometry
->outline
.faces
[geometry
->outline
.face_count
];
2158 d2d_point_subtract(&q_prev
, p0
, prev
);
2159 d2d_point_subtract(&q_next
, next
, p0
);
2161 d2d_point_normalise(&q_prev
);
2162 d2d_point_normalise(&q_next
);
2164 ccw
= d2d_point_ccw(p0
, prev
, next
);
2167 d2d_outline_vertex_set(&v
[0], p0
->x
, p0
->y
, q_prev
.x
, q_prev
.y
, q_prev
.x
, q_prev
.y
);
2168 d2d_outline_vertex_set(&v
[1], p0
->x
, p0
->y
, -q_prev
.x
, -q_prev
.y
, -q_prev
.x
, -q_prev
.y
);
2169 d2d_outline_vertex_set(&v
[2], p0
->x
+ 25.0f
* q_prev
.x
, p0
->y
+ 25.0f
* q_prev
.y
,
2170 -q_prev
.x
, -q_prev
.y
, -q_prev
.x
, -q_prev
.y
);
2171 d2d_outline_vertex_set(&v
[3], p0
->x
+ 25.0f
* q_prev
.x
, p0
->y
+ 25.0f
* q_prev
.y
,
2172 q_prev
.x
, q_prev
.y
, q_prev
.x
, q_prev
.y
);
2174 else if (ccw
< 0.0f
)
2176 d2d_outline_vertex_set(&v
[0], p0
->x
, p0
->y
, 0.0f
, 0.0f
, 0.0f
, 0.0f
);
2177 d2d_outline_vertex_set(&v
[1], p0
->x
, p0
->y
, -q_next
.x
, -q_next
.y
, -q_next
.x
, -q_next
.y
);
2178 d2d_outline_vertex_set(&v
[2], p0
->x
, p0
->y
, -q_next
.x
, -q_next
.y
, -q_prev
.x
, -q_prev
.y
);
2179 d2d_outline_vertex_set(&v
[3], p0
->x
, p0
->y
, -q_prev
.x
, -q_prev
.y
, -q_prev
.x
, -q_prev
.y
);
2183 d2d_outline_vertex_set(&v
[0], p0
->x
, p0
->y
, 0.0f
, 0.0f
, 0.0f
, 0.0f
);
2184 d2d_outline_vertex_set(&v
[1], p0
->x
, p0
->y
, q_prev
.x
, q_prev
.y
, q_prev
.x
, q_prev
.y
);
2185 d2d_outline_vertex_set(&v
[2], p0
->x
, p0
->y
, q_prev
.x
, q_prev
.y
, q_next
.x
, q_next
.y
);
2186 d2d_outline_vertex_set(&v
[3], p0
->x
, p0
->y
, q_next
.x
, q_next
.y
, q_next
.x
, q_next
.y
);
2188 geometry
->outline
.vertex_count
+= 4;
2190 d2d_face_set(&f
[0], base_idx
+ 1, base_idx
+ 0, base_idx
+ 2);
2191 d2d_face_set(&f
[1], base_idx
+ 2, base_idx
+ 0, base_idx
+ 3);
2192 geometry
->outline
.face_count
+= 2;
2197 static BOOL
d2d_geometry_outline_add_line_segment(struct d2d_geometry
*geometry
,
2198 const D2D1_POINT_2F
*p0
, const D2D1_POINT_2F
*next
)
2200 struct d2d_outline_vertex
*v
;
2201 D2D1_POINT_2F q_next
;
2205 if (!d2d_array_reserve((void **)&geometry
->outline
.vertices
, &geometry
->outline
.vertices_size
,
2206 geometry
->outline
.vertex_count
+ 4, sizeof(*geometry
->outline
.vertices
)))
2208 ERR("Failed to grow outline vertices array.\n");
2211 base_idx
= geometry
->outline
.vertex_count
;
2212 v
= &geometry
->outline
.vertices
[base_idx
];
2214 if (!d2d_array_reserve((void **)&geometry
->outline
.faces
, &geometry
->outline
.faces_size
,
2215 geometry
->outline
.face_count
+ 2, sizeof(*geometry
->outline
.faces
)))
2217 ERR("Failed to grow outline faces array.\n");
2220 f
= &geometry
->outline
.faces
[geometry
->outline
.face_count
];
2222 d2d_point_subtract(&q_next
, next
, p0
);
2223 d2d_point_normalise(&q_next
);
2225 d2d_outline_vertex_set(&v
[0], p0
->x
, p0
->y
, q_next
.x
, q_next
.y
, q_next
.x
, q_next
.y
);
2226 d2d_outline_vertex_set(&v
[1], p0
->x
, p0
->y
, -q_next
.x
, -q_next
.y
, -q_next
.x
, -q_next
.y
);
2227 d2d_outline_vertex_set(&v
[2], next
->x
, next
->y
, q_next
.x
, q_next
.y
, q_next
.x
, q_next
.y
);
2228 d2d_outline_vertex_set(&v
[3], next
->x
, next
->y
, -q_next
.x
, -q_next
.y
, -q_next
.x
, -q_next
.y
);
2229 geometry
->outline
.vertex_count
+= 4;
2231 d2d_face_set(&f
[0], base_idx
+ 0, base_idx
+ 1, base_idx
+ 2);
2232 d2d_face_set(&f
[1], base_idx
+ 2, base_idx
+ 1, base_idx
+ 3);
2233 geometry
->outline
.face_count
+= 2;
2238 static BOOL
d2d_geometry_outline_add_bezier_segment(struct d2d_geometry
*geometry
,
2239 const D2D1_POINT_2F
*p0
, const D2D1_POINT_2F
*p1
, const D2D1_POINT_2F
*p2
)
2241 struct d2d_bezier_outline_vertex
*b
;
2242 D2D1_POINT_2F r0
, r1
, r2
;
2243 D2D1_POINT_2F q0
, q1
, q2
;
2247 if (!d2d_array_reserve((void **)&geometry
->outline
.beziers
, &geometry
->outline
.beziers_size
,
2248 geometry
->outline
.bezier_count
+ 7, sizeof(*geometry
->outline
.beziers
)))
2250 ERR("Failed to grow outline beziers array.\n");
2253 base_idx
= geometry
->outline
.bezier_count
;
2254 b
= &geometry
->outline
.beziers
[base_idx
];
2256 if (!d2d_array_reserve((void **)&geometry
->outline
.bezier_faces
, &geometry
->outline
.bezier_faces_size
,
2257 geometry
->outline
.bezier_face_count
+ 5, sizeof(*geometry
->outline
.bezier_faces
)))
2259 ERR("Failed to grow outline faces array.\n");
2262 f
= &geometry
->outline
.bezier_faces
[geometry
->outline
.bezier_face_count
];
2264 d2d_point_lerp(&q0
, p0
, p1
, 0.5f
);
2265 d2d_point_lerp(&q1
, p1
, p2
, 0.5f
);
2266 d2d_point_lerp(&q2
, &q0
, &q1
, 0.5f
);
2268 d2d_point_subtract(&r0
, &q0
, p0
);
2269 d2d_point_subtract(&r1
, &q1
, &q0
);
2270 d2d_point_subtract(&r2
, p2
, &q1
);
2272 d2d_point_normalise(&r0
);
2273 d2d_point_normalise(&r1
);
2274 d2d_point_normalise(&r2
);
2276 if (d2d_point_ccw(p0
, p1
, p2
) > 0.0f
)
2278 d2d_point_scale(&r0
, -1.0f
);
2279 d2d_point_scale(&r1
, -1.0f
);
2280 d2d_point_scale(&r2
, -1.0f
);
2283 d2d_bezier_outline_vertex_set(&b
[0], p0
, p0
, p1
, p2
, r0
.x
, r0
.y
, r0
.x
, r0
.y
);
2284 d2d_bezier_outline_vertex_set(&b
[1], p0
, p0
, p1
, p2
, -r0
.x
, -r0
.y
, -r0
.x
, -r0
.y
);
2285 d2d_bezier_outline_vertex_set(&b
[2], &q0
, p0
, p1
, p2
, r0
.x
, r0
.y
, r1
.x
, r1
.y
);
2286 d2d_bezier_outline_vertex_set(&b
[3], &q2
, p0
, p1
, p2
, -r1
.x
, -r1
.y
, -r1
.x
, -r1
.y
);
2287 d2d_bezier_outline_vertex_set(&b
[4], &q1
, p0
, p1
, p2
, r1
.x
, r1
.y
, r2
.x
, r2
.y
);
2288 d2d_bezier_outline_vertex_set(&b
[5], p2
, p0
, p1
, p2
, -r2
.x
, -r2
.y
, -r2
.x
, -r2
.y
);
2289 d2d_bezier_outline_vertex_set(&b
[6], p2
, p0
, p1
, p2
, r2
.x
, r2
.y
, r2
.x
, r2
.y
);
2290 geometry
->outline
.bezier_count
+= 7;
2292 d2d_face_set(&f
[0], base_idx
+ 0, base_idx
+ 1, base_idx
+ 2);
2293 d2d_face_set(&f
[1], base_idx
+ 2, base_idx
+ 1, base_idx
+ 3);
2294 d2d_face_set(&f
[2], base_idx
+ 3, base_idx
+ 4, base_idx
+ 2);
2295 d2d_face_set(&f
[3], base_idx
+ 5, base_idx
+ 4, base_idx
+ 3);
2296 d2d_face_set(&f
[4], base_idx
+ 5, base_idx
+ 6, base_idx
+ 4);
2297 geometry
->outline
.bezier_face_count
+= 5;
2302 static BOOL
d2d_geometry_add_figure_outline(struct d2d_geometry
*geometry
,
2303 struct d2d_figure
*figure
, D2D1_FIGURE_END figure_end
)
2305 const D2D1_POINT_2F
*prev
, *p0
, *next
;
2306 enum d2d_vertex_type prev_type
, type
;
2307 size_t bezier_idx
, i
;
2309 for (i
= 0, bezier_idx
= 0; i
< figure
->vertex_count
; ++i
)
2311 type
= figure
->vertex_types
[i
];
2312 if (type
== D2D_VERTEX_TYPE_NONE
)
2315 p0
= &figure
->vertices
[i
];
2319 prev_type
= figure
->vertex_types
[figure
->vertex_count
- 1];
2320 if (prev_type
== D2D_VERTEX_TYPE_BEZIER
)
2321 prev
= &figure
->bezier_controls
[figure
->bezier_control_count
- 1];
2323 prev
= &figure
->vertices
[figure
->vertex_count
- 1];
2327 prev_type
= figure
->vertex_types
[i
- 1];
2328 if (prev_type
== D2D_VERTEX_TYPE_BEZIER
)
2329 prev
= &figure
->bezier_controls
[bezier_idx
- 1];
2331 prev
= &figure
->vertices
[i
- 1];
2334 if (type
== D2D_VERTEX_TYPE_BEZIER
)
2335 next
= &figure
->bezier_controls
[bezier_idx
++];
2336 else if (i
== figure
->vertex_count
- 1)
2337 next
= &figure
->vertices
[0];
2339 next
= &figure
->vertices
[i
+ 1];
2341 if ((figure_end
== D2D1_FIGURE_END_CLOSED
|| (i
&& i
< figure
->vertex_count
- 1))
2342 && !d2d_geometry_outline_add_join(geometry
, prev
, p0
, next
))
2344 ERR("Failed to add join.\n");
2348 if (type
== D2D_VERTEX_TYPE_LINE
&& (figure_end
== D2D1_FIGURE_END_CLOSED
|| i
< figure
->vertex_count
- 1)
2349 && !d2d_geometry_outline_add_line_segment(geometry
, p0
, next
))
2351 ERR("Failed to add line segment.\n");
2354 else if (type
== D2D_VERTEX_TYPE_BEZIER
)
2356 const D2D1_POINT_2F
*p2
;
2358 if (i
== figure
->vertex_count
- 1)
2359 p2
= &figure
->vertices
[0];
2361 p2
= &figure
->vertices
[i
+ 1];
2363 if (!d2d_geometry_outline_add_bezier_segment(geometry
, p0
, next
, p2
))
2365 ERR("Failed to add bezier segment.\n");
2374 static void d2d_geometry_cleanup(struct d2d_geometry
*geometry
)
2376 HeapFree(GetProcessHeap(), 0, geometry
->outline
.bezier_faces
);
2377 HeapFree(GetProcessHeap(), 0, geometry
->outline
.beziers
);
2378 HeapFree(GetProcessHeap(), 0, geometry
->outline
.faces
);
2379 HeapFree(GetProcessHeap(), 0, geometry
->outline
.vertices
);
2380 HeapFree(GetProcessHeap(), 0, geometry
->fill
.bezier_vertices
);
2381 HeapFree(GetProcessHeap(), 0, geometry
->fill
.faces
);
2382 HeapFree(GetProcessHeap(), 0, geometry
->fill
.vertices
);
2383 ID2D1Factory_Release(geometry
->factory
);
2386 static void d2d_geometry_init(struct d2d_geometry
*geometry
, ID2D1Factory
*factory
,
2387 const D2D1_MATRIX_3X2_F
*transform
, const struct ID2D1GeometryVtbl
*vtbl
)
2389 geometry
->ID2D1Geometry_iface
.lpVtbl
= vtbl
;
2390 geometry
->refcount
= 1;
2391 ID2D1Factory_AddRef(geometry
->factory
= factory
);
2392 geometry
->transform
= *transform
;
2395 static inline struct d2d_geometry
*impl_from_ID2D1GeometrySink(ID2D1GeometrySink
*iface
)
2397 return CONTAINING_RECORD(iface
, struct d2d_geometry
, u
.path
.ID2D1GeometrySink_iface
);
2400 static HRESULT STDMETHODCALLTYPE
d2d_geometry_sink_QueryInterface(ID2D1GeometrySink
*iface
, REFIID iid
, void **out
)
2402 TRACE("iface %p, iid %s, out %p.\n", iface
, debugstr_guid(iid
), out
);
2404 if (IsEqualGUID(iid
, &IID_ID2D1GeometrySink
)
2405 || IsEqualGUID(iid
, &IID_ID2D1SimplifiedGeometrySink
)
2406 || IsEqualGUID(iid
, &IID_IUnknown
))
2408 ID2D1GeometrySink_AddRef(iface
);
2413 WARN("%s not implemented, returning E_NOINTERFACE.\n", debugstr_guid(iid
));
2416 return E_NOINTERFACE
;
2419 static ULONG STDMETHODCALLTYPE
d2d_geometry_sink_AddRef(ID2D1GeometrySink
*iface
)
2421 struct d2d_geometry
*geometry
= impl_from_ID2D1GeometrySink(iface
);
2423 TRACE("iface %p.\n", iface
);
2425 return ID2D1Geometry_AddRef(&geometry
->ID2D1Geometry_iface
);
2428 static ULONG STDMETHODCALLTYPE
d2d_geometry_sink_Release(ID2D1GeometrySink
*iface
)
2430 struct d2d_geometry
*geometry
= impl_from_ID2D1GeometrySink(iface
);
2432 TRACE("iface %p.\n", iface
);
2434 return ID2D1Geometry_Release(&geometry
->ID2D1Geometry_iface
);
2437 static void STDMETHODCALLTYPE
d2d_geometry_sink_SetFillMode(ID2D1GeometrySink
*iface
, D2D1_FILL_MODE mode
)
2439 struct d2d_geometry
*geometry
= impl_from_ID2D1GeometrySink(iface
);
2441 TRACE("iface %p, mode %#x.\n", iface
, mode
);
2443 if (geometry
->u
.path
.state
== D2D_GEOMETRY_STATE_CLOSED
)
2445 geometry
->u
.path
.fill_mode
= mode
;
2448 static void STDMETHODCALLTYPE
d2d_geometry_sink_SetSegmentFlags(ID2D1GeometrySink
*iface
, D2D1_PATH_SEGMENT flags
)
2450 FIXME("iface %p, flags %#x stub!\n", iface
, flags
);
2453 static void STDMETHODCALLTYPE
d2d_geometry_sink_BeginFigure(ID2D1GeometrySink
*iface
,
2454 D2D1_POINT_2F start_point
, D2D1_FIGURE_BEGIN figure_begin
)
2456 struct d2d_geometry
*geometry
= impl_from_ID2D1GeometrySink(iface
);
2457 struct d2d_figure
*figure
;
2459 TRACE("iface %p, start_point {%.8e, %.8e}, figure_begin %#x.\n",
2460 iface
, start_point
.x
, start_point
.y
, figure_begin
);
2462 if (geometry
->u
.path
.state
!= D2D_GEOMETRY_STATE_OPEN
)
2464 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_ERROR
;
2468 if (figure_begin
!= D2D1_FIGURE_BEGIN_FILLED
)
2469 FIXME("Ignoring figure_begin %#x.\n", figure_begin
);
2471 if (!d2d_path_geometry_add_figure(geometry
))
2473 ERR("Failed to add figure.\n");
2474 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_ERROR
;
2478 figure
= &geometry
->u
.path
.figures
[geometry
->u
.path
.figure_count
- 1];
2479 if (figure_begin
== D2D1_FIGURE_BEGIN_HOLLOW
)
2480 figure
->flags
|= D2D_FIGURE_FLAG_HOLLOW
;
2482 if (!d2d_figure_add_vertex(figure
, start_point
))
2484 ERR("Failed to add vertex.\n");
2485 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_ERROR
;
2489 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_FIGURE
;
2492 static void STDMETHODCALLTYPE
d2d_geometry_sink_AddLines(ID2D1GeometrySink
*iface
,
2493 const D2D1_POINT_2F
*points
, UINT32 count
)
2495 struct d2d_geometry
*geometry
= impl_from_ID2D1GeometrySink(iface
);
2496 struct d2d_figure
*figure
= &geometry
->u
.path
.figures
[geometry
->u
.path
.figure_count
- 1];
2499 TRACE("iface %p, points %p, count %u.\n", iface
, points
, count
);
2501 if (geometry
->u
.path
.state
!= D2D_GEOMETRY_STATE_FIGURE
)
2503 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_ERROR
;
2507 for (i
= 0; i
< count
; ++i
)
2509 figure
->vertex_types
[figure
->vertex_count
- 1] = D2D_VERTEX_TYPE_LINE
;
2510 if (!d2d_figure_add_vertex(figure
, points
[i
]))
2512 ERR("Failed to add vertex.\n");
2517 geometry
->u
.path
.segment_count
+= count
;
2520 static void STDMETHODCALLTYPE
d2d_geometry_sink_AddBeziers(ID2D1GeometrySink
*iface
,
2521 const D2D1_BEZIER_SEGMENT
*beziers
, UINT32 count
)
2523 struct d2d_geometry
*geometry
= impl_from_ID2D1GeometrySink(iface
);
2524 struct d2d_figure
*figure
= &geometry
->u
.path
.figures
[geometry
->u
.path
.figure_count
- 1];
2528 TRACE("iface %p, beziers %p, count %u.\n", iface
, beziers
, count
);
2530 if (geometry
->u
.path
.state
!= D2D_GEOMETRY_STATE_FIGURE
)
2532 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_ERROR
;
2536 for (i
= 0; i
< count
; ++i
)
2538 D2D1_RECT_F bezier_bounds
;
2540 /* FIXME: This tries to approximate a cubic bezier with a quadratic one. */
2541 p
.x
= (beziers
[i
].point1
.x
+ beziers
[i
].point2
.x
) * 0.75f
;
2542 p
.y
= (beziers
[i
].point1
.y
+ beziers
[i
].point2
.y
) * 0.75f
;
2543 p
.x
-= (figure
->vertices
[figure
->vertex_count
- 1].x
+ beziers
[i
].point3
.x
) * 0.25f
;
2544 p
.y
-= (figure
->vertices
[figure
->vertex_count
- 1].y
+ beziers
[i
].point3
.y
) * 0.25f
;
2545 figure
->vertex_types
[figure
->vertex_count
- 1] = D2D_VERTEX_TYPE_BEZIER
;
2547 d2d_rect_get_bezier_bounds(&bezier_bounds
, &figure
->vertices
[figure
->vertex_count
- 1],
2548 &p
, &beziers
[i
].point3
);
2550 if (!d2d_figure_add_bezier_control(figure
, &p
))
2552 ERR("Failed to add bezier control.\n");
2553 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_ERROR
;
2557 if (!d2d_figure_add_vertex(figure
, beziers
[i
].point3
))
2559 ERR("Failed to add bezier vertex.\n");
2560 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_ERROR
;
2564 d2d_rect_union(&figure
->bounds
, &bezier_bounds
);
2567 geometry
->u
.path
.segment_count
+= count
;
2570 static void STDMETHODCALLTYPE
d2d_geometry_sink_EndFigure(ID2D1GeometrySink
*iface
, D2D1_FIGURE_END figure_end
)
2572 struct d2d_geometry
*geometry
= impl_from_ID2D1GeometrySink(iface
);
2573 struct d2d_figure
*figure
;
2575 TRACE("iface %p, figure_end %#x.\n", iface
, figure_end
);
2577 if (geometry
->u
.path
.state
!= D2D_GEOMETRY_STATE_FIGURE
)
2579 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_ERROR
;
2583 figure
= &geometry
->u
.path
.figures
[geometry
->u
.path
.figure_count
- 1];
2584 figure
->vertex_types
[figure
->vertex_count
- 1] = D2D_VERTEX_TYPE_LINE
;
2585 if (figure_end
== D2D1_FIGURE_END_CLOSED
)
2587 ++geometry
->u
.path
.segment_count
;
2588 figure
->flags
|= D2D_FIGURE_FLAG_CLOSED
;
2589 if (!memcmp(&figure
->vertices
[0], &figure
->vertices
[figure
->vertex_count
- 1], sizeof(*figure
->vertices
)))
2590 --figure
->vertex_count
;
2593 if (!d2d_geometry_add_figure_outline(geometry
, figure
, figure_end
))
2595 ERR("Failed to add figure outline.\n");
2596 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_ERROR
;
2600 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_OPEN
;
2603 static void d2d_path_geometry_free_figures(struct d2d_geometry
*geometry
)
2607 if (!geometry
->u
.path
.figures
)
2610 for (i
= 0; i
< geometry
->u
.path
.figure_count
; ++i
)
2612 HeapFree(GetProcessHeap(), 0, geometry
->u
.path
.figures
[i
].bezier_controls
);
2613 HeapFree(GetProcessHeap(), 0, geometry
->u
.path
.figures
[i
].original_bezier_controls
);
2614 HeapFree(GetProcessHeap(), 0, geometry
->u
.path
.figures
[i
].vertices
);
2616 HeapFree(GetProcessHeap(), 0, geometry
->u
.path
.figures
);
2617 geometry
->u
.path
.figures
= NULL
;
2618 geometry
->u
.path
.figures_size
= 0;
2621 static BOOL
d2d_geometry_get_bezier_segment_idx(struct d2d_geometry
*geometry
, struct d2d_segment_idx
*idx
, BOOL next
)
2629 for (; idx
->figure_idx
< geometry
->u
.path
.figure_count
; ++idx
->figure_idx
, idx
->vertex_idx
= idx
->control_idx
= 0)
2631 struct d2d_figure
*figure
= &geometry
->u
.path
.figures
[idx
->figure_idx
];
2633 if (!figure
->bezier_control_count
)
2636 for (; idx
->vertex_idx
< figure
->vertex_count
; ++idx
->vertex_idx
)
2638 if (figure
->vertex_types
[idx
->vertex_idx
] == D2D_VERTEX_TYPE_BEZIER
2639 || figure
->vertex_types
[idx
->vertex_idx
] == D2D_VERTEX_TYPE_SPLIT_BEZIER
)
2647 static BOOL
d2d_geometry_get_first_bezier_segment_idx(struct d2d_geometry
*geometry
, struct d2d_segment_idx
*idx
)
2649 memset(idx
, 0, sizeof(*idx
));
2651 return d2d_geometry_get_bezier_segment_idx(geometry
, idx
, FALSE
);
2654 static BOOL
d2d_geometry_get_next_bezier_segment_idx(struct d2d_geometry
*geometry
, struct d2d_segment_idx
*idx
)
2656 return d2d_geometry_get_bezier_segment_idx(geometry
, idx
, TRUE
);
2659 static BOOL
d2d_geometry_check_bezier_overlap(struct d2d_geometry
*geometry
,
2660 const struct d2d_segment_idx
*idx_p
, const struct d2d_segment_idx
*idx_q
)
2662 const D2D1_POINT_2F
*a
[3], *b
[3], *p
[2], *q
;
2663 const struct d2d_figure
*figure
;
2664 D2D1_POINT_2F v_q
[3], v_p
, v_qp
;
2665 unsigned int i
, j
, score
;
2668 figure
= &geometry
->u
.path
.figures
[idx_p
->figure_idx
];
2669 a
[0] = &figure
->vertices
[idx_p
->vertex_idx
];
2670 a
[1] = &figure
->bezier_controls
[idx_p
->control_idx
];
2671 if (idx_p
->vertex_idx
== figure
->vertex_count
- 1)
2672 a
[2] = &figure
->vertices
[0];
2674 a
[2] = &figure
->vertices
[idx_p
->vertex_idx
+ 1];
2676 figure
= &geometry
->u
.path
.figures
[idx_q
->figure_idx
];
2677 b
[0] = &figure
->vertices
[idx_q
->vertex_idx
];
2678 b
[1] = &figure
->bezier_controls
[idx_q
->control_idx
];
2679 if (idx_q
->vertex_idx
== figure
->vertex_count
- 1)
2680 b
[2] = &figure
->vertices
[0];
2682 b
[2] = &figure
->vertices
[idx_q
->vertex_idx
+ 1];
2684 if (d2d_point_ccw(a
[0], a
[1], a
[2]) == 0.0f
|| d2d_point_ccw(b
[0], b
[1], b
[2]) == 0.0f
)
2687 d2d_point_subtract(&v_q
[0], b
[1], b
[0]);
2688 d2d_point_subtract(&v_q
[1], b
[2], b
[0]);
2689 d2d_point_subtract(&v_q
[2], b
[1], b
[2]);
2691 /* Check for intersections between the edges. Strictly speaking we'd only
2692 * need to check 8 of the 9 possible intersections, since if there's any
2693 * intersection there has to be a second intersection as well. */
2694 for (i
= 0; i
< 3; ++i
)
2696 d2d_point_subtract(&v_p
, a
[(i
& 1) + 1], a
[i
& 2]);
2697 for (j
= 0; j
< 3; ++j
)
2699 det
= v_p
.x
* v_q
[j
].y
- v_p
.y
* v_q
[j
].x
;
2703 d2d_point_subtract(&v_qp
, a
[i
& 2], b
[j
& 2]);
2704 t
= (v_q
[j
].x
* v_qp
.y
- v_q
[j
].y
* v_qp
.x
) / det
;
2705 if (t
<= 0.0f
|| t
>= 1.0f
)
2708 t
= (v_p
.x
* v_qp
.y
- v_p
.y
* v_qp
.x
) / det
;
2709 if (t
<= 0.0f
|| t
>= 1.0f
)
2716 /* Check if one triangle is contained within the other. */
2717 for (j
= 0, score
= 0, q
= a
[1], p
[0] = b
[2]; j
< 3; ++j
)
2720 d2d_point_subtract(&v_p
, p
[1], p
[0]);
2721 d2d_point_subtract(&v_qp
, q
, p
[0]);
2723 if ((q
->y
< p
[0]->y
) != (q
->y
< p
[1]->y
) && v_qp
.x
< v_p
.x
* (v_qp
.y
/ v_p
.y
))
2732 for (j
= 0, score
= 0, q
= b
[1], p
[0] = a
[2]; j
< 3; ++j
)
2735 d2d_point_subtract(&v_p
, p
[1], p
[0]);
2736 d2d_point_subtract(&v_qp
, q
, p
[0]);
2738 if ((q
->y
< p
[0]->y
) != (q
->y
< p
[1]->y
) && v_qp
.x
< v_p
.x
* (v_qp
.y
/ v_p
.y
))
2747 static float d2d_geometry_bezier_ccw(struct d2d_geometry
*geometry
, const struct d2d_segment_idx
*idx
)
2749 const struct d2d_figure
*figure
= &geometry
->u
.path
.figures
[idx
->figure_idx
];
2750 size_t next
= idx
->vertex_idx
+ 1;
2752 if (next
== figure
->vertex_count
)
2755 return d2d_point_ccw(&figure
->vertices
[idx
->vertex_idx
],
2756 &figure
->bezier_controls
[idx
->control_idx
], &figure
->vertices
[next
]);
2759 static BOOL
d2d_geometry_split_bezier(struct d2d_geometry
*geometry
, const struct d2d_segment_idx
*idx
)
2761 const D2D1_POINT_2F
*p
[3];
2762 struct d2d_figure
*figure
;
2766 figure
= &geometry
->u
.path
.figures
[idx
->figure_idx
];
2767 p
[0] = &figure
->vertices
[idx
->vertex_idx
];
2768 p
[1] = &figure
->bezier_controls
[idx
->control_idx
];
2769 next
= idx
->vertex_idx
+ 1;
2770 if (next
== figure
->vertex_count
)
2772 p
[2] = &figure
->vertices
[next
];
2774 d2d_point_lerp(&q
[0], p
[0], p
[1], 0.5f
);
2775 d2d_point_lerp(&q
[1], p
[1], p
[2], 0.5f
);
2776 d2d_point_lerp(&q
[2], &q
[0], &q
[1], 0.5f
);
2778 figure
->bezier_controls
[idx
->control_idx
] = q
[0];
2779 if (!(d2d_figure_insert_bezier_control(figure
, idx
->control_idx
+ 1, &q
[1])))
2781 if (!(d2d_figure_insert_vertex(figure
, idx
->vertex_idx
+ 1, q
[2])))
2783 figure
->vertex_types
[idx
->vertex_idx
+ 1] = D2D_VERTEX_TYPE_SPLIT_BEZIER
;
2788 static HRESULT
d2d_geometry_resolve_beziers(struct d2d_geometry
*geometry
)
2790 struct d2d_segment_idx idx_p
, idx_q
;
2791 struct d2d_bezier_vertex
*b
;
2792 const D2D1_POINT_2F
*p
[3];
2793 struct d2d_figure
*figure
;
2794 size_t bezier_idx
, i
;
2796 if (!d2d_geometry_get_first_bezier_segment_idx(geometry
, &idx_p
))
2799 /* Split overlapping bezier control triangles. */
2800 while (d2d_geometry_get_next_bezier_segment_idx(geometry
, &idx_p
))
2802 d2d_geometry_get_first_bezier_segment_idx(geometry
, &idx_q
);
2803 while (idx_q
.figure_idx
< idx_p
.figure_idx
|| idx_q
.vertex_idx
< idx_p
.vertex_idx
)
2805 while (d2d_geometry_check_bezier_overlap(geometry
, &idx_p
, &idx_q
))
2807 if (fabsf(d2d_geometry_bezier_ccw(geometry
, &idx_q
)) > fabsf(d2d_geometry_bezier_ccw(geometry
, &idx_p
)))
2809 if (!d2d_geometry_split_bezier(geometry
, &idx_q
))
2810 return E_OUTOFMEMORY
;
2811 if (idx_p
.figure_idx
== idx_q
.figure_idx
)
2814 ++idx_p
.control_idx
;
2819 if (!d2d_geometry_split_bezier(geometry
, &idx_p
))
2820 return E_OUTOFMEMORY
;
2823 d2d_geometry_get_next_bezier_segment_idx(geometry
, &idx_q
);
2827 for (i
= 0; i
< geometry
->u
.path
.figure_count
; ++i
)
2829 geometry
->fill
.bezier_vertex_count
+= 3 * geometry
->u
.path
.figures
[i
].bezier_control_count
;
2832 if (!(geometry
->fill
.bezier_vertices
= HeapAlloc(GetProcessHeap(), 0,
2833 geometry
->fill
.bezier_vertex_count
* sizeof(*geometry
->fill
.bezier_vertices
))))
2835 ERR("Failed to allocate bezier vertices array.\n");
2836 geometry
->fill
.bezier_vertex_count
= 0;
2837 return E_OUTOFMEMORY
;
2841 d2d_geometry_get_first_bezier_segment_idx(geometry
, &idx_p
);
2846 figure
= &geometry
->u
.path
.figures
[idx_p
.figure_idx
];
2847 p
[0] = &figure
->vertices
[idx_p
.vertex_idx
];
2848 p
[1] = &figure
->bezier_controls
[idx_p
.control_idx
];
2850 i
= idx_p
.vertex_idx
+ 1;
2851 if (d2d_path_geometry_point_inside(geometry
, p
[1], FALSE
))
2854 d2d_figure_insert_vertex(figure
, i
, *p
[1]);
2855 /* Inserting a vertex potentially invalidates p[0]. */
2856 p
[0] = &figure
->vertices
[idx_p
.vertex_idx
];
2860 if (i
== figure
->vertex_count
)
2862 p
[2] = &figure
->vertices
[i
];
2864 b
= &geometry
->fill
.bezier_vertices
[bezier_idx
* 3];
2865 d2d_bezier_vertex_set(&b
[0], p
[0], 0.0f
, 0.0f
, sign
);
2866 d2d_bezier_vertex_set(&b
[1], p
[1], 0.5f
, 0.0f
, sign
);
2867 d2d_bezier_vertex_set(&b
[2], p
[2], 1.0f
, 1.0f
, sign
);
2869 if (!d2d_geometry_get_next_bezier_segment_idx(geometry
, &idx_p
))
2877 static HRESULT STDMETHODCALLTYPE
d2d_geometry_sink_Close(ID2D1GeometrySink
*iface
)
2879 struct d2d_geometry
*geometry
= impl_from_ID2D1GeometrySink(iface
);
2880 HRESULT hr
= E_FAIL
;
2883 TRACE("iface %p.\n", iface
);
2885 if (geometry
->u
.path
.state
!= D2D_GEOMETRY_STATE_OPEN
)
2887 if (geometry
->u
.path
.state
!= D2D_GEOMETRY_STATE_CLOSED
)
2888 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_ERROR
;
2889 return D2DERR_WRONG_STATE
;
2891 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_CLOSED
;
2893 for (i
= 0; i
< geometry
->u
.path
.figure_count
; ++i
)
2895 struct d2d_figure
*figure
= &geometry
->u
.path
.figures
[i
];
2896 size_t size
= figure
->bezier_control_count
* sizeof(*figure
->original_bezier_controls
);
2897 if (!(figure
->original_bezier_controls
= HeapAlloc(GetProcessHeap(), 0, size
)))
2899 memcpy(figure
->original_bezier_controls
, figure
->bezier_controls
, size
);
2902 if (!d2d_geometry_intersect_self(geometry
))
2904 if (FAILED(hr
= d2d_geometry_resolve_beziers(geometry
)))
2906 if (FAILED(hr
= d2d_path_geometry_triangulate(geometry
)))
2912 HeapFree(GetProcessHeap(), 0, geometry
->fill
.bezier_vertices
);
2913 geometry
->fill
.bezier_vertex_count
= 0;
2914 d2d_path_geometry_free_figures(geometry
);
2915 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_ERROR
;
2920 static void STDMETHODCALLTYPE
d2d_geometry_sink_AddLine(ID2D1GeometrySink
*iface
, D2D1_POINT_2F point
)
2922 TRACE("iface %p, point {%.8e, %.8e}.\n", iface
, point
.x
, point
.y
);
2924 d2d_geometry_sink_AddLines(iface
, &point
, 1);
2927 static void STDMETHODCALLTYPE
d2d_geometry_sink_AddBezier(ID2D1GeometrySink
*iface
, const D2D1_BEZIER_SEGMENT
*bezier
)
2929 TRACE("iface %p, bezier %p.\n", iface
, bezier
);
2931 d2d_geometry_sink_AddBeziers(iface
, bezier
, 1);
2934 static void STDMETHODCALLTYPE
d2d_geometry_sink_AddQuadraticBezier(ID2D1GeometrySink
*iface
,
2935 const D2D1_QUADRATIC_BEZIER_SEGMENT
*bezier
)
2937 TRACE("iface %p, bezier %p.\n", iface
, bezier
);
2939 ID2D1GeometrySink_AddQuadraticBeziers(iface
, bezier
, 1);
2942 static void STDMETHODCALLTYPE
d2d_geometry_sink_AddQuadraticBeziers(ID2D1GeometrySink
*iface
,
2943 const D2D1_QUADRATIC_BEZIER_SEGMENT
*beziers
, UINT32 bezier_count
)
2945 struct d2d_geometry
*geometry
= impl_from_ID2D1GeometrySink(iface
);
2946 struct d2d_figure
*figure
= &geometry
->u
.path
.figures
[geometry
->u
.path
.figure_count
- 1];
2949 TRACE("iface %p, beziers %p, bezier_count %u.\n", iface
, beziers
, bezier_count
);
2951 if (geometry
->u
.path
.state
!= D2D_GEOMETRY_STATE_FIGURE
)
2953 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_ERROR
;
2957 for (i
= 0; i
< bezier_count
; ++i
)
2959 D2D1_RECT_F bezier_bounds
;
2961 d2d_rect_get_bezier_bounds(&bezier_bounds
, &figure
->vertices
[figure
->vertex_count
- 1],
2962 &beziers
[i
].point1
, &beziers
[i
].point2
);
2964 figure
->vertex_types
[figure
->vertex_count
- 1] = D2D_VERTEX_TYPE_BEZIER
;
2965 if (!d2d_figure_add_bezier_control(figure
, &beziers
[i
].point1
))
2967 ERR("Failed to add bezier.\n");
2968 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_ERROR
;
2972 if (!d2d_figure_add_vertex(figure
, beziers
[i
].point2
))
2974 ERR("Failed to add bezier vertex.\n");
2975 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_ERROR
;
2979 d2d_rect_union(&figure
->bounds
, &bezier_bounds
);
2982 geometry
->u
.path
.segment_count
+= bezier_count
;
2985 static void STDMETHODCALLTYPE
d2d_geometry_sink_AddArc(ID2D1GeometrySink
*iface
, const D2D1_ARC_SEGMENT
*arc
)
2987 struct d2d_geometry
*geometry
= impl_from_ID2D1GeometrySink(iface
);
2989 FIXME("iface %p, arc %p stub!\n", iface
, arc
);
2991 if (geometry
->u
.path
.state
!= D2D_GEOMETRY_STATE_FIGURE
)
2993 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_ERROR
;
2997 if (!d2d_figure_add_vertex(&geometry
->u
.path
.figures
[geometry
->u
.path
.figure_count
- 1], arc
->point
))
2999 ERR("Failed to add vertex.\n");
3003 ++geometry
->u
.path
.segment_count
;
3006 static const struct ID2D1GeometrySinkVtbl d2d_geometry_sink_vtbl
=
3008 d2d_geometry_sink_QueryInterface
,
3009 d2d_geometry_sink_AddRef
,
3010 d2d_geometry_sink_Release
,
3011 d2d_geometry_sink_SetFillMode
,
3012 d2d_geometry_sink_SetSegmentFlags
,
3013 d2d_geometry_sink_BeginFigure
,
3014 d2d_geometry_sink_AddLines
,
3015 d2d_geometry_sink_AddBeziers
,
3016 d2d_geometry_sink_EndFigure
,
3017 d2d_geometry_sink_Close
,
3018 d2d_geometry_sink_AddLine
,
3019 d2d_geometry_sink_AddBezier
,
3020 d2d_geometry_sink_AddQuadraticBezier
,
3021 d2d_geometry_sink_AddQuadraticBeziers
,
3022 d2d_geometry_sink_AddArc
,
3025 static inline struct d2d_geometry
*impl_from_ID2D1PathGeometry(ID2D1PathGeometry
*iface
)
3027 return CONTAINING_RECORD(iface
, struct d2d_geometry
, ID2D1Geometry_iface
);
3030 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_QueryInterface(ID2D1PathGeometry
*iface
, REFIID iid
, void **out
)
3032 TRACE("iface %p, iid %s, out %p.\n", iface
, debugstr_guid(iid
), out
);
3034 if (IsEqualGUID(iid
, &IID_ID2D1PathGeometry
)
3035 || IsEqualGUID(iid
, &IID_ID2D1Geometry
)
3036 || IsEqualGUID(iid
, &IID_ID2D1Resource
)
3037 || IsEqualGUID(iid
, &IID_IUnknown
))
3039 ID2D1PathGeometry_AddRef(iface
);
3044 WARN("%s not implemented, returning E_NOINTERFACE.\n", debugstr_guid(iid
));
3047 return E_NOINTERFACE
;
3050 static ULONG STDMETHODCALLTYPE
d2d_path_geometry_AddRef(ID2D1PathGeometry
*iface
)
3052 struct d2d_geometry
*geometry
= impl_from_ID2D1PathGeometry(iface
);
3053 ULONG refcount
= InterlockedIncrement(&geometry
->refcount
);
3055 TRACE("%p increasing refcount to %u.\n", iface
, refcount
);
3060 static ULONG STDMETHODCALLTYPE
d2d_path_geometry_Release(ID2D1PathGeometry
*iface
)
3062 struct d2d_geometry
*geometry
= impl_from_ID2D1PathGeometry(iface
);
3063 ULONG refcount
= InterlockedDecrement(&geometry
->refcount
);
3065 TRACE("%p decreasing refcount to %u.\n", iface
, refcount
);
3069 d2d_path_geometry_free_figures(geometry
);
3070 d2d_geometry_cleanup(geometry
);
3071 HeapFree(GetProcessHeap(), 0, geometry
);
3077 static void STDMETHODCALLTYPE
d2d_path_geometry_GetFactory(ID2D1PathGeometry
*iface
, ID2D1Factory
**factory
)
3079 struct d2d_geometry
*geometry
= impl_from_ID2D1PathGeometry(iface
);
3081 TRACE("iface %p, factory %p.\n", iface
, factory
);
3083 ID2D1Factory_AddRef(*factory
= geometry
->factory
);
3086 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_GetBounds(ID2D1PathGeometry
*iface
,
3087 const D2D1_MATRIX_3X2_F
*transform
, D2D1_RECT_F
*bounds
)
3089 struct d2d_geometry
*geometry
= impl_from_ID2D1PathGeometry(iface
);
3092 TRACE("iface %p, transform %p, bounds %p.\n", iface
, transform
, bounds
);
3094 if (geometry
->u
.path
.state
!= D2D_GEOMETRY_STATE_CLOSED
)
3095 return D2DERR_WRONG_STATE
;
3097 bounds
->left
= FLT_MAX
;
3098 bounds
->top
= FLT_MAX
;
3099 bounds
->right
= -FLT_MAX
;
3100 bounds
->bottom
= -FLT_MAX
;
3104 if (geometry
->u
.path
.bounds
.left
> geometry
->u
.path
.bounds
.right
)
3106 for (i
= 0; i
< geometry
->u
.path
.figure_count
; ++i
)
3107 d2d_rect_union(&geometry
->u
.path
.bounds
, &geometry
->u
.path
.figures
[i
].bounds
);
3110 *bounds
= geometry
->u
.path
.bounds
;
3114 for (i
= 0; i
< geometry
->u
.path
.figure_count
; ++i
)
3116 const struct d2d_figure
*figure
= &geometry
->u
.path
.figures
[i
];
3117 enum d2d_vertex_type type
= D2D_VERTEX_TYPE_NONE
;
3118 D2D1_RECT_F bezier_bounds
;
3119 D2D1_POINT_2F p
, p1
, p2
;
3120 size_t j
, bezier_idx
;
3122 /* Single vertex figures are reduced by CloseFigure(). */
3123 if (figure
->vertex_count
== 0)
3125 d2d_point_transform(&p
, transform
, figure
->bounds
.left
, figure
->bounds
.top
);
3126 d2d_rect_expand(bounds
, &p
);
3130 for (j
= 0; j
< figure
->vertex_count
; ++j
)
3132 if (figure
->vertex_types
[j
] == D2D_VERTEX_TYPE_NONE
)
3135 p
= figure
->vertices
[j
];
3136 type
= figure
->vertex_types
[j
];
3137 d2d_point_transform(&p
, transform
, p
.x
, p
.y
);
3138 d2d_rect_expand(bounds
, &p
);
3142 for (bezier_idx
= 0, ++j
; j
< figure
->vertex_count
; ++j
)
3144 if (figure
->vertex_types
[j
] == D2D_VERTEX_TYPE_NONE
3145 || figure
->vertex_types
[j
] == D2D_VERTEX_TYPE_SPLIT_BEZIER
)
3150 case D2D_VERTEX_TYPE_LINE
:
3151 p
= figure
->vertices
[j
];
3152 d2d_point_transform(&p
, transform
, p
.x
, p
.y
);
3153 d2d_rect_expand(bounds
, &p
);
3156 case D2D_VERTEX_TYPE_BEZIER
:
3157 p1
= figure
->original_bezier_controls
[bezier_idx
++];
3158 d2d_point_transform(&p1
, transform
, p1
.x
, p1
.y
);
3159 p2
= figure
->vertices
[j
];
3160 d2d_point_transform(&p2
, transform
, p2
.x
, p2
.y
);
3161 d2d_rect_get_bezier_bounds(&bezier_bounds
, &p
, &p1
, &p2
);
3162 d2d_rect_union(bounds
, &bezier_bounds
);
3167 FIXME("Unhandled vertex type %#x.\n", type
);
3168 p
= figure
->vertices
[j
];
3169 d2d_point_transform(&p
, transform
, p
.x
, p
.y
);
3170 d2d_rect_expand(bounds
, &p
);
3174 type
= figure
->vertex_types
[j
];
3177 if (type
== D2D_VERTEX_TYPE_BEZIER
)
3179 p1
= figure
->original_bezier_controls
[bezier_idx
++];
3180 d2d_point_transform(&p1
, transform
, p1
.x
, p1
.y
);
3181 p2
= figure
->vertices
[0];
3182 d2d_point_transform(&p2
, transform
, p2
.x
, p2
.y
);
3183 d2d_rect_get_bezier_bounds(&bezier_bounds
, &p
, &p1
, &p2
);
3184 d2d_rect_union(bounds
, &bezier_bounds
);
3191 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_GetWidenedBounds(ID2D1PathGeometry
*iface
, float stroke_width
,
3192 ID2D1StrokeStyle
*stroke_style
, const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, D2D1_RECT_F
*bounds
)
3194 FIXME("iface %p, stroke_width %.8e, stroke_style %p, transform %p, tolerance %.8e, bounds %p stub!\n",
3195 iface
, stroke_width
, stroke_style
, transform
, tolerance
, bounds
);
3200 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_StrokeContainsPoint(ID2D1PathGeometry
*iface
,
3201 D2D1_POINT_2F point
, float stroke_width
, ID2D1StrokeStyle
*stroke_style
, const D2D1_MATRIX_3X2_F
*transform
,
3202 float tolerance
, BOOL
*contains
)
3204 FIXME("iface %p, point {%.8e, %.8e}, stroke_width %.8e, stroke_style %p, "
3205 "transform %p, tolerance %.8e, contains %p stub!\n",
3206 iface
, point
.x
, point
.y
, stroke_width
, stroke_style
, transform
, tolerance
, contains
);
3211 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_FillContainsPoint(ID2D1PathGeometry
*iface
,
3212 D2D1_POINT_2F point
, const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, BOOL
*contains
)
3214 struct d2d_geometry
*geometry
= impl_from_ID2D1PathGeometry(iface
);
3215 D2D1_MATRIX_3X2_F g_i
;
3217 TRACE("iface %p, point {%.8e, %.8e}, transform %p, tolerance %.8e, contains %p.\n",
3218 iface
, point
.x
, point
.y
, transform
, tolerance
, contains
);
3222 if (!d2d_matrix_invert(&g_i
, transform
))
3223 return D2DERR_UNSUPPORTED_OPERATION
;
3224 d2d_point_transform(&point
, &g_i
, point
.x
, point
.y
);
3227 *contains
= !!d2d_path_geometry_point_inside(geometry
, &point
, FALSE
);
3229 TRACE("-> %#x.\n", *contains
);
3234 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_CompareWithGeometry(ID2D1PathGeometry
*iface
,
3235 ID2D1Geometry
*geometry
, const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, D2D1_GEOMETRY_RELATION
*relation
)
3237 FIXME("iface %p, geometry %p, transform %p, tolerance %.8e, relation %p stub!\n",
3238 iface
, geometry
, transform
, tolerance
, relation
);
3243 static void d2d_geometry_flatten_cubic(ID2D1SimplifiedGeometrySink
*sink
, const D2D1_POINT_2F
*p0
,
3244 const D2D1_BEZIER_SEGMENT
*b
, float tolerance
)
3246 D2D1_BEZIER_SEGMENT b0
, b1
;
3250 /* It's certainly possible to calculate the maximum deviation of the
3251 * approximation from the curve, but it's a little involved. Instead, note
3252 * that if the control points were evenly spaced and collinear, p1 would
3253 * be exactly between p0 and p2, and p2 would be exactly between p1 and
3254 * p3. The deviation is a decent enough approximation, and much easier to
3257 * p1' = (p0 + p2) / 2
3258 * p2' = (p1 + p3) / 2
3259 * d = ‖p1 - p1'‖₁ + ‖p2 - p2'‖₁ */
3260 d2d_point_lerp(&q
, p0
, &b
->point2
, 0.5f
);
3261 d2d_point_subtract(&q
, &b
->point1
, &q
);
3262 d
= fabsf(q
.x
) + fabsf(q
.y
);
3263 d2d_point_lerp(&q
, &b
->point1
, &b
->point3
, 0.5f
);
3264 d2d_point_subtract(&q
, &b
->point2
, &q
);
3265 d
+= fabsf(q
.x
) + fabsf(q
.y
);
3268 ID2D1SimplifiedGeometrySink_AddLines(sink
, &b
->point3
, 1);
3272 d2d_point_lerp(&q
, &b
->point1
, &b
->point2
, 0.5f
);
3274 b1
.point3
= b
->point3
;
3275 d2d_point_lerp(&b1
.point2
, &b1
.point3
, &b
->point2
, 0.5f
);
3276 d2d_point_lerp(&b1
.point1
, &b1
.point2
, &q
, 0.5f
);
3278 d2d_point_lerp(&b0
.point1
, p0
, &b
->point1
, 0.5f
);
3279 d2d_point_lerp(&b0
.point2
, &b0
.point1
, &q
, 0.5f
);
3280 d2d_point_lerp(&b0
.point3
, &b0
.point2
, &b1
.point1
, 0.5f
);
3282 d2d_geometry_flatten_cubic(sink
, p0
, &b0
, tolerance
);
3283 ID2D1SimplifiedGeometrySink_SetSegmentFlags(sink
, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN
);
3284 d2d_geometry_flatten_cubic(sink
, &b0
.point3
, &b1
, tolerance
);
3285 ID2D1SimplifiedGeometrySink_SetSegmentFlags(sink
, D2D1_PATH_SEGMENT_NONE
);
3288 static void d2d_geometry_simplify_quadratic(ID2D1SimplifiedGeometrySink
*sink
,
3289 D2D1_GEOMETRY_SIMPLIFICATION_OPTION option
, const D2D1_POINT_2F
*p0
,
3290 const D2D1_POINT_2F
*p1
, const D2D1_POINT_2F
*p2
, float tolerance
)
3292 D2D1_BEZIER_SEGMENT b
;
3294 d2d_point_lerp(&b
.point1
, p0
, p1
, 2.0f
/ 3.0f
);
3295 d2d_point_lerp(&b
.point2
, p2
, p1
, 2.0f
/ 3.0f
);
3298 if (option
== D2D1_GEOMETRY_SIMPLIFICATION_OPTION_LINES
)
3299 d2d_geometry_flatten_cubic(sink
, p0
, &b
, tolerance
);
3301 ID2D1SimplifiedGeometrySink_AddBeziers(sink
, &b
, 1);
3304 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_Simplify(ID2D1PathGeometry
*iface
,
3305 D2D1_GEOMETRY_SIMPLIFICATION_OPTION option
, const D2D1_MATRIX_3X2_F
*transform
, float tolerance
,
3306 ID2D1SimplifiedGeometrySink
*sink
)
3308 struct d2d_geometry
*geometry
= impl_from_ID2D1PathGeometry(iface
);
3309 enum d2d_vertex_type type
= D2D_VERTEX_TYPE_NONE
;
3310 unsigned int i
, j
, bezier_idx
;
3311 D2D1_FIGURE_BEGIN begin
;
3312 D2D1_POINT_2F p
, p1
, p2
;
3313 D2D1_FIGURE_END end
;
3315 TRACE("iface %p, option %#x, transform %p, tolerance %.8e, sink %p.\n",
3316 iface
, option
, transform
, tolerance
, sink
);
3318 ID2D1SimplifiedGeometrySink_SetFillMode(sink
, geometry
->u
.path
.fill_mode
);
3319 for (i
= 0; i
< geometry
->u
.path
.figure_count
; ++i
)
3321 const struct d2d_figure
*figure
= &geometry
->u
.path
.figures
[i
];
3323 for (j
= 0; j
< figure
->vertex_count
; ++j
)
3325 if (figure
->vertex_types
[j
] == D2D_VERTEX_TYPE_NONE
)
3328 p
= figure
->vertices
[j
];
3330 d2d_point_transform(&p
, transform
, p
.x
, p
.y
);
3331 begin
= figure
->flags
& D2D_FIGURE_FLAG_HOLLOW
? D2D1_FIGURE_BEGIN_HOLLOW
: D2D1_FIGURE_BEGIN_FILLED
;
3332 ID2D1SimplifiedGeometrySink_BeginFigure(sink
, p
, begin
);
3333 type
= figure
->vertex_types
[j
];
3337 for (bezier_idx
= 0, ++j
; j
< figure
->vertex_count
; ++j
)
3339 if (figure
->vertex_types
[j
] == D2D_VERTEX_TYPE_NONE
3340 || figure
->vertex_types
[j
] == D2D_VERTEX_TYPE_SPLIT_BEZIER
)
3345 case D2D_VERTEX_TYPE_LINE
:
3346 p
= figure
->vertices
[j
];
3348 d2d_point_transform(&p
, transform
, p
.x
, p
.y
);
3349 ID2D1SimplifiedGeometrySink_AddLines(sink
, &p
, 1);
3352 case D2D_VERTEX_TYPE_BEZIER
:
3353 p1
= figure
->original_bezier_controls
[bezier_idx
++];
3355 d2d_point_transform(&p1
, transform
, p1
.x
, p1
.y
);
3356 p2
= figure
->vertices
[j
];
3358 d2d_point_transform(&p2
, transform
, p2
.x
, p2
.y
);
3359 d2d_geometry_simplify_quadratic(sink
, option
, &p
, &p1
, &p2
, tolerance
);
3364 FIXME("Unhandled vertex type %#x.\n", type
);
3365 p
= figure
->vertices
[j
];
3367 d2d_point_transform(&p
, transform
, p
.x
, p
.y
);
3368 ID2D1SimplifiedGeometrySink_AddLines(sink
, &p
, 1);
3372 type
= figure
->vertex_types
[j
];
3375 if (type
== D2D_VERTEX_TYPE_BEZIER
)
3377 p1
= figure
->original_bezier_controls
[bezier_idx
++];
3379 d2d_point_transform(&p1
, transform
, p1
.x
, p1
.y
);
3380 p2
= figure
->vertices
[0];
3382 d2d_point_transform(&p2
, transform
, p2
.x
, p2
.y
);
3383 d2d_geometry_simplify_quadratic(sink
, option
, &p
, &p1
, &p2
, tolerance
);
3386 end
= figure
->flags
& D2D_FIGURE_FLAG_CLOSED
? D2D1_FIGURE_END_CLOSED
: D2D1_FIGURE_END_OPEN
;
3387 ID2D1SimplifiedGeometrySink_EndFigure(sink
, end
);
3393 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_Tessellate(ID2D1PathGeometry
*iface
,
3394 const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, ID2D1TessellationSink
*sink
)
3396 FIXME("iface %p, transform %p, tolerance %.8e, sink %p stub!\n", iface
, transform
, tolerance
, sink
);
3401 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_CombineWithGeometry(ID2D1PathGeometry
*iface
,
3402 ID2D1Geometry
*geometry
, D2D1_COMBINE_MODE combine_mode
, const D2D1_MATRIX_3X2_F
*transform
,
3403 float tolerance
, ID2D1SimplifiedGeometrySink
*sink
)
3405 FIXME("iface %p, geometry %p, combine_mode %#x, transform %p, tolerance %.8e, sink %p stub!\n",
3406 iface
, geometry
, combine_mode
, transform
, tolerance
, sink
);
3411 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_Outline(ID2D1PathGeometry
*iface
,
3412 const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, ID2D1SimplifiedGeometrySink
*sink
)
3414 FIXME("iface %p, transform %p, tolerance %.8e, sink %p stub!\n", iface
, transform
, tolerance
, sink
);
3419 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_ComputeArea(ID2D1PathGeometry
*iface
,
3420 const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, float *area
)
3422 FIXME("iface %p, transform %p, tolerance %.8e, area %p stub!\n", iface
, transform
, tolerance
, area
);
3427 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_ComputeLength(ID2D1PathGeometry
*iface
,
3428 const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, float *length
)
3430 FIXME("iface %p, transform %p, tolerance %.8e, length %p stub!\n", iface
, transform
, tolerance
, length
);
3435 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_ComputePointAtLength(ID2D1PathGeometry
*iface
, float length
,
3436 const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, D2D1_POINT_2F
*point
, D2D1_POINT_2F
*tangent
)
3438 FIXME("iface %p, length %.8e, transform %p, tolerance %.8e, point %p, tangent %p stub!\n",
3439 iface
, length
, transform
, tolerance
, point
, tangent
);
3444 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_Widen(ID2D1PathGeometry
*iface
, float stroke_width
,
3445 ID2D1StrokeStyle
*stroke_style
, const D2D1_MATRIX_3X2_F
*transform
, float tolerance
,
3446 ID2D1SimplifiedGeometrySink
*sink
)
3448 FIXME("iface %p, stroke_width %.8e, stroke_style %p, transform %p, tolerance %.8e, sink %p stub!\n",
3449 iface
, stroke_width
, stroke_style
, transform
, tolerance
, sink
);
3454 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_Open(ID2D1PathGeometry
*iface
, ID2D1GeometrySink
**sink
)
3456 struct d2d_geometry
*geometry
= impl_from_ID2D1PathGeometry(iface
);
3458 TRACE("iface %p, sink %p.\n", iface
, sink
);
3460 if (geometry
->u
.path
.state
!= D2D_GEOMETRY_STATE_INITIAL
)
3461 return D2DERR_WRONG_STATE
;
3463 *sink
= &geometry
->u
.path
.ID2D1GeometrySink_iface
;
3464 ID2D1GeometrySink_AddRef(*sink
);
3466 geometry
->u
.path
.state
= D2D_GEOMETRY_STATE_OPEN
;
3471 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_Stream(ID2D1PathGeometry
*iface
, ID2D1GeometrySink
*sink
)
3473 FIXME("iface %p, sink %p stub!\n", iface
, sink
);
3478 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_GetSegmentCount(ID2D1PathGeometry
*iface
, UINT32
*count
)
3480 struct d2d_geometry
*geometry
= impl_from_ID2D1PathGeometry(iface
);
3482 TRACE("iface %p, count %p.\n", iface
, count
);
3484 if (geometry
->u
.path
.state
!= D2D_GEOMETRY_STATE_CLOSED
)
3485 return D2DERR_WRONG_STATE
;
3487 *count
= geometry
->u
.path
.segment_count
;
3492 static HRESULT STDMETHODCALLTYPE
d2d_path_geometry_GetFigureCount(ID2D1PathGeometry
*iface
, UINT32
*count
)
3494 struct d2d_geometry
*geometry
= impl_from_ID2D1PathGeometry(iface
);
3496 TRACE("iface %p, count %p.\n", iface
, count
);
3498 if (geometry
->u
.path
.state
!= D2D_GEOMETRY_STATE_CLOSED
)
3499 return D2DERR_WRONG_STATE
;
3501 *count
= geometry
->u
.path
.figure_count
;
3506 static const struct ID2D1PathGeometryVtbl d2d_path_geometry_vtbl
=
3508 d2d_path_geometry_QueryInterface
,
3509 d2d_path_geometry_AddRef
,
3510 d2d_path_geometry_Release
,
3511 d2d_path_geometry_GetFactory
,
3512 d2d_path_geometry_GetBounds
,
3513 d2d_path_geometry_GetWidenedBounds
,
3514 d2d_path_geometry_StrokeContainsPoint
,
3515 d2d_path_geometry_FillContainsPoint
,
3516 d2d_path_geometry_CompareWithGeometry
,
3517 d2d_path_geometry_Simplify
,
3518 d2d_path_geometry_Tessellate
,
3519 d2d_path_geometry_CombineWithGeometry
,
3520 d2d_path_geometry_Outline
,
3521 d2d_path_geometry_ComputeArea
,
3522 d2d_path_geometry_ComputeLength
,
3523 d2d_path_geometry_ComputePointAtLength
,
3524 d2d_path_geometry_Widen
,
3525 d2d_path_geometry_Open
,
3526 d2d_path_geometry_Stream
,
3527 d2d_path_geometry_GetSegmentCount
,
3528 d2d_path_geometry_GetFigureCount
,
3531 void d2d_path_geometry_init(struct d2d_geometry
*geometry
, ID2D1Factory
*factory
)
3533 d2d_geometry_init(geometry
, factory
, &identity
, (ID2D1GeometryVtbl
*)&d2d_path_geometry_vtbl
);
3534 geometry
->u
.path
.ID2D1GeometrySink_iface
.lpVtbl
= &d2d_geometry_sink_vtbl
;
3535 geometry
->u
.path
.bounds
.left
= FLT_MAX
;
3536 geometry
->u
.path
.bounds
.right
= -FLT_MAX
;
3537 geometry
->u
.path
.bounds
.top
= FLT_MAX
;
3538 geometry
->u
.path
.bounds
.bottom
= -FLT_MAX
;
3541 static inline struct d2d_geometry
*impl_from_ID2D1RectangleGeometry(ID2D1RectangleGeometry
*iface
)
3543 return CONTAINING_RECORD(iface
, struct d2d_geometry
, ID2D1Geometry_iface
);
3546 static HRESULT STDMETHODCALLTYPE
d2d_rectangle_geometry_QueryInterface(ID2D1RectangleGeometry
*iface
,
3547 REFIID iid
, void **out
)
3549 TRACE("iface %p, iid %s, out %p.\n", iface
, debugstr_guid(iid
), out
);
3551 if (IsEqualGUID(iid
, &IID_ID2D1RectangleGeometry
)
3552 || IsEqualGUID(iid
, &IID_ID2D1Geometry
)
3553 || IsEqualGUID(iid
, &IID_ID2D1Resource
)
3554 || IsEqualGUID(iid
, &IID_IUnknown
))
3556 ID2D1RectangleGeometry_AddRef(iface
);
3561 WARN("%s not implemented, returning E_NOINTERFACE.\n", debugstr_guid(iid
));
3564 return E_NOINTERFACE
;
3567 static ULONG STDMETHODCALLTYPE
d2d_rectangle_geometry_AddRef(ID2D1RectangleGeometry
*iface
)
3569 struct d2d_geometry
*geometry
= impl_from_ID2D1RectangleGeometry(iface
);
3570 ULONG refcount
= InterlockedIncrement(&geometry
->refcount
);
3572 TRACE("%p increasing refcount to %u.\n", iface
, refcount
);
3577 static ULONG STDMETHODCALLTYPE
d2d_rectangle_geometry_Release(ID2D1RectangleGeometry
*iface
)
3579 struct d2d_geometry
*geometry
= impl_from_ID2D1RectangleGeometry(iface
);
3580 ULONG refcount
= InterlockedDecrement(&geometry
->refcount
);
3582 TRACE("%p decreasing refcount to %u.\n", iface
, refcount
);
3586 d2d_geometry_cleanup(geometry
);
3587 HeapFree(GetProcessHeap(), 0, geometry
);
3593 static void STDMETHODCALLTYPE
d2d_rectangle_geometry_GetFactory(ID2D1RectangleGeometry
*iface
, ID2D1Factory
**factory
)
3595 struct d2d_geometry
*geometry
= impl_from_ID2D1RectangleGeometry(iface
);
3597 TRACE("iface %p, factory %p.\n", iface
, factory
);
3599 ID2D1Factory_AddRef(*factory
= geometry
->factory
);
3602 static HRESULT STDMETHODCALLTYPE
d2d_rectangle_geometry_GetBounds(ID2D1RectangleGeometry
*iface
,
3603 const D2D1_MATRIX_3X2_F
*transform
, D2D1_RECT_F
*bounds
)
3605 struct d2d_geometry
*geometry
= impl_from_ID2D1RectangleGeometry(iface
);
3609 TRACE("iface %p, transform %p, bounds %p.\n", iface
, transform
, bounds
);
3611 rect
= &geometry
->u
.rectangle
.rect
;
3618 bounds
->left
= FLT_MAX
;
3619 bounds
->top
= FLT_MAX
;
3620 bounds
->right
= -FLT_MAX
;
3621 bounds
->bottom
= -FLT_MAX
;
3623 d2d_point_transform(&p
, transform
, rect
->left
, rect
->top
);
3624 d2d_rect_expand(bounds
, &p
);
3625 d2d_point_transform(&p
, transform
, rect
->left
, rect
->bottom
);
3626 d2d_rect_expand(bounds
, &p
);
3627 d2d_point_transform(&p
, transform
, rect
->right
, rect
->bottom
);
3628 d2d_rect_expand(bounds
, &p
);
3629 d2d_point_transform(&p
, transform
, rect
->right
, rect
->top
);
3630 d2d_rect_expand(bounds
, &p
);
3635 static HRESULT STDMETHODCALLTYPE
d2d_rectangle_geometry_GetWidenedBounds(ID2D1RectangleGeometry
*iface
,
3636 float stroke_width
, ID2D1StrokeStyle
*stroke_style
, const D2D1_MATRIX_3X2_F
*transform
,
3637 float tolerance
, D2D1_RECT_F
*bounds
)
3639 FIXME("iface %p, stroke_width %.8e, stroke_style %p, transform %p, tolerance %.8e, bounds %p stub!\n",
3640 iface
, stroke_width
, stroke_style
, transform
, tolerance
, bounds
);
3645 static HRESULT STDMETHODCALLTYPE
d2d_rectangle_geometry_StrokeContainsPoint(ID2D1RectangleGeometry
*iface
,
3646 D2D1_POINT_2F point
, float stroke_width
, ID2D1StrokeStyle
*stroke_style
, const D2D1_MATRIX_3X2_F
*transform
,
3647 float tolerance
, BOOL
*contains
)
3649 FIXME("iface %p, point {%.8e, %.8e}, stroke_width %.8e, stroke_style %p, "
3650 "transform %p, tolerance %.8e, contains %p stub!\n",
3651 iface
, point
.x
, point
.y
, stroke_width
, stroke_style
, transform
, tolerance
, contains
);
3656 static HRESULT STDMETHODCALLTYPE
d2d_rectangle_geometry_FillContainsPoint(ID2D1RectangleGeometry
*iface
,
3657 D2D1_POINT_2F point
, const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, BOOL
*contains
)
3659 struct d2d_geometry
*geometry
= impl_from_ID2D1RectangleGeometry(iface
);
3660 D2D1_RECT_F
*rect
= &geometry
->u
.rectangle
.rect
;
3663 TRACE("iface %p, point {%.8e, %.8e}, transform %p, tolerance %.8e, contains %p.\n",
3664 iface
, point
.x
, point
.y
, transform
, tolerance
, contains
);
3668 D2D1_MATRIX_3X2_F g_i
;
3670 if (!d2d_matrix_invert(&g_i
, transform
))
3671 return D2DERR_UNSUPPORTED_OPERATION
;
3672 d2d_point_transform(&point
, &g_i
, point
.x
, point
.y
);
3675 if (tolerance
== 0.0f
)
3676 tolerance
= D2D1_DEFAULT_FLATTENING_TOLERANCE
;
3678 dx
= max(fabsf((rect
->right
+ rect
->left
) / 2.0f
- point
.x
) - (rect
->right
- rect
->left
) / 2.0f
, 0.0f
);
3679 dy
= max(fabsf((rect
->bottom
+ rect
->top
) / 2.0f
- point
.y
) - (rect
->bottom
- rect
->top
) / 2.0f
, 0.0f
);
3681 *contains
= tolerance
* tolerance
> (dx
* dx
+ dy
* dy
);
3685 static HRESULT STDMETHODCALLTYPE
d2d_rectangle_geometry_CompareWithGeometry(ID2D1RectangleGeometry
*iface
,
3686 ID2D1Geometry
*geometry
, const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, D2D1_GEOMETRY_RELATION
*relation
)
3688 FIXME("iface %p, geometry %p, transform %p, tolerance %.8e, relation %p stub!\n",
3689 iface
, geometry
, transform
, tolerance
, relation
);
3694 static HRESULT STDMETHODCALLTYPE
d2d_rectangle_geometry_Simplify(ID2D1RectangleGeometry
*iface
,
3695 D2D1_GEOMETRY_SIMPLIFICATION_OPTION option
, const D2D1_MATRIX_3X2_F
*transform
, float tolerance
,
3696 ID2D1SimplifiedGeometrySink
*sink
)
3698 struct d2d_geometry
*geometry
= impl_from_ID2D1RectangleGeometry(iface
);
3699 D2D1_RECT_F
*rect
= &geometry
->u
.rectangle
.rect
;
3703 TRACE("iface %p, option %#x, transform %p, tolerance %.8e, sink %p.\n",
3704 iface
, option
, transform
, tolerance
, sink
);
3706 d2d_point_set(&p
[0], rect
->left
, rect
->top
);
3707 d2d_point_set(&p
[1], rect
->right
, rect
->top
);
3708 d2d_point_set(&p
[2], rect
->right
, rect
->bottom
);
3709 d2d_point_set(&p
[3], rect
->left
, rect
->bottom
);
3713 for (i
= 0; i
< ARRAY_SIZE(p
); ++i
)
3715 d2d_point_transform(&p
[i
], transform
, p
[i
].x
, p
[i
].y
);
3719 ID2D1SimplifiedGeometrySink_SetFillMode(sink
, D2D1_FILL_MODE_ALTERNATE
);
3720 ID2D1SimplifiedGeometrySink_BeginFigure(sink
, p
[0], D2D1_FIGURE_BEGIN_FILLED
);
3721 ID2D1SimplifiedGeometrySink_AddLines(sink
, &p
[1], 3);
3722 ID2D1SimplifiedGeometrySink_EndFigure(sink
, D2D1_FIGURE_END_CLOSED
);
3727 static HRESULT STDMETHODCALLTYPE
d2d_rectangle_geometry_Tessellate(ID2D1RectangleGeometry
*iface
,
3728 const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, ID2D1TessellationSink
*sink
)
3730 FIXME("iface %p, transform %p, tolerance %.8e, sink %p stub!\n", iface
, transform
, tolerance
, sink
);
3735 static HRESULT STDMETHODCALLTYPE
d2d_rectangle_geometry_CombineWithGeometry(ID2D1RectangleGeometry
*iface
,
3736 ID2D1Geometry
*geometry
, D2D1_COMBINE_MODE combine_mode
, const D2D1_MATRIX_3X2_F
*transform
,
3737 float tolerance
, ID2D1SimplifiedGeometrySink
*sink
)
3739 FIXME("iface %p, geometry %p, combine_mode %#x, transform %p, tolerance %.8e, sink %p stub!\n",
3740 iface
, geometry
, combine_mode
, transform
, tolerance
, sink
);
3745 static HRESULT STDMETHODCALLTYPE
d2d_rectangle_geometry_Outline(ID2D1RectangleGeometry
*iface
,
3746 const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, ID2D1SimplifiedGeometrySink
*sink
)
3748 FIXME("iface %p, transform %p, tolerance %.8e, sink %p stub!\n", iface
, transform
, tolerance
, sink
);
3753 static HRESULT STDMETHODCALLTYPE
d2d_rectangle_geometry_ComputeArea(ID2D1RectangleGeometry
*iface
,
3754 const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, float *area
)
3756 FIXME("iface %p, transform %p, tolerance %.8e, area %p stub!\n", iface
, transform
, tolerance
, area
);
3761 static HRESULT STDMETHODCALLTYPE
d2d_rectangle_geometry_ComputeLength(ID2D1RectangleGeometry
*iface
,
3762 const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, float *length
)
3764 FIXME("iface %p, transform %p, tolerance %.8e, length %p stub!\n", iface
, transform
, tolerance
, length
);
3769 static HRESULT STDMETHODCALLTYPE
d2d_rectangle_geometry_ComputePointAtLength(ID2D1RectangleGeometry
*iface
,
3770 float length
, const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, D2D1_POINT_2F
*point
,
3771 D2D1_POINT_2F
*tangent
)
3773 FIXME("iface %p, length %.8e, transform %p, tolerance %.8e, point %p, tangent %p stub!\n",
3774 iface
, length
, transform
, tolerance
, point
, tangent
);
3779 static HRESULT STDMETHODCALLTYPE
d2d_rectangle_geometry_Widen(ID2D1RectangleGeometry
*iface
, float stroke_width
,
3780 ID2D1StrokeStyle
*stroke_style
, const D2D1_MATRIX_3X2_F
*transform
, float tolerance
,
3781 ID2D1SimplifiedGeometrySink
*sink
)
3783 FIXME("iface %p, stroke_width %.8e, stroke_style %p, transform %p, tolerance %.8e, sink %p stub!\n",
3784 iface
, stroke_width
, stroke_style
, transform
, tolerance
, sink
);
3789 static void STDMETHODCALLTYPE
d2d_rectangle_geometry_GetRect(ID2D1RectangleGeometry
*iface
, D2D1_RECT_F
*rect
)
3791 struct d2d_geometry
*geometry
= impl_from_ID2D1RectangleGeometry(iface
);
3793 TRACE("iface %p, rect %p.\n", iface
, rect
);
3795 *rect
= geometry
->u
.rectangle
.rect
;
3798 static const struct ID2D1RectangleGeometryVtbl d2d_rectangle_geometry_vtbl
=
3800 d2d_rectangle_geometry_QueryInterface
,
3801 d2d_rectangle_geometry_AddRef
,
3802 d2d_rectangle_geometry_Release
,
3803 d2d_rectangle_geometry_GetFactory
,
3804 d2d_rectangle_geometry_GetBounds
,
3805 d2d_rectangle_geometry_GetWidenedBounds
,
3806 d2d_rectangle_geometry_StrokeContainsPoint
,
3807 d2d_rectangle_geometry_FillContainsPoint
,
3808 d2d_rectangle_geometry_CompareWithGeometry
,
3809 d2d_rectangle_geometry_Simplify
,
3810 d2d_rectangle_geometry_Tessellate
,
3811 d2d_rectangle_geometry_CombineWithGeometry
,
3812 d2d_rectangle_geometry_Outline
,
3813 d2d_rectangle_geometry_ComputeArea
,
3814 d2d_rectangle_geometry_ComputeLength
,
3815 d2d_rectangle_geometry_ComputePointAtLength
,
3816 d2d_rectangle_geometry_Widen
,
3817 d2d_rectangle_geometry_GetRect
,
3820 HRESULT
d2d_rectangle_geometry_init(struct d2d_geometry
*geometry
, ID2D1Factory
*factory
, const D2D1_RECT_F
*rect
)
3826 d2d_geometry_init(geometry
, factory
, &identity
, (ID2D1GeometryVtbl
*)&d2d_rectangle_geometry_vtbl
);
3827 geometry
->u
.rectangle
.rect
= *rect
;
3829 if (!(geometry
->fill
.vertices
= HeapAlloc(GetProcessHeap(), 0, 4 * sizeof(*geometry
->fill
.vertices
))))
3831 if (!d2d_array_reserve((void **)&geometry
->fill
.faces
,
3832 &geometry
->fill
.faces_size
, 2, sizeof(*geometry
->fill
.faces
)))
3835 l
= min(rect
->left
, rect
->right
);
3836 r
= max(rect
->left
, rect
->right
);
3837 t
= min(rect
->top
, rect
->bottom
);
3838 b
= max(rect
->top
, rect
->bottom
);
3840 v
= geometry
->fill
.vertices
;
3841 d2d_point_set(&v
[0], l
, t
);
3842 d2d_point_set(&v
[1], l
, b
);
3843 d2d_point_set(&v
[2], r
, b
);
3844 d2d_point_set(&v
[3], r
, t
);
3845 geometry
->fill
.vertex_count
= 4;
3847 f
= geometry
->fill
.faces
;
3848 d2d_face_set(&f
[0], 1, 2, 0);
3849 d2d_face_set(&f
[1], 0, 2, 3);
3850 geometry
->fill
.face_count
= 2;
3852 if (!d2d_geometry_outline_add_line_segment(geometry
, &v
[0], &v
[1]))
3854 if (!d2d_geometry_outline_add_line_segment(geometry
, &v
[1], &v
[2]))
3856 if (!d2d_geometry_outline_add_line_segment(geometry
, &v
[2], &v
[3]))
3858 if (!d2d_geometry_outline_add_line_segment(geometry
, &v
[3], &v
[0]))
3861 if (!d2d_geometry_outline_add_join(geometry
, &v
[3], &v
[0], &v
[1]))
3863 if (!d2d_geometry_outline_add_join(geometry
, &v
[0], &v
[1], &v
[2]))
3865 if (!d2d_geometry_outline_add_join(geometry
, &v
[1], &v
[2], &v
[3]))
3867 if (!d2d_geometry_outline_add_join(geometry
, &v
[2], &v
[3], &v
[0]))
3873 d2d_geometry_cleanup(geometry
);
3874 return E_OUTOFMEMORY
;
3877 static inline struct d2d_geometry
*impl_from_ID2D1TransformedGeometry(ID2D1TransformedGeometry
*iface
)
3879 return CONTAINING_RECORD(iface
, struct d2d_geometry
, ID2D1Geometry_iface
);
3882 static HRESULT STDMETHODCALLTYPE
d2d_transformed_geometry_QueryInterface(ID2D1TransformedGeometry
*iface
,
3883 REFIID iid
, void **out
)
3885 TRACE("iface %p, iid %s, out %p.\n", iface
, debugstr_guid(iid
), out
);
3887 if (IsEqualGUID(iid
, &IID_ID2D1TransformedGeometry
)
3888 || IsEqualGUID(iid
, &IID_ID2D1Geometry
)
3889 || IsEqualGUID(iid
, &IID_ID2D1Resource
)
3890 || IsEqualGUID(iid
, &IID_IUnknown
))
3892 ID2D1TransformedGeometry_AddRef(iface
);
3897 WARN("%s not implemented, returning E_NOINTERFACE.\n", debugstr_guid(iid
));
3900 return E_NOINTERFACE
;
3903 static ULONG STDMETHODCALLTYPE
d2d_transformed_geometry_AddRef(ID2D1TransformedGeometry
*iface
)
3905 struct d2d_geometry
*geometry
= impl_from_ID2D1TransformedGeometry(iface
);
3906 ULONG refcount
= InterlockedIncrement(&geometry
->refcount
);
3908 TRACE("%p increasing refcount to %u.\n", iface
, refcount
);
3913 static ULONG STDMETHODCALLTYPE
d2d_transformed_geometry_Release(ID2D1TransformedGeometry
*iface
)
3915 struct d2d_geometry
*geometry
= impl_from_ID2D1TransformedGeometry(iface
);
3916 ULONG refcount
= InterlockedDecrement(&geometry
->refcount
);
3918 TRACE("%p decreasing refcount to %u.\n", iface
, refcount
);
3922 geometry
->outline
.bezier_faces
= NULL
;
3923 geometry
->outline
.beziers
= NULL
;
3924 geometry
->outline
.faces
= NULL
;
3925 geometry
->outline
.vertices
= NULL
;
3926 geometry
->fill
.bezier_vertices
= NULL
;
3927 geometry
->fill
.faces
= NULL
;
3928 geometry
->fill
.vertices
= NULL
;
3929 ID2D1Geometry_Release(geometry
->u
.transformed
.src_geometry
);
3930 d2d_geometry_cleanup(geometry
);
3931 HeapFree(GetProcessHeap(), 0, geometry
);
3937 static void STDMETHODCALLTYPE
d2d_transformed_geometry_GetFactory(ID2D1TransformedGeometry
*iface
,
3938 ID2D1Factory
**factory
)
3940 struct d2d_geometry
*geometry
= impl_from_ID2D1TransformedGeometry(iface
);
3942 TRACE("iface %p, factory %p.\n", iface
, factory
);
3944 ID2D1Factory_AddRef(*factory
= geometry
->factory
);
3947 static HRESULT STDMETHODCALLTYPE
d2d_transformed_geometry_GetBounds(ID2D1TransformedGeometry
*iface
,
3948 const D2D1_MATRIX_3X2_F
*transform
, D2D1_RECT_F
*bounds
)
3950 struct d2d_geometry
*geometry
= impl_from_ID2D1TransformedGeometry(iface
);
3951 D2D1_MATRIX_3X2_F g
;
3953 TRACE("iface %p, transform %p, bounds %p.\n", iface
, transform
, bounds
);
3955 g
= geometry
->transform
;
3957 d2d_matrix_multiply(&g
, transform
);
3959 return ID2D1Geometry_GetBounds(geometry
->u
.transformed
.src_geometry
, &g
, bounds
);
3962 static HRESULT STDMETHODCALLTYPE
d2d_transformed_geometry_GetWidenedBounds(ID2D1TransformedGeometry
*iface
,
3963 float stroke_width
, ID2D1StrokeStyle
*stroke_style
, const D2D1_MATRIX_3X2_F
*transform
,
3964 float tolerance
, D2D1_RECT_F
*bounds
)
3966 FIXME("iface %p, stroke_width %.8e, stroke_style %p, transform %p, tolerance %.8e, bounds %p stub!\n",
3967 iface
, stroke_width
, stroke_style
, transform
, tolerance
, bounds
);
3972 static HRESULT STDMETHODCALLTYPE
d2d_transformed_geometry_StrokeContainsPoint(ID2D1TransformedGeometry
*iface
,
3973 D2D1_POINT_2F point
, float stroke_width
, ID2D1StrokeStyle
*stroke_style
, const D2D1_MATRIX_3X2_F
*transform
,
3974 float tolerance
, BOOL
*contains
)
3976 struct d2d_geometry
*geometry
= impl_from_ID2D1TransformedGeometry(iface
);
3977 D2D1_MATRIX_3X2_F g
;
3979 TRACE("iface %p, point {%.8e, %.8e}, stroke_width %.8e, stroke_style %p, "
3980 "transform %p, tolerance %.8e, contains %p.\n",
3981 iface
, point
.x
, point
.y
, stroke_width
, stroke_style
, transform
, tolerance
, contains
);
3983 g
= geometry
->transform
;
3985 d2d_matrix_multiply(&g
, transform
);
3987 return ID2D1Geometry_StrokeContainsPoint(geometry
->u
.transformed
.src_geometry
, point
, stroke_width
, stroke_style
,
3988 &g
, tolerance
, contains
);
3991 static HRESULT STDMETHODCALLTYPE
d2d_transformed_geometry_FillContainsPoint(ID2D1TransformedGeometry
*iface
,
3992 D2D1_POINT_2F point
, const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, BOOL
*contains
)
3994 struct d2d_geometry
*geometry
= impl_from_ID2D1TransformedGeometry(iface
);
3995 D2D1_MATRIX_3X2_F g
;
3997 TRACE("iface %p, point {%.8e, %.8e}, transform %p, tolerance %.8e, contains %p.\n",
3998 iface
, point
.x
, point
.y
, transform
, tolerance
, contains
);
4000 g
= geometry
->transform
;
4002 d2d_matrix_multiply(&g
, transform
);
4004 return ID2D1Geometry_FillContainsPoint(geometry
->u
.transformed
.src_geometry
, point
, &g
, tolerance
, contains
);
4007 static HRESULT STDMETHODCALLTYPE
d2d_transformed_geometry_CompareWithGeometry(ID2D1TransformedGeometry
*iface
,
4008 ID2D1Geometry
*geometry
, const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, D2D1_GEOMETRY_RELATION
*relation
)
4010 FIXME("iface %p, geometry %p, transform %p, tolerance %.8e, relation %p stub!\n",
4011 iface
, geometry
, transform
, tolerance
, relation
);
4016 static HRESULT STDMETHODCALLTYPE
d2d_transformed_geometry_Simplify(ID2D1TransformedGeometry
*iface
,
4017 D2D1_GEOMETRY_SIMPLIFICATION_OPTION option
, const D2D1_MATRIX_3X2_F
*transform
, float tolerance
,
4018 ID2D1SimplifiedGeometrySink
*sink
)
4020 struct d2d_geometry
*geometry
= impl_from_ID2D1TransformedGeometry(iface
);
4021 D2D1_MATRIX_3X2_F g
;
4023 TRACE("iface %p, option %#x, transform %p, tolerance %.8e, sink %p.\n",
4024 iface
, option
, transform
, tolerance
, sink
);
4026 g
= geometry
->transform
;
4028 d2d_matrix_multiply(&g
, transform
);
4030 return ID2D1Geometry_Simplify(geometry
->u
.transformed
.src_geometry
, option
, &g
, tolerance
, sink
);
4033 static HRESULT STDMETHODCALLTYPE
d2d_transformed_geometry_Tessellate(ID2D1TransformedGeometry
*iface
,
4034 const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, ID2D1TessellationSink
*sink
)
4036 FIXME("iface %p, transform %p, tolerance %.8e, sink %p stub!\n", iface
, transform
, tolerance
, sink
);
4041 static HRESULT STDMETHODCALLTYPE
d2d_transformed_geometry_CombineWithGeometry(ID2D1TransformedGeometry
*iface
,
4042 ID2D1Geometry
*geometry
, D2D1_COMBINE_MODE combine_mode
, const D2D1_MATRIX_3X2_F
*transform
,
4043 float tolerance
, ID2D1SimplifiedGeometrySink
*sink
)
4045 FIXME("iface %p, geometry %p, combine_mode %#x, transform %p, tolerance %.8e, sink %p stub!\n",
4046 iface
, geometry
, combine_mode
, transform
, tolerance
, sink
);
4051 static HRESULT STDMETHODCALLTYPE
d2d_transformed_geometry_Outline(ID2D1TransformedGeometry
*iface
,
4052 const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, ID2D1SimplifiedGeometrySink
*sink
)
4054 FIXME("iface %p, transform %p, tolerance %.8e, sink %p stub!\n", iface
, transform
, tolerance
, sink
);
4059 static HRESULT STDMETHODCALLTYPE
d2d_transformed_geometry_ComputeArea(ID2D1TransformedGeometry
*iface
,
4060 const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, float *area
)
4062 FIXME("iface %p, transform %p, tolerance %.8e, area %p stub!\n", iface
, transform
, tolerance
, area
);
4067 static HRESULT STDMETHODCALLTYPE
d2d_transformed_geometry_ComputeLength(ID2D1TransformedGeometry
*iface
,
4068 const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, float *length
)
4070 FIXME("iface %p, transform %p, tolerance %.8e, length %p stub!\n", iface
, transform
, tolerance
, length
);
4075 static HRESULT STDMETHODCALLTYPE
d2d_transformed_geometry_ComputePointAtLength(ID2D1TransformedGeometry
*iface
,
4076 float length
, const D2D1_MATRIX_3X2_F
*transform
, float tolerance
, D2D1_POINT_2F
*point
,
4077 D2D1_POINT_2F
*tangent
)
4079 FIXME("iface %p, length %.8e, transform %p, tolerance %.8e, point %p, tangent %p stub!\n",
4080 iface
, length
, transform
, tolerance
, point
, tangent
);
4085 static HRESULT STDMETHODCALLTYPE
d2d_transformed_geometry_Widen(ID2D1TransformedGeometry
*iface
, float stroke_width
,
4086 ID2D1StrokeStyle
*stroke_style
, const D2D1_MATRIX_3X2_F
*transform
, float tolerance
,
4087 ID2D1SimplifiedGeometrySink
*sink
)
4089 FIXME("iface %p, stroke_width %.8e, stroke_style %p, transform %p, tolerance %.8e, sink %p stub!\n",
4090 iface
, stroke_width
, stroke_style
, transform
, tolerance
, sink
);
4095 static void STDMETHODCALLTYPE
d2d_transformed_geometry_GetSourceGeometry(ID2D1TransformedGeometry
*iface
,
4096 ID2D1Geometry
**src_geometry
)
4098 struct d2d_geometry
*geometry
= impl_from_ID2D1TransformedGeometry(iface
);
4100 TRACE("iface %p, src_geometry %p.\n", iface
, src_geometry
);
4102 ID2D1Geometry_AddRef(*src_geometry
= geometry
->u
.transformed
.src_geometry
);
4105 static void STDMETHODCALLTYPE
d2d_transformed_geometry_GetTransform(ID2D1TransformedGeometry
*iface
,
4106 D2D1_MATRIX_3X2_F
*transform
)
4108 struct d2d_geometry
*geometry
= impl_from_ID2D1TransformedGeometry(iface
);
4110 TRACE("iface %p, transform %p.\n", iface
, transform
);
4112 *transform
= geometry
->u
.transformed
.transform
;
4115 static const struct ID2D1TransformedGeometryVtbl d2d_transformed_geometry_vtbl
=
4117 d2d_transformed_geometry_QueryInterface
,
4118 d2d_transformed_geometry_AddRef
,
4119 d2d_transformed_geometry_Release
,
4120 d2d_transformed_geometry_GetFactory
,
4121 d2d_transformed_geometry_GetBounds
,
4122 d2d_transformed_geometry_GetWidenedBounds
,
4123 d2d_transformed_geometry_StrokeContainsPoint
,
4124 d2d_transformed_geometry_FillContainsPoint
,
4125 d2d_transformed_geometry_CompareWithGeometry
,
4126 d2d_transformed_geometry_Simplify
,
4127 d2d_transformed_geometry_Tessellate
,
4128 d2d_transformed_geometry_CombineWithGeometry
,
4129 d2d_transformed_geometry_Outline
,
4130 d2d_transformed_geometry_ComputeArea
,
4131 d2d_transformed_geometry_ComputeLength
,
4132 d2d_transformed_geometry_ComputePointAtLength
,
4133 d2d_transformed_geometry_Widen
,
4134 d2d_transformed_geometry_GetSourceGeometry
,
4135 d2d_transformed_geometry_GetTransform
,
4138 void d2d_transformed_geometry_init(struct d2d_geometry
*geometry
, ID2D1Factory
*factory
,
4139 ID2D1Geometry
*src_geometry
, const D2D_MATRIX_3X2_F
*transform
)
4141 struct d2d_geometry
*src_impl
;
4144 src_impl
= unsafe_impl_from_ID2D1Geometry(src_geometry
);
4146 g
= src_impl
->transform
;
4147 d2d_matrix_multiply(&g
, transform
);
4148 d2d_geometry_init(geometry
, factory
, &g
, (ID2D1GeometryVtbl
*)&d2d_transformed_geometry_vtbl
);
4149 ID2D1Geometry_AddRef(geometry
->u
.transformed
.src_geometry
= src_geometry
);
4150 geometry
->u
.transformed
.transform
= *transform
;
4151 geometry
->fill
= src_impl
->fill
;
4152 geometry
->outline
= src_impl
->outline
;
4155 struct d2d_geometry
*unsafe_impl_from_ID2D1Geometry(ID2D1Geometry
*iface
)
4159 assert(iface
->lpVtbl
== (const ID2D1GeometryVtbl
*)&d2d_path_geometry_vtbl
4160 || iface
->lpVtbl
== (const ID2D1GeometryVtbl
*)&d2d_rectangle_geometry_vtbl
4161 || iface
->lpVtbl
== (const ID2D1GeometryVtbl
*)&d2d_transformed_geometry_vtbl
);
4162 return CONTAINING_RECORD(iface
, struct d2d_geometry
, ID2D1Geometry_iface
);