[Gnash-commit] gnash ChangeLog server/parser/shape_character_d...

[Udo Giacomozzi]

CVSROOT:        /cvsroot/gnash
Module name:    gnash
Changes by:     Udo Giacomozzi <udog>   07/11/05 14:55:02

Modified files:
        .              : ChangeLog 
        server/parser  : shape_character_def.cpp 

Log message:
        server/parser/shape_character_def.cpp: Implement a new point_test 
algorithm (disabled by default since it's subject to discussion)

CVSWeb URLs:
http://cvs.savannah.gnu.org/viewcvs/gnash/ChangeLog?cvsroot=gnash&r1=1.4768&r2=1.4769
http://cvs.savannah.gnu.org/viewcvs/gnash/server/parser/shape_character_def.cpp?cvsroot=gnash&r1=1.42&r2=1.43

Patches:
Index: ChangeLog
===================================================================
RCS file: /cvsroot/gnash/gnash/ChangeLog,v
retrieving revision 1.4768
retrieving revision 1.4769
diff -u -b -r1.4768 -r1.4769
--- ChangeLog   5 Nov 2007 10:00:09 -0000       1.4768
+++ ChangeLog   5 Nov 2007 14:55:01 -0000       1.4769
@@ -1,3 +1,8 @@
+2007-11-05 Udo Giacomozzi <address@hidden>
+
+       * server/parser/shape_character_def.cpp: Implement a new point_test
+         algorithm (disabled by default since it's subject to discussion)      
+
 2007-11-05 Bastiaan Jacques <address@hidden>
 
        * backend/render_handler_agg.cpp: Use agg::renderer_mclip instead

Index: server/parser/shape_character_def.cpp
===================================================================
RCS file: /cvsroot/gnash/gnash/server/parser/shape_character_def.cpp,v
retrieving revision 1.42
retrieving revision 1.43
diff -u -b -r1.42 -r1.43
--- server/parser/shape_character_def.cpp       4 Nov 2007 23:12:56 -0000       
1.42
+++ server/parser/shape_character_def.cpp       5 Nov 2007 14:55:02 -0000       
1.43
@@ -17,7 +17,7 @@
 // Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 //
 
-/* $Id: shape_character_def.cpp,v 1.42 2007/11/04 23:12:56 strk Exp $ */
+/* $Id: shape_character_def.cpp,v 1.43 2007/11/05 14:55:02 udog Exp $ */
 
 // Based on the public domain shape.cpp of Thatcher Ulrich <address@hidden> 
2003
 
@@ -36,6 +36,11 @@
 #include <cfloat>
 #include <algorithm>
 
+// Define the macro below to use the new (Udo's) point-in-shape algorithm
+// which should work perfectly for any shape but ignores strokes at the 
+// moment.
+#define USE_NEW_POINT_TEST
+
 // Define the macro below to always compute bounds for shape characters
 // and compare them with the bounds encoded in the SWF
 //#define GNASH_DEBUG_SHAPE_BOUNDS 1
@@ -716,6 +721,272 @@
 }
 
 
+#ifdef USE_NEW_POINT_TEST
+
+// TODO: this should be moved to libgeometry or something
+int curve_x_crossings(float x0, float y0, float x1, float y1, 
+  float cx, float cy, float y, float &cross1, float &cross2)
+    // Finds the quadratic bezier curve crossings with the line Y.
+    // The function can have zero, one or two solutions (cross1, cross2). The 
+    // return value of the function is the number of solutions. 
+    // x0, y0 = start point of the curve
+    // x1, y1 = end point of the curve (anchor, aka ax|ay)
+    // cx, cy = control point of the curve
+    // If there are two crossings, cross1 is the nearest to x0|y0 on the 
curve.   
+{ 
+  int count=0;
+  
+  // check if any crossings possible
+  if ( ((y0 < y) && (y1 < y) && (cy < y))
+    || ((y0 > y) && (y1 > y) && (cy > y)) ) {
+    // all above or below -- no possibility of crossing 
+    return 0;
+  }
+  
+  // Quadratic bezier is:
+  //
+  // p = (1-t)^2 * a0 + 2t(1-t) * c + t^2 * a1
+  //
+  // We need to solve for x at y.
+  
+  // Use the quadratic formula.
+  
+  // Numerical Recipes suggests this variation:
+  // q = -0.5 [b +sgn(b) sqrt(b^2 - 4ac)]
+  // x1 = q/a;  x2 = c/q;
+  
+  
+  float A = y1 + y0 - 2 * cy;
+  float B = 2 * (cy - y0);
+  float C = y0 - y;
+  
+  float rad = B * B - 4 * A * C;
+  
+  if (rad < 0) {
+    return 0;
+  } else {
+    float q;
+    float sqrt_rad = sqrtf(rad);
+    if (B < 0) {
+      q = -0.5f * (B - sqrt_rad);
+    } else {
+      q = -0.5f * (B + sqrt_rad);
+    }
+    
+    // The old-school way.
+    // float t0 = (-B + sqrt_rad) / (2 * A);
+    // float t1 = (-B - sqrt_rad) / (2 * A);
+    
+    if (q != 0)        {
+      float t1 = C / q;
+      if (t1 >= 0 && t1 < 1) {
+        float x_at_t1 =
+          x0 + 2 * (cx - x0) * t1 + (x1 + x0 - 2 * cx) * t1 * t1;
+          
+        count++;
+        assert(count==1);
+        cross1 = x_at_t1; // order is important!
+      }
+    }
+    
+    if (A != 0)        {
+      float t0 = q / A;
+      if (t0 >= 0 && t0 < 1) {
+        float x_at_t0 =
+          x0 + 2 * (cx - x0) * t0 + (x1 + x0 - 2 * cx) * t0 * t0;
+          
+        count++;
+        if (count==2)
+          cross2 = x_at_t0; // order is important!
+        else
+          cross1 = x_at_t0;
+      }
+    }
+    
+    
+  }
+  
+  return count;
+}
+  
+  
+  
+bool  shape_character_def::point_test_local(float x, float y)
+    // Return true if the specified point is on the interior of our shape.
+    // Incoming coords are local coords.
+{
+
+  bool result = false;
+  unsigned npaths = m_paths.size();
+  float last_crossing;
+  bool first = true;
+
+  // browse all paths...  
+  for (unsigned pno=0; pno<npaths; pno++) {
+  
+    const path& pth = m_paths[pno];
+    unsigned nedges = pth.m_edges.size();
+
+    float next_pen_x = pth.m_ax;
+    float next_pen_y = pth.m_ay;
+    float pen_x, pen_y;
+    
+    if (pth.m_new_shape) {
+      // beginning new subshape. if the previous subshape found a hit, return
+      // immediately, otherwise process new subshape.
+      
+      if (result)
+        return true;
+      result = false;
+      first = true;
+    }
+    
+    // ...and edges
+    for (unsigned eno=0; eno<nedges; eno++) {
+    
+      const edge& edg = pth.m_edges[eno];
+      int fill;
+      
+      pen_x = next_pen_x;
+      pen_y = next_pen_y;
+      
+      next_pen_x = edg.m_ax;   
+      next_pen_y = edg.m_ay;
+      
+      /*
+      printf("EDGE #%d #%d [ %d %d ] : %.2f / %.2f -> %.2f / %.2f\n", pno, eno,
+        pth.m_fill0, pth.m_fill1, 
+        pen_x, pen_y, 
+        edg.m_ax, edg.m_ay);
+      */
+        
+        
+      float cross_x;
+      int cross_dir; // +1 = downward, -1 = upward
+      
+      if (edg.is_straight()) {
+      
+        // ==> straight line case
+      
+        // ignore horizontal lines
+        if (edg.m_ay == pen_y)   // TODO: better check for small difference? 
+          continue;          
+          
+        // does this line cross the Y coordinate?
+        if ( ((pen_y <= y) && (edg.m_ay >= y))
+          || ((pen_y >= y) && (edg.m_ay <= y)) ) {
+          
+          // calculate X crossing
+          cross_x = pen_x + (edg.m_ax - pen_x) *  
+            (y - pen_y) / (edg.m_ay - pen_y);
+            
+          if (pen_y > edg.m_ay)
+            cross_dir = -1; // upward
+          else
+            cross_dir = +1; // downward
+        
+        } else {
+        
+          // no crossing, ignore edge..
+          continue;
+        
+        }
+        
+      } else {
+      
+        // ==> curve case
+        
+        float cross1, cross2;
+        int dir1, dir2;
+
+        int scount = curve_x_crossings(pen_x, pen_y, edg.m_ax, edg.m_ay,
+          edg.m_cx, edg.m_cy, y, cross1, cross2);
+          
+        dir1 = pen_y > y ? -1 : +1;
+        dir2 = dir1 * (-1);     // second crossing always in opposite dir.
+        
+        /*
+        printf("  curve crosses at %d points\n", scount);
+        
+        if (scount>0)
+          printf("    first  crossing at %.2f / %.2f, dir %d\n", cross1, y, 
dir1);
+
+        if (scount>1)
+          printf("    second crossing at %.2f / %.2f, dir %d\n", cross2, y, 
dir2);
+        */
+
+        // ignore crossings on the right side          
+        if ((scount>1) && (cross2 > x)) 
+          scount--;
+        
+        if ((scount>0) && (cross1 > x)) {
+          cross1 = cross2;
+          dir1 = dir2;
+          scount--;
+        }
+
+        if (scount==0)
+          continue;  // no crossing left
+          
+        // still two crossings? take the nearest
+        if (scount==2) {
+          if (cross2 > cross1) {
+            cross_x = cross2;
+            cross_dir = dir2;            
+          } else {
+            cross_x = cross1;
+            cross_dir = dir1;            
+          }
+        } else {
+          cross_x = cross1;
+          cross_dir = dir1;
+        }
+      
+      } // curve
+      
+      
+      // ==> we have now:
+      //  - a valid cross_x, which is left to "x"
+      //  - cross_dir tells the direction of the crossing 
+      //    (+1 = downward, -1 = upward)
+      
+            
+      //printf(" found a crossing at %.2f / %.2f, dir %d\n", cross_x, y, 
cross_dir);
+        
+      // we only want crossings at the left of the hit test point
+      if (cross_x > x) 
+        continue;
+        
+      // we are looking for the crossing with the largest X coordinate,
+      // skip others
+      if (!first && (cross_x <= last_crossing))
+        continue;
+        
+      // ==> we found a valid crossing  
+        
+      last_crossing = cross_x;
+      first = false;          
+                            
+      // choose the appropriate fill style index (we need the one
+      // in direction to the hit test point)
+      if (cross_dir < 0)
+        fill = pth.m_fill1;   // upward -> right style
+      else
+        fill = pth.m_fill0;   // downward -> left style
+        
+      result = fill > 0; // current result until we find a better crossing
+        
+      
+    } // for edge   
+  
+  } // for path
+  
+
+  return result;
+}
+
+#else // ifdef USE_NEW_POINT_TEST
+
 bool   shape_character_def::point_test_local(float x, float y)
     // Return true if the specified point is on the interior of our shape.
     // Incoming coords are local coords.
@@ -778,7 +1049,7 @@
     }
     return false;
 }
-
+#endif
 
 float shape_character_def::get_height_local() const
 {