3#include "Rasterizer.hpp"
6template<
class ROP>
void Rasterizer<ROP>::rasterizeFill(
const Bbox_2 &box, uint Z0, uint Z1)
8 assert(Z1 >= Z0 && Z1 < mGrid.getSize(2));
9 if (Z1 < Z0 || Z1 >= mGrid.getSize(2))
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);
21template<
class ROP>
void Rasterizer<ROP>::rasterizeLine(
const Bbox_2 &box, uint Z0, uint Z1)
23 assert(Z1 >= Z0 && Z1 < mGrid.getSize(2));
24 if (Z1 < Z0 || Z1 >= mGrid.getSize(2))
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);
34 OP.writeRangeZX(Z0, Z1, Y0, X0, X1);
37 OP.writeRangeZX(Z0, Z1, Y1, X0, X1);
40 OP.writeRangeZY(Z0, Z1, Y0+1, Y1-1, X0);
42 OP.writeRangeZY(Z0, Z1, Y0+1, Y1-1, X1);
45template<
class ROP>
void Rasterizer<ROP>::rasterizeFill(
const Circle_2 &C, uint Z0, uint Z1)
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);
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();
57 assert(cY <= mGrid.EdgeLen05);
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));
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);
67template<
class ROP>
void Rasterizer<ROP>::rasterizeLine(
const Circle_2&, uint Z0, uint Z1)
69 throw std::runtime_error(
"FIXME: circle border rasterization");
72template<
class ROP>
void Rasterizer<ROP>::rasterizeFill(
const WideSegment_25 &s, uint capsMask)
74 rasterizeFill(s, capsMask, s.z(), s.z());
76template<
class ROP>
void Rasterizer<ROP>::rasterizeFill(
const WideSegment_25 &s, uint capsMask, uint Z0, uint Z1)
78 assert(Z0 >= 0 && Z0 <= Z1 && Z1 < mGrid.getSize(2));
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);
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);
93template<
class ROP>
void Rasterizer<ROP>::rasterizeLine(
const WideSegment_25 &s, uint capsMask)
97template<
class ROP>
void Rasterizer<ROP>::rasterizeLine(
const WideSegment_25 &s, uint capsMask, uint Z0, uint Z1)
102template<
class ROP>
void Rasterizer<ROP>::rasterizeFill(
const Segment_25 &s)
104 rasterizeFill(s, s.z(), s.z());
106template<
class ROP>
void Rasterizer<ROP>::rasterizeFill(
const Segment_25 &s, uint Z0, uint Z1)
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);
117template<
class ROP>
void Rasterizer<ROP>::rasterizeLine(
const Segment_25 &s)
119 rasterizeLine(s, s.z(), s.z());
121template<
class ROP>
void Rasterizer<ROP>::rasterizeLine(
const Segment_25 &s, uint Z0, uint Z1)
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);
131template<
class ROP>
void Rasterizer<ROP>::rasterizeFill(
const Triangle_2 &T, uint Z0, uint Z1)
133 assert(Z1 >= Z0 && Z1 < mGrid.getSize(2));
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);
147 for (
auto Y = Y0; Y <= Y1; ++Y, v = Point_2(xL, v.y() + mGrid.EdgeLen)) {
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());
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);
159template<
class ROP>
void Rasterizer<ROP>::rasterizeLine(
const Triangle_2 &T, uint Z0, uint Z1)
161 assert(Z1 >= Z0 && Z1 < mGrid.getSize(2));
162 const auto ex = mExpansion;
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);
170template<
class ROP>
void Rasterizer<ROP>::rasterizeFill(
const Polygon_2 &_G, uint Z0, uint Z1)
173 assert(Z1 >= Z0 && Z1 < mGrid.getSize(2));
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);
188 for (
auto Y = Y0; Y <= Y1; ++Y, v = Point_2(xL, v.y() + mGrid.EdgeLen)) {
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());
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);
200template<
class ROP>
void Rasterizer<ROP>::rasterizeLine(
const Polygon_2 &G, uint Z0, uint Z1)
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);
207template<
class ROP>
void Rasterizer<ROP>::rasterizeHSegment(
const Segment_2 &s, uint Z0, uint Z1, Real _ex)
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);
228template<
class ROP>
void Rasterizer<ROP>::rasterizeHSegmentLine(
const Segment_2 &s, uint Z0, uint Z1)
230 rasterizeHSegment(s, Z0, Z1, 0.0);
233template<
class ROP>
void Rasterizer<ROP>::rasterizeVSegment(
const Segment_2 &s, uint Z0, uint Z1, Real _ex)
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);
248template<
class ROP>
void Rasterizer<ROP>::rasterizeVSegmentLine(
const Segment_2 &s, uint Z0, uint Z1)
250 rasterizeVSegment(s, Z0, Z1, 0.0);
253template<
class ROP>
void Rasterizer<ROP>::rasterizeDSegment(
const Segment_2 &_s, uint Z0, uint Z1, Real _ex)
257 if (s.widerThanBaseLen())
258 s = s.swapWL(mTolerance, -2.0 * mTolerance);
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;
265 const auto sL = Segment_2(s.source_2() - vT, s.target_2() - vT);
266 const auto sR = Segment_2(s.source_2() + vT, s.target_2() + vT);
267 const auto LL = sL.supporting_line();
268 const auto LR = sR.supporting_line();
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());
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());
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());
293 OP.writeRangeZX(Z0, Z1, Y, X0, X1);
297template<
class ROP>
void Rasterizer<ROP>::rasterizeDSegmentLine(
const Segment_2 &s, uint Z0, uint Z1)
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);
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));
305 const int xL = std::max(0,
int(x0));
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)))
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));
322template<
class ROP>
void Rasterizer<ROP>::rasterizeFill(
const AShape *H, uint Z0, uint Z1)
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);
334 rasterizeFill(*S, 0x3, Z0, Z1);
336 rasterizeFill(H->bbox(), Z0, Z1);
338template<
class ROP>
void Rasterizer<ROP>::rasterizeLine(
const AShape *H, uint Z0, uint Z1)
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);
350 rasterizeLine(*S, 0x3, Z0, Z1);
352 rasterizeLine(H->bbox(), Z0, Z1);
355template<
class ROP>
void Rasterizer<ROP>::rasterizeFill(
const Track &T, uint itemsMask)
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))
362 if (!(itemsMask & RASTERIZE_MASK_CAPS_AND_JUNCTIONS) || !T.hasSegmentJoints()) {
363 for (
const auto &s : T.getSegments())
364 rasterizeFill(s, 0x0);
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;
373 if (s.halfWidth() > t.halfWidth() && s.z() == t.z())
375 rasterizeFill(s, mask);
380 mask = (mask & 0x2) ? 0x0 : 0x1;
381 if (T.hasEndCap() && !T.endsWithVia())
383 rasterizeFill(T.getSegments().back(), mask);
385template<
class ROP>
void Rasterizer<ROP>::rasterizeLine(
const Track &T)
387 for (
const auto &s : T.getSegments())
388 rasterizeLine(s.base());
391template<
class ROP>
void Rasterizer<ROP>::rasterizeRanges(
const std::vector<IndexRange> &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)
static Polygon_2 grow(const Polygon_2 &, Real size, Real epsilon=0.125)
Definition Geometry.hpp:155
Definition AShape.hpp:332
Segment_2 s2_extended(uint mask=0x3) const
Definition Rasterizer.hpp:28