00001
00020
00021
00022
00023 #include "findseam.h"
00024 #include "gradechop.h"
00025 #include "olutil.h"
00026 #include "plotedges.h"
00027 #include "outlines.h"
00028 #include "freelist.h"
00029 #include "seam.h"
00030
00031
00032
00033
00035 #define SPLIT_CLOSENESS 20
00036
00037 #define MAX_NUM_SEAMS 150
00038
00039 #define MAX_OLD_SEAMS 150
00040
00041 #define NO_FULL_PRIORITY -1
00042
00043 #define GOOD_PARTIAL_PRIORITY good_split
00044 #define BAD_PRIORITY 9999.0
00045
00046
00047
00048
00054 #define add_seam_to_queue(seams,seam,priority) \
00055 if (seam)\
00056 {\
00057 if (HeapFull(seams))\
00058 junk_worst_seam(seams,seam,priority);\
00059 else\
00060 HeapPush (seams, priority, (char*) seam);\
00061 }
00062
00066 #define best_seam_priority(seam_queue) \
00067 (HeapEmpty (seam_queue) ? \
00068 NO_FULL_PRIORITY : \
00069 ((SEAM*) seam_queue_element(seam_queue, 0))->priority)
00070
00074 #define create_seam_queue(seam_queue) \
00075 (seam_queue = MakeHeap (MAX_NUM_SEAMS))
00076
00080 #define create_seam_pile(seam_pile) \
00081 (seam_pile = array_new (MAX_OLD_SEAMS))
00082
00086 #define delete_seam_queue(seam_queue) \
00087 (FreeHeapData (seam_queue, delete_seam), \
00088 seam_queue = NULL) \
00089
00090
00097 #define pop_next_seam(seams,seam,priority) \
00098 (HeapPop (seams,&priority,&seam) == OK) \
00099
00100
00104 #define seam_queue_element(seam_queue,index) \
00105 ((index < SizeOfHeap (seam_queue)) ? \
00106 HeapDataFor (seam_queue, index) : \
00107 NULL) \
00108
00109
00110
00111
00112
00113
00117 void junk_worst_seam(SEAM_QUEUE seams, SEAM *new_seam, float new_priority) {
00118 SEAM *seam;
00119 float priority;
00120
00121 HeapPopWorst(seams, &priority, &seam);
00122 if (priority > new_priority) {
00123 delete_seam(seam);
00124 HeapPush (seams, new_priority, (char *) new_seam);
00125 }
00126 else {
00127 delete_seam(new_seam);
00128 HeapPush (seams, priority, (char *) seam);
00129 }
00130 }
00131
00132
00133
00164 void choose_best_seam(SEAM_QUEUE seam_queue,
00165 SEAM_PILE *seam_pile,
00166 SPLIT *split,
00167 PRIORITY priority,
00168 SEAM **seam_result,
00169 TBLOB *blob) {
00170 SEAM *seam;
00171 TPOINT topleft;
00172 TPOINT botright;
00173 char str[80];
00174 float my_priority;
00175
00176 my_priority = priority;
00177 if (split != NULL) {
00178 seam = new_seam (my_priority,
00179 (split->point1->pos.x + split->point1->pos.x) / 2,
00180 split, NULL, NULL);
00181 if (chop_debug > 1)
00182 print_seam ("Partial priority ", seam);
00183 add_seam_to_queue (seam_queue, seam, (float) my_priority);
00184
00185 if (my_priority > GOOD_PARTIAL_PRIORITY)
00186 return;
00187 }
00188
00189 blob_bounding_box(blob, &topleft, &botright);
00190
00191 while (pop_next_seam (seam_queue, seam, my_priority)) {
00192
00193 my_priority = seam_priority (seam, topleft.x, botright.x);
00194 if (chop_debug) {
00195 sprintf (str, "Full my_priority %0.0f, ", my_priority);
00196 print_seam(str, seam);
00197 }
00198
00199 if ((*seam_result == NULL ||
00200 (*seam_result)->priority > my_priority) && my_priority < ok_split) {
00201
00202 if (constrained_split (seam->split1, blob)) {
00203 delete_seam(*seam_result);
00204 clone_seam(*seam_result, seam);
00205 (*seam_result)->priority = my_priority;
00206 }
00207 else {
00208 delete_seam(seam);
00209 seam = NULL;
00210 my_priority = BAD_PRIORITY;
00211 }
00212 }
00213
00214 if (my_priority < good_split) {
00215 if (seam)
00216 delete_seam(seam);
00217 return;
00218 }
00219
00220 if (seam) {
00221
00222 if (array_count (*seam_pile) < MAX_NUM_SEAMS
00223 ) {
00224 combine_seam(seam_queue, *seam_pile, seam);
00225 *seam_pile = array_push (*seam_pile, seam);
00226 }
00227 else
00228 delete_seam(seam);
00229 }
00230
00231 my_priority = best_seam_priority (seam_queue);
00232 if ((my_priority > ok_split) ||
00233 (my_priority > GOOD_PARTIAL_PRIORITY && split))
00234 return;
00235 }
00236 }
00237
00238
00239
00246 void combine_seam(SEAM_QUEUE seam_queue, SEAM_PILE seam_pile, SEAM *seam) {
00247 register INT16 x;
00248 register INT16 dist;
00249 INT16 bottom1, top1;
00250 INT16 bottom2, top2;
00251
00252 SEAM *new_one;
00253 SEAM *this_one;
00254
00255 bottom1 = seam->split1->point1->pos.y;
00256 if (seam->split1->point2->pos.y >= bottom1)
00257 top1 = seam->split1->point2->pos.y;
00258 else {
00259 top1 = bottom1;
00260 bottom1 = seam->split1->point2->pos.y;
00261 }
00262 if (seam->split2 != NULL) {
00263 bottom2 = seam->split2->point1->pos.y;
00264 if (seam->split2->point2->pos.y >= bottom2)
00265 top2 = seam->split2->point2->pos.y;
00266 else {
00267 top2 = bottom2;
00268 bottom2 = seam->split2->point2->pos.y;
00269 }
00270 }
00271 else {
00272 bottom2 = bottom1;
00273 top2 = top1;
00274 }
00275 array_loop(seam_pile, x) {
00276 this_one = (SEAM *) array_value (seam_pile, x);
00277 dist = seam->location - this_one->location;
00278 if (-SPLIT_CLOSENESS < dist &&
00279 dist < SPLIT_CLOSENESS &&
00280 seam->priority + this_one->priority < ok_split) {
00281 if (
00284 (this_one->split1->point1->pos.y >= top1
00285 && this_one->split1->point2->pos.y >= top1
00286 || this_one->split1->point1->pos.y <= bottom1
00287 && this_one->split1->point2->pos.y <= bottom1)
00288 && (this_one->split1->point1->pos.y >= top2
00289 && this_one->split1->point2->pos.y >= top2
00290 || this_one->split1->point1->pos.y <= bottom2
00291 && this_one->split1->point2->pos.y <= bottom2)
00292 && (this_one->split2 == NULL
00293 || (this_one->split2->point1->pos.y >= top1
00294 && this_one->split2->point2->pos.y >= top1
00295 || this_one->split2->point1->pos.y <= bottom1
00296 && this_one->split2->point2->pos.y <= bottom1)
00297 && (this_one->split2->point1->pos.y >= top2
00298 && this_one->split2->point2->pos.y >= top2
00299 || this_one->split2->point1->pos.y <= bottom2
00300 && this_one->split2->point2->pos.y <= bottom2))) {
00301 new_one = join_two_seams (seam, this_one);
00302 if (chop_debug > 1)
00303 print_seam ("Combo priority ", new_one);
00304 add_seam_to_queue (seam_queue, new_one, new_one->priority);
00305 }
00306 }
00307 }
00308 }
00309
00310
00311
00318 INT16 constrained_split(SPLIT *split, TBLOB *blob) {
00319 TESSLINE *outline;
00320
00321 if (is_little_chunk (split->point1, split->point2))
00322 return (FALSE);
00323
00324 for (outline = blob->outlines; outline; outline = outline->next) {
00325 if (split_bounds_overlap (split, outline) &&
00326 crosses_outline (split->point1, split->point2, outline->loop)) {
00327 return (FALSE);
00328 }
00329 }
00330 return (TRUE);
00331 }
00332
00333
00338 void delete_seam_pile(SEAM_PILE seam_pile) {
00339 INT16 x;
00340
00341 array_loop(seam_pile, x) {
00342 delete_seam ((SEAM *) array_value (seam_pile, x));
00343 }
00344 array_free(seam_pile);
00345 }
00346
00347
00348
00354 SEAM *pick_good_seam(TBLOB *blob) {
00355 SEAM_QUEUE seam_queue;
00356 SEAM_PILE seam_pile;
00357 POINT_GROUP point_heap;
00358 PRIORITY priority;
00359 EDGEPT *edge;
00360 EDGEPT *points[MAX_NUM_POINTS];
00361 SEAM *seam = NULL;
00362 TESSLINE *outline;
00363 INT16 num_points = 0;
00364
00365 #ifndef GRAPHICS_DISABLED
00366 if (chop_debug)
00367 display_splits = TRUE;
00368
00369 draw_blob_edges(blob);
00370 #endif
00371
00372 point_heap = MakeHeap (MAX_NUM_POINTS);
00373 for (outline = blob->outlines; outline; outline = outline->next)
00374 prioritize_points(outline, point_heap);
00375
00376 while (HeapPop (point_heap, &priority, &edge) == OK) {
00377 if (num_points < MAX_NUM_POINTS)
00378 points[num_points++] = (EDGEPT *) edge;
00379 }
00380 FreeHeap(point_heap);
00381
00382
00383 create_seam_pile(seam_pile);
00384 create_seam_queue(seam_queue);
00385
00386 try_point_pairs(points, num_points, seam_queue, &seam_pile, &seam, blob);
00387
00388 try_vertical_splits(points, num_points, seam_queue, &seam_pile, &seam, blob);
00389
00390 if (seam == NULL) {
00391 choose_best_seam(seam_queue, &seam_pile, NULL, BAD_PRIORITY, &seam, blob);
00392 }
00393 else if (seam->priority > good_split) {
00394 choose_best_seam (seam_queue, &seam_pile, NULL, seam->priority,
00395 &seam, blob);
00396 }
00397 delete_seam_queue(seam_queue);
00398 delete_seam_pile(seam_pile);
00399
00400 if (seam) {
00401 if (seam->priority > ok_split) {
00402 delete_seam(seam);
00403 seam = NULL;
00404 }
00405 #ifndef GRAPHICS_DISABLED
00406 else if (display_splits) {
00407 if (seam->split1)
00408 mark_split (seam->split1);
00409 if (seam->split2)
00410 mark_split (seam->split2);
00411 if (seam->split3)
00412 mark_split (seam->split3);
00413 if (chop_debug > 1) {
00414 update_edge_window();
00415 edge_window_wait();
00416 }
00417 }
00418 #endif
00419 }
00420
00421 if (chop_debug)
00422 display_splits = FALSE;
00423
00424 return (seam);
00425 }
00426
00427
00428
00432 PRIORITY seam_priority(SEAM *seam, INT16 xmin, INT16 xmax) {
00433 PRIORITY priority;
00434
00435 if (seam->split1 == NULL)
00436 priority = 0;
00437
00438 else if (seam->split2 == NULL) {
00439 priority = (seam->priority +
00440 full_split_priority (seam->split1, xmin, xmax));
00441 }
00442
00443 else if (seam->split3 == NULL) {
00444 split_outline (seam->split2->point1, seam->split2->point2);
00445 priority = (seam->priority +
00446 full_split_priority (seam->split1, xmin, xmax));
00447 unsplit_outlines (seam->split2->point1, seam->split2->point2);
00448 }
00449
00450 else {
00451 split_outline (seam->split2->point1, seam->split2->point2);
00452 split_outline (seam->split3->point1, seam->split3->point2);
00453 priority = (seam->priority +
00454 full_split_priority (seam->split1, xmin, xmax));
00455 unsplit_outlines (seam->split3->point1, seam->split3->point2);
00456 unsplit_outlines (seam->split2->point1, seam->split2->point2);
00457 }
00458
00459 return (priority);
00460 }
00461
00462
00463
00471 void
00472 try_point_pairs (EDGEPT * points[MAX_NUM_POINTS],
00473 INT16 num_points,
00474 SEAM_QUEUE seam_queue,
00475 SEAM_PILE * seam_pile, SEAM ** seam, TBLOB * blob) {
00476 INT16 x;
00477 INT16 y;
00478 SPLIT *split;
00479 PRIORITY priority;
00480
00481 for (x = 0; x < num_points; x++) {
00482 for (y = x + 1; y < num_points; y++) {
00483
00484 if (points[y] &&
00485 weighted_edgept_dist (points[x], points[y],
00486 x_y_weight) < split_length &&
00487 points[x] != points[y]->next &&
00488 points[y] != points[x]->next &&
00489 !is_exterior_point (points[x], points[y]) &&
00490 !is_exterior_point (points[y], points[x])) {
00491
00492 split = new_split (points[x], points[y]);
00493 priority = partial_split_priority (split);
00494
00495 choose_best_seam(seam_queue, seam_pile, split, priority, seam, blob);
00496
00497 if (*seam && (*seam)->priority < good_split)
00498 return;
00499 }
00500 }
00501 }
00502
00503 }
00504
00505
00506
00513 void
00514 try_vertical_splits (EDGEPT * points[MAX_NUM_POINTS],
00515 INT16 num_points,
00516 SEAM_QUEUE seam_queue,
00517 SEAM_PILE * seam_pile, SEAM ** seam, TBLOB * blob) {
00518 EDGEPT *vertical_point = NULL;
00519 SPLIT *split;
00520 INT16 x;
00521 PRIORITY priority;
00522 TESSLINE *outline;
00523
00524 for (x = 0; x < num_points; x++) {
00525
00526 if (*seam != NULL && (*seam)->priority < good_split)
00527 return;
00528
00529 vertical_point = NULL;
00530 for (outline = blob->outlines; outline; outline = outline->next) {
00531 vertical_projection_point (points[x],
00532 outline->loop, &vertical_point);
00533 }
00534
00535 if (vertical_point &&
00536 points[x] != vertical_point->next &&
00537 vertical_point != points[x]->next &&
00538 weighted_edgept_dist (points[x], vertical_point,
00539 x_y_weight) < split_length) {
00540
00541 split = new_split (points[x], vertical_point);
00542 priority = partial_split_priority (split);
00543
00544 choose_best_seam(seam_queue, seam_pile, split, priority, seam, blob);
00545 }
00546 }
00547 }