make faster 2geom bbox calc.

(bzr r6032)

1 files changed, 154 insertions, 4 deletions

diff --git a/src/helper/geom.cpp b/src/helper/geom.cpp
index 8a32386fc..937303598 100644
--- a/src/helper/geom.cpp
+++ b/src/helper/geom.cpp
@@ -15,17 +15,167 @@
 

 #include <2geom/pathvector.h>

 #include <2geom/transforms.h>

- 

+#include <2geom/rect.h>

+#include <2geom/coord.h>

+

+/* Fast bbox calculation */

+/* Thanks to Nathan Hurst for suggesting it */

+static void

+cubic_bbox (Geom::Coord x000, Geom::Coord y000, Geom::Coord x001, Geom::Coord y001, Geom::Coord x011, Geom::Coord y011, Geom::Coord x111, Geom::Coord y111, Geom::Rect &bbox)

+{

+    Geom::Coord a, b, c, D;

+

+    bbox[0].extendTo(x111);

+    bbox[1].extendTo(y111);

+

+    /*

+     * xttt = s * (s * (s * x000 + t * x001) + t * (s * x001 + t * x011)) + t * (s * (s * x001 + t * x011) + t * (s * x011 + t * x111))

+     * xttt = s * (s2 * x000 + s * t * x001 + t * s * x001 + t2 * x011) + t * (s2 * x001 + s * t * x011 + t * s * x011 + t2 * x111)

+     * xttt = s * (s2 * x000 + 2 * st * x001 + t2 * x011) + t * (s2 * x001 + 2 * st * x011 + t2 * x111)

+     * xttt = s3 * x000 + 2 * s2t * x001 + st2 * x011 + s2t * x001 + 2st2 * x011 + t3 * x111

+     * xttt = s3 * x000 + 3s2t * x001 + 3st2 * x011 + t3 * x111

+     * xttt = s3 * x000 + (1 - s) 3s2 * x001 + (1 - s) * (1 - s) * 3s * x011 + (1 - s) * (1 - s) * (1 - s) * x111

+     * xttt = s3 * x000 + (3s2 - 3s3) * x001 + (3s - 6s2 + 3s3) * x011 + (1 - 2s + s2 - s + 2s2 - s3) * x111

+     * xttt = (x000 - 3 * x001 + 3 * x011 -     x111) * s3 +

+     *        (       3 * x001 - 6 * x011 + 3 * x111) * s2 +

+     *        (                  3 * x011 - 3 * x111) * s  +

+     *        (                                 x111)

+     * xttt' = (3 * x000 - 9 * x001 +  9 * x011 - 3 * x111) * s2 +

+     *         (           6 * x001 - 12 * x011 + 6 * x111) * s  +

+     *         (                       3 * x011 - 3 * x111)

+     */

+

+    a = 3 * x000 - 9 * x001 + 9 * x011 - 3 * x111;

+    b = 6 * x001 - 12 * x011 + 6 * x111;

+    c = 3 * x011 - 3 * x111;

+

+    /*

+     * s = (-b +/- sqrt (b * b - 4 * a * c)) / 2 * a;

+     */

+    if (fabs (a) < Geom::EPSILON) {

+        /* s = -c / b */

+        if (fabs (b) > Geom::EPSILON) {

+            double s, t, xttt;

+            s = -c / b;

+            if ((s > 0.0) && (s < 1.0)) {

+                t = 1.0 - s;

+                xttt = s * s * s * x000 + 3 * s * s * t * x001 + 3 * s * t * t * x011 + t * t * t * x111;

+                bbox[0].extendTo(xttt);

+            }

+        }

+    } else {

+        /* s = (-b +/- sqrt (b * b - 4 * a * c)) / 2 * a; */

+        D = b * b - 4 * a * c;

+        if (D >= 0.0) {

+            Geom::Coord d, s, t, xttt;

+            /* Have solution */

+            d = sqrt (D);

+            s = (-b + d) / (2 * a);

+            if ((s > 0.0) && (s < 1.0)) {

+                t = 1.0 - s;

+                xttt = s * s * s * x000 + 3 * s * s * t * x001 + 3 * s * t * t * x011 + t * t * t * x111;

+                bbox[0].extendTo(xttt);

+            }

+            s = (-b - d) / (2 * a);

+            if ((s > 0.0) && (s < 1.0)) {

+                t = 1.0 - s;

+                xttt = s * s * s * x000 + 3 * s * s * t * x001 + 3 * s * t * t * x011 + t * t * t * x111;

+                bbox[0].extendTo(xttt);

+            }

+        }

+    }

+

+    a = 3 * y000 - 9 * y001 + 9 * y011 - 3 * y111;

+    b = 6 * y001 - 12 * y011 + 6 * y111;

+    c = 3 * y011 - 3 * y111;

+

+    if (fabs (a) < Geom::EPSILON) {

+        /* s = -c / b */

+        if (fabs (b) > Geom::EPSILON) {

+            double s, t, yttt;

+            s = -c / b;

+            if ((s > 0.0) && (s < 1.0)) {

+                t = 1.0 - s;

+                yttt = s * s * s * y000 + 3 * s * s * t * y001 + 3 * s * t * t * y011 + t * t * t * y111;

+                bbox[1].extendTo(yttt);

+            }

+        }

+    } else {

+        /* s = (-b +/- sqrt (b * b - 4 * a * c)) / 2 * a; */

+        D = b * b - 4 * a * c;

+        if (D >= 0.0) {

+            Geom::Coord d, s, t, yttt;

+            /* Have solution */

+            d = sqrt (D);

+            s = (-b + d) / (2 * a);

+            if ((s > 0.0) && (s < 1.0)) {

+                t = 1.0 - s;

+                yttt = s * s * s * y000 + 3 * s * s * t * y001 + 3 * s * t * t * y011 + t * t * t * y111;

+                bbox[1].extendTo(yttt);

+            }

+            s = (-b - d) / (2 * a);

+            if ((s > 0.0) && (s < 1.0)) {

+                t = 1.0 - s;

+                yttt = s * s * s * y000 + 3 * s * s * t * y001 + 3 * s * t * t * y011 + t * t * t * y111;

+                bbox[1].extendTo(yttt);

+            }

+        }

+    }

+}

