[sdf] Added overlap support (currently only for TrueType).

* src/sdf/ftsdfrend.h (SDF_Renderer_Module): Removed the
  expermental `optimization' property.
  Added another property `overlaps', which can be used to
  turn on the overlap support.

* src/sdf/ftsdf.h (SDF_Raster_Params): Ditto as above.

* src/sdf/ftsdfrend.c (*): Added functionality to set
  and get the new `overlaps' property.

* src/sdf/ftsdf.c (sdf_raster_render):
  Removed support for all the optimization modes and
  only keep the subdivision optimization and the new
  overlap support function.

* src/sdf/ftsdf.c (sdf_generate_coarse_grid): Turned
  off until we can find a way to make it faster.

* src/sdf/ftsdf.c (sdf_generate_with_overlaps): Added
  a function to generate SDF for shapes with overlapping
  contours. It basically generate SDF for separate contours
  in seperate bitmaps and then combine them to remove
  overlaps.

5 files changed, 266 insertions, 46 deletions

diff --git a/[GSoC]ChangeLog b/[GSoC]ChangeLog
index 135f12fa7..fef32de43 100644
--- a/[GSoC]ChangeLog
+++ b/[GSoC]ChangeLog
@@ -1,3 +1,31 @@
+2020-08-12  Anuj Verma  <anujv@iitbhilai.ac.in>
+
+	[sdf] Added overlap support (currently only for TrueType).
+
+	* src/sdf/ftsdfrend.h (SDF_Renderer_Module): Removed the
+	  expermental `optimization' property.
+	  Added another property `overlaps', which can be used to
+	  turn on the overlap support.
+
+	* src/sdf/ftsdf.h (SDF_Raster_Params): Ditto as above.
+
+	* src/sdf/ftsdfrend.c (*): Added functionality to set
+	  and get the new `overlaps' property.
+
+	* src/sdf/ftsdf.c (sdf_raster_render):
+	  Removed support for all the optimization modes and
+	  only keep the subdivision optimization and the new
+	  overlap support function.
+
+	* src/sdf/ftsdf.c (sdf_generate_coarse_grid): Turned
+	  off until we can find a way to make it faster.
+
+	* src/sdf/ftsdf.c (sdf_generate_with_overlaps): Added
+	  a function to generate SDF for shapes with overlapping
+	  contours. It basically generate SDF for separate contours
+	  in seperate bitmaps and then combine them to remove
+	  overlaps.
+
 2020-08-7  Anuj Verma  <anujv@iitbhilai.ac.in>
 
 	[sdf, bsdf] Added better documentation.
diff --git a/src/sdf/ftsdf.c b/src/sdf/ftsdf.c
index 83323a7df..98f4cfc64 100644
--- a/src/sdf/ftsdf.c
+++ b/src/sdf/ftsdf.c
@@ -143,10 +143,14 @@
   /* then they will be checked for corner if they have ambiguity.         */
   #define CORNER_CHECK_EPSILON   32
 
+  #if 0
+
   /* Coarse grid dimension. Probably will be removed in the future cause  */
   /* coarse grid optimization is the slowest.                             */
   #define CG_DIMEN               8
 
