Path.cpp 5.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186
  1. /*
  2. * Copyright (c) 2018-2020, Andreas Kling <kling@serenityos.org>
  3. * All rights reserved.
  4. *
  5. * Redistribution and use in source and binary forms, with or without
  6. * modification, are permitted provided that the following conditions are met:
  7. *
  8. * 1. Redistributions of source code must retain the above copyright notice, this
  9. * list of conditions and the following disclaimer.
  10. *
  11. * 2. Redistributions in binary form must reproduce the above copyright notice,
  12. * this list of conditions and the following disclaimer in the documentation
  13. * and/or other materials provided with the distribution.
  14. *
  15. * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  16. * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  17. * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  18. * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  19. * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  20. * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  21. * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  22. * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  23. * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  24. * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25. */
  26. #include <AK/Function.h>
  27. #include <AK/HashFunctions.h>
  28. #include <AK/HashTable.h>
  29. #include <AK/QuickSort.h>
  30. #include <AK/StringBuilder.h>
  31. #include <LibGfx/Painter.h>
  32. #include <LibGfx/Path.h>
  33. #include <math.h>
  34. namespace Gfx {
  35. void Path::close()
  36. {
  37. if (m_segments.size() <= 1)
  38. return;
  39. invalidate_split_lines();
  40. auto& last_point = m_segments.last().point;
  41. for (ssize_t i = m_segments.size() - 1; i >= 0; --i) {
  42. auto& segment = m_segments[i];
  43. if (segment.type == Segment::Type::MoveTo) {
  44. if (last_point == segment.point)
  45. return;
  46. m_segments.append({ Segment::Type::LineTo, segment.point });
  47. return;
  48. }
  49. }
  50. }
  51. void Path::close_all_subpaths()
  52. {
  53. if (m_segments.size() <= 1)
  54. return;
  55. invalidate_split_lines();
  56. Optional<FloatPoint> cursor, start_of_subpath;
  57. bool is_first_point_in_subpath { false };
  58. for (auto& segment : m_segments) {
  59. switch (segment.type) {
  60. case Segment::Type::MoveTo: {
  61. if (cursor.has_value() && !is_first_point_in_subpath) {
  62. // This is a move from a subpath to another
  63. // connect the two ends of this subpath before
  64. // moving on to the next one
  65. ASSERT(start_of_subpath.has_value());
  66. m_segments.append({ Segment::Type::MoveTo, cursor.value() });
  67. m_segments.append({ Segment::Type::LineTo, start_of_subpath.value() });
  68. }
  69. is_first_point_in_subpath = true;
  70. cursor = segment.point;
  71. break;
  72. }
  73. case Segment::Type::LineTo:
  74. case Segment::Type::QuadraticBezierCurveTo:
  75. if (is_first_point_in_subpath) {
  76. start_of_subpath = cursor;
  77. is_first_point_in_subpath = false;
  78. }
  79. cursor = segment.point;
  80. break;
  81. case Segment::Type::Invalid:
  82. ASSERT_NOT_REACHED();
  83. break;
  84. }
  85. }
  86. }
  87. String Path::to_string() const
  88. {
  89. StringBuilder builder;
  90. builder.append("Path { ");
  91. for (auto& segment : m_segments) {
  92. switch (segment.type) {
  93. case Segment::Type::MoveTo:
  94. builder.append("MoveTo");
  95. break;
  96. case Segment::Type::LineTo:
  97. builder.append("LineTo");
  98. break;
  99. case Segment::Type::QuadraticBezierCurveTo:
  100. builder.append("QuadraticBezierCurveTo");
  101. break;
  102. case Segment::Type::Invalid:
  103. builder.append("Invalid");
  104. break;
  105. }
  106. builder.append('(');
  107. builder.append(segment.point.to_string());
  108. if (segment.through.has_value()) {
  109. builder.append(", ");
  110. builder.append(segment.through.value().to_string());
  111. }
  112. builder.append(')');
  113. builder.append(' ');
  114. }
  115. builder.append("}");
  116. return builder.to_string();
  117. }
  118. void Path::segmentize_path()
  119. {
  120. Vector<LineSegment> segments;
  121. auto add_line = [&](const auto& p0, const auto& p1) {
  122. float ymax = p0.y(), ymin = p1.y(), x_of_ymin = p1.x(), x_of_ymax = p0.x();
  123. auto slope = p0.x() == p1.x() ? 0 : ((float)(p0.y() - p1.y())) / ((float)(p0.x() - p1.x()));
  124. if (p0.y() < p1.y()) {
  125. ymin = ymax;
  126. ymax = p1.y();
  127. x_of_ymax = x_of_ymin;
  128. x_of_ymin = p0.x();
  129. }
  130. segments.append({ FloatPoint(p0.x(), p0.y()),
  131. FloatPoint(p1.x(), p1.y()),
  132. slope == 0 ? 0 : 1 / slope,
  133. x_of_ymin,
  134. ymax, ymin, x_of_ymax });
  135. };
  136. FloatPoint cursor { 0, 0 };
  137. for (auto& segment : m_segments) {
  138. switch (segment.type) {
  139. case Segment::Type::MoveTo:
  140. cursor = segment.point;
  141. break;
  142. case Segment::Type::LineTo: {
  143. add_line(cursor, segment.point);
  144. cursor = segment.point;
  145. break;
  146. }
  147. case Segment::Type::QuadraticBezierCurveTo: {
  148. auto& control = segment.through.value();
  149. Painter::for_each_line_segment_on_bezier_curve(control, cursor, segment.point, [&](const FloatPoint& p0, const FloatPoint& p1) {
  150. add_line(p0, p1);
  151. });
  152. cursor = segment.point;
  153. break;
  154. }
  155. case Segment::Type::Invalid:
  156. ASSERT_NOT_REACHED();
  157. break;
  158. }
  159. }
  160. // sort segments by ymax
  161. quick_sort(segments, [](const auto& line0, const auto& line1) {
  162. return line1.maximum_y < line0.maximum_y;
  163. });
  164. m_split_lines = move(segments);
  165. }
  166. }