/* * PathOutline.cpp * nlivarot * * Created by fred on Fri Nov 28 2003. * */ #include "livarot/Path.h" #include "livarot/path-description.h" #include /* * the "outliner" * takes a sequence of path commands and produces a set of commands that approximates the offset * result is stored in dest (that paremeter is handed to all the subfunctions) * not that the result is in general not mathematically correct; you can end up with unwanted holes in your * beautiful offset. a better way is to do path->polyline->polygon->offset of polygon->polyline(=contours of the polygon)->path * but computing offsets of the path is faster... */ // outline of a path. // computed by making 2 offsets, one of the "left" side of the path, one of the right side, and then glueing the two // the left side has to be reversed to make a contour void Path::Outline(Path *dest, double width, JoinType join, ButtType butt, double miter) { if ( descr_flags & descr_adding_bezier ) { CancelBezier(); } if ( descr_flags & descr_doing_subpath ) { CloseSubpath(); } if ( descr_cmd.size() <= 1 ) { return; } if ( dest == NULL ) { return; } dest->Reset(); dest->SetBackData(false); outline_callbacks calls; NR::Point endButt; NR::Point endPos; calls.cubicto = StdCubicTo; calls.bezierto = StdBezierTo; calls.arcto = StdArcTo; Path *rev = new Path; // we repeat the offset contour creation for each subpath int curP = 0; do { int lastM = curP; do { curP++; if (curP >= int(descr_cmd.size())) { break; } int typ = descr_cmd[curP]->getType(); if (typ == descr_moveto) { break; } } while (curP < int(descr_cmd.size())); if (curP >= int(descr_cmd.size())) { curP = descr_cmd.size(); } if (curP > lastM + 1) { // we have isolated a subpath, now we make a reversed version of it // we do so by taking the subpath in the reverse and constructing a path as appropriate // the construct is stored in "rev" int curD = curP - 1; NR::Point curX; NR::Point nextX; int firstTyp = descr_cmd[curD]->getType(); bool const needClose = (firstTyp == descr_close); while (curD > lastM && descr_cmd[curD]->getType() == descr_close) { curD--; } int realP = curD + 1; if (curD > lastM) { curX = PrevPoint(curD); rev->Reset (); rev->MoveTo(curX); while (curD > lastM) { int const typ = descr_cmd[curD]->getType(); if (typ == descr_moveto) { // rev->Close(); curD--; } else if (typ == descr_forced) { // rev->Close(); curD--; } else if (typ == descr_lineto) { nextX = PrevPoint (curD - 1); rev->LineTo (nextX); curX = nextX; curD--; } else if (typ == descr_cubicto) { PathDescrCubicTo* nData = dynamic_cast(descr_cmd[curD]); nextX = PrevPoint (curD - 1); NR::Point isD=-nData->start; NR::Point ieD=-nData->end; rev->CubicTo (nextX, ieD,isD); curX = nextX; curD--; } else if (typ == descr_arcto) { PathDescrArcTo* nData = dynamic_cast(descr_cmd[curD]); nextX = PrevPoint (curD - 1); rev->ArcTo (nextX, nData->rx,nData->ry,nData->angle,nData->large,nData->clockwise); curX = nextX; curD--; } else if (typ == descr_bezierto) { nextX = PrevPoint (curD - 1); rev->LineTo (nextX); curX = nextX; curD--; } else if (typ == descr_interm_bezier) { int nD = curD - 1; while (nD > lastM && descr_cmd[nD]->getType() != descr_bezierto) nD--; if ((descr_cmd[nD]->getType()) != descr_bezierto) { // pas trouve le debut!? // Not find the start?! nextX = PrevPoint (nD); rev->LineTo (nextX); curX = nextX; } else { nextX = PrevPoint (nD - 1); rev->BezierTo (nextX); for (int i = curD; i > nD; i--) { PathDescrIntermBezierTo* nData = dynamic_cast(descr_cmd[i]); rev->IntermBezierTo (nData->p); } rev->EndBezierTo (); curX = nextX; } curD = nD - 1; } else { curD--; } } // offset the paths and glue everything // actual offseting is done in SubContractOutline() if (needClose) { rev->Close (); rev->SubContractOutline (0, rev->descr_cmd.size(), dest, calls, 0.0025 * width * width, width, join, butt, miter, true, false, endPos, endButt); SubContractOutline (lastM, realP + 1 - lastM, dest, calls, 0.0025 * width * width, width, join, butt, miter, true, false, endPos, endButt); } else { rev->SubContractOutline (0, rev->descr_cmd.size(), dest, calls, 0.0025 * width * width, width, join, butt, miter, false, false, endPos, endButt); NR::Point endNor=endButt.ccw(); if (butt == butt_round) { dest->ArcTo (endPos+width*endNor, 1.0001 * width, 1.0001 * width, 0.0, true, true); } else if (butt == butt_square) { dest->LineTo (endPos-width*endNor+width*endButt); dest->LineTo (endPos+width*endNor+width*endButt); dest->LineTo (endPos+width*endNor); } else if (butt == butt_pointy) { dest->LineTo (endPos+width*endButt); dest->LineTo (endPos+width*endNor); } else { dest->LineTo (endPos+width*endNor); } SubContractOutline (lastM, realP - lastM, dest, calls, 0.0025 * width * width, width, join, butt, miter, false, true, endPos, endButt); endNor=endButt.ccw(); if (butt == butt_round) { dest->ArcTo (endPos+width*endNor, 1.0001 * width, 1.0001 * width, 0.0, true, true); } else if (butt == butt_square) { dest->LineTo (endPos-width*endNor+width*endButt); dest->LineTo (endPos+width*endNor+width*endButt); dest->LineTo (endPos+width*endNor); } else if (butt == butt_pointy) { dest->LineTo (endPos+width*endButt); dest->LineTo (endPos+width*endNor); } else { dest->LineTo (endPos+width*endNor); } dest->Close (); } } // if (curD > lastM) } // if (curP > lastM + 1) } while (curP < int(descr_cmd.size())); delete rev; } // versions for outlining closed path: they only make one side of the offset contour void Path::OutsideOutline (Path * dest, double width, JoinType join, ButtType butt, double miter) { if (descr_flags & descr_adding_bezier) { CancelBezier(); } if (descr_flags & descr_doing_subpath) { CloseSubpath(); } if (int(descr_cmd.size()) <= 1) return; if (dest == NULL) return; dest->Reset (); dest->SetBackData (false); outline_callbacks calls; NR::Point endButt, endPos; calls.cubicto = StdCubicTo; calls.bezierto = StdBezierTo; calls.arcto = StdArcTo; SubContractOutline (0, descr_cmd.size(), dest, calls, 0.0025 * width * width, width, join, butt, miter, true, false, endPos, endButt); } void Path::InsideOutline (Path * dest, double width, JoinType join, ButtType butt, double miter) { if ( descr_flags & descr_adding_bezier ) { CancelBezier(); } if ( descr_flags & descr_doing_subpath ) { CloseSubpath(); } if (int(descr_cmd.size()) <= 1) return; if (dest == NULL) return; dest->Reset (); dest->SetBackData (false); outline_callbacks calls; NR::Point endButt, endPos; calls.cubicto = StdCubicTo; calls.bezierto = StdBezierTo; calls.arcto = StdArcTo; Path *rev = new Path; int curP = 0; do { int lastM = curP; do { curP++; if (curP >= int(descr_cmd.size())) break; int typ = descr_cmd[curP]->getType(); if (typ == descr_moveto) break; } while (curP < int(descr_cmd.size())); if (curP >= int(descr_cmd.size())) curP = descr_cmd.size(); if (curP > lastM + 1) { // Otherwise there's only one point. (tr: or "only a point") // [sinon il n'y a qu'un point] int curD = curP - 1; NR::Point curX; NR::Point nextX; while (curD > lastM && (descr_cmd[curD]->getType()) == descr_close) curD--; if (curD > lastM) { curX = PrevPoint (curD); rev->Reset (); rev->MoveTo (curX); while (curD > lastM) { int typ = descr_cmd[curD]->getType(); if (typ == descr_moveto) { rev->Close (); curD--; } else if (typ == descr_forced) { curD--; } else if (typ == descr_lineto) { nextX = PrevPoint (curD - 1); rev->LineTo (nextX); curX = nextX; curD--; } else if (typ == descr_cubicto) { PathDescrCubicTo *nData = dynamic_cast(descr_cmd[curD]); nextX = PrevPoint (curD - 1); NR::Point isD=-nData->start; NR::Point ieD=-nData->end; rev->CubicTo (nextX, ieD,isD); curX = nextX; curD--; } else if (typ == descr_arcto) { PathDescrArcTo* nData = dynamic_cast(descr_cmd[curD]); nextX = PrevPoint (curD - 1); rev->ArcTo (nextX, nData->rx,nData->ry,nData->angle,nData->large,nData->clockwise); curX = nextX; curD--; } else if (typ == descr_bezierto) { nextX = PrevPoint (curD - 1); rev->LineTo (nextX); curX = nextX; curD--; } else if (typ == descr_interm_bezier) { int nD = curD - 1; while (nD > lastM && (descr_cmd[nD]->getType()) != descr_bezierto) nD--; if (descr_cmd[nD]->getType() != descr_bezierto) { // pas trouve le debut!? nextX = PrevPoint (nD); rev->LineTo (nextX); curX = nextX; } else { nextX = PrevPoint (nD - 1); rev->BezierTo (nextX); for (int i = curD; i > nD; i--) { PathDescrIntermBezierTo* nData = dynamic_cast(descr_cmd[i]); rev->IntermBezierTo (nData->p); } rev->EndBezierTo (); curX = nextX; } curD = nD - 1; } else { curD--; } } rev->Close (); rev->SubContractOutline (0, rev->descr_cmd.size(), dest, calls, 0.0025 * width * width, width, join, butt, miter, true, false, endPos, endButt); } } } while (curP < int(descr_cmd.size())); delete rev; } // the offset // take each command and offset it. // the bezier spline is split in a sequence of bezier curves, and these are transformed in cubic bezier (which is // not hard since they are quadratic bezier) // joins are put where needed void Path::SubContractOutline(int off, int num_pd, Path *dest, outline_callbacks & calls, double tolerance, double width, JoinType join, ButtType butt, double miter, bool closeIfNeeded, bool skipMoveto, NR::Point &lastP, NR::Point &lastT) { outline_callback_data callsData; callsData.orig = this; callsData.dest = dest; int curP = 1; // le moveto NR::Point curX; { int firstTyp = descr_cmd[off]->getType(); if ( firstTyp != descr_moveto ) { curX[0] = curX[1] = 0; curP = 0; } else { PathDescrMoveTo* nData = dynamic_cast(descr_cmd[off]); curX = nData->p; } } NR::Point curT(0, 0); bool doFirst = true; NR::Point firstP(0, 0); NR::Point firstT(0, 0); // et le reste, 1 par 1 while (curP < num_pd) { int curD = off + curP; int nType = descr_cmd[curD]->getType(); NR::Point nextX; NR::Point stPos, enPos, stTgt, enTgt, stNor, enNor; double stRad, enRad, stTle, enTle; if (nType == descr_forced) { curP++; } else if (nType == descr_moveto) { PathDescrMoveTo* nData = dynamic_cast(descr_cmd[curD]); nextX = nData->p; // et on avance if (doFirst) { } else { if (closeIfNeeded) { if ( NR::LInfty (curX- firstP) < 0.0001 ) { OutlineJoin (dest, firstP, curT, firstT, width, join, miter); dest->Close (); } else { PathDescrLineTo temp(firstP); TangentOnSegAt (0.0, curX, temp, stPos, stTgt, stTle); TangentOnSegAt (1.0, curX, temp, enPos, enTgt, enTle); stNor=stTgt.cw(); enNor=enTgt.cw(); // jointure { NR::Point pos; pos = curX; OutlineJoin (dest, pos, curT, stNor, width, join, miter); } dest->LineTo (enPos+width*enNor); // jointure { NR::Point pos; pos = firstP; OutlineJoin (dest, enPos, enNor, firstT, width, join, miter); dest->Close (); } } } } firstP = nextX; curP++; } else if (nType == descr_close) { if (doFirst == false) { if (NR::LInfty (curX - firstP) < 0.0001) { OutlineJoin (dest, firstP, curT, firstT, width, join, miter); dest->Close (); } else { PathDescrLineTo temp(firstP); nextX = firstP; TangentOnSegAt (0.0, curX, temp, stPos, stTgt, stTle); TangentOnSegAt (1.0, curX, temp, enPos, enTgt, enTle); stNor=stTgt.cw(); enNor=enTgt.cw(); // jointure { OutlineJoin (dest, stPos, curT, stNor, width, join, miter); } dest->LineTo (enPos+width*enNor); // jointure { OutlineJoin (dest, enPos, enNor, firstT, width, join, miter); dest->Close (); } } } doFirst = true; curP++; } else if (nType == descr_lineto) { PathDescrLineTo* nData = dynamic_cast(descr_cmd[curD]); nextX = nData->p; // test de nullité du segment if (IsNulCurve (descr_cmd, curD, curX)) { curP++; continue; } // et on avance TangentOnSegAt (0.0, curX, *nData, stPos, stTgt, stTle); TangentOnSegAt (1.0, curX, *nData, enPos, enTgt, enTle); stNor=stTgt.cw(); enNor=enTgt.cw(); lastP = enPos; lastT = enTgt; if (doFirst) { doFirst = false; firstP = stPos; firstT = stNor; if (skipMoveto) { skipMoveto = false; } else dest->MoveTo (curX+width*stNor); } else { // jointure NR::Point pos; pos = curX; OutlineJoin (dest, pos, curT, stNor, width, join, miter); } int n_d = dest->LineTo (nextX+width*enNor); if (n_d >= 0) { dest->descr_cmd[n_d]->associated = curP; dest->descr_cmd[n_d]->tSt = 0.0; dest->descr_cmd[n_d]->tEn = 1.0; } curP++; } else if (nType == descr_cubicto) { PathDescrCubicTo* nData = dynamic_cast(descr_cmd[curD]); nextX = nData->p; // test de nullite du segment if (IsNulCurve (descr_cmd, curD, curX)) { curP++; continue; } // et on avance TangentOnCubAt (0.0, curX, *nData, false, stPos, stTgt, stTle, stRad); TangentOnCubAt (1.0, curX, *nData, true, enPos, enTgt, enTle, enRad); stNor=stTgt.cw(); enNor=enTgt.cw(); lastP = enPos; lastT = enTgt; if (doFirst) { doFirst = false; firstP = stPos; firstT = stNor; if (skipMoveto) { skipMoveto = false; } else dest->MoveTo (curX+width*stNor); } else { // jointure NR::Point pos; pos = curX; OutlineJoin (dest, pos, curT, stNor, width, join, miter); } callsData.piece = curP; callsData.tSt = 0.0; callsData.tEn = 1.0; callsData.x1 = curX[0]; callsData.y1 = curX[1]; callsData.x2 = nextX[0]; callsData.y2 = nextX[1]; callsData.d.c.dx1 = nData->start[0]; callsData.d.c.dy1 = nData->start[1]; callsData.d.c.dx2 = nData->end[0]; callsData.d.c.dy2 = nData->end[1]; (calls.cubicto) (&callsData, tolerance, width); curP++; } else if (nType == descr_arcto) { PathDescrArcTo* nData = dynamic_cast(descr_cmd[curD]); nextX = nData->p; // test de nullité du segment if (IsNulCurve (descr_cmd, curD, curX)) { curP++; continue; } // et on avance TangentOnArcAt (0.0, curX, *nData, stPos, stTgt, stTle, stRad); TangentOnArcAt (1.0, curX, *nData, enPos, enTgt, enTle, enRad); stNor=stTgt.cw(); enNor=enTgt.cw(); lastP = enPos; lastT = enTgt; // tjs definie if (doFirst) { doFirst = false; firstP = stPos; firstT = stNor; if (skipMoveto) { skipMoveto = false; } else dest->MoveTo (curX+width*stNor); } else { // jointure NR::Point pos; pos = curX; OutlineJoin (dest, pos, curT, stNor, width, join, miter); } callsData.piece = curP; callsData.tSt = 0.0; callsData.tEn = 1.0; callsData.x1 = curX[0]; callsData.y1 = curX[1]; callsData.x2 = nextX[0]; callsData.y2 = nextX[1]; callsData.d.a.rx = nData->rx; callsData.d.a.ry = nData->ry; callsData.d.a.angle = nData->angle; callsData.d.a.clock = nData->clockwise; callsData.d.a.large = nData->large; (calls.arcto) (&callsData, tolerance, width); curP++; } else if (nType == descr_bezierto) { PathDescrBezierTo* nBData = dynamic_cast(descr_cmd[curD]); int nbInterm = nBData->nb; nextX = nBData->p; if (IsNulCurve (descr_cmd, curD, curX)) { curP += nbInterm + 1; continue; } curP++; curD = off + curP; int ip = curD; PathDescrIntermBezierTo* nData = dynamic_cast(descr_cmd[ip]); if (nbInterm <= 0) { // et on avance PathDescrLineTo temp(nextX); TangentOnSegAt (0.0, curX, temp, stPos, stTgt, stTle); TangentOnSegAt (1.0, curX, temp, enPos, enTgt, enTle); stNor=stTgt.cw(); enNor=enTgt.cw(); lastP = enPos; lastT = enTgt; if (doFirst) { doFirst = false; firstP = stPos; firstT = stNor; if (skipMoveto) { skipMoveto = false; } else dest->MoveTo (curX+width*stNor); } else { // jointure NR::Point pos; pos = curX; if (stTle > 0) OutlineJoin (dest, pos, curT, stNor, width, join, miter); } int n_d = dest->LineTo (nextX+width*enNor); if (n_d >= 0) { dest->descr_cmd[n_d]->associated = curP - 1; dest->descr_cmd[n_d]->tSt = 0.0; dest->descr_cmd[n_d]->tEn = 1.0; } } else if (nbInterm == 1) { NR::Point midX; midX = nData->p; // et on avance TangentOnBezAt (0.0, curX, *nData, *nBData, false, stPos, stTgt, stTle, stRad); TangentOnBezAt (1.0, curX, *nData, *nBData, true, enPos, enTgt, enTle, enRad); stNor=stTgt.cw(); enNor=enTgt.cw(); lastP = enPos; lastT = enTgt; if (doFirst) { doFirst = false; firstP = stPos; firstT = stNor; if (skipMoveto) { skipMoveto = false; } else dest->MoveTo (curX+width*stNor); } else { // jointure NR::Point pos; pos = curX; OutlineJoin (dest, pos, curT, stNor, width, join, miter); } callsData.piece = curP; callsData.tSt = 0.0; callsData.tEn = 1.0; callsData.x1 = curX[0]; callsData.y1 = curX[1]; callsData.x2 = nextX[0]; callsData.y2 = nextX[1]; callsData.d.b.mx = midX[0]; callsData.d.b.my = midX[1]; (calls.bezierto) (&callsData, tolerance, width); } else if (nbInterm > 1) { NR::Point bx=curX; NR::Point cx=curX; NR::Point dx=curX; dx = nData->p; TangentOnBezAt (0.0, curX, *nData, *nBData, false, stPos, stTgt, stTle, stRad); stNor=stTgt.cw(); ip++; nData = dynamic_cast(descr_cmd[ip]); // et on avance if (stTle > 0) { if (doFirst) { doFirst = false; firstP = stPos; firstT = stNor; if (skipMoveto) { skipMoveto = false; } else dest->MoveTo (curX+width*stNor); } else { // jointure NR::Point pos=curX; OutlineJoin (dest, pos, stTgt, stNor, width, join, miter); // dest->LineTo(curX+width*stNor.x,curY+width*stNor.y); } } cx = 2 * bx - dx; for (int k = 0; k < nbInterm - 1; k++) { bx = cx; cx = dx; dx = nData->p; ip++; nData = dynamic_cast(descr_cmd[ip]); NR::Point stx = (bx + cx) / 2; // double stw=(bw+cw)/2; PathDescrBezierTo tempb((cx + dx) / 2, 1); PathDescrIntermBezierTo tempi(cx); TangentOnBezAt (1.0, stx, tempi, tempb, true, enPos, enTgt, enTle, enRad); enNor=enTgt.cw(); lastP = enPos; lastT = enTgt; callsData.piece = curP + k; callsData.tSt = 0.0; callsData.tEn = 1.0; callsData.x1 = stx[0]; callsData.y1 = stx[1]; callsData.x2 = (cx[0] + dx[0]) / 2; callsData.y2 = (cx[1] + dx[1]) / 2; callsData.d.b.mx = cx[0]; callsData.d.b.my = cx[1]; (calls.bezierto) (&callsData, tolerance, width); } { bx = cx; cx = dx; dx = nextX; dx = 2 * dx - cx; NR::Point stx = (bx + cx) / 2; // double stw=(bw+cw)/2; PathDescrBezierTo tempb((cx + dx) / 2, 1); PathDescrIntermBezierTo tempi(cx); TangentOnBezAt (1.0, stx, tempi, tempb, true, enPos, enTgt, enTle, enRad); enNor=enTgt.cw(); lastP = enPos; lastT = enTgt; callsData.piece = curP + nbInterm - 1; callsData.tSt = 0.0; callsData.tEn = 1.0; callsData.x1 = stx[0]; callsData.y1 = stx[1]; callsData.x2 = (cx[0] + dx[0]) / 2; callsData.y2 = (cx[1] + dx[1]) / 2; callsData.d.b.mx = cx[0]; callsData.d.b.my = cx[1]; (calls.bezierto) (&callsData, tolerance, width); } } // et on avance curP += nbInterm; } curX = nextX; curT = enNor; // sera tjs bien definie } if (closeIfNeeded) { if (doFirst == false) { } } } /* * * utilitaires pour l'outline * */ // like the name says: check whether the path command is actually more than a dumb point. bool Path::IsNulCurve (std::vector const &cmd, int curD, NR::Point const &curX) { switch(cmd[curD]->getType()) { case descr_lineto: { PathDescrLineTo *nData = dynamic_cast(cmd[curD]); if (NR::LInfty(nData->p - curX) < 0.00001) { return true; } return false; } case descr_cubicto: { PathDescrCubicTo *nData = dynamic_cast(cmd[curD]); NR::Point A = nData->start + nData->end + 2*(curX - nData->p); NR::Point B = 3*(nData->p - curX) - 2*nData->start - nData->end; NR::Point C = nData->start; if (NR::LInfty(A) < 0.0001 && NR::LInfty(B) < 0.0001 && NR::LInfty (C) < 0.0001) { return true; } return false; } case descr_arcto: { PathDescrArcTo* nData = dynamic_cast(cmd[curD]); if ( NR::LInfty(nData->p - curX) < 0.00001) { if ((nData->large == false) || (fabs (nData->rx) < 0.00001 || fabs (nData->ry) < 0.00001)) { return true; } } return false; } case descr_bezierto: { PathDescrBezierTo* nBData = dynamic_cast(cmd[curD]); if (nBData->nb <= 0) { if (NR::LInfty(nBData->p - curX) < 0.00001) { return true; } return false; } else if (nBData->nb == 1) { if (NR::LInfty(nBData->p - curX) < 0.00001) { int ip = curD + 1; PathDescrIntermBezierTo* nData = dynamic_cast(cmd[ip]); if (NR::LInfty(nData->p - curX) < 0.00001) { return true; } } return false; } else if (NR::LInfty(nBData->p - curX) < 0.00001) { for (int i = 1; i <= nBData->nb; i++) { int ip = curD + i; PathDescrIntermBezierTo* nData = dynamic_cast(cmd[ip]); if (NR::LInfty(nData->p - curX) > 0.00001) { return false; } } return true; } } default: return true; } } // tangents and cuvarture computing, for the different path command types. // the need for tangent is obvious: it gives the normal, along which we offset points // curvature is used to do strength correction on the length of the tangents to the offset (see // cubic offset) /** * \param at Distance along a tangent (0 <= at <= 1). * \param iS Start point. * \param fin LineTo description containing end point. * \param pos Filled in with the position of `at' on the segment. * \param tgt Filled in with the normalised tangent vector. * \param len Filled in with the length of the segment. */ void Path::TangentOnSegAt(double at, NR::Point const &iS, PathDescrLineTo const &fin, NR::Point &pos, NR::Point &tgt, double &len) { NR::Point const iE = fin.p; NR::Point const seg = iE - iS; double const l = L2(seg); if (l <= 0.000001) { pos = iS; tgt = NR::Point(0, 0); len = 0; } else { tgt = seg / l; pos = (1 - at) * iS + at * iE; // in other words, pos = iS + at * seg len = l; } } // barf void Path::TangentOnArcAt(double at, const NR::Point &iS, PathDescrArcTo const &fin, NR::Point &pos, NR::Point &tgt, double &len, double &rad) { NR::Point const iE = fin.p; double const rx = fin.rx; double const ry = fin.ry; double const angle = fin.angle; bool const large = fin.large; bool const wise = fin.clockwise; pos = iS; tgt[0] = tgt[1] = 0; if (rx <= 0.0001 || ry <= 0.0001) return; double const sex = iE[0] - iS[0], sey = iE[1] - iS[1]; double const ca = cos (angle), sa = sin (angle); double csex = ca * sex + sa * sey; double csey = -sa * sex + ca * sey; csex /= rx; csey /= ry; double l = csex * csex + csey * csey; if (l >= 4) return; double const d = sqrt(std::max(1 - l / 4, 0.0)); double csdx = csey; double csdy = -csex; l = sqrt(l); csdx /= l; csdy /= l; csdx *= d; csdy *= d; double sang; double eang; double rax = -csdx - csex / 2; double ray = -csdy - csey / 2; if (rax < -1) { sang = M_PI; } else if (rax > 1) { sang = 0; } else { sang = acos (rax); if (ray < 0) sang = 2 * M_PI - sang; } rax = -csdx + csex / 2; ray = -csdy + csey / 2; if (rax < -1) { eang = M_PI; } else if (rax > 1) { eang = 0; } else { eang = acos (rax); if (ray < 0) eang = 2 * M_PI - eang; } csdx *= rx; csdy *= ry; double drx = ca * csdx - sa * csdy; double dry = sa * csdx + ca * csdy; if (wise) { if (large == true) { drx = -drx; dry = -dry; double swap = eang; eang = sang; sang = swap; eang += M_PI; sang += M_PI; if (eang >= 2 * M_PI) eang -= 2 * M_PI; if (sang >= 2 * M_PI) sang -= 2 * M_PI; } } else { if (large == false) { drx = -drx; dry = -dry; double swap = eang; eang = sang; sang = swap; eang += M_PI; sang += M_PI; if (eang >= 2 * M_PI) eang -= 2 * M_PI; if (sang >= 2 * M_PI) sang -= 2 * M_PI; } } drx += (iS[0] + iE[0]) / 2; dry += (iS[1] + iE[1]) / 2; if (wise) { if (sang < eang) sang += 2 * M_PI; double b = sang * (1 - at) + eang * at; double cb = cos (b), sb = sin (b); pos[0] = drx + ca * rx * cb - sa * ry * sb; pos[1] = dry + sa * rx * cb + ca * ry * sb; tgt[0] = ca * rx * sb + sa * ry * cb; tgt[1] = sa * rx * sb - ca * ry * cb; NR::Point dtgt; dtgt[0] = -ca * rx * cb + sa * ry * sb; dtgt[1] = -sa * rx * cb - ca * ry * sb; len = L2(tgt); rad = len * dot(tgt, tgt) / (tgt[0] * dtgt[1] - tgt[1] * dtgt[0]); tgt /= len; } else { if (sang > eang) sang -= 2 * M_PI; double b = sang * (1 - at) + eang * at; double cb = cos (b), sb = sin (b); pos[0] = drx + ca * rx * cb - sa * ry * sb; pos[1] = dry + sa * rx * cb + ca * ry * sb; tgt[0] = ca * rx * sb + sa * ry * cb; tgt[1] = sa * rx * sb - ca * ry * cb; NR::Point dtgt; dtgt[0] = -ca * rx * cb + sa * ry * sb; dtgt[1] = -sa * rx * cb - ca * ry * sb; len = L2(tgt); rad = len * dot(tgt, tgt) / (tgt[0] * dtgt[1] - tgt[1] * dtgt[0]); tgt /= len; } } void Path::TangentOnCubAt (double at, NR::Point const &iS, PathDescrCubicTo const &fin, bool before, NR::Point &pos, NR::Point &tgt, double &len, double &rad) { const NR::Point E = fin.p; const NR::Point Sd = fin.start; const NR::Point Ed = fin.end; pos = iS; tgt = NR::Point(0,0); len = rad = 0; const NR::Point A = Sd + Ed - 2*E + 2*iS; const NR::Point B = 0.5*(Ed - Sd); const NR::Point C = 0.25*(6*E - 6*iS - Sd - Ed); const NR::Point D = 0.125*(4*iS + 4*E - Ed + Sd); const double atb = at - 0.5; pos = (atb * atb * atb)*A + (atb * atb)*B + atb*C + D; const NR::Point der = (3 * atb * atb)*A + (2 * atb)*B + C; const NR::Point dder = (6 * atb)*A + 2*B; const NR::Point ddder = 6 * A; double l = NR::L2 (der); // lots of nasty cases. inversion points are sadly too common... if (l <= 0.0001) { len = 0; l = L2(dder); if (l <= 0.0001) { l = L2(ddder); if (l <= 0.0001) { // pas de segment.... return; } rad = 100000000; tgt = ddder / l; if (before) { tgt = -tgt; } return; } rad = -l * (dot(dder,dder)) / (cross(ddder,dder)); tgt = dder / l; if (before) { tgt = -tgt; } return; } len = l; rad = -l * (dot(der,der)) / (cross(dder,der)); tgt = der / l; } void Path::TangentOnBezAt (double at, NR::Point const &iS, PathDescrIntermBezierTo & mid, PathDescrBezierTo & fin, bool before, NR::Point & pos, NR::Point & tgt, double &len, double &rad) { pos = iS; tgt = NR::Point(0,0); len = rad = 0; const NR::Point A = fin.p + iS - 2*mid.p; const NR::Point B = 2*mid.p - 2 * iS; const NR::Point C = iS; pos = at * at * A + at * B + C; const NR::Point der = 2 * at * A + B; const NR::Point dder = 2 * A; double l = NR::L2(der); if (l <= 0.0001) { l = NR::L2(dder); if (l <= 0.0001) { // pas de segment.... // Not a segment. return; } rad = 100000000; // Why this number? tgt = dder / l; if (before) { tgt = -tgt; } return; } len = l; rad = -l * (dot(der,der)) / (cross(dder,der)); tgt = der / l; } void Path::OutlineJoin (Path * dest, NR::Point pos, NR::Point stNor, NR::Point enNor, double width, JoinType join, double miter) { const double angSi = cross (enNor,stNor); const double angCo = dot (stNor, enNor); // 1/1000 is very big/ugly, but otherwise it stuffs things up a little... // 1/1000 est tres grossier, mais sinon ca merde tout azimut if ((width >= 0 && angSi > -0.001) || (width < 0 && angSi < 0.001)) { if (angCo > 0.999) { // straight ahead // tout droit } else if (angCo < -0.999) { // half turn // demit-tour dest->LineTo (pos + width*enNor); } else { dest->LineTo (pos); dest->LineTo (pos + width*enNor); } } else { if (join == join_round) { // Use the ends of the cubic: approximate the arc at the // point where .., and support better the rounding of // coordinates of the end points. // utiliser des bouts de cubique: approximation de l'arc (au point ou on en est...), et supporte mieux // l'arrondi des coordonnees des extremites /* double angle=acos(angCo); if ( angCo >= 0 ) { NR::Point stTgt,enTgt; RotCCWTo(stNor,stTgt); RotCCWTo(enNor,enTgt); dest->CubicTo(pos.x+width*enNor.x,pos.y+width*enNor.y, angle*width*stTgt.x,angle*width*stTgt.y, angle*width*enTgt.x,angle*width*enTgt.y); } else { NR::Point biNor; NR::Point stTgt,enTgt,biTgt; biNor.x=stNor.x+enNor.x; biNor.y=stNor.y+enNor.y; double biL=sqrt(biNor.x*biNor.x+biNor.y*biNor.y); biNor.x/=biL; biNor.y/=biL; RotCCWTo(stNor,stTgt); RotCCWTo(enNor,enTgt); RotCCWTo(biNor,biTgt); dest->CubicTo(pos.x+width*biNor.x,pos.y+width*biNor.y, angle*width*stTgt.x,angle*width*stTgt.y, angle*width*biTgt.x,angle*width*biTgt.y); dest->CubicTo(pos.x+width*enNor.x,pos.y+width*enNor.y, angle*width*biTgt.x,angle*width*biTgt.y, angle*width*enTgt.x,angle*width*enTgt.y); }*/ if (width > 0) { dest->ArcTo (pos + width*enNor, 1.0001 * width, 1.0001 * width, 0.0, false, true); } else { dest->ArcTo (pos + width*enNor, -1.0001 * width, -1.0001 * width, 0.0, false, false); } } else if (join == join_pointy) { NR::Point const biss = unit_vector(NR::rot90( stNor - enNor )); double c2 = NR::dot (biss, enNor); double l = width / c2; if ( fabs(l) > miter) { dest->LineTo (pos + width*enNor); } else { dest->LineTo (pos+l*biss); dest->LineTo (pos+width*enNor); } } else { dest->LineTo (pos + width*enNor); } } } // les callbacks // see http://www.home.unix-ag.org/simon/sketch/pathstroke.py to understand what's happening here void Path::RecStdCubicTo (outline_callback_data * data, double tol, double width, int lev) { NR::Point stPos, miPos, enPos; NR::Point stTgt, enTgt, miTgt, stNor, enNor, miNor; double stRad, miRad, enRad; double stTle, miTle, enTle; // un cubic { PathDescrCubicTo temp(NR::Point(data->x2, data->y2), NR::Point(data->d.c.dx1, data->d.c.dy1), NR::Point(data->d.c.dx2, data->d.c.dy2)); NR::Point initial_point(data->x1, data->y1); TangentOnCubAt (0.0, initial_point, temp, false, stPos, stTgt, stTle, stRad); TangentOnCubAt (0.5, initial_point, temp, false, miPos, miTgt, miTle, miRad); TangentOnCubAt (1.0, initial_point, temp, true, enPos, enTgt, enTle, enRad); stNor=stTgt.cw(); miNor=miTgt.cw(); enNor=enTgt.cw(); } double stGue = 1, miGue = 1, enGue = 1; // correction of the lengths of the tangent to the offset // if you don't see why i wrote that, draw a little figure and everything will be clear if (fabs (stRad) > 0.01) stGue += width / stRad; if (fabs (miRad) > 0.01) miGue += width / miRad; if (fabs (enRad) > 0.01) enGue += width / enRad; stGue *= stTle; miGue *= miTle; enGue *= enTle; if (lev <= 0) { int n_d = data->dest->CubicTo (enPos + width*enNor, stGue*stTgt, enGue*enTgt); if (n_d >= 0) { data->dest->descr_cmd[n_d]->associated = data->piece; data->dest->descr_cmd[n_d]->tSt = data->tSt; data->dest->descr_cmd[n_d]->tEn = data->tEn; } return; } NR::Point chk; const NR::Point req = miPos + width * miNor; { PathDescrCubicTo temp(enPos + width * enNor, stGue * stTgt, enGue * enTgt); double chTle, chRad; NR::Point chTgt; TangentOnCubAt (0.5, stPos+width*stNor, temp, false, chk, chTgt, chTle, chRad); } const NR::Point diff = req - chk; const double err = dot(diff,diff); if (err <= tol ) { // tolerance is given as a quadratic value, no need to use tol*tol here // printf("%f <= %f %i\n",err,tol,lev); int n_d = data->dest->CubicTo (enPos + width*enNor, stGue*stTgt, enGue*enTgt); if (n_d >= 0) { data->dest->descr_cmd[n_d]->associated = data->piece; data->dest->descr_cmd[n_d]->tSt = data->tSt; data->dest->descr_cmd[n_d]->tEn = data->tEn; } } else { outline_callback_data desc = *data; desc.tSt = data->tSt; desc.tEn = (data->tSt + data->tEn) / 2; desc.x1 = data->x1; desc.y1 = data->y1; desc.x2 = miPos[0]; desc.y2 = miPos[1]; desc.d.c.dx1 = 0.5 * stTle * stTgt[0]; desc.d.c.dy1 = 0.5 * stTle * stTgt[1]; desc.d.c.dx2 = 0.5 * miTle * miTgt[0]; desc.d.c.dy2 = 0.5 * miTle * miTgt[1]; RecStdCubicTo (&desc, tol, width, lev - 1); desc.tSt = (data->tSt + data->tEn) / 2; desc.tEn = data->tEn; desc.x1 = miPos[0]; desc.y1 = miPos[1]; desc.x2 = data->x2; desc.y2 = data->y2; desc.d.c.dx1 = 0.5 * miTle * miTgt[0]; desc.d.c.dy1 = 0.5 * miTle * miTgt[1]; desc.d.c.dx2 = 0.5 * enTle * enTgt[0]; desc.d.c.dy2 = 0.5 * enTle * enTgt[1]; RecStdCubicTo (&desc, tol, width, lev - 1); } } void Path::StdCubicTo (Path::outline_callback_data * data, double tol, double width) { // fflush (stdout); RecStdCubicTo (data, tol, width, 8); } void Path::StdBezierTo (Path::outline_callback_data * data, double tol, double width) { PathDescrBezierTo tempb(NR::Point(data->x2, data->y2), 1); PathDescrIntermBezierTo tempi(NR::Point(data->d.b.mx, data->d.b.my)); NR::Point stPos, enPos, stTgt, enTgt; double stRad, enRad, stTle, enTle; NR::Point tmp(data->x1,data->y1); TangentOnBezAt (0.0, tmp, tempi, tempb, false, stPos, stTgt, stTle, stRad); TangentOnBezAt (1.0, tmp, tempi, tempb, true, enPos, enTgt, enTle, enRad); data->d.c.dx1 = stTle * stTgt[0]; data->d.c.dy1 = stTle * stTgt[1]; data->d.c.dx2 = enTle * enTgt[0]; data->d.c.dy2 = enTle * enTgt[1]; RecStdCubicTo (data, tol, width, 8); } void Path::RecStdArcTo (outline_callback_data * data, double tol, double width, int lev) { NR::Point stPos, miPos, enPos; NR::Point stTgt, enTgt, miTgt, stNor, enNor, miNor; double stRad, miRad, enRad; double stTle, miTle, enTle; // un cubic { PathDescrArcTo temp(NR::Point(data->x2, data->y2), data->d.a.rx, data->d.a.ry, data->d.a.angle, data->d.a.large, data->d.a.clock); NR::Point tmp(data->x1,data->y1); TangentOnArcAt (data->d.a.stA, tmp, temp, stPos, stTgt, stTle, stRad); TangentOnArcAt ((data->d.a.stA + data->d.a.enA) / 2, tmp, temp, miPos, miTgt, miTle, miRad); TangentOnArcAt (data->d.a.enA, tmp, temp, enPos, enTgt, enTle, enRad); stNor=stTgt.cw(); miNor=miTgt.cw(); enNor=enTgt.cw(); } double stGue = 1, miGue = 1, enGue = 1; if (fabs (stRad) > 0.01) stGue += width / stRad; if (fabs (miRad) > 0.01) miGue += width / miRad; if (fabs (enRad) > 0.01) enGue += width / enRad; stGue *= stTle; miGue *= miTle; enGue *= enTle; double sang, eang; { NR::Point tms(data->x1,data->y1),tme(data->x2,data->y2); ArcAngles (tms,tme, data->d.a.rx, data->d.a.ry, data->d.a.angle, data->d.a.large, !data->d.a.clock, sang, eang); } double scal = eang - sang; if (scal < 0) scal += 2 * M_PI; if (scal > 2 * M_PI) scal -= 2 * M_PI; scal *= data->d.a.enA - data->d.a.stA; if (lev <= 0) { int n_d = data->dest->CubicTo (enPos + width*enNor, stGue*scal*stTgt, enGue*scal*enTgt); if (n_d >= 0) { data->dest->descr_cmd[n_d]->associated = data->piece; data->dest->descr_cmd[n_d]->tSt = data->d.a.stA; data->dest->descr_cmd[n_d]->tEn = data->d.a.enA; } return; } NR::Point chk; const NR::Point req = miPos + width*miNor; { PathDescrCubicTo temp(enPos + width * enNor, stGue * scal * stTgt, enGue * scal * enTgt); double chTle, chRad; NR::Point chTgt; TangentOnCubAt (0.5, stPos+width*stNor, temp, false, chk, chTgt, chTle, chRad); } const NR::Point diff = req - chk; const double err = (dot(diff,diff)); if (err <= tol * tol) { int n_d = data->dest->CubicTo (enPos + width*enNor, stGue*scal*stTgt, enGue*scal*enTgt); if (n_d >= 0) { data->dest->descr_cmd[n_d]->associated = data->piece; data->dest->descr_cmd[n_d]->tSt = data->d.a.stA; data->dest->descr_cmd[n_d]->tEn = data->d.a.enA; } } else { outline_callback_data desc = *data; desc.d.a.stA = data->d.a.stA; desc.d.a.enA = (data->d.a.stA + data->d.a.enA) / 2; RecStdArcTo (&desc, tol, width, lev - 1); desc.d.a.stA = (data->d.a.stA + data->d.a.enA) / 2; desc.d.a.enA = data->d.a.enA; RecStdArcTo (&desc, tol, width, lev - 1); } } void Path::StdArcTo (Path::outline_callback_data * data, double tol, double width) { data->d.a.stA = 0.0; data->d.a.enA = 1.0; RecStdArcTo (data, tol, width, 8); } /* Local Variables: mode:c++ c-file-style:"stroustrup" c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) indent-tabs-mode:nil fill-column:99 End: */ // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4 :