libcore/Geometry.cpp

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