1544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin/************************************************************************** 2544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin * 3544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin * Copyright 2009 VMware, Inc. All Rights Reserved. 4544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin * 5544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin * Permission is hereby granted, free of charge, to any person obtaining a 6544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin * copy of this software and associated documentation files (the 7544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin * "Software"), to deal in the Software without restriction, including 8544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin * without limitation the rights to use, copy, modify, merge, publish, 9544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin * distribute, sub license, and/or sell copies of the Software, and to 10544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin * permit persons to whom the Software is furnished to do so, subject to 11544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin * the following conditions: 12544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin * 13544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin * The above copyright notice and this permission notice (including the 14544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin * next paragraph) shall be included in all copies or substantial portions 15544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin * of the Software. 16544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin * 17544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 18544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 19544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. 20544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR 21544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, 22544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE 23544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 24544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin * 25544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin **************************************************************************/ 26544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 27544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin#include "bezier.h" 28544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 29544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin#include "matrix.h" 30544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin#include "polygon.h" 31544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 32544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin#include "pipe/p_compiler.h" 33544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin#include "util/u_debug.h" 34544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 35544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin#include <stdlib.h> 36544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin#include <stdio.h> 37544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin#include <assert.h> 38544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin#include <math.h> 39544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 40544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusinstatic const float flatness = 0.5; 41544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 42544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 43544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusinstatic INLINE void split_left(struct bezier *bez, VGfloat t, struct bezier* left) 44544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin{ 45544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin left->x1 = bez->x1; 46544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin left->y1 = bez->y1; 47544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 48544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin left->x2 = bez->x1 + t * (bez->x2 - bez->x1); 49544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin left->y2 = bez->y1 + t * (bez->y2 - bez->y1); 50544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 51544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin left->x3 = bez->x2 + t * (bez->x3 - bez->x2); 52544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin left->y3 = bez->y2 + t * (bez->y3 - bez->y2); 53544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 54544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bez->x3 = bez->x3 + t * (bez->x4 - bez->x3); 55544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bez->y3 = bez->y3 + t * (bez->y4 - bez->y3); 56544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 57544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bez->x2 = left->x3 + t * (bez->x3 - left->x3); 58544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bez->y2 = left->y3 + t * (bez->y3 - left->y3); 59544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 60544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin left->x3 = left->x2 + t * (left->x3 - left->x2); 61544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin left->y3 = left->y2 + t * (left->y3 - left->y2); 62544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 63544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin left->x4 = bez->x1 = left->x3 + t * (bez->x2 - left->x3); 64544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin left->y4 = bez->y1 = left->y3 + t * (bez->y2 - left->y3); 65544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin} 66544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 67544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusinstatic INLINE void split(struct bezier *bez, 68544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin struct bezier *first_half, 69544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin struct bezier *second_half) 70544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin{ 71544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin double c = (bez->x2 + bez->x3) * 0.5; 72544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin first_half->x2 = (bez->x1 + bez->x2) * 0.5; 73544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin second_half->x3 = (bez->x3 + bez->x4) * 0.5; 74544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin first_half->x1 = bez->x1; 75544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin second_half->x4 = bez->x4; 76544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin first_half->x3 = (first_half->x2 + c) * 0.5; 77544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin second_half->x2 = (second_half->x3 + c) * 0.5; 78544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin first_half->x4 = second_half->x1 = 79544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin (first_half->x3 + second_half->x2) * 0.5; 80544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 81544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin c = (bez->y2 + bez->y3) / 2; 82544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin first_half->y2 = (bez->y1 + bez->y2) * 0.5; 83544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin second_half->y3 = (bez->y3 + bez->y4) * 0.5; 84544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin first_half->y1 = bez->y1; 85544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin second_half->y4 = bez->y4; 86544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin first_half->y3 = (first_half->y2 + c) * 0.5; 87544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin second_half->y2 = (second_half->y3 + c) * 0.5; 88544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin first_half->y4 = second_half->y1 = 89544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin (first_half->y3 + second_half->y2) * 0.5; 90544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin} 91544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 92544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusinstruct polygon * bezier_to_polygon(struct bezier *bez) 93544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin{ 94544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin struct polygon *poly = polygon_create(64); 95544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin polygon_vertex_append(poly, bez->x1, bez->y1); 96544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bezier_add_to_polygon(bez, poly); 97544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin return poly; 98544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin} 99544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 100544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusinvoid bezier_add_to_polygon(const struct bezier *bez, 101544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin struct polygon *poly) 102544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin{ 103544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin struct bezier beziers[32]; 104544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin struct bezier *b; 105544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 106544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin beziers[0] = *bez; 107544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin b = beziers; 108544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 109544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin while (b >= beziers) { 110544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin double y4y1 = b->y4 - b->y1; 111544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin double x4x1 = b->x4 - b->x1; 112544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin double l = ABS(x4x1) + ABS(y4y1); 113544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin double d; 114544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (l > 1.f) { 115544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin d = ABS((x4x1)*(b->y1 - b->y2) - (y4y1)*(b->x1 - b->x2)) 116544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin + ABS((x4x1)*(b->y1 - b->y3) - (y4y1)*(b->x1 - b->x3)); 117544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin } else { 118544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin d = ABS(b->x1 - b->x2) + ABS(b->y1 - b->y2) + 119544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin ABS(b->x1 - b->x3) + ABS(b->y1 - b->y3); 120544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin l = 1.; 121544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin } 122544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (d < flatness*l || b == beziers + 31) { 123544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin /* good enough, we pop it off and add the endpoint */ 124544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin polygon_vertex_append(poly, b->x4, b->y4); 125544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin --b; 126544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin } else { 127544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin /* split, second half of the bezier goes lower into the stack */ 128544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin split(b, b+1, b); 129544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin ++b; 130544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin } 131544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin } 132544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin} 133544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 134544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusinstatic void add_if_close(struct bezier *bez, VGfloat *length, VGfloat error) 135544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin{ 136544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin struct bezier left, right; /* bez poly splits */ 137544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin VGfloat len = 0.0; /* arc length */ 138544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin VGfloat chord; /* chord length */ 139544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 140544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin len = len + line_length(bez->x1, bez->y1, bez->x2, bez->y2); 141544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin len = len + line_length(bez->x2, bez->y2, bez->x3, bez->y3); 142544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin len = len + line_length(bez->x3, bez->y3, bez->x4, bez->y4); 143544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 144544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin chord = line_length(bez->x1, bez->y1, bez->x4, bez->y4); 145544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 146544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if ((len-chord) > error) { 147544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin split(bez, &left, &right); /* split in two */ 148544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin add_if_close(&left, length, error); /* try left side */ 149544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin add_if_close(&right, length, error); /* try right side */ 150544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin return; 151544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin } 152544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 153544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin *length = *length + len; 154544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 155544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin return; 156544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin} 157544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 158544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusinfloat bezier_length(struct bezier *bez, float error) 159544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin{ 160544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin VGfloat length = 0.f; 161544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 162544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin add_if_close(bez, &length, error); 163544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin return length; 164544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin} 165544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 166544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusinvoid bezier_init(struct bezier *bez, 167544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float x1, float y1, 168544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float x2, float y2, 169544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float x3, float y3, 170544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float x4, float y4) 171544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin{ 172544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bez->x1 = x1; 173544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bez->y1 = y1; 174544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bez->x2 = x2; 175544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bez->y2 = y2; 176544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bez->x3 = x3; 177544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bez->y3 = y3; 178544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bez->x4 = x4; 179544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bez->y4 = y4; 180544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin#if 0 181544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin debug_printf("bezier in [%f, %f, %f, %f, %f, %f]\n", 182544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin x1, y1, x2, y2, x3, y3, x4, y4); 183544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin#endif 184544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin} 185544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 186544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 187544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusinstatic INLINE void bezier_init2v(struct bezier *bez, 188544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float *pt1, 189544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float *pt2, 190544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float *pt3, 191544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float *pt4) 192544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin{ 193544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bez->x1 = pt1[0]; 194544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bez->y1 = pt1[1]; 195544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 196544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bez->x2 = pt2[0]; 197544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bez->y2 = pt2[1]; 198544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 199544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bez->x3 = pt3[0]; 200544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bez->y3 = pt3[1]; 201544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 202544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bez->x4 = pt4[0]; 203544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bez->y4 = pt4[1]; 204544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin} 205544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 206544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 207544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusinvoid bezier_transform(struct bezier *bez, 208544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin struct matrix *matrix) 209544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin{ 210544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin assert(matrix_is_affine(matrix)); 211544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin matrix_map_point(matrix, bez->x1, bez->y1, &bez->x1, &bez->y1); 212544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin matrix_map_point(matrix, bez->x2, bez->y2, &bez->x2, &bez->y2); 213544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin matrix_map_point(matrix, bez->x3, bez->y3, &bez->x3, &bez->y3); 214544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin matrix_map_point(matrix, bez->x4, bez->y4, &bez->x4, &bez->y4); 215544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin} 216544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 217544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusinstatic INLINE void bezier_point_at(const struct bezier *bez, float t, float *pt) 218544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin{ 219544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float a, b, c, d; 220544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float m_t; 221544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin m_t = 1. - t; 222544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin b = m_t * m_t; 223544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin c = t * t; 224544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin d = c * t; 225544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin a = b * m_t; 226544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin b *= 3. * t; 227544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin c *= 3. * m_t; 228544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin pt[0] = a*bez->x1 + b*bez->x2 + c*bez->x3 + d*bez->x4; 229544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin pt[1] = a*bez->y1 + b*bez->y2 + c*bez->y3 + d*bez->y4; 230544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin} 231544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 232544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusinstatic INLINE void bezier_normal_at(const struct bezier *bez, float t, float *norm) 233544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin{ 234544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float m_t = 1. - t; 235544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float a = m_t * m_t; 236544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float b = t * m_t; 237544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float c = t * t; 238544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 239544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin norm[0] = (bez->y2-bez->y1) * a + (bez->y3-bez->y2) * b + (bez->y4-bez->y3) * c; 240544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin norm[1] = -(bez->x2-bez->x1) * a - (bez->x3-bez->x2) * b - (bez->x4-bez->x3) * c; 241544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin} 242544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 243544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusinenum shift_result { 244544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin Ok, 245544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin Discard, 246544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin Split, 247544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin Circle 248544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin}; 249544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 250544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusinstatic enum shift_result good_offset(const struct bezier *b1, 251544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin const struct bezier *b2, 252544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float offset, float threshold) 253544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin{ 254544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin const float o2 = offset*offset; 255544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin const float max_dist_line = threshold*offset*offset; 256544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin const float max_dist_normal = threshold*offset; 257544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin const float spacing = 0.25; 258910b58039a3980d9857380cf367bdbe2395d791fAlan Hourihane float i; 259910b58039a3980d9857380cf367bdbe2395d791fAlan Hourihane for (i = spacing; i < 0.99; i += spacing) { 260544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float p1[2],p2[2], d, l; 261544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float normal[2]; 262544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bezier_point_at(b1, i, p1); 263544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bezier_point_at(b2, i, p2); 264544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin d = (p1[0] - p2[0])*(p1[0] - p2[0]) + (p1[1] - p2[1])*(p1[1] - p2[1]); 265544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (ABS(d - o2) > max_dist_line) 266544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin return Split; 267544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 268544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bezier_normal_at(b1, i, normal); 269544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin l = ABS(normal[0]) + ABS(normal[1]); 270544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (l != 0.) { 271544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin d = ABS(normal[0]*(p1[1] - p2[1]) - normal[1]*(p1[0] - p2[0]) ) / l; 272544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (d > max_dist_normal) 273544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin return Split; 274544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin } 275544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin } 276544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin return Ok; 277544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin} 278544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 279544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusinstatic INLINE void shift_line_by_normal(float *l, float offset) 280544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin{ 281544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float norm[4]; 282544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float tx, ty; 283544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 284544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin line_normal(l, norm); 285544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin line_normalize(norm); 286544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 287544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin tx = (norm[2] - norm[0]) * offset; 288544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin ty = (norm[3] - norm[1]) * offset; 289544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin l[0] += tx; l[1] += ty; 290544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin l[2] += tx; l[3] += ty; 291544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin} 292544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 293544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusinstatic INLINE VGboolean is_bezier_line(float (*points)[2], int count) 294544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin{ 295544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float dx13 = points[2][0] - points[0][0]; 296544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float dy13 = points[2][1] - points[0][1]; 297544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 298544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float dx12 = points[1][0] - points[0][0]; 299544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float dy12 = points[1][1] - points[0][1]; 300544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 301544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin debug_assert(count > 2); 302544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 303544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (count == 3) { 304544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin return floatsEqual(dx12 * dy13, dx13 * dy12); 305544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin } else if (count == 4) { 306544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float dx14 = points[3][0] - points[0][0]; 307544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float dy14 = points[3][1] - points[0][1]; 308544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 309544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin return (floatsEqual(dx12 * dy13, dx13 * dy12) && 310544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin floatsEqual(dx12 * dy14, dx14 * dy12)); 311544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin } 312544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 313544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin return VG_FALSE; 314544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin} 315544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 316544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusinstatic INLINE void compute_pt_normal(float *pt1, float *pt2, float *res) 317544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin{ 318544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float line[4]; 319544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float normal[4]; 320544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin line[0] = 0.f; line[1] = 0.f; 321544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin line[2] = pt2[0] - pt1[0]; 322544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin line[3] = pt2[1] - pt1[1]; 323544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin line_normal(line, normal); 324544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin line_normalize(normal); 325544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 326544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin res[0] = normal[2]; 327544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin res[1] = normal[3]; 328544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin} 329544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 330544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusinstatic enum shift_result shift(const struct bezier *orig, 331544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin struct bezier *shifted, 332544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float offset, float threshold) 333544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin{ 334910b58039a3980d9857380cf367bdbe2395d791fAlan Hourihane int i; 335544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin int map[4]; 336544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin VGboolean p1_p2_equal = (orig->x1 == orig->x2 && orig->y1 == orig->y2); 337544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin VGboolean p2_p3_equal = (orig->x2 == orig->x3 && orig->y2 == orig->y3); 338544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin VGboolean p3_p4_equal = (orig->x3 == orig->x4 && orig->y3 == orig->y4); 339544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 340544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float points[4][2]; 341544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin int np = 0; 342544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float bounds[4]; 343544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float points_shifted[4][2]; 344544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float prev_normal[2]; 345544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 346544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin points[np][0] = orig->x1; 347544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin points[np][1] = orig->y1; 348544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin map[0] = 0; 349544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin ++np; 350544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (!p1_p2_equal) { 351544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin points[np][0] = orig->x2; 352544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin points[np][1] = orig->y2; 353544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin ++np; 354544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin } 355544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin map[1] = np - 1; 356544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (!p2_p3_equal) { 357544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin points[np][0] = orig->x3; 358544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin points[np][1] = orig->y3; 359544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin ++np; 360544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin } 361544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin map[2] = np - 1; 362544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (!p3_p4_equal) { 363544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin points[np][0] = orig->x4; 364544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin points[np][1] = orig->y4; 365544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin ++np; 366544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin } 367544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin map[3] = np - 1; 368544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (np == 1) 369544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin return Discard; 370544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 371544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin /* We need to specialcase lines of 3 or 4 points due to numerical 372544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin instability in intersection code below */ 373544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (np > 2 && is_bezier_line(points, np)) { 374544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float l[4] = { points[0][0], points[0][1], 375544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin points[np-1][0], points[np-1][1] }; 376544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float ctrl1[2], ctrl2[2]; 377544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (floatsEqual(points[0][0], points[np-1][0]) && 378544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin floatsEqual(points[0][1], points[np-1][1])) 379544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin return Discard; 380544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 381544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin shift_line_by_normal(l, offset); 382544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin line_point_at(l, 0.33, ctrl1); 383544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin line_point_at(l, 0.66, ctrl2); 384544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bezier_init(shifted, l[0], l[1], 385544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin ctrl1[0], ctrl1[1], ctrl2[0], ctrl2[1], 386544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin l[2], l[3]); 387544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin return Ok; 388544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin } 389544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 390544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bezier_bounds(orig, bounds); 391544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (np == 4 && bounds[2] < .1*offset && bounds[3] < .1*offset) { 392544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float l = (orig->x1 - orig->x2)*(orig->x1 - orig->x2) + 393544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin (orig->y1 - orig->y2)*(orig->y1 - orig->y1) * 394544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin (orig->x3 - orig->x4)*(orig->x3 - orig->x4) + 395544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin (orig->y3 - orig->y4)*(orig->y3 - orig->y4); 396544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float dot = (orig->x1 - orig->x2)*(orig->x3 - orig->x4) + 397544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin (orig->y1 - orig->y2)*(orig->y3 - orig->y4); 398544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (dot < 0 && dot*dot < 0.8*l) 399544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin /* the points are close and reverse dirction. Approximate the whole 400544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin thing by a semi circle */ 401544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin return Circle; 402544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin } 403544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 404544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin compute_pt_normal(points[0], points[1], prev_normal); 405544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 406544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin points_shifted[0][0] = points[0][0] + offset * prev_normal[0]; 407544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin points_shifted[0][1] = points[0][1] + offset * prev_normal[1]; 408544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 409910b58039a3980d9857380cf367bdbe2395d791fAlan Hourihane for (i = 1; i < np - 1; ++i) { 410544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float normal_sum[2], r; 411544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float next_normal[2]; 412544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin compute_pt_normal(points[i], points[i + 1], next_normal); 413544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 414544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin normal_sum[0] = prev_normal[0] + next_normal[0]; 415544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin normal_sum[1] = prev_normal[1] + next_normal[1]; 416544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 417544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin r = 1.0 + prev_normal[0] * next_normal[0] 418544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin + prev_normal[1] * next_normal[1]; 419544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 420544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (floatsEqual(r + 1, 1)) { 421544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin points_shifted[i][0] = points[i][0] + offset * prev_normal[0]; 422544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin points_shifted[i][1] = points[i][1] + offset * prev_normal[1]; 423544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin } else { 424544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float k = offset / r; 425544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin points_shifted[i][0] = points[i][0] + k * normal_sum[0]; 426544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin points_shifted[i][1] = points[i][1] + k * normal_sum[1]; 427544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin } 428544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 429544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin prev_normal[0] = next_normal[0]; 430544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin prev_normal[1] = next_normal[1]; 431544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin } 432544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 433544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin points_shifted[np - 1][0] = points[np - 1][0] + offset * prev_normal[0]; 434544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin points_shifted[np - 1][1] = points[np - 1][1] + offset * prev_normal[1]; 435544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 436544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bezier_init2v(shifted, 437544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin points_shifted[map[0]], points_shifted[map[1]], 438544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin points_shifted[map[2]], points_shifted[map[3]]); 439544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 440544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin return good_offset(orig, shifted, offset, threshold); 441544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin} 442544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 443544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusinstatic VGboolean make_circle(const struct bezier *b, float offset, struct bezier *o) 444544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin{ 445544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float normals[3][2]; 446544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float dist; 447544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float angles[2]; 448544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float sign = 1.f; 449544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin int i; 450544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float circle[3][2]; 451544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 452544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin normals[0][0] = b->y2 - b->y1; 453544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin normals[0][1] = b->x1 - b->x2; 454544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin dist = sqrt(normals[0][0]*normals[0][0] + normals[0][1]*normals[0][1]); 455544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (floatsEqual(dist + 1, 1.f)) 456544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin return VG_FALSE; 457544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin normals[0][0] /= dist; 458544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin normals[0][1] /= dist; 459544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 460544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin normals[2][0] = b->y4 - b->y3; 461544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin normals[2][1] = b->x3 - b->x4; 462544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin dist = sqrt(normals[2][0]*normals[2][0] + normals[2][1]*normals[2][1]); 463544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (floatsEqual(dist + 1, 1.f)) 464544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin return VG_FALSE; 465544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin normals[2][0] /= dist; 466544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin normals[2][1] /= dist; 467544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 468544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin normals[1][0] = b->x1 - b->x2 - b->x3 + b->x4; 469544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin normals[1][1] = b->y1 - b->y2 - b->y3 + b->y4; 470544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin dist = -1*sqrt(normals[1][0]*normals[1][0] + normals[1][1]*normals[1][1]); 471544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin normals[1][0] /= dist; 472544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin normals[1][1] /= dist; 473544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 474544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin for (i = 0; i < 2; ++i) { 475544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float cos_a = normals[i][0]*normals[i+1][0] + normals[i][1]*normals[i+1][1]; 476544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (cos_a > 1.) 477544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin cos_a = 1.; 478544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (cos_a < -1.) 479544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin cos_a = -1; 480544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin angles[i] = acos(cos_a)/M_PI; 481544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin } 482544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 483544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (angles[0] + angles[1] > 1.) { 484544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin /* more than 180 degrees */ 485544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin normals[1][0] = -normals[1][0]; 486544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin normals[1][1] = -normals[1][1]; 487544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin angles[0] = 1. - angles[0]; 488544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin angles[1] = 1. - angles[1]; 489544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin sign = -1.; 490544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin } 491544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 492544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin circle[0][0] = b->x1 + normals[0][0]*offset; 493544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin circle[0][1] = b->y1 + normals[0][1]*offset; 494544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 495544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin circle[1][0] = 0.5*(b->x1 + b->x4) + normals[1][0]*offset; 496544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin circle[1][1] = 0.5*(b->y1 + b->y4) + normals[1][1]*offset; 497544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 498544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin circle[2][0] = b->x4 + normals[2][0]*offset; 499544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin circle[2][1] = b->y4 + normals[2][1]*offset; 500544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 501544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin for (i = 0; i < 2; ++i) { 502544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float kappa = 2.*KAPPA * sign * offset * angles[i]; 503544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 504544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin o->x1 = circle[i][0]; 505544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin o->y1 = circle[i][1]; 506544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin o->x2 = circle[i][0] - normals[i][1]*kappa; 507544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin o->y2 = circle[i][1] + normals[i][0]*kappa; 508544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin o->x3 = circle[i+1][0] + normals[i+1][1]*kappa; 509544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin o->y3 = circle[i+1][1] - normals[i+1][0]*kappa; 510544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin o->x4 = circle[i+1][0]; 511544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin o->y4 = circle[i+1][1]; 512544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 513544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin ++o; 514544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin } 515544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin return VG_TRUE; 516544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin} 517544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 518544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusinint bezier_translate_by_normal(struct bezier *bez, 519544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin struct bezier *curves, 520544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin int max_curves, 521544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float normal_len, 522544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float threshold) 523544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin{ 524544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin struct bezier beziers[10]; 525544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin struct bezier *b, *o; 526544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 527544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin /* fixme: this should really be floatsEqual */ 528544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (bez->x1 == bez->x2 && bez->x1 == bez->x3 && bez->x1 == bez->x4 && 529544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bez->y1 == bez->y2 && bez->y1 == bez->y3 && bez->y1 == bez->y4) 530544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin return 0; 531544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 532544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin --max_curves; 533544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusinredo: 534544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin beziers[0] = *bez; 535544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin b = beziers; 536544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin o = curves; 537544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 538544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin while (b >= beziers) { 539544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin int stack_segments = b - beziers + 1; 540544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin enum shift_result res; 541544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if ((stack_segments == 10) || (o - curves == max_curves - stack_segments)) { 542544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin threshold *= 1.5; 543544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (threshold > 2.) 544544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin goto give_up; 545544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin goto redo; 546544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin } 547544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin res = shift(b, o, normal_len, threshold); 548544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (res == Discard) { 549544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin --b; 550544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin } else if (res == Ok) { 551544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin ++o; 552544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin --b; 553544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin continue; 554544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin } else if (res == Circle && max_curves - (o - curves) >= 2) { 555544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin /* add semi circle */ 556544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (make_circle(b, normal_len, o)) 557544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin o += 2; 558544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin --b; 559544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin } else { 560544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin split(b, b+1, b); 561544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin ++b; 562544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin } 563544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin } 564544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 565544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusingive_up: 566544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin while (b >= beziers) { 567544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin enum shift_result res = shift(b, o, normal_len, threshold); 568544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 569544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin /* if res isn't Ok or Split then *o is undefined */ 570544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (res == Ok || res == Split) 571544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin ++o; 572544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 573544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin --b; 574544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin } 575544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 576544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin debug_assert(o - curves <= max_curves); 577544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin return o - curves; 578544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin} 579544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 580544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusinvoid bezier_bounds(const struct bezier *bez, 581544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float *bounds/*x/y/width/height*/) 582544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin{ 583544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float xmin = bez->x1; 584544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float xmax = bez->x1; 585544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float ymin = bez->y1; 586544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float ymax = bez->y1; 587544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 588544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (bez->x2 < xmin) 589544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin xmin = bez->x2; 590544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin else if (bez->x2 > xmax) 591544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin xmax = bez->x2; 592544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (bez->x3 < xmin) 593544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin xmin = bez->x3; 594544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin else if (bez->x3 > xmax) 595544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin xmax = bez->x3; 596544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (bez->x4 < xmin) 597544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin xmin = bez->x4; 598544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin else if (bez->x4 > xmax) 599544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin xmax = bez->x4; 600544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 601544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (bez->y2 < ymin) 602544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin ymin = bez->y2; 603544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin else if (bez->y2 > ymax) 604544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin ymax = bez->y2; 605544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (bez->y3 < ymin) 606544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin ymin = bez->y3; 607544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin else if (bez->y3 > ymax) 608544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin ymax = bez->y3; 609544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (bez->y4 < ymin) 610544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin ymin = bez->y4; 611544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin else if (bez->y4 > ymax) 612544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin ymax = bez->y4; 613544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 614544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bounds[0] = xmin; /* x */ 615544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bounds[1] = ymin; /* y */ 616544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bounds[2] = xmax - xmin; /* width */ 617544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bounds[3] = ymax - ymin; /* height */ 618544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin} 619544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 620544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusinvoid bezier_start_tangent(const struct bezier *bez, 621544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float *tangent) 622544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin{ 623544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin tangent[0] = bez->x1; 624544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin tangent[1] = bez->y1; 625544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin tangent[2] = bez->x2; 626544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin tangent[3] = bez->y2; 627544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 628544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (null_line(tangent)) { 629544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin tangent[0] = bez->x1; 630544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin tangent[1] = bez->y1; 631544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin tangent[2] = bez->x3; 632544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin tangent[3] = bez->y3; 633544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin } 634544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (null_line(tangent)) { 635544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin tangent[0] = bez->x1; 636544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin tangent[1] = bez->y1; 637544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin tangent[2] = bez->x4; 638544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin tangent[3] = bez->y4; 639544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin } 640544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin} 641544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 642544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 643544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusinstatic INLINE VGfloat bezier_t_at_length(struct bezier *bez, 644544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin VGfloat at_length, 645544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin VGfloat error) 646544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin{ 647544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin VGfloat len = bezier_length(bez, error); 648544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin VGfloat t = 1.0; 649544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin VGfloat last_bigger = 1.; 650544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 651544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (at_length > len || floatsEqual(at_length, len)) 652544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin return t; 653544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 654544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (floatIsZero(at_length)) 655544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin return 0.f; 656544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 657544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin t *= 0.5; 658544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin while (1) { 659544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin struct bezier right = *bez; 660544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin struct bezier left; 661544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin VGfloat tmp_len; 662544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin split_left(&right, t, &left); 663544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin tmp_len = bezier_length(&left, error); 664544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (ABS(tmp_len - at_length) < error) 665544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin break; 666544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 667544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin if (tmp_len < at_length) { 668544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin t += (last_bigger - t)*.5; 669544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin } else { 670544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin last_bigger = t; 671544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin t -= t*.5; 672544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin } 673544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin } 674544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin return t; 675544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin} 676544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 677544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusinvoid bezier_point_at_length(struct bezier *bez, 678544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float length, 679544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float *point, 680544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float *normal) 681544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin{ 682544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin /* ~0.000001 seems to be required to pass G2080x tests */ 683544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin VGfloat t = bezier_t_at_length(bez, length, 0.000001); 684544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bezier_point_at(bez, t, point); 685544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bezier_normal_at(bez, t, normal); 686544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin vector_unit(normal); 687544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin} 688544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 689544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusinvoid bezier_point_at_t(struct bezier *bez, float t, 690544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float *point, float *normal) 691544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin{ 692544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bezier_point_at(bez, t, point); 693544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bezier_normal_at(bez, t, normal); 694544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin vector_unit(normal); 695544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin} 696544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 697544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusinvoid bezier_exact_bounds(const struct bezier *bez, 698544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin float *bounds/*x/y/width/height*/) 699544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin{ 700544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin struct polygon *poly = polygon_create(64); 701544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin polygon_vertex_append(poly, bez->x1, bez->y1); 702544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin bezier_add_to_polygon(bez, poly); 703544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin polygon_bounding_rect(poly, bounds); 704544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin polygon_destroy(poly); 705544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin} 706544dd4b11f7be76bb00fe29a60eaf2772dcc69caZack Rusin 707