24 #include "allheaders.h"
25 #include "arrayaccess.h"
36 #include "config_auto.h"
40 ICOORD C_OUTLINE::step_coords[4] = {
56 : box(bot_left, top_right), start(startpt->pos), offsets(nullptr) {
66 steps = static_cast<uint8_t *>(calloc(step_mem(), 1));
69 for (stepindex = 0; stepindex < length; stepindex++) {
72 edgept = edgept->
next;
86 ):start (startpt), offsets(nullptr) {
99 steps = static_cast<uint8_t*>(calloc(step_mem(), 1));
101 lastdir = new_steps[length - 1];
103 for (stepindex = 0, srcindex = 0; srcindex < length;
104 stepindex++, srcindex++) {
105 new_box =
TBOX (pos, pos);
108 dir = new_steps[srcindex];
110 dirdiff = dir - prevdir;
111 pos +=
step (stepindex);
112 if ((dirdiff == 64 || dirdiff == -64) && stepindex > 0) {
114 prevdir = stepindex >= 0 ?
step_dir (stepindex) : lastdir;
122 if (dirdiff == 64 || dirdiff == -64) {
125 for (
int i = 0; i < stepindex; ++i)
129 while (stepindex > 1 && (dirdiff == 64 || dirdiff == -64));
130 stepcount = stepindex;
150 int16_t destindex = INT16_MAX;
154 stepcount = srcline->stepcount * 2;
155 if (stepcount == 0) {
162 steps = static_cast<uint8_t *>(calloc(step_mem(), 1));
164 for (
int iteration = 0; iteration < 2; ++iteration) {
165 DIR128 round1 = iteration == 0 ? 32 : 0;
166 DIR128 round2 = iteration != 0 ? 32 : 0;
167 pos = srcline->start;
169 prevpos.
rotate (rotation);
171 box =
TBOX (start, start);
173 for (stepindex = 0; stepindex < srcline->stepcount; stepindex++) {
174 pos += srcline->
step (stepindex);
176 destpos.
rotate (rotation);
178 while (destpos.
x () != prevpos.
x () || destpos.
y () != prevpos.
y ()) {
184 set_step(destindex++, dir + round1);
185 prevpos +=
step(destindex - 1);
189 -64 && dirdiff != 64)) {
190 set_step(destindex++, dir + round2);
191 prevpos +=
step(destindex - 1);
193 prevpos -=
step(destindex - 1);
195 prevpos -=
step(destindex - 1);
196 set_step(destindex - 1, dir + round2);
197 prevpos +=
step(destindex - 1);
202 prevpos +=
step(destindex - 1);
204 while (destindex >= 2 &&
208 prevpos -=
step(destindex - 1);
209 prevpos -=
step(destindex - 2);
213 new_box =
TBOX (destpos, destpos);
217 ASSERT_HOST (destpos.
x () == start.
x () && destpos.
y () == start.
y ());
219 while ((dirdiff == 64 || dirdiff == -64) && destindex > 1) {
222 for (
int i = 0; i < destindex; ++i)
230 stepcount = destindex;
232 for (stepindex = 0; stepindex < stepcount; stepindex++) {
233 destpos +=
step (stepindex);
235 ASSERT_HOST (destpos.
x () == start.
x () && destpos.
y () == start.
y ());
240 C_OUTLINE_IT ol_it(outlines);
246 ol_it.add_to_end(outline);
263 C_OUTLINE_IT it(const_cast<C_OUTLINE_LIST*>(&children));
268 for (stepindex = 0; stepindex < total_steps; stepindex++) {
270 next_step =
step (stepindex);
271 if (next_step.
x () < 0)
273 else if (next_step.
x () > 0)
277 for (it.mark_cycle_pt (); !it.cycled_list (); it.forward ())
278 total += it.data ()->area ();
293 C_OUTLINE_IT it(const_cast<C_OUTLINE_LIST*>(&children));
296 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward())
297 total_steps += it.data()->pathlength();
317 if (total_steps == 0)
320 for (stepindex = 0; stepindex < total_steps; stepindex++) {
322 next_step =
step (stepindex);
323 if (next_step.
x () < 0)
325 else if (next_step.
x () > 0)
341 bool first_was_max_x;
342 bool first_was_max_y;
343 bool looking_for_max_x;
344 bool looking_for_min_x;
345 bool looking_for_max_y;
346 bool looking_for_min_y;
350 int32_t max_x, min_x, max_y, min_y;
351 int32_t initial_x, initial_y;
359 max_x = min_x = pos.
x();
360 max_y = min_y = pos.
y();
361 looking_for_max_x =
true;
362 looking_for_min_x =
true;
363 looking_for_max_y =
true;
364 looking_for_min_y =
true;
365 first_was_max_x =
false;
366 first_was_max_y =
false;
369 for (stepindex = 0; stepindex < total_steps; stepindex++) {
371 next_step =
step(stepindex);
373 if (next_step.
x() < 0) {
374 if (looking_for_max_x && pos.
x() < min_x)
376 if (looking_for_min_x && max_x - pos.
x() > threshold) {
377 if (looking_for_max_x) {
379 first_was_max_x =
false;
382 looking_for_max_x =
true;
383 looking_for_min_x =
false;
387 else if (next_step.
x() > 0) {
388 if (looking_for_min_x && pos.
x() > max_x)
390 if (looking_for_max_x && pos.
x() - min_x > threshold) {
391 if (looking_for_min_x) {
393 first_was_max_x =
true;
396 looking_for_max_x =
false;
397 looking_for_min_x =
true;
401 else if (next_step.
y() < 0) {
402 if (looking_for_max_y && pos.
y() < min_y)
404 if (looking_for_min_y && max_y - pos.
y() > threshold) {
405 if (looking_for_max_y) {
407 first_was_max_y =
false;
410 looking_for_max_y =
true;
411 looking_for_min_y =
false;
416 if (looking_for_min_y && pos.
y() > max_y)
418 if (looking_for_max_y && pos.
y() - min_y > threshold) {
419 if (looking_for_min_y) {
421 first_was_max_y =
true;
424 looking_for_max_y =
false;
425 looking_for_min_y =
true;
431 if (first_was_max_x && looking_for_min_x) {
432 if (max_x - initial_x > threshold)
437 else if (!first_was_max_x && looking_for_max_x) {
438 if (initial_x - min_x > threshold)
443 if (first_was_max_y && looking_for_min_y) {
444 if (max_y - initial_y > threshold)
449 else if (!first_was_max_y && looking_for_max_y) {
450 if (initial_y - min_y > threshold)
475 return other.box.
contains(this->box);
478 for (stepindex = 0; stepindex < stepcount
480 pos +=
step (stepindex);
484 for (stepindex = 0; stepindex < other.stepcount
487 pos += other.
step (stepindex);
509 for (stepindex = 0; stepindex < stepcount; stepindex++) {
510 stepvec =
step (stepindex);
512 if (vec.
y () <= 0 && vec.
y () + stepvec.
y () > 0) {
513 cross = vec * stepvec;
519 else if (vec.
y () > 0 && vec.
y () + stepvec.
y () <= 0) {
520 cross = vec * stepvec;
548 for (stepindex = 0; stepindex < stepcount; stepindex++) {
550 dirdiff = dir - prevdir;
551 ASSERT_HOST (dirdiff == 0 || dirdiff == 32 || dirdiff == -32);
572 halfsteps = (stepcount + 1) / 2;
573 for (stepindex = 0; stepindex < halfsteps; stepindex++) {
574 farindex = stepcount - stepindex - 1;
577 set_step (farindex, stepdir + halfturn);
589 C_OUTLINE_IT it(&children);
594 for (it.mark_cycle_pt (); !it.cycled_list (); it.forward ())
595 it.data ()->move (vec);
605 if (stepcount == 0)
return true;
609 C_OUTLINE_IT child_it(const_cast<C_OUTLINE_LIST*>(&children));
610 for (child_it.mark_cycle_pt(); !child_it.cycled_list(); child_it.forward()) {
612 if (
child->outer_area() * parent_area > 0 || !
child->IsLegallyNested())
628 if (box.
width() < min_size || box.
height() < min_size) {
630 delete it->extract();
631 }
else if (!children.empty()) {
633 C_OUTLINE_IT child_it(&children);
634 for (child_it.mark_cycle_pt(); !child_it.cycled_list();
635 child_it.forward()) {
637 child->RemoveSmallRecursive(min_size, &child_it);
651 static void ComputeGradient(
const l_uint32* data,
int wpl,
652 int x,
int y,
int width,
int height,
654 const l_uint32* line = data + y * wpl;
655 int pix_x_y = x < width && y < height ? GET_DATA_BYTE(line, x) : 255;
656 int pix_x_prevy = x < width && y > 0 ? GET_DATA_BYTE(line - wpl, x) : 255;
657 int pix_prevx_prevy = x > 0 && y > 0 ? GET_DATA_BYTE(line - wpl, x - 1) : 255;
658 int pix_prevx_y = x > 0 && y < height ? GET_DATA_BYTE(line, x - 1) : 255;
659 gradient->
set_x(pix_x_y + pix_x_prevy - (pix_prevx_y + pix_prevx_prevy));
660 gradient->
set_y(pix_x_prevy + pix_prevx_prevy - (pix_x_y + pix_prevx_y));
668 static bool EvaluateVerticalDiff(
const l_uint32* data,
int wpl,
int diff_sign,
669 int x,
int y,
int height,
670 int* best_diff,
int* best_sum,
int* best_y) {
671 if (y <= 0 || y >= height)
673 const l_uint32* line = data + y * wpl;
674 int pixel1 = GET_DATA_BYTE(line - wpl, x);
675 int pixel2 = GET_DATA_BYTE(line, x);
676 int diff = (pixel2 - pixel1) * diff_sign;
677 if (diff > *best_diff) {
679 *best_sum = pixel1 + pixel2;
690 static bool EvaluateHorizontalDiff(
const l_uint32* line,
int diff_sign,
692 int* best_diff,
int* best_sum,
int* best_x) {
693 if (x <= 0 || x >= width)
695 int pixel1 = GET_DATA_BYTE(line, x - 1);
696 int pixel2 = GET_DATA_BYTE(line, x);
697 int diff = (pixel2 - pixel1) * diff_sign;
698 if (diff > *best_diff) {
700 *best_sum = pixel1 + pixel2;
722 if (pixGetDepth(pix) != 8)
return;
723 const l_uint32* data = pixGetData(pix);
724 int wpl = pixGetWpl(pix);
725 int width = pixGetWidth(pix);
726 int height = pixGetHeight(pix);
732 ComputeGradient(data, wpl, pos.
x(), height - pos.
y(), width, height,
734 for (
int s = 0; s < stepcount; ++s) {
740 ComputeGradient(data, wpl, pos.
x(), height - pos.
y(), width, height,
743 ICOORD gradient = prev_gradient + next_gradient;
750 if (pt1.
y == pt2.
y && abs(gradient.y()) * 2 >= abs(gradient.x())) {
752 int diff_sign = (pt1.
x > pt2.
x) == negative ? 1 : -1;
753 int x = std::min(pt1.
x, pt2.
x);
754 int y = height - pt1.
y;
757 EvaluateVerticalDiff(data, wpl, diff_sign, x, y, height,
758 &best_diff, &best_sum, &best_y);
763 }
while (EvaluateVerticalDiff(data, wpl, diff_sign, x, test_y, height,
764 &best_diff, &best_sum, &best_y));
768 }
while (EvaluateVerticalDiff(data, wpl, diff_sign, x, test_y, height,
769 &best_diff, &best_sum, &best_y));
770 offset = diff_sign * (best_sum / 2 - threshold) +
771 (y - best_y) * best_diff;
772 }
else if (pt1.
x == pt2.
x && abs(gradient.x()) * 2 >= abs(gradient.y())) {
774 int diff_sign = (pt1.
y > pt2.
y) == negative ? 1 : -1;
776 int y = height - std::max(pt1.
y, pt2.
y);
777 const l_uint32* line = pixGetData(pix) + y * wpl;
780 EvaluateHorizontalDiff(line, diff_sign, x, width,
781 &best_diff, &best_sum, &best_x);
786 }
while (EvaluateHorizontalDiff(line, diff_sign, test_x, width,
787 &best_diff, &best_sum, &best_x));
791 }
while (EvaluateHorizontalDiff(line, diff_sign, test_x, width,
792 &best_diff, &best_sum, &best_x));
793 offset = diff_sign * (threshold - best_sum / 2) +
794 (best_x - x) * best_diff;
797 ClipToRange<int>(offset, -INT8_MAX, INT8_MAX);
798 offsets[s].
pixel_diff = ClipToRange<int>(best_diff, 0, UINT8_MAX);
799 if (negative) gradient = -gradient;
804 prev_gradient = next_gradient;
845 memset(dir_counts, 0,
sizeof(dir_counts));
846 memset(pos_totals, 0,
sizeof(pos_totals));
851 tail_pos -=
step(stepcount - 1);
852 tail_pos -=
step(stepcount - 2);
855 ICOORD head_pos = tail_pos;
857 for (
int s = -2; s < 2; ++s) {
858 increment_step(s, 1, &head_pos, dir_counts, pos_totals);
860 for (
int s = 0; s < stepcount; pos +=
step(s++)) {
862 increment_step(s + 2, 1, &head_pos, dir_counts, pos_totals);
869 if (dir_counts[dir_index] >= 2 || (dir_counts[dir_index] == 1 &&
870 dir_counts[
Modulo(dir_index - 1, 4)] == 2 &&
871 dir_counts[
Modulo(dir_index + 1, 4)] == 2)) {
873 best_diff = dir_counts[dir_index];
874 int edge_pos = step_vec.
x() == 0 ? pos.
x() : pos.
y();
878 offset = pos_totals[dir_index] - best_diff * edge_pos;
881 ClipToRange<int>(offset, -INT8_MAX, INT8_MAX);
882 offsets[s].
pixel_diff = ClipToRange<int>(best_diff, 0, UINT8_MAX);
884 FCOORD direction(head_pos.
x() - tail_pos.
x(), head_pos.
y() - tail_pos.
y());
885 offsets[s].
direction = direction.to_direction();
886 increment_step(s - 2, -1, &tail_pos, dir_counts, pos_totals);
896 for (
int stepindex = 0; stepindex < stepcount; ++stepindex) {
898 if (next_step.
y() < 0) {
899 pixRasterop(pix, 0, top - pos.
y(), pos.
x() - left, 1,
900 PIX_NOT(PIX_DST),
nullptr, 0, 0);
901 }
else if (next_step.
y() > 0) {
902 pixRasterop(pix, 0, top - pos.
y() - 1, pos.
x() - left, 1,
903 PIX_NOT(PIX_DST),
nullptr, 0, 0);
918 for (
int stepindex = 0; stepindex < stepcount; ++stepindex) {
920 if (next_step.
y() < 0) {
921 pixSetPixel(pix, pos.
x() - left, top - pos.
y(), 1);
922 }
else if (next_step.
y() > 0) {
923 pixSetPixel(pix, pos.
x() - left - 1, top - pos.
y() - 1, 1);
924 }
else if (next_step.
x() < 0) {
925 pixSetPixel(pix, pos.
x() - left - 1, top - pos.
y(), 1);
926 }
else if (next_step.
x() > 0) {
927 pixSetPixel(pix, pos.
x() - left, top - pos.
y() - 1, 1);
941 #ifndef GRAPHICS_DISABLED
949 if (stepcount == 0) {
956 while (stepindex < stepcount) {
957 pos +=
step(stepindex);
961 while (stepindex < stepcount &&
963 pos +=
step(stepindex);
977 if (stepcount == 0) {
988 for (
int s = 0; s < stepcount; pos +=
step(s++)) {
990 if (edge_weight == 0) {
1012 start = source.start;
1014 stepcount = source.stepcount;
1015 steps = static_cast<uint8_t *>(malloc(step_mem()));
1016 memmove (steps, source.steps, step_mem());
1017 if (!children.empty ())
1019 children.deep_copy(&source.children, &
deep_copy);
1021 if (source.offsets !=
nullptr) {
1023 memcpy(offsets, source.offsets, stepcount *
sizeof(*offsets));
1036 void C_OUTLINE::increment_step(
int s,
int increment,
ICOORD* pos,
1037 int* dir_counts,
int* pos_totals)
const {
1038 int step_index =
Modulo(s, stepcount);
1040 dir_counts[dir_index] += increment;
1042 if (step_vec.
x() == 0)
1043 pos_totals[dir_index] += pos->
x() * increment;
1045 pos_totals[dir_index] += pos->
y() * increment;
1050 return step_coords[chaindir % 4];