ahoptim.c

qt-embedded-2.3.8.tar.gz源码

        }
      }
      *p_num_springs = num_springs;
      *p_springs     = springs;

      stems      = optimizer->vert_stems;
      stem_limit = stems + optimizer->num_vstems;

      p_springs     = &optimizer->vert_springs;
      p_num_springs = &optimizer->num_vsprings;
    }

  Exit:

#ifdef AH_DEBUG_OPTIM
    AH_Dump_Springs( optimizer );
#endif

    return error;
  }


  /*************************************************************************/
  /*************************************************************************/
  /*************************************************************************/
  /****                                                                 ****/
  /****   OPTIMIZE THROUGH MY STRANGE SIMULATED ANNEALING ALGO ;-)      ****/
  /****                                                                 ****/
  /*************************************************************************/
  /*************************************************************************/
  /*************************************************************************/

#ifndef AH_BRUTE_FORCE

  /* compute all spring tensions */
  static
  void  optim_compute_tensions( AH_Optimizer*  optimizer )
  {
    AH_Spring*  spring = optimizer->springs;
    AH_Spring*  limit  = spring + optimizer->num_springs;


    for ( ; spring < limit; spring++ )
    {
      AH_Stem*  stem1 = spring->stem1;
      AH_Stem*  stem2 = spring->stem2;
      FT_Int    status;

      FT_Pos  width;
      FT_Pos  tension;
      FT_Pos  sign;


      /* compute the tension; it simply is -K*(new_width-old_width) */
      width   = stem2->pos - ( stem1->pos + stem1->width );
      tension = width - spring->owidth;

      sign = 1;
      if ( tension < 0 )
      {
        sign    = -1;
        tension = -tension;
      }

      if ( width <= 0 )
        tension = 32000;
      else
        tension = ( tension << 10 ) / width;

      tension = -sign * FT_MulFix( tension, optimizer->tension_scale );
      spring->tension = tension;

      /* now, distribute tension among the englobing stems, if they */
      /* are able to move                                           */
      status = 0;
      if ( stem1->pos <= stem1->min_pos )
        status |= 1;
      if ( stem2->pos >= stem2->max_pos )
        status |= 2;

      if ( !status )
        tension /= 2;

      if ( ( status & 1 ) == 0 )
        stem1->force -= tension;

      if ( ( status & 2 ) == 0 )
        stem2->force += tension;
    }
  }


  /* compute all stem movements -- returns 0 if nothing moved */
  static
  int  optim_compute_stem_movements( AH_Optimizer*  optimizer )
  {
    AH_Stem*  stems = optimizer->stems;
    AH_Stem*  limit = stems + optimizer->num_stems;
    AH_Stem*  stem  = stems;
    int       moved = 0;


    /* set initial forces to velocity */
    for ( stem = stems; stem < limit; stem++ )
    {
      stem->force     = stem->velocity;
      stem->velocity /= 2;                  /* XXX: Heuristics */
    }

    /* compute the sum of forces applied on each stem */
    optim_compute_tensions( optimizer );

#ifdef AH_DEBUG_OPTIM
    AH_Dump_Springs( optimizer );
    AH_Dump_Stems2( optimizer );
#endif

    /* now, see whether something can move */
    for ( stem = stems; stem < limit; stem++ )
    {
      if ( stem->force > optimizer->tension_threshold )
      {
        /* there is enough tension to move the stem to the right */
        if ( stem->pos < stem->max_pos )
        {
          stem->pos     += 64;
          stem->velocity = stem->force / 2;
          moved          = 1;
        }
        else
          stem->velocity = 0;
      }
      else if ( stem->force < optimizer->tension_threshold )
      {
        /* there is enough tension to move the stem to the left */
        if ( stem->pos > stem->min_pos )
        {
          stem->pos     -= 64;
          stem->velocity = stem->force / 2;
          moved          = 1;
        }
        else
          stem->velocity = 0;
      }
    }

    /* return 0 if nothing moved */
    return moved;
  }

