1/** <title>NSBezierPath.m</title> 2 3 <abstract>The NSBezierPath class</abstract> 4 5 Copyright (C) 1999, 2005 Free Software Foundation, Inc. 6 7 Author: Enrico Sersale <enrico@imago.ro> 8 Date: Dec 1999 9 Modified: Fred Kiefer <FredKiefer@gmx.de> 10 Date: January 2001 11 12 This file is part of the GNUstep GUI Library. 13 14 This library is free software; you can redistribute it and/or 15 modify it under the terms of the GNU Lesser General Public 16 License as published by the Free Software Foundation; either 17 version 2 of the License, or (at your option) any later version. 18 19 This library is distributed in the hope that it will be useful, 20 but WITHOUT ANY WARRANTY; without even the implied warranty of 21 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 22 Lesser General Public License for more details. 23 24 You should have received a copy of the GNU Lesser General Public 25 License along with this library; see the file COPYING.LIB. 26 If not, see <http://www.gnu.org/licenses/> or write to the 27 Free Software Foundation, 51 Franklin Street, Fifth Floor, 28 Boston, MA 02110-1301, USA. 29*/ 30 31#import <Foundation/NSData.h> 32#import <Foundation/NSDebug.h> 33#import "AppKit/NSAffineTransform.h" 34#import "AppKit/NSFont.h" 35#import "AppKit/NSImage.h" 36#import "AppKit/PSOperators.h" 37#import "GNUstepGUI/GSFontInfo.h" 38#import "GSGuiPrivate.h" 39 40#include <math.h> 41 42#ifndef M_PI 43#define M_PI 3.1415926535897932384626434 44#endif 45 46typedef struct _PathElement 47{ 48 /*NSBezierPathElement*/int type; 49 NSPoint points[3]; 50} PathElement; 51 52//#define GSUNION_TYPES GSUNION_OBJ 53#define GSI_ARRAY_TYPES 0 54#define GSI_ARRAY_TYPE PathElement 55 56#define GSI_ARRAY_NO_RETAIN 57#define GSI_ARRAY_NO_RELEASE 58 59#ifdef GSIArray 60#undef GSIArray 61#endif 62#include <GNUstepBase/GSIArray.h> 63 64#define _IN_NSBEZIERPATH_M 1 65#import "AppKit/NSBezierPath.h" 66#undef _IN_NSBEZIERPATH_M 67 68 69// This magic number is 4 *(sqrt(2) -1)/3 70#define KAPPA 0.5522847498 71#define INVALIDATE_CACHE() [self _invalidateCache] 72 73static void flatten(NSPoint coeff[], CGFloat flatness, NSBezierPath *path); 74 75static NSWindingRule default_winding_rule = NSNonZeroWindingRule; 76static CGFloat default_line_width = 1.0; 77static CGFloat default_flatness = 0.6; 78static NSLineJoinStyle default_line_join_style = NSMiterLineJoinStyle; 79static NSLineCapStyle default_line_cap_style = NSButtLineCapStyle; 80static CGFloat default_miter_limit = 10.0; 81 82@interface NSBezierPath (PrivateMethods) 83- (void)_invalidateCache; 84- (void)_recalculateBounds; 85@end 86 87 88#if 0 89@interface GSBezierPath : NSBezierPath 90{ 91 GSIArray pathElements; 92 BOOL flat; 93} 94@end 95#endif 96 97@implementation NSBezierPath 98 99+ (void)initialize 100{ 101 if (self == [NSBezierPath class]) 102 { 103 [self setVersion: 2]; 104 } 105} 106 107// 108// Creating common paths 109// 110+ (NSBezierPath *)bezierPath 111{ 112 return AUTORELEASE([[self alloc] init]); 113} 114 115+ (NSBezierPath *)bezierPathWithRect: (NSRect)aRect 116{ 117 NSBezierPath *path; 118 119 path = [self bezierPath]; 120 [path appendBezierPathWithRect: aRect]; 121 122 return path; 123} 124 125+ (NSBezierPath *)bezierPathWithOvalInRect: (NSRect)aRect 126{ 127 NSBezierPath *path; 128 129 path = [self bezierPath]; 130 [path appendBezierPathWithOvalInRect: aRect]; 131 132 return path; 133} 134 135+ (NSBezierPath *)bezierPathWithRoundedRect: (NSRect)aRect 136 xRadius: (CGFloat)xRadius 137 yRadius: (CGFloat)yRadius 138{ 139 NSBezierPath *path; 140 141 path = [self bezierPath]; 142 [path appendBezierPathWithRoundedRect: aRect 143 xRadius: xRadius 144 yRadius: yRadius]; 145 146 return path; 147} 148 149// 150// Immediate mode drawing of common paths 151// 152+ (void)fillRect: (NSRect)aRect 153{ 154 PSrectfill(NSMinX(aRect), NSMinY(aRect), NSWidth(aRect), NSHeight(aRect)); 155} 156 157+ (void)strokeRect: (NSRect)aRect 158{ 159 PSrectstroke(NSMinX(aRect), NSMinY(aRect), NSWidth(aRect), NSHeight(aRect)); 160} 161 162+ (void)clipRect: (NSRect)aRect 163{ 164 PSrectclip(NSMinX(aRect), NSMinY(aRect), NSWidth(aRect), NSHeight(aRect)); 165} 166 167+ (void)strokeLineFromPoint: (NSPoint)point1 toPoint: (NSPoint)point2 168{ 169 NSBezierPath *path = [[self alloc] init]; 170 171 [path moveToPoint: point1]; 172 [path lineToPoint: point2]; 173 [path stroke]; 174 RELEASE(path); 175} 176 177+ (void)drawPackedGlyphs: (const char *)packedGlyphs atPoint: (NSPoint)aPoint 178{ 179 NSBezierPath *path = [[self alloc] init]; 180 181 [path moveToPoint: aPoint]; 182 [path appendBezierPathWithPackedGlyphs: packedGlyphs]; 183 [path fill]; 184 RELEASE(path); 185} 186 187// 188// Default path rendering parameters 189// 190+ (void)setDefaultMiterLimit:(CGFloat)limit 191{ 192 default_miter_limit = limit; 193 // Do we need this? 194 PSsetmiterlimit(limit); 195} 196 197+ (CGFloat)defaultMiterLimit 198{ 199 return default_miter_limit; 200} 201 202+ (void)setDefaultFlatness:(CGFloat)flatness 203{ 204 default_flatness = flatness; 205 PSsetflat(flatness); 206} 207 208+ (CGFloat)defaultFlatness 209{ 210 return default_flatness; 211} 212 213+ (void)setDefaultWindingRule:(NSWindingRule)windingRule 214{ 215 default_winding_rule = windingRule; 216} 217 218+ (NSWindingRule)defaultWindingRule 219{ 220 return default_winding_rule; 221} 222 223+ (void)setDefaultLineCapStyle:(NSLineCapStyle)lineCapStyle 224{ 225 default_line_cap_style = lineCapStyle; 226 PSsetlinecap(lineCapStyle); 227} 228 229+ (NSLineCapStyle)defaultLineCapStyle 230{ 231 return default_line_cap_style; 232} 233 234+ (void)setDefaultLineJoinStyle:(NSLineJoinStyle)lineJoinStyle 235{ 236 default_line_join_style = lineJoinStyle; 237 PSsetlinejoin(lineJoinStyle); 238} 239 240+ (NSLineJoinStyle)defaultLineJoinStyle 241{ 242 return default_line_join_style; 243} 244 245+ (void)setDefaultLineWidth:(CGFloat)lineWidth 246{ 247 default_line_width = lineWidth; 248 PSsetlinewidth(lineWidth); 249} 250 251+ (CGFloat)defaultLineWidth 252{ 253 return default_line_width; 254} 255 256- (id) init 257{ 258 NSZone *zone; 259 260 self = [super init]; 261 if (self == nil) 262 return nil; 263 264 // Those values come from the default. 265 [self setLineWidth: default_line_width]; 266 [self setFlatness: default_flatness]; 267 [self setLineCapStyle: default_line_cap_style]; 268 [self setLineJoinStyle: default_line_join_style]; 269 [self setMiterLimit: default_miter_limit]; 270 [self setWindingRule: default_winding_rule]; 271 // Set by allocation 272 //_bounds = NSZeroRect; 273 //_controlPointBounds = NSZeroRect; 274 //_cachesBezierPath = NO; 275 //_cacheImage = nil; 276 //_dash_count = 0; 277 //_dash_phase = 0; 278 //_dash_pattern = NULL; 279 280 zone = [self zone]; 281 _pathElements = NSZoneMalloc(zone, sizeof(GSIArray_t)); 282 GSIArrayInitWithZoneAndCapacity(_pathElements, zone, 8); 283 _flat = YES; 284 285 return self; 286} 287 288- (void) dealloc 289{ 290 GSIArrayEmpty(_pathElements); 291 NSZoneFree([self zone], _pathElements); 292 293 if (_cacheImage != nil) 294 RELEASE(_cacheImage); 295 296 if (_dash_pattern != NULL) 297 NSZoneFree([self zone], _dash_pattern); 298 299 [super dealloc]; 300} 301 302// 303// Path construction 304// 305- (void)moveToPoint:(NSPoint)aPoint 306{ 307 PathElement elem; 308 309 elem.type = NSMoveToBezierPathElement; 310 elem.points[0] = aPoint; 311 elem.points[1] = NSZeroPoint; 312 elem.points[2] = NSZeroPoint; 313 GSIArrayAddItem(_pathElements, (GSIArrayItem)elem); 314 INVALIDATE_CACHE(); 315} 316 317- (void)lineToPoint:(NSPoint)aPoint 318{ 319 PathElement elem; 320 321 elem.type = NSLineToBezierPathElement; 322 elem.points[0] = aPoint; 323 elem.points[1] = NSZeroPoint; 324 elem.points[2] = NSZeroPoint; 325 GSIArrayAddItem(_pathElements, (GSIArrayItem)elem); 326 INVALIDATE_CACHE(); 327} 328 329- (void)curveToPoint:(NSPoint)aPoint 330 controlPoint1:(NSPoint)controlPoint1 331 controlPoint2:(NSPoint)controlPoint2 332{ 333 PathElement elem; 334 335 elem.type = NSCurveToBezierPathElement; 336 elem.points[0] = controlPoint1; 337 elem.points[1] = controlPoint2; 338 elem.points[2] = aPoint; 339 GSIArrayAddItem(_pathElements, (GSIArrayItem)elem); 340 _flat = NO; 341 342 INVALIDATE_CACHE(); 343} 344 345- (void)closePath 346{ 347 PathElement elem; 348 349 elem.type = NSClosePathBezierPathElement; 350 elem.points[0] = NSZeroPoint; 351 elem.points[1] = NSZeroPoint; 352 elem.points[2] = NSZeroPoint; 353 GSIArrayAddItem(_pathElements, (GSIArrayItem)elem); 354 INVALIDATE_CACHE(); 355} 356 357- (void)removeAllPoints 358{ 359 GSIArrayRemoveAllItems(_pathElements); 360 _flat = YES; 361 INVALIDATE_CACHE(); 362} 363 364// 365// Relative path construction 366// 367- (void)relativeMoveToPoint:(NSPoint)aPoint 368{ 369 NSPoint p = [self currentPoint]; 370 371 p.x = p.x + aPoint.x; 372 p.y = p.y + aPoint.y; 373 [self moveToPoint: p]; 374} 375 376- (void)relativeLineToPoint:(NSPoint)aPoint 377{ 378 NSPoint p = [self currentPoint]; 379 380 p.x = p.x + aPoint.x; 381 p.y = p.y + aPoint.y; 382 [self lineToPoint: p]; 383} 384 385- (void)relativeCurveToPoint:(NSPoint)aPoint 386 controlPoint1:(NSPoint)controlPoint1 387 controlPoint2:(NSPoint)controlPoint2 388{ 389 NSPoint p = [self currentPoint]; 390 391 aPoint.x = p.x + aPoint.x; 392 aPoint.y = p.y + aPoint.y; 393 controlPoint1.x = p.x + controlPoint1.x; 394 controlPoint1.y = p.y + controlPoint1.y; 395 controlPoint2.x = p.x + controlPoint2.x; 396 controlPoint2.y = p.y + controlPoint2.y; 397 [self curveToPoint: aPoint 398 controlPoint1: controlPoint1 399 controlPoint2: controlPoint2]; 400} 401 402// 403// Path rendering parameters 404// 405- (CGFloat)lineWidth 406{ 407 return _lineWidth; 408} 409 410- (void)setLineWidth:(CGFloat)lineWidth 411{ 412 _lineWidth = lineWidth; 413} 414 415- (NSLineCapStyle)lineCapStyle 416{ 417 return _lineCapStyle; 418} 419 420- (void)setLineCapStyle:(NSLineCapStyle)lineCapStyle 421{ 422 _lineCapStyle = lineCapStyle; 423} 424 425- (NSLineJoinStyle)lineJoinStyle 426{ 427 return _lineJoinStyle; 428} 429 430- (void)setLineJoinStyle:(NSLineJoinStyle)lineJoinStyle 431{ 432 _lineJoinStyle = lineJoinStyle; 433} 434 435- (NSWindingRule)windingRule 436{ 437 return _windingRule; 438} 439 440- (void)setWindingRule:(NSWindingRule)windingRule 441{ 442 _windingRule = windingRule; 443} 444 445- (void)setFlatness:(CGFloat)flatness 446{ 447 _flatness = flatness; 448} 449 450- (CGFloat)flatness 451{ 452 return _flatness; 453} 454 455- (void)setMiterLimit:(CGFloat)limit 456{ 457 _miterLimit = limit; 458} 459 460- (CGFloat)miterLimit 461{ 462 return _miterLimit; 463} 464 465- (void)getLineDash:(CGFloat *)pattern count:(NSInteger *)count phase:(CGFloat *)phase 466{ 467 // FIXME: How big is the pattern array? 468 // We assume that this value is in count! 469 if (count != NULL) 470 { 471 if (*count < _dash_count) 472 { 473 *count = _dash_count; 474 return; 475 } 476 *count = _dash_count; 477 } 478 479 if (phase != NULL) 480 *phase = _dash_phase; 481 482 memcpy(pattern, _dash_pattern, _dash_count * sizeof(CGFloat)); 483} 484 485- (void)setLineDash:(const CGFloat *)pattern count:(NSInteger)count phase:(CGFloat)phase 486{ 487 NSZone *myZone = [self zone]; 488 489 if ((pattern == NULL) || (count == 0)) 490 { 491 if (_dash_pattern != NULL) 492 { 493 NSZoneFree(myZone, _dash_pattern); 494 _dash_pattern = NULL; 495 } 496 _dash_count = 0; 497 _dash_phase = 0.0; 498 return; 499 } 500 501 if (_dash_pattern == NULL) 502 _dash_pattern = NSZoneMalloc(myZone, count * sizeof(CGFloat)); 503 else 504 _dash_pattern = NSZoneRealloc(myZone, _dash_pattern, count * sizeof(CGFloat)); 505 506 _dash_count = count; 507 _dash_phase = phase; 508 memcpy(_dash_pattern, pattern, _dash_count * sizeof(CGFloat)); 509} 510 511// 512// Path operations 513// 514- (void)stroke 515{ 516 NSGraphicsContext *ctxt = GSCurrentContext(); 517 518 if (_cachesBezierPath) 519 { 520 NSRect bounds = [self bounds]; 521 NSPoint origin = bounds.origin; 522 523 // FIXME: I don't see how this should work with color changes 524 if (_cacheImage == nil) 525 { 526 _cacheImage = [[NSImage alloc] initWithSize: bounds.size]; 527 [_cacheImage lockFocus]; 528 DPStranslate(ctxt, -origin.x, -origin.y); 529 [ctxt GSSendBezierPath: self]; 530 DPSstroke(ctxt); 531 [_cacheImage unlockFocus]; 532 } 533 [_cacheImage compositeToPoint: origin operation: NSCompositeCopy]; 534 } 535 else 536 { 537 [ctxt GSSendBezierPath: self]; 538 DPSstroke(ctxt); 539 } 540} 541 542- (void)fill 543{ 544 NSGraphicsContext *ctxt = GSCurrentContext(); 545 546 if (_cachesBezierPath) 547 { 548 NSRect bounds = [self bounds]; 549 NSPoint origin = bounds.origin; 550 551 // FIXME: I don't see how this should work with color changes 552 if (_cacheImage == nil) 553 { 554 _cacheImage = [[NSImage alloc] initWithSize: bounds.size]; 555 [_cacheImage lockFocus]; 556 DPStranslate(ctxt, -origin.x, -origin.y); 557 [ctxt GSSendBezierPath: self]; 558 if ([self windingRule] == NSNonZeroWindingRule) 559 DPSfill(ctxt); 560 else 561 DPSeofill(ctxt); 562 [_cacheImage unlockFocus]; 563 } 564 [_cacheImage compositeToPoint: origin operation: NSCompositeCopy]; 565 } 566 else 567 { 568 [ctxt GSSendBezierPath: self]; 569 if ([self windingRule] == NSNonZeroWindingRule) 570 DPSfill(ctxt); 571 else 572 DPSeofill(ctxt); 573 } 574} 575 576- (void)addClip 577{ 578 NSGraphicsContext *ctxt = GSCurrentContext(); 579 580 [ctxt GSSendBezierPath: self]; 581 if ([self windingRule] == NSNonZeroWindingRule) 582 DPSclip(ctxt); 583 else 584 DPSeoclip(ctxt); 585} 586 587- (void)setClip 588{ 589 NSGraphicsContext *ctxt = GSCurrentContext(); 590 591 DPSinitclip(ctxt); 592 [ctxt GSSendBezierPath: self]; 593 if ([self windingRule] == NSNonZeroWindingRule) 594 DPSclip(ctxt); 595 else 596 DPSeoclip(ctxt); 597} 598 599// 600// Path modifications. 601// 602- (NSBezierPath *)bezierPathByFlatteningPath 603{ 604 NSBezierPath *path; 605 NSBezierPathElement type; 606 NSPoint pts[3]; 607 NSPoint coeff[4]; 608 NSPoint p, last_p; 609 NSInteger i, count; 610 BOOL first = YES; 611 612 if (_flat) 613 return self; 614 615 /* Silence compiler warnings. */ 616 p = NSZeroPoint; 617 last_p = NSZeroPoint; 618 619 path = [[self class] bezierPath]; 620 count = [self elementCount]; 621 for (i = 0; i < count; i++) 622 { 623 type = [self elementAtIndex: i associatedPoints: pts]; 624 switch(type) 625 { 626 case NSMoveToBezierPathElement: 627 [path moveToPoint: pts[0]]; 628 last_p = p = pts[0]; 629 first = NO; 630 break; 631 case NSLineToBezierPathElement: 632 [path lineToPoint: pts[0]]; 633 p = pts[0]; 634 if (first) 635 { 636 last_p = pts[0]; 637 first = NO; 638 } 639 break; 640 case NSCurveToBezierPathElement: 641 coeff[0] = p; 642 coeff[1] = pts[0]; 643 coeff[2] = pts[1]; 644 coeff[3] = pts[2]; 645 flatten(coeff, [self flatness], path); 646 p = pts[2]; 647 if (first) 648 { 649 last_p = pts[2]; 650 first = NO; 651 } 652 break; 653 case NSClosePathBezierPathElement: 654 [path closePath]; 655 p = last_p; 656 break; 657 default: 658 break; 659 } 660 } 661 662 return path; 663} 664 665- (NSBezierPath *) bezierPathByReversingPath 666{ 667 NSBezierPath *path = [object_getClass(self) bezierPath]; 668 NSBezierPathElement type, last_type; 669 NSPoint pts[3]; 670 NSPoint p, cp1, cp2; 671 NSInteger i, count; 672 BOOL closed = NO; 673 674 /* Silence compiler warnings. */ 675 p = NSZeroPoint; 676 677 last_type = NSMoveToBezierPathElement; 678 count = [self elementCount]; 679 for (i = count - 1; i >= 0; i--) 680 { 681 type = [self elementAtIndex: i associatedPoints: pts]; 682 switch(type) 683 { 684 case NSMoveToBezierPathElement: 685 p = pts[0]; 686 break; 687 case NSLineToBezierPathElement: 688 p = pts[0]; 689 break; 690 case NSCurveToBezierPathElement: 691 cp1 = pts[0]; 692 cp2 = pts[1]; 693 p = pts[2]; 694 break; 695 case NSClosePathBezierPathElement: 696 p = pts[0]; 697 break; 698 default: 699 break; 700 } 701 702 switch(last_type) 703 { 704 case NSMoveToBezierPathElement: 705 if (closed) 706 { 707 [path closePath]; 708 closed = NO; 709 } 710 [path moveToPoint: p]; 711 break; 712 case NSLineToBezierPathElement: 713 [path lineToPoint: p]; 714 break; 715 case NSCurveToBezierPathElement: 716 [path curveToPoint: p 717 controlPoint1: cp2 718 controlPoint2: cp1]; 719 break; 720 case NSClosePathBezierPathElement: 721 closed = YES; 722 break; 723 default: 724 break; 725 } 726 last_type = type; 727 } 728 729 if (closed) 730 [path closePath]; 731 return path; 732} 733 734// 735// Applying transformations. 736// 737- (void) transformUsingAffineTransform: (NSAffineTransform *)transform 738{ 739 NSBezierPathElement type; 740 NSPoint pts[3]; 741 NSInteger i, count; 742 SEL transformPointSel = @selector(transformPoint:); 743 NSPoint (*transformPointImp)(NSAffineTransform*, SEL, NSPoint); 744 745 transformPointImp = (NSPoint (*)(NSAffineTransform*, SEL, NSPoint)) 746 [transform methodForSelector: transformPointSel]; 747 748 count = [self elementCount]; 749 for (i = 0; i < count; i++) 750 { 751 type = [self elementAtIndex: i associatedPoints: pts]; 752 switch(type) 753 { 754 case NSMoveToBezierPathElement: 755 case NSLineToBezierPathElement: 756 pts[0] = (*transformPointImp)(transform, 757 transformPointSel, pts[0]); 758 [self setAssociatedPoints: pts atIndex: i]; 759 break; 760 case NSCurveToBezierPathElement: 761 pts[0] = (*transformPointImp)(transform, 762 transformPointSel, pts[0]); 763 pts[1] = (*transformPointImp)(transform, 764 transformPointSel, pts[1]); 765 pts[2] = (*transformPointImp)(transform, 766 transformPointSel, pts[2]); 767 [self setAssociatedPoints: pts atIndex: i]; 768 break; 769 case NSClosePathBezierPathElement: 770 break; 771 default: 772 break; 773 } 774 } 775 INVALIDATE_CACHE(); 776} 777 778// 779// Path info 780// 781- (BOOL) isEmpty 782{ 783 return ([self elementCount] == 0); 784} 785 786- (NSPoint) currentPoint 787{ 788 NSBezierPathElement type; 789 NSPoint points[3]; 790 NSInteger count; 791 792 count = [self elementCount]; 793 if (!count) 794 [NSException raise: NSGenericException 795 format: @"No current Point in NSBezierPath"]; 796 797 type = [self elementAtIndex: count - 1 associatedPoints: points]; 798 switch(type) 799 { 800 case NSMoveToBezierPathElement: 801 case NSLineToBezierPathElement: 802 return points[0]; 803 break; 804 case NSCurveToBezierPathElement: 805 return points[2]; 806 break; 807 case NSClosePathBezierPathElement: 808 return points[0]; 809 break; 810 default: 811 break; 812 } 813 814 return NSZeroPoint; 815} 816 817- (NSRect) controlPointBounds 818{ 819 if (_shouldRecalculateBounds) 820 [self _recalculateBounds]; 821 return _controlPointBounds; 822} 823 824- (NSRect) bounds 825{ 826 if (_shouldRecalculateBounds) 827 [self _recalculateBounds]; 828 return _bounds; 829} 830 831// 832// Elements 833// 834- (NSInteger) elementCount 835{ 836 return GSIArrayCount(_pathElements); 837} 838 839- (NSBezierPathElement) elementAtIndex: (NSInteger)index 840 associatedPoints: (NSPoint *)points 841{ 842 PathElement elm = GSIArrayItemAtIndex(_pathElements, index).ext; 843 NSBezierPathElement type = elm.type; 844 NSInteger i; 845 846 if (points != NULL) 847 { 848 switch(type) 849 { 850 case NSMoveToBezierPathElement: 851 case NSLineToBezierPathElement: 852 points[0] = elm.points[0]; 853 break; 854 case NSCurveToBezierPathElement: 855 points[0] = elm.points[0]; 856 points[1] = elm.points[1]; 857 points[2] = elm.points[2]; 858 break; 859 case NSClosePathBezierPathElement: 860 // We have to find the last move element and take its point 861 for (i = index - 1; i >= 0; i--) 862 { 863 elm = GSIArrayItemAtIndex(_pathElements, i).ext; 864 if (elm.type == NSMoveToBezierPathElement) 865 { 866 points[0] = elm.points[0]; 867 break; 868 } 869 } 870 // FIXME: What to do if we don't find a move element? 871 break; 872 default: 873 break; 874 } 875 } 876 877 return type; 878} 879 880- (NSBezierPathElement) elementAtIndex: (NSInteger)index 881{ 882 return [self elementAtIndex: index associatedPoints: NULL]; 883} 884 885- (void)setAssociatedPoints:(NSPoint *)points atIndex:(NSInteger)index 886{ 887 PathElement elm = GSIArrayItemAtIndex(_pathElements, index).ext; 888 NSBezierPathElement type = elm.type; 889 890 switch(type) 891 { 892 case NSMoveToBezierPathElement: 893 case NSLineToBezierPathElement: 894 elm.points[0] = points[0]; 895 break; 896 case NSCurveToBezierPathElement: 897 elm.points[0] = points[0]; 898 elm.points[1] = points[1]; 899 elm.points[2] = points[2]; 900 break; 901 case NSClosePathBezierPathElement: 902 break; 903 default: 904 break; 905 } 906 907 GSIArraySetItemAtIndex(_pathElements, (GSIArrayItem)elm, index); 908 INVALIDATE_CACHE(); 909} 910 911// 912// Appending common paths 913// 914- (void) appendBezierPath: (NSBezierPath *)aPath 915{ 916 NSBezierPathElement type; 917 NSPoint points[3]; 918 NSInteger i, count; 919 920 count = [aPath elementCount]; 921 for (i = 0; i < count; i++) 922 { 923 type = [aPath elementAtIndex: i associatedPoints: points]; 924 switch(type) 925 { 926 case NSMoveToBezierPathElement: 927 [self moveToPoint: points[0]]; 928 break; 929 case NSLineToBezierPathElement: 930 [self lineToPoint: points[0]]; 931 break; 932 case NSCurveToBezierPathElement: 933 [self curveToPoint: points[2] 934 controlPoint1: points[0] 935 controlPoint2: points[1]]; 936 break; 937 case NSClosePathBezierPathElement: 938 [self closePath]; 939 break; 940 default: 941 break; 942 } 943 } 944} 945 946- (void)appendBezierPathWithRect:(NSRect)aRect 947{ 948 NSPoint p; 949 950 [self moveToPoint: aRect.origin]; 951 p.x = aRect.origin.x + aRect.size.width; 952 p.y = aRect.origin.y; 953 [self lineToPoint: p]; 954 p.x = aRect.origin.x + aRect.size.width; 955 p.y = aRect.origin.y + aRect.size.height; 956 [self lineToPoint: p]; 957 p.x = aRect.origin.x; 958 p.y = aRect.origin.y + aRect.size.height; 959 [self lineToPoint: p]; 960 [self closePath]; 961} 962 963- (void)appendBezierPathWithPoints:(NSPoint *)points count:(NSInteger)count 964{ 965 NSInteger i; 966 967 if (!count) 968 return; 969 970 if ([self isEmpty]) 971 { 972 [self moveToPoint: points[0]]; 973 } 974 else 975 { 976 [self lineToPoint: points[0]]; 977 } 978 979 for (i = 1; i < count; i++) 980 { 981 [self lineToPoint: points[i]]; 982 } 983} 984 985- (void) appendBezierPathWithOvalInRect: (NSRect)aRect 986{ 987 NSPoint p, p1, p2; 988 double originx = aRect.origin.x; 989 double originy = aRect.origin.y; 990 double width = aRect.size.width; 991 double height = aRect.size.height; 992 double hdiff = width / 2 * KAPPA; 993 double vdiff = height / 2 * KAPPA; 994 995 p = NSMakePoint(originx + width / 2, originy + height); 996 [self moveToPoint: p]; 997 998 p = NSMakePoint(originx, originy + height / 2); 999 p1 = NSMakePoint(originx + width / 2 - hdiff, originy + height); 1000 p2 = NSMakePoint(originx, originy + height / 2 + vdiff); 1001 [self curveToPoint: p controlPoint1: p1 controlPoint2: p2]; 1002 1003 p = NSMakePoint(originx + width / 2, originy); 1004 p1 = NSMakePoint(originx, originy + height / 2 - vdiff); 1005 p2 = NSMakePoint(originx + width / 2 - hdiff, originy); 1006 [self curveToPoint: p controlPoint1: p1 controlPoint2: p2]; 1007 1008 p = NSMakePoint(originx + width, originy + height / 2); 1009 p1 = NSMakePoint(originx + width / 2 + hdiff, originy); 1010 p2 = NSMakePoint(originx + width, originy + height / 2 - vdiff); 1011 [self curveToPoint: p controlPoint1: p1 controlPoint2: p2]; 1012 1013 p = NSMakePoint(originx + width / 2, originy + height); 1014 p1 = NSMakePoint(originx + width, originy + height / 2 + vdiff); 1015 p2 = NSMakePoint(originx + width / 2 + hdiff, originy + height); 1016 [self curveToPoint: p controlPoint1: p1 controlPoint2: p2]; 1017} 1018 1019/* startAngle and endAngle are in degrees, counterclockwise, from the 1020 x axis */ 1021- (void) appendBezierPathWithArcWithCenter: (NSPoint)center 1022 radius: (CGFloat)radius 1023 startAngle: (CGFloat)startAngle 1024 endAngle: (CGFloat)endAngle 1025 clockwise: (BOOL)clockwise 1026{ 1027 CGFloat startAngle_rad, endAngle_rad, diff; 1028 NSPoint p0, p1, p2, p3; 1029 1030 /* We use the Postscript prescription for managing the angles and 1031 drawing the arc. See the documentation for `arc' and `arcn' in 1032 the Postscript Reference. */ 1033 1034 if (clockwise) 1035 { 1036 /* This modification of the angles is the postscript 1037 prescription. */ 1038 while (startAngle < endAngle) 1039 endAngle -= 360; 1040 1041 /* This is used when we draw a clockwise quarter of 1042 circumference. By adding diff at the starting angle of the 1043 quarter, we get the ending angle. diff is negative because 1044 we draw clockwise. */ 1045 diff = - M_PI / 2; 1046 } 1047 else 1048 { 1049 /* This modification of the angles is the postscript 1050 prescription. */ 1051 while (endAngle < startAngle) 1052 endAngle += 360; 1053 1054 /* This is used when we draw a counterclockwise quarter of 1055 circumference. By adding diff at the starting angle of the 1056 quarter, we get the ending angle. diff is positive because 1057 we draw counterclockwise. */ 1058 diff = M_PI / 2; 1059 } 1060 1061 /* Convert the angles to radians */ 1062 startAngle_rad = M_PI * startAngle / 180; 1063 endAngle_rad = M_PI * endAngle / 180; 1064 1065 /* Start point */ 1066 p0 = NSMakePoint (center.x + radius * cos (startAngle_rad), 1067 center.y + radius * sin (startAngle_rad)); 1068 if ([self elementCount] == 0) 1069 { 1070 [self moveToPoint: p0]; 1071 } 1072 else 1073 { 1074 NSPoint ps = [self currentPoint]; 1075 1076 if (p0.x != ps.x || p0.y != ps.y) 1077 { 1078 [self lineToPoint: p0]; 1079 } 1080 } 1081 1082 while ((clockwise) ? (startAngle_rad > endAngle_rad) 1083 : (startAngle_rad < endAngle_rad)) 1084 { 1085 /* Add a quarter circle */ 1086 if ((clockwise) ? (startAngle_rad + diff >= endAngle_rad) 1087 : (startAngle_rad + diff <= endAngle_rad)) 1088 { 1089 CGFloat sin_start = sin (startAngle_rad); 1090 CGFloat cos_start = cos (startAngle_rad); 1091 CGFloat sign = (clockwise) ? -1.0 : 1.0; 1092 1093 p1 = NSMakePoint (center.x 1094 + radius * (cos_start - KAPPA * sin_start * sign), 1095 center.y 1096 + radius * (sin_start + KAPPA * cos_start * sign)); 1097 p2 = NSMakePoint (center.x 1098 + radius * (-sin_start * sign + KAPPA * cos_start), 1099 center.y 1100 + radius * (cos_start * sign + KAPPA * sin_start)); 1101 p3 = NSMakePoint (center.x + radius * (-sin_start * sign), 1102 center.y + radius * cos_start * sign); 1103 1104 [self curveToPoint: p3 controlPoint1: p1 controlPoint2: p2]; 1105 startAngle_rad += diff; 1106 } 1107 else 1108 { 1109 /* Add the missing bit 1110 * We require that the arc be less than a semicircle. 1111 * The arc may go either clockwise or counterclockwise. 1112 * The approximation is a very simple one: a single curve 1113 * whose middle two control points are a fraction F of the way 1114 * to the intersection of the tangents, where 1115 * F = (4/3) / (1 + sqrt (1 + (d / r)^2)) 1116 * where r is the radius and d is the distance from either tangent 1117 * point to the intersection of the tangents. This produces 1118 * a curve whose center point, as well as its ends, lies on 1119 * the desired arc. 1120 */ 1121 NSPoint ps = [self currentPoint]; 1122 /* tangent is the tangent of half the angle */ 1123 CGFloat tangent = tan ((endAngle_rad - startAngle_rad) / 2); 1124 /* trad is the distance from either tangent point to the 1125 intersection of the tangents */ 1126 CGFloat trad = radius * tangent; 1127 /* pt is the intersection of the tangents */ 1128 NSPoint pt = NSMakePoint (ps.x - trad * sin (startAngle_rad), 1129 ps.y + trad * cos (startAngle_rad)); 1130 /* This is F - in this expression we need to compute 1131 (trad/radius)^2, which is simply tangent^2 */ 1132 CGFloat f = (4.0 / 3.0) / (1.0 + sqrt (1.0 + (tangent * tangent))); 1133 1134 p1 = NSMakePoint (ps.x + (pt.x - ps.x) * f, ps.y + (pt.y - ps.y) * f); 1135 p3 = NSMakePoint(center.x + radius * cos (endAngle_rad), 1136 center.y + radius * sin (endAngle_rad)); 1137 p2 = NSMakePoint (p3.x + (pt.x - p3.x) * f, p3.y + (pt.y - p3.y) * f); 1138 [self curveToPoint: p3 controlPoint1: p1 controlPoint2: p2]; 1139 break; 1140 } 1141 } 1142} 1143 1144- (void) appendBezierPathWithArcWithCenter: (NSPoint)center 1145 radius: (CGFloat)radius 1146 startAngle: (CGFloat)startAngle 1147 endAngle: (CGFloat)endAngle 1148{ 1149 [self appendBezierPathWithArcWithCenter: center radius: radius 1150 startAngle: startAngle endAngle: endAngle clockwise: NO]; 1151} 1152 1153- (void) appendBezierPathWithArcFromPoint: (NSPoint)point1 1154 toPoint: (NSPoint)point2 1155 radius: (CGFloat)radius 1156{ 1157 CGFloat x1, y1; 1158 CGFloat dx1, dy1, dx2, dy2; 1159 CGFloat l, a1, a2; 1160 NSPoint p; 1161 1162 p = [self currentPoint]; 1163 1164 x1 = point1.x; 1165 y1 = point1.y; 1166 dx1 = p.x - x1; 1167 dy1 = p.y - y1; 1168 1169 l= dx1*dx1 + dy1*dy1; 1170 if (l <= 0) 1171 { 1172 [self lineToPoint: point1]; 1173 return; 1174 } 1175 l = 1/sqrt(l); 1176 dx1 *= l; 1177 dy1 *= l; 1178 1179 dx2 = point2.x - x1; 1180 dy2 = point2.y - y1; 1181 1182 l = dx2*dx2 + dy2*dy2; 1183 if (l <= 0) 1184 { 1185 [self lineToPoint: point1]; 1186 return; 1187 } 1188 1189 l = 1/sqrt(l); 1190 dx2 *= l; 1191 dy2 *= l; 1192 1193 l = dx1*dx2 + dy1*dy2; 1194 if (l < -0.999) 1195 { 1196 [self lineToPoint: point1]; 1197 return; 1198 } 1199 1200 l = radius/sin(acos(l)); 1201 p.x = x1 + (dx1 + dx2)*l; 1202 p.y = y1 + (dy1 + dy2)*l; 1203 1204 if (dx1 < -1) 1205 a1 = 180; 1206 else if (dx1 > 1) 1207 a1 = 0; 1208 else 1209 a1 = acos(dx1) / M_PI*180; 1210 if (dy1 < 0) 1211 { 1212 a1 = -a1; 1213 } 1214 1215 if (dx2 < -1) 1216 a2 = 180; 1217 else if (dx2 > 1) 1218 a2 = 0; 1219 else 1220 a2 = acos(dx2) / M_PI*180; 1221 if (dy2 < 0) 1222 { 1223 a2 = -a2; 1224 } 1225 1226 l = dx1*dy2 - dx2*dy1; 1227 if (l < 0) 1228 { 1229 a2 = a2 - 90; 1230 a1 = a1 + 90; 1231 [self appendBezierPathWithArcWithCenter: p 1232 radius: radius 1233 startAngle: a1 1234 endAngle: a2 1235 clockwise: NO]; 1236 } 1237 else 1238 { 1239 a2 = a2 + 90; 1240 a1 = a1 - 90; 1241 [self appendBezierPathWithArcWithCenter: p 1242 radius: radius 1243 startAngle: a1 1244 endAngle: a2 1245 clockwise: YES]; 1246 } 1247} 1248 1249- (void)appendBezierPathWithGlyph:(NSGlyph)glyph inFont:(NSFont *)font 1250{ 1251 [[font fontInfo] appendBezierPathWithGlyphs: &glyph 1252 count: 1 1253 toBezierPath: self]; 1254} 1255 1256- (void)appendBezierPathWithGlyphs:(NSGlyph *)glyphs 1257 count:(NSInteger)count 1258 inFont:(NSFont *)font 1259{ 1260 [[font fontInfo] appendBezierPathWithGlyphs: glyphs 1261 count: count 1262 toBezierPath: self]; 1263} 1264 1265- (void)appendBezierPathWithPackedGlyphs:(const char *)packedGlyphs 1266{ 1267 [GSCurrentContext() appendBezierPathWithPackedGlyphs: packedGlyphs 1268 path: self]; 1269} 1270 1271- (void) appendBezierPathWithRoundedRect: (NSRect)aRect 1272 xRadius: (CGFloat)xRadius 1273 yRadius: (CGFloat)yRadius 1274{ 1275 NSPoint startp, endp, controlp1, controlp2, topLeft, topRight, bottomRight; 1276 1277 xRadius = MIN(xRadius, aRect.size.width / 2.0); 1278 yRadius = MIN(yRadius, aRect.size.height / 2.0); 1279 1280 if (xRadius == 0.0 || yRadius == 0.0) 1281 { 1282 [self appendBezierPathWithRect: aRect]; 1283 return; 1284 } 1285 1286 topLeft = NSMakePoint(NSMinX(aRect), NSMaxY(aRect)); 1287 topRight = NSMakePoint(NSMaxX(aRect), NSMaxY(aRect)); 1288 bottomRight = NSMakePoint(NSMaxX(aRect), NSMinY(aRect)); 1289 1290 startp = NSMakePoint(topLeft.x + xRadius, topLeft.y); 1291 endp = NSMakePoint(topLeft.x, topLeft.y - yRadius); 1292 controlp1 = NSMakePoint(startp.x - (KAPPA * xRadius), startp.y); 1293 controlp2 = NSMakePoint(endp.x, endp.y + (KAPPA * yRadius)); 1294 [self moveToPoint: startp]; 1295 [self curveToPoint: endp controlPoint1: controlp1 controlPoint2: controlp2]; 1296 1297 startp = NSMakePoint(aRect.origin.x, aRect.origin.y + yRadius); 1298 endp = NSMakePoint(aRect.origin.x + xRadius, aRect.origin.y); 1299 controlp1 = NSMakePoint(startp.x, startp.y - (KAPPA * yRadius)); 1300 controlp2 = NSMakePoint(endp.x - (KAPPA * xRadius), endp.y); 1301 [self lineToPoint: startp]; 1302 [self curveToPoint: endp controlPoint1: controlp1 controlPoint2: controlp2]; 1303 1304 startp = NSMakePoint(bottomRight.x - xRadius, bottomRight.y); 1305 endp = NSMakePoint(bottomRight.x, bottomRight.y + yRadius); 1306 controlp1 = NSMakePoint(startp.x + (KAPPA * xRadius), startp.y); 1307 controlp2 = NSMakePoint(endp.x, endp.y - (KAPPA * yRadius)); 1308 [self lineToPoint: startp]; 1309 [self curveToPoint: endp controlPoint1: controlp1 controlPoint2: controlp2]; 1310 1311 startp = NSMakePoint(topRight.x, topRight.y - yRadius); 1312 endp = NSMakePoint(topRight.x - xRadius, topRight.y); 1313 controlp1 = NSMakePoint(startp.x, startp.y + (KAPPA * yRadius)); 1314 controlp2 = NSMakePoint(endp.x + (KAPPA * xRadius), endp.y); 1315 [self lineToPoint: startp]; 1316 [self curveToPoint: endp controlPoint1: controlp1 controlPoint2: controlp2]; 1317 1318 [self closePath]; 1319} 1320 1321/* We use our own point structure with double elements while recursing to 1322 avoid losing accuracy at really fine subdivisions of curves. */ 1323typedef struct 1324{ 1325 double x, y; 1326} double_point; 1327 1328static int winding_line(double_point from, double_point to, double_point p) 1329{ 1330 int y_dir; 1331 double k, x; 1332 1333 if (from.y == to.y) 1334 return 0; 1335 1336 if (to.y < from.y) 1337 { 1338 y_dir = -2; 1339 if (p.y < to.y) 1340 return 0; 1341 if (p.y > from.y) 1342 return 0; 1343 } 1344 else 1345 { 1346 y_dir = 2; 1347 if (p.y < from.y) 1348 return 0; 1349 if (p.y > to.y) 1350 return 0; 1351 } 1352 1353 if (p.y == from.y || p.y == to.y) 1354 y_dir /= 2; 1355 1356 /* The line is intersected. Check if the intersection is outside the 1357 line's bounding box. */ 1358 if (to.x < from.x) 1359 { 1360 if (p.x < to.x) 1361 return 0; 1362 if (p.x > from.x) 1363 return y_dir; 1364 } 1365 else 1366 { 1367 if (p.x < from.x) 1368 return 0; 1369 if (p.x > to.x) 1370 return y_dir; 1371 } 1372 1373 /* Determine the exact x coordinate of the intersection. */ 1374 k = (double)(from.x - to.x) / (double)(from.y - to.y); 1375 x = to.x + k * (double)(p.y - to.y); 1376 if (x < p.x) 1377 return y_dir; 1378 1379 return 0; 1380} 1381 1382static int winding_curve(double_point from, double_point to, double_point c1, 1383 double_point c2, double_point p, int depth) 1384{ 1385 double x0, x1; 1386 double y0, y1; 1387 double scale; 1388 1389 /* Get the vertical extents of the convex hull. */ 1390 y0 = y1 = from.y; 1391 if (to.y < y0) 1392 y0 = to.y; 1393 else if (to.y > y1) 1394 y1 = to.y; 1395 if (c1.y < y0) 1396 y0 = c1.y; 1397 else if (c1.y > y1) 1398 y1 = c1.y; 1399 if (c2.y < y0) 1400 y0 = c2.y; 1401 else if (c2.y > y1) 1402 y1 = c2.y; 1403 1404 /* If the point is outside the convex hull, the line can't intersect the 1405 curve. */ 1406 if (p.y < y0 || p.y > y1) 1407 return 0; 1408 1409 /* Get the horizontal convex hull. */ 1410 x0 = x1 = from.x; 1411 if (to.x < x0) 1412 x0 = to.x; 1413 else if (to.x > x1) 1414 x1 = to.x; 1415 if (c1.x < x0) 1416 x0 = c1.x; 1417 else if (c1.x > x1) 1418 x1 = c1.x; 1419 if (c2.x < x0) 1420 x0 = c2.x; 1421 else if (c2.x > x1) 1422 x1 = c2.x; 1423 1424 /* If the point is left of the convex hull, the line doesn't intersect 1425 the curve. */ 1426 if (p.x < x0) 1427 return 0; 1428 1429 /* If the point is right of the convex hull, the net winding count is 0, 1430 1, or -1, and it depends only on how the end-points are placed in 1431 relation to the point. Essentially, it's equivalent to a line. */ 1432 if (p.x > x1) 1433 return winding_line(from, to, p); 1434 1435 /* Limit the recursion, just to be safe. */ 1436 if (depth >= 40) 1437 return winding_line(from, to, p); 1438 1439 /* The line possibly intersects the curve in some interesting way. If the 1440 curve is flat enough, we can pretend it's a line. Otherwise, we 1441 subdivide and recurse. 1442 1443 First, calculate a suitable scale based on the coordinates of the 1444 convex hull. This is used to get a good cutoff for the subdivision. 1445 Since it's based on the coordinates in the curve, scaling the curve 1446 up or down won't affect relative accuracy. Note that if the scale is 1447 zero, the convex hull, and thus the curve, has no extent. */ 1448 1449 scale = fabs(x0) + fabs(x1) + fabs(y0) + fabs(y1); 1450 if (!scale) 1451 return 0; 1452 1453 scale /= 40000000.0; 1454 1455 /* Deal with the degenerate case to == from. */ 1456 if (to.x == from.x && to.y == from.y) 1457 { 1458 if (x1 - x0 < scale && y1 - y0 < scale) 1459 return winding_line(from, to, p); 1460 } 1461 else 1462 { 1463 double dx, dy; 1464 double nx, ny; 1465 double d0, d1, d2, d3; 1466 1467 /* Get the direction vector and the normal vector. */ 1468 dx = to.x - from.x; 1469 dy = to.y - from.y; 1470 d0 = sqrt(dx * dx + dy * dy); 1471 dx /= d0; 1472 dy /= d0; 1473 nx = dy; 1474 ny = -dx; 1475 1476 /* Check that the distances along the direction vector are 1477 monotone. */ 1478 1479 d0 = from.x * dx + from.y * dy; 1480 d1 = c1.x * dx + c1.y * dy; 1481 d2 = c2.x * dx + c2.y * dy; 1482 d3 = to.x * dx + to.y * dy; 1483 1484 if ((d3 > d2 && d2 > d1 && d1 > d0) 1485 || (d3 < d2 && d2 < d1 && d1 < d0)) 1486 { 1487 /* Check that the control points are close to the straigt line 1488 between from and to. */ 1489 d0 = to.x * nx + to.y * ny; 1490 d1 = c1.x * nx + c1.y * ny; 1491 d2 = c2.x * nx + c2.y * ny; 1492 1493 if (fabs(d0 - d1) < scale && fabs(d0 - d2) < scale) 1494 { 1495 /* It's flat enough. */ 1496 return winding_line(from, to, p); 1497 } 1498 } 1499 } 1500 1501 { 1502 /* Subdivide. */ 1503 double_point m, l1, l2, r1, r2; 1504 1505 m.x = (from.x + to.x + 3 * (c1.x + c2.x)) / 8; 1506 m.y = (from.y + to.y + 3 * (c1.y + c2.y)) / 8; 1507 1508 l1.x = (from.x + c1.x) / 2; 1509 l1.y = (from.y + c1.y) / 2; 1510 1511 l2.x = (from.x + 2 * c1.x + c2.x) / 4; 1512 l2.y = (from.y + 2 * c1.y + c2.y) / 4; 1513 1514 r2.x = (to.x + c2.x) / 2; 1515 r2.y = (to.y + c2.y) / 2; 1516 1517 r1.x = (to.x + 2 * c2.x + c1.x) / 4; 1518 r1.y = (to.y + 2 * c2.y + c1.y) / 4; 1519 1520 return winding_curve(from, m, l1, l2, p, depth + 1) 1521 + winding_curve(m, to, r1, r2, p, depth + 1); 1522 } 1523} 1524 1525- (int) windingCountAtPoint: (NSPoint)point 1526{ 1527 int total; 1528 NSBezierPathElement type; 1529 NSInteger count; 1530 BOOL first; 1531 NSPoint pts[3]; 1532 NSPoint first_p, last_p; 1533 NSInteger i; 1534 1535 /* We trace a line from (-INF, point.y) to (point) and count the 1536 intersections. Simple, really. ;) 1537 1538 Lines are trivially checked with a few complications: 1539 1540 a. Tangent lines, i.e. horizontal lines. These can be ignored since 1541 the winding count is undefined on edges. 1542 1543 b. Lines whose endpoints are touched by our infinite line. To get 1544 these right, we return half a winding for such intersections. 1545 Except for intermediate horizontal lines, which are ignored, the 1546 next line will also be intersected in one endpoint. If it's going 1547 in the same direction as the first line, the two half intersections 1548 will add up to one real intersection. If it isn't, the two half 1549 intersections with opposite signs will cancel out. Either way, we 1550 get the right results. 1551 1552 (If this happens for the first element, s/next/previous/ in the 1553 explanation. In practice, we double the winding counts while 1554 working and divide by 2 just before returning.) 1555 1556 Curves are checked first using the convex hull, and if necessary, by 1557 subdividing until they are flat enough to check as lines. We use a 1558 very fine subdivision, and thus get good accuracy. This is possible 1559 because only the parts of the curve that might intersect the line are 1560 subdivided (due to the convex hull checks). */ 1561 1562 total = 0; 1563 count = [self elementCount]; 1564 1565 if (count == 0) 1566 return 0; 1567 1568 /* 'Unroll' the first element to avoid compiler warnings. It has to be 1569 a MoveTo, anyway. */ 1570 type = [self elementAtIndex: 0 associatedPoints: pts]; 1571 if (type != NSMoveToBezierPathElement) 1572 { 1573 NSWarnLog(@"Invalid path, first element isn't MoveTo."); 1574 return 0; 1575 } 1576 last_p = first_p = pts[0]; 1577 first = NO; 1578 1579#define D(a) (double_point){a.x,a.y} 1580 for (i = 1; i < count; i++) 1581 { 1582 type = [self elementAtIndex: i associatedPoints: pts]; 1583 switch(type) 1584 { 1585 case NSMoveToBezierPathElement: 1586 if (!first) 1587 { 1588 total += winding_line(D(last_p), D(first_p), D(point)); 1589 } 1590 last_p = first_p = pts[0]; 1591 first = NO; 1592 break; 1593 case NSLineToBezierPathElement: 1594 if (first) 1595 { 1596 NSWarnLog(@"Invalid path, LineTo without MoveTo."); 1597 return 0; 1598 } 1599 total += winding_line(D(last_p), D(pts[0]), D(point)); 1600 last_p = pts[0]; 1601 break; 1602 case NSCurveToBezierPathElement: 1603 if (first) 1604 { 1605 NSWarnLog(@"Invalid path, CurveTo without MoveTo."); 1606 return 0; 1607 } 1608 total += winding_curve(D(last_p), D(pts[2]), D(pts[0]), D(pts[1]), D(point), 0); 1609 last_p = pts[2]; 1610 break; 1611 case NSClosePathBezierPathElement: 1612 if (first) 1613 { 1614 NSWarnLog(@"Invalid path, ClosePath with no open subpath."); 1615 return 0; 1616 } 1617 first = YES; 1618 total += winding_line(D(last_p), D(first_p), D(point)); 1619 break; 1620 default: 1621 NSWarnLog(@"Invalid element in path."); 1622 return 0; 1623 } 1624 } 1625 1626 if (!first) 1627 total += winding_line(D(last_p), D(first_p), D(point)); 1628#undef D 1629 1630 if (total & 1) 1631 { 1632 /* This should only happen for points on edges, and the winding 1633 count is undefined at such points. */ 1634 NSDebugLLog(@"NSBezierPath", @"winding count total is odd"); 1635 } 1636 return total / 2; 1637} 1638 1639- (BOOL) containsPoint: (NSPoint)point 1640{ 1641 int sum; 1642 1643 if (![self elementCount]) 1644 return NO; 1645 1646 if (!NSPointInRect(point, [self bounds])) 1647 return NO; 1648 1649 sum = [self windingCountAtPoint: point]; 1650 if ([self windingRule] == NSNonZeroWindingRule) 1651 { 1652 if (sum == 0) 1653 return NO; 1654 else 1655 return YES; 1656 } 1657 else 1658 { 1659 if ((sum % 2) == 0) 1660 return NO; 1661 else 1662 return YES; 1663 } 1664} 1665 1666// 1667// Caching paths 1668// 1669// 1670// Caching 1671// 1672- (BOOL)cachesBezierPath 1673{ 1674 return _cachesBezierPath; 1675} 1676 1677- (void)setCachesBezierPath:(BOOL)flag 1678{ 1679 _cachesBezierPath = flag; 1680 1681 if (!flag) 1682 INVALIDATE_CACHE(); 1683} 1684 1685// 1686// NSCoding protocol 1687// 1688- (void)encodeWithCoder:(NSCoder *)aCoder 1689{ 1690 NSBezierPathElement type; 1691 NSPoint pts[3]; 1692 1693 if ([aCoder allowsKeyedCoding]) 1694 { 1695 NSUInteger count, i; 1696 NSMutableData *d; 1697 float x,y; 1698 char ctype; 1699 1700 [aCoder encodeFloat: [self flatness] forKey: @"NSFlatness"]; 1701 [aCoder encodeFloat: [self lineWidth] forKey: @"NSLineWidth"]; 1702 [aCoder encodeInt: [self lineCapStyle] forKey: @"NSLineCapStyle"]; 1703 [aCoder encodeInt: [self lineJoinStyle] forKey: @"NSLineJoinStyle"]; 1704 [aCoder encodeInt: [self windingRule] forKey: @"NSWindingRule"]; 1705 [aCoder encodeFloat: [self miterLimit] forKey: @"NSMiterLimit"]; 1706 1707 count = [self elementCount]; 1708 d = [[NSMutableData alloc] init]; 1709 for (i = 0; i < count; i++) 1710 { 1711 type = [self elementAtIndex: i associatedPoints: pts]; 1712 ctype = type; 1713 [d serializeDataAt: &ctype 1714 ofObjCType: "c" 1715 context: nil]; 1716 1717 switch (type) 1718 { 1719 case NSMoveToBezierPathElement: 1720 case NSLineToBezierPathElement: 1721 x = pts[0].x; 1722 y = pts[0].y; 1723 [d serializeDataAt: &x 1724 ofObjCType: "f" 1725 context: nil]; 1726 [d serializeDataAt: &y 1727 ofObjCType: "f" 1728 context: nil]; 1729 break; 1730 case NSCurveToBezierPathElement: 1731 x = pts[0].x; 1732 y = pts[0].y; 1733 [d serializeDataAt: &x 1734 ofObjCType: "f" 1735 context: nil]; 1736 [d serializeDataAt: &y 1737 ofObjCType: "f" 1738 context: nil]; 1739 [d serializeDataAt: &ctype 1740 ofObjCType: "c" 1741 context: nil]; 1742 x = pts[1].x; 1743 y = pts[1].y; 1744 [d serializeDataAt: &x 1745 ofObjCType: "f" 1746 context: nil]; 1747 [d serializeDataAt: &y 1748 ofObjCType: "f" 1749 context: nil]; 1750 [d serializeDataAt: &ctype 1751 ofObjCType: "c" 1752 context: nil]; 1753 x = pts[2].x; 1754 y = pts[2].y; 1755 [d serializeDataAt: &x 1756 ofObjCType: "f" 1757 context: nil]; 1758 [d serializeDataAt: &y 1759 ofObjCType: "f" 1760 context: nil]; 1761 break; 1762 case NSClosePathBezierPathElement: 1763 x = pts[0].x; 1764 y = pts[0].y; 1765 [d serializeDataAt: &x 1766 ofObjCType: "f" 1767 context: nil]; 1768 [d serializeDataAt: &y 1769 ofObjCType: "f" 1770 context: nil]; 1771 [d serializeDataAt: &ctype 1772 ofObjCType: "c" 1773 context: nil]; 1774 x = pts[0].x; 1775 y = pts[0].y; 1776 [d serializeDataAt: &x 1777 ofObjCType: "f" 1778 context: nil]; 1779 [d serializeDataAt: &y 1780 ofObjCType: "f" 1781 context: nil]; 1782 break; 1783 default: 1784 break; 1785 } 1786 } 1787 [aCoder encodeBytes: [d bytes] 1788 length: [d length] 1789 forKey: @"NSSegments"]; 1790 RELEASE(d); 1791 } 1792 else 1793 { 1794 int i, count; 1795 float f; 1796 1797 f = [self lineWidth]; 1798 [aCoder encodeValueOfObjCType: @encode(float) at: &f]; 1799 i = [self lineCapStyle]; 1800 [aCoder encodeValueOfObjCType: @encode(int) at: &i]; 1801 i = [self lineJoinStyle]; 1802 [aCoder encodeValueOfObjCType: @encode(int) at: &i]; 1803 i = [self windingRule]; 1804 [aCoder encodeValueOfObjCType: @encode(int) at: &i]; 1805 [aCoder encodeValueOfObjCType: @encode(BOOL) at: &_cachesBezierPath]; 1806 1807 // version 2 1808 f = [self flatness]; 1809 [aCoder encodeValueOfObjCType: @encode(float) at: &f]; 1810 f = [self miterLimit]; 1811 [aCoder encodeValueOfObjCType: @encode(float) at: &f]; 1812 1813 count = [self elementCount]; 1814 [aCoder encodeValueOfObjCType: @encode(int) at: &count]; 1815 1816 for (i = 0; i < count; i++) 1817 { 1818 type = [self elementAtIndex: i associatedPoints: pts]; 1819 [aCoder encodeValueOfObjCType: @encode(int) at: &type]; 1820 switch(type) 1821 { 1822 case NSMoveToBezierPathElement: 1823 case NSLineToBezierPathElement: 1824 [aCoder encodePoint: pts[0]]; 1825 break; 1826 case NSCurveToBezierPathElement: 1827 [aCoder encodePoint: pts[0]]; 1828 [aCoder encodePoint: pts[1]]; 1829 [aCoder encodePoint: pts[2]]; 1830 break; 1831 case NSClosePathBezierPathElement: 1832 break; 1833 default: 1834 break; 1835 } 1836 } 1837 } 1838} 1839 1840- (id)initWithCoder:(NSCoder *)aCoder 1841{ 1842 // We have to init the place to store the elements 1843 [self init]; 1844 _cacheImage = nil; 1845 _shouldRecalculateBounds = YES; 1846 1847 if ([aCoder allowsKeyedCoding]) 1848 { 1849 float f; 1850 int i; 1851 1852 if ([aCoder containsValueForKey: @"NSFlatness"]) 1853 { 1854 f = [aCoder decodeFloatForKey: @"NSFlatness"]; 1855 [self setFlatness: f]; 1856 } 1857 if ([aCoder containsValueForKey: @"NSLineWidth"]) 1858 { 1859 f = [aCoder decodeFloatForKey: @"NSLineWidth"]; 1860 [self setLineWidth: f]; 1861 } 1862 if ([aCoder containsValueForKey: @"NSLineCapStyle"]) 1863 { 1864 i = [aCoder decodeIntForKey: @"NSLineCapStyle"]; 1865 [self setLineCapStyle: i]; 1866 } 1867 if ([aCoder containsValueForKey: @"NSLineJoinStyle"]) 1868 { 1869 i = [aCoder decodeIntForKey: @"NSLineJoinStyle"]; 1870 [self setLineJoinStyle: i]; 1871 } 1872 if ([aCoder containsValueForKey: @"NSWindingRule"]) 1873 { 1874 i = [aCoder decodeIntForKey: @"NSWindingRule"]; 1875 [self setWindingRule: i]; 1876 } 1877 if ([aCoder containsValueForKey: @"NSMiterLimit"]) 1878 { 1879 f = [aCoder decodeFloatForKey: @"NSMiterLimit"]; 1880 [self setMiterLimit: f]; 1881 } 1882 1883 if ([aCoder containsValueForKey: @"NSSegments"]) 1884 { 1885 NSUInteger length; 1886 const uint8_t *data; 1887 NSData *d; 1888 unsigned int cursor = 0; 1889 1890 data = [aCoder decodeBytesForKey: @"NSSegments" 1891 returnedLength: &length]; 1892 d = [NSData dataWithBytes: data length: length]; 1893 //NSLog(@"decoded segments %@", d); 1894 while (cursor < length) 1895 { 1896 char c; 1897 float f, g; 1898 NSPoint p, cp1, cp2; 1899 1900 [d deserializeDataAt: &c 1901 ofObjCType: "c" 1902 atCursor: &cursor 1903 context: nil]; 1904 switch (c) 1905 { 1906 case NSMoveToBezierPathElement: 1907 [d deserializeDataAt: &f 1908 ofObjCType: "f" 1909 atCursor: &cursor 1910 context: nil]; 1911 [d deserializeDataAt: &g 1912 ofObjCType: "f" 1913 atCursor: &cursor 1914 context: nil]; 1915 p = NSMakePoint(f, g); 1916 [self moveToPoint: p]; 1917 //NSLog(@"Decoded move %@", NSStringFromPoint(p)); 1918 break; 1919 case NSLineToBezierPathElement: 1920 1921 [d deserializeDataAt: &f 1922 ofObjCType: "f" 1923 atCursor: &cursor 1924 context: nil]; 1925 [d deserializeDataAt: &g 1926 ofObjCType: "f" 1927 atCursor: &cursor 1928 context: nil]; 1929 p = NSMakePoint(f, g); 1930 [self lineToPoint: p]; 1931 //NSLog(@"Decoded line %@", NSStringFromPoint(p)); 1932 break; 1933 case NSCurveToBezierPathElement: 1934 [d deserializeDataAt: &f 1935 ofObjCType: "f" 1936 atCursor: &cursor 1937 context: nil]; 1938 [d deserializeDataAt: &g 1939 ofObjCType: "f" 1940 atCursor: &cursor 1941 context: nil]; 1942 cp1 = NSMakePoint(f, g); 1943 [d deserializeDataAt: &c 1944 ofObjCType: "c" 1945 atCursor: &cursor 1946 context: nil]; 1947 [d deserializeDataAt: &f 1948 ofObjCType: "f" 1949 atCursor: &cursor 1950 context: nil]; 1951 [d deserializeDataAt: &g 1952 ofObjCType: "f" 1953 atCursor: &cursor 1954 context: nil]; 1955 cp2 = NSMakePoint(f, g); 1956 [d deserializeDataAt: &c 1957 ofObjCType: "c" 1958 atCursor: &cursor 1959 context: nil]; 1960 [d deserializeDataAt: &f 1961 ofObjCType: "f" 1962 atCursor: &cursor 1963 context: nil]; 1964 [d deserializeDataAt: &g 1965 ofObjCType: "f" 1966 atCursor: &cursor 1967 context: nil]; 1968 p = NSMakePoint(f, g); 1969 [self curveToPoint: p 1970 controlPoint1: cp1 1971 controlPoint2: cp2]; 1972 //NSLog(@"Decoded curve %@ %@ %@", NSStringFromPoint(p), NSStringFromPoint(cp1), NSStringFromPoint(cp2)); 1973 break; 1974 case NSClosePathBezierPathElement: 1975 [d deserializeDataAt: &f 1976 ofObjCType: "f" 1977 atCursor: &cursor 1978 context: nil]; 1979 [d deserializeDataAt: &g 1980 ofObjCType: "f" 1981 atCursor: &cursor 1982 context: nil]; 1983 p = NSMakePoint(f, g); 1984 [d deserializeDataAt: &c 1985 ofObjCType: "c" 1986 atCursor: &cursor 1987 context: nil]; 1988 [d deserializeDataAt: &f 1989 ofObjCType: "f" 1990 atCursor: &cursor 1991 context: nil]; 1992 [d deserializeDataAt: &g 1993 ofObjCType: "f" 1994 atCursor: &cursor 1995 context: nil]; 1996 cp1 = NSMakePoint(f, g); 1997 //NSLog(@"Decoded close %@ %@", NSStringFromPoint(p), NSStringFromPoint(cp1)); 1998 [self closePath]; 1999 break; 2000 default: 2001 //NSLog(@"Unable to decode unknown bezier path element type %d", c); 2002 break; 2003 } 2004 } 2005 } 2006 } 2007 else 2008 { 2009 NSBezierPathElement type; 2010 NSPoint pts[3]; 2011 int i, count; 2012 float f; 2013 int version = [aCoder versionForClassName: @"NSBezierPath"]; 2014 2015 [aCoder decodeValueOfObjCType: @encode(float) at: &f]; 2016 [self setLineWidth: f]; 2017 [aCoder decodeValueOfObjCType: @encode(int) at: &i]; 2018 [self setLineCapStyle: i]; 2019 [aCoder decodeValueOfObjCType: @encode(int) at: &i]; 2020 [self setLineJoinStyle: i]; 2021 [aCoder decodeValueOfObjCType: @encode(int) at: &i]; 2022 [self setWindingRule: i]; 2023 [aCoder decodeValueOfObjCType: @encode(BOOL) at: &_cachesBezierPath]; 2024 2025 if (version >= 2) 2026 { 2027 [aCoder decodeValueOfObjCType: @encode(float) at: &f]; 2028 [self setFlatness: f]; 2029 [aCoder decodeValueOfObjCType: @encode(float) at: &f]; 2030 [self setMiterLimit: f]; 2031 } 2032 2033 [aCoder decodeValueOfObjCType: @encode(int) at: &count]; 2034 2035 for (i = 0; i < count; i++) 2036 { 2037 [aCoder decodeValueOfObjCType: @encode(int) at: &type]; 2038 switch(type) 2039 { 2040 case NSMoveToBezierPathElement: 2041 pts[0] = [aCoder decodePoint]; 2042 [self moveToPoint: pts[0]]; 2043 break; 2044 case NSLineToBezierPathElement: 2045 pts[0] = [aCoder decodePoint]; 2046 [self lineToPoint: pts[0]]; 2047 break; 2048 case NSCurveToBezierPathElement: 2049 pts[0] = [aCoder decodePoint]; 2050 pts[1] = [aCoder decodePoint]; 2051 pts[2] = [aCoder decodePoint]; 2052 [self curveToPoint: pts[2] controlPoint1: pts[0] controlPoint2: pts[1]]; 2053 break; 2054 case NSClosePathBezierPathElement: 2055 [self closePath]; 2056 break; 2057 default: 2058 break; 2059 } 2060 } 2061 } 2062 2063 return self; 2064} 2065 2066// 2067// NSCopying Protocol 2068// 2069- (id)copyWithZone:(NSZone *)zone 2070{ 2071 NSBezierPath *path = (NSBezierPath*)NSCopyObject (self, 0, zone); 2072 2073 if (_cachesBezierPath && _cacheImage) 2074 path->_cacheImage = [_cacheImage copy]; 2075 2076 if (_dash_pattern != NULL) 2077 { 2078 CGFloat *pattern = NSZoneMalloc(zone, _dash_count * sizeof(CGFloat)); 2079 2080 memcpy(pattern, _dash_pattern, _dash_count * sizeof(CGFloat)); 2081 _dash_pattern = pattern; 2082 } 2083 2084 path->_pathElements = GSIArrayCopyWithZone(_pathElements, zone); 2085 2086 return path; 2087} 2088 2089@end 2090 2091 2092@implementation NSBezierPath (PrivateMethods) 2093 2094- (void) _invalidateCache 2095{ 2096 _shouldRecalculateBounds = YES; 2097 DESTROY(_cacheImage); 2098} 2099 2100 2101/* Helper for -_recalculateBounds. */ 2102static NSPoint point_on_curve(double t, NSPoint a, NSPoint b, NSPoint c, 2103 NSPoint d) 2104{ 2105 double ti = 1.0 - t; 2106 return NSMakePoint(ti * ti * ti * a.x + 3 * ti * ti * t * b.x 2107 + 3 * ti * t * t * c.x + t * t * t * d.x, 2108 ti * ti * ti * a.y + 3 * ti * ti * t * b.y 2109 + 3 * ti * t * t * c.y + t * t * t * d.y); 2110} 2111 2112- (void)_recalculateBounds 2113{ 2114 NSBezierPathElement type; 2115 NSPoint p; /* Current point. */ 2116 NSPoint pts[3]; 2117 NSPoint min, max; /* Path bounding box. */ 2118 NSPoint cmin, cmax; /* Control-point bounding box. */ 2119 int i, count, num_curves; 2120 2121 count = [self elementCount]; 2122 if (!count) 2123 { 2124 _bounds = NSZeroRect; 2125 _controlPointBounds = NSZeroRect; 2126 _shouldRecalculateBounds = NO; 2127 return; 2128 } 2129 2130 p = min = max = cmin = cmax = NSMakePoint(0, 0); 2131 2132#define CHECK_MAX(max, p) \ 2133 if (p.x > max.x) max.x = p.x; \ 2134 if (p.y > max.y) max.y = p.y; 2135#define CHECK_MIN(min, p) \ 2136 if (p.x < min.x) min.x = p.x; \ 2137 if (p.y < min.y) min.y = p.y; 2138 2139 num_curves = 0; 2140 for (i = 0; i < count; i++) 2141 { 2142 type = [self elementAtIndex: i associatedPoints: pts]; 2143 2144 if (i == 0) 2145 { 2146 cmin = cmax = min = max = p = pts[0]; 2147 } 2148 2149 switch (type) 2150 { 2151 case NSClosePathBezierPathElement: 2152 p = pts[0]; 2153 continue; 2154 2155 case NSMoveToBezierPathElement: 2156 case NSLineToBezierPathElement: 2157 CHECK_MAX(max, pts[0]) 2158 CHECK_MIN(min, pts[0]) 2159 p = pts[0]; 2160 break; 2161 2162 case NSCurveToBezierPathElement: 2163 { 2164 double t0, t1, t; 2165 NSPoint q; 2166 2167 num_curves++; 2168 CHECK_MAX(cmax, pts[0]) 2169 CHECK_MIN(cmin, pts[0]) 2170 CHECK_MAX(cmax, pts[1]) 2171 CHECK_MIN(cmin, pts[1]) 2172 2173 CHECK_MAX(max, pts[2]) 2174 CHECK_MIN(min, pts[2]) 2175 2176#define CHECK_CURVE_EXTREMES(x) \ 2177 t = (p.x * (pts[2].x - pts[1].x) \ 2178 + pts[0].x * (-pts[2].x - pts[1].x) \ 2179 + pts[1].x * pts[1].x + pts[0].x * pts[0].x); \ 2180 if (t >= 0.0) \ 2181 { \ 2182 t = sqrt(t); \ 2183 t0 = (pts[1].x - 2 * pts[0].x + p.x + t) \ 2184 / (-pts[2].x + 3 * pts[1].x - 3 * pts[0].x + p.x); \ 2185 t1 = (pts[1].x - 2 * pts[0].x + p.x - t) \ 2186 / (-pts[2].x + 3 * pts[1].x - 3 * pts[0].x + p.x); \ 2187\ 2188 if (t0 > 0.0 && t0 < 1.0) \ 2189 { \ 2190 q = point_on_curve(t0, p, pts[0], pts[1], pts[2]); \ 2191 CHECK_MAX(max, q) \ 2192 CHECK_MIN(min, q) \ 2193 } \ 2194 if (t1 > 0.0 && t1 < 1.0) \ 2195 { \ 2196 q = point_on_curve(t1, p, pts[0], pts[1], pts[2]); \ 2197 CHECK_MAX(max, q) \ 2198 CHECK_MIN(min, q) \ 2199 } \ 2200 } 2201 2202 CHECK_CURVE_EXTREMES(x) 2203 CHECK_CURVE_EXTREMES(y) 2204 2205#undef CHECK_CURVE_EXTREMES 2206 2207 p = pts[2]; 2208 break; 2209 } 2210 } 2211 } 2212 2213 /* If there were no curve elements, the control-point bounding box is the 2214 same as the path bounding box. Otherwise, the control-point bounding box 2215 is the union of the path bounding box and the bounding box of the curve 2216 control points. */ 2217 if (num_curves) 2218 { 2219 CHECK_MAX(cmax, max) 2220 CHECK_MIN(cmin, min) 2221 } 2222 else 2223 { 2224 cmin = min; 2225 cmax = max; 2226 } 2227 2228 _bounds = NSMakeRect(min.x, min.y, max.x - min.x, max.y - min.y); 2229 _controlPointBounds = NSMakeRect(cmin.x, cmin.y, 2230 cmax.x - cmin.x, cmax.y - cmin.y); 2231 _shouldRecalculateBounds = NO; 2232#undef CHECK_MAX 2233#undef CHECK_MIN 2234} 2235 2236@end 2237 2238#if 0 2239@implementation GSBezierPath 2240 2241- (void) appendBezierPath: (NSBezierPath *)aPath 2242{ 2243 PathElement elem; 2244 int i, count; 2245 2246 if (![aPath isKindOfClass: object_getClass(self)]) 2247 { 2248 [super appendBezierPath: aPath]; 2249 return; 2250 } 2251 2252 flat = flat && ((GSBezierPath*)aPath)->flat; 2253 count = [aPath elementCount]; 2254 2255 for (i = 0; i < count; i++) 2256 { 2257 elem = GSIArrayItemAtIndex(((GSBezierPath*)aPath)->pathElements, i).ext; 2258 GSIArrayAddItem(pathElements, (GSIArrayItem)elem); 2259 } 2260 INVALIDATE_CACHE(); 2261} 2262 2263@end // GSBezierPath 2264#endif 2265 2266static void flatten(NSPoint coeff[], CGFloat flatness, NSBezierPath *path) 2267{ 2268 // Check if the Bezier path defined by the four points has the given flatness. 2269 // If not split it up in the middle and recurse. 2270 // Otherwise add the end point to the path. 2271 BOOL flat = YES; 2272 2273 // This criteria for flatness is based on code from Libart which has the 2274 // following copyright: 2275/* Libart_LGPL - library of basic graphic primitives 2276 * Copyright (C) 1998 Raph Levien 2277 * 2278 * This library is free software; you can redistribute it and/or 2279 * modify it under the terms of the GNU Lesser General Public 2280 * License as published by the Free Software Foundation; either 2281 * version 2 of the License, or (at your option) any later version. 2282 * 2283 * This library is distributed in the hope that it will be useful, 2284 * but WITHOUT ANY WARRANTY; without even the implied warranty of 2285 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 2286 * Lesser General Public License for more details. 2287 * 2288 * You should have received a copy of the GNU Lesser General Public 2289 * License along with this library; if not, write to the 2290 * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 2291 * Boston, MA 02110-1301, USA. 2292 */ 2293 2294 double x1_0, y1_0; 2295 double x3_2, y3_2; 2296 double x3_0, y3_0; 2297 double z3_0_dot; 2298 double z1_dot, z2_dot; 2299 double z1_perp, z2_perp; 2300 double max_perp_sq; 2301 2302 x3_0 = coeff[3].x - coeff[0].x; 2303 y3_0 = coeff[3].y - coeff[0].y; 2304 x3_2 = coeff[3].x - coeff[2].x; 2305 y3_2 = coeff[3].y - coeff[2].y; 2306 x1_0 = coeff[1].x - coeff[0].x; 2307 y1_0 = coeff[1].y - coeff[0].y; 2308 z3_0_dot = x3_0 * x3_0 + y3_0 * y3_0; 2309 2310 if (z3_0_dot < 0.001) 2311 flat = YES; 2312 else 2313 { 2314 max_perp_sq = flatness * flatness * z3_0_dot; 2315 2316 z1_perp = y1_0 * x3_0 - x1_0 * y3_0; 2317 if (z1_perp * z1_perp > max_perp_sq) 2318 flat = NO; 2319 else 2320 { 2321 z2_perp = y3_2 * x3_0 - x3_2 * y3_0; 2322 if (z2_perp * z2_perp > max_perp_sq) 2323 flat = NO; 2324 else 2325 { 2326 z1_dot = x1_0 * x3_0 + y1_0 * y3_0; 2327 if (z1_dot < 0 && z1_dot * z1_dot > max_perp_sq) 2328 flat = NO; 2329 else 2330 { 2331 z2_dot = x3_2 * x3_0 + y3_2 * y3_0; 2332 if (z2_dot < 0 && z2_dot * z2_dot > max_perp_sq) 2333 flat = NO; 2334 else 2335 { 2336 if ((z1_dot + z1_dot > z3_0_dot) || 2337 (z2_dot + z2_dot > z3_0_dot)) 2338 flat = NO; 2339 } 2340 } 2341 } 2342 } 2343 } 2344 2345 if (!flat) 2346 { 2347 NSPoint bleft[4], bright[4]; 2348 2349 bleft[0] = coeff[0]; 2350 bleft[1].x = (coeff[0].x + coeff[1].x) / 2; 2351 bleft[1].y = (coeff[0].y + coeff[1].y) / 2; 2352 bleft[2].x = (coeff[0].x + 2*coeff[1].x + coeff[2].x) / 4; 2353 bleft[2].y = (coeff[0].y + 2*coeff[1].y + coeff[2].y) / 4; 2354 bleft[3].x = (coeff[0].x + 3*(coeff[1].x + coeff[2].x) + coeff[3].x) / 8; 2355 bleft[3].y = (coeff[0].y + 3*(coeff[1].y + coeff[2].y) + coeff[3].y) / 8; 2356 bright[0].x = bleft[3].x; 2357 bright[0].y = bleft[3].y; 2358 bright[1].x = (coeff[3].x + 2*coeff[2].x + coeff[1].x) / 4; 2359 bright[1].y = (coeff[3].y + 2*coeff[2].y + coeff[1].y) / 4; 2360 bright[2].x = (coeff[3].x + coeff[2].x) / 2; 2361 bright[2].y = (coeff[3].y + coeff[2].y) / 2; 2362 bright[3] = coeff[3]; 2363 2364 flatten(bleft, flatness, path); 2365 flatten(bright, flatness, path); 2366 } 2367 else 2368 { 2369 //[path lineToPoint: coeff[1]]; 2370 //[path lineToPoint: coeff[2]]; 2371 [path lineToPoint: coeff[3]]; 2372 } 2373} 2374 2375