1 /** Copyright (C) 2016 Ultimaker - Released under terms of the AGPLv3 License */
2 #include "wallOverlap.h"
3
4 #include <cmath> // isfinite
5 #include <sstream>
6
7 #include "utils/AABB.h" // for debug output svg html
8 #include "utils/SVG.h"
9
10 namespace cura
11 {
12
WallOverlapComputation(Polygons & polygons,const coord_t line_width)13 WallOverlapComputation::WallOverlapComputation(Polygons& polygons, const coord_t line_width)
14 : overlap_linker(polygons, line_width)
15 , line_width(line_width)
16 {
17
18 }
19
20
getFlow(const Point & from,const Point & to)21 Ratio WallOverlapComputation::getFlow(const Point& from, const Point& to)
22 {
23 using Point2LinkIt = PolygonProximityLinker::Point2Link::iterator;
24
25 if (!overlap_linker.isLinked(from))
26 { // [from] is not linked
27 return 1;
28 }
29 const std::pair<Point2LinkIt, Point2LinkIt> to_links = overlap_linker.getLinks(to);
30 if (to_links.first == to_links.second)
31 { // [to] is not linked
32 return 1;
33 }
34
35 coord_t overlap_area = 0;
36 // note that we don't need to loop over all from_links, because they are handled in the previous getFlow(.) call (or in the very last)
37 for (Point2LinkIt to_link_it = to_links.first; to_link_it != to_links.second; ++to_link_it)
38 {
39 const ProximityPointLink& to_link = to_link_it->second;
40 ListPolyIt to_it = to_link.a;
41 ListPolyIt to_other_it = to_link.b;
42 if (to_link.a.p() != to)
43 {
44 assert(to_link.b.p() == to && "Either part of the link should be the point in the link!");
45 std::swap(to_it, to_other_it);
46 }
47 ListPolyIt from_it = to_it.prev();
48
49 ListPolyIt to_other_next_it = to_other_it.next(); // move towards [from]; the lines on the other side move in the other direction
50 // to from
51 // o<--o<--T<--F
52 // | : :
53 // v : :
54 // o-->o-->o-->o
55 // , ,
56 // ; to_other_next
57 // to other
58
59 bool are_in_same_general_direction = dot(from - to, to_other_it.p() - to_other_next_it.p()) > 0;
60 // handle multiple points linked to [to]
61 // o<<<T<<<F
62 // / |
63 // / |
64 // o>>>o>>>o
65 // , ,
66 // ; to other next
67 // to other
68 if (!are_in_same_general_direction)
69 {
70 overlap_area = std::max(overlap_area, handlePotentialOverlap(to_it, to_it, to_link, to_other_next_it, to_other_it));
71 }
72
73 // handle multiple points linked to [to_other]
74 // o<<<T<<<F
75 // | /
76 // | /
77 // o>>>o>>>o
78 bool all_are_in_same_general_direction = are_in_same_general_direction && dot(from - to, to_other_it.prev().p() - to_other_it.p()) > 0;
79 if (!all_are_in_same_general_direction)
80 {
81 overlap_area = std::max(overlap_area, handlePotentialOverlap(from_it, to_it, to_link, to_other_it, to_other_it));
82 }
83
84 // handle normal case where the segment from-to overlaps with another segment
85 // o<<<T<<<F
86 // | |
87 // | |
88 // o>>>o>>>o
89 // , ,
90 // ; to other next
91 // to other
92 if (!are_in_same_general_direction)
93 {
94 overlap_area = std::max(overlap_area, handlePotentialOverlap(from_it, to_it, to_link, to_other_next_it, to_other_it));
95 }
96 }
97
98 coord_t normal_area = vSize(from - to) * line_width;
99 Ratio ratio = Ratio(normal_area - overlap_area) / normal_area;
100 // clamp the ratio because overlap compensation might be faulty because
101 // WallOverlapComputation::getApproxOverlapArea only gives roughly accurate results
102 return std::min(1.0_r, std::max(0.0_r, ratio));
103 }
104
handlePotentialOverlap(const ListPolyIt from_it,const ListPolyIt to_it,const ProximityPointLink & to_link,const ListPolyIt from_other_it,const ListPolyIt to_other_it)105 coord_t WallOverlapComputation::handlePotentialOverlap(const ListPolyIt from_it, const ListPolyIt to_it, const ProximityPointLink& to_link, const ListPolyIt from_other_it, const ListPolyIt to_other_it)
106 {
107 if (from_it == to_other_it && from_it == from_other_it)
108 { // don't compute overlap with a line and itself
109 return 0;
110 }
111 const ProximityPointLink* from_link = overlap_linker.getLink(from_it, from_other_it);
112 if (!from_link)
113 {
114 return 0;
115 }
116 if (!getIsPassed(to_link, *from_link))
117 { // check whether the segment is already passed
118 setIsPassed(to_link, *from_link);
119 return 0;
120 }
121 return getApproxOverlapArea(from_it.p(), to_it.p(), to_link.dist, to_other_it.p(), from_other_it.p(), from_link->dist);
122 }
123
getApproxOverlapArea(const Point from,const Point to,const coord_t to_dist,const Point other_from,const Point other_to,const coord_t from_dist)124 coord_t WallOverlapComputation::getApproxOverlapArea(const Point from, const Point to, const coord_t to_dist, const Point other_from, const Point other_to, const coord_t from_dist)
125 {
126 const coord_t overlap_width_2 = line_width * 2 - from_dist - to_dist; //Twice the width of the overlap area, perpendicular to the lines.
127
128 // check whether the line segment overlaps with the point if one of the line segments is just a point
129 if (from == to)
130 {
131 if (LinearAlg2D::pointIsProjectedBeyondLine(from, other_from, other_to) != 0)
132 {
133 return 0;
134 }
135 const coord_t overlap_length_2 = vSize(other_to - other_from); //Twice the length of the overlap area, alongside the lines.
136 return overlap_length_2 * overlap_width_2 / 4; //Area = width * height.
137 }
138 if (other_from == other_to)
139 {
140 if (LinearAlg2D::pointIsProjectedBeyondLine(other_from, from, to) != 0)
141 {
142 return 0;
143 }
144 const coord_t overlap_length_2 = vSize(from - to); //Twice the length of the overlap area, alongside the lines.
145 return overlap_length_2 * overlap_width_2 / 4; //Area = width * height.
146 }
147
148 short from_rel = LinearAlg2D::pointIsProjectedBeyondLine(from, other_from, other_to);
149 short to_rel = LinearAlg2D::pointIsProjectedBeyondLine(to, other_from, other_to);
150 short other_from_rel = LinearAlg2D::pointIsProjectedBeyondLine(other_from, from, to);
151 short other_to_rel = LinearAlg2D::pointIsProjectedBeyondLine(other_to, from, to);
152 if (from_rel != 0 && to_rel == from_rel && other_from_rel != 0 && other_to_rel == other_from_rel)
153 {
154 // both segments project fully beyond or before each other
155 // for example: or:
156 // O<------O . O------>O
157 // : : \_
158 // ' O------->O O------>O
159 return 0;
160 }
161
162 if (from_rel != 0 && from_rel == other_from_rel && to_rel == 0 && other_to_rel == 0)
163 {
164 // only ends of line segments overlap
165 //
166 // to_proj
167 // ^^^^^
168 // O<--+----O
169 // : :
170 // O-----+-->O
171 // ,,,,,
172 // other_to_proj
173 const Point other_vec = other_from - other_to;
174 const coord_t to_proj = dot(to - other_to, other_vec) / vSize(other_vec);
175
176 const Point vec = from - to;
177 const coord_t other_to_proj = dot(other_to - to, vec) / vSize(vec);
178
179 const coord_t overlap_length_2 = to_proj + other_to_proj; //Twice the length of the overlap area, alongside the lines.
180 return overlap_length_2 * overlap_width_2 / 4; //Area = width * height.
181 }
182 if (to_rel != 0 && to_rel == other_to_rel && from_rel == 0 && other_from_rel == 0)
183 {
184 // only beginnings of line segments overlap
185 //
186 // from_proj
187 // ^^^^^
188 // O<---+---O
189 // : :
190 // O---+---->O
191 // ,,,,,
192 // other_from_proj
193 const Point other_vec = other_to - other_from;
194 const coord_t from_proj = dot(from - other_from, other_vec) / vSize(other_vec);
195
196 const Point vec = to - from;
197 const coord_t other_from_proj = dot(other_from - from, vec) / vSize(vec);
198
199 const coord_t overlap_length_2 = from_proj + other_from_proj; //Twice the length of the overlap area, alongside the lines.
200 return overlap_length_2 * overlap_width_2 / 4; //Area = width * height.
201 }
202
203 //More complex case.
204 const Point from_middle = other_to + from; // don't divide by two just yet
205 const Point to_middle = other_from + to; // don't divide by two just yet
206
207 const coord_t overlap_length_2 = vSize(from_middle - to_middle); //(An approximation of) twice the length of the overlap area, alongside the lines.
208 return overlap_length_2 * overlap_width_2 / 4; //Area = width * height.
209 }
210
getIsPassed(const ProximityPointLink & link_a,const ProximityPointLink & link_b)211 bool WallOverlapComputation::getIsPassed(const ProximityPointLink& link_a, const ProximityPointLink& link_b)
212 {
213 return passed_links.find(SymmetricPair<ProximityPointLink>(link_a, link_b)) != passed_links.end();
214 }
215
setIsPassed(const ProximityPointLink & link_a,const ProximityPointLink & link_b)216 void WallOverlapComputation::setIsPassed(const ProximityPointLink& link_a, const ProximityPointLink& link_b)
217 {
218 passed_links.emplace(link_a, link_b);
219 }
220
221
222 }//namespace cura
223