+

 Geom::Rect

 bounds_fast_transformed(Geom::PathVector const & pv, Geom::Matrix const & t)

 {

-    return Geom::bounds_fast(pv * t);

+    return bounds_exact_transformed(pv, t); //use this as it is faster for now! :)

+//    return Geom::bounds_fast(pv * t);

 }

 

 Geom::Rect

 bounds_exact_transformed(Geom::PathVector const & pv, Geom::Matrix const & t)

 {

-    return Geom::bounds_exact(pv * t);

+    Geom::Rect bbox;

+    

+    if (pv.empty())

+        return bbox;

+

+    Geom::Curve *temp = pv.front().front().transformed(t);

+    bbox = temp->boundsExact();

+    delete temp;

+

+    for (Geom::PathVector::const_iterator it = pv.begin(); it != pv.end(); ++it) {

+        bbox.expandTo(it->initialPoint() * t);

+

+        // don't loop including closing segment, since that segment can never increase the bbox

+        for (Geom::Path::const_iterator cit = it->begin(); cit != it->end_open(); ++cit) {

+            Geom::Curve const *c = &*cit;

+

+            if(Geom::LineSegment const *line_segment = dynamic_cast<Geom::LineSegment const *>(c))

+            {

+                bbox.expandTo( (*line_segment)[1] * t );

+            }

+            else if(Geom::CubicBezier const *cubic_bezier = dynamic_cast<Geom::CubicBezier const  *>(c))

+            {

+                Geom::Point c0 = (*cubic_bezier)[0] * t;

+                Geom::Point c1 = (*cubic_bezier)[1] * t;

+                Geom::Point c2 = (*cubic_bezier)[2] * t;

+                Geom::Point c3 = (*cubic_bezier)[3] * t;

+                cubic_bbox( c0[0], c0[1],

+                            c1[0], c1[1],

+                            c2[0], c2[1],

+                            c3[0], c3[1],

+                            bbox );

+            }

+            else

+            {

+                // should handle all not-so-easy curves:

+                Geom::Curve *ctemp = cit->transformed(t);

+                bbox.unionWith( ctemp->boundsExact());

+                delete ctemp;

+            }

+        }

+    }

+    //return Geom::bounds_exact(pv * t);

+    return bbox;

 }

 

 /*

@@ -37,4 +187,4 @@ bounds_exact_transformed(Geom::PathVector const & pv, Geom::Matrix const & t)
   fill-column:99

   End:

 */

-// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
\ No newline at end of file
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :