krita

kis_painter.cc

00001 /*
00002  *  Copyright (c) 2002 Patrick Julien <freak@codepimps.org>
00003  *  Copyright (c) 2004 Boudewijn Rempt <boud@valdyas.org>
00004  *  Copyright (c) 2004 Clarence Dang <dang@kde.org>
00005  *  Copyright (c) 2004 Adrian Page <adrian@pagenet.plus.com>
00006  *  Copyright (c) 2004 Cyrille Berger <cberger@cberger.net>
00007  *
00008  *  This program is free software; you can redistribute it and/or modify
00009  *  it under the terms of the GNU General Public License as published by
00010  *  the Free Software Foundation; either version 2 of the License, or
00011  *  (at your option) any later version.
00012  *
00013  *  This program is distributed in the hope that it will be useful,
00014  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00015  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00016  *  GNU General Public License for more details.
00017  *
00018  *  You should have received a copy of the GNU General Public License
00019  *  along with this program; if not, write to the Free Software
00020  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
00021  */
00022 #include <stdlib.h>
00023 #include <string.h>
00024 #include <cfloat>
00025 #include <cmath>
00026 #include <climits>
00027 #include <strings.h>
00028 
00029 #include "qbrush.h"
00030 #include "qfontinfo.h"
00031 #include "qfontmetrics.h"
00032 #include "qpen.h"
00033 #include "qregion.h"
00034 #include "qwmatrix.h"
00035 #include <qimage.h>
00036 #include <qmap.h>
00037 #include <qpainter.h>
00038 #include <qpixmap.h>
00039 #include <qpointarray.h>
00040 #include <qrect.h>
00041 #include <qstring.h>
00042 
00043 #include <kdebug.h>
00044 #include <kcommand.h>
00045 #include <klocale.h>
00046 
00047 #include "kis_brush.h"
00048 #include "kis_debug_areas.h"
00049 #include "kis_image.h"
00050 #include "kis_layer.h"
00051 #include "kis_paint_device.h"
00052 #include "kis_painter.h"
00053 #include "kis_pattern.h"
00054 #include "kis_rect.h"
00055 #include "kis_colorspace.h"
00056 #include "kis_transaction.h"
00057 #include "kis_types.h"
00058 #include "kis_vec.h"
00059 #include "kis_iterators_pixel.h"
00060 #include "kis_paintop.h"
00061 #include "kis_selection.h"
00062 #include "kis_fill_painter.h"
00063 #include "kis_color.h"
00064 
00065 // Maximum distance from a Bezier control point to the line through the start
00066 // and end points for the curve to be considered flat.
00067 #define BEZIER_FLATNESS_THRESHOLD 0.5
00068 
00069 KisPainter::KisPainter()
00070 {
00071     init();
00072 }
00073 
00074 KisPainter::KisPainter(KisPaintDeviceSP device)
00075 {
00076     init();
00077     Q_ASSERT(device);
00078         begin(device);
00079 }
00080 
00081 void KisPainter::init()
00082 {
00083     m_transaction = 0;
00084     m_paintOp = 0;
00085     m_filter = 0;
00086     m_brush = 0;
00087     m_pattern= 0;
00088     m_opacity = OPACITY_OPAQUE;
00089     m_compositeOp = COMPOSITE_OVER;
00090     m_dab = 0;
00091     m_fillStyle = FillStyleNone;
00092     m_strokeStyle = StrokeStyleBrush;
00093     m_pressure = PRESSURE_MIN;
00094 }
00095 
00096 KisPainter::~KisPainter()
00097 {
00098     m_brush = 0;
00099     delete m_paintOp;
00100     end();
00101 }
00102 
00103 void KisPainter::begin(KisPaintDeviceSP device)
00104 {
00105     if (!device) return;
00106 
00107     if (m_transaction)
00108         delete m_transaction;
00109 
00110     m_device = device;
00111     m_colorSpace = device->colorSpace();
00112     m_pixelSize = device->pixelSize();
00113 }
00114 
00115 KCommand *KisPainter::end()
00116 {
00117     return endTransaction();
00118 }
00119 
00120 void KisPainter::beginTransaction(const QString& customName)
00121 {
00122     if (m_transaction)
00123         delete m_transaction;
00124     m_transaction = new KisTransaction(customName, m_device);
00125     Q_CHECK_PTR(m_transaction);
00126 }
00127 
00128 void KisPainter::beginTransaction( KisTransaction* command)
00129 {
00130     if (m_transaction)
00131         delete m_transaction;
00132     m_transaction = command;
00133 }
00134 
00135 
00136 KCommand *KisPainter::endTransaction()
00137 {
00138     KCommand *command = m_transaction;
00139         m_transaction = 0;
00140         return command;
00141 }
00142 
00143 
00144 QRect KisPainter::dirtyRect() {
00145     QRect r = m_dirtyRect;
00146     m_dirtyRect = QRect();
00147     return r;
00148 }
00149 
00150 void KisPainter::bitBlt(Q_INT32 dx, Q_INT32 dy,
00151                         const KisCompositeOp& op,
00152                         KisPaintDeviceSP srcdev,
00153                         Q_UINT8 opacity,
00154                         Q_INT32 sx, Q_INT32 sy,
00155                         Q_INT32 sw, Q_INT32 sh)
00156 {
00157     if (srcdev == 0) {
00158         return;
00159     }
00160 
00161     QRect srcRect = QRect(sx, sy, sw, sh);
00162 
00163     if (srcdev->extentIsValid() && op != COMPOSITE_COPY) {
00164         srcRect &= srcdev->extent();
00165     }
00166 
00167     if (srcRect.isEmpty()) {
00168         return;
00169     }
00170 
00171     dx += srcRect.x() - sx;
00172     dy += srcRect.y() - sy;
00173 
00174     sx = srcRect.x();
00175     sy = srcRect.y();
00176     sw = srcRect.width();
00177     sh = srcRect.height();
00178 
00179     addDirtyRect(QRect(dx, dy, sw, sh));
00180 
00181     KisColorSpace * srcCs = srcdev->colorSpace();
00182 
00183     Q_INT32 dstY = dy;
00184     Q_INT32 srcY = sy;
00185     Q_INT32 rowsRemaining = sh;
00186 
00187     while (rowsRemaining > 0) {
00188 
00189         Q_INT32 dstX = dx;
00190         Q_INT32 srcX = sx;
00191         Q_INT32 columnsRemaining = sw;
00192         Q_INT32 numContiguousDstRows = m_device->numContiguousRows(dstY, dstX, dstX + sw - 1);
00193         Q_INT32 numContiguousSrcRows = srcdev->numContiguousRows(srcY, srcX, srcX + sw - 1);
00194 
00195         Q_INT32 rows = QMIN(numContiguousDstRows, numContiguousSrcRows);
00196         rows = QMIN(rows, rowsRemaining);
00197 
00198         while (columnsRemaining > 0) {
00199 
00200             Q_INT32 numContiguousDstColumns = m_device->numContiguousColumns(dstX, dstY, dstY + rows - 1);
00201             Q_INT32 numContiguousSrcColumns = srcdev->numContiguousColumns(srcX, srcY, srcY + rows - 1);
00202 
00203             Q_INT32 columns = QMIN(numContiguousDstColumns, numContiguousSrcColumns);
00204             columns = QMIN(columns, columnsRemaining);
00205 
00206             const Q_UINT8 *srcData = srcdev->pixel(srcX, srcY);
00207             Q_INT32 srcRowStride = srcdev->rowStride(srcX, srcY);
00208 
00209             Q_UINT8 *dstData = m_device->writablePixel(dstX, dstY);
00210             Q_INT32 dstRowStride = m_device->rowStride(dstX, dstY);
00211 
00212 
00213             m_colorSpace->bitBlt(dstData,
00214                           dstRowStride,
00215                           srcCs,
00216                           srcData,
00217                           srcRowStride,
00218                           0,
00219                           0,
00220                           opacity,
00221                           rows,
00222                           columns,
00223                           op);
00224 
00225             srcX += columns;
00226             dstX += columns;
00227             columnsRemaining -= columns;
00228         }
00229 
00230         srcY += rows;
00231         dstY += rows;
00232         rowsRemaining -= rows;
00233     }
00234 }
00235 
00236 void KisPainter::bltSelection(Q_INT32 dx, Q_INT32 dy,
00237                   const KisCompositeOp &op,
00238                   KisPaintDeviceSP srcdev,
00239                   KisSelectionSP seldev,
00240                   Q_UINT8 opacity,
00241                   Q_INT32 sx, Q_INT32 sy,
00242                   Q_INT32 sw, Q_INT32 sh)
00243 {
00244     if (srcdev == 0) return;
00245 
00246     if (seldev == 0) return;
00247 
00248     if (m_device == 0) return;
00249 
00250     if (seldev->isTotallyUnselected(QRect(dx, dy, sw, sh))) {
00251 /*
00252         kdDebug() << "Blitting outside selection rect\n";
00253 
00254         kdDebug() << "srcdev: " << srcdev << " (" << srcdev->name() << ")"
00255                 << ", seldev: " << seldev << " (" << seldev->name() << ")"
00256                 << ". dx, dy " << dx << "," << dy
00257                 << ". sx, sy : sw, sy " << sx << "," << sy << " : " << sw << "," << sh << endl;
00258 */
00259         return;
00260     }
00261 
00262     QRect srcRect = QRect(sx, sy, sw, sh);
00263 
00264     if (srcdev->extentIsValid() && op != COMPOSITE_COPY) {
00265         srcRect &= srcdev->extent();
00266     }
00267 
00268     if (srcRect.isEmpty()) {
00269         return;
00270     }
00271 
00272     dx += srcRect.x() - sx;
00273     dy += srcRect.y() - sy;
00274 
00275     sx = srcRect.x();
00276     sy = srcRect.y();
00277     sw = srcRect.width();
00278     sh = srcRect.height();
00279 
00280     addDirtyRect(QRect(dx, dy, sw, sh));
00281 
00282     KisColorSpace * srcCs = srcdev->colorSpace();
00283 
00284     Q_INT32 dstY = dy;
00285     Q_INT32 srcY = sy;
00286     Q_INT32 rowsRemaining = sh;
00287 
00288     while (rowsRemaining > 0) {
00289 
00290         Q_INT32 dstX = dx;
00291         Q_INT32 srcX = sx;
00292         Q_INT32 columnsRemaining = sw;
00293         Q_INT32 numContiguousDstRows = m_device->numContiguousRows(dstY, dstX, dstX + sw - 1);
00294         Q_INT32 numContiguousSrcRows = srcdev->numContiguousRows(srcY, srcX, srcX + sw - 1);
00295         Q_INT32 numContiguousSelRows = seldev->numContiguousRows(dstY, dstX, dstX + sw - 1);
00296 
00297         Q_INT32 rows = QMIN(numContiguousDstRows, numContiguousSrcRows);
00298         rows = QMIN(numContiguousSelRows, rows);
00299         rows = QMIN(rows, rowsRemaining);
00300 
00301         while (columnsRemaining > 0) {
00302 
00303             Q_INT32 numContiguousDstColumns = m_device->numContiguousColumns(dstX, dstY, dstY + rows - 1);
00304             Q_INT32 numContiguousSrcColumns = srcdev->numContiguousColumns(srcX, srcY, srcY + rows - 1);
00305             Q_INT32 numContiguousSelColumns = seldev->numContiguousColumns(dstX, dstY, dstY + rows - 1);
00306 
00307             Q_INT32 columns = QMIN(numContiguousDstColumns, numContiguousSrcColumns);
00308             columns = QMIN(numContiguousSelColumns, columns);
00309             columns = QMIN(columns, columnsRemaining);
00310 
00311             Q_UINT8 *dstData = m_device->writablePixel(dstX, dstY);
00312             Q_INT32 dstRowStride = m_device->rowStride(dstX, dstY);
00313 
00314             const Q_UINT8 *srcData = srcdev->pixel(srcX, srcY);
00315             Q_INT32 srcRowStride = srcdev->rowStride(srcX, srcY);
00316 
00317             const Q_UINT8 *selData = seldev->pixel(dstX, dstY);
00318             Q_INT32 selRowStride = seldev->rowStride(dstX, dstY);
00319 
00320             m_colorSpace->bitBlt(dstData,
00321                                    dstRowStride,
00322                                    srcCs,
00323                                    srcData,
00324                                    srcRowStride,
00325                                    selData,
00326                                    selRowStride,
00327                                    opacity,
00328                                    rows,
00329                                    columns,
00330                                    op);
00331 
00332             srcX += columns;
00333             dstX += columns;
00334             columnsRemaining -= columns;
00335         }
00336 
00337         srcY += rows;
00338         dstY += rows;
00339         rowsRemaining -= rows;
00340     }
00341 }
00342 
00343 
00344 void KisPainter::bltSelection(Q_INT32 dx, Q_INT32 dy,
00345                   const KisCompositeOp& op,
00346                   KisPaintDeviceSP srcdev,
00347                   Q_UINT8 opacity,
00348                   Q_INT32 sx, Q_INT32 sy,
00349                   Q_INT32 sw, Q_INT32 sh)
00350 {
00351     if (m_device == 0) return;
00352     if (!m_device->hasSelection()) {
00353         bitBlt(dx, dy, op, srcdev, opacity, sx, sy, sw, sh);
00354     }
00355     else
00356         bltSelection(dx,dy,op,srcdev, m_device->selection(),opacity,sx,sy,sw,sh);
00357 }
00358 
00359 double KisPainter::paintLine(const KisPoint & pos1,
00360                  const double pressure1,
00361                  const double xTilt1,
00362                  const double yTilt1,
00363                  const KisPoint & pos2,
00364                  const double pressure2,
00365                  const double xTilt2,
00366                  const double yTilt2,
00367                  const double inSavedDist)
00368 {
00369     if (!m_device) return 0;
00370     if (!m_paintOp) return 0;
00371     if (!m_brush) return 0;
00372 
00373     double savedDist = inSavedDist;
00374     KisVector2D end(pos2);
00375     KisVector2D start(pos1);
00376 
00377     KisVector2D dragVec = end - start;
00378     KisVector2D movement = dragVec;
00379 
00380     if (savedDist < 0) {
00381         m_paintOp->paintAt(pos1, KisPaintInformation(pressure1, xTilt1, yTilt1, movement));
00382         savedDist = 0;
00383     }
00384 
00385     // XXX: The spacing should vary as the pressure changes along the line.
00386     // This is a quick simplification.
00387     double xSpacing = m_brush->xSpacing((pressure1 + pressure2) / 2);
00388     double ySpacing = m_brush->ySpacing((pressure1 + pressure2) / 2);
00389 
00390     if (xSpacing < 0.5) {
00391         xSpacing = 0.5;
00392     }
00393     if (ySpacing < 0.5) {
00394         ySpacing = 0.5;
00395     }
00396 
00397     double xScale = 1;
00398     double yScale = 1;
00399     double spacing;
00400     // Scale x or y so that we effectively have a square brush
00401     // and calculate distance in that coordinate space. We reverse this scaling
00402     // before drawing the brush. This produces the correct spacing in both
00403     // x and y directions, even if the brush's aspect ratio is not 1:1.
00404     if (xSpacing > ySpacing) {
00405         yScale = xSpacing / ySpacing;
00406         spacing = xSpacing;
00407     }
00408     else {
00409         xScale = ySpacing / xSpacing;
00410         spacing = ySpacing;
00411     }
00412 
00413     dragVec.setX(dragVec.x() * xScale);
00414     dragVec.setY(dragVec.y() * yScale);
00415 
00416     double newDist = dragVec.length();
00417     double dist = savedDist + newDist;
00418     double l_savedDist = savedDist;
00419 
00420     if (dist < spacing) {
00421         return dist;
00422     }
00423 
00424     dragVec.normalize();
00425     KisVector2D step(0, 0);
00426 
00427     while (dist >= spacing) {
00428         if (l_savedDist > 0) {
00429             step += dragVec * (spacing - l_savedDist);
00430             l_savedDist -= spacing;
00431         }
00432         else {
00433             step += dragVec * spacing;
00434         }
00435 
00436         KisPoint p(start.x() + (step.x() / xScale), start.y() + (step.y() / yScale));
00437 
00438         double distanceMoved = step.length();
00439         double t = 0;
00440 
00441         if (newDist > DBL_EPSILON) {
00442             t = distanceMoved / newDist;
00443         }
00444 
00445         double pressure = (1 - t) * pressure1 + t * pressure2;
00446         double xTilt = (1 - t) * xTilt1 + t * xTilt2;
00447         double yTilt = (1 - t) * yTilt1 + t * yTilt2;
00448 
00449         m_paintOp->paintAt(p, KisPaintInformation(pressure, xTilt, yTilt, movement));
00450         dist -= spacing;
00451     }
00452 
00453     if (dist > 0)
00454         return dist;
00455     else
00456         return 0;
00457 }
00458 
00459 void KisPainter::paintPolyline (const vKisPoint &points,
00460                                 int index, int numPoints)
00461 {
00462     if (index >= (int) points.count ())
00463         return;
00464 
00465     if (numPoints < 0)
00466         numPoints = points.count ();
00467 
00468     if (index + numPoints > (int) points.count ())
00469         numPoints = points.count () - index;
00470 
00471 
00472     for (int i = index; i < index + numPoints - 1; i++)
00473     {
00474         paintLine (points [index], 0/*pressure*/, 0, 0, points [index + 1],
00475                0/*pressure*/, 0, 0);
00476     }
00477 }
00478 
00479 void KisPainter::getBezierCurvePoints(const KisPoint &pos1,
00480                       const KisPoint &control1,
00481                       const KisPoint &control2,
00482                       const KisPoint &pos2,
00483                       vKisPoint& points)
00484 {
00485     double d1 = pointToLineDistance(control1, pos1, pos2);
00486     double d2 = pointToLineDistance(control2, pos1, pos2);
00487 
00488     if (d1 < BEZIER_FLATNESS_THRESHOLD && d2 < BEZIER_FLATNESS_THRESHOLD) {
00489         points.push_back(pos1);
00490     } else {
00491         // Midpoint subdivision. See Foley & Van Dam Computer Graphics P.508
00492         KisVector2D p1 = pos1;
00493         KisVector2D p2 = control1;
00494         KisVector2D p3 = control2;
00495         KisVector2D p4 = pos2;
00496 
00497         KisVector2D l2 = (p1 + p2) / 2;
00498         KisVector2D h = (p2 + p3) / 2;
00499         KisVector2D l3 = (l2 + h) / 2;
00500         KisVector2D r3 = (p3 + p4) / 2;
00501         KisVector2D r2 = (h + r3) / 2;
00502         KisVector2D l4 = (l3 + r2) / 2;
00503         KisVector2D r1 = l4;
00504         KisVector2D l1 = p1;
00505         KisVector2D r4 = p4;
00506 
00507         getBezierCurvePoints(l1.toKisPoint(), l2.toKisPoint(), l3.toKisPoint(), l4.toKisPoint(), points);
00508         getBezierCurvePoints(r1.toKisPoint(), r2.toKisPoint(), r3.toKisPoint(), r4.toKisPoint(), points);
00509     }
00510 }
00511 
00512 double KisPainter::paintBezierCurve(const KisPoint &pos1,
00513                     const double pressure1,
00514                     const double xTilt1,
00515                     const double yTilt1,
00516                     const KisPoint &control1,
00517                     const KisPoint &control2,
00518                     const KisPoint &pos2,
00519                     const double pressure2,
00520                     const double xTilt2,
00521                     const double yTilt2,
00522                     const double savedDist)
00523 {
00524     double newDistance;
00525     double d1 = pointToLineDistance(control1, pos1, pos2);
00526     double d2 = pointToLineDistance(control2, pos1, pos2);
00527 
00528     if (d1 < BEZIER_FLATNESS_THRESHOLD && d2 < BEZIER_FLATNESS_THRESHOLD) {
00529         newDistance = paintLine(pos1, pressure1, xTilt1, yTilt1, pos2, pressure2, xTilt2, yTilt2, savedDist);
00530     } else {
00531         // Midpoint subdivision. See Foley & Van Dam Computer Graphics P.508
00532         KisVector2D p1 = pos1;
00533         KisVector2D p2 = control1;
00534         KisVector2D p3 = control2;
00535         KisVector2D p4 = pos2;
00536 
00537         KisVector2D l2 = (p1 + p2) / 2;
00538         KisVector2D h = (p2 + p3) / 2;
00539         KisVector2D l3 = (l2 + h) / 2;
00540         KisVector2D r3 = (p3 + p4) / 2;
00541         KisVector2D r2 = (h + r3) / 2;
00542         KisVector2D l4 = (l3 + r2) / 2;
00543         KisVector2D r1 = l4;
00544         KisVector2D l1 = p1;
00545         KisVector2D r4 = p4;
00546 
00547         double midPressure = (pressure1 + pressure2) / 2;
00548         double midXTilt = (xTilt1 + xTilt2) / 2;
00549         double midYTilt = (yTilt1 + yTilt2) / 2;
00550 
00551         newDistance = paintBezierCurve(l1.toKisPoint(), pressure1, xTilt1, yTilt1,
00552                            l2.toKisPoint(), l3.toKisPoint(),
00553                            l4.toKisPoint(), midPressure, midXTilt, midYTilt,
00554                            savedDist);
00555         newDistance = paintBezierCurve(r1.toKisPoint(), midPressure, midXTilt, midYTilt,
00556                            r2.toKisPoint(),
00557                            r3.toKisPoint(),
00558                            r4.toKisPoint(), pressure2, xTilt2, yTilt2, newDistance);
00559     }
00560 
00561     return newDistance;
00562 }
00563 
00564 void KisPainter::paintRect (const KisPoint &startPoint,
00565                             const KisPoint &endPoint,
00566                             const double /*pressure*/,
00567                 const double /*xTilt*/,
00568                 const double /*yTilt*/)
00569 {
00570     KoRect normalizedRect = KisRect (startPoint, endPoint).normalize ();
00571 
00572     vKisPoint points;
00573 
00574     points.push_back(normalizedRect.topLeft());
00575     points.push_back(normalizedRect.bottomLeft());
00576     points.push_back(normalizedRect.bottomRight());
00577     points.push_back(normalizedRect.topRight());
00578 
00579     paintPolygon(points);
00580 }
00581 
00582 void KisPainter::paintEllipse (const KisPoint &startPoint,
00583                                const KisPoint &endPoint,
00584                                const double /*pressure*/,
00585                    const double /*xTilt*/,
00586                    const double /*yTilt*/)
00587 {
00588     KisRect r = KisRect(startPoint, endPoint).normalize();
00589 
00590     // See http://www.whizkidtech.redprince.net/bezier/circle/ for explanation.
00591     // kappa = (4/3*(sqrt(2)-1))
00592     const double kappa = 0.5522847498;
00593     const double lx = (r.width() / 2) * kappa;
00594     const double ly = (r.height() / 2) * kappa;
00595 
00596     KisPoint center = r.center();
00597 
00598     KisPoint p0(r.left(), center.y());
00599     KisPoint p1(r.left(), center.y() - ly);
00600     KisPoint p2(center.x() - lx, r.top());
00601     KisPoint p3(center.x(), r.top());
00602 
00603     vKisPoint points;
00604 
00605     getBezierCurvePoints(p0, p1, p2, p3, points);
00606 
00607     KisPoint p4(center.x() + lx, r.top());
00608     KisPoint p5(r.right(), center.y() - ly);
00609     KisPoint p6(r.right(), center.y());
00610 
00611     getBezierCurvePoints(p3, p4, p5, p6, points);
00612 
00613     KisPoint p7(r.right(), center.y() + ly);
00614     KisPoint p8(center.x() + lx, r.bottom());
00615     KisPoint p9(center.x(), r.bottom());
00616 
00617     getBezierCurvePoints(p6, p7, p8, p9, points);
00618 
00619     KisPoint p10(center.x() - lx, r.bottom());
00620     KisPoint p11(r.left(), center.y() + ly);
00621 
00622     getBezierCurvePoints(p9, p10, p11, p0, points);
00623 
00624     paintPolygon(points);
00625 }
00626 
00627 void KisPainter::paintAt(const KisPoint & pos,
00628                          const double pressure,
00629                          const double xTilt,
00630                          const double yTilt)
00631 {
00632     if (!m_paintOp) return;
00633     m_paintOp->paintAt(pos, KisPaintInformation(pressure, xTilt, yTilt, KisVector2D()));
00634 }
00635 
00636 double KisPainter::pointToLineDistance(const KisPoint& p, const KisPoint& l0, const KisPoint& l1)
00637 {
00638     double lineLength = sqrt((l1.x() - l0.x()) * (l1.x() - l0.x()) + (l1.y() - l0.y()) * (l1.y() - l0.y()));
00639     double distance = 0;
00640 
00641     if (lineLength > DBL_EPSILON) {
00642         distance = ((l0.y() - l1.y()) * p.x() + (l1.x() - l0.x()) * p.y() + l0.x() * l1.y() - l1.x() * l0.y()) / lineLength;
00643         distance = fabs(distance);
00644     }
00645 
00646     return distance;
00647 }
00648 
00649 /*
00650  * Concave Polygon Scan Conversion
00651  * by Paul Heckbert
00652  * from "Graphics Gems", Academic Press, 1990
00653  */
00654 
00655 /*
00656  * concave: scan convert nvert-sided concave non-simple polygon with vertices at
00657  * (point[i].x, point[i].y) for i in [0..nvert-1] within the window win by
00658  * calling spanproc for each visible span of pixels.
00659  * Polygon can be clockwise or counterclockwise.
00660  * Algorithm does uniform point sampling at pixel centers.
00661  * Inside-outside test done by Jordan's rule: a point is considered inside if
00662  * an emanating ray intersects the polygon an odd number of times.
00663  * drawproc should fill in pixels from xl to xr inclusive on scanline y,
00664  * e.g:
00665  *    drawproc(y, xl, xr)
00666  *    int y, xl, xr;
00667  *    {
00668  *        int x;
00669  *        for (x=xl; x<=xr; x++)
00670  *        pixel_write(x, y, pixelvalue);
00671  *    }
00672  *
00673  *  Paul Heckbert    30 June 81, 18 Dec 89
00674  */
00675 
00676 typedef struct {    /* a polygon edge */
00677     double x;       /* x coordinate of edge's intersection with current scanline */
00678     double dx;      /* change in x with respect to y */
00679     int i;            /* edge number: edge i goes from pt[i] to pt[i+1] */
00680 } Edge;
00681 
00682 static int n;            /* number of vertices */
00683 static const KisPoint *pt;    /* vertices */
00684 
00685 static int nact;        /* number of active edges */
00686 static Edge *active;        /* active edge list:edges crossing scanline y */
00687 
00688 /* comparison routines for qsort */
00689 static int compare_ind(const void *pu, const void *pv)
00690 {
00691     const int *u = static_cast<const int *>(pu);
00692     const int *v = static_cast<const int *>(pv);
00693 
00694     return pt[*u].y() <= pt[*v].y() ? -1 : 1;
00695 }
00696 
00697 static int compare_active(const void *pu, const void *pv)
00698 {
00699     const Edge *u = static_cast<const Edge *>(pu);
00700     const Edge *v = static_cast<const Edge *>(pv);
00701 
00702     return u->x <= v->x ? -1 : 1;
00703 }
00704 
00705 static void cdelete(int i)        /* remove edge i from active list */
00706 {
00707     int j;
00708 
00709     for (j=0; j<nact && active[j].i!=i; j++);
00710     if (j>=nact) return;        /* edge not in active list; happens at win->y0*/
00711     nact--;
00712     bcopy(&active[j+1], &active[j], (nact-j)*sizeof active[0]);
00713 }
00714 
00715 static void cinsert(int i, int y)        /* append edge i to end of active list */
00716 {
00717     int j;
00718     double dx;
00719     const KisPoint *p, *q;
00720 
00721     j = i<n-1 ? i+1 : 0;
00722     if (pt[i].y() < pt[j].y()) {
00723         p = &pt[i]; q = &pt[j];
00724     } else {
00725         p = &pt[j]; q = &pt[i];
00726     }
00727     /* initialize x position at intersection of edge with scanline y */
00728     active[nact].dx = dx = (q->x()-p->x())/(q->y()-p->y());
00729     active[nact].x = dx*(y+.5-p->y())+p->x();
00730     active[nact].i = i;
00731     nact++;
00732 }
00733 
00734 void KisPainter::fillPolygon(const vKisPoint& points, FillStyle fillStyle)
00735 {
00736     int nvert = points.count();
00737     int k, y0, y1, y, i, j, xl, xr;
00738     int *ind;        /* list of vertex indices, sorted by pt[ind[j]].y */
00739 
00740     n = nvert;
00741     pt = &(points[0]);
00742     if (n<3) return;
00743     if (fillStyle == FillStyleNone) {
00744         return;
00745     }
00746 
00747     ind = new int[n];
00748     Q_CHECK_PTR(ind);
00749     active = new Edge[n];
00750     Q_CHECK_PTR(active);
00751 
00752     /* create y-sorted array of indices ind[k] into vertex list */
00753     for (k=0; k<n; k++)
00754         ind[k] = k;
00755     qsort(ind, n, sizeof ind[0], compare_ind);  /* sort ind by pt[ind[k]].y */
00756 
00757     nact = 0;                /* start with empty active list */
00758     k = 0;                    /* ind[k] is next vertex to process */
00759     y0 = static_cast<int>(ceil(pt[ind[0]].y()-.5));            /* ymin of polygon */
00760     y1 = static_cast<int>(floor(pt[ind[n-1]].y()-.5));        /* ymax of polygon */
00761 
00762     int x0 = INT_MAX;
00763     int x1 = INT_MIN;
00764 
00765     for (int i = 0; i < nvert; i++) {
00766         int pointHighX = static_cast<int>(ceil(points[i].x() - 0.5));
00767         int pointLowX = static_cast<int>(floor(points[i].x() - 0.5));
00768 
00769         if (pointLowX < x0) {
00770             x0 = pointLowX;
00771         }
00772         if (pointHighX > x1) {
00773             x1 = pointHighX;
00774         }
00775     }
00776 
00777     // Fill the polygon bounding rectangle with the required contents then we'll
00778     // create a mask for the actual polygon coverage.
00779 
00780     KisPaintDeviceSP polygon = new KisPaintDevice(m_device->colorSpace(), "polygon");
00781     Q_CHECK_PTR(polygon);
00782 
00783     KisFillPainter fillPainter(polygon);
00784     QRect boundingRectangle(x0, y0, x1 - x0 + 1, y1 - y0 + 1);
00785 
00786     // Clip to the image bounds.
00787     if (m_device->image()) {
00788         boundingRectangle &= m_device->image()->bounds();
00789     }
00790 
00791     switch (fillStyle) {
00792     default:
00793         // Fall through
00794     case FillStyleGradient:
00795         // Currently unsupported, fall through
00796     case FillStyleStrokes:
00797         // Currently unsupported, fall through
00798         kdWarning(DBG_AREA_CORE) << "Unknown or unsupported fill style in fillPolygon\n";
00799     case FillStyleForegroundColor:
00800         fillPainter.fillRect(boundingRectangle, paintColor(), OPACITY_OPAQUE);
00801         break;
00802     case FillStyleBackgroundColor:
00803         fillPainter.fillRect(boundingRectangle, backgroundColor(), OPACITY_OPAQUE);
00804         break;
00805     case FillStylePattern:
00806         Q_ASSERT(m_pattern != 0);
00807         fillPainter.fillRect(boundingRectangle, m_pattern);
00808         break;
00809     }
00810 
00811     KisSelectionSP polygonMask = new KisSelection(polygon);
00812 
00813     for (y=y0; y<=y1; y++) {        /* step through scanlines */
00814         /* scanline y is at y+.5 in continuous coordinates */
00815 
00816         /* check vertices between previous scanline and current one, if any */
00817         for (; k<n && pt[ind[k]].y()<=y+.5; k++) {
00818             /* to simplify, if pt.y=y+.5, pretend it's above */
00819             /* invariant: y-.5 < pt[i].y <= y+.5 */
00820             i = ind[k];
00821             /*
00822              * insert or delete edges before and after vertex i (i-1 to i,
00823              * and i to i+1) from active list if they cross scanline y
00824              */
00825             j = i>0 ? i-1 : n-1;        /* vertex previous to i */
00826             if (pt[j].y() <= y-.5)        /* old edge, remove from active list */
00827                 cdelete(j);
00828             else if (pt[j].y() > y+.5)    /* new edge, add to active list */
00829                 cinsert(j, y);
00830             j = i<n-1 ? i+1 : 0;        /* vertex next after i */
00831             if (pt[j].y() <= y-.5)        /* old edge, remove from active list */
00832                 cdelete(i);
00833             else if (pt[j].y() > y+.5)    /* new edge, add to active list */
00834                 cinsert(i, y);
00835         }
00836 
00837         /* sort active edge list by active[j].x */
00838         qsort(active, nact, sizeof active[0], compare_active);
00839 
00840         /* draw horizontal segments for scanline y */
00841         for (j=0; j<nact; j+=2) {    /* draw horizontal segments */
00842             /* span 'tween j & j+1 is inside, span tween j+1 & j+2 is outside */
00843             xl = static_cast<int>(ceil(active[j].x-.5));        /* left end of span */
00844             xr = static_cast<int>(floor(active[j+1].x-.5));        /* right end of span */
00845 
00846             if (xl<=xr) {
00847                 KisHLineIterator it = polygonMask->createHLineIterator(xl, y, xr - xl + 1, true);
00848 
00849                 while (!it.isDone()) {
00850                     // We're using a selection here, that means alpha colorspace, that means one byte.
00851                     it.rawData()[0] = MAX_SELECTED;
00852                     ++it;
00853                 }
00854             }
00855 
00856             active[j].x += active[j].dx;        /* increment edge coords */
00857             active[j+1].x += active[j+1].dx;
00858         }
00859     }
00860     delete [] ind;
00861     delete [] active;
00862 
00863     polygon->applySelectionMask(polygonMask);
00864 
00865     QRect r = polygon->extent();
00866 
00867     // The strokes for the outline may have already added updated the dirtyrect, but it can't hurt,
00868     // and if we're painting without outlines, then there will be no dirty rect. Let's do it ourselves...
00869     // addDirtyRect( r ); // XXX the bltSelection will add to the dirtyrect
00870 
00871     bltSelection(r.x(), r.y(), compositeOp(), polygon, opacity(), r.x(), r.y(), r.width(), r.height());
00872 }
00873 
00874 void KisPainter::paintPolygon(const vKisPoint& points)
00875 {
00876     if (m_fillStyle != FillStyleNone) {
00877         fillPolygon(points, m_fillStyle);
00878     }
00879 
00880     if (m_strokeStyle != StrokeStyleNone) {
00881         if (points.count() > 1) {
00882             double distance = -1;
00883 
00884             for (uint i = 0; i < points.count() - 1; i++) {
00885                 distance = paintLine(points[i], PRESSURE_DEFAULT, 0, 0, points[i + 1], PRESSURE_DEFAULT, 0, 0, distance);
00886             }
00887             paintLine(points[points.count() - 1], PRESSURE_DEFAULT, 0, 0, points[0], PRESSURE_DEFAULT, 0, 0, distance);
00888         }
00889     }
00890 }
00891 
KDE Home | KDE Accessibility Home | Description of Access Keys