+  #endif
+
   /**************************************************************************
    *
    * macros
@@ -247,8 +251,8 @@
   typedef enum  SDF_Contour_Orientation_
   {
     SDF_ORIENTATION_NONE  = 0,
-    SDF_ORIENTATION_CW    = 0,
-    SDF_ORIENTATION_ACW   = 0
+    SDF_ORIENTATION_CW    = 1,
+    SDF_ORIENTATION_ACW   = 2
 
   } SDF_Contour_Orientation;
 
@@ -410,6 +414,12 @@
    *     useful because OpenGL and DirectX have different coordinate
    *     system for textures.
    *
+   *   overload_sign ::
+   *     In the subdivision and bounding box optimization, the default
+   *     outside sign is taken as -1. This parameter can be used to
+   *     modify that behaviour. For example, while generating SDF for
+   *     single counter-clockwise contour the outside sign should be 1.
+   *
    */
   typedef struct SDF_Params_
   {
@@ -417,6 +427,8 @@
     FT_Bool         flip_sign;
     FT_Bool         flip_y;
 
+    FT_Int          overload_sign;
+
   } SDF_Params;
 
   /**************************************************************************
@@ -3068,6 +3080,9 @@
       FT_Char  current_sign = -1;
       FT_UInt  index;
 
+      if ( internal_params.overload_sign != 0 )
+        current_sign = internal_params.overload_sign < 0 ? -1 : 1;
+
       for ( i = 0; i < width; i++ )
       {
         index = j * width + i;
@@ -3145,6 +3160,186 @@
     return error;
   }
 
+  /**************************************************************************
+   *
+   * @Function:
+   *   sdf_generate_with_overlaps
+   *
+   * @Description:
+   *   This function can be used to generate SDF for glyphs with
+   *   overlapping contours. The function generate SDF for contours
+   *   seperately on seperate bitmaps (to generate SDF it uses
+   *   `sdf_generate_subdivision'). And at the end it simply combine 
+   *   all the SDF into the output bitmap, this fixes all the signs
+   *   and removes overlaps.
+   *
+   * @Input:
+   *   internal_params ::
+   *     Internal parameters and properties required by the rasterizer.
+   *     See `SDF_Params' for the actual parameters.
+   *
+   *   shape ::
+   *     A complete shape which is used to generate SDF.
+   *
+   *   spread ::
+   *     Maximum distances to be allowed inthe output bitmap.
+   *
+   * @Return
+   *   bitmap ::
+   *     The output bitmap which will contain the SDF information.
+   *
+   *   FT_Error ::
+   *     FreeType error, 0 means success.
+   *
+   */
+  static FT_Error
+  sdf_generate_with_overlaps( SDF_Params        internal_params,
+                              SDF_Shape*        shape,
+                              FT_UInt           spread,
+                              const FT_Bitmap*  bitmap )
+  {
+    FT_Error      error = FT_Err_Ok;
+    FT_Int        num_contours;      /* total number of contours      */
+    FT_Int        i, j;              /* iterators                     */
+    FT_Bitmap*    bitmaps;           /* seperate bitmaps for contours */
+    SDF_Contour*  contour;           /* temporary variable to iterate */
+    SDF_Shape     temp_shape;        /* temporary shape               */
+    SDF_Contour*  temp_contour;      /* temporary contour             */
+    FT_Memory     memory;            /* to allocate memory            */
+    FT_6D10*      t;                 /* target bitmap buffer          */
+
+    /* orientation of all the seperate contours */
+    SDF_Contour_Orientation*  orientations;
+
+
+    if ( !shape || !bitmap || !shape->memory )
+    {
+      error = FT_THROW( Invalid_Argument );
+      goto Exit;
+    }
+
+    /* assign the necessary variables */
+    contour = shape->contours;
+    memory = shape->memory;
+    temp_shape.memory = memory;
+    num_contours = 0;
+
+    /* find the number of contours in the shape */
+    while ( contour )
+    {
+      num_contours++;
+      contour = contour->next;
+    }
+
+    /* allocate the bitmaps to generate SDF for seperate contours */
+    if ( SDF_ALLOC( bitmaps, num_contours * sizeof( *bitmaps ) ) )
+      goto Exit;
+
+    /* allocate array to hold orientation for all contours */
+    if ( SDF_ALLOC( orientations, num_contours * sizeof( *orientations ) ) )
+      goto Exit;
+
+    contour = shape->contours;
+
+    /* Iterate through all the contours */
+    /* and generate SDF seperately.     */
+    for ( i = 0; i < num_contours; i++ )
+    {
+      /* initialize the corresponding bitmap */
+      FT_Bitmap_Init( &bitmaps[i] );
+
+      bitmaps[i].width      = bitmap->width;
+      bitmaps[i].rows       = bitmap->rows;
+      bitmaps[i].pitch      = bitmap->pitch;
+      bitmaps[i].num_grays  = bitmap->num_grays;
+      bitmaps[i].pixel_mode = bitmap->pixel_mode;
+
+      /* allocate memory for the buffer */
+      if ( SDF_ALLOC( bitmaps[i].buffer, bitmap->rows * bitmap->pitch ) )
+        goto Exit;
+
+      /* Allocate a temporary contour to pass to the */
+      /* generation function. This is done because   */
+      /* `split_sdf_shape' deallocate the contour,   */
+      /* so we cannot pass a static memory.          */
+      if ( SDF_ALLOC( temp_contour, sizeof( *temp_contour ) ) )
+        goto Exit;
+
+      /* initialize the new contour */
+      temp_contour->edges  = contour->edges;
+      temp_contour->next   = NULL;
+
+      /* Use the `temp_shape' to hold the new contour. */
+      /* Now, the `temp_shape' has only one contour.   */
+      temp_shape.contours  = temp_contour;
+
+      /* determine the orientation */
+      orientations[i] = get_contour_orientation( temp_contour );
+
+      /* The `overload_sign; property is specific to  */
+      /* sdf_generate_bounding_box. This basically    */
+      /* overload the default sign of the outside     */
+      /* pixels. Which is necessary for counter clock */
+      /* wise contours.                               */
+      if ( orientations[i] == SDF_ORIENTATION_ACW )
+        internal_params.overload_sign = -1;
+      else
+        internal_params.overload_sign = 0;
+
+      /* finally generate the SDF */
+      FT_CALL( sdf_generate_subdivision( internal_params,
+                                         &temp_shape,
+                                         spread,
+                                         &bitmaps[i] ) );
+
+      contour = contour->next;
+    }
+
+    /* cast the output bitmap buffer */
+    t  = (FT_6D10*)bitmap->buffer;
+
+    /* Iterate through all the pixels and combine all the */
+    /* seperate contours. This is the rule for combining: */
+    /*                                                    */
+    /* => For all clockwise contours compute the largest  */
+    /*    value. Name this as `val_c'.                    */
+    /* => For all counter clockwise contours compute the  */
+    /*    smallest value. Name this as `val_ac'.          */
+    /* => Now, finally use the smaller of `val_c' and     */
+    /*    `val_ac'.                                       */
+    for ( j = 0; j < bitmap->rows; j++ )
+    {
+      for ( i = 0; i < bitmap->width; i++ )
+      {
+        FT_Int   id = j * bitmap->width + i; /* index of current pixel   */
+        FT_Int   c;                          /* contour iterator         */
+        FT_6D10  val_c  = SHRT_MIN;          /* max clockwise value      */
+        FT_6D10  val_ac = SHRT_MAX;          /* min anti-clockwise value */
+
+
+        /* iterate through all the contours */
+        for ( c = 0; c < num_contours; c++ )
+        {
+          /* current contour value */
+          FT_6D10  temp = ((FT_6D10*)bitmaps[c].buffer)[id];
+
+
+          if ( orientations[c] == SDF_ORIENTATION_CW )
+            val_c = FT_MAX( val_c, temp );  /* for clockwise */
+          else
+            val_ac = FT_MIN( val_ac, temp ); /* for anti-clockwise */
+        }
+
+        /* finally find the smaller of two and assign to output */
+        t[id] = FT_MIN( val_c, val_ac );
+      }
+    }
+
+  Exit:
+    return error;
+  }
+
+  #if 0 /* coarse grid optimization is the slowest at the moment. */
 
   /**************************************************************************
    *
@@ -3404,6 +3599,8 @@
     return error;
   }
 
+  #endif
+
   /**************************************************************************
    *
    * interface functions
@@ -3526,6 +3723,7 @@
     internal_params.orientation = FT_Outline_Get_Orientation( outline );
     internal_params.flip_sign = sdf_params->flip_sign;
     internal_params.flip_y = sdf_params->flip_y;
+    internal_params.overload_sign = 0;
 
     /* assign a custom user pointer to `FT_Memory'   */
     /* also keep a reference of the old user pointer */
