Bezier Rendering Methods

JavaScript performance comparison

Test case created by Ammar Hattab

Info

Compare Performance of Different Bezier Curves Rendering Methods

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 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)
                       
                        //Canvas
                        var canvas = document.getElementById('canvas1');
                    var context = canvas.getContext('2d');
                        GeneralDraw(context, _calculatedLineX, _calculatedLineY, x1, y1, x2, y2, x3, y3, x4, y4);
                }
               
                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)
                       
                        //Canvas
                        var canvas = document.getElementById('canvas1');
                    var context = canvas.getContext('2d');
                        GeneralDraw(context, _calculatedLineX, _calculatedLineY, x1, y1, x2, y2, x3, y3, x4, y4);
                }
               
                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)
                       
                        //Canvas
                        var canvas = document.getElementById('canvas1');
                    var context = canvas.getContext('2d');
                        GeneralDraw(context, _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)
                       
                        //Canvas
                        var canvas = document.getElementById('canvas1');
                    var context = canvas.getContext('2d');
                        GeneralDraw(context, _calculatedLineX, _calculatedLineY, x1, y1, x2, y2, x3, y3, x4, y4);
                }
               
                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)
                       
                        //Canvas
                        var canvas = document.getElementById('canvas1');
                    var context = canvas.getContext('2d');
                        GeneralDraw(context, _calculatedLineX, _calculatedLineY, x1, y1, x2, y2, x3, y3, x4, y4);
                }
               
                function GeneralDraw(context, _calculatedLineX, _calculatedLineY, x1, y1, x2, y2, x3, y3, x4, y4)
                {
                        //Draw Green Line
                        context.lineWidth = 30;
                    context.strokeStyle = 'lightgreen';            
                        context.beginPath();
                        context.moveTo(x1, y1);
                        for(i=0; i<_calculatedLineX.length; i++) {
                                context.lineTo(_calculatedLineX[i], _calculatedLineY[i]);
                        }
                        context.lineTo(x4, y4);
                        context.stroke();
                       
                        //Draw thin blue lines
                        context.lineWidth = 1;
                    context.strokeStyle = 'darkblue';              
                        context.beginPath();
                        context.moveTo(x1, y1);
                        for(i=0; i<_calculatedLineX.length; i++) {
                                context.lineTo(_calculatedLineX[i], _calculatedLineY[i]);
                        }
                        context.lineTo(x4, y4);
                        context.stroke();
                       
                        //Draw points as circles
                        context.fillStyle = 'darkblue';
                        for(i=0; i<_calculatedLineX.length; i++) {
                                context.beginPath();                   
                                context.arc(_calculatedLineX[i], _calculatedLineY[i], 1, 0, Math.PI*2, true);
                                context.closePath();
                                context.fill();                        
                        }
                       
                        context.fillStyle = 'darkblue';
                        context.beginPath();                   
                        context.arc(x1, y1, 7, 0, Math.PI*2, true);
                        context.closePath();
                        context.fill();
                       
                        context.fillStyle = 'darkblue';
                        context.beginPath();                   
                        context.arc(x4, y4, 7, 0, Math.PI*2, true);
                        context.closePath();
                        context.fill();
                       
                        context.fillStyle = 'darkgreen';
                        context.beginPath();                   
                        context.arc(x2, y2, 5, 0, Math.PI*2, true);
                        context.closePath();
                        context.fill();
                       
                        context.fillStyle = 'darkgreen';
                        context.beginPath();                   
                        context.arc(x3, y3, 5, 0, Math.PI*2, true);
                        context.closePath();
                        context.fill();                
                }
};
</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, 20);
pending…
Fast Incremental Method
DrawMethod2(188, 130, 140, 10, 388, 10, 388, 170, 20);
pending…
Dynamic Number of Steps Based on Length
DrawMethod3(188, 130, 140, 10, 388, 10, 388, 170);
pending…
de Casteljau Subdivion With Distance Approximation
DrawMethod4(188, 130, 140, 10, 388, 10, 388, 170, 0.25);
pending…
de Casteljau Subdivion With Angle Tolerance and Cusps and Collinear Handling
DrawMethod5(188, 130, 140, 10, 388, 10, 388, 170, 0.25, 0.26, 0.00001, 0.01, 0.05, 10000);
pending…

Compare results of other browsers

Revisions

You can edit these tests or add even more tests to this page by appending /edit to the URL. Here’s a list of current revisions for this page:

0 comments

Add a comment