1// Copyright 2011 Google Inc.
2// Copyright 2020 Yevhenii Reizner
3//
4// Use of this source code is governed by a BSD-style license that can be
5// found in the LICENSE file.
6
7use crate::{Point, Rect};
8
9use tiny_skia_path::Scalar;
10
11pub const MAX_POINTS: usize = 4;
12
13/// Clip the line pts[0]...pts[1] against clip, ignoring segments that
14/// lie completely above or below the clip. For portions to the left or
15/// right, turn those into vertical line segments that are aligned to the
16/// edge of the clip.
17///
18/// Return the number of line segments that result, and store the end-points
19/// of those segments sequentially in lines as follows:
20///
21/// 1st segment: lines[0]..lines[1]
22/// 2nd segment: lines[1]..lines[2]
23/// 3rd segment: lines[2]..lines[3]
24pub fn clip<'a>(
25 src: &[Point; 2],
26 clip: &Rect,
27 can_cull_to_the_right: bool,
28 points: &'a mut [Point; MAX_POINTS],
29) -> &'a [Point] {
30 let (mut index0, mut index1) = if src[0].y < src[1].y { (0, 1) } else { (1, 0) };
31
32 // Check if we're completely clipped out in Y (above or below)
33
34 if src[index1].y <= clip.top() {
35 // we're above the clip
36 return &[];
37 }
38
39 if src[index0].y >= clip.bottom() {
40 // we're below the clip
41 return &[];
42 }
43
44 // Chop in Y to produce a single segment, stored in tmp[0..1]
45
46 let mut tmp = *src;
47
48 // now compute intersections
49 if src[index0].y < clip.top() {
50 tmp[index0] = Point::from_xy(sect_with_horizontal(src, clip.top()), clip.top());
51 debug_assert!(is_between_unsorted(tmp[index0].x, src[0].x, src[1].x));
52 }
53
54 if tmp[index1].y > clip.bottom() {
55 tmp[index1] = Point::from_xy(sect_with_horizontal(src, clip.bottom()), clip.bottom());
56 debug_assert!(is_between_unsorted(tmp[index1].x, src[0].x, src[1].x));
57 }
58
59 // Chop it into 1..3 segments that are wholly within the clip in X.
60
61 // temp storage for up to 3 segments
62 let mut result_storage = [Point::zero(); MAX_POINTS];
63 let mut line_count = 1;
64 let mut reverse;
65
66 if src[0].x < src[1].x {
67 index0 = 0;
68 index1 = 1;
69 reverse = false;
70 } else {
71 index0 = 1;
72 index1 = 0;
73 reverse = true;
74 }
75
76 let result: &[Point] = if tmp[index1].x <= clip.left() {
77 // wholly to the left
78 tmp[0].x = clip.left();
79 tmp[1].x = clip.left();
80 reverse = false;
81 &tmp
82 } else if tmp[index0].x >= clip.right() {
83 // wholly to the right
84 if can_cull_to_the_right {
85 return &[];
86 }
87
88 tmp[0].x = clip.right();
89 tmp[1].x = clip.right();
90 reverse = false;
91 &tmp
92 } else {
93 let mut offset = 0;
94
95 if tmp[index0].x < clip.left() {
96 result_storage[offset] = Point::from_xy(clip.left(), tmp[index0].y);
97 offset += 1;
98 result_storage[offset] =
99 Point::from_xy(clip.left(), sect_clamp_with_vertical(&tmp, clip.left()));
100 debug_assert!(is_between_unsorted(
101 result_storage[offset].y,
102 tmp[0].y,
103 tmp[1].y
104 ));
105 } else {
106 result_storage[offset] = tmp[index0];
107 }
108 offset += 1;
109
110 if tmp[index1].x > clip.right() {
111 result_storage[offset] =
112 Point::from_xy(clip.right(), sect_clamp_with_vertical(&tmp, clip.right()));
113 debug_assert!(is_between_unsorted(
114 result_storage[offset].y,
115 tmp[0].y,
116 tmp[1].y
117 ));
118 offset += 1;
119 result_storage[offset] = Point::from_xy(clip.right(), tmp[index1].y);
120 } else {
121 result_storage[offset] = tmp[index1];
122 }
123
124 line_count = offset;
125 &result_storage
126 };
127
128 // Now copy the results into the caller's lines[] parameter
129 if reverse {
130 // copy the pts in reverse order to maintain winding order
131 for i in 0..=line_count {
132 points[line_count - i] = result[i];
133 }
134 } else {
135 let len = line_count + 1;
136 points[0..len].copy_from_slice(&result[0..len]);
137 }
138
139 &points[0..line_count + 1]
140}
141
142/// Returns X coordinate of intersection with horizontal line at Y.
143fn sect_with_horizontal(src: &[Point; 2], y: f32) -> f32 {
144 let dy: f32 = src[1].y - src[0].y;
145 if dy.is_nearly_zero() {
146 src[0].x.ave(src[1].x)
147 } else {
148 // need the extra precision so we don't compute a value that exceeds
149 // our original limits
150 let x0: f64 = f64::from(src[0].x);
151 let y0: f64 = f64::from(src[0].y);
152 let x1: f64 = f64::from(src[1].x);
153 let y1: f64 = f64::from(src[1].y);
154 let result: f64 = x0 + (f64::from(y) - y0) * (x1 - x0) / (y1 - y0);
155
156 // The computed X value might still exceed [X0..X1] due to quantum flux
157 // when the doubles were added and subtracted, so we have to pin the
158 // answer :(
159 pin_unsorted_f64(value:result, limit0:x0, limit1:x1) as f32
160 }
161}
162
163/// Returns value between the two limits, where the limits are either ascending or descending.
164fn is_between_unsorted(value: f32, limit0: f32, limit1: f32) -> bool {
165 if limit0 < limit1 {
166 limit0 <= value && value <= limit1
167 } else {
168 limit1 <= value && value <= limit0
169 }
170}
171
172fn sect_clamp_with_vertical(src: &[Point; 2], x: f32) -> f32 {
173 let y: f32 = sect_with_vertical(src, x);
174 // Our caller expects y to be between src[0].y and src[1].y (unsorted), but due to the
175 // numerics of floats/doubles, we might have computed a value slightly outside of that,
176 // so we have to manually clamp afterwards.
177 // See skbug.com/7491
178 pin_unsorted_f32(value:y, limit0:src[0].y, limit1:src[1].y)
179}
180
181/// Returns Y coordinate of intersection with vertical line at X.
182fn sect_with_vertical(src: &[Point; 2], x: f32) -> f32 {
183 let dx: f32 = src[1].x - src[0].x;
184 if dx.is_nearly_zero() {
185 src[0].y.ave(src[1].y)
186 } else {
187 // need the extra precision so we don't compute a value that exceeds
188 // our original limits
189 let x0: f64 = f64::from(src[0].x);
190 let y0: f64 = f64::from(src[0].y);
191 let x1: f64 = f64::from(src[1].x);
192 let y1: f64 = f64::from(src[1].y);
193 let result: f64 = y0 + (f64::from(x) - x0) * (y1 - y0) / (x1 - x0);
194 result as f32
195 }
196}
197
198fn pin_unsorted_f32(value: f32, mut limit0: f32, mut limit1: f32) -> f32 {
199 if limit1 < limit0 {
200 core::mem::swap(&mut limit0, &mut limit1);
201 }
202 // now the limits are sorted
203 debug_assert!(limit0 <= limit1);
204
205 if value < limit0 {
206 limit0
207 } else if value > limit1 {
208 limit1
209 } else {
210 value
211 }
212}
213
214fn pin_unsorted_f64(value: f64, mut limit0: f64, mut limit1: f64) -> f64 {
215 if limit1 < limit0 {
216 core::mem::swap(&mut limit0, &mut limit1);
217 }
218 // now the limits are sorted
219 debug_assert!(limit0 <= limit1);
220
221 if value < limit0 {
222 limit0
223 } else if value > limit1 {
224 limit1
225 } else {
226 value
227 }
228}
229
230/// Intersect the line segment against the rect. If there is a non-empty
231/// resulting segment, return true and set dst[] to that segment. If not,
232/// return false and ignore dst[].
233///
234/// `clip` is specialized for scan-conversion, as it adds vertical
235/// segments on the sides to show where the line extended beyond the
236/// left or right sides. `intersect` does not.
237pub fn intersect(src: &[Point; 2], clip: &Rect, dst: &mut [Point; 2]) -> bool {
238 let bounds = Rect::from_ltrb(
239 src[0].x.min(src[1].x),
240 src[0].y.min(src[1].y),
241 src[0].x.max(src[1].x),
242 src[0].y.max(src[1].y),
243 );
244
245 if let Some(bounds) = bounds {
246 if contains_no_empty_check(clip, &bounds) {
247 dst.copy_from_slice(src);
248 return true;
249 }
250
251 // check for no overlap, and only permit coincident edges if the line
252 // and the edge are colinear
253 if nested_lt(bounds.right(), clip.left(), bounds.width())
254 || nested_lt(clip.right(), bounds.left(), bounds.width())
255 || nested_lt(bounds.bottom(), clip.top(), bounds.height())
256 || nested_lt(clip.bottom(), bounds.top(), bounds.height())
257 {
258 return false;
259 }
260 }
261
262 let (index0, index1) = if src[0].y < src[1].y { (0, 1) } else { (1, 0) };
263
264 let mut tmp = src.clone();
265
266 // now compute Y intersections
267 if tmp[index0].y < clip.top() {
268 tmp[index0] = Point::from_xy(sect_with_horizontal(src, clip.top()), clip.top());
269 }
270
271 if tmp[index1].y > clip.bottom() {
272 tmp[index1] = Point::from_xy(sect_with_horizontal(src, clip.bottom()), clip.bottom());
273 }
274
275 let (index0, index1) = if tmp[0].x < tmp[1].x { (0, 1) } else { (1, 0) };
276
277 // check for quick-reject in X again, now that we may have been chopped
278 if tmp[index1].x <= clip.left() || tmp[index0].x >= clip.right() {
279 // usually we will return false, but we don't if the line is vertical and coincident
280 // with the clip.
281 if tmp[0].x != tmp[1].x || tmp[0].x < clip.left() || tmp[0].x > clip.right() {
282 return false;
283 }
284 }
285
286 if tmp[index0].x < clip.left() {
287 tmp[index0] = Point::from_xy(clip.left(), sect_with_vertical(src, clip.left()));
288 }
289
290 if tmp[index1].x > clip.right() {
291 tmp[index1] = Point::from_xy(clip.right(), sect_with_vertical(src, clip.right()));
292 }
293
294 dst.copy_from_slice(&tmp);
295 true
296}
297
298fn nested_lt(a: f32, b: f32, dim: f32) -> bool {
299 a <= b && (a < b || dim > 0.0)
300}
301
302// returns true if outer contains inner, even if inner is empty.
303fn contains_no_empty_check(outer: &Rect, inner: &Rect) -> bool {
304 outer.left() <= inner.left()
305 && outer.top() <= inner.top()
306 && outer.right() >= inner.right()
307 && outer.bottom() >= inner.bottom()
308}
309