PCB Environment 2
Loading...
Searching...
No Matches
RasterizerMidpoint.hpp
1
2#include "Log.hpp"
3#include "Rasterizer.hpp"
4#include "Track.hpp"
5
6template<class ROP> void Rasterizer<ROP>::rasterizeFill(const Bbox_2 &box, uint Z0, uint Z1)
7{
8 assert(Z1 >= Z0 && Z1 < mGrid.getSize(2));
9 if (Z1 < Z0 || Z1 >= mGrid.getSize(2))
10 return;
11 const auto ex = mExpansion - mGrid.EdgeLen05 - mTolerance;
12 const auto eh = std::max(ex, box.xmin() - box.xmax());
13 const auto ev = std::max(ex, box.ymin() - box.ymax());
14 const auto X0 = mGrid.XIndexBounded(box.xmin(), -eh);
15 const auto X1 = mGrid.XIndexBounded(box.xmax(), +eh);
16 const auto Y0 = mGrid.YIndexBounded(box.ymin(), -ev);
17 const auto Y1 = mGrid.YIndexBounded(box.ymax(), +ev);
18 OP.writeRangeZYX(Z0, Z1, Y0, Y1, X0, X1);
19}
20
21template<class ROP> void Rasterizer<ROP>::rasterizeLine(const Bbox_2 &box, uint Z0, uint Z1)
22{
23 assert(Z1 >= Z0 && Z1 < mGrid.getSize(2));
24 if (Z1 < Z0 || Z1 >= mGrid.getSize(2))
25 return;
26 const auto ex = mExpansion - mGrid.EdgeLen05 - mTolerance;
27 const auto eh = std::max(ex, box.xmin() - box.xmax());
28 const auto ev = std::max(ex, box.ymin() - box.ymax());
29 const auto X0 = mGrid.XIndexBounded(box.xmin(), -eh);
30 const auto X1 = mGrid.XIndexBounded(box.xmax(), +eh);
31 const auto Y0 = mGrid.YIndexBounded(box.ymin(), -ev);
32 const auto Y1 = mGrid.YIndexBounded(box.ymax(), +ev);
33 OP.reserve(4);
34 OP.writeRangeZX(Z0, Z1, Y0, X0, X1);
35 if (Y1 == Y0)
36 return;
37 OP.writeRangeZX(Z0, Z1, Y1, X0, X1);
38 if (Y1 == (Y0 + 1))
39 return;
40 OP.writeRangeZY(Z0, Z1, Y0+1, Y1-1, X0);
41 if (X0 != X1)
42 OP.writeRangeZY(Z0, Z1, Y0+1, Y1-1, X1);
43}
44
45template<class ROP> void Rasterizer<ROP>::rasterizeFill(const Circle_2 &C, uint Z0, uint Z1)
46{
47 assert(Z1 >= Z0 && Z1 < mGrid.getSize(2));
48 const auto &O = C.center();
49 const auto r = std::sqrt(C.squared_radius()) + mExpansion;
50 const auto r2 = r * r;
51 const auto ex = std::min(mGrid.EdgeLen05 + mTolerance, r); // ensure Y0 <= Y1
52 const auto Y0 = mGrid.YIndexBounded(O.y() - r, +ex);
53 const auto Y1 = mGrid.YIndexBounded(O.y() + r, -ex);
54 DEBUG("rasterizeCircle: O=" << O << " r=" << r << " Z=[" << Z0 << ',' << Z1 << "] Y=[" << Y0 << ',' << Y1 << ']');
55 auto cY = mGrid.MidPointY(Y0) - O.y(); // y-distance from circle center to midpoint of lowest row
56 assert(Y0 <= Y1);
57 assert(cY <= mGrid.EdgeLen05); // can be > 0 for small circles centered below the midpoint
58 OP.reserve(Y1 - Y0 + 1);
59 for (auto Y = Y0; Y <= Y1; ++Y, cY += mGrid.EdgeLen) {
60 const auto cX = std::sqrt(std::max(r2 - cY * cY, 0.0)); // x-distance corresponding to y-distance on circle
61 const auto X0 = mGrid.XIndexBounded(O.x() - cX, +ex);
62 const auto X1 = mGrid.XIndexBounded(O.x() + cX, -ex);
63 OP.writeRangeZX(Z0, Z1, Y, X0, X1);
64 }
65}
66
67template<class ROP> void Rasterizer<ROP>::rasterizeLine(const Circle_2&, uint Z0, uint Z1)
68{
69 throw std::runtime_error("FIXME: circle border rasterization");
70}
71
72template<class ROP> void Rasterizer<ROP>::rasterizeFill(const WideSegment_25 &s, uint capsMask)
73{
74 rasterizeFill(s, capsMask, s.z(), s.z());
75}
76template<class ROP> void Rasterizer<ROP>::rasterizeFill(const WideSegment_25 &s, uint capsMask, uint Z0, uint Z1)
77{
78 assert(Z0 >= 0 && Z0 <= Z1 && Z1 < mGrid.getSize(2));
79
80 if (capsMask & RASTERIZE_CAPS_MASK_SOURCE)
81 rasterizeFill(s.sourceCap(), Z0, Z1);
82 if (capsMask & RASTERIZE_CAPS_MASK_TARGET)
83 rasterizeFill(s.targetCap(), Z0, Z1);
84
85 const Real ex = s.halfWidth() + mExpansion;
86 if (s.base().is_horizontal())
87 rasterizeHSegment(s.base().s2(), Z0, Z1, ex);
88 else if (s.base().is_vertical())
89 rasterizeVSegment(s.base().s2(), Z0, Z1, ex);
90 else rasterizeDSegment(s.base().s2(), Z0, Z1, ex);
91}
92
93template<class ROP> void Rasterizer<ROP>::rasterizeLine(const WideSegment_25 &s, uint capsMask)
94{
95 rasterizeLine(capsMask ? Segment_25(s.s2_extended(capsMask), s.z()) : s.base());
96}
97template<class ROP> void Rasterizer<ROP>::rasterizeLine(const WideSegment_25 &s, uint capsMask, uint Z0, uint Z1)
98{
99 rasterizeLine(capsMask ? Segment_25(s.s2_extended(capsMask), s.z()) : s.base(), Z0, Z1);
100}
101
102template<class ROP> void Rasterizer<ROP>::rasterizeFill(const Segment_25 &s)
103{
104 rasterizeFill(s, s.z(), s.z());
105}
106template<class ROP> void Rasterizer<ROP>::rasterizeFill(const Segment_25 &s, uint Z0, uint Z1)
107{
108 assert(Z0 >= 0 && Z0 <= Z1 && Z1 < mGrid.getSize(2));
109 const Real ex = mExpansion;
110 if (s.is_horizontal())
111 rasterizeHSegment(s.s2(), Z0, Z1, ex);
112 else if (s.is_vertical())
113 rasterizeVSegment(s.s2(), Z0, Z1, ex);
114 else rasterizeDSegment(s.s2(), Z0, Z1, ex);
115}
116
117template<class ROP> void Rasterizer<ROP>::rasterizeLine(const Segment_25 &s)
118{
119 rasterizeLine(s, s.z(), s.z());
120}
121template<class ROP> void Rasterizer<ROP>::rasterizeLine(const Segment_25 &s, uint Z0, uint Z1)
122{
123 assert(Z0 >= 0 && Z0 <= Z1 && Z1 < mGrid.getSize(2));
124 if (s.is_horizontal())
125 rasterizeHSegmentLine(s.s2(), Z0, Z1);
126 else if (s.is_vertical())
127 rasterizeVSegmentLine(s.s2(), Z0, Z1);
128 else rasterizeDSegmentLine(s.s2(), Z0, Z1);
129}
130
131template<class ROP> void Rasterizer<ROP>::rasterizeFill(const Triangle_2 &T, uint Z0, uint Z1)
132{
133 assert(Z1 >= Z0 && Z1 < mGrid.getSize(2));
134 if (mExpansion)
135 throw std::runtime_error("FIXME: triangle rasterization with dilation");
136 const auto ex = mGrid.EdgeLen05 + mTolerance;
137 const auto box = T.bbox();
138 const auto XL = mGrid.XIndexBounded(box.xmin(), +ex);
139 const auto XR = mGrid.XIndexBounded(box.xmax(), -ex);
140 const auto xL = mGrid.MidPointX(XL);
141 const auto xR = mGrid.MidPointX(XR);
142 const auto Y0 = mGrid.YIndexBounded(box.ymin(), +ex);
143 const auto Y1 = mGrid.YIndexBounded(box.ymax(), -ex);
144 const auto y0 = mGrid.MidPointY(Y0);
145 OP.reserve(Y1 - Y0 + 1);
146 Point_2 v(xL, y0);
147 for (auto Y = Y0; Y <= Y1; ++Y, v = Point_2(xL, v.y() + mGrid.EdgeLen)) {
148 uint X0, X1;
149 for (X0 = XL, v = Point_2(xL, v.y()); X0 <= XR && T.has_on_unbounded_side(v); ++X0)
150 v = Point_2(v.x() + mGrid.EdgeLen, v.y());
151 if (X0 > XR)
152 continue;
153 for (X1 = XR, v = Point_2(xR, v.y()); X1 > X0 && T.has_on_unbounded_side(v); --X1)
154 v = Point_2(v.x() - mGrid.EdgeLen, v.y());
155 OP.writeRangeZX(Z0, Z1, Y, X0, X1);
156 }
157}
158
159template<class ROP> void Rasterizer<ROP>::rasterizeLine(const Triangle_2 &T, uint Z0, uint Z1)
160{
161 assert(Z1 >= Z0 && Z1 < mGrid.getSize(2));
162 const auto ex = mExpansion;
163 mExpansion = 0.0;
164 rasterizeLine(Segment_2(T.vertex(0), T.vertex(1)), Z0, Z1);
165 rasterizeLine(Segment_2(T.vertex(1), T.vertex(2)), Z0, Z1);
166 rasterizeLine(Segment_2(T.vertex(2), T.vertex(0)), Z0, Z1);
167 mExpansion = ex;
168}
169
170template<class ROP> void Rasterizer<ROP>::rasterizeFill(const Polygon_2 &_G, uint Z0, uint Z1)
171{
172 Polygon_2 G_ex;
173 assert(Z1 >= Z0 && Z1 < mGrid.getSize(2));
174 if (mExpansion)
175 G_ex = PolygonEx::grow(_G, mExpansion);
176 const Polygon_2 *G = mExpansion ? &G_ex : &_G;
177 const auto ex = mGrid.EdgeLen05 + mTolerance;
178 const auto box = G->bbox();
179 const auto XL = mGrid.XIndexBounded(box.xmin(), +ex);
180 const auto XR = mGrid.XIndexBounded(box.xmax(), -ex);
181 const auto xL = mGrid.MidPointX(XL);
182 const auto xR = mGrid.MidPointX(XR);
183 const auto Y0 = mGrid.YIndexBounded(box.ymin(), +ex);
184 const auto Y1 = mGrid.YIndexBounded(box.ymax(), -ex);
185 const auto y0 = mGrid.MidPointY(Y0);
186 OP.reserve(Y1 - Y0 + 1);
187 Point_2 v(xL, y0);
188 for (auto Y = Y0; Y <= Y1; ++Y, v = Point_2(xL, v.y() + mGrid.EdgeLen)) {
189 uint X0, X1;
190 for (X0 = XL, v = Point_2(xL, v.y()); X0 <= XR && G->has_on_unbounded_side(v); ++X0)
191 v = Point_2(v.x() + mGrid.EdgeLen, v.y());
192 if (X0 > XR)
193 continue;
194 for (X1 = XR, v = Point_2(xR, v.y()); X1 > X0 && G->has_on_unbounded_side(v); --X1)
195 v = Point_2(v.x() - mGrid.EdgeLen, v.y());
196 OP.writeRangeZX(Z0, Z1, Y, X0, X1);
197 }
198}
199
200template<class ROP> void Rasterizer<ROP>::rasterizeLine(const Polygon_2 &G, uint Z0, uint Z1)
201{
202 assert(Z1 >= Z0 && Z1 < mGrid.getSize(2));
203 for (auto E = G.edges_begin(); E != G.edges_end(); ++E)
204 rasterizeLine(*E, Z0, Z1);
205}
206
207template<class ROP> void Rasterizer<ROP>::rasterizeHSegment(const Segment_2 &s, uint Z0, uint Z1, Real _ex)
208{
209 // Midpoint rasterization:
210 // 0.5 to 1.5 with shifting by 0.5 becomes 1 to 1 but we want to draw both 0 and 1 so we subtract tolerance on the left.
211 // 0.5 to 1.4 becomes 1-TOL to 0.9 so we correctly only draw on 0.
212 // 0.0 to 0.4 becomes 0.2-TOL to 0.2, but we draw on 0 anyway because we always draw at least 1 cell.
213 // We also need to add tolerance on the right because there can be tiny errors such that we get 0 to 0.99999999999994 which should really be 1 with exact calculations.
214 // Something will always be off somewhere :(
215 assert(s.source().y() == s.target().y());
216 const auto x0 = std::min(s.source().x(), s.target().x());
217 const auto x1 = std::max(s.source().x(), s.target().x());
218 const auto hex = std::min(mGrid.EdgeLen05 - mTolerance, (x1 - x0) * 0.5);
219 const auto vex = std::min(mGrid.EdgeLen05 + mTolerance - _ex, 0.0);
220 const auto X0 = mGrid.XIndexBounded(x0, +hex);
221 const auto X1 = mGrid.XIndexBounded(x1, -hex);
222 const auto Y0 = mGrid.YIndexBounded(s.source().y(), +vex);
223 const auto Y1 = mGrid.YIndexBounded(s.source().y(), -vex);
224 DEBUG("rasterizeSegmentH rect[" << X0 << ',' << X1 << "]x[" << Y0 << ',' << Y1 << "] x=(" << (x0 + hex - mTolerance) << ',' << (x1 - hex) << ')');
225 OP.writeRangeZYX(Z0, Z1, Y0, Y1, X0, X1);
226}
227
228template<class ROP> void Rasterizer<ROP>::rasterizeHSegmentLine(const Segment_2 &s, uint Z0, uint Z1)
229{
230 rasterizeHSegment(s, Z0, Z1, 0.0);
231}
232
233template<class ROP> void Rasterizer<ROP>::rasterizeVSegment(const Segment_2 &s, uint Z0, uint Z1, Real _ex)
234{
235 assert(s.source().x() == s.target().x());
236 const auto y0 = std::min(s.source().y(), s.target().y());
237 const auto y1 = std::max(s.source().y(), s.target().y());
238 const auto vex = std::min(mGrid.EdgeLen05 - mTolerance, (y1 - y0) * 0.5);
239 const auto hex = std::min(mGrid.EdgeLen05 + mTolerance - _ex, 0.0);
240 const auto X0 = mGrid.XIndexBounded(s.source().x(), +hex);
241 const auto X1 = mGrid.XIndexBounded(s.source().x(), -hex);
242 const auto Y0 = mGrid.YIndexBounded(y0, +vex);
243 const auto Y1 = mGrid.YIndexBounded(y1, -vex);
244 DEBUG("rasterizeSegmentV rect[" << X0 << ',' << X1 << "]x[" << Y0 << ',' << Y1 << "] y=(" << (y0 + vex - mTolerance) << ',' << (y1 - vex) << ')');
245 OP.writeRangeZYX(Z0, Z1, Y0, Y1, X0, X1);
246}
247
248template<class ROP> void Rasterizer<ROP>::rasterizeVSegmentLine(const Segment_2 &s, uint Z0, uint Z1)
249{
250 rasterizeVSegment(s, Z0, Z1, 0.0);
251}
252
253template<class ROP> void Rasterizer<ROP>::rasterizeDSegment(const Segment_2 &_s, uint Z0, uint Z1, Real _ex)
254{
255 // TODO: Verify rasterization rules.
256 auto s = WideSegment_25(_s, Z0, _ex);
257 if (s.widerThanBaseLen())
258 s = s.swapWL(mTolerance, -2.0 * mTolerance); // we have to increase the width a bit or we miss the start and end points of route segments
259 s = s.orderedY();
260 if (std::abs(s.base().s2().to_vector().y()) < 0x1.0p-7)
261 throw std::runtime_error("FIXME: rasterizing nearly horizontal segment requires special handling");
262 const auto ex = mGrid.EdgeLen05;
263 const auto uT = s.getHalfWidthSpan();
264 const auto vT = uT.x() < 0.0 ? -uT : uT; // perpendicular (half-width) vector with dx >= 0
265 const auto sL = Segment_2(s.source_2() - vT, s.target_2() - vT); // left track boundary
266 const auto sR = Segment_2(s.source_2() + vT, s.target_2() + vT); // right track boundary
267 const auto LL = sL.supporting_line();
268 const auto LR = sR.supporting_line();
269 // Create a triangulation of the segment. sL and sR have the same endpoint order so the edges fit.
270 const auto AL = Triangle_2(sL.source(), sL.target(), sR.source());
271 const auto AR = Triangle_2(sR.source(), sR.target(), sL.target());
272 const auto y0 = std::min(sL.source().y(), sR.source().y());
273 const auto y1 = std::max(sL.target().y(), sR.target().y());
274 const auto yA0 = std::max(sL.source().y(), sR.source().y()); // y-range that is delimited by LL and LR
275 const auto yA1 = std::min(sL.target().y(), sR.target().y());
276 const auto Y0 = mGrid.YIndexBounded(y0, +ex - mTolerance);
277 const auto Y1 = mGrid.YIndexBounded(y1, -ex);
278 auto y = mGrid.MidPointY(Y0);
279 OP.reserve(Y1 - Y0 + 1);
280 for (auto Y = Y0; Y <= Y1; ++Y, y += mGrid.EdgeLen) {
281 int X0 = mGrid.XIndexBounded(LL.x_at_y(y), +ex - mTolerance);
282 int X1 = mGrid.XIndexBounded(LR.x_at_y(y), -ex);
283 if (y < yA0 || y > yA1) {
284 auto m = Point_2(mGrid.MidPointX(X0), y);
285 for (; X0 < X1 && AL.has_on_unbounded_side(m) && AR.has_on_unbounded_side(m); ++X0)
286 m = Point_2(m.x() + mGrid.EdgeLen, m.y());
287 if (X0 != X1)
288 m = Point_2(mGrid.MidPointX(X1), m.y());
289 for (; X1 >= X0 && AL.has_on_unbounded_side(m) && AR.has_on_unbounded_side(m); --X1)
290 m = Point_2(m.x() - mGrid.EdgeLen, m.y());
291 }
292 if (X0 <= X1)
293 OP.writeRangeZX(Z0, Z1, Y, X0, X1);
294 }
295}
296
297template<class ROP> void Rasterizer<ROP>::rasterizeDSegmentLine(const Segment_2 &s, uint Z0, uint Z1)
298{
299 const auto ex = mTolerance + mGrid.EdgeLen05;
300 const auto x0 = mGrid.XfIndex(std::min(s.source().x(), s.target().x()), +ex);
301 const auto y0 = mGrid.YfIndex(std::min(s.source().y(), s.target().y()), +ex);
302 const auto x1 = std::max(mGrid.XfIndex(std::max(s.source().x(), s.target().x()), -ex), x0); // == if within tolerance
303 const auto y1 = std::max(mGrid.YfIndex(std::max(s.source().y(), s.target().y()), -ex), y0);
304 const int xR = std::min(int(mGrid.getSize(0)) - 1, int(x1)); // don't overshoot ...
305 const int xL = std::max(0, int(x0)); // or undershoot on nearly horizontal lines
306 if (xL > xR)
307 return;
308 OP.reserve(int(y1 - y0 + 1));
309 const auto xrev = (s.source().x() > s.target().x()) ^ (s.source().y() > s.target().y());
310 const Real dxdy = (s.target().x() - s.source().x()) / (s.target().y() - s.source().y());
311 Real x = xrev ? x1 : x0;
312 for (auto y = y0; y <= y1; y += 1.0, x += dxdy) {
313 const auto Y = int(y);
314 if (Y < 0 || Y >= int(mGrid.getSize(1)))
315 continue;
316 auto X0 = std::max(xL, std::min(xR, int(x)));
317 auto X1 = std::max(xL, std::min(xR, int(x + dxdy)));
318 OP.writeRangeZX(Z0, Z1, Y, std::min(X0, X1), std::max(X0, X1));
319 }
320}
321
322template<class ROP> void Rasterizer<ROP>::rasterizeFill(const AShape *H, uint Z0, uint Z1)
323{
324 assert(H);
325 if (const auto R = dynamic_cast<const Iso_rectangle_2 *>(H))
326 rasterizeFill(R->bbox(), Z0, Z1);
327 else if (const auto C = dynamic_cast<const Circle_2 *>(H))
328 rasterizeFill(*C, Z0, Z1);
329 else if (const auto T = dynamic_cast<const Triangle_2 *>(H))
330 rasterizeFill(*T, Z0, Z1);
331 else if (const auto G = dynamic_cast<const Polygon_2 *>(H))
332 rasterizeFill(*G, Z0, Z1);
333 else if (const auto S = dynamic_cast<const WideSegment_25 *>(H))
334 rasterizeFill(*S, 0x3, Z0, Z1);
335 else if (H)
336 rasterizeFill(H->bbox(), Z0, Z1);
337}
338template<class ROP> void Rasterizer<ROP>::rasterizeLine(const AShape *H, uint Z0, uint Z1)
339{
340 assert(H);
341 if (const auto R = dynamic_cast<const Iso_rectangle_2 *>(H))
342 rasterizeLine(R->bbox(), Z0, Z1);
343 else if (const auto C = dynamic_cast<const Circle_2 *>(H))
344 rasterizeLine(*C, Z0, Z1);
345 else if (const auto T = dynamic_cast<const Triangle_2 *>(H))
346 rasterizeLine(*T, Z0, Z1);
347 else if (const auto G = dynamic_cast<const Polygon_2 *>(H))
348 rasterizeLine(*G, Z0, Z1);
349 else if (const auto S = dynamic_cast<const WideSegment_25 *>(H))
350 rasterizeLine(*S, 0x3, Z0, Z1);
351 else if (H)
352 rasterizeLine(H->bbox(), Z0, Z1);
353}
354
355template<class ROP> void Rasterizer<ROP>::rasterizeFill(const Track &T, uint itemsMask)
356{
357 if (itemsMask & RASTERIZE_MASK_VIAS)
358 for (const auto &v : T.getVias())
359 rasterizeFill(v.getCircle(), v.zmin(), v.zmax());
360 if (!T.hasSegments() || !(itemsMask & RASTERIZE_MASK_SEGMENTS))
361 return;
362 if (!(itemsMask & RASTERIZE_MASK_CAPS_AND_JUNCTIONS) || !T.hasSegmentJoints()) { // it's simpler if we don't have to draw any caps
363 for (const auto &s : T.getSegments())
364 rasterizeFill(s, 0x0);
365 return;
366 }
367 uint mask = (T.hasStartCap() && !T.startsWithVia()) ? 0x0 : 0x2;
368 for (uint i = 0; i < T.numSegments() - 1; ++i) {
369 const auto &s = T.getSegment(i);
370 const auto &t = T.getSegment(i+1);
371 mask = (mask & 0x2) ? 0x0 : 0x1;
372 // If the next segment is narrower and there is no via, rasterize the target cap and skip the next source cap.
373 if (s.halfWidth() > t.halfWidth() && s.z() == t.z())
374 mask |= 0x2;
375 rasterizeFill(s, mask);
376 if (s.z() != t.z())
377 mask |= 0x2; // s ends in a via, so skip the next source cap
378 }
379 // Last segment.
380 mask = (mask & 0x2) ? 0x0 : 0x1;
381 if (T.hasEndCap() && !T.endsWithVia())
382 mask |= 0x2;
383 rasterizeFill(T.getSegments().back(), mask);
384}
385template<class ROP> void Rasterizer<ROP>::rasterizeLine(const Track &T)
386{
387 for (const auto &s : T.getSegments())
388 rasterizeLine(s.base());
389}
390
391template<class ROP> void Rasterizer<ROP>::rasterizeRanges(const std::vector<IndexRange> &ranges)
392{
393 for (const IndexRange &R : ranges)
394 for (uint Z = R.Z0; Z <= R.Z1; ++Z)
395 for (uint Y = R.Y0; Y <= R.Y1; ++Y)
396 for (uint I = mGrid.LinearIndex(Z,Y,R.X0), I1 = I + (R.X1 - R.X0); I <= I1; ++I)
397 OP.writeIndex(I);
398}
Definition AShape.hpp:21
static Polygon_2 grow(const Polygon_2 &, Real size, Real epsilon=0.125)
Definition Geometry.hpp:155
Definition Track.hpp:21
Definition AShape.hpp:332
Segment_2 s2_extended(uint mask=0x3) const
Definition Rasterizer.hpp:28