@@ -3537,26 +3735,17 @@
 
     FT_CALL( sdf_outline_decompose( outline, shape ) );
 
-    /* TEMPORARY */
-    if ( sdf_params->optimization == OPTIMIZATION_BB )
-      FT_CALL( sdf_generate_bounding_box( internal_params,
-                                          shape, sdf_params->spread,
-                                          sdf_params->root.target ) );
-    else if ( sdf_params->optimization == OPTIMIZATION_SUB )
+    if ( sdf_params->overlaps )
+      FT_CALL( sdf_generate_with_overlaps( internal_params,
+                                           shape, sdf_params->spread,
+                                           sdf_params->root.target ) );
+    else
       FT_CALL( sdf_generate_subdivision( internal_params,
                                          shape, sdf_params->spread,
                                          sdf_params->root.target ) );
-    else if ( sdf_params->optimization == OPTIMIZATION_CG )
-      FT_CALL( sdf_generate_coarse_grid( internal_params,
-                                         shape, sdf_params->spread,
-                                         sdf_params->root.target ) );
-    else
-      FT_CALL( sdf_generate( internal_params,
-                             shape, sdf_params->spread,
-                             sdf_params->root.target ) );
 
-    if ( shape )
-      sdf_shape_done( &shape );
+    //if ( shape )
+    //  sdf_shape_done( &shape );
 
     /* restore the memory->user */
     SDF_MEMORY_TRACKER_DONE();
diff --git a/src/sdf/ftsdf.h b/src/sdf/ftsdf.h
index 4d786adff..914401a34 100644
--- a/src/sdf/ftsdf.h
+++ b/src/sdf/ftsdf.h
@@ -11,16 +11,6 @@
 
 FT_BEGIN_HEADER
 
