libcore/Geometry.cpp

   1 //
   2 //   Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
   3 //   Free Software Foundation, Inc
   4 //
   5 // This program is free software; you can redistribute it and/or modify
   6 // it under the terms of the GNU General Public License as published by
   7 // the Free Software Foundation; either version 3 of the License, or
   8 // (at your option) any later version.
   9 //
  10 // This program is distributed in the hope that it will be useful,
  11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 // GNU General Public License for more details.
  14 //
  15 // You should have received a copy of the GNU General Public License
  16 // along with this program; if not, write to the Free Software
  17 // Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  18 //
  19
  20 #include "Geometry.h"
  21
  22 #include <cmath>
  23 #include <algorithm>
  24 #include <cstdint>
  25
  26 #include "log.h"
  27 #include "LineStyle.h"
  28
  29 namespace gnash {
  30 namespace geometry {
  31
  32 namespace {
  33
  34 // TODO: this should be moved to libgeometry or something
  35 // Finds the quadratic bezier curve crossings with the line Y.
  36 // The function can have zero, one or two solutions (cross1, cross2). The
  37 // return value of the function is the number of solutions.
  38 // x0, y0 = start point of the curve
  39 // x1, y1 = end point of the curve (anchor, aka ax|ay)
  40 // cx, cy = control point of the curve
  41 // If there are two crossings, cross1 is the nearest to x0|y0 on the curve.
  42 template<typename T>
  43 int curve_x_crossings(const T x0, const T y0, const T x1, const T y1,
  44     const T cx, const T cy, const T y, T& cross1, T& cross2)
  45 {
  46     int count=0;
  47
  48     // check if any crossings possible
  49     if ( ((y0 < y) && (y1 < y) && (cy < y))
  50         || ((y0 > y) && (y1 > y) && (cy > y)) )
  51     {
  52         // all above or below -- no possibility of crossing
  53         return 0;
  54     }
  55
  56     // Quadratic bezier is:
  57     //
  58     // p = (1-t)^2 * a0 + 2t(1-t) * c + t^2 * a1
  59     //
  60     // We need to solve for x at y.
  61
  62     // Use the quadratic formula.
  63
  64     // Numerical Recipes suggests this variation:
  65     // q = -0.5 [b +sgn(b) sqrt(b^2 - 4ac)]
  66     // x1 = q/a;  x2 = c/q;
  67
  68     const T A = y1 + y0 - 2 * cy;
  69     const T B = 2 * (cy - y0);
  70     const T C = y0 - y;
  71
  72     const T rad = B * B - 4 * A * C;
  73
  74     if (rad < 0) {
  75         return 0;
  76     }
  77     else {
  78         T q;
  79         const T sqrt_rad = std::sqrt(rad);
  80         if (B < 0) {
  81             q = -0.5f * (B - sqrt_rad);
  82         }
  83         else {
  84             q = -0.5f * (B + sqrt_rad);
  85         }
  86
  87         // The old-school way.
  88         // float t0 = (-B + sqrt_rad) / (2 * A);
  89         // float t1 = (-B - sqrt_rad) / (2 * A);
  90
  91         if (q != 0) {
  92             const T t1 = C / q;
  93
  94             if (t1 >= 0 && t1 < 1) {
  95                 const T x_at_t1 =
  96                     x0 + 2 * (cx - x0) * t1 + (x1 + x0 - 2 * cx) * t1 * t1;
  97
  98                 count++;
  99                 assert(count==1);
 100                 cross1 = x_at_t1;             // order is important!
 101             }
 102         }
 103
 104         if (A != 0) {
 105             const T t0 = q / A;
 106             if (t0 >= 0 && t0 < 1) {
 107                 const T x_at_t0 =
 108                     x0 + 2 * (cx - x0) * t0 + (x1 + x0 - 2 * cx) * t0 * t0;
 109
 110                 ++count;
 111                 // order is important!
 112                 if (count == 2) cross2 = x_at_t0;
 113                 else cross1 = x_at_t0;
 114             }
 115         }
 116
 117     }
 118
 119     return count;
 120 }
 121
 122 } // anonymous namespace
 123
 124 bool
 125 pointTest(const std::vector<Path>& paths,
 126         const std::vector<LineStyle>& lineStyles, std::int32_t x,
 127         std::int32_t y, const SWFMatrix& wm)
 128 {
 129
 130     /*
 131     Principle:
 132     For the fill of the shape, we project a ray from the test point to the left
 133     side of the shape counting all crossings. When a line or curve segment is
 134     crossed we add 1 if the left fill style is set. Regardless of the left fill
 135     style we subtract 1 from the counter then the right fill style is set.
 136     This is true when the line goes in downward direction. If it goes upward,
 137     the fill styles are reversed.
 138
 139     The final counter value reveals if the point is inside the shape (and
 140     depends on filling rule, see below).
 141     This method should not depend on subshapes and work for some malformed
 142     shapes situations:
 143     - wrong fill side (eg. left side set for a clockwise drawen rectangle)
 144     - intersecting paths
 145     */
 146     point pt(x, y);
 147
 148     // later we will need non-zero for glyphs... (TODO)
 149     bool even_odd = true;
 150
 151     unsigned npaths = paths.size();
 152     int counter = 0;
 153
 154     // browse all paths
 155     for (unsigned pno=0; pno<npaths; pno++)
 156     {
 157         const Path& pth = paths[pno];
 158         unsigned nedges = pth.m_edges.size();
 159
 160         float next_pen_x = pth.ap.x;
 161         float next_pen_y = pth.ap.y;
 162         float pen_x, pen_y;
 163
 164         if (pth.empty()) continue;
 165
 166         // If the path has a line style, check for strokes there
 167         if (pth.m_line != 0 )
 168         {
 169             assert(lineStyles.size() >= pth.m_line);
 170             const LineStyle& ls = lineStyles[pth.m_line-1];
 171             double thickness = ls.getThickness();
 172             if (! thickness )
 173             {
 174                 thickness = 20; // at least ONE PIXEL thick.
 175             }
 176             else if ((!ls.scaleThicknessVertically()) &&
 177                     (!ls.scaleThicknessHorizontally()) )
 178             {
 179                 // TODO: pass the SWFMatrix to withinSquareDistance instead ?
 180                 double xScale = wm.get_x_scale();
 181                 double yScale = wm.get_y_scale();
 182                 thickness *= std::max(xScale, yScale);
 183             }
 184             else if (ls.scaleThicknessVertically() !=
 185                     ls.scaleThicknessHorizontally())
 186             {
 187                 LOG_ONCE(log_unimpl(_("Collision detection for "
 188                                       "unidirectionally scaled strokes")));
 189             }
 190
 191             double dist = thickness / 2.0;
 192             double sqdist = dist * dist;
 193             if (pth.withinSquareDistance(pt, sqdist))
 194                 return true;
 195         }
 196
 197         // browse all edges of the path
 198         for (unsigned eno=0; eno<nedges; eno++)
 199         {
 200             const Edge& edg = pth.m_edges[eno];
 201             pen_x = next_pen_x;
 202             pen_y = next_pen_y;
 203             next_pen_x = edg.ap.x;
 204             next_pen_y = edg.ap.y;
 205
 206             float cross1 = 0.0, cross2 = 0.0;
 207             int dir1 = 0, dir2 = 0; // +1 = downward, -1 = upward
 208             int crosscount = 0;
 209
 210             if (edg.straight())
 211             {
 212                 // ignore horizontal lines
 213                 // TODO: better check for small difference?
 214                 if (edg.ap.y == pen_y)
 215                 {
 216                     continue;
 217                 }
 218                 // does this line cross the Y coordinate?
 219                 if ( ((pen_y <= y) && (edg.ap.y >= y))
 220                     || ((pen_y >= y) && (edg.ap.y <= y)) )
 221                 {
 222
 223                     // calculate X crossing
 224                     cross1 = pen_x + (edg.ap.x - pen_x) *
 225                         (y - pen_y) / (edg.ap.y - pen_y);
 226
 227                     if (pen_y > edg.ap.y)
 228                         dir1 = -1;  // upward
 229                     else
 230                         dir1 = +1;  // downward
 231
 232                     crosscount = 1;
 233                 }
 234                 else
 235                 {
 236                     // no crossing found
 237                     crosscount = 0;
 238                 }
 239             }
 240             else {
 241                 // ==> curve case
 242                 crosscount =
 243                     curve_x_crossings<float>(pen_x, pen_y, edg.ap.x, edg.ap.y,
 244                         edg.cp.x, edg.cp.y, y, cross1, cross2);
 245                 dir1 = pen_y > y ? -1 : +1;
 246                 dir2 = dir1 * (-1); // second crossing always in opposite dir.
 247             } // curve
 248
 249             // ==> we have now:
 250             //  - one (cross1) or two (cross1, cross2) ray crossings (X
 251             //    coordinate)
 252             //  - dir1/dir2 tells the direction of the crossing
 253             //    (+1 = downward, -1 = upward)
 254             //  - crosscount tells the number of crossings
 255
 256             // need at least one crossing
 257             if (crosscount == 0)
 258             {
 259                 continue;
 260             }
 261
 262             // check first crossing
 263             if (cross1 <= x)
 264             {
 265                 if (pth.m_fill0 > 0) counter += dir1;
 266                 if (pth.m_fill1 > 0) counter -= dir1;
 267             }
 268
 269             // check optional second crossing (only possible with curves)
 270             if ( (crosscount > 1) && (cross2 <= x) )
 271             {
 272                 if (pth.m_fill0 > 0) counter += dir2;
 273                 if (pth.m_fill1 > 0) counter -= dir2;
 274             }
 275
 276         }// for edge
 277     } // for path
 278
 279     return ( (even_odd && (counter % 2) != 0) ||
 280              (!even_odd && (counter != 0)) );
 281 }
 282
 283 } // namespace geometry
 284 } // namespace gnash
 285
 286