#endif /* AH_BRUTE_FORCE */


  /* compute current global distortion from springs */
  static
  FT_Pos  optim_compute_distortion( AH_Optimizer*  optimizer )
  {
    AH_Spring*  spring = optimizer->springs;
    AH_Spring*  limit  = spring + optimizer->num_springs;
    FT_Pos      distortion = 0;


    for ( ; spring < limit; spring++ )
    {
      AH_Stem*  stem1 = spring->stem1;
      AH_Stem*  stem2 = spring->stem2;
      FT_Pos  width;

      width  = stem2->pos - ( stem1->pos + stem1->width );
      width -= spring->owidth;
      if ( width < 0 )
        width = -width;

      distortion += width;
    }

    return distortion;
  }


  /* record stems configuration in `best of' history */
  static
  void  optim_record_configuration( AH_Optimizer*  optimizer )
  {
    FT_Pos             distortion;
    AH_Configuration*  configs = optimizer->configs;
    AH_Configuration*  limit   = configs + optimizer->num_configs;
    AH_Configuration*  config;


    distortion = optim_compute_distortion( optimizer );
    LOG(( "config distortion = %.1f ", FLOAT( distortion * 64 ) ));

    /* check that we really need to add this configuration to our */
    /* sorted history                                             */
    if ( limit > configs && limit[-1].distortion < distortion )
    {
      LOG(( "ejected\n" ));
      return;
    }

    /* add new configuration at the end of the table */
    {
      int  n;


      config = limit;
      if ( optimizer->num_configs < AH_MAX_CONFIGS )
        optimizer->num_configs++;
      else
        config--;

      config->distortion = distortion;

      for ( n = 0; n < optimizer->num_stems; n++ )
        config->positions[n] = optimizer->stems[n].pos;
    }

    /* move the current configuration towards the front of the list */
    /* when necessary -- yes this is slow bubble sort ;-)           */
    while ( config > configs && config[0].distortion < config[-1].distortion )
    {
      AH_Configuration  temp;


      config--;
      temp      = config[0];
      config[0] = config[1];
      config[1] = temp;
    }
    LOG(( "recorded!\n" ));
  }


#ifdef AH_BRUTE_FORCE

  /* optimize outline in a single direction */
  static
  void  optim_compute( AH_Optimizer*  optimizer )
  {
    int       n;
    FT_Bool   moved;

    AH_Stem*  stem  = optimizer->stems;
    AH_Stem*  limit = stem + optimizer->num_stems;


    /* empty, exit */
    if ( stem >= limit )
      return;

    optimizer->num_configs = 0;

    stem = optimizer->stems;
    for ( ; stem < limit; stem++ )
      stem->pos = stem->min_pos;

    do
    {
      /* record current configuration */
      optim_record_configuration( optimizer );

      /* now change configuration */
      moved = 0;
      for ( stem = optimizer->stems; stem < limit; stem++ )
      {
        if ( stem->pos < stem->max_pos )
        {
          stem->pos += 64;
          moved      = 1;
          break;
        }

        stem->pos = stem->min_pos;
      }
    } while ( moved );

    /* now, set the best stem positions */
    for ( n = 0; n < optimizer->num_stems; n++ )
    {
      AH_Stem*  stem = optimizer->stems + n;
      FT_Pos    pos  = optimizer->configs[0].positions[n];


      stem->edge1->pos = pos;
      stem->edge2->pos = pos + stem->width;

      stem->edge1->flags |= ah_edge_done;
      stem->edge2->flags |= ah_edge_done;
    }
  }

