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 |