1 | /**************************************************************************** |
2 | ** |
3 | ** Copyright (C) 2016 The Qt Company Ltd. |
4 | ** Contact: https://www.qt.io/licensing/ |
5 | ** |
6 | ** This file is part of the QtGui module of the Qt Toolkit. |
7 | ** |
8 | ** $QT_BEGIN_LICENSE:LGPL$ |
9 | ** Commercial License Usage |
10 | ** Licensees holding valid commercial Qt licenses may use this file in |
11 | ** accordance with the commercial license agreement provided with the |
12 | ** Software or, alternatively, in accordance with the terms contained in |
13 | ** a written agreement between you and The Qt Company. For licensing terms |
14 | ** and conditions see https://www.qt.io/terms-conditions. For further |
15 | ** information use the contact form at https://www.qt.io/contact-us. |
16 | ** |
17 | ** GNU Lesser General Public License Usage |
18 | ** Alternatively, this file may be used under the terms of the GNU Lesser |
19 | ** General Public License version 3 as published by the Free Software |
20 | ** Foundation and appearing in the file LICENSE.LGPL3 included in the |
21 | ** packaging of this file. Please review the following information to |
22 | ** ensure the GNU Lesser General Public License version 3 requirements |
23 | ** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. |
24 | ** |
25 | ** GNU General Public License Usage |
26 | ** Alternatively, this file may be used under the terms of the GNU |
27 | ** General Public License version 2.0 or (at your option) the GNU General |
28 | ** Public license version 3 or any later version approved by the KDE Free |
29 | ** Qt Foundation. The licenses are as published by the Free Software |
30 | ** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 |
31 | ** included in the packaging of this file. Please review the following |
32 | ** information to ensure the GNU General Public License requirements will |
33 | ** be met: https://www.gnu.org/licenses/gpl-2.0.html and |
34 | ** https://www.gnu.org/licenses/gpl-3.0.html. |
35 | ** |
36 | ** $QT_END_LICENSE$ |
37 | ** |
38 | ****************************************************************************/ |
39 | |
40 | #include "qregion.h" |
41 | #include "qpainterpath.h" |
42 | #include "qpolygon.h" |
43 | #include "qbuffer.h" |
44 | #include "qdatastream.h" |
45 | #include "qvariant.h" |
46 | #include "qvarlengtharray.h" |
47 | #include "qimage.h" |
48 | #include "qbitmap.h" |
49 | |
50 | #include <private/qdebug_p.h> |
51 | |
52 | QT_BEGIN_NAMESPACE |
53 | |
54 | /*! |
55 | \class QRegion |
56 | \brief The QRegion class specifies a clip region for a painter. |
57 | |
58 | \inmodule QtGui |
59 | \ingroup painting |
60 | \ingroup shared |
61 | |
62 | QRegion is used with QPainter::setClipRegion() to limit the paint |
63 | area to what needs to be painted. There is also a QWidget::repaint() |
64 | function that takes a QRegion parameter. QRegion is the best tool for |
65 | minimizing the amount of screen area to be updated by a repaint. |
66 | |
67 | This class is not suitable for constructing shapes for rendering, especially |
68 | as outlines. Use QPainterPath to create paths and shapes for use with |
69 | QPainter. |
70 | |
71 | QRegion is an \l{implicitly shared} class. |
72 | |
73 | \section1 Creating and Using Regions |
74 | |
75 | A region can be created from a rectangle, an ellipse, a polygon or |
76 | a bitmap. Complex regions may be created by combining simple |
77 | regions using united(), intersected(), subtracted(), or xored() (exclusive |
78 | or). You can move a region using translate(). |
79 | |
80 | You can test whether a region isEmpty() or if it |
81 | contains() a QPoint or QRect. The bounding rectangle can be found |
82 | with boundingRect(). |
83 | |
84 | Iteration over the region (with begin(), end(), or C++11 |
85 | ranged-for loops) gives a decomposition of the region into |
86 | rectangles. |
87 | |
88 | Example of using complex regions: |
89 | \snippet code/src_gui_painting_qregion.cpp 0 |
90 | |
91 | \section1 Additional License Information |
92 | |
93 | On Embedded Linux and X11 platforms, parts of this class rely on |
94 | code obtained under the following licenses: |
95 | |
96 | \legalese |
97 | Copyright (c) 1987 X Consortium |
98 | |
99 | Permission is hereby granted, free of charge, to any person obtaining a copy |
100 | of this software and associated documentation files (the "Software"), to deal |
101 | in the Software without restriction, including without limitation the rights |
102 | to use, copy, modify, merge, publish, distribute, sublicense, and/or sell |
103 | copies of the Software, and to permit persons to whom the Software is |
104 | furnished to do so, subject to the following conditions: |
105 | |
106 | The above copyright notice and this permission notice shall be included in |
107 | all copies or substantial portions of the Software. |
108 | |
109 | THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
110 | IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
111 | FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE |
112 | X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN |
113 | AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN |
114 | CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. |
115 | |
116 | Except as contained in this notice, the name of the X Consortium shall not be |
117 | used in advertising or otherwise to promote the sale, use or other dealings |
118 | in this Software without prior written authorization from the X Consortium. |
119 | \endlegalese |
120 | |
121 | \br |
122 | |
123 | \legalese |
124 | Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts. |
125 | |
126 | All Rights Reserved |
127 | |
128 | Permission to use, copy, modify, and distribute this software and its |
129 | documentation for any purpose and without fee is hereby granted, |
130 | provided that the above copyright notice appear in all copies and that |
131 | both that copyright notice and this permission notice appear in |
132 | supporting documentation, and that the name of Digital not be |
133 | used in advertising or publicity pertaining to distribution of the |
134 | software without specific, written prior permission. |
135 | |
136 | DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING |
137 | ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL |
138 | DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR |
139 | ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, |
140 | WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, |
141 | ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS |
142 | SOFTWARE. |
143 | \endlegalese |
144 | |
145 | \sa QPainter::setClipRegion(), QPainter::setClipRect(), QPainterPath |
146 | */ |
147 | |
148 | |
149 | /*! |
150 | \enum QRegion::RegionType |
151 | |
152 | Specifies the shape of the region to be created. |
153 | |
154 | \value Rectangle the region covers the entire rectangle. |
155 | \value Ellipse the region is an ellipse inside the rectangle. |
156 | */ |
157 | |
158 | /*! |
159 | \fn void QRegion::translate(const QPoint &point) |
160 | |
161 | \overload |
162 | |
163 | Translates the region \a{point}\e{.x()} along the x axis and |
164 | \a{point}\e{.y()} along the y axis, relative to the current |
165 | position. Positive values move the region to the right and down. |
166 | |
167 | Translates to the given \a point. |
168 | */ |
169 | |
170 | /***************************************************************************** |
171 | QRegion member functions |
172 | *****************************************************************************/ |
173 | |
174 | /*! |
175 | \fn QRegion::QRegion() |
176 | |
177 | Constructs an empty region. |
178 | |
179 | \sa isEmpty() |
180 | */ |
181 | |
182 | /*! |
183 | \fn QRegion::QRegion(const QRect &r, RegionType t) |
184 | \overload |
185 | |
186 | Create a region based on the rectange \a r with region type \a t. |
187 | |
188 | If the rectangle is invalid a null region will be created. |
189 | |
190 | \sa QRegion::RegionType |
191 | */ |
192 | |
193 | /*! |
194 | \fn QRegion::QRegion(const QPolygon &a, Qt::FillRule fillRule) |
195 | |
196 | Constructs a polygon region from the point array \a a with the fill rule |
197 | specified by \a fillRule. |
198 | |
199 | If \a fillRule is \l{Qt::WindingFill}, the polygon region is defined |
200 | using the winding algorithm; if it is \l{Qt::OddEvenFill}, the odd-even fill |
201 | algorithm is used. |
202 | |
203 | \warning This constructor can be used to create complex regions that will |
204 | slow down painting when used. |
205 | */ |
206 | |
207 | /*! |
208 | \fn QRegion::QRegion(const QRegion &r) |
209 | |
210 | Constructs a new region which is equal to region \a r. |
211 | */ |
212 | |
213 | /*! |
214 | \fn QRegion::QRegion(QRegion &&other) |
215 | \since 5.7 |
216 | |
217 | Move-constructs a new region from region \a other. |
218 | After the call, \a other is null. |
219 | |
220 | \sa isNull() |
221 | */ |
222 | |
223 | /*! |
224 | \fn QRegion::QRegion(const QBitmap &bm) |
225 | |
226 | Constructs a region from the bitmap \a bm. |
227 | |
228 | The resulting region consists of the pixels in bitmap \a bm that |
229 | are Qt::color1, as if each pixel was a 1 by 1 rectangle. |
230 | |
231 | This constructor may create complex regions that will slow down |
232 | painting when used. Note that drawing masked pixmaps can be done |
233 | much faster using QPixmap::setMask(). |
234 | */ |
235 | |
236 | /*! |
237 | Constructs a rectangular or elliptic region. |
238 | |
239 | If \a t is \c Rectangle, the region is the filled rectangle (\a x, |
240 | \a y, \a w, \a h). If \a t is \c Ellipse, the region is the filled |
241 | ellipse with center at (\a x + \a w / 2, \a y + \a h / 2) and size |
242 | (\a w ,\a h). |
243 | */ |
244 | QRegion::QRegion(int x, int y, int w, int h, RegionType t) |
245 | { |
246 | QRegion tmp(QRect(x, y, w, h), t); |
247 | tmp.d->ref.ref(); |
248 | d = tmp.d; |
249 | } |
250 | |
251 | /*! |
252 | \fn QRegion::~QRegion() |
253 | \internal |
254 | |
255 | Destroys the region. |
256 | */ |
257 | |
258 | void QRegion::detach() |
259 | { |
260 | if (d->ref.isShared()) |
261 | *this = copy(); |
262 | } |
263 | |
264 | // duplicates in qregion_win.cpp and qregion_wce.cpp |
265 | #define QRGN_SETRECT 1 // region stream commands |
266 | #define QRGN_SETELLIPSE 2 // (these are internal) |
267 | #define QRGN_SETPTARRAY_ALT 3 |
268 | #define QRGN_SETPTARRAY_WIND 4 |
269 | #define QRGN_TRANSLATE 5 |
270 | #define QRGN_OR 6 |
271 | #define QRGN_AND 7 |
272 | #define QRGN_SUB 8 |
273 | #define QRGN_XOR 9 |
274 | #define QRGN_RECTS 10 |
275 | |
276 | |
277 | #ifndef QT_NO_DATASTREAM |
278 | |
279 | /* |
280 | Executes region commands in the internal buffer and rebuilds the |
281 | original region. |
282 | |
283 | We do this when we read a region from the data stream. |
284 | |
285 | If \a ver is non-0, uses the format version \a ver on reading the |
286 | byte array. |
287 | */ |
288 | void QRegion::exec(const QByteArray &buffer, int ver, QDataStream::ByteOrder byteOrder) |
289 | { |
290 | QByteArray copy = buffer; |
291 | QDataStream s(©, QIODevice::ReadOnly); |
292 | if (ver) |
293 | s.setVersion(ver); |
294 | s.setByteOrder(byteOrder); |
295 | QRegion rgn; |
296 | #ifndef QT_NO_DEBUG |
297 | int test_cnt = 0; |
298 | #endif |
299 | while (!s.atEnd()) { |
300 | qint32 id; |
301 | if (s.version() == 1) { |
302 | int id_int; |
303 | s >> id_int; |
304 | id = id_int; |
305 | } else { |
306 | s >> id; |
307 | } |
308 | #ifndef QT_NO_DEBUG |
309 | if (test_cnt > 0 && id != QRGN_TRANSLATE) |
310 | qWarning("QRegion::exec: Internal error" ); |
311 | test_cnt++; |
312 | #endif |
313 | if (id == QRGN_SETRECT || id == QRGN_SETELLIPSE) { |
314 | QRect r; |
315 | s >> r; |
316 | rgn = QRegion(r, id == QRGN_SETRECT ? Rectangle : Ellipse); |
317 | } else if (id == QRGN_SETPTARRAY_ALT || id == QRGN_SETPTARRAY_WIND) { |
318 | QPolygon a; |
319 | s >> a; |
320 | rgn = QRegion(a, id == QRGN_SETPTARRAY_WIND ? Qt::WindingFill : Qt::OddEvenFill); |
321 | } else if (id == QRGN_TRANSLATE) { |
322 | QPoint p; |
323 | s >> p; |
324 | rgn.translate(p.x(), p.y()); |
325 | } else if (id >= QRGN_OR && id <= QRGN_XOR) { |
326 | QByteArray bop1, bop2; |
327 | QRegion r1, r2; |
328 | s >> bop1; |
329 | r1.exec(bop1); |
330 | s >> bop2; |
331 | r2.exec(bop2); |
332 | |
333 | switch (id) { |
334 | case QRGN_OR: |
335 | rgn = r1.united(r2); |
336 | break; |
337 | case QRGN_AND: |
338 | rgn = r1.intersected(r2); |
339 | break; |
340 | case QRGN_SUB: |
341 | rgn = r1.subtracted(r2); |
342 | break; |
343 | case QRGN_XOR: |
344 | rgn = r1.xored(r2); |
345 | break; |
346 | } |
347 | } else if (id == QRGN_RECTS) { |
348 | // (This is the only form used in Qt 2.0) |
349 | quint32 n; |
350 | s >> n; |
351 | QRect r; |
352 | for (int i=0; i<(int)n; i++) { |
353 | s >> r; |
354 | rgn = rgn.united(QRegion(r)); |
355 | } |
356 | } |
357 | } |
358 | *this = rgn; |
359 | } |
360 | |
361 | |
362 | /***************************************************************************** |
363 | QRegion stream functions |
364 | *****************************************************************************/ |
365 | |
366 | /*! |
367 | \fn QRegion &QRegion::operator=(const QRegion &r) |
368 | |
369 | Assigns \a r to this region and returns a reference to the region. |
370 | */ |
371 | |
372 | /*! |
373 | \fn QRegion &QRegion::operator=(QRegion &&other) |
374 | |
375 | Move-assigns \a other to this QRegion instance. |
376 | |
377 | \since 5.2 |
378 | */ |
379 | |
380 | /*! |
381 | \fn void QRegion::swap(QRegion &other) |
382 | \since 4.8 |
383 | |
384 | Swaps region \a other with this region. This operation is very |
385 | fast and never fails. |
386 | */ |
387 | |
388 | /*! |
389 | \relates QRegion |
390 | |
391 | Writes the region \a r to the stream \a s and returns a reference |
392 | to the stream. |
393 | |
394 | \sa{Serializing Qt Data Types}{Format of the QDataStream operators} |
395 | */ |
396 | |
397 | QDataStream &operator<<(QDataStream &s, const QRegion &r) |
398 | { |
399 | auto b = r.begin(), e = r.end(); |
400 | if (b == e) { |
401 | s << (quint32)0; |
402 | } else { |
403 | const auto size = e - b; |
404 | if (s.version() == 1) { |
405 | for (auto i = size - 1; i > 0; --i) { |
406 | s << (quint32)(12 + i * 24); |
407 | s << (int)QRGN_OR; |
408 | } |
409 | for (auto it = b; it != e; ++it) |
410 | s << (quint32)(4+8) << (int)QRGN_SETRECT << *it; |
411 | } else { |
412 | s << quint32(4 + 4 + 16 * size); // 16: storage size of QRect |
413 | s << (qint32)QRGN_RECTS; |
414 | s << quint32(size); |
415 | for (auto it = b; it != e; ++it) |
416 | s << *it; |
417 | } |
418 | } |
419 | return s; |
420 | } |
421 | |
422 | /*! |
423 | \relates QRegion |
424 | |
425 | Reads a region from the stream \a s into \a r and returns a |
426 | reference to the stream. |
427 | |
428 | \sa{Serializing Qt Data Types}{Format of the QDataStream operators} |
429 | */ |
430 | |
431 | QDataStream &operator>>(QDataStream &s, QRegion &r) |
432 | { |
433 | QByteArray b; |
434 | s >> b; |
435 | r.exec(b, s.version(), s.byteOrder()); |
436 | return s; |
437 | } |
438 | #endif //QT_NO_DATASTREAM |
439 | |
440 | #ifndef QT_NO_DEBUG_STREAM |
441 | QDebug operator<<(QDebug s, const QRegion &r) |
442 | { |
443 | QDebugStateSaver saver(s); |
444 | s.nospace(); |
445 | s << "QRegion(" ; |
446 | if (r.isNull()) { |
447 | s << "null" ; |
448 | } else if (r.isEmpty()) { |
449 | s << "empty" ; |
450 | } else { |
451 | const int count = r.rectCount(); |
452 | if (count > 1) |
453 | s << "size=" << count << ", bounds=(" ; |
454 | QtDebugUtils::formatQRect(s, r.boundingRect()); |
455 | if (count > 1) { |
456 | s << ") - [" ; |
457 | bool first = true; |
458 | for (const QRect &rect : r) { |
459 | if (!first) |
460 | s << ", " ; |
461 | s << '('; |
462 | QtDebugUtils::formatQRect(s, rect); |
463 | s << ')'; |
464 | first = false; |
465 | } |
466 | s << ']'; |
467 | } |
468 | } |
469 | s << ')'; |
470 | return s; |
471 | } |
472 | #endif |
473 | |
474 | |
475 | // These are not inline - they can be implemented better on some platforms |
476 | // (eg. Windows at least provides 3-variable operations). For now, simple. |
477 | |
478 | |
479 | /*! |
480 | Applies the united() function to this region and \a r. \c r1|r2 is |
481 | equivalent to \c r1.united(r2). |
482 | |
483 | \sa united(), operator+() |
484 | */ |
485 | #ifdef Q_COMPILER_MANGLES_RETURN_TYPE |
486 | const |
487 | #endif |
488 | QRegion QRegion::operator|(const QRegion &r) const |
489 | { return united(r); } |
490 | |
491 | /*! |
492 | Applies the united() function to this region and \a r. \c r1+r2 is |
493 | equivalent to \c r1.united(r2). |
494 | |
495 | \sa united(), operator|() |
496 | */ |
497 | #ifdef Q_COMPILER_MANGLES_RETURN_TYPE |
498 | const |
499 | #endif |
500 | QRegion QRegion::operator+(const QRegion &r) const |
501 | { return united(r); } |
502 | |
503 | /*! |
504 | \overload |
505 | \since 4.4 |
506 | */ |
507 | #ifdef Q_COMPILER_MANGLES_RETURN_TYPE |
508 | const |
509 | #endif |
510 | QRegion QRegion::operator+(const QRect &r) const |
511 | { return united(r); } |
512 | |
513 | /*! |
514 | Applies the intersected() function to this region and \a r. \c r1&r2 |
515 | is equivalent to \c r1.intersected(r2). |
516 | |
517 | \sa intersected() |
518 | */ |
519 | #ifdef Q_COMPILER_MANGLES_RETURN_TYPE |
520 | const |
521 | #endif |
522 | QRegion QRegion::operator&(const QRegion &r) const |
523 | { return intersected(r); } |
524 | |
525 | /*! |
526 | \overload |
527 | \since 4.4 |
528 | */ |
529 | #ifdef Q_COMPILER_MANGLES_RETURN_TYPE |
530 | const |
531 | #endif |
532 | QRegion QRegion::operator&(const QRect &r) const |
533 | { |
534 | return intersected(r); |
535 | } |
536 | |
537 | /*! |
538 | Applies the subtracted() function to this region and \a r. \c r1-r2 |
539 | is equivalent to \c r1.subtracted(r2). |
540 | |
541 | \sa subtracted() |
542 | */ |
543 | #ifdef Q_COMPILER_MANGLES_RETURN_TYPE |
544 | const |
545 | #endif |
546 | QRegion QRegion::operator-(const QRegion &r) const |
547 | { return subtracted(r); } |
548 | |
549 | /*! |
550 | Applies the xored() function to this region and \a r. \c r1^r2 is |
551 | equivalent to \c r1.xored(r2). |
552 | |
553 | \sa xored() |
554 | */ |
555 | #ifdef Q_COMPILER_MANGLES_RETURN_TYPE |
556 | const |
557 | #endif |
558 | QRegion QRegion::operator^(const QRegion &r) const |
559 | { return xored(r); } |
560 | |
561 | /*! |
562 | Applies the united() function to this region and \a r and assigns |
563 | the result to this region. \c r1|=r2 is equivalent to \c |
564 | {r1 = r1.united(r2)}. |
565 | |
566 | \sa united() |
567 | */ |
568 | QRegion& QRegion::operator|=(const QRegion &r) |
569 | { return *this = *this | r; } |
570 | |
571 | /*! |
572 | \fn QRegion& QRegion::operator+=(const QRect &rect) |
573 | |
574 | Returns a region that is the union of this region with the specified \a rect. |
575 | |
576 | \sa united() |
577 | */ |
578 | /*! |
579 | \fn QRegion& QRegion::operator+=(const QRegion &r) |
580 | |
581 | Applies the united() function to this region and \a r and assigns |
582 | the result to this region. \c r1+=r2 is equivalent to \c |
583 | {r1 = r1.united(r2)}. |
584 | |
585 | \sa intersected() |
586 | */ |
587 | #if !defined (Q_OS_UNIX) && !defined (Q_OS_WIN) |
588 | QRegion& QRegion::operator+=(const QRect &r) |
589 | { |
590 | return operator+=(QRegion(r)); |
591 | } |
592 | #endif |
593 | |
594 | /*! |
595 | \fn QRegion& QRegion::operator&=(const QRegion &r) |
596 | |
597 | Applies the intersected() function to this region and \a r and |
598 | assigns the result to this region. \c r1&=r2 is equivalent to \c |
599 | r1 = r1.intersected(r2). |
600 | |
601 | \sa intersected() |
602 | */ |
603 | QRegion& QRegion::operator&=(const QRegion &r) |
604 | { return *this = *this & r; } |
605 | |
606 | /*! |
607 | \overload |
608 | \since 4.4 |
609 | */ |
610 | #if defined (Q_OS_UNIX) || defined (Q_OS_WIN) |
611 | QRegion& QRegion::operator&=(const QRect &r) |
612 | { |
613 | return *this = *this & r; |
614 | } |
615 | #else |
616 | QRegion& QRegion::operator&=(const QRect &r) |
617 | { |
618 | return *this &= (QRegion(r)); |
619 | } |
620 | #endif |
621 | |
622 | /*! |
623 | \fn QRegion& QRegion::operator-=(const QRegion &r) |
624 | |
625 | Applies the subtracted() function to this region and \a r and |
626 | assigns the result to this region. \c r1-=r2 is equivalent to \c |
627 | {r1 = r1.subtracted(r2)}. |
628 | |
629 | \sa subtracted() |
630 | */ |
631 | QRegion& QRegion::operator-=(const QRegion &r) |
632 | { return *this = *this - r; } |
633 | |
634 | /*! |
635 | Applies the xored() function to this region and \a r and |
636 | assigns the result to this region. \c r1^=r2 is equivalent to \c |
637 | {r1 = r1.xored(r2)}. |
638 | |
639 | \sa xored() |
640 | */ |
641 | QRegion& QRegion::operator^=(const QRegion &r) |
642 | { return *this = *this ^ r; } |
643 | |
644 | /*! |
645 | \fn bool QRegion::operator!=(const QRegion &other) const |
646 | |
647 | Returns \c true if this region is different from the \a other region; |
648 | otherwise returns \c false. |
649 | */ |
650 | |
651 | /*! |
652 | Returns the region as a QVariant |
653 | */ |
654 | QRegion::operator QVariant() const |
655 | { |
656 | return QVariant(QVariant::Region, this); |
657 | } |
658 | |
659 | /*! |
660 | \fn bool QRegion::operator==(const QRegion &r) const |
661 | |
662 | Returns \c true if the region is equal to \a r; otherwise returns |
663 | false. |
664 | */ |
665 | |
666 | /*! |
667 | \fn void QRegion::translate(int dx, int dy) |
668 | |
669 | Translates (moves) the region \a dx along the X axis and \a dy |
670 | along the Y axis. |
671 | */ |
672 | |
673 | /*! |
674 | \fn QRegion QRegion::translated(const QPoint &p) const |
675 | \overload |
676 | \since 4.1 |
677 | |
678 | Returns a copy of the regtion that is translated \a{p}\e{.x()} |
679 | along the x axis and \a{p}\e{.y()} along the y axis, relative to |
680 | the current position. Positive values move the rectangle to the |
681 | right and down. |
682 | |
683 | \sa translate() |
684 | */ |
685 | |
686 | /*! |
687 | \since 4.1 |
688 | |
689 | Returns a copy of the region that is translated \a dx along the |
690 | x axis and \a dy along the y axis, relative to the current |
691 | position. Positive values move the region to the right and |
692 | down. |
693 | |
694 | \sa translate() |
695 | */ |
696 | |
697 | QRegion |
698 | QRegion::translated(int dx, int dy) const |
699 | { |
700 | QRegion ret(*this); |
701 | ret.translate(dx, dy); |
702 | return ret; |
703 | } |
704 | |
705 | |
706 | inline bool rect_intersects(const QRect &r1, const QRect &r2) |
707 | { |
708 | return (r1.right() >= r2.left() && r1.left() <= r2.right() && |
709 | r1.bottom() >= r2.top() && r1.top() <= r2.bottom()); |
710 | } |
711 | |
712 | /*! |
713 | \since 4.2 |
714 | |
715 | Returns \c true if this region intersects with \a region, otherwise |
716 | returns \c false. |
717 | */ |
718 | bool QRegion::intersects(const QRegion ®ion) const |
719 | { |
720 | if (isEmpty() || region.isEmpty()) |
721 | return false; |
722 | |
723 | if (!rect_intersects(boundingRect(), region.boundingRect())) |
724 | return false; |
725 | if (rectCount() == 1 && region.rectCount() == 1) |
726 | return true; |
727 | |
728 | for (const QRect &myRect : *this) |
729 | for (const QRect &otherRect : region) |
730 | if (rect_intersects(myRect, otherRect)) |
731 | return true; |
732 | return false; |
733 | } |
734 | |
735 | /*! |
736 | \fn bool QRegion::intersects(const QRect &rect) const |
737 | \since 4.2 |
738 | |
739 | Returns \c true if this region intersects with \a rect, otherwise |
740 | returns \c false. |
741 | */ |
742 | |
743 | |
744 | #if !defined (Q_OS_UNIX) && !defined (Q_OS_WIN) || defined(Q_CLANG_QDOC) |
745 | /* |
746 | \overload |
747 | \since 4.4 |
748 | */ |
749 | QRegion QRegion::intersect(const QRect &r) const |
750 | { |
751 | return intersect(QRegion(r)); |
752 | } |
753 | #endif |
754 | |
755 | /*! |
756 | \fn int QRegion::rectCount() const |
757 | \since 4.6 |
758 | |
759 | Returns the number of rectangles that this region is composed of. |
760 | Same as \c{end() - begin()}. |
761 | */ |
762 | |
763 | /*! |
764 | \fn bool QRegion::isEmpty() const |
765 | |
766 | Returns \c true if the region is empty; otherwise returns \c false. An |
767 | empty region is a region that contains no points. |
768 | |
769 | Example: |
770 | \snippet code/src_gui_painting_qregion_unix.cpp 0 |
771 | */ |
772 | |
773 | /*! |
774 | \fn bool QRegion::isNull() const |
775 | \since 5.0 |
776 | |
777 | Returns \c true if the region is empty; otherwise returns \c false. An |
778 | empty region is a region that contains no points. This function is |
779 | the same as isEmpty |
780 | |
781 | \sa isEmpty() |
782 | */ |
783 | |
784 | /*! |
785 | \fn bool QRegion::contains(const QPoint &p) const |
786 | |
787 | Returns \c true if the region contains the point \a p; otherwise |
788 | returns \c false. |
789 | */ |
790 | |
791 | /*! |
792 | \fn bool QRegion::contains(const QRect &r) const |
793 | \overload |
794 | |
795 | Returns \c true if the region overlaps the rectangle \a r; otherwise |
796 | returns \c false. |
797 | */ |
798 | |
799 | /*! |
800 | \fn QRegion QRegion::unite(const QRegion &r) const |
801 | \obsolete |
802 | |
803 | Use united(\a r) instead. |
804 | */ |
805 | |
806 | /*! |
807 | \fn QRegion QRegion::unite(const QRect &rect) const |
808 | \since 4.4 |
809 | \obsolete |
810 | |
811 | Use united(\a rect) instead. |
812 | */ |
813 | |
814 | /*! |
815 | \fn QRegion QRegion::united(const QRect &rect) const |
816 | \since 4.4 |
817 | |
818 | Returns a region which is the union of this region and the given \a rect. |
819 | |
820 | \sa intersected(), subtracted(), xored() |
821 | */ |
822 | |
823 | /*! |
824 | \fn QRegion QRegion::united(const QRegion &r) const |
825 | \since 4.2 |
826 | |
827 | Returns a region which is the union of this region and \a r. |
828 | |
829 | \image runion.png Region Union |
830 | |
831 | The figure shows the union of two elliptical regions. |
832 | |
833 | \sa intersected(), subtracted(), xored() |
834 | */ |
835 | |
836 | /*! |
837 | \fn QRegion QRegion::intersect(const QRegion &r) const |
838 | \obsolete |
839 | |
840 | Use intersected(\a r) instead. |
841 | */ |
842 | |
843 | /*! |
844 | \fn QRegion QRegion::intersect(const QRect &rect) const |
845 | \since 4.4 |
846 | \obsolete |
847 | |
848 | Use intersected(\a rect) instead. |
849 | */ |
850 | |
851 | /*! |
852 | \fn QRegion QRegion::intersected(const QRect &rect) const |
853 | \since 4.4 |
854 | |
855 | Returns a region which is the intersection of this region and the given \a rect. |
856 | |
857 | \sa subtracted(), united(), xored() |
858 | */ |
859 | |
860 | /*! |
861 | \fn QRegion QRegion::intersected(const QRegion &r) const |
862 | \since 4.2 |
863 | |
864 | Returns a region which is the intersection of this region and \a r. |
865 | |
866 | \image rintersect.png Region Intersection |
867 | |
868 | The figure shows the intersection of two elliptical regions. |
869 | |
870 | \sa subtracted(), united(), xored() |
871 | */ |
872 | |
873 | /*! |
874 | \fn QRegion QRegion::subtract(const QRegion &r) const |
875 | \obsolete |
876 | |
877 | Use subtracted(\a r) instead. |
878 | */ |
879 | |
880 | /*! |
881 | \fn QRegion QRegion::subtracted(const QRegion &r) const |
882 | \since 4.2 |
883 | |
884 | Returns a region which is \a r subtracted from this region. |
885 | |
886 | \image rsubtract.png Region Subtraction |
887 | |
888 | The figure shows the result when the ellipse on the right is |
889 | subtracted from the ellipse on the left (\c {left - right}). |
890 | |
891 | \sa intersected(), united(), xored() |
892 | */ |
893 | |
894 | /*! |
895 | \fn QRegion QRegion::eor(const QRegion &r) const |
896 | \obsolete |
897 | |
898 | Use xored(\a r) instead. |
899 | */ |
900 | |
901 | /*! |
902 | \fn QRegion QRegion::xored(const QRegion &r) const |
903 | \since 4.2 |
904 | |
905 | Returns a region which is the exclusive or (XOR) of this region |
906 | and \a r. |
907 | |
908 | \image rxor.png Region XORed |
909 | |
910 | The figure shows the exclusive or of two elliptical regions. |
911 | |
912 | \sa intersected(), united(), subtracted() |
913 | */ |
914 | |
915 | /*! |
916 | \fn QRect QRegion::boundingRect() const |
917 | |
918 | Returns the bounding rectangle of this region. An empty region |
919 | gives a rectangle that is QRect::isNull(). |
920 | */ |
921 | |
922 | #if QT_DEPRECATED_SINCE(5, 11) |
923 | /*! |
924 | \fn QVector<QRect> QRegion::rects() const |
925 | \obsolete |
926 | |
927 | Use begin() and end() instead. |
928 | |
929 | Returns an array of non-overlapping rectangles that make up the |
930 | region. |
931 | |
932 | The union of all the rectangles is equal to the original region. |
933 | */ |
934 | #endif |
935 | |
936 | /*! |
937 | \typedef QRegion::const_iterator |
938 | \since 5.8 |
939 | |
940 | An iterator over the non-overlapping rectangles that make up the |
941 | region. |
942 | |
943 | The union of all the rectangles is equal to the original region. |
944 | |
945 | QRegion does not offer mutable iterators. |
946 | |
947 | \sa begin(), end() |
948 | */ |
949 | |
950 | /*! |
951 | \typedef QRegion::const_reverse_iterator |
952 | \since 5.8 |
953 | |
954 | A reverse iterator over the non-overlapping rectangles that make up the |
955 | region. |
956 | |
957 | The union of all the rectangles is equal to the original region. |
958 | |
959 | QRegion does not offer mutable iterators. |
960 | |
961 | \sa rbegin(), rend() |
962 | */ |
963 | |
964 | /*! |
965 | \fn QRegion::begin() const |
966 | \since 5.8 |
967 | |
968 | Returns a const_iterator pointing to the beginning of the range of |
969 | non-overlapping rectangles that make up the region. |
970 | |
971 | The union of all the rectangles is equal to the original region. |
972 | |
973 | \sa rbegin(), cbegin(), end() |
974 | */ |
975 | |
976 | /*! |
977 | \fn QRegion::cbegin() const |
978 | \since 5.8 |
979 | |
980 | Same as begin(). |
981 | */ |
982 | |
983 | /*! |
984 | \fn QRegion::end() const |
985 | \since 5.8 |
986 | |
987 | Returns a const_iterator pointing to one past the end of |
988 | non-overlapping rectangles that make up the region. |
989 | |
990 | The union of all the rectangles is equal to the original region. |
991 | |
992 | \sa rend(), cend(), begin() |
993 | */ |
994 | |
995 | /*! |
996 | \fn QRegion::cend() const |
997 | \since 5.8 |
998 | |
999 | Same as end(). |
1000 | */ |
1001 | |
1002 | /*! |
1003 | \fn QRegion::rbegin() const |
1004 | \since 5.8 |
1005 | |
1006 | Returns a const_reverse_iterator pointing to the beginning of the |
1007 | range of non-overlapping rectangles that make up the region. |
1008 | |
1009 | The union of all the rectangles is equal to the original region. |
1010 | |
1011 | \sa begin(), crbegin(), rend() |
1012 | */ |
1013 | |
1014 | /*! |
1015 | \fn QRegion::crbegin() const |
1016 | \since 5.8 |
1017 | |
1018 | Same as rbegin(). |
1019 | */ |
1020 | |
1021 | /*! |
1022 | \fn QRegion::rend() const |
1023 | \since 5.8 |
1024 | |
1025 | Returns a const_reverse_iterator pointing to one past the end of |
1026 | the range of non-overlapping rectangles that make up the region. |
1027 | |
1028 | The union of all the rectangles is equal to the original region. |
1029 | |
1030 | \sa end(), crend(), rbegin() |
1031 | */ |
1032 | |
1033 | /*! |
1034 | \fn QRegion::crend() const |
1035 | \since 5.8 |
1036 | |
1037 | Same as rend(). |
1038 | */ |
1039 | |
1040 | /*! |
1041 | \fn void QRegion::setRects(const QRect *rects, int number) |
1042 | |
1043 | Sets the region using the array of rectangles specified by \a rects and |
1044 | \a number. |
1045 | The rectangles \e must be optimally Y-X sorted and follow these restrictions: |
1046 | |
1047 | \list |
1048 | \li The rectangles must not intersect. |
1049 | \li All rectangles with a given top coordinate must have the same height. |
1050 | \li No two rectangles may abut horizontally (they should be combined |
1051 | into a single wider rectangle in that case). |
1052 | \li The rectangles must be sorted in ascending order, with Y as the major |
1053 | sort key and X as the minor sort key. |
1054 | \endlist |
1055 | \omit |
1056 | Only some platforms have these restrictions (Qt for Embedded Linux, X11 and \macos). |
1057 | \endomit |
1058 | */ |
1059 | |
1060 | namespace { |
1061 | |
1062 | struct Segment |
1063 | { |
1064 | Segment() {} |
1065 | Segment(const QPoint &p) |
1066 | : added(false) |
1067 | , point(p) |
1068 | { |
1069 | } |
1070 | |
1071 | int left() const |
1072 | { |
1073 | return qMin(point.x(), next->point.x()); |
1074 | } |
1075 | |
1076 | int right() const |
1077 | { |
1078 | return qMax(point.x(), next->point.x()); |
1079 | } |
1080 | |
1081 | bool overlaps(const Segment &other) const |
1082 | { |
1083 | return left() < other.right() && other.left() < right(); |
1084 | } |
1085 | |
1086 | void connect(Segment &other) |
1087 | { |
1088 | next = &other; |
1089 | other.prev = this; |
1090 | |
1091 | horizontal = (point.y() == other.point.y()); |
1092 | } |
1093 | |
1094 | void merge(Segment &other) |
1095 | { |
1096 | if (right() <= other.right()) { |
1097 | QPoint p = other.point; |
1098 | Segment *oprev = other.prev; |
1099 | |
1100 | other.point = point; |
1101 | other.prev = prev; |
1102 | prev->next = &other; |
1103 | |
1104 | point = p; |
1105 | prev = oprev; |
1106 | oprev->next = this; |
1107 | } else { |
1108 | Segment *onext = other.next; |
1109 | other.next = next; |
1110 | next->prev = &other; |
1111 | |
1112 | next = onext; |
1113 | next->prev = this; |
1114 | } |
1115 | } |
1116 | |
1117 | int horizontal : 1; |
1118 | int added : 1; |
1119 | |
1120 | QPoint point; |
1121 | Segment *prev; |
1122 | Segment *next; |
1123 | }; |
1124 | |
1125 | void mergeSegments(Segment *a, int na, Segment *b, int nb) |
1126 | { |
1127 | int i = 0; |
1128 | int j = 0; |
1129 | |
1130 | while (i != na && j != nb) { |
1131 | Segment &sa = a[i]; |
1132 | Segment &sb = b[j]; |
1133 | const int ra = sa.right(); |
1134 | const int rb = sb.right(); |
1135 | if (sa.overlaps(sb)) |
1136 | sa.merge(sb); |
1137 | i += (rb >= ra); |
1138 | j += (ra >= rb); |
1139 | } |
1140 | } |
1141 | |
1142 | void addSegmentsToPath(Segment *segment, QPainterPath &path) |
1143 | { |
1144 | Segment *current = segment; |
1145 | path.moveTo(current->point); |
1146 | |
1147 | current->added = true; |
1148 | |
1149 | Segment *last = current; |
1150 | current = current->next; |
1151 | while (current != segment) { |
1152 | if (current->horizontal != last->horizontal) |
1153 | path.lineTo(current->point); |
1154 | current->added = true; |
1155 | last = current; |
1156 | current = current->next; |
1157 | } |
1158 | } |
1159 | |
1160 | } // unnamed namespace |
1161 | |
1162 | // the following is really a lie, because Segments cannot be relocated, as they |
1163 | // reference each other by address. For the same reason, they aren't even copyable, |
1164 | // but the code works with the compiler-generated (wrong) copy and move special |
1165 | // members, so use this as an optimization. The only container these are used in |
1166 | // (a QVarLengthArray in qt_regionToPath()) is resized once up-front, so doesn't |
1167 | // have a problem with this, but benefits from not having to run Segment ctors: |
1168 | Q_DECLARE_TYPEINFO(Segment, Q_PRIMITIVE_TYPE); |
1169 | |
1170 | Q_GUI_EXPORT QPainterPath qt_regionToPath(const QRegion ®ion) |
1171 | { |
1172 | QPainterPath result; |
1173 | if (region.rectCount() == 1) { |
1174 | result.addRect(region.boundingRect()); |
1175 | return result; |
1176 | } |
1177 | |
1178 | auto rect = region.begin(); |
1179 | const auto end = region.end(); |
1180 | |
1181 | QVarLengthArray<Segment> segments; |
1182 | segments.resize(4 * (end - rect)); |
1183 | |
1184 | int lastRowSegmentCount = 0; |
1185 | Segment *lastRowSegments = 0; |
1186 | |
1187 | int lastSegment = 0; |
1188 | int lastY = 0; |
1189 | while (rect != end) { |
1190 | const int y = rect[0].y(); |
1191 | int count = 0; |
1192 | while (&rect[count] != end && rect[count].y() == y) |
1193 | ++count; |
1194 | |
1195 | for (int i = 0; i < count; ++i) { |
1196 | int offset = lastSegment + i; |
1197 | segments[offset] = Segment(rect[i].topLeft()); |
1198 | segments[offset += count] = Segment(rect[i].topRight() + QPoint(1, 0)); |
1199 | segments[offset += count] = Segment(rect[i].bottomRight() + QPoint(1, 1)); |
1200 | segments[offset += count] = Segment(rect[i].bottomLeft() + QPoint(0, 1)); |
1201 | |
1202 | offset = lastSegment + i; |
1203 | for (int j = 0; j < 4; ++j) |
1204 | segments[offset + j * count].connect(segments[offset + ((j + 1) % 4) * count]); |
1205 | } |
1206 | |
1207 | if (lastRowSegments && lastY == y) |
1208 | mergeSegments(lastRowSegments, lastRowSegmentCount, &segments[lastSegment], count); |
1209 | |
1210 | lastRowSegments = &segments[lastSegment + 2 * count]; |
1211 | lastRowSegmentCount = count; |
1212 | lastSegment += 4 * count; |
1213 | lastY = y + rect[0].height(); |
1214 | rect += count; |
1215 | } |
1216 | |
1217 | for (int i = 0; i < lastSegment; ++i) { |
1218 | Segment *segment = &segments[i]; |
1219 | if (!segment->added) |
1220 | addSegmentsToPath(segment, result); |
1221 | } |
1222 | |
1223 | return result; |
1224 | } |
1225 | |
1226 | #if defined(Q_OS_UNIX) || defined(Q_OS_WIN) |
1227 | |
1228 | //#define QT_REGION_DEBUG |
1229 | /* |
1230 | * clip region |
1231 | */ |
1232 | |
1233 | struct QRegionPrivate { |
1234 | int numRects; |
1235 | int innerArea; |
1236 | QVector<QRect> rects; |
1237 | QRect extents; |
1238 | QRect innerRect; |
1239 | |
1240 | inline QRegionPrivate() : numRects(0), innerArea(-1) {} |
1241 | inline QRegionPrivate(const QRect &r) |
1242 | : numRects(1), |
1243 | innerArea(r.width() * r.height()), |
1244 | extents(r), |
1245 | innerRect(r) |
1246 | { |
1247 | } |
1248 | |
1249 | void intersect(const QRect &r); |
1250 | |
1251 | /* |
1252 | * Returns \c true if r is guaranteed to be fully contained in this region. |
1253 | * A false return value does not guarantee the opposite. |
1254 | */ |
1255 | inline bool contains(const QRegionPrivate &r) const { |
1256 | return contains(r.extents); |
1257 | } |
1258 | |
1259 | inline bool contains(const QRect &r2) const { |
1260 | const QRect &r1 = innerRect; |
1261 | return r2.left() >= r1.left() && r2.right() <= r1.right() |
1262 | && r2.top() >= r1.top() && r2.bottom() <= r1.bottom(); |
1263 | } |
1264 | |
1265 | /* |
1266 | * Returns \c true if this region is guaranteed to be fully contained in r. |
1267 | */ |
1268 | inline bool within(const QRect &r1) const { |
1269 | const QRect &r2 = extents; |
1270 | return r2.left() >= r1.left() && r2.right() <= r1.right() |
1271 | && r2.top() >= r1.top() && r2.bottom() <= r1.bottom(); |
1272 | } |
1273 | |
1274 | inline void updateInnerRect(const QRect &rect) { |
1275 | const int area = rect.width() * rect.height(); |
1276 | if (area > innerArea) { |
1277 | innerArea = area; |
1278 | innerRect = rect; |
1279 | } |
1280 | } |
1281 | |
1282 | inline void vectorize() { |
1283 | if (numRects == 1) { |
1284 | if (!rects.size()) |
1285 | rects.resize(1); |
1286 | rects[0] = extents; |
1287 | } |
1288 | } |
1289 | |
1290 | const QRect *begin() const noexcept |
1291 | { return numRects == 1 ? &extents : rects.data(); } // avoid vectorize() |
1292 | |
1293 | const QRect *end() const noexcept |
1294 | { return begin() + numRects; } |
1295 | |
1296 | inline void append(const QRect *r); |
1297 | void append(const QRegionPrivate *r); |
1298 | void prepend(const QRect *r); |
1299 | void prepend(const QRegionPrivate *r); |
1300 | inline bool canAppend(const QRect *r) const; |
1301 | inline bool canAppend(const QRegionPrivate *r) const; |
1302 | inline bool canPrepend(const QRect *r) const; |
1303 | inline bool canPrepend(const QRegionPrivate *r) const; |
1304 | |
1305 | inline bool mergeFromRight(QRect *left, const QRect *right); |
1306 | inline bool mergeFromLeft(QRect *left, const QRect *right); |
1307 | inline bool mergeFromBelow(QRect *top, const QRect *bottom, |
1308 | const QRect *nextToTop, |
1309 | const QRect *nextToBottom); |
1310 | inline bool mergeFromAbove(QRect *bottom, const QRect *top, |
1311 | const QRect *nextToBottom, |
1312 | const QRect *nextToTop); |
1313 | |
1314 | #ifdef QT_REGION_DEBUG |
1315 | void selfTest() const; |
1316 | #endif |
1317 | }; |
1318 | |
1319 | static inline bool isEmptyHelper(const QRegionPrivate *preg) |
1320 | { |
1321 | return !preg || preg->numRects == 0; |
1322 | } |
1323 | |
1324 | static inline bool canMergeFromRight(const QRect *left, const QRect *right) |
1325 | { |
1326 | return (right->top() == left->top() |
1327 | && right->bottom() == left->bottom() |
1328 | && right->left() <= (left->right() + 1)); |
1329 | } |
1330 | |
1331 | static inline bool canMergeFromLeft(const QRect *right, const QRect *left) |
1332 | { |
1333 | return canMergeFromRight(left, right); |
1334 | } |
1335 | |
1336 | bool QRegionPrivate::mergeFromRight(QRect *left, const QRect *right) |
1337 | { |
1338 | if (canMergeFromRight(left, right)) { |
1339 | left->setRight(right->right()); |
1340 | updateInnerRect(*left); |
1341 | return true; |
1342 | } |
1343 | return false; |
1344 | } |
1345 | |
1346 | bool QRegionPrivate::mergeFromLeft(QRect *right, const QRect *left) |
1347 | { |
1348 | if (canMergeFromLeft(right, left)) { |
1349 | right->setLeft(left->left()); |
1350 | updateInnerRect(*right); |
1351 | return true; |
1352 | } |
1353 | return false; |
1354 | } |
1355 | |
1356 | static inline bool canMergeFromBelow(const QRect *top, const QRect *bottom, |
1357 | const QRect *nextToTop, |
1358 | const QRect *nextToBottom) |
1359 | { |
1360 | if (nextToTop && nextToTop->y() == top->y()) |
1361 | return false; |
1362 | if (nextToBottom && nextToBottom->y() == bottom->y()) |
1363 | return false; |
1364 | |
1365 | return ((top->bottom() >= (bottom->top() - 1)) |
1366 | && top->left() == bottom->left() |
1367 | && top->right() == bottom->right()); |
1368 | } |
1369 | |
1370 | bool QRegionPrivate::mergeFromBelow(QRect *top, const QRect *bottom, |
1371 | const QRect *nextToTop, |
1372 | const QRect *nextToBottom) |
1373 | { |
1374 | if (canMergeFromBelow(top, bottom, nextToTop, nextToBottom)) { |
1375 | top->setBottom(bottom->bottom()); |
1376 | updateInnerRect(*top); |
1377 | return true; |
1378 | } |
1379 | return false; |
1380 | } |
1381 | |
1382 | bool QRegionPrivate::mergeFromAbove(QRect *bottom, const QRect *top, |
1383 | const QRect *nextToBottom, |
1384 | const QRect *nextToTop) |
1385 | { |
1386 | if (canMergeFromBelow(top, bottom, nextToTop, nextToBottom)) { |
1387 | bottom->setTop(top->top()); |
1388 | updateInnerRect(*bottom); |
1389 | return true; |
1390 | } |
1391 | return false; |
1392 | } |
1393 | |
1394 | static inline QRect qt_rect_intersect_normalized(const QRect &r1, |
1395 | const QRect &r2) |
1396 | { |
1397 | QRect r; |
1398 | r.setLeft(qMax(r1.left(), r2.left())); |
1399 | r.setRight(qMin(r1.right(), r2.right())); |
1400 | r.setTop(qMax(r1.top(), r2.top())); |
1401 | r.setBottom(qMin(r1.bottom(), r2.bottom())); |
1402 | return r; |
1403 | } |
1404 | |
1405 | void QRegionPrivate::intersect(const QRect &rect) |
1406 | { |
1407 | Q_ASSERT(extents.intersects(rect)); |
1408 | Q_ASSERT(numRects > 1); |
1409 | |
1410 | #ifdef QT_REGION_DEBUG |
1411 | selfTest(); |
1412 | #endif |
1413 | |
1414 | const QRect r = rect.normalized(); |
1415 | extents = QRect(); |
1416 | innerRect = QRect(); |
1417 | innerArea = -1; |
1418 | |
1419 | QRect *dest = rects.data(); |
1420 | const QRect *src = dest; |
1421 | int n = numRects; |
1422 | numRects = 0; |
1423 | while (n--) { |
1424 | *dest = qt_rect_intersect_normalized(*src++, r); |
1425 | if (dest->isEmpty()) |
1426 | continue; |
1427 | |
1428 | if (numRects == 0) { |
1429 | extents = *dest; |
1430 | } else { |
1431 | extents.setLeft(qMin(extents.left(), dest->left())); |
1432 | // hw: extents.top() will never change after initialization |
1433 | //extents.setTop(qMin(extents.top(), dest->top())); |
1434 | extents.setRight(qMax(extents.right(), dest->right())); |
1435 | extents.setBottom(qMax(extents.bottom(), dest->bottom())); |
1436 | |
1437 | const QRect *nextToLast = (numRects > 1 ? dest - 2 : 0); |
1438 | |
1439 | // mergeFromBelow inlined and optimized |
1440 | if (canMergeFromBelow(dest - 1, dest, nextToLast, 0)) { |
1441 | if (!n || src->y() != dest->y() || src->left() > r.right()) { |
1442 | QRect *prev = dest - 1; |
1443 | prev->setBottom(dest->bottom()); |
1444 | updateInnerRect(*prev); |
1445 | continue; |
1446 | } |
1447 | } |
1448 | } |
1449 | updateInnerRect(*dest); |
1450 | ++dest; |
1451 | ++numRects; |
1452 | } |
1453 | #ifdef QT_REGION_DEBUG |
1454 | selfTest(); |
1455 | #endif |
1456 | } |
1457 | |
1458 | void QRegionPrivate::append(const QRect *r) |
1459 | { |
1460 | Q_ASSERT(!r->isEmpty()); |
1461 | |
1462 | QRect *myLast = (numRects == 1 ? &extents : rects.data() + (numRects - 1)); |
1463 | if (mergeFromRight(myLast, r)) { |
1464 | if (numRects > 1) { |
1465 | const QRect *nextToTop = (numRects > 2 ? myLast - 2 : 0); |
1466 | if (mergeFromBelow(myLast - 1, myLast, nextToTop, 0)) |
1467 | --numRects; |
1468 | } |
1469 | } else if (mergeFromBelow(myLast, r, (numRects > 1 ? myLast - 1 : 0), 0)) { |
1470 | // nothing |
1471 | } else { |
1472 | vectorize(); |
1473 | ++numRects; |
1474 | updateInnerRect(*r); |
1475 | if (rects.size() < numRects) |
1476 | rects.resize(numRects); |
1477 | rects[numRects - 1] = *r; |
1478 | } |
1479 | extents.setCoords(qMin(extents.left(), r->left()), |
1480 | qMin(extents.top(), r->top()), |
1481 | qMax(extents.right(), r->right()), |
1482 | qMax(extents.bottom(), r->bottom())); |
1483 | |
1484 | #ifdef QT_REGION_DEBUG |
1485 | selfTest(); |
1486 | #endif |
1487 | } |
1488 | |
1489 | void QRegionPrivate::append(const QRegionPrivate *r) |
1490 | { |
1491 | Q_ASSERT(!isEmptyHelper(r)); |
1492 | |
1493 | if (r->numRects == 1) { |
1494 | append(&r->extents); |
1495 | return; |
1496 | } |
1497 | |
1498 | vectorize(); |
1499 | |
1500 | QRect *destRect = rects.data() + numRects; |
1501 | const QRect *srcRect = r->rects.constData(); |
1502 | int numAppend = r->numRects; |
1503 | |
1504 | // try merging |
1505 | { |
1506 | const QRect *rFirst = srcRect; |
1507 | QRect *myLast = destRect - 1; |
1508 | const QRect *nextToLast = (numRects > 1 ? myLast - 1 : 0); |
1509 | if (mergeFromRight(myLast, rFirst)) { |
1510 | ++srcRect; |
1511 | --numAppend; |
1512 | const QRect *rNextToFirst = (numAppend > 1 ? rFirst + 2 : 0); |
1513 | if (mergeFromBelow(myLast, rFirst + 1, nextToLast, rNextToFirst)) { |
1514 | ++srcRect; |
1515 | --numAppend; |
1516 | } |
1517 | if (numRects > 1) { |
1518 | nextToLast = (numRects > 2 ? myLast - 2 : 0); |
1519 | rNextToFirst = (numAppend > 0 ? srcRect : 0); |
1520 | if (mergeFromBelow(myLast - 1, myLast, nextToLast, rNextToFirst)) { |
1521 | --destRect; |
1522 | --numRects; |
1523 | } |
1524 | } |
1525 | } else if (mergeFromBelow(myLast, rFirst, nextToLast, rFirst + 1)) { |
1526 | ++srcRect; |
1527 | --numAppend; |
1528 | } |
1529 | } |
1530 | |
1531 | // append rectangles |
1532 | if (numAppend > 0) { |
1533 | const int newNumRects = numRects + numAppend; |
1534 | if (newNumRects > rects.size()) { |
1535 | rects.resize(newNumRects); |
1536 | destRect = rects.data() + numRects; |
1537 | } |
1538 | memcpy(destRect, srcRect, numAppend * sizeof(QRect)); |
1539 | |
1540 | numRects = newNumRects; |
1541 | } |
1542 | |
1543 | // update inner rectangle |
1544 | if (innerArea < r->innerArea) { |
1545 | innerArea = r->innerArea; |
1546 | innerRect = r->innerRect; |
1547 | } |
1548 | |
1549 | // update extents |
1550 | destRect = &extents; |
1551 | srcRect = &r->extents; |
1552 | extents.setCoords(qMin(destRect->left(), srcRect->left()), |
1553 | qMin(destRect->top(), srcRect->top()), |
1554 | qMax(destRect->right(), srcRect->right()), |
1555 | qMax(destRect->bottom(), srcRect->bottom())); |
1556 | |
1557 | #ifdef QT_REGION_DEBUG |
1558 | selfTest(); |
1559 | #endif |
1560 | } |
1561 | |
1562 | void QRegionPrivate::prepend(const QRegionPrivate *r) |
1563 | { |
1564 | Q_ASSERT(!isEmptyHelper(r)); |
1565 | |
1566 | if (r->numRects == 1) { |
1567 | prepend(&r->extents); |
1568 | return; |
1569 | } |
1570 | |
1571 | vectorize(); |
1572 | |
1573 | int numPrepend = r->numRects; |
1574 | int numSkip = 0; |
1575 | |
1576 | // try merging |
1577 | { |
1578 | QRect *myFirst = rects.data(); |
1579 | const QRect *nextToFirst = (numRects > 1 ? myFirst + 1 : 0); |
1580 | const QRect *rLast = r->rects.constData() + r->numRects - 1; |
1581 | const QRect *rNextToLast = (r->numRects > 1 ? rLast - 1 : 0); |
1582 | if (mergeFromLeft(myFirst, rLast)) { |
1583 | --numPrepend; |
1584 | --rLast; |
1585 | rNextToLast = (numPrepend > 1 ? rLast - 1 : 0); |
1586 | if (mergeFromAbove(myFirst, rLast, nextToFirst, rNextToLast)) { |
1587 | --numPrepend; |
1588 | --rLast; |
1589 | } |
1590 | if (numRects > 1) { |
1591 | nextToFirst = (numRects > 2? myFirst + 2 : 0); |
1592 | rNextToLast = (numPrepend > 0 ? rLast : 0); |
1593 | if (mergeFromAbove(myFirst + 1, myFirst, nextToFirst, rNextToLast)) { |
1594 | --numRects; |
1595 | ++numSkip; |
1596 | } |
1597 | } |
1598 | } else if (mergeFromAbove(myFirst, rLast, nextToFirst, rNextToLast)) { |
1599 | --numPrepend; |
1600 | } |
1601 | } |
1602 | |
1603 | if (numPrepend > 0) { |
1604 | const int newNumRects = numRects + numPrepend; |
1605 | if (newNumRects > rects.size()) |
1606 | rects.resize(newNumRects); |
1607 | |
1608 | // move existing rectangles |
1609 | memmove(rects.data() + numPrepend, rects.constData() + numSkip, |
1610 | numRects * sizeof(QRect)); |
1611 | |
1612 | // prepend new rectangles |
1613 | memcpy(rects.data(), r->rects.constData(), numPrepend * sizeof(QRect)); |
1614 | |
1615 | numRects = newNumRects; |
1616 | } |
1617 | |
1618 | // update inner rectangle |
1619 | if (innerArea < r->innerArea) { |
1620 | innerArea = r->innerArea; |
1621 | innerRect = r->innerRect; |
1622 | } |
1623 | |
1624 | // update extents |
1625 | extents.setCoords(qMin(extents.left(), r->extents.left()), |
1626 | qMin(extents.top(), r->extents.top()), |
1627 | qMax(extents.right(), r->extents.right()), |
1628 | qMax(extents.bottom(), r->extents.bottom())); |
1629 | |
1630 | #ifdef QT_REGION_DEBUG |
1631 | selfTest(); |
1632 | #endif |
1633 | } |
1634 | |
1635 | void QRegionPrivate::prepend(const QRect *r) |
1636 | { |
1637 | Q_ASSERT(!r->isEmpty()); |
1638 | |
1639 | QRect *myFirst = (numRects == 1 ? &extents : rects.data()); |
1640 | if (mergeFromLeft(myFirst, r)) { |
1641 | if (numRects > 1) { |
1642 | const QRect *nextToFirst = (numRects > 2 ? myFirst + 2 : 0); |
1643 | if (mergeFromAbove(myFirst + 1, myFirst, nextToFirst, 0)) { |
1644 | --numRects; |
1645 | memmove(rects.data(), rects.constData() + 1, |
1646 | numRects * sizeof(QRect)); |
1647 | } |
1648 | } |
1649 | } else if (mergeFromAbove(myFirst, r, (numRects > 1 ? myFirst + 1 : 0), 0)) { |
1650 | // nothing |
1651 | } else { |
1652 | vectorize(); |
1653 | ++numRects; |
1654 | updateInnerRect(*r); |
1655 | rects.prepend(*r); |
1656 | } |
1657 | extents.setCoords(qMin(extents.left(), r->left()), |
1658 | qMin(extents.top(), r->top()), |
1659 | qMax(extents.right(), r->right()), |
1660 | qMax(extents.bottom(), r->bottom())); |
1661 | |
1662 | #ifdef QT_REGION_DEBUG |
1663 | selfTest(); |
1664 | #endif |
1665 | } |
1666 | |
1667 | bool QRegionPrivate::canAppend(const QRect *r) const |
1668 | { |
1669 | Q_ASSERT(!r->isEmpty()); |
1670 | |
1671 | const QRect *myLast = (numRects == 1) ? &extents : (rects.constData() + (numRects - 1)); |
1672 | if (r->top() > myLast->bottom()) |
1673 | return true; |
1674 | if (r->top() == myLast->top() |
1675 | && r->height() == myLast->height() |
1676 | && r->left() > myLast->right()) |
1677 | { |
1678 | return true; |
1679 | } |
1680 | |
1681 | return false; |
1682 | } |
1683 | |
1684 | bool QRegionPrivate::canAppend(const QRegionPrivate *r) const |
1685 | { |
1686 | return canAppend(r->numRects == 1 ? &r->extents : r->rects.constData()); |
1687 | } |
1688 | |
1689 | bool QRegionPrivate::canPrepend(const QRect *r) const |
1690 | { |
1691 | Q_ASSERT(!r->isEmpty()); |
1692 | |
1693 | const QRect *myFirst = (numRects == 1) ? &extents : rects.constData(); |
1694 | if (r->bottom() < myFirst->top()) // not overlapping |
1695 | return true; |
1696 | if (r->top() == myFirst->top() |
1697 | && r->height() == myFirst->height() |
1698 | && r->right() < myFirst->left()) |
1699 | { |
1700 | return true; |
1701 | } |
1702 | |
1703 | return false; |
1704 | } |
1705 | |
1706 | bool QRegionPrivate::canPrepend(const QRegionPrivate *r) const |
1707 | { |
1708 | return canPrepend(r->numRects == 1 ? &r->extents : r->rects.constData() + r->numRects - 1); |
1709 | } |
1710 | |
1711 | #ifdef QT_REGION_DEBUG |
1712 | void QRegionPrivate::selfTest() const |
1713 | { |
1714 | if (numRects == 0) { |
1715 | Q_ASSERT(extents.isEmpty()); |
1716 | Q_ASSERT(innerRect.isEmpty()); |
1717 | return; |
1718 | } |
1719 | |
1720 | Q_ASSERT(innerArea == (innerRect.width() * innerRect.height())); |
1721 | |
1722 | if (numRects == 1) { |
1723 | Q_ASSERT(innerRect == extents); |
1724 | Q_ASSERT(!innerRect.isEmpty()); |
1725 | return; |
1726 | } |
1727 | |
1728 | for (int i = 0; i < numRects; ++i) { |
1729 | const QRect r = rects.at(i); |
1730 | if ((r.width() * r.height()) > innerArea) |
1731 | qDebug() << "selfTest(): innerRect" << innerRect << '<' << r; |
1732 | } |
1733 | |
1734 | QRect r = rects.first(); |
1735 | for (int i = 1; i < numRects; ++i) { |
1736 | const QRect r2 = rects.at(i); |
1737 | Q_ASSERT(!r2.isEmpty()); |
1738 | if (r2.y() == r.y()) { |
1739 | Q_ASSERT(r.bottom() == r2.bottom()); |
1740 | Q_ASSERT(r.right() < (r2.left() + 1)); |
1741 | } else { |
1742 | Q_ASSERT(r2.y() >= r.bottom()); |
1743 | } |
1744 | r = r2; |
1745 | } |
1746 | } |
1747 | #endif // QT_REGION_DEBUG |
1748 | |
1749 | static QRegionPrivate qrp; |
1750 | const QRegion::QRegionData QRegion::shared_empty = {Q_REFCOUNT_INITIALIZE_STATIC, &qrp}; |
1751 | |
1752 | typedef void (*OverlapFunc)(QRegionPrivate &dest, const QRect *r1, const QRect *r1End, |
1753 | const QRect *r2, const QRect *r2End, int y1, int y2); |
1754 | typedef void (*NonOverlapFunc)(QRegionPrivate &dest, const QRect *r, const QRect *rEnd, |
1755 | int y1, int y2); |
1756 | |
1757 | static bool EqualRegion(const QRegionPrivate *r1, const QRegionPrivate *r2); |
1758 | static void UnionRegion(const QRegionPrivate *reg1, const QRegionPrivate *reg2, QRegionPrivate &dest); |
1759 | static void miRegionOp(QRegionPrivate &dest, const QRegionPrivate *reg1, const QRegionPrivate *reg2, |
1760 | OverlapFunc overlapFunc, NonOverlapFunc nonOverlap1Func, |
1761 | NonOverlapFunc nonOverlap2Func); |
1762 | |
1763 | #define RectangleOut 0 |
1764 | #define RectangleIn 1 |
1765 | #define RectanglePart 2 |
1766 | #define EvenOddRule 0 |
1767 | #define WindingRule 1 |
1768 | |
1769 | // START OF region.h extract |
1770 | /* $XConsortium: region.h,v 11.14 94/04/17 20:22:20 rws Exp $ */ |
1771 | /************************************************************************ |
1772 | |
1773 | Copyright (c) 1987 X Consortium |
1774 | |
1775 | Permission is hereby granted, free of charge, to any person obtaining a copy |
1776 | of this software and associated documentation files (the "Software"), to deal |
1777 | in the Software without restriction, including without limitation the rights |
1778 | to use, copy, modify, merge, publish, distribute, sublicense, and/or sell |
1779 | copies of the Software, and to permit persons to whom the Software is |
1780 | furnished to do so, subject to the following conditions: |
1781 | |
1782 | The above copyright notice and this permission notice shall be included in |
1783 | all copies or substantial portions of the Software. |
1784 | |
1785 | THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
1786 | IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
1787 | FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE |
1788 | X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN |
1789 | AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN |
1790 | CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. |
1791 | |
1792 | Except as contained in this notice, the name of the X Consortium shall not be |
1793 | used in advertising or otherwise to promote the sale, use or other dealings |
1794 | in this Software without prior written authorization from the X Consortium. |
1795 | |
1796 | |
1797 | Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts. |
1798 | |
1799 | All Rights Reserved |
1800 | |
1801 | Permission to use, copy, modify, and distribute this software and its |
1802 | documentation for any purpose and without fee is hereby granted, |
1803 | provided that the above copyright notice appear in all copies and that |
1804 | both that copyright notice and this permission notice appear in |
1805 | supporting documentation, and that the name of Digital not be |
1806 | used in advertising or publicity pertaining to distribution of the |
1807 | software without specific, written prior permission. |
1808 | |
1809 | DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING |
1810 | ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL |
1811 | DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR |
1812 | ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, |
1813 | WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, |
1814 | ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS |
1815 | SOFTWARE. |
1816 | |
1817 | ************************************************************************/ |
1818 | |
1819 | #ifndef _XREGION_H |
1820 | #define _XREGION_H |
1821 | |
1822 | QT_BEGIN_INCLUDE_NAMESPACE |
1823 | #include <limits.h> |
1824 | QT_END_INCLUDE_NAMESPACE |
1825 | |
1826 | /* 1 if two BOXes overlap. |
1827 | * 0 if two BOXes do not overlap. |
1828 | * Remember, x2 and y2 are not in the region |
1829 | */ |
1830 | #define EXTENTCHECK(r1, r2) \ |
1831 | ((r1)->right() >= (r2)->left() && \ |
1832 | (r1)->left() <= (r2)->right() && \ |
1833 | (r1)->bottom() >= (r2)->top() && \ |
1834 | (r1)->top() <= (r2)->bottom()) |
1835 | |
1836 | /* |
1837 | * update region extents |
1838 | */ |
1839 | #define EXTENTS(r,idRect){\ |
1840 | if((r)->left() < (idRect)->extents.left())\ |
1841 | (idRect)->extents.setLeft((r)->left());\ |
1842 | if((r)->top() < (idRect)->extents.top())\ |
1843 | (idRect)->extents.setTop((r)->top());\ |
1844 | if((r)->right() > (idRect)->extents.right())\ |
1845 | (idRect)->extents.setRight((r)->right());\ |
1846 | if((r)->bottom() > (idRect)->extents.bottom())\ |
1847 | (idRect)->extents.setBottom((r)->bottom());\ |
1848 | } |
1849 | |
1850 | /* |
1851 | * Check to see if there is enough memory in the present region. |
1852 | */ |
1853 | #define MEMCHECK(dest, rect, firstrect){\ |
1854 | if ((dest).numRects >= ((dest).rects.size()-1)){\ |
1855 | firstrect.resize(firstrect.size() * 2); \ |
1856 | (rect) = (firstrect).data() + (dest).numRects;\ |
1857 | }\ |
1858 | } |
1859 | |
1860 | |
1861 | /* |
1862 | * number of points to buffer before sending them off |
1863 | * to scanlines(): Must be an even number |
1864 | */ |
1865 | #define NUMPTSTOBUFFER 200 |
1866 | |
1867 | /* |
1868 | * used to allocate buffers for points and link |
1869 | * the buffers together |
1870 | */ |
1871 | typedef struct _POINTBLOCK { |
1872 | char data[NUMPTSTOBUFFER * sizeof(QPoint)]; |
1873 | QPoint *pts; |
1874 | struct _POINTBLOCK *next; |
1875 | } POINTBLOCK; |
1876 | |
1877 | #endif |
1878 | // END OF region.h extract |
1879 | |
1880 | // START OF Region.c extract |
1881 | /* $XConsortium: Region.c /main/30 1996/10/22 14:21:24 kaleb $ */ |
1882 | /************************************************************************ |
1883 | |
1884 | Copyright (c) 1987, 1988 X Consortium |
1885 | |
1886 | Permission is hereby granted, free of charge, to any person obtaining a copy |
1887 | of this software and associated documentation files (the "Software"), to deal |
1888 | in the Software without restriction, including without limitation the rights |
1889 | to use, copy, modify, merge, publish, distribute, sublicense, and/or sell |
1890 | copies of the Software, and to permit persons to whom the Software is |
1891 | furnished to do so, subject to the following conditions: |
1892 | |
1893 | The above copyright notice and this permission notice shall be included in |
1894 | all copies or substantial portions of the Software. |
1895 | |
1896 | THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
1897 | IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
1898 | FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE |
1899 | X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN |
1900 | AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN |
1901 | CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. |
1902 | |
1903 | Except as contained in this notice, the name of the X Consortium shall not be |
1904 | used in advertising or otherwise to promote the sale, use or other dealings |
1905 | in this Software without prior written authorization from the X Consortium. |
1906 | |
1907 | |
1908 | Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts. |
1909 | |
1910 | All Rights Reserved |
1911 | |
1912 | Permission to use, copy, modify, and distribute this software and its |
1913 | documentation for any purpose and without fee is hereby granted, |
1914 | provided that the above copyright notice appear in all copies and that |
1915 | both that copyright notice and this permission notice appear in |
1916 | supporting documentation, and that the name of Digital not be |
1917 | used in advertising or publicity pertaining to distribution of the |
1918 | software without specific, written prior permission. |
1919 | |
1920 | DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING |
1921 | ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL |
1922 | DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR |
1923 | ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, |
1924 | WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, |
1925 | ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS |
1926 | SOFTWARE. |
1927 | |
1928 | ************************************************************************/ |
1929 | /* |
1930 | * The functions in this file implement the Region abstraction, similar to one |
1931 | * used in the X11 sample server. A Region is simply an area, as the name |
1932 | * implies, and is implemented as a "y-x-banded" array of rectangles. To |
1933 | * explain: Each Region is made up of a certain number of rectangles sorted |
1934 | * by y coordinate first, and then by x coordinate. |
1935 | * |
1936 | * Furthermore, the rectangles are banded such that every rectangle with a |
1937 | * given upper-left y coordinate (y1) will have the same lower-right y |
1938 | * coordinate (y2) and vice versa. If a rectangle has scanlines in a band, it |
1939 | * will span the entire vertical distance of the band. This means that some |
1940 | * areas that could be merged into a taller rectangle will be represented as |
1941 | * several shorter rectangles to account for shorter rectangles to its left |
1942 | * or right but within its "vertical scope". |
1943 | * |
1944 | * An added constraint on the rectangles is that they must cover as much |
1945 | * horizontal area as possible. E.g. no two rectangles in a band are allowed |
1946 | * to touch. |
1947 | * |
1948 | * Whenever possible, bands will be merged together to cover a greater vertical |
1949 | * distance (and thus reduce the number of rectangles). Two bands can be merged |
1950 | * only if the bottom of one touches the top of the other and they have |
1951 | * rectangles in the same places (of the same width, of course). This maintains |
1952 | * the y-x-banding that's so nice to have... |
1953 | */ |
1954 | /* $XFree86: xc/lib/X11/Region.c,v 1.1.1.2.2.2 1998/10/04 15:22:50 hohndel Exp $ */ |
1955 | |
1956 | static void UnionRectWithRegion(const QRect *rect, const QRegionPrivate *source, |
1957 | QRegionPrivate &dest) |
1958 | { |
1959 | if (rect->isEmpty()) |
1960 | return; |
1961 | |
1962 | Q_ASSERT(EqualRegion(source, &dest)); |
1963 | |
1964 | if (dest.numRects == 0) { |
1965 | dest = QRegionPrivate(*rect); |
1966 | } else if (dest.canAppend(rect)) { |
1967 | dest.append(rect); |
1968 | } else { |
1969 | QRegionPrivate p(*rect); |
1970 | UnionRegion(&p, source, dest); |
1971 | } |
1972 | } |
1973 | |
1974 | /*- |
1975 | *----------------------------------------------------------------------- |
1976 | * miSetExtents -- |
1977 | * Reset the extents and innerRect of a region to what they should be. |
1978 | * Called by miSubtract and miIntersect b/c they can't figure it out |
1979 | * along the way or do so easily, as miUnion can. |
1980 | * |
1981 | * Results: |
1982 | * None. |
1983 | * |
1984 | * Side Effects: |
1985 | * The region's 'extents' and 'innerRect' structure is overwritten. |
1986 | * |
1987 | *----------------------------------------------------------------------- |
1988 | */ |
1989 | static void miSetExtents(QRegionPrivate &dest) |
1990 | { |
1991 | const QRect *pBox, |
1992 | *pBoxEnd; |
1993 | QRect *pExtents; |
1994 | |
1995 | dest.innerRect.setCoords(0, 0, -1, -1); |
1996 | dest.innerArea = -1; |
1997 | if (dest.numRects == 0) { |
1998 | dest.extents.setCoords(0, 0, -1, -1); |
1999 | return; |
2000 | } |
2001 | |
2002 | pExtents = &dest.extents; |
2003 | if (dest.rects.isEmpty()) |
2004 | pBox = &dest.extents; |
2005 | else |
2006 | pBox = dest.rects.constData(); |
2007 | pBoxEnd = pBox + dest.numRects - 1; |
2008 | |
2009 | /* |
2010 | * Since pBox is the first rectangle in the region, it must have the |
2011 | * smallest y1 and since pBoxEnd is the last rectangle in the region, |
2012 | * it must have the largest y2, because of banding. Initialize x1 and |
2013 | * x2 from pBox and pBoxEnd, resp., as good things to initialize them |
2014 | * to... |
2015 | */ |
2016 | pExtents->setLeft(pBox->left()); |
2017 | pExtents->setTop(pBox->top()); |
2018 | pExtents->setRight(pBoxEnd->right()); |
2019 | pExtents->setBottom(pBoxEnd->bottom()); |
2020 | |
2021 | Q_ASSERT(pExtents->top() <= pExtents->bottom()); |
2022 | while (pBox <= pBoxEnd) { |
2023 | if (pBox->left() < pExtents->left()) |
2024 | pExtents->setLeft(pBox->left()); |
2025 | if (pBox->right() > pExtents->right()) |
2026 | pExtents->setRight(pBox->right()); |
2027 | dest.updateInnerRect(*pBox); |
2028 | ++pBox; |
2029 | } |
2030 | Q_ASSERT(pExtents->left() <= pExtents->right()); |
2031 | } |
2032 | |
2033 | /* TranslateRegion(pRegion, x, y) |
2034 | translates in place |
2035 | added by raymond |
2036 | */ |
2037 | |
2038 | static void OffsetRegion(QRegionPrivate ®ion, int x, int y) |
2039 | { |
2040 | if (region.rects.size()) { |
2041 | QRect *pbox = region.rects.data(); |
2042 | int nbox = region.numRects; |
2043 | |
2044 | while (nbox--) { |
2045 | pbox->translate(x, y); |
2046 | ++pbox; |
2047 | } |
2048 | } |
2049 | region.extents.translate(x, y); |
2050 | region.innerRect.translate(x, y); |
2051 | } |
2052 | |
2053 | /*====================================================================== |
2054 | * Region Intersection |
2055 | *====================================================================*/ |
2056 | /*- |
2057 | *----------------------------------------------------------------------- |
2058 | * miIntersectO -- |
2059 | * Handle an overlapping band for miIntersect. |
2060 | * |
2061 | * Results: |
2062 | * None. |
2063 | * |
2064 | * Side Effects: |
2065 | * Rectangles may be added to the region. |
2066 | * |
2067 | *----------------------------------------------------------------------- |
2068 | */ |
2069 | static void miIntersectO(QRegionPrivate &dest, const QRect *r1, const QRect *r1End, |
2070 | const QRect *r2, const QRect *r2End, int y1, int y2) |
2071 | { |
2072 | int x1; |
2073 | int x2; |
2074 | QRect *pNextRect; |
2075 | |
2076 | pNextRect = dest.rects.data() + dest.numRects; |
2077 | |
2078 | while (r1 != r1End && r2 != r2End) { |
2079 | x1 = qMax(r1->left(), r2->left()); |
2080 | x2 = qMin(r1->right(), r2->right()); |
2081 | |
2082 | /* |
2083 | * If there's any overlap between the two rectangles, add that |
2084 | * overlap to the new region. |
2085 | * There's no need to check for subsumption because the only way |
2086 | * such a need could arise is if some region has two rectangles |
2087 | * right next to each other. Since that should never happen... |
2088 | */ |
2089 | if (x1 <= x2) { |
2090 | Q_ASSERT(y1 <= y2); |
2091 | MEMCHECK(dest, pNextRect, dest.rects) |
2092 | pNextRect->setCoords(x1, y1, x2, y2); |
2093 | ++dest.numRects; |
2094 | ++pNextRect; |
2095 | } |
2096 | |
2097 | /* |
2098 | * Need to advance the pointers. Shift the one that extends |
2099 | * to the right the least, since the other still has a chance to |
2100 | * overlap with that region's next rectangle, if you see what I mean. |
2101 | */ |
2102 | if (r1->right() < r2->right()) { |
2103 | ++r1; |
2104 | } else if (r2->right() < r1->right()) { |
2105 | ++r2; |
2106 | } else { |
2107 | ++r1; |
2108 | ++r2; |
2109 | } |
2110 | } |
2111 | } |
2112 | |
2113 | /*====================================================================== |
2114 | * Generic Region Operator |
2115 | *====================================================================*/ |
2116 | |
2117 | /*- |
2118 | *----------------------------------------------------------------------- |
2119 | * miCoalesce -- |
2120 | * Attempt to merge the boxes in the current band with those in the |
2121 | * previous one. Used only by miRegionOp. |
2122 | * |
2123 | * Results: |
2124 | * The new index for the previous band. |
2125 | * |
2126 | * Side Effects: |
2127 | * If coalescing takes place: |
2128 | * - rectangles in the previous band will have their y2 fields |
2129 | * altered. |
2130 | * - dest.numRects will be decreased. |
2131 | * |
2132 | *----------------------------------------------------------------------- |
2133 | */ |
2134 | static int miCoalesce(QRegionPrivate &dest, int prevStart, int curStart) |
2135 | { |
2136 | QRect *pPrevBox; /* Current box in previous band */ |
2137 | QRect *pCurBox; /* Current box in current band */ |
2138 | QRect *pRegEnd; /* End of region */ |
2139 | int curNumRects; /* Number of rectangles in current band */ |
2140 | int prevNumRects; /* Number of rectangles in previous band */ |
2141 | int bandY1; /* Y1 coordinate for current band */ |
2142 | QRect *rData = dest.rects.data(); |
2143 | |
2144 | pRegEnd = rData + dest.numRects; |
2145 | |
2146 | pPrevBox = rData + prevStart; |
2147 | prevNumRects = curStart - prevStart; |
2148 | |
2149 | /* |
2150 | * Figure out how many rectangles are in the current band. Have to do |
2151 | * this because multiple bands could have been added in miRegionOp |
2152 | * at the end when one region has been exhausted. |
2153 | */ |
2154 | pCurBox = rData + curStart; |
2155 | bandY1 = pCurBox->top(); |
2156 | for (curNumRects = 0; pCurBox != pRegEnd && pCurBox->top() == bandY1; ++curNumRects) { |
2157 | ++pCurBox; |
2158 | } |
2159 | |
2160 | if (pCurBox != pRegEnd) { |
2161 | /* |
2162 | * If more than one band was added, we have to find the start |
2163 | * of the last band added so the next coalescing job can start |
2164 | * at the right place... (given when multiple bands are added, |
2165 | * this may be pointless -- see above). |
2166 | */ |
2167 | --pRegEnd; |
2168 | while ((pRegEnd - 1)->top() == pRegEnd->top()) |
2169 | --pRegEnd; |
2170 | curStart = pRegEnd - rData; |
2171 | pRegEnd = rData + dest.numRects; |
2172 | } |
2173 | |
2174 | if (curNumRects == prevNumRects && curNumRects != 0) { |
2175 | pCurBox -= curNumRects; |
2176 | /* |
2177 | * The bands may only be coalesced if the bottom of the previous |
2178 | * matches the top scanline of the current. |
2179 | */ |
2180 | if (pPrevBox->bottom() == pCurBox->top() - 1) { |
2181 | /* |
2182 | * Make sure the bands have boxes in the same places. This |
2183 | * assumes that boxes have been added in such a way that they |
2184 | * cover the most area possible. I.e. two boxes in a band must |
2185 | * have some horizontal space between them. |
2186 | */ |
2187 | do { |
2188 | if (pPrevBox->left() != pCurBox->left() || pPrevBox->right() != pCurBox->right()) { |
2189 | // The bands don't line up so they can't be coalesced. |
2190 | return curStart; |
2191 | } |
2192 | ++pPrevBox; |
2193 | ++pCurBox; |
2194 | --prevNumRects; |
2195 | } while (prevNumRects != 0); |
2196 | |
2197 | dest.numRects -= curNumRects; |
2198 | pCurBox -= curNumRects; |
2199 | pPrevBox -= curNumRects; |
2200 | |
2201 | /* |
2202 | * The bands may be merged, so set the bottom y of each box |
2203 | * in the previous band to that of the corresponding box in |
2204 | * the current band. |
2205 | */ |
2206 | do { |
2207 | pPrevBox->setBottom(pCurBox->bottom()); |
2208 | dest.updateInnerRect(*pPrevBox); |
2209 | ++pPrevBox; |
2210 | ++pCurBox; |
2211 | curNumRects -= 1; |
2212 | } while (curNumRects != 0); |
2213 | |
2214 | /* |
2215 | * If only one band was added to the region, we have to backup |
2216 | * curStart to the start of the previous band. |
2217 | * |
2218 | * If more than one band was added to the region, copy the |
2219 | * other bands down. The assumption here is that the other bands |
2220 | * came from the same region as the current one and no further |
2221 | * coalescing can be done on them since it's all been done |
2222 | * already... curStart is already in the right place. |
2223 | */ |
2224 | if (pCurBox == pRegEnd) { |
2225 | curStart = prevStart; |
2226 | } else { |
2227 | do { |
2228 | *pPrevBox++ = *pCurBox++; |
2229 | dest.updateInnerRect(*pPrevBox); |
2230 | } while (pCurBox != pRegEnd); |
2231 | } |
2232 | } |
2233 | } |
2234 | return curStart; |
2235 | } |
2236 | |
2237 | /*- |
2238 | *----------------------------------------------------------------------- |
2239 | * miRegionOp -- |
2240 | * Apply an operation to two regions. Called by miUnion, miInverse, |
2241 | * miSubtract, miIntersect... |
2242 | * |
2243 | * Results: |
2244 | * None. |
2245 | * |
2246 | * Side Effects: |
2247 | * The new region is overwritten. |
2248 | * |
2249 | * Notes: |
2250 | * The idea behind this function is to view the two regions as sets. |
2251 | * Together they cover a rectangle of area that this function divides |
2252 | * into horizontal bands where points are covered only by one region |
2253 | * or by both. For the first case, the nonOverlapFunc is called with |
2254 | * each the band and the band's upper and lower extents. For the |
2255 | * second, the overlapFunc is called to process the entire band. It |
2256 | * is responsible for clipping the rectangles in the band, though |
2257 | * this function provides the boundaries. |
2258 | * At the end of each band, the new region is coalesced, if possible, |
2259 | * to reduce the number of rectangles in the region. |
2260 | * |
2261 | *----------------------------------------------------------------------- |
2262 | */ |
2263 | static void miRegionOp(QRegionPrivate &dest, |
2264 | const QRegionPrivate *reg1, const QRegionPrivate *reg2, |
2265 | OverlapFunc overlapFunc, NonOverlapFunc nonOverlap1Func, |
2266 | NonOverlapFunc nonOverlap2Func) |
2267 | { |
2268 | const QRect *r1; // Pointer into first region |
2269 | const QRect *r2; // Pointer into 2d region |
2270 | const QRect *r1End; // End of 1st region |
2271 | const QRect *r2End; // End of 2d region |
2272 | int ybot; // Bottom of intersection |
2273 | int ytop; // Top of intersection |
2274 | int prevBand; // Index of start of previous band in dest |
2275 | int curBand; // Index of start of current band in dest |
2276 | const QRect *r1BandEnd; // End of current band in r1 |
2277 | const QRect *r2BandEnd; // End of current band in r2 |
2278 | int top; // Top of non-overlapping band |
2279 | int bot; // Bottom of non-overlapping band |
2280 | |
2281 | /* |
2282 | * Initialization: |
2283 | * set r1, r2, r1End and r2End appropriately, preserve the important |
2284 | * parts of the destination region until the end in case it's one of |
2285 | * the two source regions, then mark the "new" region empty, allocating |
2286 | * another array of rectangles for it to use. |
2287 | */ |
2288 | if (reg1->numRects == 1) |
2289 | r1 = ®1->extents; |
2290 | else |
2291 | r1 = reg1->rects.constData(); |
2292 | if (reg2->numRects == 1) |
2293 | r2 = ®2->extents; |
2294 | else |
2295 | r2 = reg2->rects.constData(); |
2296 | |
2297 | r1End = r1 + reg1->numRects; |
2298 | r2End = r2 + reg2->numRects; |
2299 | |
2300 | dest.vectorize(); |
2301 | |
2302 | /* |
2303 | * The following calls are going to detach dest.rects. Since dest might be |
2304 | * aliasing *reg1 and/or *reg2, and we could have active iterators on |
2305 | * reg1->rects and reg2->rects (if the regions have more than 1 rectangle), |
2306 | * take a copy of dest.rects to keep those iteractors valid. |
2307 | */ |
2308 | const QVector<QRect> destRectsCopy = dest.rects; |
2309 | Q_UNUSED(destRectsCopy); |
2310 | |
2311 | dest.numRects = 0; |
2312 | |
2313 | /* |
2314 | * Allocate a reasonable number of rectangles for the new region. The idea |
2315 | * is to allocate enough so the individual functions don't need to |
2316 | * reallocate and copy the array, which is time consuming, yet we don't |
2317 | * have to worry about using too much memory. I hope to be able to |
2318 | * nuke the realloc() at the end of this function eventually. |
2319 | */ |
2320 | dest.rects.resize(qMax(reg1->numRects,reg2->numRects) * 2); |
2321 | |
2322 | /* |
2323 | * Initialize ybot and ytop. |
2324 | * In the upcoming loop, ybot and ytop serve different functions depending |
2325 | * on whether the band being handled is an overlapping or non-overlapping |
2326 | * band. |
2327 | * In the case of a non-overlapping band (only one of the regions |
2328 | * has points in the band), ybot is the bottom of the most recent |
2329 | * intersection and thus clips the top of the rectangles in that band. |
2330 | * ytop is the top of the next intersection between the two regions and |
2331 | * serves to clip the bottom of the rectangles in the current band. |
2332 | * For an overlapping band (where the two regions intersect), ytop clips |
2333 | * the top of the rectangles of both regions and ybot clips the bottoms. |
2334 | */ |
2335 | if (reg1->extents.top() < reg2->extents.top()) |
2336 | ybot = reg1->extents.top() - 1; |
2337 | else |
2338 | ybot = reg2->extents.top() - 1; |
2339 | |
2340 | /* |
2341 | * prevBand serves to mark the start of the previous band so rectangles |
2342 | * can be coalesced into larger rectangles. qv. miCoalesce, above. |
2343 | * In the beginning, there is no previous band, so prevBand == curBand |
2344 | * (curBand is set later on, of course, but the first band will always |
2345 | * start at index 0). prevBand and curBand must be indices because of |
2346 | * the possible expansion, and resultant moving, of the new region's |
2347 | * array of rectangles. |
2348 | */ |
2349 | prevBand = 0; |
2350 | |
2351 | do { |
2352 | curBand = dest.numRects; |
2353 | |
2354 | /* |
2355 | * This algorithm proceeds one source-band (as opposed to a |
2356 | * destination band, which is determined by where the two regions |
2357 | * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the |
2358 | * rectangle after the last one in the current band for their |
2359 | * respective regions. |
2360 | */ |
2361 | r1BandEnd = r1; |
2362 | while (r1BandEnd != r1End && r1BandEnd->top() == r1->top()) |
2363 | ++r1BandEnd; |
2364 | |
2365 | r2BandEnd = r2; |
2366 | while (r2BandEnd != r2End && r2BandEnd->top() == r2->top()) |
2367 | ++r2BandEnd; |
2368 | |
2369 | /* |
2370 | * First handle the band that doesn't intersect, if any. |
2371 | * |
2372 | * Note that attention is restricted to one band in the |
2373 | * non-intersecting region at once, so if a region has n |
2374 | * bands between the current position and the next place it overlaps |
2375 | * the other, this entire loop will be passed through n times. |
2376 | */ |
2377 | if (r1->top() < r2->top()) { |
2378 | top = qMax(r1->top(), ybot + 1); |
2379 | bot = qMin(r1->bottom(), r2->top() - 1); |
2380 | |
2381 | if (nonOverlap1Func != 0 && bot >= top) |
2382 | (*nonOverlap1Func)(dest, r1, r1BandEnd, top, bot); |
2383 | ytop = r2->top(); |
2384 | } else if (r2->top() < r1->top()) { |
2385 | top = qMax(r2->top(), ybot + 1); |
2386 | bot = qMin(r2->bottom(), r1->top() - 1); |
2387 | |
2388 | if (nonOverlap2Func != 0 && bot >= top) |
2389 | (*nonOverlap2Func)(dest, r2, r2BandEnd, top, bot); |
2390 | ytop = r1->top(); |
2391 | } else { |
2392 | ytop = r1->top(); |
2393 | } |
2394 | |
2395 | /* |
2396 | * If any rectangles got added to the region, try and coalesce them |
2397 | * with rectangles from the previous band. Note we could just do |
2398 | * this test in miCoalesce, but some machines incur a not |
2399 | * inconsiderable cost for function calls, so... |
2400 | */ |
2401 | if (dest.numRects != curBand) |
2402 | prevBand = miCoalesce(dest, prevBand, curBand); |
2403 | |
2404 | /* |
2405 | * Now see if we've hit an intersecting band. The two bands only |
2406 | * intersect if ybot >= ytop |
2407 | */ |
2408 | ybot = qMin(r1->bottom(), r2->bottom()); |
2409 | curBand = dest.numRects; |
2410 | if (ybot >= ytop) |
2411 | (*overlapFunc)(dest, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot); |
2412 | |
2413 | if (dest.numRects != curBand) |
2414 | prevBand = miCoalesce(dest, prevBand, curBand); |
2415 | |
2416 | /* |
2417 | * If we've finished with a band (y2 == ybot) we skip forward |
2418 | * in the region to the next band. |
2419 | */ |
2420 | if (r1->bottom() == ybot) |
2421 | r1 = r1BandEnd; |
2422 | if (r2->bottom() == ybot) |
2423 | r2 = r2BandEnd; |
2424 | } while (r1 != r1End && r2 != r2End); |
2425 | |
2426 | /* |
2427 | * Deal with whichever region still has rectangles left. |
2428 | */ |
2429 | curBand = dest.numRects; |
2430 | if (r1 != r1End) { |
2431 | if (nonOverlap1Func != 0) { |
2432 | do { |
2433 | r1BandEnd = r1; |
2434 | while (r1BandEnd < r1End && r1BandEnd->top() == r1->top()) |
2435 | ++r1BandEnd; |
2436 | (*nonOverlap1Func)(dest, r1, r1BandEnd, qMax(r1->top(), ybot + 1), r1->bottom()); |
2437 | r1 = r1BandEnd; |
2438 | } while (r1 != r1End); |
2439 | } |
2440 | } else if ((r2 != r2End) && (nonOverlap2Func != 0)) { |
2441 | do { |
2442 | r2BandEnd = r2; |
2443 | while (r2BandEnd < r2End && r2BandEnd->top() == r2->top()) |
2444 | ++r2BandEnd; |
2445 | (*nonOverlap2Func)(dest, r2, r2BandEnd, qMax(r2->top(), ybot + 1), r2->bottom()); |
2446 | r2 = r2BandEnd; |
2447 | } while (r2 != r2End); |
2448 | } |
2449 | |
2450 | if (dest.numRects != curBand) |
2451 | (void)miCoalesce(dest, prevBand, curBand); |
2452 | |
2453 | /* |
2454 | * A bit of cleanup. To keep regions from growing without bound, |
2455 | * we shrink the array of rectangles to match the new number of |
2456 | * rectangles in the region. |
2457 | * |
2458 | * Only do this stuff if the number of rectangles allocated is more than |
2459 | * twice the number of rectangles in the region (a simple optimization). |
2460 | */ |
2461 | if (qMax(4, dest.numRects) < (dest.rects.size() >> 1)) |
2462 | dest.rects.resize(dest.numRects); |
2463 | } |
2464 | |
2465 | /*====================================================================== |
2466 | * Region Union |
2467 | *====================================================================*/ |
2468 | |
2469 | /*- |
2470 | *----------------------------------------------------------------------- |
2471 | * miUnionNonO -- |
2472 | * Handle a non-overlapping band for the union operation. Just |
2473 | * Adds the rectangles into the region. Doesn't have to check for |
2474 | * subsumption or anything. |
2475 | * |
2476 | * Results: |
2477 | * None. |
2478 | * |
2479 | * Side Effects: |
2480 | * dest.numRects is incremented and the final rectangles overwritten |
2481 | * with the rectangles we're passed. |
2482 | * |
2483 | *----------------------------------------------------------------------- |
2484 | */ |
2485 | |
2486 | static void miUnionNonO(QRegionPrivate &dest, const QRect *r, const QRect *rEnd, |
2487 | int y1, int y2) |
2488 | { |
2489 | QRect *pNextRect; |
2490 | |
2491 | pNextRect = dest.rects.data() + dest.numRects; |
2492 | |
2493 | Q_ASSERT(y1 <= y2); |
2494 | |
2495 | while (r != rEnd) { |
2496 | Q_ASSERT(r->left() <= r->right()); |
2497 | MEMCHECK(dest, pNextRect, dest.rects) |
2498 | pNextRect->setCoords(r->left(), y1, r->right(), y2); |
2499 | dest.numRects++; |
2500 | ++pNextRect; |
2501 | ++r; |
2502 | } |
2503 | } |
2504 | |
2505 | |
2506 | /*- |
2507 | *----------------------------------------------------------------------- |
2508 | * miUnionO -- |
2509 | * Handle an overlapping band for the union operation. Picks the |
2510 | * left-most rectangle each time and merges it into the region. |
2511 | * |
2512 | * Results: |
2513 | * None. |
2514 | * |
2515 | * Side Effects: |
2516 | * Rectangles are overwritten in dest.rects and dest.numRects will |
2517 | * be changed. |
2518 | * |
2519 | *----------------------------------------------------------------------- |
2520 | */ |
2521 | |
2522 | static void miUnionO(QRegionPrivate &dest, const QRect *r1, const QRect *r1End, |
2523 | const QRect *r2, const QRect *r2End, int y1, int y2) |
2524 | { |
2525 | QRect *pNextRect; |
2526 | |
2527 | pNextRect = dest.rects.data() + dest.numRects; |
2528 | |
2529 | #define MERGERECT(r) \ |
2530 | if ((dest.numRects != 0) && \ |
2531 | (pNextRect[-1].top() == y1) && \ |
2532 | (pNextRect[-1].bottom() == y2) && \ |
2533 | (pNextRect[-1].right() >= r->left()-1)) { \ |
2534 | if (pNextRect[-1].right() < r->right()) { \ |
2535 | pNextRect[-1].setRight(r->right()); \ |
2536 | dest.updateInnerRect(pNextRect[-1]); \ |
2537 | Q_ASSERT(pNextRect[-1].left() <= pNextRect[-1].right()); \ |
2538 | } \ |
2539 | } else { \ |
2540 | MEMCHECK(dest, pNextRect, dest.rects) \ |
2541 | pNextRect->setCoords(r->left(), y1, r->right(), y2); \ |
2542 | dest.updateInnerRect(*pNextRect); \ |
2543 | dest.numRects++; \ |
2544 | pNextRect++; \ |
2545 | } \ |
2546 | r++; |
2547 | |
2548 | Q_ASSERT(y1 <= y2); |
2549 | while (r1 != r1End && r2 != r2End) { |
2550 | if (r1->left() < r2->left()) { |
2551 | MERGERECT(r1) |
2552 | } else { |
2553 | MERGERECT(r2) |
2554 | } |
2555 | } |
2556 | |
2557 | if (r1 != r1End) { |
2558 | do { |
2559 | MERGERECT(r1) |
2560 | } while (r1 != r1End); |
2561 | } else { |
2562 | while (r2 != r2End) { |
2563 | MERGERECT(r2) |
2564 | } |
2565 | } |
2566 | } |
2567 | |
2568 | static void UnionRegion(const QRegionPrivate *reg1, const QRegionPrivate *reg2, QRegionPrivate &dest) |
2569 | { |
2570 | Q_ASSERT(!isEmptyHelper(reg1) && !isEmptyHelper(reg2)); |
2571 | Q_ASSERT(!reg1->contains(*reg2)); |
2572 | Q_ASSERT(!reg2->contains(*reg1)); |
2573 | Q_ASSERT(!EqualRegion(reg1, reg2)); |
2574 | Q_ASSERT(!reg1->canAppend(reg2)); |
2575 | Q_ASSERT(!reg2->canAppend(reg1)); |
2576 | |
2577 | if (reg1->innerArea > reg2->innerArea) { |
2578 | dest.innerArea = reg1->innerArea; |
2579 | dest.innerRect = reg1->innerRect; |
2580 | } else { |
2581 | dest.innerArea = reg2->innerArea; |
2582 | dest.innerRect = reg2->innerRect; |
2583 | } |
2584 | miRegionOp(dest, reg1, reg2, miUnionO, miUnionNonO, miUnionNonO); |
2585 | |
2586 | dest.extents.setCoords(qMin(reg1->extents.left(), reg2->extents.left()), |
2587 | qMin(reg1->extents.top(), reg2->extents.top()), |
2588 | qMax(reg1->extents.right(), reg2->extents.right()), |
2589 | qMax(reg1->extents.bottom(), reg2->extents.bottom())); |
2590 | } |
2591 | |
2592 | /*====================================================================== |
2593 | * Region Subtraction |
2594 | *====================================================================*/ |
2595 | |
2596 | /*- |
2597 | *----------------------------------------------------------------------- |
2598 | * miSubtractNonO -- |
2599 | * Deal with non-overlapping band for subtraction. Any parts from |
2600 | * region 2 we discard. Anything from region 1 we add to the region. |
2601 | * |
2602 | * Results: |
2603 | * None. |
2604 | * |
2605 | * Side Effects: |
2606 | * dest may be affected. |
2607 | * |
2608 | *----------------------------------------------------------------------- |
2609 | */ |
2610 | |
2611 | static void miSubtractNonO1(QRegionPrivate &dest, const QRect *r, |
2612 | const QRect *rEnd, int y1, int y2) |
2613 | { |
2614 | QRect *pNextRect; |
2615 | |
2616 | pNextRect = dest.rects.data() + dest.numRects; |
2617 | |
2618 | Q_ASSERT(y1<=y2); |
2619 | |
2620 | while (r != rEnd) { |
2621 | Q_ASSERT(r->left() <= r->right()); |
2622 | MEMCHECK(dest, pNextRect, dest.rects) |
2623 | pNextRect->setCoords(r->left(), y1, r->right(), y2); |
2624 | ++dest.numRects; |
2625 | ++pNextRect; |
2626 | ++r; |
2627 | } |
2628 | } |
2629 | |
2630 | /*- |
2631 | *----------------------------------------------------------------------- |
2632 | * miSubtractO -- |
2633 | * Overlapping band subtraction. x1 is the left-most point not yet |
2634 | * checked. |
2635 | * |
2636 | * Results: |
2637 | * None. |
2638 | * |
2639 | * Side Effects: |
2640 | * dest may have rectangles added to it. |
2641 | * |
2642 | *----------------------------------------------------------------------- |
2643 | */ |
2644 | |
2645 | static void miSubtractO(QRegionPrivate &dest, const QRect *r1, const QRect *r1End, |
2646 | const QRect *r2, const QRect *r2End, int y1, int y2) |
2647 | { |
2648 | QRect *pNextRect; |
2649 | int x1; |
2650 | |
2651 | x1 = r1->left(); |
2652 | |
2653 | Q_ASSERT(y1 <= y2); |
2654 | pNextRect = dest.rects.data() + dest.numRects; |
2655 | |
2656 | while (r1 != r1End && r2 != r2End) { |
2657 | if (r2->right() < x1) { |
2658 | /* |
2659 | * Subtrahend missed the boat: go to next subtrahend. |
2660 | */ |
2661 | ++r2; |
2662 | } else if (r2->left() <= x1) { |
2663 | /* |
2664 | * Subtrahend precedes minuend: nuke left edge of minuend. |
2665 | */ |
2666 | x1 = r2->right() + 1; |
2667 | if (x1 > r1->right()) { |
2668 | /* |
2669 | * Minuend completely covered: advance to next minuend and |
2670 | * reset left fence to edge of new minuend. |
2671 | */ |
2672 | ++r1; |
2673 | if (r1 != r1End) |
2674 | x1 = r1->left(); |
2675 | } else { |
2676 | // Subtrahend now used up since it doesn't extend beyond minuend |
2677 | ++r2; |
2678 | } |
2679 | } else if (r2->left() <= r1->right()) { |
2680 | /* |
2681 | * Left part of subtrahend covers part of minuend: add uncovered |
2682 | * part of minuend to region and skip to next subtrahend. |
2683 | */ |
2684 | Q_ASSERT(x1 < r2->left()); |
2685 | MEMCHECK(dest, pNextRect, dest.rects) |
2686 | pNextRect->setCoords(x1, y1, r2->left() - 1, y2); |
2687 | ++dest.numRects; |
2688 | ++pNextRect; |
2689 | |
2690 | x1 = r2->right() + 1; |
2691 | if (x1 > r1->right()) { |
2692 | /* |
2693 | * Minuend used up: advance to new... |
2694 | */ |
2695 | ++r1; |
2696 | if (r1 != r1End) |
2697 | x1 = r1->left(); |
2698 | } else { |
2699 | // Subtrahend used up |
2700 | ++r2; |
2701 | } |
2702 | } else { |
2703 | /* |
2704 | * Minuend used up: add any remaining piece before advancing. |
2705 | */ |
2706 | if (r1->right() >= x1) { |
2707 | MEMCHECK(dest, pNextRect, dest.rects) |
2708 | pNextRect->setCoords(x1, y1, r1->right(), y2); |
2709 | ++dest.numRects; |
2710 | ++pNextRect; |
2711 | } |
2712 | ++r1; |
2713 | if (r1 != r1End) |
2714 | x1 = r1->left(); |
2715 | } |
2716 | } |
2717 | |
2718 | /* |
2719 | * Add remaining minuend rectangles to region. |
2720 | */ |
2721 | while (r1 != r1End) { |
2722 | Q_ASSERT(x1 <= r1->right()); |
2723 | MEMCHECK(dest, pNextRect, dest.rects) |
2724 | pNextRect->setCoords(x1, y1, r1->right(), y2); |
2725 | ++dest.numRects; |
2726 | ++pNextRect; |
2727 | |
2728 | ++r1; |
2729 | if (r1 != r1End) |
2730 | x1 = r1->left(); |
2731 | } |
2732 | } |
2733 | |
2734 | /*- |
2735 | *----------------------------------------------------------------------- |
2736 | * miSubtract -- |
2737 | * Subtract regS from regM and leave the result in regD. |
2738 | * S stands for subtrahend, M for minuend and D for difference. |
2739 | * |
2740 | * Side Effects: |
2741 | * regD is overwritten. |
2742 | * |
2743 | *----------------------------------------------------------------------- |
2744 | */ |
2745 | |
2746 | static void SubtractRegion(QRegionPrivate *regM, QRegionPrivate *regS, |
2747 | QRegionPrivate &dest) |
2748 | { |
2749 | Q_ASSERT(!isEmptyHelper(regM)); |
2750 | Q_ASSERT(!isEmptyHelper(regS)); |
2751 | Q_ASSERT(EXTENTCHECK(®M->extents, ®S->extents)); |
2752 | Q_ASSERT(!regS->contains(*regM)); |
2753 | Q_ASSERT(!EqualRegion(regM, regS)); |
2754 | |
2755 | miRegionOp(dest, regM, regS, miSubtractO, miSubtractNonO1, 0); |
2756 | |
2757 | /* |
2758 | * Can't alter dest's extents before we call miRegionOp because |
2759 | * it might be one of the source regions and miRegionOp depends |
2760 | * on the extents of those regions being the unaltered. Besides, this |
2761 | * way there's no checking against rectangles that will be nuked |
2762 | * due to coalescing, so we have to examine fewer rectangles. |
2763 | */ |
2764 | miSetExtents(dest); |
2765 | } |
2766 | |
2767 | static void XorRegion(QRegionPrivate *sra, QRegionPrivate *srb, QRegionPrivate &dest) |
2768 | { |
2769 | Q_ASSERT(!isEmptyHelper(sra) && !isEmptyHelper(srb)); |
2770 | Q_ASSERT(EXTENTCHECK(&sra->extents, &srb->extents)); |
2771 | Q_ASSERT(!EqualRegion(sra, srb)); |
2772 | |
2773 | QRegionPrivate tra, trb; |
2774 | |
2775 | if (!srb->contains(*sra)) |
2776 | SubtractRegion(sra, srb, tra); |
2777 | if (!sra->contains(*srb)) |
2778 | SubtractRegion(srb, sra, trb); |
2779 | |
2780 | Q_ASSERT(isEmptyHelper(&trb) || !tra.contains(trb)); |
2781 | Q_ASSERT(isEmptyHelper(&tra) || !trb.contains(tra)); |
2782 | |
2783 | if (isEmptyHelper(&tra)) { |
2784 | dest = trb; |
2785 | } else if (isEmptyHelper(&trb)) { |
2786 | dest = tra; |
2787 | } else if (tra.canAppend(&trb)) { |
2788 | dest = tra; |
2789 | dest.append(&trb); |
2790 | } else if (trb.canAppend(&tra)) { |
2791 | dest = trb; |
2792 | dest.append(&tra); |
2793 | } else { |
2794 | UnionRegion(&tra, &trb, dest); |
2795 | } |
2796 | } |
2797 | |
2798 | /* |
2799 | * Check to see if two regions are equal |
2800 | */ |
2801 | static bool EqualRegion(const QRegionPrivate *r1, const QRegionPrivate *r2) |
2802 | { |
2803 | if (r1->numRects != r2->numRects) { |
2804 | return false; |
2805 | } else if (r1->numRects == 0) { |
2806 | return true; |
2807 | } else if (r1->extents != r2->extents) { |
2808 | return false; |
2809 | } else if (r1->numRects == 1 && r2->numRects == 1) { |
2810 | return true; // equality tested in previous if-statement |
2811 | } else { |
2812 | const QRect *rr1 = (r1->numRects == 1) ? &r1->extents : r1->rects.constData(); |
2813 | const QRect *rr2 = (r2->numRects == 1) ? &r2->extents : r2->rects.constData(); |
2814 | for (int i = 0; i < r1->numRects; ++i, ++rr1, ++rr2) { |
2815 | if (*rr1 != *rr2) |
2816 | return false; |
2817 | } |
2818 | } |
2819 | |
2820 | return true; |
2821 | } |
2822 | |
2823 | static bool PointInRegion(QRegionPrivate *pRegion, int x, int y) |
2824 | { |
2825 | int i; |
2826 | |
2827 | if (isEmptyHelper(pRegion)) |
2828 | return false; |
2829 | if (!pRegion->extents.contains(x, y)) |
2830 | return false; |
2831 | if (pRegion->numRects == 1) |
2832 | return pRegion->extents.contains(x, y); |
2833 | if (pRegion->innerRect.contains(x, y)) |
2834 | return true; |
2835 | for (i = 0; i < pRegion->numRects; ++i) { |
2836 | if (pRegion->rects[i].contains(x, y)) |
2837 | return true; |
2838 | } |
2839 | return false; |
2840 | } |
2841 | |
2842 | static bool RectInRegion(QRegionPrivate *region, int rx, int ry, uint rwidth, uint rheight) |
2843 | { |
2844 | const QRect *pbox; |
2845 | const QRect *pboxEnd; |
2846 | QRect rect(rx, ry, rwidth, rheight); |
2847 | QRect *prect = ▭ |
2848 | int partIn, partOut; |
2849 | |
2850 | if (!region || region->numRects == 0 || !EXTENTCHECK(®ion->extents, prect)) |
2851 | return RectangleOut; |
2852 | |
2853 | partOut = false; |
2854 | partIn = false; |
2855 | |
2856 | /* can stop when both partOut and partIn are true, or we reach prect->y2 */ |
2857 | pbox = (region->numRects == 1) ? ®ion->extents : region->rects.constData(); |
2858 | pboxEnd = pbox + region->numRects; |
2859 | for (; pbox < pboxEnd; ++pbox) { |
2860 | if (pbox->bottom() < ry) |
2861 | continue; |
2862 | |
2863 | if (pbox->top() > ry) { |
2864 | partOut = true; |
2865 | if (partIn || pbox->top() > prect->bottom()) |
2866 | break; |
2867 | ry = pbox->top(); |
2868 | } |
2869 | |
2870 | if (pbox->right() < rx) |
2871 | continue; /* not far enough over yet */ |
2872 | |
2873 | if (pbox->left() > rx) { |
2874 | partOut = true; /* missed part of rectangle to left */ |
2875 | if (partIn) |
2876 | break; |
2877 | } |
2878 | |
2879 | if (pbox->left() <= prect->right()) { |
2880 | partIn = true; /* definitely overlap */ |
2881 | if (partOut) |
2882 | break; |
2883 | } |
2884 | |
2885 | if (pbox->right() >= prect->right()) { |
2886 | ry = pbox->bottom() + 1; /* finished with this band */ |
2887 | if (ry > prect->bottom()) |
2888 | break; |
2889 | rx = prect->left(); /* reset x out to left again */ |
2890 | } else { |
2891 | /* |
2892 | * Because boxes in a band are maximal width, if the first box |
2893 | * to overlap the rectangle doesn't completely cover it in that |
2894 | * band, the rectangle must be partially out, since some of it |
2895 | * will be uncovered in that band. partIn will have been set true |
2896 | * by now... |
2897 | */ |
2898 | break; |
2899 | } |
2900 | } |
2901 | return partIn ? ((ry <= prect->bottom()) ? RectanglePart : RectangleIn) : RectangleOut; |
2902 | } |
2903 | // END OF Region.c extract |
2904 | // START OF poly.h extract |
2905 | /* $XConsortium: poly.h,v 1.4 94/04/17 20:22:19 rws Exp $ */ |
2906 | /************************************************************************ |
2907 | |
2908 | Copyright (c) 1987 X Consortium |
2909 | |
2910 | Permission is hereby granted, free of charge, to any person obtaining a copy |
2911 | of this software and associated documentation files (the "Software"), to deal |
2912 | in the Software without restriction, including without limitation the rights |
2913 | to use, copy, modify, merge, publish, distribute, sublicense, and/or sell |
2914 | copies of the Software, and to permit persons to whom the Software is |
2915 | furnished to do so, subject to the following conditions: |
2916 | |
2917 | The above copyright notice and this permission notice shall be included in |
2918 | all copies or substantial portions of the Software. |
2919 | |
2920 | THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
2921 | IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
2922 | FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE |
2923 | X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN |
2924 | AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN |
2925 | CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. |
2926 | |
2927 | Except as contained in this notice, the name of the X Consortium shall not be |
2928 | used in advertising or otherwise to promote the sale, use or other dealings |
2929 | in this Software without prior written authorization from the X Consortium. |
2930 | |
2931 | |
2932 | Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts. |
2933 | |
2934 | All Rights Reserved |
2935 | |
2936 | Permission to use, copy, modify, and distribute this software and its |
2937 | documentation for any purpose and without fee is hereby granted, |
2938 | provided that the above copyright notice appear in all copies and that |
2939 | both that copyright notice and this permission notice appear in |
2940 | supporting documentation, and that the name of Digital not be |
2941 | used in advertising or publicity pertaining to distribution of the |
2942 | software without specific, written prior permission. |
2943 | |
2944 | DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING |
2945 | ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL |
2946 | DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR |
2947 | ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, |
2948 | WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, |
2949 | ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS |
2950 | SOFTWARE. |
2951 | |
2952 | ************************************************************************/ |
2953 | |
2954 | /* |
2955 | * This file contains a few macros to help track |
2956 | * the edge of a filled object. The object is assumed |
2957 | * to be filled in scanline order, and thus the |
2958 | * algorithm used is an extension of Bresenham's line |
2959 | * drawing algorithm which assumes that y is always the |
2960 | * major axis. |
2961 | * Since these pieces of code are the same for any filled shape, |
2962 | * it is more convenient to gather the library in one |
2963 | * place, but since these pieces of code are also in |
2964 | * the inner loops of output primitives, procedure call |
2965 | * overhead is out of the question. |
2966 | * See the author for a derivation if needed. |
2967 | */ |
2968 | |
2969 | |
2970 | /* |
2971 | * In scan converting polygons, we want to choose those pixels |
2972 | * which are inside the polygon. Thus, we add .5 to the starting |
2973 | * x coordinate for both left and right edges. Now we choose the |
2974 | * first pixel which is inside the pgon for the left edge and the |
2975 | * first pixel which is outside the pgon for the right edge. |
2976 | * Draw the left pixel, but not the right. |
2977 | * |
2978 | * How to add .5 to the starting x coordinate: |
2979 | * If the edge is moving to the right, then subtract dy from the |
2980 | * error term from the general form of the algorithm. |
2981 | * If the edge is moving to the left, then add dy to the error term. |
2982 | * |
2983 | * The reason for the difference between edges moving to the left |
2984 | * and edges moving to the right is simple: If an edge is moving |
2985 | * to the right, then we want the algorithm to flip immediately. |
2986 | * If it is moving to the left, then we don't want it to flip until |
2987 | * we traverse an entire pixel. |
2988 | */ |
2989 | #define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \ |
2990 | int dx; /* local storage */ \ |
2991 | \ |
2992 | /* \ |
2993 | * if the edge is horizontal, then it is ignored \ |
2994 | * and assumed not to be processed. Otherwise, do this stuff. \ |
2995 | */ \ |
2996 | if ((dy) != 0) { \ |
2997 | xStart = (x1); \ |
2998 | dx = (x2) - xStart; \ |
2999 | if (dx < 0) { \ |
3000 | m = dx / (dy); \ |
3001 | m1 = m - 1; \ |
3002 | incr1 = -2 * dx + 2 * (dy) * m1; \ |
3003 | incr2 = -2 * dx + 2 * (dy) * m; \ |
3004 | d = 2 * m * (dy) - 2 * dx - 2 * (dy); \ |
3005 | } else { \ |
3006 | m = dx / (dy); \ |
3007 | m1 = m + 1; \ |
3008 | incr1 = 2 * dx - 2 * (dy) * m1; \ |
3009 | incr2 = 2 * dx - 2 * (dy) * m; \ |
3010 | d = -2 * m * (dy) + 2 * dx; \ |
3011 | } \ |
3012 | } \ |
3013 | } |
3014 | |
3015 | #define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \ |
3016 | if (m1 > 0) { \ |
3017 | if (d > 0) { \ |
3018 | minval += m1; \ |
3019 | d += incr1; \ |
3020 | } \ |
3021 | else { \ |
3022 | minval += m; \ |
3023 | d += incr2; \ |
3024 | } \ |
3025 | } else {\ |
3026 | if (d >= 0) { \ |
3027 | minval += m1; \ |
3028 | d += incr1; \ |
3029 | } \ |
3030 | else { \ |
3031 | minval += m; \ |
3032 | d += incr2; \ |
3033 | } \ |
3034 | } \ |
3035 | } |
3036 | |
3037 | |
3038 | /* |
3039 | * This structure contains all of the information needed |
3040 | * to run the bresenham algorithm. |
3041 | * The variables may be hardcoded into the declarations |
3042 | * instead of using this structure to make use of |
3043 | * register declarations. |
3044 | */ |
3045 | typedef struct { |
3046 | int minor_axis; /* minor axis */ |
3047 | int d; /* decision variable */ |
3048 | int m, m1; /* slope and slope+1 */ |
3049 | int incr1, incr2; /* error increments */ |
3050 | } BRESINFO; |
3051 | |
3052 | |
3053 | #define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \ |
3054 | BRESINITPGON(dmaj, min1, min2, bres.minor_axis, bres.d, \ |
3055 | bres.m, bres.m1, bres.incr1, bres.incr2) |
3056 | |
3057 | #define BRESINCRPGONSTRUCT(bres) \ |
3058 | BRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2) |
3059 | |
3060 | |
3061 | |
3062 | /* |
3063 | * These are the data structures needed to scan |
3064 | * convert regions. Two different scan conversion |
3065 | * methods are available -- the even-odd method, and |
3066 | * the winding number method. |
3067 | * The even-odd rule states that a point is inside |
3068 | * the polygon if a ray drawn from that point in any |
3069 | * direction will pass through an odd number of |
3070 | * path segments. |
3071 | * By the winding number rule, a point is decided |
3072 | * to be inside the polygon if a ray drawn from that |
3073 | * point in any direction passes through a different |
3074 | * number of clockwise and counter-clockwise path |
3075 | * segments. |
3076 | * |
3077 | * These data structures are adapted somewhat from |
3078 | * the algorithm in (Foley/Van Dam) for scan converting |
3079 | * polygons. |
3080 | * The basic algorithm is to start at the top (smallest y) |
3081 | * of the polygon, stepping down to the bottom of |
3082 | * the polygon by incrementing the y coordinate. We |
3083 | * keep a list of edges which the current scanline crosses, |
3084 | * sorted by x. This list is called the Active Edge Table (AET) |
3085 | * As we change the y-coordinate, we update each entry in |
3086 | * in the active edge table to reflect the edges new xcoord. |
3087 | * This list must be sorted at each scanline in case |
3088 | * two edges intersect. |
3089 | * We also keep a data structure known as the Edge Table (ET), |
3090 | * which keeps track of all the edges which the current |
3091 | * scanline has not yet reached. The ET is basically a |
3092 | * list of ScanLineList structures containing a list of |
3093 | * edges which are entered at a given scanline. There is one |
3094 | * ScanLineList per scanline at which an edge is entered. |
3095 | * When we enter a new edge, we move it from the ET to the AET. |
3096 | * |
3097 | * From the AET, we can implement the even-odd rule as in |
3098 | * (Foley/Van Dam). |
3099 | * The winding number rule is a little trickier. We also |
3100 | * keep the EdgeTableEntries in the AET linked by the |
3101 | * nextWETE (winding EdgeTableEntry) link. This allows |
3102 | * the edges to be linked just as before for updating |
3103 | * purposes, but only uses the edges linked by the nextWETE |
3104 | * link as edges representing spans of the polygon to |
3105 | * drawn (as with the even-odd rule). |
3106 | */ |
3107 | |
3108 | /* |
3109 | * for the winding number rule |
3110 | */ |
3111 | #define CLOCKWISE 1 |
3112 | #define COUNTERCLOCKWISE -1 |
3113 | |
3114 | typedef struct _EdgeTableEntry { |
3115 | int ymax; /* ycoord at which we exit this edge. */ |
3116 | int ClockWise; /* flag for winding number rule */ |
3117 | BRESINFO bres; /* Bresenham info to run the edge */ |
3118 | struct _EdgeTableEntry *next; /* next in the list */ |
3119 | struct _EdgeTableEntry *back; /* for insertion sort */ |
3120 | struct _EdgeTableEntry *nextWETE; /* for winding num rule */ |
3121 | } EdgeTableEntry; |
3122 | |
3123 | |
3124 | typedef struct _ScanLineList{ |
3125 | int scanline; /* the scanline represented */ |
3126 | EdgeTableEntry *edgelist; /* header node */ |
3127 | struct _ScanLineList *next; /* next in the list */ |
3128 | } ScanLineList; |
3129 | |
3130 | |
3131 | typedef struct { |
3132 | int ymax; /* ymax for the polygon */ |
3133 | int ymin; /* ymin for the polygon */ |
3134 | ScanLineList scanlines; /* header node */ |
3135 | } EdgeTable; |
3136 | |
3137 | |
3138 | /* |
3139 | * Here is a struct to help with storage allocation |
3140 | * so we can allocate a big chunk at a time, and then take |
3141 | * pieces from this heap when we need to. |
3142 | */ |
3143 | #define SLLSPERBLOCK 25 |
3144 | |
3145 | typedef struct _ScanLineListBlock { |
3146 | ScanLineList SLLs[SLLSPERBLOCK]; |
3147 | struct _ScanLineListBlock *next; |
3148 | } ScanLineListBlock; |
3149 | |
3150 | |
3151 | |
3152 | /* |
3153 | * |
3154 | * a few macros for the inner loops of the fill code where |
3155 | * performance considerations don't allow a procedure call. |
3156 | * |
3157 | * Evaluate the given edge at the given scanline. |
3158 | * If the edge has expired, then we leave it and fix up |
3159 | * the active edge table; otherwise, we increment the |
3160 | * x value to be ready for the next scanline. |
3161 | * The winding number rule is in effect, so we must notify |
3162 | * the caller when the edge has been removed so he |
3163 | * can reorder the Winding Active Edge Table. |
3164 | */ |
3165 | #define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \ |
3166 | if (pAET->ymax == y) { /* leaving this edge */ \ |
3167 | pPrevAET->next = pAET->next; \ |
3168 | pAET = pPrevAET->next; \ |
3169 | fixWAET = 1; \ |
3170 | if (pAET) \ |
3171 | pAET->back = pPrevAET; \ |
3172 | } \ |
3173 | else { \ |
3174 | BRESINCRPGONSTRUCT(pAET->bres) \ |
3175 | pPrevAET = pAET; \ |
3176 | pAET = pAET->next; \ |
3177 | } \ |
3178 | } |
3179 | |
3180 | |
3181 | /* |
3182 | * Evaluate the given edge at the given scanline. |
3183 | * If the edge has expired, then we leave it and fix up |
3184 | * the active edge table; otherwise, we increment the |
3185 | * x value to be ready for the next scanline. |
3186 | * The even-odd rule is in effect. |
3187 | */ |
3188 | #define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \ |
3189 | if (pAET->ymax == y) { /* leaving this edge */ \ |
3190 | pPrevAET->next = pAET->next; \ |
3191 | pAET = pPrevAET->next; \ |
3192 | if (pAET) \ |
3193 | pAET->back = pPrevAET; \ |
3194 | } \ |
3195 | else { \ |
3196 | BRESINCRPGONSTRUCT(pAET->bres) \ |
3197 | pPrevAET = pAET; \ |
3198 | pAET = pAET->next; \ |
3199 | } \ |
3200 | } |
3201 | // END OF poly.h extract |
3202 | // START OF PolyReg.c extract |
3203 | /* $XConsortium: PolyReg.c,v 11.23 94/11/17 21:59:37 converse Exp $ */ |
3204 | /************************************************************************ |
3205 | |
3206 | Copyright (c) 1987 X Consortium |
3207 | |
3208 | Permission is hereby granted, free of charge, to any person obtaining a copy |
3209 | of this software and associated documentation files (the "Software"), to deal |
3210 | in the Software without restriction, including without limitation the rights |
3211 | to use, copy, modify, merge, publish, distribute, sublicense, and/or sell |
3212 | copies of the Software, and to permit persons to whom the Software is |
3213 | furnished to do so, subject to the following conditions: |
3214 | |
3215 | The above copyright notice and this permission notice shall be included in |
3216 | all copies or substantial portions of the Software. |
3217 | |
3218 | THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
3219 | IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
3220 | FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE |
3221 | X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN |
3222 | AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN |
3223 | CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. |
3224 | |
3225 | Except as contained in this notice, the name of the X Consortium shall not be |
3226 | used in advertising or otherwise to promote the sale, use or other dealings |
3227 | in this Software without prior written authorization from the X Consortium. |
3228 | |
3229 | |
3230 | Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts. |
3231 | |
3232 | All Rights Reserved |
3233 | |
3234 | Permission to use, copy, modify, and distribute this software and its |
3235 | documentation for any purpose and without fee is hereby granted, |
3236 | provided that the above copyright notice appear in all copies and that |
3237 | both that copyright notice and this permission notice appear in |
3238 | supporting documentation, and that the name of Digital not be |
3239 | used in advertising or publicity pertaining to distribution of the |
3240 | software without specific, written prior permission. |
3241 | |
3242 | DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING |
3243 | ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL |
3244 | DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR |
3245 | ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, |
3246 | WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, |
3247 | ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS |
3248 | SOFTWARE. |
3249 | |
3250 | ************************************************************************/ |
3251 | /* $XFree86: xc/lib/X11/PolyReg.c,v 1.1.1.2.8.2 1998/10/04 15:22:49 hohndel Exp $ */ |
3252 | |
3253 | #define LARGE_COORDINATE INT_MAX |
3254 | #define SMALL_COORDINATE INT_MIN |
3255 | |
3256 | /* |
3257 | * InsertEdgeInET |
3258 | * |
3259 | * Insert the given edge into the edge table. |
3260 | * First we must find the correct bucket in the |
3261 | * Edge table, then find the right slot in the |
3262 | * bucket. Finally, we can insert it. |
3263 | * |
3264 | */ |
3265 | static void InsertEdgeInET(EdgeTable *ET, EdgeTableEntry *ETE, int scanline, |
3266 | ScanLineListBlock **SLLBlock, int *iSLLBlock) |
3267 | { |
3268 | EdgeTableEntry *start, *prev; |
3269 | ScanLineList *pSLL, *pPrevSLL; |
3270 | ScanLineListBlock *tmpSLLBlock; |
3271 | |
3272 | /* |
3273 | * find the right bucket to put the edge into |
3274 | */ |
3275 | pPrevSLL = &ET->scanlines; |
3276 | pSLL = pPrevSLL->next; |
3277 | while (pSLL && (pSLL->scanline < scanline)) { |
3278 | pPrevSLL = pSLL; |
3279 | pSLL = pSLL->next; |
3280 | } |
3281 | |
3282 | /* |
3283 | * reassign pSLL (pointer to ScanLineList) if necessary |
3284 | */ |
3285 | if ((!pSLL) || (pSLL->scanline > scanline)) { |
3286 | if (*iSLLBlock > SLLSPERBLOCK-1) |
3287 | { |
3288 | tmpSLLBlock = |
3289 | (ScanLineListBlock *)malloc(sizeof(ScanLineListBlock)); |
3290 | Q_CHECK_PTR(tmpSLLBlock); |
3291 | (*SLLBlock)->next = tmpSLLBlock; |
3292 | tmpSLLBlock->next = (ScanLineListBlock *)NULL; |
3293 | *SLLBlock = tmpSLLBlock; |
3294 | *iSLLBlock = 0; |
3295 | } |
3296 | pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]); |
3297 | |
3298 | pSLL->next = pPrevSLL->next; |
3299 | pSLL->edgelist = (EdgeTableEntry *)NULL; |
3300 | pPrevSLL->next = pSLL; |
3301 | } |
3302 | pSLL->scanline = scanline; |
3303 | |
3304 | /* |
3305 | * now insert the edge in the right bucket |
3306 | */ |
3307 | prev = 0; |
3308 | start = pSLL->edgelist; |
3309 | while (start && (start->bres.minor_axis < ETE->bres.minor_axis)) { |
3310 | prev = start; |
3311 | start = start->next; |
3312 | } |
3313 | ETE->next = start; |
3314 | |
3315 | if (prev) |
3316 | prev->next = ETE; |
3317 | else |
3318 | pSLL->edgelist = ETE; |
3319 | } |
3320 | |
3321 | /* |
3322 | * CreateEdgeTable |
3323 | * |
3324 | * This routine creates the edge table for |
3325 | * scan converting polygons. |
3326 | * The Edge Table (ET) looks like: |
3327 | * |
3328 | * EdgeTable |
3329 | * -------- |
3330 | * | ymax | ScanLineLists |
3331 | * |scanline|-->------------>-------------->... |
3332 | * -------- |scanline| |scanline| |
3333 | * |edgelist| |edgelist| |
3334 | * --------- --------- |
3335 | * | | |
3336 | * | | |
3337 | * V V |
3338 | * list of ETEs list of ETEs |
3339 | * |
3340 | * where ETE is an EdgeTableEntry data structure, |
3341 | * and there is one ScanLineList per scanline at |
3342 | * which an edge is initially entered. |
3343 | * |
3344 | */ |
3345 | |
3346 | static void CreateETandAET(int count, const QPoint *pts, |
3347 | EdgeTable *ET, EdgeTableEntry *AET, EdgeTableEntry *pETEs, |
3348 | ScanLineListBlock *pSLLBlock) |
3349 | { |
3350 | const QPoint *top, |
3351 | *bottom, |
3352 | *PrevPt, |
3353 | *CurrPt; |
3354 | int iSLLBlock = 0; |
3355 | int dy; |
3356 | |
3357 | if (count < 2) |
3358 | return; |
3359 | |
3360 | /* |
3361 | * initialize the Active Edge Table |
3362 | */ |
3363 | AET->next = 0; |
3364 | AET->back = 0; |
3365 | AET->nextWETE = 0; |
3366 | AET->bres.minor_axis = SMALL_COORDINATE; |
3367 | |
3368 | /* |
3369 | * initialize the Edge Table. |
3370 | */ |
3371 | ET->scanlines.next = 0; |
3372 | ET->ymax = SMALL_COORDINATE; |
3373 | ET->ymin = LARGE_COORDINATE; |
3374 | pSLLBlock->next = 0; |
3375 | |
3376 | PrevPt = &pts[count - 1]; |
3377 | |
3378 | /* |
3379 | * for each vertex in the array of points. |
3380 | * In this loop we are dealing with two vertices at |
3381 | * a time -- these make up one edge of the polygon. |
3382 | */ |
3383 | while (count--) { |
3384 | CurrPt = pts++; |
3385 | |
3386 | /* |
3387 | * find out which point is above and which is below. |
3388 | */ |
3389 | if (PrevPt->y() > CurrPt->y()) { |
3390 | bottom = PrevPt; |
3391 | top = CurrPt; |
3392 | pETEs->ClockWise = 0; |
3393 | } else { |
3394 | bottom = CurrPt; |
3395 | top = PrevPt; |
3396 | pETEs->ClockWise = 1; |
3397 | } |
3398 | |
3399 | /* |
3400 | * don't add horizontal edges to the Edge table. |
3401 | */ |
3402 | if (bottom->y() != top->y()) { |
3403 | pETEs->ymax = bottom->y() - 1; /* -1 so we don't get last scanline */ |
3404 | |
3405 | /* |
3406 | * initialize integer edge algorithm |
3407 | */ |
3408 | dy = bottom->y() - top->y(); |
3409 | BRESINITPGONSTRUCT(dy, top->x(), bottom->x(), pETEs->bres) |
3410 | |
3411 | InsertEdgeInET(ET, pETEs, top->y(), &pSLLBlock, &iSLLBlock); |
3412 | |
3413 | if (PrevPt->y() > ET->ymax) |
3414 | ET->ymax = PrevPt->y(); |
3415 | if (PrevPt->y() < ET->ymin) |
3416 | ET->ymin = PrevPt->y(); |
3417 | ++pETEs; |
3418 | } |
3419 | |
3420 | PrevPt = CurrPt; |
3421 | } |
3422 | } |
3423 | |
3424 | /* |
3425 | * loadAET |
3426 | * |
3427 | * This routine moves EdgeTableEntries from the |
3428 | * EdgeTable into the Active Edge Table, |
3429 | * leaving them sorted by smaller x coordinate. |
3430 | * |
3431 | */ |
3432 | |
3433 | static void loadAET(EdgeTableEntry *AET, EdgeTableEntry *ETEs) |
3434 | { |
3435 | EdgeTableEntry *pPrevAET; |
3436 | EdgeTableEntry *tmp; |
3437 | |
3438 | pPrevAET = AET; |
3439 | AET = AET->next; |
3440 | while (ETEs) { |
3441 | while (AET && AET->bres.minor_axis < ETEs->bres.minor_axis) { |
3442 | pPrevAET = AET; |
3443 | AET = AET->next; |
3444 | } |
3445 | tmp = ETEs->next; |
3446 | ETEs->next = AET; |
3447 | if (AET) |
3448 | AET->back = ETEs; |
3449 | ETEs->back = pPrevAET; |
3450 | pPrevAET->next = ETEs; |
3451 | pPrevAET = ETEs; |
3452 | |
3453 | ETEs = tmp; |
3454 | } |
3455 | } |
3456 | |
3457 | /* |
3458 | * computeWAET |
3459 | * |
3460 | * This routine links the AET by the |
3461 | * nextWETE (winding EdgeTableEntry) link for |
3462 | * use by the winding number rule. The final |
3463 | * Active Edge Table (AET) might look something |
3464 | * like: |
3465 | * |
3466 | * AET |
3467 | * ---------- --------- --------- |
3468 | * |ymax | |ymax | |ymax | |
3469 | * | ... | |... | |... | |
3470 | * |next |->|next |->|next |->... |
3471 | * |nextWETE| |nextWETE| |nextWETE| |
3472 | * --------- --------- ^-------- |
3473 | * | | | |
3474 | * V-------------------> V---> ... |
3475 | * |
3476 | */ |
3477 | static void computeWAET(EdgeTableEntry *AET) |
3478 | { |
3479 | EdgeTableEntry *pWETE; |
3480 | int inside = 1; |
3481 | int isInside = 0; |
3482 | |
3483 | AET->nextWETE = 0; |
3484 | pWETE = AET; |
3485 | AET = AET->next; |
3486 | while (AET) { |
3487 | if (AET->ClockWise) |
3488 | ++isInside; |
3489 | else |
3490 | --isInside; |
3491 | |
3492 | if ((!inside && !isInside) || (inside && isInside)) { |
3493 | pWETE->nextWETE = AET; |
3494 | pWETE = AET; |
3495 | inside = !inside; |
3496 | } |
3497 | AET = AET->next; |
3498 | } |
3499 | pWETE->nextWETE = 0; |
3500 | } |
3501 | |
3502 | /* |
3503 | * InsertionSort |
3504 | * |
3505 | * Just a simple insertion sort using |
3506 | * pointers and back pointers to sort the Active |
3507 | * Edge Table. |
3508 | * |
3509 | */ |
3510 | |
3511 | static int InsertionSort(EdgeTableEntry *AET) |
3512 | { |
3513 | EdgeTableEntry *pETEchase; |
3514 | EdgeTableEntry *pETEinsert; |
3515 | EdgeTableEntry *pETEchaseBackTMP; |
3516 | int changed = 0; |
3517 | |
3518 | AET = AET->next; |
3519 | while (AET) { |
3520 | pETEinsert = AET; |
3521 | pETEchase = AET; |
3522 | while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis) |
3523 | pETEchase = pETEchase->back; |
3524 | |
3525 | AET = AET->next; |
3526 | if (pETEchase != pETEinsert) { |
3527 | pETEchaseBackTMP = pETEchase->back; |
3528 | pETEinsert->back->next = AET; |
3529 | if (AET) |
3530 | AET->back = pETEinsert->back; |
3531 | pETEinsert->next = pETEchase; |
3532 | pETEchase->back->next = pETEinsert; |
3533 | pETEchase->back = pETEinsert; |
3534 | pETEinsert->back = pETEchaseBackTMP; |
3535 | changed = 1; |
3536 | } |
3537 | } |
3538 | return changed; |
3539 | } |
3540 | |
3541 | /* |
3542 | * Clean up our act. |
3543 | */ |
3544 | static void FreeStorage(ScanLineListBlock *pSLLBlock) |
3545 | { |
3546 | ScanLineListBlock *tmpSLLBlock; |
3547 | |
3548 | while (pSLLBlock) { |
3549 | tmpSLLBlock = pSLLBlock->next; |
3550 | free(pSLLBlock); |
3551 | pSLLBlock = tmpSLLBlock; |
3552 | } |
3553 | } |
3554 | |
3555 | struct QRegionSpan { |
3556 | QRegionSpan() {} |
3557 | QRegionSpan(int x1_, int x2_) : x1(x1_), x2(x2_) {} |
3558 | |
3559 | int x1; |
3560 | int x2; |
3561 | int width() const { return x2 - x1; } |
3562 | }; |
3563 | |
3564 | Q_DECLARE_TYPEINFO(QRegionSpan, Q_PRIMITIVE_TYPE); |
3565 | |
3566 | static inline void flushRow(const QRegionSpan *spans, int y, int numSpans, QRegionPrivate *reg, int *lastRow, int *extendTo, bool *needsExtend) |
3567 | { |
3568 | QRect *regRects = reg->rects.data() + *lastRow; |
3569 | bool canExtend = reg->rects.size() - *lastRow == numSpans |
3570 | && !(*needsExtend && *extendTo + 1 != y) |
3571 | && (*needsExtend || regRects[0].y() + regRects[0].height() == y); |
3572 | |
3573 | for (int i = 0; i < numSpans && canExtend; ++i) { |
3574 | if (regRects[i].x() != spans[i].x1 || regRects[i].right() != spans[i].x2 - 1) |
3575 | canExtend = false; |
3576 | } |
3577 | |
3578 | if (canExtend) { |
3579 | *extendTo = y; |
3580 | *needsExtend = true; |
3581 | } else { |
3582 | if (*needsExtend) { |
3583 | for (int i = 0; i < reg->rects.size() - *lastRow; ++i) |
3584 | regRects[i].setBottom(*extendTo); |
3585 | } |
3586 | |
3587 | *lastRow = reg->rects.size(); |
3588 | reg->rects.reserve(*lastRow + numSpans); |
3589 | for (int i = 0; i < numSpans; ++i) |
3590 | reg->rects << QRect(spans[i].x1, y, spans[i].width(), 1); |
3591 | |
3592 | if (spans[0].x1 < reg->extents.left()) |
3593 | reg->extents.setLeft(spans[0].x1); |
3594 | |
3595 | if (spans[numSpans-1].x2 - 1 > reg->extents.right()) |
3596 | reg->extents.setRight(spans[numSpans-1].x2 - 1); |
3597 | |
3598 | *needsExtend = false; |
3599 | } |
3600 | } |
3601 | |
3602 | /* |
3603 | * Create an array of rectangles from a list of points. |
3604 | * If indeed these things (POINTS, RECTS) are the same, |
3605 | * then this proc is still needed, because it allocates |
3606 | * storage for the array, which was allocated on the |
3607 | * stack by the calling procedure. |
3608 | * |
3609 | */ |
3610 | static void PtsToRegion(int numFullPtBlocks, int iCurPtBlock, |
3611 | POINTBLOCK *FirstPtBlock, QRegionPrivate *reg) |
3612 | { |
3613 | int lastRow = 0; |
3614 | int extendTo = 0; |
3615 | bool needsExtend = false; |
3616 | QVarLengthArray<QRegionSpan> row; |
3617 | int rowSize = 0; |
3618 | |
3619 | reg->extents.setLeft(INT_MAX); |
3620 | reg->extents.setRight(INT_MIN); |
3621 | reg->innerArea = -1; |
3622 | |
3623 | POINTBLOCK *CurPtBlock = FirstPtBlock; |
3624 | for (; numFullPtBlocks >= 0; --numFullPtBlocks) { |
3625 | /* the loop uses 2 points per iteration */ |
3626 | int i = NUMPTSTOBUFFER >> 1; |
3627 | if (!numFullPtBlocks) |
3628 | i = iCurPtBlock >> 1; |
3629 | if(i) { |
3630 | row.resize(qMax(row.size(), rowSize + i)); |
3631 | for (QPoint *pts = CurPtBlock->pts; i--; pts += 2) { |
3632 | const int width = pts[1].x() - pts[0].x(); |
3633 | if (width) { |
3634 | if (rowSize && row[rowSize-1].x2 == pts[0].x()) |
3635 | row[rowSize-1].x2 = pts[1].x(); |
3636 | else |
3637 | row[rowSize++] = QRegionSpan(pts[0].x(), pts[1].x()); |
3638 | } |
3639 | |
3640 | if (rowSize) { |
3641 | QPoint *next = i ? &pts[2] : (numFullPtBlocks && iCurPtBlock ? CurPtBlock->next->pts : nullptr); |
3642 | |
3643 | if (!next || next->y() != pts[0].y()) { |
3644 | flushRow(row.data(), pts[0].y(), rowSize, reg, &lastRow, &extendTo, &needsExtend); |
3645 | rowSize = 0; |
3646 | } |
3647 | } |
3648 | } |
3649 | } |
3650 | CurPtBlock = CurPtBlock->next; |
3651 | } |
3652 | |
3653 | if (needsExtend) { |
3654 | for (int i = lastRow; i < reg->rects.size(); ++i) |
3655 | reg->rects[i].setBottom(extendTo); |
3656 | } |
3657 | |
3658 | reg->numRects = reg->rects.size(); |
3659 | |
3660 | if (reg->numRects) { |
3661 | reg->extents.setTop(reg->rects[0].top()); |
3662 | reg->extents.setBottom(reg->rects[lastRow].bottom()); |
3663 | |
3664 | for (int i = 0; i < reg->rects.size(); ++i) |
3665 | reg->updateInnerRect(reg->rects[i]); |
3666 | } else { |
3667 | reg->extents.setCoords(0, 0, 0, 0); |
3668 | } |
3669 | } |
3670 | |
3671 | /* |
3672 | * polytoregion |
3673 | * |
3674 | * Scan converts a polygon by returning a run-length |
3675 | * encoding of the resultant bitmap -- the run-length |
3676 | * encoding is in the form of an array of rectangles. |
3677 | * |
3678 | * Can return 0 in case of errors. |
3679 | */ |
3680 | static QRegionPrivate *PolygonRegion(const QPoint *Pts, int Count, int rule) |
3681 | //Point *Pts; /* the pts */ |
3682 | //int Count; /* number of pts */ |
3683 | //int rule; /* winding rule */ |
3684 | { |
3685 | QRegionPrivate *region; |
3686 | EdgeTableEntry *pAET; /* Active Edge Table */ |
3687 | int y; /* current scanline */ |
3688 | int iPts = 0; /* number of pts in buffer */ |
3689 | EdgeTableEntry *pWETE; /* Winding Edge Table Entry*/ |
3690 | ScanLineList *pSLL; /* current scanLineList */ |
3691 | QPoint *pts; /* output buffer */ |
3692 | EdgeTableEntry *pPrevAET; /* ptr to previous AET */ |
3693 | EdgeTable ET; /* header node for ET */ |
3694 | EdgeTableEntry *AET; /* header node for AET */ |
3695 | EdgeTableEntry *pETEs; /* EdgeTableEntries pool */ |
3696 | ScanLineListBlock SLLBlock; /* header for scanlinelist */ |
3697 | int fixWAET = false; |
3698 | POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers */ |
3699 | FirstPtBlock.pts = reinterpret_cast<QPoint *>(FirstPtBlock.data); |
3700 | POINTBLOCK *tmpPtBlock; |
3701 | int numFullPtBlocks = 0; |
3702 | |
3703 | region = new QRegionPrivate; |
3704 | |
3705 | /* special case a rectangle */ |
3706 | if (((Count == 4) || |
3707 | ((Count == 5) && (Pts[4].x() == Pts[0].x()) && (Pts[4].y() == Pts[0].y()))) |
3708 | && (((Pts[0].y() == Pts[1].y()) && (Pts[1].x() == Pts[2].x()) && (Pts[2].y() == Pts[3].y()) |
3709 | && (Pts[3].x() == Pts[0].x())) || ((Pts[0].x() == Pts[1].x()) |
3710 | && (Pts[1].y() == Pts[2].y()) && (Pts[2].x() == Pts[3].x()) |
3711 | && (Pts[3].y() == Pts[0].y())))) { |
3712 | int x = qMin(Pts[0].x(), Pts[2].x()); |
3713 | region->extents.setLeft(x); |
3714 | int y = qMin(Pts[0].y(), Pts[2].y()); |
3715 | region->extents.setTop(y); |
3716 | region->extents.setWidth(qMax(Pts[0].x(), Pts[2].x()) - x); |
3717 | region->extents.setHeight(qMax(Pts[0].y(), Pts[2].y()) - y); |
3718 | if ((region->extents.left() <= region->extents.right()) && |
3719 | (region->extents.top() <= region->extents.bottom())) { |
3720 | region->numRects = 1; |
3721 | region->innerRect = region->extents; |
3722 | region->innerArea = region->innerRect.width() * region->innerRect.height(); |
3723 | } |
3724 | return region; |
3725 | } |
3726 | |
3727 | if (!(pETEs = static_cast<EdgeTableEntry *>(malloc(sizeof(EdgeTableEntry) * Count)))) { |
3728 | delete region; |
3729 | return 0; |
3730 | } |
3731 | |
3732 | region->vectorize(); |
3733 | |
3734 | AET = new EdgeTableEntry; |
3735 | pts = FirstPtBlock.pts; |
3736 | CreateETandAET(Count, Pts, &ET, AET, pETEs, &SLLBlock); |
3737 | |
3738 | pSLL = ET.scanlines.next; |
3739 | curPtBlock = &FirstPtBlock; |
3740 | |
3741 | // sanity check that the region won't become too big... |
3742 | if (ET.ymax - ET.ymin > 100000) { |
3743 | // clean up region ptr |
3744 | #ifndef QT_NO_DEBUG |
3745 | qWarning("QRegion: creating region from big polygon failed...!" ); |
3746 | #endif |
3747 | delete AET; |
3748 | delete region; |
3749 | return 0; |
3750 | } |
3751 | |
3752 | |
3753 | QT_TRY { |
3754 | if (rule == EvenOddRule) { |
3755 | /* |
3756 | * for each scanline |
3757 | */ |
3758 | for (y = ET.ymin; y < ET.ymax; ++y) { |
3759 | |
3760 | /* |
3761 | * Add a new edge to the active edge table when we |
3762 | * get to the next edge. |
3763 | */ |
3764 | if (pSLL && y == pSLL->scanline) { |
3765 | loadAET(AET, pSLL->edgelist); |
3766 | pSLL = pSLL->next; |
3767 | } |
3768 | pPrevAET = AET; |
3769 | pAET = AET->next; |
3770 | |
3771 | /* |
3772 | * for each active edge |
3773 | */ |
3774 | while (pAET) { |
3775 | pts->setX(pAET->bres.minor_axis); |
3776 | pts->setY(y); |
3777 | ++pts; |
3778 | ++iPts; |
3779 | |
3780 | /* |
3781 | * send out the buffer |
3782 | */ |
3783 | if (iPts == NUMPTSTOBUFFER) { |
3784 | tmpPtBlock = (POINTBLOCK *)malloc(sizeof(POINTBLOCK)); |
3785 | Q_CHECK_PTR(tmpPtBlock); |
3786 | tmpPtBlock->pts = reinterpret_cast<QPoint *>(tmpPtBlock->data); |
3787 | curPtBlock->next = tmpPtBlock; |
3788 | curPtBlock = tmpPtBlock; |
3789 | pts = curPtBlock->pts; |
3790 | ++numFullPtBlocks; |
3791 | iPts = 0; |
3792 | } |
3793 | EVALUATEEDGEEVENODD(pAET, pPrevAET, y) |
3794 | } |
3795 | InsertionSort(AET); |
3796 | } |
3797 | } else { |
3798 | /* |
3799 | * for each scanline |
3800 | */ |
3801 | for (y = ET.ymin; y < ET.ymax; ++y) { |
3802 | /* |
3803 | * Add a new edge to the active edge table when we |
3804 | * get to the next edge. |
3805 | */ |
3806 | if (pSLL && y == pSLL->scanline) { |
3807 | loadAET(AET, pSLL->edgelist); |
3808 | computeWAET(AET); |
3809 | pSLL = pSLL->next; |
3810 | } |
3811 | pPrevAET = AET; |
3812 | pAET = AET->next; |
3813 | pWETE = pAET; |
3814 | |
3815 | /* |
3816 | * for each active edge |
3817 | */ |
3818 | while (pAET) { |
3819 | /* |
3820 | * add to the buffer only those edges that |
3821 | * are in the Winding active edge table. |
3822 | */ |
3823 | if (pWETE == pAET) { |
3824 | pts->setX(pAET->bres.minor_axis); |
3825 | pts->setY(y); |
3826 | ++pts; |
3827 | ++iPts; |
3828 | |
3829 | /* |
3830 | * send out the buffer |
3831 | */ |
3832 | if (iPts == NUMPTSTOBUFFER) { |
3833 | tmpPtBlock = static_cast<POINTBLOCK *>(malloc(sizeof(POINTBLOCK))); |
3834 | tmpPtBlock->pts = reinterpret_cast<QPoint *>(tmpPtBlock->data); |
3835 | curPtBlock->next = tmpPtBlock; |
3836 | curPtBlock = tmpPtBlock; |
3837 | pts = curPtBlock->pts; |
3838 | ++numFullPtBlocks; |
3839 | iPts = 0; |
3840 | } |
3841 | pWETE = pWETE->nextWETE; |
3842 | } |
3843 | EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) |
3844 | } |
3845 | |
3846 | /* |
3847 | * recompute the winding active edge table if |
3848 | * we just resorted or have exited an edge. |
3849 | */ |
3850 | if (InsertionSort(AET) || fixWAET) { |
3851 | computeWAET(AET); |
3852 | fixWAET = false; |
3853 | } |
3854 | } |
3855 | } |
3856 | } QT_CATCH(...) { |
3857 | FreeStorage(SLLBlock.next); |
3858 | PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region); |
3859 | for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) { |
3860 | tmpPtBlock = curPtBlock->next; |
3861 | free(curPtBlock); |
3862 | curPtBlock = tmpPtBlock; |
3863 | } |
3864 | free(pETEs); |
3865 | return 0; // this function returns 0 in case of an error |
3866 | } |
3867 | |
3868 | FreeStorage(SLLBlock.next); |
3869 | PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region); |
3870 | for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) { |
3871 | tmpPtBlock = curPtBlock->next; |
3872 | free(curPtBlock); |
3873 | curPtBlock = tmpPtBlock; |
3874 | } |
3875 | delete AET; |
3876 | free(pETEs); |
3877 | return region; |
3878 | } |
3879 | // END OF PolyReg.c extract |
3880 | |
3881 | QRegionPrivate *qt_bitmapToRegion(const QBitmap& bitmap) |
3882 | { |
3883 | const QImage image = bitmap.toImage(); |
3884 | |
3885 | QRegionPrivate *region = new QRegionPrivate; |
3886 | |
3887 | QRect xr; |
3888 | |
3889 | #define AddSpan \ |
3890 | { \ |
3891 | xr.setCoords(prev1, y, x-1, y); \ |
3892 | UnionRectWithRegion(&xr, region, *region); \ |
3893 | } |
3894 | |
3895 | const uchar zero = 0; |
3896 | bool little = image.format() == QImage::Format_MonoLSB; |
3897 | |
3898 | int x, |
3899 | y; |
3900 | for (y = 0; y < image.height(); ++y) { |
3901 | const uchar *line = image.constScanLine(y); |
3902 | int w = image.width(); |
3903 | uchar all = zero; |
3904 | int prev1 = -1; |
3905 | for (x = 0; x < w;) { |
3906 | uchar byte = line[x / 8]; |
3907 | if (x > w - 8 || byte!=all) { |
3908 | if (little) { |
3909 | for (int b = 8; b > 0 && x < w; --b) { |
3910 | if (!(byte & 0x01) == !all) { |
3911 | // More of the same |
3912 | } else { |
3913 | // A change. |
3914 | if (all!=zero) { |
3915 | AddSpan |
3916 | all = zero; |
3917 | } else { |
3918 | prev1 = x; |
3919 | all = ~zero; |
3920 | } |
3921 | } |
3922 | byte >>= 1; |
3923 | ++x; |
3924 | } |
3925 | } else { |
3926 | for (int b = 8; b > 0 && x < w; --b) { |
3927 | if (!(byte & 0x80) == !all) { |
3928 | // More of the same |
3929 | } else { |
3930 | // A change. |
3931 | if (all != zero) { |
3932 | AddSpan |
3933 | all = zero; |
3934 | } else { |
3935 | prev1 = x; |
3936 | all = ~zero; |
3937 | } |
3938 | } |
3939 | byte <<= 1; |
3940 | ++x; |
3941 | } |
3942 | } |
3943 | } else { |
3944 | x += 8; |
3945 | } |
3946 | } |
3947 | if (all != zero) { |
3948 | AddSpan |
3949 | } |
3950 | } |
3951 | #undef AddSpan |
3952 | |
3953 | return region; |
3954 | } |
3955 | |
3956 | QRegion::QRegion() |
3957 | : d(const_cast<QRegionData*>(&shared_empty)) |
3958 | { |
3959 | } |
3960 | |
3961 | QRegion::QRegion(const QRect &r, RegionType t) |
3962 | { |
3963 | if (r.isEmpty()) { |
3964 | d = const_cast<QRegionData*>(&shared_empty); |
3965 | } else { |
3966 | d = new QRegionData; |
3967 | d->ref.initializeOwned(); |
3968 | if (t == Rectangle) { |
3969 | d->qt_rgn = new QRegionPrivate(r); |
3970 | } else if (t == Ellipse) { |
3971 | QPainterPath path; |
3972 | path.addEllipse(r.x(), r.y(), r.width(), r.height()); |
3973 | QPolygon a = path.toSubpathPolygons().at(0).toPolygon(); |
3974 | d->qt_rgn = PolygonRegion(a.constData(), a.size(), EvenOddRule); |
3975 | } |
3976 | } |
3977 | } |
3978 | |
3979 | QRegion::QRegion(const QPolygon &a, Qt::FillRule fillRule) |
3980 | { |
3981 | if (a.count() > 2) { |
3982 | QRegionPrivate *qt_rgn = PolygonRegion(a.constData(), a.size(), |
3983 | fillRule == Qt::WindingFill ? WindingRule : EvenOddRule); |
3984 | if (qt_rgn) { |
3985 | d = new QRegionData; |
3986 | d->ref.initializeOwned(); |
3987 | d->qt_rgn = qt_rgn; |
3988 | } else { |
3989 | d = const_cast<QRegionData*>(&shared_empty); |
3990 | } |
3991 | } else { |
3992 | d = const_cast<QRegionData*>(&shared_empty); |
3993 | } |
3994 | } |
3995 | |
3996 | QRegion::QRegion(const QRegion &r) |
3997 | { |
3998 | d = r.d; |
3999 | d->ref.ref(); |
4000 | } |
4001 | |
4002 | |
4003 | QRegion::QRegion(const QBitmap &bm) |
4004 | { |
4005 | if (bm.isNull()) { |
4006 | d = const_cast<QRegionData*>(&shared_empty); |
4007 | } else { |
4008 | d = new QRegionData; |
4009 | d->ref.initializeOwned(); |
4010 | d->qt_rgn = qt_bitmapToRegion(bm); |
4011 | } |
4012 | } |
4013 | |
4014 | void QRegion::cleanUp(QRegion::QRegionData *x) |
4015 | { |
4016 | delete x->qt_rgn; |
4017 | delete x; |
4018 | } |
4019 | |
4020 | QRegion::~QRegion() |
4021 | { |
4022 | if (!d->ref.deref()) |
4023 | cleanUp(d); |
4024 | } |
4025 | |
4026 | |
4027 | QRegion &QRegion::operator=(const QRegion &r) |
4028 | { |
4029 | r.d->ref.ref(); |
4030 | if (!d->ref.deref()) |
4031 | cleanUp(d); |
4032 | d = r.d; |
4033 | return *this; |
4034 | } |
4035 | |
4036 | |
4037 | /*! |
4038 | \internal |
4039 | */ |
4040 | QRegion QRegion::copy() const |
4041 | { |
4042 | QRegion r; |
4043 | QScopedPointer<QRegionData> x(new QRegionData); |
4044 | x->ref.initializeOwned(); |
4045 | if (d->qt_rgn) |
4046 | x->qt_rgn = new QRegionPrivate(*d->qt_rgn); |
4047 | else |
4048 | x->qt_rgn = new QRegionPrivate; |
4049 | if (!r.d->ref.deref()) |
4050 | cleanUp(r.d); |
4051 | r.d = x.take(); |
4052 | return r; |
4053 | } |
4054 | |
4055 | bool QRegion::isEmpty() const |
4056 | { |
4057 | return d == &shared_empty || d->qt_rgn->numRects == 0; |
4058 | } |
4059 | |
4060 | bool QRegion::isNull() const |
4061 | { |
4062 | return d == &shared_empty || d->qt_rgn->numRects == 0; |
4063 | } |
4064 | |
4065 | bool QRegion::contains(const QPoint &p) const |
4066 | { |
4067 | return PointInRegion(d->qt_rgn, p.x(), p.y()); |
4068 | } |
4069 | |
4070 | bool QRegion::contains(const QRect &r) const |
4071 | { |
4072 | return RectInRegion(d->qt_rgn, r.left(), r.top(), r.width(), r.height()) != RectangleOut; |
4073 | } |
4074 | |
4075 | |
4076 | |
4077 | void QRegion::translate(int dx, int dy) |
4078 | { |
4079 | if ((dx == 0 && dy == 0) || isEmptyHelper(d->qt_rgn)) |
4080 | return; |
4081 | |
4082 | detach(); |
4083 | OffsetRegion(*d->qt_rgn, dx, dy); |
4084 | } |
4085 | |
4086 | QRegion QRegion::united(const QRegion &r) const |
4087 | { |
4088 | if (isEmptyHelper(d->qt_rgn)) |
4089 | return r; |
4090 | if (isEmptyHelper(r.d->qt_rgn)) |
4091 | return *this; |
4092 | if (d == r.d) |
4093 | return *this; |
4094 | |
4095 | if (d->qt_rgn->contains(*r.d->qt_rgn)) { |
4096 | return *this; |
4097 | } else if (r.d->qt_rgn->contains(*d->qt_rgn)) { |
4098 | return r; |
4099 | } else if (d->qt_rgn->canAppend(r.d->qt_rgn)) { |
4100 | QRegion result(*this); |
4101 | result.detach(); |
4102 | result.d->qt_rgn->append(r.d->qt_rgn); |
4103 | return result; |
4104 | } else if (d->qt_rgn->canPrepend(r.d->qt_rgn)) { |
4105 | QRegion result(*this); |
4106 | result.detach(); |
4107 | result.d->qt_rgn->prepend(r.d->qt_rgn); |
4108 | return result; |
4109 | } else if (EqualRegion(d->qt_rgn, r.d->qt_rgn)) { |
4110 | return |
---|