#else /* AH_BRUTE_FORCE */

  /* optimize outline in a single direction */
  static
  void  optim_compute( AH_Optimizer*  optimizer )
  {
    int  n, counter, counter2;


    optimizer->num_configs       = 0;
    optimizer->tension_scale     = 0x80000L;
    optimizer->tension_threshold = 64;

    /* record initial configuration threshold */
    optim_record_configuration( optimizer );

    counter = 0;
    for ( counter2 = optimizer->num_stems*8; counter2 >= 0; counter2-- )
    {
      if ( counter == 0 )
        counter = 2 * optimizer->num_stems;

      if ( !optim_compute_stem_movements( optimizer ) )
        break;

      optim_record_configuration( optimizer );

      counter--;
      if ( counter == 0 )
        optimizer->tension_scale /= 2;
    }

    /* now, set the best stem positions */
    for ( n = 0; n < optimizer->num_stems; n++ )
    {
      AH_Stem*  stem = optimizer->stems + n;
      FT_Pos    pos  = optimizer->configs[0].positions[n];


      stem->edge1->pos = pos;
      stem->edge2->pos = pos + stem->width;

      stem->edge1->flags |= ah_edge_done;
      stem->edge2->flags |= ah_edge_done;
    }
  }

#endif /* AH_BRUTE_FORCE */


  /*************************************************************************/
  /*************************************************************************/
  /*************************************************************************/
  /****                                                                 ****/
  /****   HIGH-LEVEL OPTIMIZER API                                      ****/
  /****                                                                 ****/
  /*************************************************************************/
  /*************************************************************************/
  /*************************************************************************/


  /* releases the optimization data */
  void AH_Optimizer_Done( AH_Optimizer*  optimizer )
  {
    if ( optimizer )
    {
      FT_Memory  memory = optimizer->memory;


      FREE( optimizer->horz_stems );
      FREE( optimizer->vert_stems );
      FREE( optimizer->horz_springs );
      FREE( optimizer->vert_springs );
      FREE( optimizer->positions );
    }
  }


  /* loads the outline into the optimizer */
  int  AH_Optimizer_Init( AH_Optimizer*  optimizer,
                          AH_Outline*    outline,
                          FT_Memory      memory )
  {
    FT_Error  error;


    MEM_Set( optimizer, 0, sizeof ( *optimizer ) );
    optimizer->outline = outline;
    optimizer->memory  = memory;

    LOG(( "initializing new optimizer\n" ));
    /* compute stems and springs */
    error = optim_compute_stems  ( optimizer ) ||
            optim_compute_springs( optimizer );
    if ( error )
      goto Fail;

    /* allocate stem positions history and configurations */
    {
      int  n, max_stems;


      max_stems = optimizer->num_hstems;
      if ( max_stems < optimizer->num_vstems )
        max_stems = optimizer->num_vstems;

      if ( ALLOC_ARRAY( optimizer->positions,
                        max_stems * AH_MAX_CONFIGS, FT_Pos ) )
        goto Fail;

      optimizer->num_configs = 0;
      for ( n = 0; n < AH_MAX_CONFIGS; n++ )
        optimizer->configs[n].positions = optimizer->positions +
                                          n * max_stems;
    }

    return error;

  Fail:
    AH_Optimizer_Done( optimizer );
    return error;
  }


  /* compute optimal outline */
  void  AH_Optimizer_Compute( AH_Optimizer*  optimizer )
  {
    optimizer->num_stems   = optimizer->num_hstems;
    optimizer->stems       = optimizer->horz_stems;
    optimizer->num_springs = optimizer->num_hsprings;
    optimizer->springs     = optimizer->horz_springs;

    if ( optimizer->num_springs > 0 )
    {
      LOG(( "horizontal optimization ------------------------\n" ));
      optim_compute( optimizer );
    }

    optimizer->num_stems   = optimizer->num_vstems;
    optimizer->stems       = optimizer->vert_stems;
    optimizer->num_springs = optimizer->num_vsprings;
    optimizer->springs     = optimizer->vert_springs;

    if ( optimizer->num_springs )
    {
      LOG(( "vertical optimization --------------------------\n" ));
      optim_compute( optimizer );
    }
  }


/* END */