Bezier Rendering Methods High Precision

JavaScript performance comparison

Test case created by Ammar Hattab

Info

Compare Performance of Different Bezier Curves Rendering Methods but with Higher Precision

Preparation code

<canvas id="canvas1" width="420" height="200"></canvas>
<script>
Benchmark.prototype.setup = function() {
        function CalculateMethod1(_preX, _preY, x1, y1, x2, y2, x3, y3, x4, y4, NUM_STEPS)
                {
                    var step = NUM_STEPS;
                        var stepmu = 1/NUM_STEPS;
                        while(step--)
                        {
                           mu = 1-(stepmu* step);
                           var mum1,mum13,mu3;
                           mum1 = 1 - mu;
                           mum13 = mum1 * mum1 * mum1;
                           mu3 = mu * mu * mu;
                           px = mum13*x1 + 3*mu*mum1*mum1*x2 + 3*mu*mu*mum1*x3 + mu3*x4;
                           py = mum13*y1 + 3*mu*mum1*mum1*y2 + 3*mu*mu*mum1*y3 + mu3*y4;                       
                           _preX.push(px);
                           _preY.push(py);                     
                        }
                       
                }
               
                function CalculateMethod2(_preX, _preY, x1, y1, x2, y2, x3, y3, x4, y4, NUM_STEPS)
                {
                    var dx1 = x2 - x1;
                        var dy1 = y2 - y1;
                        var dx2 = x3 - x2;
                        var dy2 = y3 - y2;
                        var dx3 = x4 - x3;
                        var dy3 = y4 - y3;
   
                        var subdiv_step  = 1.0 / (NUM_STEPS + 1);
                        var subdiv_step2 = subdiv_step*subdiv_step;
                        var subdiv_step3 = subdiv_step*subdiv_step*subdiv_step;
   
                        var pre1 = 3.0 * subdiv_step;
                        var pre2 = 3.0 * subdiv_step2;
                        var pre4 = 6.0 * subdiv_step2;
                        var pre5 = 6.0 * subdiv_step3;
   
                        var tmp1x = x1 - x2 * 2.0 + x3;
                        var tmp1y = y1 - y2 * 2.0 + y3;
   
                        var tmp2x = (x2 - x3)*3.0 - x1 + x4;
                        var tmp2y = (y2 - y3)*3.0 - y1 + y4;
   
                        var fx = x1;
                        var fy = y1;
   
                        var dfx = (x2 - x1)*pre1 + tmp1x*pre2 + tmp2x*subdiv_step3;
                        var dfy = (y2 - y1)*pre1 + tmp1y*pre2 + tmp2y*subdiv_step3;
   
                        var ddfx = tmp1x*pre4 + tmp2x*pre5;
                        var ddfy = tmp1y*pre4 + tmp2y*pre5;
   
                        var dddfx = tmp2x*pre5;
                        var dddfy = tmp2y*pre5;
   
                        var step = NUM_STEPS;
   
                        while(step--)
                        {
                                fx   += dfx;
                                fy   += dfy;
                                dfx  += ddfx;
                                dfy  += ddfy;
                                ddfx += dddfx;
                                ddfy += dddfy;
                                _preX.push(fx);
                                _preY.push(fy);                
                        }
                       
                }
               
                function CalculateMethod3(_preX, _preY, x1, y1, x2, y2, x3, y3, x4, y4)
                {
                    var dx1 = x2 - x1;
                        var dy1 = y2 - y1;
                        var dx2 = x3 - x2;
                        var dy2 = y3 - y2;
                        var dx3 = x4 - x3;
                        var dy3 = y4 - y3;
   
                        var len = Math.sqrt(dx1 * dx1 + dy1 * dy1) +
                                  Math.sqrt(dx2 * dx2 + dy2 * dy2) +
                                  Math.sqrt(dx3 * dx3 + dy3 * dy3);
   
                        var num_steps = Math.round(len * 0.25);
                        CalculateMethod2(_preX, _preY, x1, y1, x2, y2, x3, y3, x4, y4, num_steps)
                }
               
                function CalculateMethod4(_preX, _preY, x1, y1, x2, y2, x3, y3, x4, y4, m_distance_tolerance)
                {
   
                        // Calculate all the mid-points of the line segments
                        //----------------------
                        var x12   = (x1 + x2) / 2;
                        var y12   = (y1 + y2) / 2;
                        var x23   = (x2 + x3) / 2;
                        var y23   = (y2 + y3) / 2;
                        var x34   = (x3 + x4) / 2;
                        var y34   = (y3 + y4) / 2;
                        var x123  = (x12 + x23) / 2;
                        var y123  = (y12 + y23) / 2;
                        var x234  = (x23 + x34) / 2;
                        var y234  = (y23 + y34) / 2;
                        var x1234 = (x123 + x234) / 2;
                        var y1234 = (y123 + y234) / 2;
   
                        // Try to approximate the full cubic curve by a single straight line
                        //------------------
                        var dx = x4-x1;
                        var dy = y4-y1;
   
                        var d2 = Math.abs(((x2 - x4) * dy - (y2 - y4) * dx));
                        var d3 = Math.abs(((x3 - x4) * dy - (y3 - y4) * dx));
   
                        if((d2 + d3)*(d2 + d3) < m_distance_tolerance * (dx*dx + dy*dy))
                        {
                                _preX.push(x1234);
                                _preY.push(y1234);
                                return;
                        }
   
                        // Continue subdivision
                        //----------------------
                        CalculateMethod4(_preX, _preY, x1, y1, x12, y12, x123, y123, x1234, y1234, m_distance_tolerance);
                        CalculateMethod4(_preX, _preY, x1234, y1234, x234, y234, x34, y34, x4, y4, m_distance_tolerance);
                }
               
                function CalculateMethod5(_preX, _preY, x1, y1, x2, y2, x3, y3, x4, y4, m_distance_tolerance, m_angle_tolerance , curve_collinearity_epsilon, curve_angle_tolerance_epsilon, m_cusp_limit, curve_recursion_limit, level)
                {
                        if(level > curve_recursion_limit)
                        {
                                return;
                        }
   
                        // Calculate all the mid-points of the line segments
                        //----------------------
                        var x12   = (x1 + x2) / 2;
                        var y12   = (y1 + y2) / 2;
                        var x23   = (x2 + x3) / 2;
                        var y23   = (y2 + y3) / 2;
                        var x34   = (x3 + x4) / 2;
                        var y34   = (y3 + y4) / 2;
                        var x123  = (x12 + x23) / 2;
                        var y123  = (y12 + y23) / 2;
                        var x234  = (x23 + x34) / 2;
                        var y234  = (y23 + y34) / 2;
                        var x1234 = (x123 + x234) / 2;
                        var y1234 = (y123 + y234) / 2;
   
                        if(level > 0) // Enforce subdivision first time
                        {
                                // Try to approximate the full cubic curve by a single straight line
                                //------------------
                                var dx = x4-x1;
                                var dy = y4-y1;
   
                                var d2 = Math.abs(((x2 - x4) * dy - (y2 - y4) * dx));
                                var d3 = Math.abs(((x3 - x4) * dy - (y3 - y4) * dx));
   
                                var da1, da2;
   
                                if(d2 > curve_collinearity_epsilon && d3 > curve_collinearity_epsilon)
                                {
                                        // Regular care
                                        //-----------------
                                        if((d2 + d3)*(d2 + d3) <= m_distance_tolerance * (dx*dx + dy*dy))
                                        {
                                                // If the curvature doesn't exceed the distance_tolerance value
                                                // we tend to finish subdivisions.
                                                //----------------------
                                                if(m_angle_tolerance < curve_angle_tolerance_epsilon)
                                                {
                                                        m_points.add(point_type(x1234, y1234));
                                                        return;
                                                }
   
                                                // Angle & Cusp Condition
                                                //----------------------
                                                var a23 = Math.atan(y3 - y2, x3 - x2);
                                                da1 = Math.abs(a23 - Math.atan(y2 - y1, x2 - x1));
                                                da2 = Math.abs(Math.atan(y4 - y3, x4 - x3) - a23);
                                                if(da1 >= Math.PI) da1 = 2*Math.PI - da1;
                                                if(da2 >= Math.PI) da2 = 2*Math.PI - da2;
   
                                                if(da1 + da2 < m_angle_tolerance)
                                                {
                                                        // Finally we can stop the recursion
                                                        //----------------------
                                                        _preX.push(x1234);
                                                        _preY.push(y1234);
                                                        return;
                                                }
   
                                                if(m_cusp_limit != 0.0)
                                                {
                                                        if(da1 > m_cusp_limit)
                                                        {
                                                                _preX.push(x2);
                                                                _preY.push(y2);
                                                                return;
                                                        }
   
                                                        if(da2 > m_cusp_limit)
                                                        {
                                                                _preX.push(x3);
                                                                _preY.push(y3);
                                                                return;
                                                        }
                                                }
                                        }
                                }
                                else
                                {
                                        if(d2 > curve_collinearity_epsilon)
                                        {
                                                // p1,p3,p4 are collinear, p2 is considerable
                                                //----------------------
                                                if(d2 * d2 <= m_distance_tolerance * (dx*dx + dy*dy))
                                                {
                                                        if(m_angle_tolerance < curve_angle_tolerance_epsilon)
                                                        {
                                                                _preX.push(x1234);
                                                                _preY.push(y1234);
                                                                return;
                                                        }
   
                                                        // Angle Condition
                                                        //----------------------
                                                        da1 = Math.abs(Math.atan(y3 - y2, x3 - x2) - Math.atan(y2 - y1, x2 - x1));
                                                        if(da1 >= Math.PI) da1 = 2*Math.PI - da1;
   
                                                        if(da1 < m_angle_tolerance)
                                                        {
                                                                _preX.push(x2);
                                                                _preY.push(y2);
                                                                _preX.push(x3);
                                                                _preY.push(y3);
                                                                return;
                                                        }
   
                                                        if(m_cusp_limit != 0.0)
                                                        {
                                                                if(da1 > m_cusp_limit)
                                                                {
                                                                        _preX.push(x2);
                                                                        _preY.push(y2);
                                                                        return;
                                                                }
                                                        }
                                                }
                                        }
                                        else
                                        if(d3 > curve_collinearity_epsilon)
                                        {
                                                // p1,p2,p4 are collinear, p3 is considerable
                                                //----------------------
                                                if(d3 * d3 <= m_distance_tolerance * (dx*dx + dy*dy))
                                                {
                                                        if(m_angle_tolerance < curve_angle_tolerance_epsilon)
                                                        {
                                                                _preX.push(x1234);
                                                                _preY.push(y1234);
                                                                return;
                                                        }
   
                                                        // Angle Condition
                                                        //----------------------
                                                        da1 = Math.abs(Math.atan(y4 - y3, x4 - x3) - Math.atan(y3 - y2, x3 - x2));
                                                        if(da1 >= Math.PI) da1 = 2*Math.PI - da1;
   
                                                        if(da1 < m_angle_tolerance)
                                                        {
                                                                _preX.push(x2);
                                                                _preY.push(y2);
                                                                _preX.push(x3);
                                                                _preY.push(y3);
                                                                return;
                                                        }
   
                                                        if(m_cusp_limit != 0.0)
                                                        {
                                                                if(da1 > m_cusp_limit)
                                                                {
                                                                        _preX.push(x3);
                                                                        _preY.push(y3);
                                                                        return;
                                                                }
                                                        }
                                                }
                                        }
                                        else
                                        {
                                                // Collinear case
                                                //-----------------
                                                dx = x1234 - (x1 + x4) / 2;
                                                dy = y1234 - (y1 + y4) / 2;
                                                if(dx*dx + dy*dy <= m_distance_tolerance)
                                                {
                                                        _preX.push(x1234);
                                                        _preY.push(y1234);
                                                        return;
                                                }
                                        }
                                }
                        }
   
                        // Continue subdivision
                        //----------------------
                        CalculateMethod5(_preX, _preY, x1, y1, x12, y12, x123, y123, x1234, y1234, m_distance_tolerance, m_angle_tolerance , curve_collinearity_epsilon, curve_angle_tolerance_epsilon, m_cusp_limit, curve_recursion_limit, level + 1);
                        CalculateMethod5(_preX, _preY, x1234, y1234, x234, y234, x34, y34, x4, y4, m_distance_tolerance, m_angle_tolerance , curve_collinearity_epsilon, curve_angle_tolerance_epsilon, m_cusp_limit, curve_recursion_limit, level + 1);
                }
               
                function CalculateMethod6(_preX, _preY, x1, y1, x2, y2, x3, y3, x4, y4, deltaHalf, deltaDouble, INITIAL_NUM_STEPS)
        {
                var dx1 = x2 - x1;
                var dy1 = y2 - y1;
                var dx2 = x3 - x2;
                var dy2 = y3 - y2;
                var dx3 = x4 - x3;
                var dy3 = y4 - y3;
   
                var subdiv_step  = 1.0 / (INITIAL_NUM_STEPS + 1);
                var subdiv_step2 = subdiv_step*subdiv_step;
                var subdiv_step3 = subdiv_step*subdiv_step*subdiv_step;
   
                var pre1 = 3.0 * subdiv_step;
                var pre2 = 3.0 * subdiv_step2;
                var pre4 = 6.0 * subdiv_step2;
                var pre5 = 6.0 * subdiv_step3;
   
                var tmp1x = x1 - x2 * 2.0 + x3;
                var tmp1y = y1 - y2 * 2.0 + y3;
   
                var tmp2x = (x2 - x3)*3.0 - x1 + x4;
                var tmp2y = (y2 - y3)*3.0 - y1 + y4;
   
                var fx = x1;
                var fy = y1;
   
                var dfx = (x2 - x1)*pre1 + tmp1x*pre2 + tmp2x*subdiv_step3;
                var dfy = (y2 - y1)*pre1 + tmp1y*pre2 + tmp2y*subdiv_step3;
   
                var ddfx = tmp1x*pre4 + tmp2x*pre5;
                var ddfy = tmp1y*pre4 + tmp2y*pre5;
   
                var dddfx = tmp2x*pre5;
                var dddfy = tmp2y*pre5;
   
                var step = INITIAL_NUM_STEPS;
                var stopd=Math.round((x4 - x1)*(x4 - x1) + (y4 - y1)*(y4 - y1));
               
                while(stopd>10)
                {
                       
                        //ModifyStepSize
                        var d=(dfx*dfx + dfy*dfy);
                        if(d> deltaHalf){ //do half step size
                                dfx = (0.5*dfx)-(ddfx*1/8)+(dddfx*1/16);
                                dfy = (0.5*dfy)-(ddfy*1/8)+(dddfy*1/16);
                                ddfx = (0.25*ddfx) -(dddfx*1/8);
                                ddfy = (0.25*ddfy) -(dddfy*1/8);
                                dddfx = (dddfx*1/8);
                                dddfy = (dddfy*1/8);
                        }else if(d< deltaDouble){//do double step size
                                dfx = (2*dfx)+ddfx;
                                dfy = (2*dfy)+ddfy;
                                ddfx = (4*ddfx) +(dddfx*4);
                                ddfy = (4*ddfy) +(dddfy*4);
                                dddfx = dddfx*8;
                                dddfy = dddfy*8;
                        }
                       
                        fx   += dfx;
                        fy   += dfy;
                        dfx  += ddfx;
                        dfy  += ddfy;
                        ddfx += dddfx;
                        ddfy += dddfy;
                        _preX.push(fx);
                        _preY.push(fy);
                       
                        stopd=Math.round((x4 - fx)*(x4 - fx) + (y4 - fy)*(y4 - fy));
                                               
                }
               
        }
               
                function DrawMethod1(x1, y1, x2, y2, x3, y3, x4, y4, NUM_STEPS)
                {
                        //Calculate
                        var _calculatedLineX = [];
                        var _calculatedLineY = [];
                        CalculateMethod1(_calculatedLineX, _calculatedLineY, x1, y1, x2, y2, x3, y3, x4, y4, NUM_STEPS)                
               
                }
               
                function DrawMethod2(x1, y1, x2, y2, x3, y3, x4, y4, NUM_STEPS)
                {
                        //Calculate
                        var _calculatedLineX = [];
                        var _calculatedLineY = [];
                        CalculateMethod2(_calculatedLineX, _calculatedLineY, x1, y1, x2, y2, x3, y3, x4, y4, NUM_STEPS)
                       
                }
               
                function DrawMethod3(x1, y1, x2, y2, x3, y3, x4, y4)
                {
                        //Calculate
                        var _calculatedLineX = [];
                        var _calculatedLineY = [];
                        CalculateMethod3(_calculatedLineX, _calculatedLineY, x1, y1, x2, y2, x3, y3, x4, y4)
                       
                }
               
                function DrawMethod4(x1, y1, x2, y2, x3, y3, x4, y4, m_distance_tolerance)
                {
                        //Calculate
                        var _calculatedLineX = [];
                        var _calculatedLineY = [];
                        CalculateMethod4(_calculatedLineX, _calculatedLineY, x1, y1, x2, y2, x3, y3, x4, y4, m_distance_tolerance)                     
                       
                }
               
                function DrawMethod5(x1, y1, x2, y2, x3, y3, x4, y4, m_distance_tolerance, m_angle_tolerance , curve_collinearity_epsilon, curve_angle_tolerance_epsilon, m_cusp_limit, curve_recursion_limit)
                {
                        //Calculate
                        var _calculatedLineX = [];
                        var _calculatedLineY = [];
                        CalculateMethod5(_calculatedLineX, _calculatedLineY, x1, y1, x2, y2, x3, y3, x4, y4, m_distance_tolerance, m_angle_tolerance , curve_collinearity_epsilon, curve_angle_tolerance_epsilon, m_cusp_limit, curve_recursion_limit, 0)
                       
                }
               
                function DrawMethod6(x1, y1, x2, y2, x3, y3, x4, y4, deltaHalf, deltaDouble, INITIAL_NUM_STEPS)
                {
                        //Calculate
                        var _calculatedLineX = [];
                        var _calculatedLineY = [];
                        CalculateMethod6(_calculatedLineX, _calculatedLineY, x1, y1, x2, y2, x3, y3, x4, y4, deltaHalf, deltaDouble, INITIAL_NUM_STEPS)
                       
                }
};
</script>

Preparation code output

Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in unknown unknown
Test Ops/sec
Brute Force
DrawMethod1(188, 130, 140, 10, 388, 10, 388, 170, 100);
pending…
Optimized Forward Difference
DrawMethod2(188, 130, 140, 10, 388, 10, 388, 170, 100);
pending…
Dynamic Number of Steps
DrawMethod3(188, 130, 140, 10, 388, 10, 388, 170);
pending…
De Casteljau Subdivision
DrawMethod4(188, 130, 140, 10, 388, 10, 388, 170, 0.03);
pending…
De Casteljau Subdivion With More Handling
DrawMethod5(188, 130, 140, 10, 388, 10, 388, 170, 0.03, 0.26, 0.00001, 0.01, 0.05, 10000);
pending…
Adaptive Forward Difference
DrawMethod6(188, 130, 140, 10, 388, 10, 388, 170, 15, 10, 50);
pending…

You can edit these tests or add even more tests to this page by appending /edit to the URL.

Compare results of other browsers

0 comments

Add a comment