root / ImageMagick / branches / ImageMagick-6.3.5 / magick / draw.c

Revision 8050, 182.7 kB (checked in by cristy, 14 months ago)
Line 
1/*
2%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3%                                                                             %
4%                                                                             %
5%                                                                             %
6%                        DDDD   RRRR    AAA   W   W                           %
7%                        D   D  R   R  A   A  W   W                           %
8%                        D   D  RRRR   AAAAA  W W W                           %
9%                        D   D  R RN   A   A  WW WW                           %
10%                        DDDD   R  R   A   A  W   W                           %
11%                                                                             %
12%                                                                             %
13%                     ImageMagick Image Drawing Methods                       %
14%                                                                             %
15%                                                                             %
16%                              Software Design                                %
17%                                John Cristy                                  %
18%                                 July 1998                                   %
19%                                                                             %
20%                                                                             %
21%  Copyright 1999-2007 ImageMagick Studio LLC, a non-profit organization      %
22%  dedicated to making software imaging solutions freely available.           %
23%                                                                             %
24%  You may not use this file except in compliance with the License.  You may  %
25%  obtain a copy of the License at                                            %
26%                                                                             %
27%    http://www.imagemagick.org/script/license.php                            %
28%                                                                             %
29%  Unless required by applicable law or agreed to in writing, software        %
30%  distributed under the License is distributed on an "AS IS" BASIS,          %
31%  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.   %
32%  See the License for the specific language governing permissions and        %
33%  limitations under the License.                                             %
34%                                                                             %
35%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
36%
37% Bill Radcliffe of Corbis (www.corbis.com) contributed the polygon
38% rendering code based on Paul Heckbert's "Concave Polygon Scan Conversion",
39% Graphics Gems, 1990.  Leonard Rosenthal and David Harr of Appligent
40% (www.appligent.com) contributed the dash pattern, linecap stroking
41% algorithm, and minor rendering improvements.
42%
43*/
44
45/*
46  Include declarations.
47*/
48#include "magick/studio.h"
49#include "magick/annotate.h"
50#include "magick/blob.h"
51#include "magick/cache.h"
52#include "magick/cache-view.h"
53#include "magick/color.h"
54#include "magick/composite.h"
55#include "magick/composite-private.h"
56#include "magick/constitute.h"
57#include "magick/draw.h"
58#include "magick/draw-private.h"
59#include "magick/enhance.h"
60#include "magick/exception.h"
61#include "magick/exception-private.h"
62#include "magick/gem.h"
63#include "magick/geometry.h"
64#include "magick/image-private.h"
65#include "magick/list.h"
66#include "magick/log.h"
67#include "magick/monitor.h"
68#include "magick/option.h"
69#include "magick/paint.h"
70#include "magick/pixel-private.h"
71#include "magick/property.h"
72#include "magick/resample.h"
73#include "magick/string_.h"
74#include "magick/token.h"
75#include "magick/transform.h"
76#include "magick/utility.h"
77
78/*
79  Define declarations.
80*/
81#define BezierQuantum  200
82
83/*
84  Typedef declarations.
85*/
86typedef struct _EdgeInfo
87{
88  SegmentInfo
89    bounds;
90
91  MagickRealType
92    scanline;
93
94  PointInfo
95    *points;
96
97  unsigned long
98    number_points;
99
100  long
101    direction;
102
103  MagickBooleanType
104    ghostline;
105
106  unsigned long
107    highwater;
108} EdgeInfo;
109
110typedef struct _ElementInfo
111{
112  MagickRealType
113    cx,
114    cy,
115    major,
116    minor,
117    angle;
118} ElementInfo;
119
120typedef struct _PolygonInfo
121{
122  EdgeInfo
123    *edges;
124
125  unsigned long
126    number_edges;
127} PolygonInfo;
128
129typedef enum
130{
131  MoveToCode,
132  OpenCode,
133  GhostlineCode,
134  LineToCode,
135  EndCode
136} PathInfoCode;
137
138typedef struct _PathInfo
139{
140  PointInfo
141    point;
142
143  PathInfoCode
144    code;
145} PathInfo;
146
147/*
148  Forward declarations.
149*/
150static PrimitiveInfo
151  *TraceStrokePolygon(const DrawInfo *,const PrimitiveInfo *);
152
153static MagickBooleanType
154  DrawStrokePolygon(Image *,const DrawInfo *,const PrimitiveInfo *);
155
156static unsigned long
157  TracePath(PrimitiveInfo *,const char *);
158
159static void
160  TraceArc(PrimitiveInfo *,const PointInfo,const PointInfo,const PointInfo),
161  TraceArcPath(PrimitiveInfo *,const PointInfo,const PointInfo,const PointInfo,
162    const MagickRealType,const MagickBooleanType,const MagickBooleanType),
163  TraceBezier(PrimitiveInfo *,const unsigned long),
164  TraceCircle(PrimitiveInfo *,const PointInfo,const PointInfo),
165  TraceEllipse(PrimitiveInfo *,const PointInfo,const PointInfo,const PointInfo),
166  TraceLine(PrimitiveInfo *,const PointInfo,const PointInfo),
167  TraceRectangle(PrimitiveInfo *,const PointInfo,const PointInfo),
168  TraceRoundRectangle(PrimitiveInfo *,const PointInfo,const PointInfo,
169    PointInfo),
170  TraceSquareLinecap(PrimitiveInfo *,const unsigned long,const MagickRealType);
171
172/*
173%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
174%                                                                             %
175%                                                                             %
176%                                                                             %
177%   A c q u i r e D r a w I n f o                                             %
178%                                                                             %
179%                                                                             %
180%                                                                             %
181%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
182%
183%  AcquireDrawInfo() returns a DrawInfo structure properly initialized.
184%
185%  The format of the AcquireDrawInfo method is:
186%
187%      DrawInfo *AcquireDrawInfo(void)
188%
189*/
190MagickExport DrawInfo *AcquireDrawInfo(void)
191{
192  DrawInfo
193    *draw_info;
194
195  draw_info=(DrawInfo *) AcquireMagickMemory(sizeof(*draw_info));
196  if (draw_info == (DrawInfo *) NULL)
197    ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
198  GetDrawInfo((ImageInfo *) NULL,draw_info);
199  return(draw_info);
200}
201
202/*
203%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
204%                                                                             %
205%                                                                             %
206%                                                                             %
207%   C l o n e D r a w I n f o                                                 %
208%                                                                             %
209%                                                                             %
210%                                                                             %
211%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
212%
213%  CloneDrawInfo() makes a copy of the given draw info structure.  If NULL
214%  is specified, a new image info structure is created initialized to
215%  default values.
216%
217%  The format of the CloneDrawInfo method is:
218%
219%      DrawInfo *CloneDrawInfo(const ImageInfo *image_info,
220%        const DrawInfo *draw_info)
221%
222%  A description of each parameter follows:
223%
224%    o image_info: The image info.
225%
226%    o draw_info: The draw info.
227%
228*/
229MagickExport DrawInfo *CloneDrawInfo(const ImageInfo *image_info,
230  const DrawInfo *draw_info)
231{
232  DrawInfo
233    *clone_info;
234
235  clone_info=(DrawInfo *) AcquireMagickMemory(sizeof(*clone_info));
236  if (clone_info == (DrawInfo *) NULL)
237    ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
238  GetDrawInfo(image_info,clone_info);
239  if (draw_info == (DrawInfo *) NULL)
240    return(clone_info);
241  if (clone_info->primitive != (char *) NULL)
242    (void) CloneString(&clone_info->primitive,draw_info->primitive);
243  if (draw_info->geometry != (char *) NULL)
244    (void) CloneString(&clone_info->geometry,draw_info->geometry);
245  clone_info->viewbox=draw_info->viewbox;
246  clone_info->affine=draw_info->affine;
247  clone_info->gravity=draw_info->gravity;
248  clone_info->fill=draw_info->fill;
249  clone_info->stroke=draw_info->stroke;
250  clone_info->stroke_width=draw_info->stroke_width;
251  if (draw_info->fill_pattern != (Image *) NULL)
252    clone_info->fill_pattern=CloneImage(draw_info->fill_pattern,0,0,MagickTrue,
253      &draw_info->fill_pattern->exception);
254  else
255    if (draw_info->tile != (Image *) NULL)
256      clone_info->fill_pattern=CloneImage(draw_info->tile,0,0,MagickTrue,
257        &draw_info->tile->exception);
258  clone_info->tile=NewImageList();  /* tile is deprecated */
259  if (draw_info->stroke_pattern != (Image *) NULL)
260    clone_info->stroke_pattern=CloneImage(draw_info->stroke_pattern,0,0,
261      MagickTrue,&draw_info->stroke_pattern->exception);
262  clone_info->stroke_antialias=draw_info->stroke_antialias;
263  clone_info->text_antialias=draw_info->text_antialias;
264  clone_info->fill_rule=draw_info->fill_rule;
265  clone_info->linecap=draw_info->linecap;
266  clone_info->linejoin=draw_info->linejoin;
267  clone_info->miterlimit=draw_info->miterlimit;
268  clone_info->dash_offset=draw_info->dash_offset;
269  clone_info->decorate=draw_info->decorate;
270  clone_info->compose=draw_info->compose;
271  if (draw_info->text != (char *) NULL)
272    (void) CloneString(&clone_info->text,draw_info->text);
273  if (draw_info->font != (char *) NULL)
274    (void) CloneString(&clone_info->font,draw_info->font);
275  if (draw_info->metrics != (char *) NULL)
276    (void) CloneString(&clone_info->metrics,draw_info->metrics);
277  if (draw_info->family != (char *) NULL)
278    (void) CloneString(&clone_info->family,draw_info->family);
279  clone_info->style=draw_info->style;
280  clone_info->stretch=draw_info->stretch;
281  clone_info->weight=draw_info->weight;
282  if (draw_info->encoding != (char *) NULL)
283    (void) CloneString(&clone_info->encoding,draw_info->encoding);
284  clone_info->pointsize=draw_info->pointsize;
285  if (draw_info->density != (char *) NULL)
286    (void) CloneString(&clone_info->density,draw_info->density);
287  clone_info->align=draw_info->align;
288  clone_info->undercolor=draw_info->undercolor;
289  clone_info->border_color=draw_info->border_color;
290  if (draw_info->server_name != (char *) NULL)
291    (void) CloneString(&clone_info->server_name,draw_info->server_name);
292  if (draw_info->dash_pattern != (double *) NULL)
293    {
294      register long
295        x;
296
297      for (x=0; draw_info->dash_pattern[x] != 0.0; x++);
298      clone_info->dash_pattern=(double *) AcquireQuantumMemory((size_t) x+1UL,
299        sizeof(*clone_info->dash_pattern));
300      if (clone_info->dash_pattern == (double *) NULL)
301        ThrowFatalException(ResourceLimitFatalError,
302          "UnableToAllocateDashPattern");
303      (void) CopyMagickMemory(clone_info->dash_pattern,draw_info->dash_pattern,
304        (size_t) (x+1)*sizeof(*clone_info->dash_pattern));
305    }
306  clone_info->gradient=draw_info->gradient;
307  if (draw_info->gradient.stops != (StopInfo *) NULL)
308    {
309      unsigned long
310        number_stops;
311
312      number_stops=clone_info->gradient.number_stops;
313      clone_info->gradient.stops=(StopInfo *) AcquireQuantumMemory((size_t)
314        number_stops,sizeof(*clone_info->gradient.stops));
315      if (clone_info->gradient.stops == (StopInfo *) NULL)
316        ThrowFatalException(ResourceLimitFatalError,
317          "UnableToAllocateDashPattern");
318      (void) CopyMagickMemory(clone_info->gradient.stops,
319        draw_info->gradient.stops,(size_t) number_stops*
320        sizeof(*clone_info->gradient.stops));
321    }
322  if (draw_info->clip_mask != (char *) NULL)
323    (void) CloneString(&clone_info->clip_mask,draw_info->clip_mask);
324  clone_info->bounds=draw_info->bounds;
325  clone_info->clip_units=draw_info->clip_units;
326  clone_info->render=draw_info->render;
327  clone_info->opacity=draw_info->opacity;
328  clone_info->element_reference=draw_info->element_reference;
329  clone_info->debug=IsEventLogging();
330  return(clone_info);
331}
332
333/*
334%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
335%                                                                             %
336%                                                                             %
337%                                                                             %
338+   C o n v e r t P a t h T o P o l y g o n                                   %
339%                                                                             %
340%                                                                             %
341%                                                                             %
342%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
343%
344%  ConvertPathToPolygon() converts a path to the more efficient sorted
345%  rendering form.
346%
347%  The format of the ConvertPathToPolygon method is:
348%
349%      PolygonInfo *ConvertPathToPolygon(const DrawInfo *draw_info,
350%        const PathInfo *path_info)
351%
352%  A description of each parameter follows:
353%
354%    o Method ConvertPathToPolygon returns the path in a more efficient sorted
355%      rendering form of type PolygonInfo.
356%
357%    o draw_info: Specifies a pointer to an DrawInfo structure.
358%
359%    o path_info: Specifies a pointer to an PathInfo structure.
360%
361%
362*/
363
364#if defined(__cplusplus) || defined(c_plusplus)
365extern "C" {
366#endif
367
368static int CompareEdges(const void *x,const void *y)
369{
370  register const EdgeInfo
371    *p,
372    *q;
373
374  /*
375    Compare two edges.
376  */
377  p=(const EdgeInfo *) x;
378  q=(const EdgeInfo *) y;
379  if ((p->points[0].y-MagickEpsilon) > q->points[0].y)
380    return(1);
381  if ((p->points[0].y+MagickEpsilon) < q->points[0].y)
382    return(-1);
383  if ((p->points[0].x-MagickEpsilon) > q->points[0].x)
384    return(1);
385  if ((p->points[0].x+MagickEpsilon) < q->points[0].x)
386    return(-1);
387  if (((p->points[1].x-p->points[0].x)*(q->points[1].y-q->points[0].y)-
388       (p->points[1].y-p->points[0].y)*(q->points[1].x-q->points[0].x)) > 0.0)
389    return(1);
390  return(-1);
391}
392
393#if defined(__cplusplus) || defined(c_plusplus)
394}
395#endif
396
397static void LogPolygonInfo(const PolygonInfo *polygon_info)
398{
399  register EdgeInfo
400    *p;
401
402  register long
403    i,
404    j;
405
406  (void) LogMagickEvent(DrawEvent,GetMagickModule(),"    begin active-edge");
407  p=polygon_info->edges;
408  for (i=0; i < (long) polygon_info->number_edges; i++)
409  {
410    (void) LogMagickEvent(DrawEvent,GetMagickModule(),"      edge %lu:",i);
411    (void) LogMagickEvent(DrawEvent,GetMagickModule(),"      direction: %s",
412      p->direction != MagickFalse ? "down" : "up");
413    (void) LogMagickEvent(DrawEvent,GetMagickModule(),"      ghostline: %s",
414      p->ghostline != MagickFalse ? "transparent" : "opaque");
415    (void) LogMagickEvent(DrawEvent,GetMagickModule(),
416      "      bounds: %g,%g - %g,%g",p->bounds.x1,p->bounds.y1,p->bounds.x2,
417      p->bounds.y2);
418    for (j=0; j < (long) p->number_points; j++)
419      (void) LogMagickEvent(DrawEvent,GetMagickModule(),"        %g,%g",
420        p->points[j].x,p->points[j].y);
421    p++;
422  }
423  (void) LogMagickEvent(DrawEvent,GetMagickModule(),"    end active-edge");
424}
425
426static void ReversePoints(PointInfo *points,const unsigned long number_points)
427{
428  PointInfo
429    point;
430
431  register long
432    i;
433
434  for (i=0; i < (long) (number_points >> 1); i++)
435  {
436    point=points[i];
437    points[i]=points[number_points-(i+1)];
438    points[number_points-(i+1)]=point;
439  }
440}
441
442static PolygonInfo *ConvertPathToPolygon(
443  const DrawInfo *magick_unused(draw_info),const PathInfo *path_info)
444{
445  long
446    direction,
447    next_direction;
448
449  PointInfo
450    point,
451    *points;
452
453  PolygonInfo
454    *polygon_info;
455
456  SegmentInfo
457    bounds;
458
459  register long
460    i,
461    n;
462
463  MagickBooleanType
464    ghostline;
465
466  unsigned long
467    edge,
468    number_edges,
469    number_points;
470
471  /*
472    Convert a path to the more efficient sorted rendering form.
473  */
474  polygon_info=(PolygonInfo *) AcquireMagickMemory(sizeof(*polygon_info));
475  if (polygon_info == (PolygonInfo *) NULL)
476    return((PolygonInfo *) NULL);
477  number_edges=16;
478  polygon_info->edges=(EdgeInfo *) AcquireQuantumMemory((size_t) number_edges,
479    sizeof(*polygon_info->edges));
480  if (polygon_info->edges == (EdgeInfo *) NULL)
481    return((PolygonInfo *) NULL);
482  direction=0;
483  edge=0;
484  ghostline=MagickFalse;
485  n=0;
486  number_points=0;
487  points=(PointInfo *) NULL;
488  (void) ResetMagickMemory(&point,0,sizeof(point));
489  (void) ResetMagickMemory(&bounds,0,sizeof(bounds));
490  for (i=0; path_info[i].code != EndCode; i++)
491  {
492    if ((path_info[i].code == MoveToCode) || (path_info[i].code == OpenCode) ||
493        (path_info[i].code == GhostlineCode))
494      {
495        /*
496          Move to.
497        */
498        if ((points != (PointInfo *) NULL) && (n >= 2))
499          {
500            if (edge == number_edges)
501              {
502                number_edges<<=1;
503                polygon_info->edges=(EdgeInfo *) ResizeQuantumMemory(
504                  polygon_info->edges,(size_t) number_edges,
505                  sizeof(*polygon_info->edges));
506                if (polygon_info->edges == (EdgeInfo *) NULL)
507                  return((PolygonInfo *) NULL);
508              }
509            polygon_info->edges[edge].number_points=(unsigned long) n;
510            polygon_info->edges[edge].scanline=(-1.0);
511            polygon_info->edges[edge].highwater=0;
512            polygon_info->edges[edge].ghostline=ghostline;
513            polygon_info->edges[edge].direction=(long) (direction > 0);
514            if (direction < 0)
515              ReversePoints(points,(unsigned long) n);
516            polygon_info->edges[edge].points=points;
517            polygon_info->edges[edge].bounds=bounds;
518            polygon_info->edges[edge].bounds.y1=points[0].y;
519            polygon_info->edges[edge].bounds.y2=points[n-1].y;
520            points=(PointInfo *) NULL;
521            ghostline=MagickFalse;
522            edge++;
523          }
524        if (points == (PointInfo *) NULL)
525          {
526            number_points=16;
527            points=(PointInfo *) AcquireQuantumMemory((size_t) number_points,
528              sizeof(*points));
529            if (points == (PointInfo *) NULL)
530              return((PolygonInfo *) NULL);
531          }
532        ghostline=path_info[i].code == GhostlineCode ? MagickTrue : MagickFalse;
533        point=path_info[i].point;
534        points[0]=point;
535        bounds.x1=point.x;
536        bounds.x2=point.x;
537        direction=0;
538        n=1;
539        continue;
540      }
541    /*
542      Line to.
543    */
544    next_direction=((path_info[i].point.y > point.y) ||
545      ((path_info[i].point.y == point.y) &&
546       (path_info[i].point.x > point.x))) ? 1 : -1;
547    if ((direction != 0) && (direction != next_direction))
548      {
549        /*
550          New edge.
551        */
552        point=points[n-1];
553        if (edge == number_edges)
554          {
555            number_edges<<=1;
556            polygon_info->edges=(EdgeInfo *) ResizeQuantumMemory(
557              polygon_info->edges,(size_t) number_edges,
558              sizeof(*polygon_info->edges));
559            if (polygon_info->edges == (EdgeInfo *) NULL)
560              return((PolygonInfo *) NULL);
561          }
562        polygon_info->edges[edge].number_points=(unsigned long) n;
563        polygon_info->edges[edge].scanline=(-1.0);
564        polygon_info->edges[edge].highwater=0;
565        polygon_info->edges[edge].ghostline=ghostline;
566        polygon_info->edges[edge].direction=(long) (direction > 0);
567        if (direction < 0)
568          ReversePoints(points,(unsigned long) n);
569        polygon_info->edges[edge].points=points;
570        polygon_info->edges[edge].bounds=bounds;
571        polygon_info->edges[edge].bounds.y1=points[0].y;
572        polygon_info->edges[edge].bounds.y2=points[n-1].y;
573        number_points=16;
574        points=(PointInfo *) AcquireQuantumMemory((size_t) number_points,
575          sizeof(*points));
576        if (points == (PointInfo *) NULL)
577          return((PolygonInfo *) NULL);
578        n=1;
579        ghostline=MagickFalse;
580        points[0]=point;
581        bounds.x1=point.x;
582        bounds.x2=point.x;
583        edge++;
584      }
585    direction=next_direction;
586    if (points == (PointInfo *) NULL)
587      continue;
588    if (n == (long) number_points)
589      {
590        number_points<<=1;
591        points=(PointInfo *) ResizeQuantumMemory(points,(size_t) number_points,
592          sizeof(*points));
593        if (points == (PointInfo *) NULL)
594          return((PolygonInfo *) NULL);
595      }
596    point=path_info[i].point;
597    points[n]=point;
598    if (point.x < bounds.x1)
599      bounds.x1=point.x;
600    if (point.x > bounds.x2)
601      bounds.x2=point.x;
602    n++;
603  }
604  if (points != (PointInfo *) NULL)
605    {
606      if (n < 2)
607        points=(PointInfo *) RelinquishMagickMemory(points);
608      else
609        {
610          if (edge == number_edges)
611            {
612              number_edges<<=1;
613              polygon_info->edges=(EdgeInfo *) ResizeQuantumMemory(
614                polygon_info->edges,(size_t) number_edges,
615                sizeof(*polygon_info->edges));
616              if (polygon_info->edges == (EdgeInfo *) NULL)
617                return((PolygonInfo *) NULL);
618            }
619          polygon_info->edges[edge].number_points=(unsigned long) n;
620          polygon_info->edges[edge].scanline=(-1.0);
621          polygon_info->edges[edge].highwater=0;
622          polygon_info->edges[edge].ghostline=ghostline;
623          polygon_info->edges[edge].direction=(long) (direction > 0);
624          if (direction < 0)
625            ReversePoints(points,(unsigned long) n);
626          polygon_info->edges[edge].points=points;
627          polygon_info->edges[edge].bounds=bounds;
628          polygon_info->edges[edge].bounds.y1=points[0].y;
629          polygon_info->edges[edge].bounds.y2=points[n-1].y;
630          ghostline=MagickFalse;
631          edge++;
632        }
633    }
634  polygon_info->number_edges=edge;
635  qsort(polygon_info->edges,(size_t) polygon_info->number_edges,
636    sizeof(*polygon_info->edges),CompareEdges);
637  if (IsEventLogging() != MagickFalse)
638    LogPolygonInfo(polygon_info);
639  return(polygon_info);
640}
641
642/*
643%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
644%                                                                             %
645%                                                                             %
646%                                                                             %
647+   C o n v e r t P r i m i t i v e T o P a t h                               %
648%                                                                             %
649%                                                                             %
650%                                                                             %
651%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
652%
653%  ConvertPrimitiveToPath() converts a PrimitiveInfo structure into a vector
654%  path structure.
655%
656%  The format of the ConvertPrimitiveToPath method is:
657%
658%      PathInfo *ConvertPrimitiveToPath(const DrawInfo *draw_info,
659%        const PrimitiveInfo *primitive_info)
660%
661%  A description of each parameter follows:
662%
663%    o Method ConvertPrimitiveToPath returns a vector path structure of type
664%      PathInfo.
665%
666%    o draw_info: a structure of type DrawInfo.
667%
668%    o primitive_info: Specifies a pointer to an PrimitiveInfo structure.
669%
670%
671*/
672
673static void LogPathInfo(const PathInfo *path_info)
674{
675  register const PathInfo
676    *p;
677
678  (void) LogMagickEvent(DrawEvent,GetMagickModule(),"    begin vector-path");
679  for (p=path_info; p->code != EndCode; p++)
680    (void) LogMagickEvent(DrawEvent,GetMagickModule(),
681      "      %g,%g %s",p->point.x,p->point.y,p->code == GhostlineCode ?
682      "moveto ghostline" : p->code == OpenCode ? "moveto open" :
683      p->code == MoveToCode ? "moveto" : p->code == LineToCode ? "lineto" :
684      "?");
685  (void) LogMagickEvent(DrawEvent,GetMagickModule(),"    end vector-path");
686}
687
688static PathInfo *ConvertPrimitiveToPath(
689  const DrawInfo *magick_unused(draw_info),const PrimitiveInfo *primitive_info)
690{
691  long
692    coordinates,
693    start;
694
695  PathInfo
696    *path_info;
697
698  PathInfoCode
699    code;
700
701  PointInfo
702    p,
703    q;
704
705  register long
706    i,
707    n;
708
709  /*
710    Converts a PrimitiveInfo structure into a vector path structure.
711  */
712  switch (primitive_info->primitive)
713  {
714    case PointPrimitive:
715    case ColorPrimitive:
716    case MattePrimitive:
717    case TextPrimitive:
718    case ImagePrimitive:
719      return((PathInfo *) NULL);
720    default:
721      break;
722  }
723  for (i=0; primitive_info[i].primitive != UndefinedPrimitive; i++);
724  path_info=(PathInfo *) AcquireQuantumMemory((size_t) (2UL*i+3UL),
725    sizeof(*path_info));
726  if (path_info == (PathInfo *) NULL)
727    return((PathInfo *) NULL);
728  coordinates=0;
729  n=0;
730  p.x=(-1.0);
731  p.y=(-1.0);
732  q.x=(-1.0);
733  q.y=(-1.0);
734  start=0;
735  for (i=0; primitive_info[i].primitive != UndefinedPrimitive; i++)
736  {
737    code=LineToCode;
738    if (coordinates <= 0)
739      {
740        coordinates=(long) primitive_info[i].coordinates;
741        p=primitive_info[i].point;
742        start=n;
743        code=MoveToCode;
744      }
745    coordinates--;
746    /*
747      Eliminate duplicate points.
748    */
749    if ((i == 0) || (fabs(q.x-primitive_info[i].point.x) > MagickEpsilon) ||
750        (fabs(q.y-primitive_info[i].point.y) > MagickEpsilon))
751      {
752        path_info[n].code=code;
753        path_info[n].point=primitive_info[i].point;
754        q=primitive_info[i].point;
755        n++;
756      }
757    if (coordinates > 0)
758      continue;
759    if ((fabs(p.x-primitive_info[i].point.x) <= MagickEpsilon) &&
760        (fabs(p.y-primitive_info[i].point.y) <= MagickEpsilon))
761      continue;
762    /*
763      Mark the p point as open if it does not match the q.
764    */
765    path_info[start].code=OpenCode;
766    path_info[n].code=GhostlineCode;
767    path_info[n].point=primitive_info[i].point;
768    n++;
769    path_info[n].code=LineToCode;
770    path_info[n].point=p;
771    n++;
772  }
773  path_info[n].code=EndCode;
774  path_info[n].point.x=0.0;
775  path_info[n].point.y=0.0;
776  if (IsEventLogging() != MagickFalse)
777    LogPathInfo(path_info);
778  return(path_info);
779}
780
781/*
782%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
783%                                                                             %
784%                                                                             %
785%                                                                             %
786%   D e s t r o y D r a w I n f o                                             %
787%                                                                             %
788%                                                                             %
789%                                                                             %
790%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
791%
792%  DestroyDrawInfo() deallocates memory associated with an DrawInfo
793%  structure.
794%
795%  The format of the DestroyDrawInfo method is:
796%
797%      DrawInfo *DestroyDrawInfo(DrawInfo *draw_info)
798%
799%  A description of each parameter follows:
800%
801%    o draw_info: The draw info.
802%
803*/
804MagickExport DrawInfo *DestroyDrawInfo(DrawInfo *draw_info)
805{
806  if (draw_info->debug != MagickFalse)
807    (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
808  assert(draw_info != (DrawInfo *) NULL);
809  assert(draw_info->signature == MagickSignature);
810  if (draw_info->primitive != (char *) NULL)
811    draw_info->primitive=DestroyString(draw_info->primitive);
812  if (draw_info->text != (char *) NULL)
813    draw_info->text=DestroyString(draw_info->text);
814  if (draw_info->geometry != (char *) NULL)
815    draw_info->geometry=DestroyString(draw_info->geometry);
816  if (draw_info->tile != (Image *) NULL)
817    draw_info->tile=DestroyImage(draw_info->tile);
818  if (draw_info->fill_pattern != (Image *) NULL)
819    draw_info->fill_pattern=DestroyImage(draw_info->fill_pattern);
820  if (draw_info->stroke_pattern != (Image *) NULL)
821    draw_info->stroke_pattern=DestroyImage(draw_info->stroke_pattern);
822  if (draw_info->font != (char *) NULL)
823    draw_info->font=DestroyString(draw_info->font);
824  if (draw_info->metrics != (char *) NULL)
825    draw_info->metrics=DestroyString(draw_info->metrics);
826  if (draw_info->family != (char *) NULL)
827    draw_info->family=DestroyString(draw_info->family);
828  if (draw_info->encoding != (char *) NULL)
829    draw_info->encoding=DestroyString(draw_info->encoding);
830  if (draw_info->density != (char *) NULL)
831    draw_info->density=DestroyString(draw_info->density);
832  if (draw_info->server_name != (char *) NULL)
833    draw_info->server_name=(char *)
834     RelinquishMagickMemory(draw_info->server_name);
835  if (draw_info->dash_pattern != (double *) NULL)
836    draw_info->dash_pattern=(double *) RelinquishMagickMemory(
837      draw_info->dash_pattern);
838  if (draw_info->gradient.stops != (StopInfo *) NULL)
839    draw_info->gradient.stops=(StopInfo *) RelinquishMagickMemory(
840      draw_info->gradient.stops);
841  if (draw_info->clip_mask != (char *) NULL)
842    draw_info->clip_mask=DestroyString(draw_info->clip_mask);
843  draw_info->signature=(~MagickSignature);
844  draw_info=(DrawInfo *) RelinquishMagickMemory(draw_info);
845  return(draw_info);
846}
847
848/*
849%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
850%                                                                             %
851%                                                                             %
852%                                                                             %
853+   D e s t r o y E d g e                                                     %
854%                                                                             %
855%                                                                             %
856%                                                                             %
857%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
858%
859%  DestroyEdge() destroys the specified polygon edge.
860%
861%  The format of the DestroyEdge method is:
862%
863%      long DestroyEdge(PolygonInfo *polygon_info,const int edge)
864%
865%  A description of each parameter follows:
866%
867%    o polygon_info: Specifies a pointer to an PolygonInfo structure.
868%
869%    o edge: the polygon edge number to destroy.
870%
871%
872*/
873static unsigned long DestroyEdge(PolygonInfo *polygon_info,
874  const unsigned long edge)
875{
876  assert(edge < polygon_info->number_edges);
877  polygon_info->edges[edge].points=(PointInfo *) RelinquishMagickMemory(
878    polygon_info->edges[edge].points);
879  polygon_info->number_edges--;
880  if (edge < polygon_info->number_edges)
881    (void) CopyMagickMemory(polygon_info->edges+edge,polygon_info->edges+edge+1,
882      (size_t) (polygon_info->number_edges-edge)*sizeof(*polygon_info->edges));
883  return(polygon_info->number_edges);
884}
885
886/*
887%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
888%                                                                             %
889%                                                                             %
890%                                                                             %
891+   D e s t r o y P o l y g o n I n f o                                       %
892%                                                                             %
893%                                                                             %
894%                                                                             %
895%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
896%
897%  DestroyPolygonInfo() destroys the PolygonInfo data structure.
898%
899%  The format of the DestroyPolygonInfo method is:
900%
901%      void DestroyPolygonInfo(PolygonInfo *polygon_info)
902%
903%  A description of each parameter follows:
904%
905%    o polygon_info: Specifies a pointer to an PolygonInfo structure.
906%
907*/
908static void DestroyPolygonInfo(PolygonInfo *polygon_info)
909{
910  register long
911    i;
912
913  for (i=0; i < (long) polygon_info->number_edges; i++)
914    polygon_info->edges[i].points=(PointInfo *)
915      RelinquishMagickMemory(polygon_info->edges[i].points);
916  polygon_info->edges=(EdgeInfo *) RelinquishMagickMemory(polygon_info->edges);
917  polygon_info=(PolygonInfo *) RelinquishMagickMemory(polygon_info);
918}
919
920/*
921%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
922%                                                                             %
923%                                                                             %
924%                                                                             %
925%     D r a w A f f i n e I m a g e                                           %
926%                                                                             %
927%                                                                             %
928%                                                                             %
929%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
930%
931%  DrawAffineImage() composites the source over the destination image as
932%  dictated by the affine transform.
933%
934%  The format of the DrawAffineImage method is:
935%
936%      MagickBooleanType DrawAffineImage(Image *image,const Image *source,
937%        const AffineMatrix *affine)
938%
939%  A description of each parameter follows:
940%
941%    o image: The image.
942%
943%    o source: The source image.
944%
945%    o affine: The affine transform.
946%
947*/
948
949static SegmentInfo AffineEdge(const Image *image,const AffineMatrix *affine,
950  const double y,const SegmentInfo *edge)
951{
952  double
953    intercept,
954    z;
955
956  register double
957    x;
958
959  SegmentInfo
960    inverse_edge;
961
962  /*
963