Added the bulk of the algorithm for GPU accelerated 2D vector curve...

core/cross/gpu2d/cubic_math_utils.cc

Index: core/cross/gpu2d/cubic_math_utils.cc
===================================================================
--- core/cross/gpu2d/cubic_math_utils.cc	(revision 40063)
+++ core/cross/gpu2d/cubic_math_utils.cc	(working copy)
@@ -49,6 +49,59 @@
   return (cross_product < 0.0f) ? -1 : ((cross_product > 0.0f) ? 1 : 0);
 }
 
+bool EdgeEdgeTest(float ax, float ay,
+                  float v0x, float v0y,
+                  float u0x, float u0y,
+                  float u1x, float u1y) {
+  // This edge to edge test is based on Franlin Antonio's gem: "Faster
+  // Line Segment Intersection", in Graphics Gems III, pp. 199-202.
+  float bx = u0x - u1x;
+  float by = u0y - u1y;
+  float cx = v0x - u0x;
+  float cy = v0y - u0y;
+  float f = ay * bx - ax * by;
+  float d = by * cx - bx * cy;
+  if ((f > 0 && d >= 0 && d <= f) || (f < 0 && d <= 0 && d >= f)) {
+    float e = ax * cy - ay * cx;
+
+    // This additional test avoids reporting coincident edges, which
+    // is the behavior we want.
+    if (ApproxEqual(e, 0) || ApproxEqual(f, 0) || ApproxEqual(e, f)) {
+      return false;
+    }
+
+    if (f > 0) {
+      return e >= 0 && e <= f;
+    } else {
+      return e <= 0 && e >= f;
+    }
+  }
+  return false;
+}
+
+bool EdgeAgainstTriEdges(float v0x, float v0y,
+                         float v1x, float v1y,
+                         float u0x, float u0y,
+                         float u1x, float u1y,
+                         float u2x, float u2y) {
+  float ax, ay;
+  ax = v1x - v0x;
+  ay = v1y - v0y;
+  // Test edge u0, u1 against v0, v1.
+  if (EdgeEdgeTest(ax, ay, v0x, v0y, u0x, u0y, u1x, u1y)) {
+    return true;
+  }
+  // Test edge u1, u2 against v0, v1.
+  if (EdgeEdgeTest(ax, ay, v0x, v0y, u1x, u1y, u2x, u2y)) {
+    return true;
+  }
+  // Test edge u2, u1 against v0, v1.
+  if (EdgeEdgeTest(ax, ay, v0x, v0y, u2x, u2y, u0x, u0y)) {
+    return true;
+  }
+  return false;
+}
+
 }  // anonymous namespace
 
 bool LinesIntersect(float p1x, float p1y,
@@ -91,6 +144,44 @@
   return (u > 0.0f) && (v > 0.0f) && (u + v < 1.0f);
 }
 
+bool TrianglesOverlap(float a1x, float a1y,
+                      float b1x, float b1y,
+                      float c1x, float c1y,
+                      float a2x, float a2y,
+                      float b2x, float b2y,
+                      float c2x, float c2y) {
+  // Derived from coplanar_tri_tri() at
+  // http://jgt.akpeters.com/papers/ShenHengTang03/tri_tri.html ,
+  // simplified for the 2D case and modified so that overlapping edges
+  // do not report overlapping triangles.
+
+  // Test all edges of triangle 1 against the edges of triangle 2.
+  if (EdgeAgainstTriEdges(a1x, a1y, b1x, b1y, a2x, a2y, b2x, b2y, c2x, c2y))
+    return true;
+  if (EdgeAgainstTriEdges(b1x, b1y, c1x, c1y, a2x, a2y, b2x, b2y, c2x, c2y))
+    return true;
+  if (EdgeAgainstTriEdges(c1x, c1y, a1x, a1y, a2x, a2y, b2x, b2y, c2x, c2y))
+    return true;
+  // Finally, test if tri1 is totally contained in tri2 or vice versa.
+  if (PointInTriangle(a1x, a1y, a2x, a2y, b2x, b2y, c2x, c2y))
+    return true;
+  if (PointInTriangle(a2x, a2y, a1x, a1y, b1x, b1y, c1x, c1y))
+    return true;
+
+  // Because we define that triangles sharing a vertex or edge don't
+  // overlap, we must perform additional point-in-triangle tests to
+  // see whether one triangle is contained in the other.
+  if (PointInTriangle(b1x, b1y, a2x, a2y, b2x, b2y, c2x, c2y))
+    return true;
+  if (PointInTriangle(c1x, c1y, a2x, a2y, b2x, b2y, c2x, c2y))
+    return true;
+  if (PointInTriangle(b2x, b2y, a1x, a1y, b1x, b1y, c1x, c1y))
+    return true;
+  if (PointInTriangle(c2x, c2y, a1x, a1y, b1x, b1y, c1x, c1y))
+    return true;
+  return false;
+}
+
 }  // namespace cubic
 }  // namespace gpu2d
 }  // namespace o3d