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