granicus.if.org Git - imagemagick/blob - MagickCore/layer.c

   1 /*
   2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   3 %                                                                             %
   4 %                                                                             %
   5 %                     L       AAA   Y   Y  EEEEE  RRRR                        %
   6 %                     L      A   A   Y Y   E      R   R                       %
   7 %                     L      AAAAA    Y    EEE    RRRR                        %
   8 %                     L      A   A    Y    E      R R                         %
   9 %                     LLLLL  A   A    Y    EEEEE  R  R                        %
  10 %                                                                             %
  11 %                      MagickCore Image Layering Methods                      %
  12 %                                                                             %
  13 %                              Software Design                                %
  14 %                                John Cristy                                  %
  15 %                              Anthony Thyssen                                %
  16 %                               January 2006                                  %
  17 %                                                                             %
  18 %                                                                             %
  19 %  Copyright 1999-2011 ImageMagick Studio LLC, a non-profit organization      %
  20 %  dedicated to making software imaging solutions freely available.           %
  21 %                                                                             %
  22 %  You may not use this file except in compliance with the License.  You may  %
  23 %  obtain a copy of the License at                                            %
  24 %                                                                             %
  25 %    http://www.imagemagick.org/script/license.php                            %
  26 %                                                                             %
  27 %  Unless required by applicable law or agreed to in writing, software        %
  28 %  distributed under the License is distributed on an "AS IS" BASIS,          %
  29 %  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.   %
  30 %  See the License for the specific language governing permissions and        %
  31 %  limitations under the License.                                             %
  32 %                                                                             %
  33 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  34 %
  35 */
  36 \f
  37 /*
  38   Include declarations.
  39 */
  40 #include "MagickCore/studio.h"
  41 #include "MagickCore/artifact.h"
  42 #include "MagickCore/cache.h"
  43 #include "MagickCore/color.h"
  44 #include "MagickCore/color-private.h"
  45 #include "MagickCore/composite.h"
  46 #include "MagickCore/effect.h"
  47 #include "MagickCore/exception.h"
  48 #include "MagickCore/exception-private.h"
  49 #include "MagickCore/geometry.h"
  50 #include "MagickCore/image.h"
  51 #include "MagickCore/layer.h"
  52 #include "MagickCore/list.h"
  53 #include "MagickCore/memory_.h"
  54 #include "MagickCore/monitor.h"
  55 #include "MagickCore/monitor-private.h"
  56 #include "MagickCore/option.h"
  57 #include "MagickCore/pixel-accessor.h"
  58 #include "MagickCore/property.h"
  59 #include "MagickCore/profile.h"
  60 #include "MagickCore/resource_.h"
  61 #include "MagickCore/resize.h"
  62 #include "MagickCore/statistic.h"
  63 #include "MagickCore/string_.h"
  64 #include "MagickCore/transform.h"
  65 \f
  66 /*
  67 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  68 %                                                                             %
  69 %                                                                             %
  70 %                                                                             %
  71 +     C l e a r B o u n d s                                                   %
  72 %                                                                             %
  73 %                                                                             %
  74 %                                                                             %
  75 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  76 %
  77 %  ClearBounds() Clear the area specified by the bounds in an image to
  78 %  transparency.  This typically used to handle Background Disposal
  79 %  for the previous frame in an animation sequence.
  80 %
  81 %  WARNING: no bounds checks are performed, except for the null or
  82 %  missed image, for images that don't change. in all other cases
  83 %  bound must fall within the image.
  84 %
  85 %  The format is:
  86 %
  87 %      void ClearBounds(Image *image,RectangleInfo *bounds)
  88 %
  89 %  A description of each parameter follows:
  90 %
  91 %    o image: the image to had the area cleared in
  92 %
  93 %    o bounds: the area to be clear within the imag image
  94 %
  95 */
  96 static void ClearBounds(Image *image,RectangleInfo *bounds)
  97 {
  98   ExceptionInfo
  99     *exception;
 100
 101   ssize_t
 102     y;
 103
 104   if (bounds->x < 0)
 105     return;
 106   exception=(&image->exception);
 107   if (image->matte == MagickFalse)
 108     (void) SetImageAlphaChannel(image,OpaqueAlphaChannel,exception);
 109   for (y=0; y < (ssize_t) bounds->height; y++)
 110   {
 111     register ssize_t
 112       x;
 113
 114     register Quantum
 115       *restrict q;
 116
 117     q=GetAuthenticPixels(image,bounds->x,bounds->y+y,bounds->width,1,exception);
 118     if (q == (Quantum *) NULL)
 119       break;
 120     for (x=0; x < (ssize_t) bounds->width; x++)
 121     {
 122       SetPixelAlpha(image,TransparentAlpha,q);
 123       q+=GetPixelChannels(image);
 124     }
 125     if (SyncAuthenticPixels(image,exception) == MagickFalse)
 126       break;
 127   }
 128 }
 129 \f
 130 /*
 131 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 132 %                                                                             %
 133 %                                                                             %
 134 %                                                                             %
 135 +     I s B o u n d s C l e a r e d                                           %
 136 %                                                                             %
 137 %                                                                             %
 138 %                                                                             %
 139 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 140 %
 141 %  IsBoundsCleared() tests whether any pixel in the bounds given, gets cleared
 142 %  when going from the first image to the second image.  This typically used
 143 %  to check if a proposed disposal method will work successfully to generate
 144 %  the second frame image from the first disposed form of the previous frame.
 145 %
 146 %  The format is:
 147 %
 148 %      MagickBooleanType IsBoundsCleared(const Image *image1,
 149 %        const Image *image2,RectangleInfo bounds,ExceptionInfo *exception)
 150 %
 151 %  A description of each parameter follows:
 152 %
 153 %    o image1, image 2: the images to check for cleared pixels
 154 %
 155 %    o bounds: the area to be clear within the imag image
 156 %
 157 %    o exception: return any errors or warnings in this structure.
 158 %
 159 %  WARNING: no bounds checks are performed, except for the null or
 160 %  missed image, for images that don't change. in all other cases
 161 %  bound must fall within the image.
 162 %
 163 */
 164 static MagickBooleanType IsBoundsCleared(const Image *image1,
 165   const Image *image2,RectangleInfo *bounds,ExceptionInfo *exception)
 166 {
 167   register ssize_t
 168     x;
 169
 170   register const Quantum
 171     *p,
 172     *q;
 173
 174   ssize_t
 175     y;
 176
 177   if (bounds->x < 0)
 178     return(MagickFalse);
 179   for (y=0; y < (ssize_t) bounds->height; y++)
 180   {
 181     p=GetVirtualPixels(image1,bounds->x,bounds->y+y,bounds->width,1,
 182       exception);
 183     q=GetVirtualPixels(image2,bounds->x,bounds->y+y,bounds->width,1,
 184       exception);
 185     if ((p == (const Quantum *) NULL) || (q == (Quantum *) NULL))
 186       break;
 187     for (x=0; x < (ssize_t) bounds->width; x++)
 188     {
 189       if ((GetPixelAlpha(image1,p) <= (Quantum) (QuantumRange/2)) &&
 190           (GetPixelAlpha(image1,q) > (Quantum) (QuantumRange/2)))
 191         break;
 192       p+=GetPixelChannels(image1);
 193       q++;
 194     }
 195     if (x < (ssize_t) bounds->width)
 196       break;
 197   }
 198   return(y < (ssize_t) bounds->height ? MagickTrue : MagickFalse);
 199 }
 200 \f
 201 /*
 202 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 203 %                                                                             %
 204 %                                                                             %
 205 %                                                                             %
 206 %     C o a l e s c e I m a g e s                                             %
 207 %                                                                             %
 208 %                                                                             %
 209 %                                                                             %
 210 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 211 %
 212 %  CoalesceImages() composites a set of images while respecting any page
 213 %  offsets and disposal methods.  GIF, MIFF, and MNG animation sequences
 214 %  typically start with an image background and each subsequent image
 215 %  varies in size and offset.  A new image sequence is returned with all
 216 %  images the same size as the first images virtual canvas and composited
 217 %  with the next image in the sequence.
 218 %
 219 %  The format of the CoalesceImages method is:
 220 %
 221 %      Image *CoalesceImages(Image *image,ExceptionInfo *exception)
 222 %
 223 %  A description of each parameter follows:
 224 %
 225 %    o image: the image sequence.
 226 %
 227 %    o exception: return any errors or warnings in this structure.
 228 %
 229 */
 230 MagickExport Image *CoalesceImages(const Image *image,ExceptionInfo *exception)
 231 {
 232   Image
 233     *coalesce_image,
 234     *dispose_image,
 235     *previous;
 236
 237   register Image
 238     *next;
 239
 240   RectangleInfo
 241     bounds;
 242
 243   /*
 244     Coalesce the image sequence.
 245   */
 246   assert(image != (Image *) NULL);
 247   assert(image->signature == MagickSignature);
 248   if (image->debug != MagickFalse)
 249     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
 250   assert(exception != (ExceptionInfo *) NULL);
 251   assert(exception->signature == MagickSignature);
 252
 253   /* initialise first image */
 254   next=GetFirstImageInList(image);
 255   bounds=next->page;
 256   if (bounds.width == 0)
 257     {
 258       bounds.width=next->columns;
 259       if (bounds.x > 0)
 260         bounds.width+=bounds.x;
 261     }
 262   if (bounds.height == 0)
 263     {
 264       bounds.height=next->rows;
 265       if (bounds.y > 0)
 266         bounds.height+=bounds.y;
 267     }
 268   bounds.x=0;
 269   bounds.y=0;
 270   coalesce_image=CloneImage(next,bounds.width,bounds.height,MagickTrue,
 271     exception);
 272   if (coalesce_image == (Image *) NULL)
 273     return((Image *) NULL);
 274   coalesce_image->page=bounds;
 275   coalesce_image->dispose=NoneDispose;
 276   coalesce_image->background_color.alpha=(Quantum) TransparentAlpha;
 277   (void) SetImageBackgroundColor(coalesce_image,exception);
 278   /*
 279     Coalesce rest of the images.
 280   */
 281   dispose_image=CloneImage(coalesce_image,0,0,MagickTrue,exception);
 282   (void) CompositeImage(coalesce_image,CopyCompositeOp,next,next->page.x,
 283     next->page.y,exception);
 284   next=GetNextImageInList(next);
 285   for ( ; next != (Image *) NULL; next=GetNextImageInList(next))
 286   {
 287     /*
 288       Determine the bounds that was overlaid in the previous image.
 289     */
 290     previous=GetPreviousImageInList(next);
 291     bounds=previous->page;
 292     bounds.width=previous->columns;
 293     bounds.height=previous->rows;
 294     if (bounds.x < 0)
 295       {
 296         bounds.width+=bounds.x;
 297         bounds.x=0;
 298       }
 299     if ((ssize_t) (bounds.x+bounds.width) > (ssize_t) coalesce_image->columns)
 300       bounds.width=coalesce_image->columns-bounds.x;
 301     if (bounds.y < 0)
 302       {
 303         bounds.height+=bounds.y;
 304         bounds.y=0;
 305       }
 306     if ((ssize_t) (bounds.y+bounds.height) > (ssize_t) coalesce_image->rows)
 307       bounds.height=coalesce_image->rows-bounds.y;
 308     /*
 309       Replace the dispose image with the new coalesced image.
 310     */
 311     if (GetPreviousImageInList(next)->dispose != PreviousDispose)
 312       {
 313         dispose_image=DestroyImage(dispose_image);
 314         dispose_image=CloneImage(coalesce_image,0,0,MagickTrue,exception);
 315         if (dispose_image == (Image *) NULL)
 316           {
 317             coalesce_image=DestroyImageList(coalesce_image);
 318             return((Image *) NULL);
 319           }
 320       }
 321     /*
 322       Clear the overlaid area of the coalesced bounds for background disposal
 323     */
 324     if (next->previous->dispose == BackgroundDispose)
 325       ClearBounds(dispose_image, &bounds);
 326     /*
 327       Next image is the dispose image, overlaid with next frame in sequence.
 328     */
 329     coalesce_image->next=CloneImage(dispose_image,0,0,MagickTrue,exception);
 330     coalesce_image->next->previous=coalesce_image;
 331     previous=coalesce_image;
 332     coalesce_image=GetNextImageInList(coalesce_image);
 333     coalesce_image->matte=MagickTrue;
 334     (void) CompositeImage(coalesce_image,next->matte != MagickFalse ?
 335       OverCompositeOp : CopyCompositeOp,next,next->page.x,next->page.y,
 336       exception);
 337     (void) CloneImageProfiles(coalesce_image,next);
 338     (void) CloneImageProperties(coalesce_image,next);
 339     (void) CloneImageArtifacts(coalesce_image,next);
 340     coalesce_image->page=previous->page;
 341     /*
 342       If a pixel goes opaque to transparent, use background dispose.
 343     */
 344     if (IsBoundsCleared(previous,coalesce_image,&bounds,exception))
 345       coalesce_image->dispose=BackgroundDispose;
 346     else
 347       coalesce_image->dispose=NoneDispose;
 348     previous->dispose=coalesce_image->dispose;
 349   }
 350   dispose_image=DestroyImage(dispose_image);
 351   return(GetFirstImageInList(coalesce_image));
 352 }
 353 \f
 354 /*
 355 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 356 %                                                                             %
 357 %                                                                             %
 358 %                                                                             %
 359 %     D i s p o s e I m a g e s                                               %
 360 %                                                                             %
 361 %                                                                             %
 362 %                                                                             %
 363 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 364 %
 365 %  DisposeImages() returns the coalesced frames of a GIF animation as it would
 366 %  appear after the GIF dispose method of that frame has been applied.  That
 367 %  is it returned the appearance of each frame before the next is overlaid.
 368 %
 369 %  The format of the DisposeImages method is:
 370 %
 371 %      Image *DisposeImages(Image *image,ExceptionInfo *exception)
 372 %
 373 %  A description of each parameter follows:
 374 %
 375 %    o image: the image sequence.
 376 %
 377 %    o exception: return any errors or warnings in this structure.
 378 %
 379 */
 380 MagickExport Image *DisposeImages(const Image *image,ExceptionInfo *exception)
 381 {
 382   Image
 383     *dispose_image,
 384     *dispose_images;
 385
 386   register Image
 387     *curr;
 388
 389   RectangleInfo
 390     bounds;
 391
 392   /*
 393     Run the image through the animation sequence
 394   */
 395   assert(image != (Image *) NULL);
 396   assert(image->signature == MagickSignature);
 397   if (image->debug != MagickFalse)
 398     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
 399   assert(exception != (ExceptionInfo *) NULL);
 400   assert(exception->signature == MagickSignature);
 401   curr=GetFirstImageInList(image);
 402   dispose_image=CloneImage(curr,curr->page.width,curr->page.height,MagickTrue,
 403     exception);
 404   if (dispose_image == (Image *) NULL)
 405     return((Image *) NULL);
 406   dispose_image->page=curr->page;
 407   dispose_image->page.x=0;
 408   dispose_image->page.y=0;
 409   dispose_image->dispose=NoneDispose;
 410   dispose_image->background_color.alpha=(Quantum) TransparentAlpha;
 411   (void) SetImageBackgroundColor(dispose_image,exception);
 412   dispose_images=NewImageList();
 413   for ( ; curr != (Image *) NULL; curr=GetNextImageInList(curr))
 414   {
 415     Image
 416       *current_image;
 417
 418     /*
 419       Overlay this frame's image over the previous disposal image.
 420     */
 421     current_image=CloneImage(dispose_image,0,0,MagickTrue,exception);
 422     if (current_image == (Image *) NULL)
 423       {
 424         dispose_images=DestroyImageList(dispose_images);
 425         dispose_image=DestroyImage(dispose_image);
 426         return((Image *) NULL);
 427       }
 428     (void) CompositeImage(current_image,curr->matte != MagickFalse ?
 429       OverCompositeOp : CopyCompositeOp,curr,curr->page.x,curr->page.y,
 430       exception);
 431
 432     /*
 433       Handle Background dispose: image is displayed for the delay period.
 434     */
 435     if (curr->dispose == BackgroundDispose)
 436       {
 437         bounds=curr->page;
 438         bounds.width=curr->columns;
 439         bounds.height=curr->rows;
 440         if (bounds.x < 0)
 441           {
 442             bounds.width+=bounds.x;
 443             bounds.x=0;
 444           }
 445         if ((ssize_t) (bounds.x+bounds.width) > (ssize_t) current_image->columns)
 446           bounds.width=current_image->columns-bounds.x;
 447         if (bounds.y < 0)
 448           {
 449             bounds.height+=bounds.y;
 450             bounds.y=0;
 451           }
 452         if ((ssize_t) (bounds.y+bounds.height) > (ssize_t) current_image->rows)
 453           bounds.height=current_image->rows-bounds.y;
 454         ClearBounds(current_image,&bounds);
 455       }
 456     /*
 457       Select the appropriate previous/disposed image.
 458     */
 459     if (curr->dispose == PreviousDispose)
 460       current_image=DestroyImage(current_image);
 461     else
 462       {
 463         dispose_image=DestroyImage(dispose_image);
 464         dispose_image=current_image;
 465         current_image=(Image *)NULL;
 466       }
 467     /*
 468       Save the dispose image just calculated for return.
 469     */
 470     {
 471       Image
 472         *dispose;
 473
 474       dispose=CloneImage(dispose_image,0,0,MagickTrue,exception);
 475       if (dispose == (Image *) NULL)
 476         {
 477           dispose_images=DestroyImageList(dispose_images);
 478           dispose_image=DestroyImage(dispose_image);
 479           return((Image *) NULL);
 480         }
 481       (void) CloneImageProfiles(dispose,curr);
 482       (void) CloneImageProperties(dispose,curr);
 483       (void) CloneImageArtifacts(dispose,curr);
 484       dispose->page.x=0;
 485       dispose->page.y=0;
 486       dispose->dispose=curr->dispose;
 487       AppendImageToList(&dispose_images,dispose);
 488     }
 489   }
 490   dispose_image=DestroyImage(dispose_image);
 491   return(GetFirstImageInList(dispose_images));
 492 }
 493 \f
 494 /*
 495 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 496 %                                                                             %
 497 %                                                                             %
 498 %                                                                             %
 499 +     C o m p a r e P i x e l s                                               %
 500 %                                                                             %
 501 %                                                                             %
 502 %                                                                             %
 503 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 504 %
 505 %  ComparePixels() Compare the two pixels and return true if the pixels
 506 %  differ according to the given LayerType comparision method.
 507 %
 508 %  This currently only used internally by CompareImagesBounds(). It is
 509 %  doubtful that this sub-routine will be useful outside this module.
 510 %
 511 %  The format of the ComparePixels method is:
 512 %
 513 %      MagickBooleanType *ComparePixels(const ImageLayerMethod method,
 514 %        const PixelInfo *p,const PixelInfo *q)
 515 %
 516 %  A description of each parameter follows:
 517 %
 518 %    o method: What differences to look for. Must be one of
 519 %              CompareAnyLayer, CompareClearLayer, CompareOverlayLayer.
 520 %
 521 %    o p, q: the pixels to test for appropriate differences.
 522 %
 523 */
 524
 525 static MagickBooleanType ComparePixels(const ImageLayerMethod method,
 526   const PixelInfo *p,const PixelInfo *q)
 527 {
 528   MagickRealType
 529     o1,
 530     o2;
 531
 532   /*
 533     Any change in pixel values
 534   */
 535   if (method == CompareAnyLayer)
 536     return((MagickBooleanType)(IsFuzzyEquivalencePixelInfo(p,q) == MagickFalse));
 537
 538   o1 = (p->matte != MagickFalse) ? p->alpha : OpaqueAlpha;
 539   o2 = (q->matte != MagickFalse) ? q->alpha : OpaqueAlpha;
 540
 541   /*
 542     Pixel goes from opaque to transprency
 543   */
 544   if (method == CompareClearLayer)
 545     return((MagickBooleanType) ( (o1 <= ((MagickRealType) QuantumRange/2.0)) &&
 546       (o2 > ((MagickRealType) QuantumRange/2.0)) ) );
 547
 548   /*
 549     overlay would change first pixel by second
 550   */
 551   if (method == CompareOverlayLayer)
 552     {
 553       if (o2 > ((MagickRealType) QuantumRange/2.0))
 554         return MagickFalse;
 555       return((MagickBooleanType) (IsFuzzyEquivalencePixelInfo(p,q) == MagickFalse));
 556     }
 557   return(MagickFalse);
 558 }
 559
 560 \f
 561 /*
 562 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 563 %                                                                             %
 564 %                                                                             %
 565 %                                                                             %
 566 +     C o m p a r e I m a g e B o u n d s                                     %
 567 %                                                                             %
 568 %                                                                             %
 569 %                                                                             %
 570 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 571 %
 572 %  CompareImagesBounds() Given two images return the smallest rectangular area
 573 %  by which the two images differ, accourding to the given 'Compare...'
 574 %  layer method.
 575 %
 576 %  This currently only used internally in this module, but may eventually
 577 %  be used by other modules.
 578 %
 579 %  The format of the CompareImagesBounds method is:
 580 %
 581 %      RectangleInfo *CompareImagesBounds(const ImageLayerMethod method,
 582 %        const Image *image1, const Image *image2, ExceptionInfo *exception)
 583 %
 584 %  A description of each parameter follows:
 585 %
 586 %    o method: What differences to look for. Must be one of CompareAnyLayer,
 587 %      CompareClearLayer, CompareOverlayLayer.
 588 %
 589 %    o image1, image2: the two images to compare.
 590 %
 591 %    o exception: return any errors or warnings in this structure.
 592 %
 593 */
 594
 595 static RectangleInfo CompareImagesBounds(const Image *image1,const Image *image2,
 596   const ImageLayerMethod method,ExceptionInfo *exception)
 597 {
 598   RectangleInfo
 599     bounds;
 600
 601   PixelInfo
 602     pixel1,
 603     pixel2;
 604
 605   register const Quantum
 606     *p,
 607     *q;
 608
 609   register ssize_t
 610     x;
 611
 612   ssize_t
 613     y;
 614
 615   /*
 616     Set bounding box of the differences between images.
 617   */
 618   GetPixelInfo(image1,&pixel1);
 619   GetPixelInfo(image2,&pixel2);
 620   for (x=0; x < (ssize_t) image1->columns; x++)
 621   {
 622     p=GetVirtualPixels(image1,x,0,1,image1->rows,exception);
 623     q=GetVirtualPixels(image2,x,0,1,image2->rows,exception);
 624     if ((p == (const Quantum *) NULL) ||
 625         (q == (Quantum *) NULL))
 626       break;
 627     for (y=0; y < (ssize_t) image1->rows; y++)
 628     {
 629       SetPixelInfo(image1,p,&pixel1);
 630       SetPixelInfo(image2,q,&pixel2);
 631       if (ComparePixels(method,&pixel1,&pixel2))
 632         break;
 633       p+=GetPixelChannels(image1);
 634       q++;
 635     }
 636     if (y < (ssize_t) image1->rows)
 637       break;
 638   }
 639   if (x >= (ssize_t) image1->columns)
 640     {
 641       /*
 642         Images are identical, return a null image.
 643       */
 644       bounds.x=-1;
 645       bounds.y=-1;
 646       bounds.width=1;
 647       bounds.height=1;
 648       return(bounds);
 649     }
 650   bounds.x=x;
 651   for (x=(ssize_t) image1->columns-1; x >= 0; x--)
 652   {
 653     p=GetVirtualPixels(image1,x,0,1,image1->rows,exception);
 654     q=GetVirtualPixels(image2,x,0,1,image2->rows,exception);
 655     if ((p == (const Quantum *) NULL) ||
 656         (q == (Quantum *) NULL))
 657       break;
 658     for (y=0; y < (ssize_t) image1->rows; y++)
 659     {
 660       SetPixelInfo(image1,p,&pixel1);
 661       SetPixelInfo(image2,q,&pixel2);
 662       if (ComparePixels(method,&pixel1,&pixel2))
 663         break;
 664       p+=GetPixelChannels(image1);
 665       q++;
 666     }
 667     if (y < (ssize_t) image1->rows)
 668       break;
 669   }
 670   bounds.width=(size_t) (x-bounds.x+1);
 671   for (y=0; y < (ssize_t) image1->rows; y++)
 672   {
 673     p=GetVirtualPixels(image1,0,y,image1->columns,1,exception);
 674     q=GetVirtualPixels(image2,0,y,image2->columns,1,exception);
 675     if ((p == (const Quantum *) NULL) ||
 676         (q == (Quantum *) NULL))
 677       break;
 678     for (x=0; x < (ssize_t) image1->columns; x++)
 679     {
 680       SetPixelInfo(image1,p,&pixel1);
 681       SetPixelInfo(image2,q,&pixel2);
 682       if (ComparePixels(method,&pixel1,&pixel2))
 683         break;
 684       p+=GetPixelChannels(image1);
 685       q++;
 686     }
 687     if (x < (ssize_t) image1->columns)
 688       break;
 689   }
 690   bounds.y=y;
 691   for (y=(ssize_t) image1->rows-1; y >= 0; y--)
 692   {
 693     p=GetVirtualPixels(image1,0,y,image1->columns,1,exception);
 694     q=GetVirtualPixels(image2,0,y,image2->columns,1,exception);
 695     if ((p == (const Quantum *) NULL) ||
 696         (q == (Quantum *) NULL))
 697       break;
 698     for (x=0; x < (ssize_t) image1->columns; x++)
 699     {
 700       SetPixelInfo(image1,p,&pixel1);
 701       SetPixelInfo(image2,q,&pixel2);
 702       if (ComparePixels(method,&pixel1,&pixel2))
 703         break;
 704       p+=GetPixelChannels(image1);
 705       q++;
 706     }
 707     if (x < (ssize_t) image1->columns)
 708       break;
 709   }
 710   bounds.height=(size_t) (y-bounds.y+1);
 711   return(bounds);
 712 }
 713 \f
 714 /*
 715 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 716 %                                                                             %
 717 %                                                                             %
 718 %                                                                             %
 719 %     C o m p a r e I m a g e L a y e r s                                     %
 720 %                                                                             %
 721 %                                                                             %
 722 %                                                                             %
 723 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 724 %
 725 %  CompareImagesLayers() compares each image with the next in a sequence and
 726 %  returns the minimum bounding region of all the pixel differences (of the
 727 %  ImageLayerMethod specified) it discovers.
 728 %
 729 %  Images do NOT have to be the same size, though it is best that all the
 730 %  images are 'coalesced' (images are all the same size, on a flattened
 731 %  canvas, so as to represent exactly how an specific frame should look).
 732 %
 733 %  No GIF dispose methods are applied, so GIF animations must be coalesced
 734 %  before applying this image operator to find differences to them.
 735 %
 736 %  The format of the CompareImagesLayers method is:
 737 %
 738 %      Image *CompareImagesLayers(const Image *images,
 739 %        const ImageLayerMethod method,ExceptionInfo *exception)
 740 %
 741 %  A description of each parameter follows:
 742 %
 743 %    o image: the image.
 744 %
 745 %    o method: the layers type to compare images with. Must be one of...
 746 %              CompareAnyLayer, CompareClearLayer, CompareOverlayLayer.
 747 %
 748 %    o exception: return any errors or warnings in this structure.
 749 %
 750 */
 751
 752 MagickExport Image *CompareImagesLayers(const Image *image,
 753   const ImageLayerMethod method, ExceptionInfo *exception)
 754 {
 755   Image
 756     *image_a,
 757     *image_b,
 758     *layers;
 759
 760   RectangleInfo
 761     *bounds;
 762
 763   register const Image
 764     *next;
 765
 766   register ssize_t
 767     i;
 768
 769   assert(image != (const Image *) NULL);
 770   assert(image->signature == MagickSignature);
 771   if (image->debug != MagickFalse)
 772     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
 773   assert(exception != (ExceptionInfo *) NULL);
 774   assert(exception->signature == MagickSignature);
 775   assert((method == CompareAnyLayer) ||
 776          (method == CompareClearLayer) ||
 777          (method == CompareOverlayLayer));
 778   /*
 779     Allocate bounds memory.
 780   */
 781   next=GetFirstImageInList(image);
 782   bounds=(RectangleInfo *) AcquireQuantumMemory((size_t)
 783     GetImageListLength(next),sizeof(*bounds));
 784   if (bounds == (RectangleInfo *) NULL)
 785     ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
 786   /*
 787     Set up first comparision images.
 788   */
 789   image_a=CloneImage(next,next->page.width,next->page.height,
 790     MagickTrue,exception);
 791   if (image_a == (Image *) NULL)
 792     {
 793       bounds=(RectangleInfo *) RelinquishMagickMemory(bounds);
 794       return((Image *) NULL);
 795     }
 796   image_a->background_color.alpha=(Quantum) TransparentAlpha;
 797   (void) SetImageBackgroundColor(image_a,exception);
 798   image_a->page=next->page;
 799   image_a->page.x=0;
 800   image_a->page.y=0;
 801   (void) CompositeImage(image_a,CopyCompositeOp,next,next->page.x,next->page.y,
 802     exception);
 803   /*
 804     Compute the bounding box of changes for the later images
 805   */
 806   i=0;
 807   next=GetNextImageInList(next);
 808   for ( ; next != (const Image *) NULL; next=GetNextImageInList(next))
 809   {
 810     image_b=CloneImage(image_a,0,0,MagickTrue,exception);
 811     if (image_b == (Image *) NULL)
 812       {
 813         image_a=DestroyImage(image_a);
 814         bounds=(RectangleInfo *) RelinquishMagickMemory(bounds);
 815         return((Image *) NULL);
 816       }
 817     (void) CompositeImage(image_a,CopyCompositeOp,next,next->page.x,
 818       next->page.y,exception);
 819     bounds[i]=CompareImagesBounds(image_b,image_a,method,exception);
 820
 821     image_b=DestroyImage(image_b);
 822     i++;
 823   }
 824   image_a=DestroyImage(image_a);
 825   /*
 826     Clone first image in sequence.
 827   */
 828   next=GetFirstImageInList(image);
 829   layers=CloneImage(next,0,0,MagickTrue,exception);
 830   if (layers == (Image *) NULL)
 831     {
 832       bounds=(RectangleInfo *) RelinquishMagickMemory(bounds);
 833       return((Image *) NULL);
 834     }
 835   /*
 836     Deconstruct the image sequence.
 837   */
 838   i=0;
 839   next=GetNextImageInList(next);
 840   for ( ; next != (const Image *) NULL; next=GetNextImageInList(next))
 841   {
 842     image_a=CloneImage(next,0,0,MagickTrue,exception);
 843     if (image_a == (Image *) NULL)
 844       break;
 845     image_b=CropImage(image_a,&bounds[i],exception);
 846     image_a=DestroyImage(image_a);
 847     if (image_b == (Image *) NULL)
 848       break;
 849     AppendImageToList(&layers,image_b);
 850     i++;
 851   }
 852   bounds=(RectangleInfo *) RelinquishMagickMemory(bounds);
 853   if (next != (Image *) NULL)
 854     {
 855       layers=DestroyImageList(layers);
 856       return((Image *) NULL);
 857     }
 858   return(GetFirstImageInList(layers));
 859 }
 860 \f
 861 /*
 862 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 863 %                                                                             %
 864 %                                                                             %
 865 %                                                                             %
 866 +     O p t i m i z e L a y e r F r a m e s                                   %
 867 %                                                                             %
 868 %                                                                             %
 869 %                                                                             %
 870 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 871 %
 872 %  OptimizeLayerFrames() takes a coalesced GIF animation, and compares each
 873 %  frame against the three different 'disposal' forms of the previous frame.
 874 %  From this it then attempts to select the smallest cropped image and
 875 %  disposal method needed to reproduce the resulting image.
 876 %
 877 %  Note that this not easy, and may require the expansion of the bounds
 878 %  of previous frame, simply clear pixels for the next animation frame to
 879 %  transparency according to the selected dispose method.
 880 %
 881 %  The format of the OptimizeLayerFrames method is:
 882 %
 883 %      Image *OptimizeLayerFrames(const Image *image,
 884 %        const ImageLayerMethod method, ExceptionInfo *exception)
 885 %
 886 %  A description of each parameter follows:
 887 %
 888 %    o image: the image.
 889 %
 890 %    o method: the layers technique to optimize with. Must be one of...
 891 %      OptimizeImageLayer, or  OptimizePlusLayer.  The Plus form allows
 892 %      the addition of extra 'zero delay' frames to clear pixels from
 893 %      the previous frame, and the removal of frames that done change,
 894 %      merging the delay times together.
 895 %
 896 %    o exception: return any errors or warnings in this structure.
 897 %
 898 */
 899 /*
 900   Define a 'fake' dispose method where the frame is duplicated, (for
 901   OptimizePlusLayer) with a extra zero time delay frame which does a
 902   BackgroundDisposal to clear the pixels that need to be cleared.
 903 */
 904 #define DupDispose  ((DisposeType)9)
 905 /*
 906   Another 'fake' dispose method used to removed frames that don't change.
 907 */
 908 #define DelDispose  ((DisposeType)8)
 909
 910 #define DEBUG_OPT_FRAME 0
 911
 912 static Image *OptimizeLayerFrames(const Image *image,
 913   const ImageLayerMethod method, ExceptionInfo *exception)
 914 {
 915   ExceptionInfo
 916     *sans_exception;
 917
 918   Image
 919     *prev_image,
 920     *dup_image,
 921     *bgnd_image,
 922     *optimized_image;
 923
 924   RectangleInfo
 925     try_bounds,
 926     bgnd_bounds,
 927     dup_bounds,
 928     *bounds;
 929
 930   MagickBooleanType
 931     add_frames,
 932     try_cleared,
 933     cleared;
 934
 935   DisposeType
 936     *disposals;
 937
 938   register const Image
 939     *curr;
 940
 941   register ssize_t
 942     i;
 943
 944   assert(image != (const Image *) NULL);
 945   assert(image->signature == MagickSignature);
 946   if (image->debug != MagickFalse)
 947     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
 948   assert(exception != (ExceptionInfo *) NULL);
 949   assert(exception->signature == MagickSignature);
 950   assert(method == OptimizeLayer ||
 951          method == OptimizeImageLayer ||
 952          method == OptimizePlusLayer);
 953
 954   /*
 955     Are we allowed to add/remove frames from animation
 956   */
 957   add_frames=method == OptimizePlusLayer ? MagickTrue : MagickFalse;
 958   /*
 959     Ensure  all the images are the same size
 960   */
 961   curr=GetFirstImageInList(image);
 962   for (; curr != (Image *) NULL; curr=GetNextImageInList(curr))
 963   {
 964     if ((curr->columns != image->columns) || (curr->rows != image->rows))
 965       ThrowImageException(OptionError,"ImagesAreNotTheSameSize");
 966     /*
 967       FUTURE: also check that image is also fully coalesced (full page)
 968       Though as long as they are the same size it should not matter.
 969     */
 970   }
 971   /*
 972     Allocate memory (times 2 if we allow the use of frame duplications)
 973   */
 974   curr=GetFirstImageInList(image);
 975   bounds=(RectangleInfo *) AcquireQuantumMemory((size_t)
 976     GetImageListLength(curr),(add_frames != MagickFalse ? 2UL : 1UL)*
 977     sizeof(*bounds));
 978   if (bounds == (RectangleInfo *) NULL)
 979     ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
 980   disposals=(DisposeType *) AcquireQuantumMemory((size_t)
 981     GetImageListLength(image),(add_frames != MagickFalse ? 2UL : 1UL)*
 982     sizeof(*disposals));
 983   if (disposals == (DisposeType *) NULL)
 984     {
 985       bounds=(RectangleInfo *) RelinquishMagickMemory(bounds);
 986       ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
 987     }
 988   /*
 989     Initialise Previous Image as fully transparent
 990   */
 991   prev_image=CloneImage(curr,curr->page.width,curr->page.height,
 992     MagickTrue,exception);
 993   if (prev_image == (Image *) NULL)
 994     {
 995       bounds=(RectangleInfo *) RelinquishMagickMemory(bounds);
 996       disposals=(DisposeType *) RelinquishMagickMemory(disposals);
 997       return((Image *) NULL);
 998     }
 999   prev_image->page=curr->page;  /* ERROR: <-- should not be need, but is! */
1000   prev_image->page.x=0;
1001   prev_image->page.y=0;
1002   prev_image->dispose=NoneDispose;
1003
1004   prev_image->background_color.alpha=(Quantum) TransparentAlpha;
1005   (void) SetImageBackgroundColor(prev_image,exception);
1006   /*
1007     Figure out the area of overlay of the first frame
1008     No pixel could be cleared as all pixels are already cleared.
1009   */
1010 #if DEBUG_OPT_FRAME
1011   i=0;
1012   (void) FormatLocaleFile(stderr, "frame %.20g :-\n", (double) i);
1013 #endif
1014   disposals[0]=NoneDispose;
1015   bounds[0]=CompareImagesBounds(prev_image,curr,CompareAnyLayer,exception);
1016 #if DEBUG_OPT_FRAME
1017   (void) FormatLocaleFile(stderr, "overlay: %.20gx%.20g%+.20g%+.20g\n\n",
1018     (double) bounds[i].width,(double) bounds[i].height,
1019     (double) bounds[i].x,(double) bounds[i].y );
1020 #endif
1021   /*
1022     Compute the bounding box of changes for each pair of images.
1023   */
1024   i=1;
1025   bgnd_image=(Image *)NULL;
1026   dup_image=(Image *)NULL;
1027   dup_bounds.width=0;
1028   dup_bounds.height=0;
1029   dup_bounds.x=0;
1030   dup_bounds.y=0;
1031   curr=GetNextImageInList(curr);
1032   for ( ; curr != (const Image *) NULL; curr=GetNextImageInList(curr))
1033   {
1034 #if DEBUG_OPT_FRAME
1035     (void) FormatLocaleFile(stderr, "frame %.20g :-\n", (double) i);
1036 #endif
1037     /*
1038       Assume none disposal is the best
1039     */
1040     bounds[i]=CompareImagesBounds(curr->previous,curr,CompareAnyLayer,exception);
1041     cleared=IsBoundsCleared(curr->previous,curr,&bounds[i],exception);
1042     disposals[i-1]=NoneDispose;
1043 #if DEBUG_OPT_FRAME
1044     (void) FormatLocaleFile(stderr, "overlay: %.20gx%.20g%+.20g%+.20g%s%s\n",
1045          (double) bounds[i].width,(double) bounds[i].height,
1046          (double) bounds[i].x,(double) bounds[i].y,
1047          bounds[i].x < 0?"  (unchanged)":"",
1048          cleared?"  (pixels cleared)":"");
1049 #endif
1050     if ( bounds[i].x < 0 ) {
1051       /*
1052         Image frame is exactly the same as the previous frame!
1053         If not adding frames leave it to be cropped down to a null image.
1054         Otherwise mark previous image for deleted, transfering its crop bounds
1055         to the current image.
1056       */
1057       if ( add_frames && i>=2 ) {
1058         disposals[i-1]=DelDispose;
1059         disposals[i]=NoneDispose;
1060         bounds[i]=bounds[i-1];
1061         i++;
1062         continue;
1063       }
1064     }
1065     else
1066       {
1067         /*
1068           Compare a none disposal against a previous disposal
1069         */
1070         try_bounds=CompareImagesBounds(prev_image,curr,CompareAnyLayer,exception);
1071         try_cleared=IsBoundsCleared(prev_image,curr,&try_bounds,exception);
1072 #if DEBUG_OPT_FRAME
1073     (void) FormatLocaleFile(stderr, "test_prev: %.20gx%.20g%+.20g%+.20g%s\n",
1074          (double) try_bounds.width,(double) try_bounds.height,
1075          (double) try_bounds.x,(double) try_bounds.y,
1076          try_cleared?"  (pixels were cleared)":"");
1077 #endif
1078         if ( (!try_cleared && cleared ) ||
1079                 try_bounds.width * try_bounds.height
1080                     <  bounds[i].width * bounds[i].height )
1081           {
1082             cleared=try_cleared;
1083             bounds[i]=try_bounds;
1084             disposals[i-1]=PreviousDispose;
1085 #if DEBUG_OPT_FRAME
1086             (void) FormatLocaleFile(stderr, "previous: accepted\n");
1087           } else {
1088             (void) FormatLocaleFile(stderr, "previous: rejected\n");
1089 #endif
1090           }
1091
1092         /*
1093           If we are allowed lets try a complex frame duplication.
1094           It is useless if the previous image already clears pixels correctly.
1095           This method will always clear all the pixels that need to be cleared.
1096         */
1097         dup_bounds.width=dup_bounds.height=0; /* no dup, no pixel added */
1098         if ( add_frames )
1099           {
1100             dup_image=CloneImage(curr->previous,curr->previous->page.width,
1101                 curr->previous->page.height,MagickTrue,exception);
1102             if (dup_image == (Image *) NULL)
1103               {
1104                 bounds=(RectangleInfo *) RelinquishMagickMemory(bounds);
1105                 disposals=(DisposeType *) RelinquishMagickMemory(disposals);
1106                 prev_image=DestroyImage(prev_image);
1107                 return((Image *) NULL);
1108               }
1109             dup_bounds=CompareImagesBounds(dup_image,curr,CompareClearLayer,exception);
1110             ClearBounds(dup_image,&dup_bounds);
1111             try_bounds=CompareImagesBounds(dup_image,curr,CompareAnyLayer,exception);
1112             if ( cleared ||
1113                    dup_bounds.width*dup_bounds.height
1114                       +try_bounds.width*try_bounds.height
1115                    < bounds[i].width * bounds[i].height )
1116               {
1117                 cleared=MagickFalse;
1118                 bounds[i]=try_bounds;
1119                 disposals[i-1]=DupDispose;
1120                 /* to be finalised later, if found to be optimial */
1121               }
1122             else
1123               dup_bounds.width=dup_bounds.height=0;
1124           }
1125         /*
1126           Now compare against a simple background disposal
1127         */
1128         bgnd_image=CloneImage(curr->previous,curr->previous->page.width,
1129           curr->previous->page.height,MagickTrue,exception);
1130         if (bgnd_image == (Image *) NULL)
1131           {
1132             bounds=(RectangleInfo *) RelinquishMagickMemory(bounds);
1133             disposals=(DisposeType *) RelinquishMagickMemory(disposals);
1134             prev_image=DestroyImage(prev_image);
1135             if ( dup_image != (Image *) NULL)
1136               dup_image=DestroyImage(dup_image);
1137             return((Image *) NULL);
1138           }
1139         bgnd_bounds=bounds[i-1]; /* interum bounds of the previous image */
1140         ClearBounds(bgnd_image,&bgnd_bounds);
1141         try_bounds=CompareImagesBounds(bgnd_image,curr,CompareAnyLayer,exception);
1142         try_cleared=IsBoundsCleared(bgnd_image,curr,&try_bounds,exception);
1143 #if DEBUG_OPT_FRAME
1144     (void) FormatLocaleFile(stderr, "background: %s\n",
1145          try_cleared?"(pixels cleared)":"");
1146 #endif
1147         if ( try_cleared )
1148           {
1149             /*
1150               Straight background disposal failed to clear pixels needed!
1151               Lets try expanding the disposal area of the previous frame, to
1152               include the pixels that are cleared.  This guaranteed
1153               to work, though may not be the most optimized solution.
1154             */
1155             try_bounds=CompareImagesBounds(curr->previous,curr,CompareClearLayer,exception);
1156 #if DEBUG_OPT_FRAME
1157             (void) FormatLocaleFile(stderr, "expand_clear: %.20gx%.20g%+.20g%+.20g%s\n",
1158                 (double) try_bounds.width,(double) try_bounds.height,
1159                 (double) try_bounds.x,(double) try_bounds.y,
1160                 try_bounds.x<0?"  (no expand nessary)":"");
1161 #endif
1162             if ( bgnd_bounds.x < 0 )
1163               bgnd_bounds = try_bounds;
1164             else
1165               {
1166 #if DEBUG_OPT_FRAME
1167                 (void) FormatLocaleFile(stderr, "expand_bgnd: %.20gx%.20g%+.20g%+.20g\n",
1168                     (double) bgnd_bounds.width,(double) bgnd_bounds.height,
1169                     (double) bgnd_bounds.x,(double) bgnd_bounds.y );
1170 #endif
1171                 if ( try_bounds.x < bgnd_bounds.x )
1172                   {
1173                      bgnd_bounds.width+= bgnd_bounds.x-try_bounds.x;
1174                      if ( bgnd_bounds.width < try_bounds.width )
1175                        bgnd_bounds.width = try_bounds.width;
1176                      bgnd_bounds.x = try_bounds.x;
1177                   }
1178                 else
1179                   {
1180                      try_bounds.width += try_bounds.x - bgnd_bounds.x;
1181                      if ( bgnd_bounds.width < try_bounds.width )
1182                        bgnd_bounds.width = try_bounds.width;
1183                   }
1184                 if ( try_bounds.y < bgnd_bounds.y )
1185                   {
1186                      bgnd_bounds.height += bgnd_bounds.y - try_bounds.y;
1187                      if ( bgnd_bounds.height < try_bounds.height )
1188                        bgnd_bounds.height = try_bounds.height;
1189                      bgnd_bounds.y = try_bounds.y;
1190                   }
1191                 else
1192                   {
1193                     try_bounds.height += try_bounds.y - bgnd_bounds.y;
1194                      if ( bgnd_bounds.height < try_bounds.height )
1195                        bgnd_bounds.height = try_bounds.height;
1196                   }
1197 #if DEBUG_OPT_FRAME
1198                 (void) FormatLocaleFile(stderr, "        to : %.20gx%.20g%+.20g%+.20g\n",
1199                     (double) bgnd_bounds.width,(double) bgnd_bounds.height,
1200                     (double) bgnd_bounds.x,(double) bgnd_bounds.y );
1201 #endif
1202               }
1203             ClearBounds(bgnd_image,&bgnd_bounds);
1204 #if DEBUG_OPT_FRAME
1205 /* Something strange is happening with a specific animation
1206  * CompareAnyLayers (normal method) and CompareClearLayers returns the whole
1207  * image, which is not posibly correct!  As verified by previous tests.
1208  * Something changed beyond the bgnd_bounds clearing.  But without being able
1209  * to see, or writet he image at this point it is hard to tell what is wrong!
1210  * Only CompareOverlay seemed to return something sensible.
1211  */
1212             try_bounds=CompareImagesBounds(bgnd_image,curr,CompareClearLayer,exception);
1213             (void) FormatLocaleFile(stderr, "expand_ctst: %.20gx%.20g%+.20g%+.20g\n",
1214                 (double) try_bounds.width,(double) try_bounds.height,
1215                 (double) try_bounds.x,(double) try_bounds.y );
1216             try_bounds=CompareImagesBounds(bgnd_image,curr,CompareAnyLayer,exception);
1217             try_cleared=IsBoundsCleared(bgnd_image,curr,&try_bounds,exception);
1218             (void) FormatLocaleFile(stderr, "expand_any : %.20gx%.20g%+.20g%+.20g%s\n",
1219                 (double) try_bounds.width,(double) try_bounds.height,
1220                 (double) try_bounds.x,(double) try_bounds.y,
1221                 try_cleared?"   (pixels cleared)":"");
1222 #endif
1223             try_bounds=CompareImagesBounds(bgnd_image,curr,CompareOverlayLayer,exception);
1224 #if DEBUG_OPT_FRAME
1225             try_cleared=IsBoundsCleared(bgnd_image,curr,&try_bounds,exception);
1226             (void) FormatLocaleFile(stderr, "expand_test: %.20gx%.20g%+.20g%+.20g%s\n",
1227                 (double) try_bounds.width,(double) try_bounds.height,
1228                 (double) try_bounds.x,(double) try_bounds.y,
1229                 try_cleared?"   (pixels cleared)":"");
1230 #endif
1231           }
1232         /*
1233           Test if this background dispose is smaller than any of the
1234           other methods we tryed before this (including duplicated frame)
1235         */
1236         if ( cleared ||
1237               bgnd_bounds.width*bgnd_bounds.height
1238                 +try_bounds.width*try_bounds.height
1239               < bounds[i-1].width*bounds[i-1].height
1240                   +dup_bounds.width*dup_bounds.height
1241                   +bounds[i].width*bounds[i].height )
1242           {
1243             cleared=MagickFalse;
1244             bounds[i-1]=bgnd_bounds;
1245             bounds[i]=try_bounds;
1246             if ( disposals[i-1] == DupDispose )
1247               dup_image=DestroyImage(dup_image);
1248             disposals[i-1]=BackgroundDispose;
1249 #if DEBUG_OPT_FRAME
1250     (void) FormatLocaleFile(stderr, "expand_bgnd: accepted\n");
1251           } else {
1252     (void) FormatLocaleFile(stderr, "expand_bgnd: reject\n");
1253 #endif
1254           }
1255       }
1256     /*
1257        Finalise choice of dispose, set new prev_image,
1258        and junk any extra images as appropriate,
1259     */
1260     if ( disposals[i-1] == DupDispose )
1261       {
1262          if (bgnd_image != (Image *) NULL)
1263            bgnd_image=DestroyImage(bgnd_image);
1264          prev_image=DestroyImage(prev_image);
1265          prev_image=dup_image, dup_image=(Image *) NULL;
1266          bounds[i+1]=bounds[i];
1267          bounds[i]=dup_bounds;
1268          disposals[i-1]=DupDispose;
1269          disposals[i]=BackgroundDispose;
1270          i++;
1271       }
1272     else
1273       {
1274         if ( dup_image != (Image *) NULL)
1275           dup_image=DestroyImage(dup_image);
1276         if ( disposals[i-1] != PreviousDispose )
1277           prev_image=DestroyImage(prev_image);
1278         if ( disposals[i-1] == BackgroundDispose )
1279           prev_image=bgnd_image,  bgnd_image=(Image *)NULL;
1280         if (bgnd_image != (Image *) NULL)
1281           bgnd_image=DestroyImage(bgnd_image);
1282         if ( disposals[i-1] == NoneDispose )
1283           {
1284             prev_image=CloneImage(curr->previous,curr->previous->page.width,
1285               curr->previous->page.height,MagickTrue,exception);
1286             if (prev_image == (Image *) NULL)
1287               {
1288                 bounds=(RectangleInfo *) RelinquishMagickMemory(bounds);
1289                 disposals=(DisposeType *) RelinquishMagickMemory(disposals);
1290                 return((Image *) NULL);
1291               }
1292           }
1293
1294       }
1295     assert(prev_image != (Image *) NULL);
1296     disposals[i]=disposals[i-1];
1297 #if DEBUG_OPT_FRAME
1298     (void) FormatLocaleFile(stderr, "final   %.20g : %s  %.20gx%.20g%+.20g%+.20g\n",
1299          (double) i-1,
1300          CommandOptionToMnemonic(MagickDisposeOptions, disposals[i-1]),
1301          (double) bounds[i-1].width, (double) bounds[i-1].height,
1302          (double) bounds[i-1].x, (double) bounds[i-1].y );
1303 #endif
1304 #if DEBUG_OPT_FRAME
1305     (void) FormatLocaleFile(stderr, "interum %.20g : %s  %.20gx%.20g%+.20g%+.20g\n",
1306          (double) i,
1307          CommandOptionToMnemonic(MagickDisposeOptions, disposals[i]),
1308          (double) bounds[i].width, (double) bounds[i].height,
1309          (double) bounds[i].x, (double) bounds[i].y );
1310     (void) FormatLocaleFile(stderr, "\n");
1311 #endif
1312     i++;
1313   }
1314   prev_image=DestroyImage(prev_image);
1315   /*
1316     Optimize all images in sequence.
1317   */
1318   sans_exception=AcquireExceptionInfo();
1319   i=0;
1320   curr=GetFirstImageInList(image);
1321   optimized_image=NewImageList();
1322   while ( curr != (const Image *) NULL )
1323   {
1324     prev_image=CloneImage(curr,0,0,MagickTrue,exception);
1325     if (prev_image == (Image *) NULL)
1326       break;
1327     if ( disposals[i] == DelDispose ) {
1328       size_t time = 0;
1329       while ( disposals[i] == DelDispose ) {
1330         time += curr->delay*1000/curr->ticks_per_second;
1331         curr=GetNextImageInList(curr);
1332         i++;
1333       }
1334       time += curr->delay*1000/curr->ticks_per_second;
1335       prev_image->ticks_per_second = 100L;
1336       prev_image->delay = time*prev_image->ticks_per_second/1000;
1337     }
1338     bgnd_image=CropImage(prev_image,&bounds[i],sans_exception);
1339     prev_image=DestroyImage(prev_image);
1340     if (bgnd_image == (Image *) NULL)
1341       break;
1342     bgnd_image->dispose=disposals[i];
1343     if ( disposals[i] == DupDispose ) {
1344       bgnd_image->delay=0;
1345       bgnd_image->dispose=NoneDispose;
1346     }
1347     else
1348       curr=GetNextImageInList(curr);
1349     AppendImageToList(&optimized_image,bgnd_image);
1350     i++;
1351   }
1352   sans_exception=DestroyExceptionInfo(sans_exception);
1353   bounds=(RectangleInfo *) RelinquishMagickMemory(bounds);
1354   disposals=(DisposeType *) RelinquishMagickMemory(disposals);
1355   if (curr != (Image *) NULL)
1356     {
1357       optimized_image=DestroyImageList(optimized_image);
1358       return((Image *) NULL);
1359     }
1360   return(GetFirstImageInList(optimized_image));
1361 }
1362 \f
1363 /*
1364 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1365 %                                                                             %
1366 %                                                                             %
1367 %                                                                             %
1368 %     O p t i m i z e I m a g e L a y e r s                                   %
1369 %                                                                             %
1370 %                                                                             %
1371 %                                                                             %
1372 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1373 %
1374 %  OptimizeImageLayers() compares each image the GIF disposed forms of the
1375 %  previous image in the sequence.  From this it attempts to select the
1376 %  smallest cropped image to replace each frame, while preserving the results
1377 %  of the GIF animation.
1378 %
1379 %  The format of the OptimizeImageLayers method is:
1380 %
1381 %      Image *OptimizeImageLayers(const Image *image,
1382 %               ExceptionInfo *exception)
1383 %
1384 %  A description of each parameter follows:
1385 %
1386 %    o image: the image.
1387 %
1388 %    o exception: return any errors or warnings in this structure.
1389 %
1390 */
1391 MagickExport Image *OptimizeImageLayers(const Image *image,
1392   ExceptionInfo *exception)
1393 {
1394   return(OptimizeLayerFrames(image,OptimizeImageLayer,exception));
1395 }
1396 \f
1397 /*
1398 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1399 %                                                                             %
1400 %                                                                             %
1401 %                                                                             %
1402 %     O p t i m i z e P l u s I m a g e L a y e r s                           %
1403 %                                                                             %
1404 %                                                                             %
1405 %                                                                             %
1406 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1407 %
1408 %  OptimizeImagePlusLayers() is exactly as OptimizeImageLayers(), but may
1409 %  also add or even remove extra frames in the animation, if it improves
1410 %  the total number of pixels in the resulting GIF animation.
1411 %
1412 %  The format of the OptimizePlusImageLayers method is:
1413 %
1414 %      Image *OptimizePlusImageLayers(const Image *image,
1415 %               ExceptionInfo *exception)
1416 %
1417 %  A description of each parameter follows:
1418 %
1419 %    o image: the image.
1420 %
1421 %    o exception: return any errors or warnings in this structure.
1422 %
1423 */
1424 MagickExport Image *OptimizePlusImageLayers(const Image *image,
1425   ExceptionInfo *exception)
1426 {
1427   return OptimizeLayerFrames(image, OptimizePlusLayer, exception);
1428 }
1429 \f
1430 /*
1431 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1432 %                                                                             %
1433 %                                                                             %
1434 %                                                                             %
1435 %     O p t i m i z e I m a g e T r a n s p a r e n c y                       %
1436 %                                                                             %
1437 %                                                                             %
1438 %                                                                             %
1439 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1440 %
1441 %  OptimizeImageTransparency() takes a frame optimized GIF animation, and
1442 %  compares the overlayed pixels against the disposal image resulting from all
1443 %  the previous frames in the animation.  Any pixel that does not change the
1444 %  disposal image (and thus does not effect the outcome of an overlay) is made
1445 %  transparent.
1446 %
1447 %  WARNING: This modifies the current images directly, rather than generate
1448 %  a new image sequence.
1449 %
1450 %  The format of the OptimizeImageTransperency method is:
1451 %
1452 %      void OptimizeImageTransperency(Image *image,ExceptionInfo *exception)
1453 %
1454 %  A description of each parameter follows:
1455 %
1456 %    o image: the image sequence
1457 %
1458 %    o exception: return any errors or warnings in this structure.
1459 %
1460 */
1461 MagickExport void OptimizeImageTransparency(const Image *image,
1462      ExceptionInfo *exception)
1463 {
1464   Image
1465     *dispose_image;
1466
1467   register Image
1468     *next;
1469
1470   /*
1471     Run the image through the animation sequence
1472   */
1473   assert(image != (Image *) NULL);
1474   assert(image->signature == MagickSignature);
1475   if (image->debug != MagickFalse)
1476     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
1477   assert(exception != (ExceptionInfo *) NULL);
1478   assert(exception->signature == MagickSignature);
1479   next=GetFirstImageInList(image);
1480   dispose_image=CloneImage(next,next->page.width,next->page.height,
1481     MagickTrue,exception);
1482   if (dispose_image == (Image *) NULL)
1483     return;
1484   dispose_image->page=next->page;
1485   dispose_image->page.x=0;
1486   dispose_image->page.y=0;
1487   dispose_image->dispose=NoneDispose;
1488   dispose_image->background_color.alpha=(Quantum) TransparentAlpha;
1489   (void) SetImageBackgroundColor(dispose_image,exception);
1490
1491   while ( next != (Image *) NULL )
1492   {
1493     Image
1494       *current_image;
1495
1496     /*
1497       Overlay this frame's image over the previous disposal image
1498     */
1499     current_image=CloneImage(dispose_image,0,0,MagickTrue,exception);
1500     if (current_image == (Image *) NULL)
1501       {
1502         dispose_image=DestroyImage(dispose_image);
1503         return;
1504       }
1505     (void) CompositeImage(current_image,next->matte != MagickFalse ?
1506       OverCompositeOp : CopyCompositeOp, next,next->page.x,next->page.y,
1507       exception);
1508     /*
1509       At this point the image would be displayed, for the delay period
1510     **
1511       Work out the disposal of the previous image
1512     */
1513     if (next->dispose == BackgroundDispose)
1514       {
1515         RectangleInfo
1516           bounds=next->page;
1517
1518         bounds.width=next->columns;
1519         bounds.height=next->rows;
1520         if (bounds.x < 0)
1521           {
1522             bounds.width+=bounds.x;
1523             bounds.x=0;
1524           }
1525         if ((ssize_t) (bounds.x+bounds.width) > (ssize_t) current_image->columns)
1526           bounds.width=current_image->columns-bounds.x;
1527         if (bounds.y < 0)
1528           {
1529             bounds.height+=bounds.y;
1530             bounds.y=0;
1531           }
1532         if ((ssize_t) (bounds.y+bounds.height) > (ssize_t) current_image->rows)
1533           bounds.height=current_image->rows-bounds.y;
1534         ClearBounds(current_image, &bounds);
1535       }
1536     if (next->dispose != PreviousDispose)
1537       {
1538         dispose_image=DestroyImage(dispose_image);
1539         dispose_image=current_image;
1540       }
1541     else
1542       current_image=DestroyImage(current_image);
1543
1544     /*
1545       Optimize Transparency of the next frame (if present)
1546     */
1547     next=GetNextImageInList(next);
1548     if ( next != (Image *) NULL ) {
1549       (void) CompositeImage(next, ChangeMaskCompositeOp,
1550         dispose_image, -(next->page.x), -(next->page.y), exception );
1551     }
1552   }
1553   dispose_image=DestroyImage(dispose_image);
1554   return;
1555 }
1556 \f
1557 /*
1558 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1559 %                                                                             %
1560 %                                                                             %
1561 %                                                                             %
1562 %     R e m o v e D u p l i c a t e L a y e r s                               %
1563 %                                                                             %
1564 %                                                                             %
1565 %                                                                             %
1566 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1567 %
1568 %  RemoveDuplicateLayers() removes any image that is exactly the same as the
1569 %  next image in the given image list.  Image size and virtual canvas offset
1570 %  must also match, though not the virtual canvas size itself.
1571 %
1572 %  No check is made with regards to image disposal setting, though it is the
1573 %  dispose setting of later image that is kept.  Also any time delays are also
1574 %  added together. As such coalesced image animations should still produce the
1575 %  same result, though with duplicte frames merged into a single frame.
1576 %
1577 %  The format of the RemoveDuplicateLayers method is:
1578 %
1579 %      void RemoveDuplicateLayers(Image **image, ExceptionInfo *exception)
1580 %
1581 %  A description of each parameter follows:
1582 %
1583 %    o images: the image list
1584 %
1585 %    o exception: return any errors or warnings in this structure.
1586 %
1587 */
1588 MagickExport void RemoveDuplicateLayers(Image **images,
1589      ExceptionInfo *exception)
1590 {
1591   register Image
1592     *curr,
1593     *next;
1594
1595   RectangleInfo
1596     bounds;
1597
1598   assert((*images) != (const Image *) NULL);
1599   assert((*images)->signature == MagickSignature);
1600   if ((*images)->debug != MagickFalse)
1601     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",(*images)->filename);
1602   assert(exception != (ExceptionInfo *) NULL);
1603   assert(exception->signature == MagickSignature);
1604
1605   curr=GetFirstImageInList(*images);
1606   for (; (next=GetNextImageInList(curr)) != (Image *) NULL; curr=next)
1607   {
1608     if ( curr->columns != next->columns || curr->rows != next->rows
1609          || curr->page.x != next->page.x || curr->page.y != next->page.y )
1610       continue;
1611     bounds=CompareImagesBounds(curr,next,CompareAnyLayer,exception);
1612     if ( bounds.x < 0 ) {
1613       /*
1614         the two images are the same, merge time delays and delete one.
1615       */
1616       size_t time;
1617       time = curr->delay*1000/curr->ticks_per_second;
1618       time += next->delay*1000/next->ticks_per_second;
1619       next->ticks_per_second = 100L;
1620       next->delay = time*curr->ticks_per_second/1000;
1621       next->iterations = curr->iterations;
1622       *images = curr;
1623       (void) DeleteImageFromList(images);
1624     }
1625   }
1626   *images = GetFirstImageInList(*images);
1627 }
1628 \f
1629 /*
1630 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1631 %                                                                             %
1632 %                                                                             %
1633 %                                                                             %
1634 %     R e m o v e Z e r o D e l a y L a y e r s                               %
1635 %                                                                             %
1636 %                                                                             %
1637 %                                                                             %
1638 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1639 %
1640 %  RemoveZeroDelayLayers() removes any image that as a zero delay time. Such
1641 %  images generally represent intermediate or partial updates in GIF
1642 %  animations used for file optimization.  They are not ment to be displayed
1643 %  to users of the animation.  Viewable images in an animation should have a
1644 %  time delay of 3 or more centi-seconds (hundredths of a second).
1645 %
1646 %  However if all the frames have a zero time delay, then either the animation
1647 %  is as yet incomplete, or it is not a GIF animation.  This a non-sensible
1648 %  situation, so no image will be removed and a 'Zero Time Animation' warning
1649 %  (exception) given.
1650 %
1651 %  No warning will be given if no image was removed because all images had an
1652 %  appropriate non-zero time delay set.
1653 %
1654 %  Due to the special requirements of GIF disposal handling, GIF animations
1655 %  should be coalesced first, before calling this function, though that is not
1656 %  a requirement.
1657 %
1658 %  The format of the RemoveZeroDelayLayers method is:
1659 %
1660 %      void RemoveZeroDelayLayers(Image **image, ExceptionInfo *exception)
1661 %
1662 %  A description of each parameter follows:
1663 %
1664 %    o images: the image list
1665 %
1666 %    o exception: return any errors or warnings in this structure.
1667 %
1668 */
1669 MagickExport void RemoveZeroDelayLayers(Image **images,
1670      ExceptionInfo *exception)
1671 {
1672   Image
1673     *i;
1674
1675   assert((*images) != (const Image *) NULL);
1676   assert((*images)->signature == MagickSignature);
1677   if ((*images)->debug != MagickFalse)
1678     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",(*images)->filename);
1679   assert(exception != (ExceptionInfo *) NULL);
1680   assert(exception->signature == MagickSignature);
1681
1682   i=GetFirstImageInList(*images);
1683   for ( ; i != (Image *) NULL; i=GetNextImageInList(i))
1684     if ( i->delay != 0L ) break;
1685   if ( i == (Image *) NULL ) {
1686     (void) ThrowMagickException(exception,GetMagickModule(),OptionWarning,
1687        "ZeroTimeAnimation","`%s'",GetFirstImageInList(*images)->filename);
1688     return;
1689   }
1690   i=GetFirstImageInList(*images);
1691   while ( i != (Image *) NULL )
1692   {
1693     if ( i->delay == 0L ) {
1694       (void) DeleteImageFromList(&i);
1695       *images=i;
1696     }
1697     else
1698       i=GetNextImageInList(i);
1699   }
1700   *images=GetFirstImageInList(*images);
1701 }
1702 \f
1703 /*
1704 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1705 %                                                                             %
1706 %                                                                             %
1707 %                                                                             %
1708 %     C o m p o s i t e L a y e r s                                           %
1709 %                                                                             %
1710 %                                                                             %
1711 %                                                                             %
1712 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1713 %
1714 %  CompositeLayers() compose first image sequence (source) over the second
1715 %  image sequence (destination), using the given compose method and offsets.
1716 %
1717 %  The pointers to the image list does not have to be the start of that image
1718 %  list, but may start somewhere in the middle.  Each layer from the two image
1719 %  lists are composted together until the end of one of the image lists is
1720 %  reached.  The offset of each composition is also adjusted to match the
1721 %  virtual canvas offsets of each layer. As such the given offset is relative
1722 %  to the virtual canvas, and not the actual image.
1723 %
1724 %  No GIF disposal handling is performed, so GIF animations should be
1725 %  coalesced before use.  However this not a requirement, and individual
1726 %  layer images may have any size or offset, for special compositions.
1727 %
1728 %  Special case:- If one of the image sequences is just a single image that
1729 %  image is repeatally composed with all the images in the other image list.
1730 %  Either the source or destination lists may be the single image, for this
1731 %  situation.
1732 %
1733 %  The destination list will be expanded as needed to match number of source
1734 %  image overlaid (from current position to end of list).
1735 %
1736 %  The format of the CompositeLayers method is:
1737 %
1738 %      void CompositeLayers(Image *destination,
1739 %          const CompositeOperator compose, Image *source,
1740 %          const ssize_t x_offset, const ssize_t y_offset,
1741 %          ExceptionInfo *exception);
1742 %
1743 %  A description of each parameter follows:
1744 %
1745 %    o destination: the destination images and results
1746 %
1747 %    o source: source image(s) for the layer composition
1748 %
1749 %    o compose, x_offset, y_offset:  arguments passed on to CompositeImages()
1750 %
1751 %    o exception: return any errors or warnings in this structure.
1752 %
1753 */
1754
1755 static inline void CompositeCanvas(Image *destination,
1756   const CompositeOperator compose,Image *source,ssize_t x_offset,
1757   ssize_t y_offset,ExceptionInfo *exception)
1758 {
1759   x_offset+=source->page.x-destination->page.x;
1760   y_offset+=source->page.y-destination->page.y;
1761   (void) CompositeImage(destination,compose,source,x_offset,y_offset,
1762     exception);
1763 }
1764
1765 MagickExport void CompositeLayers(Image *destination,
1766   const CompositeOperator compose, Image *source,const ssize_t x_offset,
1767   const ssize_t y_offset,ExceptionInfo *exception)
1768 {
1769   assert(destination != (Image *) NULL);
1770   assert(destination->signature == MagickSignature);
1771   assert(source != (Image *) NULL);
1772   assert(source->signature == MagickSignature);
1773   assert(exception != (ExceptionInfo *) NULL);
1774   assert(exception->signature == MagickSignature);
1775   if (source->debug != MagickFalse || destination->debug != MagickFalse)
1776     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s - %s",
1777       source->filename, destination->filename);
1778
1779   /*
1780     Overlay single source image over destation image/list
1781   */
1782   if ( source->previous == (Image *) NULL && source->next == (Image *) NULL )
1783     while ( destination != (Image *) NULL )
1784     {
1785       CompositeCanvas(destination, compose, source, x_offset, y_offset,
1786         exception);
1787       destination=GetNextImageInList(destination);
1788     }
1789
1790   /*
1791     Overlay source image list over single destination
1792     Generating multiple clones of destination image to match source list.
1793     Original Destination image becomes first image of generated list.
1794     As such the image list pointer does not require any change in caller.
1795     Some animation attributes however also needs coping in this case.
1796   */
1797   else if ( destination->previous == (Image *) NULL &&
1798             destination->next == (Image *) NULL )
1799   {
1800     Image *dest = CloneImage(destination,0,0,MagickTrue,exception);
1801
1802     CompositeCanvas(destination, compose, source, x_offset, y_offset,
1803       exception);
1804     /* copy source image attributes ? */
1805     if ( source->next != (Image *) NULL )
1806       {
1807         destination->delay = source->delay;
1808         destination->iterations = source->iterations;
1809       }
1810     source=GetNextImageInList(source);
1811
1812     while ( source != (Image *) NULL )
1813     {
1814       AppendImageToList(&destination,
1815            CloneImage(dest,0,0,MagickTrue,exception));
1816       destination=GetLastImageInList(destination);
1817
1818       CompositeCanvas(destination, compose, source, x_offset, y_offset,
1819         exception);
1820       destination->delay = source->delay;
1821       destination->iterations = source->iterations;
1822       source=GetNextImageInList(source);
1823     }
1824     dest=DestroyImage(dest);
1825   }
1826
1827   /*
1828     Overlay a source image list over a destination image list
1829     until either list runs out of images. (Does not repeat)
1830   */
1831   else
1832     while ( source != (Image *) NULL && destination != (Image *) NULL )
1833     {
1834       CompositeCanvas(destination, compose, source, x_offset, y_offset,
1835         exception);
1836       source=GetNextImageInList(source);
1837       destination=GetNextImageInList(destination);
1838     }
1839 }
1840 \f
1841 /*
1842 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1843 %                                                                             %
1844 %                                                                             %
1845 %                                                                             %
1846 %     M e r g e I m a g e L a y e r s                                         %
1847 %                                                                             %
1848 %                                                                             %
1849 %                                                                             %
1850 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1851 %
1852 %  MergeImageLayers() composes all the image layers from the current given
1853 %  image onward to produce a single image of the merged layers.
1854 %
1855 %  The inital canvas's size depends on the given ImageLayerMethod, and is
1856 %  initialized using the first images background color.  The images
1857 %  are then compositied onto that image in sequence using the given
1858 %  composition that has been assigned to each individual image.
1859 %
1860 %  The format of the MergeImageLayers is:
1861 %
1862 %      Image *MergeImageLayers(const Image *image,
1863 %        const ImageLayerMethod method, ExceptionInfo *exception)
1864 %
1865 %  A description of each parameter follows:
1866 %
1867 %    o image: the image list to be composited together
1868 %
1869 %    o method: the method of selecting the size of the initial canvas.
1870 %
1871 %        MergeLayer: Merge all layers onto a canvas just large enough
1872 %           to hold all the actual images. The virtual canvas of the
1873 %           first image is preserved but otherwise ignored.
1874 %
1875 %        FlattenLayer: Use the virtual canvas size of first image.
1876 %           Images which fall outside this canvas is clipped.
1877 %           This can be used to 'fill out' a given virtual canvas.
1878 %
1879 %        MosaicLayer: Start with the virtual canvas of the first image,
1880 %           enlarging left and right edges to contain all images.
1881 %           Images with negative offsets will be clipped.
1882 %
1883 %        TrimBoundsLayer: Determine the overall bounds of all the image
1884 %           layers just as in "MergeLayer", then adjust the the canvas
1885 %           and offsets to be relative to those bounds, without overlaying
1886 %           the images.
1887 %
1888 %           WARNING: a new image is not returned, the original image
1889 %           sequence page data is modified instead.
1890 %
1891 %    o exception: return any errors or warnings in this structure.
1892 %
1893 */
1894 MagickExport Image *MergeImageLayers(Image *image,const ImageLayerMethod method,
1895   ExceptionInfo *exception)
1896 {
1897 #define MergeLayersTag  "Merge/Layers"
1898
1899   Image
1900     *canvas;
1901
1902   MagickBooleanType
1903     proceed;
1904
1905   RectangleInfo
1906     page;
1907
1908   register const Image
1909     *next;
1910
1911   size_t
1912     number_images,
1913     height,
1914     width;
1915
1916   ssize_t
1917     scene;
1918
1919   assert(image != (Image *) NULL);
1920   assert(image->signature == MagickSignature);
1921   if (image->debug != MagickFalse)
1922     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
1923   assert(exception != (ExceptionInfo *) NULL);
1924   assert(exception->signature == MagickSignature);
1925   /*
1926     Determine canvas image size, and its virtual canvas size and offset
1927   */
1928   page=image->page;
1929   width=image->columns;
1930   height=image->rows;
1931   switch (method)
1932   {
1933     case TrimBoundsLayer:
1934     case MergeLayer:
1935     default:
1936     {
1937       next = GetNextImageInList(image);
1938       for ( ; next != (Image *) NULL;  next=GetNextImageInList(next)) {
1939         if ( page.x > next->page.x ) {
1940              width += page.x-next->page.x;
1941              page.x = next->page.x;
1942         }
1943         if ( page.y > next->page.y ) {
1944              height += page.y-next->page.y;
1945              page.y = next->page.y;
1946         }
1947         if ( (ssize_t) width < (next->page.x + (ssize_t)next->columns - page.x) )
1948            width = (size_t) next->page.x + (ssize_t)next->columns - page.x;
1949         if ( (ssize_t) height < (next->page.y + (ssize_t)next->rows - page.y) )
1950            height = (size_t) next->page.y + (ssize_t)next->rows - page.y;
1951       }
1952       break;
1953     }
1954     case FlattenLayer:
1955     {
1956       if ( page.width > 0 )
1957         width=page.width;
1958       if ( page.height > 0 )
1959         height=page.height;
1960       page.x=0;
1961       page.y=0;
1962       break;
1963     }
1964     case MosaicLayer:
1965     {
1966       if ( page.width > 0 )
1967         width=page.width;
1968       if ( page.height > 0 )
1969         height=page.height;
1970       for (next=image; next != (Image *) NULL; next=GetNextImageInList(next)) {
1971         if (method == MosaicLayer) {
1972           page.x=next->page.x;
1973           page.y=next->page.y;
1974           if ( (ssize_t) width < (next->page.x + (ssize_t)next->columns) )
1975              width = (size_t) next->page.x + next->columns;
1976           if ( (ssize_t) height < (next->page.y + (ssize_t)next->rows) )
1977              height = (size_t) next->page.y + next->rows;
1978         }
1979       }
1980       page.width=width;
1981       page.height=height;
1982       page.x=0;
1983       page.y=0;
1984     }
1985     break;
1986   }
1987   /* set virtual canvas size if not defined */
1988   if ( page.width == 0 )
1989     page.width = (page.x < 0) ? width : width+page.x;
1990   if ( page.height == 0 )
1991     page.height = (page.y < 0) ? height : height+page.y;
1992
1993   /*
1994     Handle "TrimBoundsLayer" method separately to normal 'layer merge'
1995   */
1996   if ( method == TrimBoundsLayer ) {
1997     number_images=GetImageListLength(image);
1998     for (scene=0; scene < (ssize_t) number_images; scene++)
1999     {
2000       image->page.x -= page.x;
2001       image->page.y -= page.y;
2002       image->page.width = width;
2003       image->page.height = height;
2004       proceed=SetImageProgress(image,MergeLayersTag,(MagickOffsetType) scene,
2005         number_images);
2006       if (proceed == MagickFalse)
2007         break;
2008       image=GetNextImageInList(image);
2009     }
2010     return((Image *) NULL);
2011   }
2012
2013   /*
2014     Create canvas size of width and height, and background color.
2015   */
2016   canvas=CloneImage(image,width,height,MagickTrue,exception);
2017   if (canvas == (Image *) NULL)
2018     return((Image *) NULL);
2019   (void) SetImageBackgroundColor(canvas,exception);
2020   canvas->page=page;
2021   canvas->dispose=UndefinedDispose;
2022
2023   /*
2024     Compose images onto canvas, with progress monitor
2025   */
2026   number_images=GetImageListLength(image);
2027   for (scene=0; scene < (ssize_t) number_images; scene++)
2028   {
2029     (void) CompositeImage(canvas,image->compose,image,image->page.x-
2030       canvas->page.x,image->page.y-canvas->page.y,exception);
2031     proceed=SetImageProgress(image,MergeLayersTag,(MagickOffsetType) scene,
2032       number_images);
2033     if (proceed == MagickFalse)
2034       break;
2035     image=GetNextImageInList(image);
2036   }
2037   return(canvas);
2038 }
2039