-  /* @experimental struct: */
-  typedef enum Optimizations_ {
-    OPTIMIZATION_NONE = 0,  /* default: check all points against all edges  */
-    OPTIMIZATION_BB   = 1,  /* use bounding box to check nearby grid points */
-    OPTIMIZATION_SUB  = 2,  /* subdivide then use bounding box              */
-    OPTIMIZATION_CG   = 3   /* use coarse grid to only check relevant edges */
-
-  } Optimizations;
-  /* --------- */
-
   /**************************************************************************
    *
    * @struct:
@@ -53,6 +43,13 @@ FT_BEGIN_HEADER
    *     Setting this parameter to true maked the output image flipped
    *     along the y-axis.
    *
+   *   overlaps ::
+   *     Set this to true to generate SDF for glyphs having overlapping
+   *     contours. The overlapping support is limited to glyph which do
+   *     not have self intersecting contours. Also, removing overlaps
+   *     require a considerable amount of extra memory and this is not
+   *     valid while generating SDF from bitmap.
+   *
    * @note:
    *   It is valid for both `sdf' and `bsdf' renderer.
    *
@@ -63,9 +60,7 @@ FT_BEGIN_HEADER
     FT_UInt           spread;
     FT_Bool           flip_sign;
     FT_Bool           flip_y;
-
-    /* @experimental fields: */
-    FT_Int            optimization;
+    FT_Bool           overlaps;
 
   } SDF_Raster_Params;
 
diff --git a/src/sdf/ftsdfrend.c b/src/sdf/ftsdfrend.c
index dbd5f0010..d65d28083 100644
--- a/src/sdf/ftsdfrend.c
+++ b/src/sdf/ftsdfrend.c
@@ -81,15 +81,14 @@
       FT_TRACE7(( "[sdf] sdf_property_set: "
                   "updated property `flip_y' to %d\n", val ));
     }
-    /* TEMPORARY */
-    else if ( ft_strcmp( property_name, "optimization" ) == 0 )
+    else if ( ft_strcmp( property_name, "overlaps" ) == 0 )
     {
       FT_Int  val = *(const FT_Int*)value;
 
 
-      render->optimization = val;
+      render->overlaps = val;
       FT_TRACE7(( "[sdf] sdf_property_set: "
-                  "updated property `optimization' to %d\n", val ));
+                  "updated property `overlaps' to %d\n", val ));
     }
     else
     {
@@ -133,6 +132,13 @@
 
       *val = render->flip_y;
     }
+    else if ( ft_strcmp( property_name, "overlaps" ) == 0 )
+    {
+      FT_Int*  val = (FT_Int*)value;
+
+
+      *val = render->overlaps;
+    }
     else
     {
       FT_TRACE0(( "[sdf] sdf_property_get: "
@@ -179,9 +185,7 @@
     sdf_render->spread    = DEFAULT_SPREAD;
     sdf_render->flip_sign = 0;
     sdf_render->flip_y    = 0;
-
-    /* TEMPORARY */
-    sdf_render->optimization = OPTIMIZATION_NONE;
+    sdf_render->overlaps  = 0;
 
     return FT_Err_Ok;
   }
@@ -295,9 +299,7 @@
     params.spread      = sdf_module->spread;
     params.flip_sign   = sdf_module->flip_sign;
     params.flip_y      = sdf_module->flip_y;
-
-    /* TEMPORARY */
-    params.optimization = sdf_module->optimization;
+    params.overlaps    = sdf_module->overlaps;
 
     /* render the outline */
     error = render->raster_render( render->raster, (const FT_Raster_Params*)&params );
diff --git a/src/sdf/ftsdfrend.h b/src/sdf/ftsdfrend.h
index 766134980..80ebd2bcc 100644
--- a/src/sdf/ftsdfrend.h
+++ b/src/sdf/ftsdfrend.h
@@ -40,9 +40,17 @@ FT_BEGIN_HEADER
    *   flip_y ::
    *     Setting this parameter to true maked the output image flipped
    *     along the y-axis.
-
+   *   
+   *   overlaps ::
+   *     Set this to true to generate SDF for glyphs having overlapping
+   *     contours. The overlapping support is limited to glyph which do
+   *     not have self intersecting contours. Also, removing overlaps
+   *     require a considerable amount of extra memory and this is not
+   *     valid while generating SDF from bitmap.
+   *
    * @note:
-   *   It is valid for both `sdf' and `bsdf' renderer.
+   *   All properties except `overlaps' is valid for both `sdf' and
+   *   `bsdf' renderer.
    *
    */
   typedef struct  SDF_Renderer_Module_
@@ -51,9 +59,7 @@ FT_BEGIN_HEADER
     FT_UInt         spread;
     FT_Bool         flip_sign;
     FT_Bool         flip_y;
-
-    /* @experimental fields: */
-    FT_Int          optimization;
+    FT_Bool         overlaps;
 
   } SDF_Renderer_Module, *SDF_Renderer;