David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 1 | /***************************************************************************/ |
| 2 | /* */ |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 3 | /* ahoptim.c */ |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 4 | /* */ |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 5 | /* FreeType auto hinting outline optimization (body). */ |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 6 | /* */ |
Werner Lemberg | 415235d | 2001-06-28 17:49:10 +0000 | [diff] [blame] | 7 | /* Copyright 2000-2001 Catharon Productions Inc. */ |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 8 | /* Author: David Turner */ |
| 9 | /* */ |
| 10 | /* This file is part of the Catharon Typography Project and shall only */ |
| 11 | /* be used, modified, and distributed under the terms of the Catharon */ |
| 12 | /* Open Source License that should come with this file under the name */ |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 13 | /* `CatharonLicense.txt'. By continuing to use, modify, or distribute */ |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 14 | /* this file you indicate that you have read the license and */ |
| 15 | /* understand and accept it fully. */ |
| 16 | /* */ |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 17 | /* Note that this license is compatible with the FreeType license. */ |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 18 | /* */ |
| 19 | /***************************************************************************/ |
| 20 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 21 | |
| 22 | /*************************************************************************/ |
| 23 | /* */ |
| 24 | /* This module is in charge of optimising the outlines produced by the */ |
| 25 | /* auto-hinter in direct mode. This is required at small pixel sizes in */ |
| 26 | /* order to ensure coherent spacing, among other things.. */ |
| 27 | /* */ |
| 28 | /* The technique used in this module is a simplified simulated */ |
| 29 | /* annealing. */ |
| 30 | /* */ |
| 31 | /*************************************************************************/ |
| 32 | |
Werner Lemberg | cc069be | 2000-12-08 16:17:16 +0000 | [diff] [blame] | 33 | |
| 34 | #include <ft2build.h> |
David Turner | e459d74 | 2002-03-22 13:52:37 +0000 | [diff] [blame^] | 35 | #include FT_INTERNAL_OBJECTS_H /* for FT_ALLOC_ARRAY() and FT_FREE() */ |
David Turner | 8d3a401 | 2001-03-20 11:14:24 +0000 | [diff] [blame] | 36 | #include "ahoptim.h" |
Werner Lemberg | cc069be | 2000-12-08 16:17:16 +0000 | [diff] [blame] | 37 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 38 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 39 | /* define this macro to use brute force optimisation -- this is slow, */ |
| 40 | /* but a good way to perfect the distortion function `by hand' through */ |
| 41 | /* tweaking */ |
| 42 | #define AH_BRUTE_FORCE |
| 43 | |
| 44 | |
| 45 | #define xxxAH_DEBUG_OPTIM |
| 46 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 47 | |
| 48 | #undef LOG |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 49 | #ifdef AH_DEBUG_OPTIM |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 50 | |
Werner Lemberg | 16a60e8 | 2000-12-12 16:29:46 +0000 | [diff] [blame] | 51 | #define LOG( x ) optim_log ## x |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 52 | |
| 53 | #else |
| 54 | |
| 55 | #define LOG( x ) |
| 56 | |
| 57 | #endif /* AH_DEBUG_OPTIM */ |
| 58 | |
| 59 | |
| 60 | #ifdef AH_DEBUG_OPTIM |
| 61 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 62 | #include <stdarg.h> |
| 63 | #include <stdlib.h> |
| 64 | #include <string.h> |
| 65 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 66 | #define FLOAT( x ) ( (float)( (x) / 64.0 ) ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 67 | |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 68 | static void |
| 69 | optim_log( const char* fmt, ... ) |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 70 | { |
| 71 | va_list ap; |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 72 | |
| 73 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 74 | va_start( ap, fmt ); |
| 75 | vprintf( fmt, ap ); |
| 76 | va_end( ap ); |
| 77 | } |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 78 | |
| 79 | |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 80 | static void |
| 81 | AH_Dump_Stems( AH_Optimizer* optimizer ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 82 | { |
| 83 | int n; |
| 84 | AH_Stem* stem; |
| 85 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 86 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 87 | stem = optimizer->stems; |
| 88 | for ( n = 0; n < optimizer->num_stems; n++, stem++ ) |
| 89 | { |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 90 | LOG(( " %c%2d [%.1f:%.1f]={%.1f:%.1f}=" |
| 91 | "<%1.f..%1.f> force=%.1f speed=%.1f\n", |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 92 | optimizer->vertical ? 'V' : 'H', n, |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 93 | FLOAT( stem->edge1->opos ), FLOAT( stem->edge2->opos ), |
| 94 | FLOAT( stem->edge1->pos ), FLOAT( stem->edge2->pos ), |
| 95 | FLOAT( stem->min_pos ), FLOAT( stem->max_pos ), |
| 96 | FLOAT( stem->force ), FLOAT( stem->velocity ) )); |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 97 | } |
| 98 | } |
| 99 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 100 | |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 101 | static void |
| 102 | AH_Dump_Stems2( AH_Optimizer* optimizer ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 103 | { |
| 104 | int n; |
| 105 | AH_Stem* stem; |
| 106 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 107 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 108 | stem = optimizer->stems; |
| 109 | for ( n = 0; n < optimizer->num_stems; n++, stem++ ) |
| 110 | { |
| 111 | LOG(( " %c%2d [%.1f]=<%1.f..%1.f> force=%.1f speed=%.1f\n", |
| 112 | optimizer->vertical ? 'V' : 'H', n, |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 113 | FLOAT( stem->pos ), |
| 114 | FLOAT( stem->min_pos ), FLOAT( stem->max_pos ), |
| 115 | FLOAT( stem->force ), FLOAT( stem->velocity ) )); |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 116 | } |
| 117 | } |
| 118 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 119 | |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 120 | static void |
| 121 | AH_Dump_Springs( AH_Optimizer* optimizer ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 122 | { |
| 123 | int n; |
| 124 | AH_Spring* spring; |
| 125 | AH_Stem* stems; |
| 126 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 127 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 128 | spring = optimizer->springs; |
| 129 | stems = optimizer->stems; |
| 130 | LOG(( "%cSprings ", optimizer->vertical ? 'V' : 'H' )); |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 131 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 132 | for ( n = 0; n < optimizer->num_springs; n++, spring++ ) |
| 133 | { |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 134 | LOG(( " [%d-%d:%.1f:%1.f:%.1f]", |
| 135 | spring->stem1 - stems, spring->stem2 - stems, |
| 136 | FLOAT( spring->owidth ), |
Werner Lemberg | e4b32a5 | 2000-10-31 20:42:18 +0000 | [diff] [blame] | 137 | FLOAT( spring->stem2->pos - |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 138 | ( spring->stem1->pos + spring->stem1->width ) ), |
| 139 | FLOAT( spring->tension ) )); |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 140 | } |
| 141 | |
| 142 | LOG(( "\n" )); |
| 143 | } |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 144 | |
| 145 | #endif /* AH_DEBUG_OPTIM */ |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 146 | |
| 147 | |
| 148 | /*************************************************************************/ |
| 149 | /*************************************************************************/ |
| 150 | /*************************************************************************/ |
| 151 | /**** ****/ |
| 152 | /**** COMPUTE STEMS AND SPRINGS IN AN OUTLINE ****/ |
| 153 | /**** ****/ |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 154 | /*************************************************************************/ |
| 155 | /*************************************************************************/ |
| 156 | /*************************************************************************/ |
| 157 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 158 | |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 159 | static int |
| 160 | valid_stem_segments( AH_Segment* seg1, |
| 161 | AH_Segment* seg2 ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 162 | { |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 163 | return seg1->serif == 0 && |
| 164 | seg2 && |
| 165 | seg2->link == seg1 && |
| 166 | seg1->pos < seg2->pos && |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 167 | seg1->min_coord <= seg2->max_coord && |
| 168 | seg2->min_coord <= seg1->max_coord; |
| 169 | } |
| 170 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 171 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 172 | /* compute all stems in an outline */ |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 173 | static int |
| 174 | optim_compute_stems( AH_Optimizer* optimizer ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 175 | { |
| 176 | AH_Outline* outline = optimizer->outline; |
| 177 | FT_Fixed scale; |
| 178 | FT_Memory memory = optimizer->memory; |
| 179 | FT_Error error = 0; |
| 180 | FT_Int dimension; |
| 181 | AH_Edge* edges; |
| 182 | AH_Edge* edge_limit; |
| 183 | AH_Stem** p_stems; |
| 184 | FT_Int* p_num_stems; |
| 185 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 186 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 187 | edges = outline->horz_edges; |
| 188 | edge_limit = edges + outline->num_hedges; |
| 189 | scale = outline->y_scale; |
| 190 | |
| 191 | p_stems = &optimizer->horz_stems; |
| 192 | p_num_stems = &optimizer->num_hstems; |
| 193 | |
| 194 | for ( dimension = 1; dimension >= 0; dimension-- ) |
| 195 | { |
| 196 | AH_Stem* stems = 0; |
| 197 | FT_Int num_stems = 0; |
| 198 | AH_Edge* edge; |
| 199 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 200 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 201 | /* first of all, count the number of stems in this direction */ |
| 202 | for ( edge = edges; edge < edge_limit; edge++ ) |
| 203 | { |
| 204 | AH_Segment* seg = edge->first; |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 205 | |
| 206 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 207 | do |
| 208 | { |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 209 | if (valid_stem_segments( seg, seg->link ) ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 210 | num_stems++; |
| 211 | |
| 212 | seg = seg->edge_next; |
| 213 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 214 | } while ( seg != edge->first ); |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 215 | } |
| 216 | |
| 217 | /* now allocate the stems and build their table */ |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 218 | if ( num_stems > 0 ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 219 | { |
| 220 | AH_Stem* stem; |
| 221 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 222 | |
David Turner | e459d74 | 2002-03-22 13:52:37 +0000 | [diff] [blame^] | 223 | if ( FT_NEW_ARRAY( stems, num_stems ) ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 224 | goto Exit; |
| 225 | |
| 226 | stem = stems; |
| 227 | for ( edge = edges; edge < edge_limit; edge++ ) |
| 228 | { |
| 229 | AH_Segment* seg = edge->first; |
| 230 | AH_Segment* seg2; |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 231 | |
| 232 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 233 | do |
| 234 | { |
| 235 | seg2 = seg->link; |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 236 | if ( valid_stem_segments( seg, seg2 ) ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 237 | { |
| 238 | AH_Edge* edge1 = seg->edge; |
| 239 | AH_Edge* edge2 = seg2->edge; |
| 240 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 241 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 242 | stem->edge1 = edge1; |
| 243 | stem->edge2 = edge2; |
| 244 | stem->opos = edge1->opos; |
| 245 | stem->pos = edge1->pos; |
| 246 | stem->owidth = edge2->opos - edge1->opos; |
| 247 | stem->width = edge2->pos - edge1->pos; |
| 248 | |
| 249 | /* compute min_coord and max_coord */ |
| 250 | { |
| 251 | FT_Pos min_coord = seg->min_coord; |
| 252 | FT_Pos max_coord = seg->max_coord; |
| 253 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 254 | |
| 255 | if ( seg2->min_coord > min_coord ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 256 | min_coord = seg2->min_coord; |
| 257 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 258 | if ( seg2->max_coord < max_coord ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 259 | max_coord = seg2->max_coord; |
| 260 | |
| 261 | stem->min_coord = min_coord; |
| 262 | stem->max_coord = max_coord; |
| 263 | } |
| 264 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 265 | /* compute minimum and maximum positions for stem -- */ |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 266 | /* note that the left-most/bottom-most stem has always */ |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 267 | /* a fixed position */ |
| 268 | if ( stem == stems || edge1->blue_edge || edge2->blue_edge ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 269 | { |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 270 | /* this stem cannot move; it is snapped to a blue edge */ |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 271 | stem->min_pos = stem->pos; |
| 272 | stem->max_pos = stem->pos; |
| 273 | } |
| 274 | else |
| 275 | { |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 276 | /* this edge can move; compute its min and max positions */ |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 277 | FT_Pos pos1 = stem->opos; |
| 278 | FT_Pos pos2 = pos1 + stem->owidth - stem->width; |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 279 | FT_Pos min1 = pos1 & -64; |
| 280 | FT_Pos min2 = pos2 & -64; |
| 281 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 282 | |
| 283 | stem->min_pos = min1; |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 284 | stem->max_pos = min1 + 64; |
| 285 | if ( min2 < min1 ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 286 | stem->min_pos = min2; |
| 287 | else |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 288 | stem->max_pos = min2 + 64; |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 289 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 290 | /* XXX: just to see what it does */ |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 291 | stem->max_pos += 64; |
| 292 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 293 | /* just for the case where direct hinting did some */ |
| 294 | /* incredible things (e.g. blue edge shifts) */ |
| 295 | if ( stem->min_pos > stem->pos ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 296 | stem->min_pos = stem->pos; |
| 297 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 298 | if ( stem->max_pos < stem->pos ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 299 | stem->max_pos = stem->pos; |
| 300 | } |
| 301 | |
| 302 | stem->velocity = 0; |
| 303 | stem->force = 0; |
| 304 | |
| 305 | stem++; |
| 306 | } |
| 307 | seg = seg->edge_next; |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 308 | |
| 309 | } while ( seg != edge->first ); |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 310 | } |
| 311 | } |
| 312 | |
| 313 | *p_stems = stems; |
| 314 | *p_num_stems = num_stems; |
| 315 | |
| 316 | edges = outline->vert_edges; |
| 317 | edge_limit = edges + outline->num_vedges; |
| 318 | scale = outline->x_scale; |
| 319 | |
| 320 | p_stems = &optimizer->vert_stems; |
| 321 | p_num_stems = &optimizer->num_vstems; |
| 322 | } |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 323 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 324 | Exit: |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 325 | |
| 326 | #ifdef AH_DEBUG_OPTIM |
| 327 | AH_Dump_Stems( optimizer ); |
| 328 | #endif |
| 329 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 330 | return error; |
| 331 | } |
| 332 | |
| 333 | |
| 334 | /* returns the spring area between two stems, 0 if none */ |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 335 | static FT_Pos |
| 336 | stem_spring_area( AH_Stem* stem1, |
| 337 | AH_Stem* stem2 ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 338 | { |
| 339 | FT_Pos area1 = stem1->max_coord - stem1->min_coord; |
| 340 | FT_Pos area2 = stem2->max_coord - stem2->min_coord; |
| 341 | FT_Pos min = stem1->min_coord; |
| 342 | FT_Pos max = stem1->max_coord; |
| 343 | FT_Pos area; |
| 344 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 345 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 346 | /* order stems */ |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 347 | if ( stem2->opos <= stem1->opos + stem1->owidth ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 348 | return 0; |
| 349 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 350 | if ( min < stem2->min_coord ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 351 | min = stem2->min_coord; |
| 352 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 353 | if ( max < stem2->max_coord ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 354 | max = stem2->max_coord; |
| 355 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 356 | area = ( max-min ); |
| 357 | if ( 2 * area < area1 && 2 * area < area2 ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 358 | area = 0; |
| 359 | |
| 360 | return area; |
| 361 | } |
| 362 | |
| 363 | |
| 364 | /* compute all springs in an outline */ |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 365 | static int |
| 366 | optim_compute_springs( AH_Optimizer* optimizer ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 367 | { |
| 368 | /* basically, a spring exists between two stems if most of their */ |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 369 | /* surface is aligned */ |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 370 | FT_Memory memory = optimizer->memory; |
| 371 | |
| 372 | AH_Stem* stems; |
| 373 | AH_Stem* stem_limit; |
| 374 | AH_Stem* stem; |
| 375 | int dimension; |
| 376 | int error = 0; |
| 377 | |
| 378 | FT_Int* p_num_springs; |
| 379 | AH_Spring** p_springs; |
| 380 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 381 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 382 | stems = optimizer->horz_stems; |
| 383 | stem_limit = stems + optimizer->num_hstems; |
| 384 | |
| 385 | p_springs = &optimizer->horz_springs; |
| 386 | p_num_springs = &optimizer->num_hsprings; |
| 387 | |
| 388 | for ( dimension = 1; dimension >= 0; dimension-- ) |
| 389 | { |
| 390 | FT_Int num_springs = 0; |
| 391 | AH_Spring* springs = 0; |
| 392 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 393 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 394 | /* first of all, count stem springs */ |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 395 | for ( stem = stems; stem + 1 < stem_limit; stem++ ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 396 | { |
| 397 | AH_Stem* stem2; |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 398 | |
| 399 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 400 | for ( stem2 = stem+1; stem2 < stem_limit; stem2++ ) |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 401 | if ( stem_spring_area( stem, stem2 ) ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 402 | num_springs++; |
| 403 | } |
| 404 | |
| 405 | /* then allocate and build the springs table */ |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 406 | if ( num_springs > 0 ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 407 | { |
| 408 | AH_Spring* spring; |
| 409 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 410 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 411 | /* allocate table of springs */ |
David Turner | e459d74 | 2002-03-22 13:52:37 +0000 | [diff] [blame^] | 412 | if ( FT_NEW_ARRAY( springs, num_springs ) ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 413 | goto Exit; |
| 414 | |
| 415 | /* fill the springs table */ |
| 416 | spring = springs; |
| 417 | for ( stem = stems; stem+1 < stem_limit; stem++ ) |
| 418 | { |
| 419 | AH_Stem* stem2; |
| 420 | FT_Pos area; |
| 421 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 422 | |
| 423 | for ( stem2 = stem + 1; stem2 < stem_limit; stem2++ ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 424 | { |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 425 | area = stem_spring_area( stem, stem2 ); |
| 426 | if ( area ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 427 | { |
| 428 | /* add a new spring here */ |
| 429 | spring->stem1 = stem; |
| 430 | spring->stem2 = stem2; |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 431 | spring->owidth = stem2->opos - ( stem->opos + stem->owidth ); |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 432 | spring->tension = 0; |
| 433 | |
| 434 | spring++; |
| 435 | } |
| 436 | } |
| 437 | } |
| 438 | } |
| 439 | *p_num_springs = num_springs; |
| 440 | *p_springs = springs; |
| 441 | |
| 442 | stems = optimizer->vert_stems; |
| 443 | stem_limit = stems + optimizer->num_vstems; |
| 444 | |
| 445 | p_springs = &optimizer->vert_springs; |
| 446 | p_num_springs = &optimizer->num_vsprings; |
| 447 | } |
| 448 | |
| 449 | Exit: |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 450 | |
| 451 | #ifdef AH_DEBUG_OPTIM |
| 452 | AH_Dump_Springs( optimizer ); |
| 453 | #endif |
| 454 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 455 | return error; |
| 456 | } |
| 457 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 458 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 459 | /*************************************************************************/ |
| 460 | /*************************************************************************/ |
| 461 | /*************************************************************************/ |
| 462 | /**** ****/ |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 463 | /**** OPTIMIZE THROUGH MY STRANGE SIMULATED ANNEALING ALGO ;-) ****/ |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 464 | /**** ****/ |
| 465 | /*************************************************************************/ |
| 466 | /*************************************************************************/ |
| 467 | /*************************************************************************/ |
| 468 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 469 | #ifndef AH_BRUTE_FORCE |
| 470 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 471 | /* compute all spring tensions */ |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 472 | static void |
| 473 | optim_compute_tensions( AH_Optimizer* optimizer ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 474 | { |
| 475 | AH_Spring* spring = optimizer->springs; |
| 476 | AH_Spring* limit = spring + optimizer->num_springs; |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 477 | |
| 478 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 479 | for ( ; spring < limit; spring++ ) |
| 480 | { |
| 481 | AH_Stem* stem1 = spring->stem1; |
| 482 | AH_Stem* stem2 = spring->stem2; |
| 483 | FT_Int status; |
| 484 | |
| 485 | FT_Pos width; |
| 486 | FT_Pos tension; |
| 487 | FT_Pos sign; |
| 488 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 489 | |
| 490 | /* compute the tension; it simply is -K*(new_width-old_width) */ |
| 491 | width = stem2->pos - ( stem1->pos + stem1->width ); |
| 492 | tension = width - spring->owidth; |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 493 | |
| 494 | sign = 1; |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 495 | if ( tension < 0 ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 496 | { |
| 497 | sign = -1; |
| 498 | tension = -tension; |
| 499 | } |
| 500 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 501 | if ( width <= 0 ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 502 | tension = 32000; |
| 503 | else |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 504 | tension = ( tension << 10 ) / width; |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 505 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 506 | tension = -sign * FT_MulFix( tension, optimizer->tension_scale ); |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 507 | spring->tension = tension; |
| 508 | |
| 509 | /* now, distribute tension among the englobing stems, if they */ |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 510 | /* are able to move */ |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 511 | status = 0; |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 512 | if ( stem1->pos <= stem1->min_pos ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 513 | status |= 1; |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 514 | if ( stem2->pos >= stem2->max_pos ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 515 | status |= 2; |
| 516 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 517 | if ( !status ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 518 | tension /= 2; |
| 519 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 520 | if ( ( status & 1 ) == 0 ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 521 | stem1->force -= tension; |
| 522 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 523 | if ( ( status & 2 ) == 0 ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 524 | stem2->force += tension; |
| 525 | } |
| 526 | } |
| 527 | |
| 528 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 529 | /* compute all stem movements -- returns 0 if nothing moved */ |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 530 | static int |
| 531 | optim_compute_stem_movements( AH_Optimizer* optimizer ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 532 | { |
| 533 | AH_Stem* stems = optimizer->stems; |
| 534 | AH_Stem* limit = stems + optimizer->num_stems; |
| 535 | AH_Stem* stem = stems; |
| 536 | int moved = 0; |
| 537 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 538 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 539 | /* set initial forces to velocity */ |
| 540 | for ( stem = stems; stem < limit; stem++ ) |
| 541 | { |
| 542 | stem->force = stem->velocity; |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 543 | stem->velocity /= 2; /* XXX: Heuristics */ |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 544 | } |
| 545 | |
| 546 | /* compute the sum of forces applied on each stem */ |
| 547 | optim_compute_tensions( optimizer ); |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 548 | |
| 549 | #ifdef AH_DEBUG_OPTIM |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 550 | AH_Dump_Springs( optimizer ); |
| 551 | AH_Dump_Stems2( optimizer ); |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 552 | #endif |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 553 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 554 | /* now, see whether something can move */ |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 555 | for ( stem = stems; stem < limit; stem++ ) |
| 556 | { |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 557 | if ( stem->force > optimizer->tension_threshold ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 558 | { |
| 559 | /* there is enough tension to move the stem to the right */ |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 560 | if ( stem->pos < stem->max_pos ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 561 | { |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 562 | stem->pos += 64; |
| 563 | stem->velocity = stem->force / 2; |
| 564 | moved = 1; |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 565 | } |
| 566 | else |
| 567 | stem->velocity = 0; |
| 568 | } |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 569 | else if ( stem->force < optimizer->tension_threshold ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 570 | { |
| 571 | /* there is enough tension to move the stem to the left */ |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 572 | if ( stem->pos > stem->min_pos ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 573 | { |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 574 | stem->pos -= 64; |
| 575 | stem->velocity = stem->force / 2; |
| 576 | moved = 1; |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 577 | } |
| 578 | else |
| 579 | stem->velocity = 0; |
| 580 | } |
| 581 | } |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 582 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 583 | /* return 0 if nothing moved */ |
| 584 | return moved; |
| 585 | } |
| 586 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 587 | #endif /* AH_BRUTE_FORCE */ |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 588 | |
| 589 | |
| 590 | /* compute current global distortion from springs */ |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 591 | static FT_Pos |
| 592 | optim_compute_distortion( AH_Optimizer* optimizer ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 593 | { |
| 594 | AH_Spring* spring = optimizer->springs; |
| 595 | AH_Spring* limit = spring + optimizer->num_springs; |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 596 | FT_Pos distortion = 0; |
| 597 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 598 | |
| 599 | for ( ; spring < limit; spring++ ) |
| 600 | { |
| 601 | AH_Stem* stem1 = spring->stem1; |
| 602 | AH_Stem* stem2 = spring->stem2; |
| 603 | FT_Pos width; |
| 604 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 605 | width = stem2->pos - ( stem1->pos + stem1->width ); |
| 606 | width -= spring->owidth; |
| 607 | if ( width < 0 ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 608 | width = -width; |
| 609 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 610 | distortion += width; |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 611 | } |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 612 | |
| 613 | return distortion; |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 614 | } |
| 615 | |
| 616 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 617 | /* record stems configuration in `best of' history */ |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 618 | static void |
| 619 | optim_record_configuration( AH_Optimizer* optimizer ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 620 | { |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 621 | FT_Pos distortion; |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 622 | AH_Configuration* configs = optimizer->configs; |
| 623 | AH_Configuration* limit = configs + optimizer->num_configs; |
| 624 | AH_Configuration* config; |
| 625 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 626 | |
| 627 | distortion = optim_compute_distortion( optimizer ); |
| 628 | LOG(( "config distortion = %.1f ", FLOAT( distortion * 64 ) )); |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 629 | |
| 630 | /* check that we really need to add this configuration to our */ |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 631 | /* sorted history */ |
| 632 | if ( limit > configs && limit[-1].distortion < distortion ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 633 | { |
| 634 | LOG(( "ejected\n" )); |
| 635 | return; |
| 636 | } |
| 637 | |
| 638 | /* add new configuration at the end of the table */ |
| 639 | { |
| 640 | int n; |
| 641 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 642 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 643 | config = limit; |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 644 | if ( optimizer->num_configs < AH_MAX_CONFIGS ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 645 | optimizer->num_configs++; |
| 646 | else |
| 647 | config--; |
| 648 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 649 | config->distortion = distortion; |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 650 | |
| 651 | for ( n = 0; n < optimizer->num_stems; n++ ) |
| 652 | config->positions[n] = optimizer->stems[n].pos; |
| 653 | } |
| 654 | |
| 655 | /* move the current configuration towards the front of the list */ |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 656 | /* when necessary -- yes this is slow bubble sort ;-) */ |
| 657 | while ( config > configs && config[0].distortion < config[-1].distortion ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 658 | { |
| 659 | AH_Configuration temp; |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 660 | |
| 661 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 662 | config--; |
| 663 | temp = config[0]; |
| 664 | config[0] = config[1]; |
| 665 | config[1] = temp; |
| 666 | } |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 667 | LOG(( "recorded!\n" )); |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 668 | } |
| 669 | |
| 670 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 671 | #ifdef AH_BRUTE_FORCE |
| 672 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 673 | /* optimize outline in a single direction */ |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 674 | static void |
| 675 | optim_compute( AH_Optimizer* optimizer ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 676 | { |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 677 | int n; |
| 678 | FT_Bool moved; |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 679 | |
| 680 | AH_Stem* stem = optimizer->stems; |
| 681 | AH_Stem* limit = stem + optimizer->num_stems; |
| 682 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 683 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 684 | /* empty, exit */ |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 685 | if ( stem >= limit ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 686 | return; |
| 687 | |
| 688 | optimizer->num_configs = 0; |
| 689 | |
| 690 | stem = optimizer->stems; |
| 691 | for ( ; stem < limit; stem++ ) |
| 692 | stem->pos = stem->min_pos; |
| 693 | |
| 694 | do |
| 695 | { |
| 696 | /* record current configuration */ |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 697 | optim_record_configuration( optimizer ); |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 698 | |
| 699 | /* now change configuration */ |
| 700 | moved = 0; |
| 701 | for ( stem = optimizer->stems; stem < limit; stem++ ) |
| 702 | { |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 703 | if ( stem->pos < stem->max_pos ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 704 | { |
| 705 | stem->pos += 64; |
| 706 | moved = 1; |
| 707 | break; |
| 708 | } |
| 709 | |
| 710 | stem->pos = stem->min_pos; |
| 711 | } |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 712 | } while ( moved ); |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 713 | |
| 714 | /* now, set the best stem positions */ |
| 715 | for ( n = 0; n < optimizer->num_stems; n++ ) |
| 716 | { |
| 717 | AH_Stem* stem = optimizer->stems + n; |
| 718 | FT_Pos pos = optimizer->configs[0].positions[n]; |
| 719 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 720 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 721 | stem->edge1->pos = pos; |
| 722 | stem->edge2->pos = pos + stem->width; |
| 723 | |
| 724 | stem->edge1->flags |= ah_edge_done; |
| 725 | stem->edge2->flags |= ah_edge_done; |
| 726 | } |
| 727 | } |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 728 | |
| 729 | #else /* AH_BRUTE_FORCE */ |
| 730 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 731 | /* optimize outline in a single direction */ |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 732 | static void |
| 733 | optim_compute( AH_Optimizer* optimizer ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 734 | { |
| 735 | int n, counter, counter2; |
| 736 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 737 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 738 | optimizer->num_configs = 0; |
| 739 | optimizer->tension_scale = 0x80000L; |
| 740 | optimizer->tension_threshold = 64; |
| 741 | |
| 742 | /* record initial configuration threshold */ |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 743 | optim_record_configuration( optimizer ); |
| 744 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 745 | counter = 0; |
| 746 | for ( counter2 = optimizer->num_stems*8; counter2 >= 0; counter2-- ) |
| 747 | { |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 748 | if ( counter == 0 ) |
| 749 | counter = 2 * optimizer->num_stems; |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 750 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 751 | if ( !optim_compute_stem_movements( optimizer ) ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 752 | break; |
| 753 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 754 | optim_record_configuration( optimizer ); |
| 755 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 756 | counter--; |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 757 | if ( counter == 0 ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 758 | optimizer->tension_scale /= 2; |
| 759 | } |
| 760 | |
| 761 | /* now, set the best stem positions */ |
| 762 | for ( n = 0; n < optimizer->num_stems; n++ ) |
| 763 | { |
| 764 | AH_Stem* stem = optimizer->stems + n; |
| 765 | FT_Pos pos = optimizer->configs[0].positions[n]; |
| 766 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 767 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 768 | stem->edge1->pos = pos; |
| 769 | stem->edge2->pos = pos + stem->width; |
| 770 | |
| 771 | stem->edge1->flags |= ah_edge_done; |
| 772 | stem->edge2->flags |= ah_edge_done; |
| 773 | } |
| 774 | } |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 775 | |
| 776 | #endif /* AH_BRUTE_FORCE */ |
| 777 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 778 | |
| 779 | /*************************************************************************/ |
| 780 | /*************************************************************************/ |
| 781 | /*************************************************************************/ |
| 782 | /**** ****/ |
| 783 | /**** HIGH-LEVEL OPTIMIZER API ****/ |
| 784 | /**** ****/ |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 785 | /*************************************************************************/ |
| 786 | /*************************************************************************/ |
| 787 | /*************************************************************************/ |
| 788 | |
| 789 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 790 | /* releases the optimization data */ |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 791 | void |
| 792 | AH_Optimizer_Done( AH_Optimizer* optimizer ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 793 | { |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 794 | if ( optimizer ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 795 | { |
| 796 | FT_Memory memory = optimizer->memory; |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 797 | |
| 798 | |
David Turner | e459d74 | 2002-03-22 13:52:37 +0000 | [diff] [blame^] | 799 | FT_FREE( optimizer->horz_stems ); |
| 800 | FT_FREE( optimizer->vert_stems ); |
| 801 | FT_FREE( optimizer->horz_springs ); |
| 802 | FT_FREE( optimizer->vert_springs ); |
| 803 | FT_FREE( optimizer->positions ); |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 804 | } |
| 805 | } |
| 806 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 807 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 808 | /* loads the outline into the optimizer */ |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 809 | int |
| 810 | AH_Optimizer_Init( AH_Optimizer* optimizer, |
| 811 | AH_Outline* outline, |
| 812 | FT_Memory memory ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 813 | { |
| 814 | FT_Error error; |
| 815 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 816 | |
David Turner | e459d74 | 2002-03-22 13:52:37 +0000 | [diff] [blame^] | 817 | FT_MEM_SET( optimizer, 0, sizeof ( *optimizer ) ); |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 818 | optimizer->outline = outline; |
| 819 | optimizer->memory = memory; |
| 820 | |
| 821 | LOG(( "initializing new optimizer\n" )); |
| 822 | /* compute stems and springs */ |
| 823 | error = optim_compute_stems ( optimizer ) || |
| 824 | optim_compute_springs( optimizer ); |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 825 | if ( error ) |
| 826 | goto Fail; |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 827 | |
| 828 | /* allocate stem positions history and configurations */ |
| 829 | { |
| 830 | int n, max_stems; |
| 831 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 832 | |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 833 | max_stems = optimizer->num_hstems; |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 834 | if ( max_stems < optimizer->num_vstems ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 835 | max_stems = optimizer->num_vstems; |
| 836 | |
David Turner | e459d74 | 2002-03-22 13:52:37 +0000 | [diff] [blame^] | 837 | if ( FT_NEW_ARRAY( optimizer->positions, max_stems * AH_MAX_CONFIGS ) ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 838 | goto Fail; |
| 839 | |
| 840 | optimizer->num_configs = 0; |
| 841 | for ( n = 0; n < AH_MAX_CONFIGS; n++ ) |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 842 | optimizer->configs[n].positions = optimizer->positions + |
| 843 | n * max_stems; |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 844 | } |
| 845 | |
| 846 | return error; |
| 847 | |
| 848 | Fail: |
| 849 | AH_Optimizer_Done( optimizer ); |
| 850 | return error; |
| 851 | } |
| 852 | |
| 853 | |
| 854 | /* compute optimal outline */ |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 855 | void |
| 856 | AH_Optimizer_Compute( AH_Optimizer* optimizer ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 857 | { |
| 858 | optimizer->num_stems = optimizer->num_hstems; |
| 859 | optimizer->stems = optimizer->horz_stems; |
| 860 | optimizer->num_springs = optimizer->num_hsprings; |
| 861 | optimizer->springs = optimizer->horz_springs; |
| 862 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 863 | if ( optimizer->num_springs > 0 ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 864 | { |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 865 | LOG(( "horizontal optimization ------------------------\n" )); |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 866 | optim_compute( optimizer ); |
| 867 | } |
| 868 | |
| 869 | optimizer->num_stems = optimizer->num_vstems; |
| 870 | optimizer->stems = optimizer->vert_stems; |
| 871 | optimizer->num_springs = optimizer->num_vsprings; |
| 872 | optimizer->springs = optimizer->vert_springs; |
| 873 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 874 | if ( optimizer->num_springs ) |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 875 | { |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 876 | LOG(( "vertical optimization --------------------------\n" )); |
David Turner | 3469d0d | 2000-07-19 20:02:14 +0000 | [diff] [blame] | 877 | optim_compute( optimizer ); |
| 878 | } |
| 879 | } |
| 880 | |
| 881 | |
Werner Lemberg | c3dd151 | 2000-07-26 14:11:15 +0000 | [diff] [blame] | 882 | /* END */ |