1ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 2ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov//---------------------------------------------------------------------------- 3ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// XYQ: 2006-01-22 Copied from AGG project. 4ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// TODO: This file uses intensive floating point operations, so it's NOT suitable 5ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// for platforms like Symbian OS. We need to change to FIX format. 6ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov//---------------------------------------------------------------------------- 7ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov//---------------------------------------------------------------------------- 8ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// Anti-Grain Geometry - Version 2.3 9ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// Copyright (C) 2002-2005 Maxim Shemanarev (http://www.antigrain.com) 10ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// 11ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// Permission to copy, use, modify, sell and distribute this software 12ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// is granted provided this copyright notice appears in all copies. 13ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// This software is provided "as is" without express or implied 14ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// warranty, and with no claim as to its suitability for any purpose. 15ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// 16ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov//---------------------------------------------------------------------------- 17ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// Contact: mcseem@antigrain.com 18ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// mcseemagg@yahoo.com 19ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// http://www.antigrain.com 20ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov//---------------------------------------------------------------------------- 21ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#include "../../../../include/fxcrt/fx_basic.h" 22ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#include "agg_curves.h" 23ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#include "agg_math.h" 24ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovnamespace agg 25ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 26ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovconst FX_FLOAT curve_collinearity_epsilon = 1e-30f; 27ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovenum curve_recursion_limit_e { curve_recursion_limit = 16 }; 28ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovvoid curve4_div::init(FX_FLOAT x1, FX_FLOAT y1, 29ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_FLOAT x2, FX_FLOAT y2, 30ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_FLOAT x3, FX_FLOAT y3, 31ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_FLOAT x4, FX_FLOAT y4) 32ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 33ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_points.remove_all(); 34ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_distance_tolerance_square = 1.0f / 4; 35ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_distance_tolerance_manhattan = 1.0f * 4; 36ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bezier(x1, y1, x2, y2, x3, y3, x4, y4); 37ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_count = 0; 38ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 39ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovvoid curve4_div::recursive_bezier(FX_FLOAT x1, FX_FLOAT y1, 40ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_FLOAT x2, FX_FLOAT y2, 41ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_FLOAT x3, FX_FLOAT y3, 42ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_FLOAT x4, FX_FLOAT y4, 43ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned level) 44ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 45ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if(level > curve_recursion_limit) { 46ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return; 47ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 48ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_FLOAT x12 = (x1 + x2) / 2; 49ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_FLOAT y12 = (y1 + y2) / 2; 50ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_FLOAT x23 = (x2 + x3) / 2; 51ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_FLOAT y23 = (y2 + y3) / 2; 52ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_FLOAT x34 = (x3 + x4) / 2; 53ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_FLOAT y34 = (y3 + y4) / 2; 54ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_FLOAT x123 = (x12 + x23) / 2; 55ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_FLOAT y123 = (y12 + y23) / 2; 56ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_FLOAT x234 = (x23 + x34) / 2; 57ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_FLOAT y234 = (y23 + y34) / 2; 58ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_FLOAT x1234 = (x123 + x234) / 2; 59ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_FLOAT y1234 = (y123 + y234) / 2; 60ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_FLOAT dx = x4 - x1; 61ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_FLOAT dy = y4 - y1; 62ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_FLOAT d2 = FXSYS_fabs(FXSYS_Mul(x2 - x4, dy) - FXSYS_Mul(y2 - y4, dx)); 63ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_FLOAT d3 = FXSYS_fabs(FXSYS_Mul(x3 - x4, dy) - FXSYS_Mul(y3 - y4, dx)); 64ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov switch((int(d2 > curve_collinearity_epsilon) << 1) + 65ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int(d3 > curve_collinearity_epsilon)) { 66ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov case 0: 67ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if(FXSYS_fabs(x1 + x3 - x2 - x2) + 68ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FXSYS_fabs(y1 + y3 - y2 - y2) + 69ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FXSYS_fabs(x2 + x4 - x3 - x3) + 70ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FXSYS_fabs(y2 + y4 - y3 - y3) <= m_distance_tolerance_manhattan) { 71ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_points.add(point_type(x1234, y1234, path_flags_jr)); 72ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return; 73ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 74ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov break; 75ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov case 1: 76ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if(FXSYS_Mul(d3, d3) <= FXSYS_Mul(m_distance_tolerance_square, 77ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FXSYS_Mul(dx, dx) + FXSYS_Mul(dy, dy))) { 78ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_points.add(point_type(x23, y23, path_flags_jr)); 79ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return; 80ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 81ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov break; 82ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov case 2: 83ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if(FXSYS_Mul(d2, d2) <= FXSYS_Mul(m_distance_tolerance_square, 84ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FXSYS_Mul(dx, dx) + FXSYS_Mul(dy, dy))) { 85ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_points.add(point_type(x23, y23, path_flags_jr)); 86ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return; 87ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 88ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov break; 89ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov case 3: 90ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if(FXSYS_Mul(d2 + d3, d2 + d3) <= FXSYS_Mul(m_distance_tolerance_square, 91ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FXSYS_Mul(dx, dx) + FXSYS_Mul(dy, dy))) { 92ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_points.add(point_type(x23, y23, path_flags_jr)); 93ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return; 94ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 95ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov break; 96ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 97ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov recursive_bezier(x1, y1, x12, y12, x123, y123, x1234, y1234, level + 1); 98ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov recursive_bezier(x1234, y1234, x234, y234, x34, y34, x4, y4, level + 1); 99ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 100ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovvoid curve4_div::bezier(FX_FLOAT x1, FX_FLOAT y1, 101ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_FLOAT x2, FX_FLOAT y2, 102ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_FLOAT x3, FX_FLOAT y3, 103ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_FLOAT x4, FX_FLOAT y4) 104ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 105ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_points.add(point_type(x1, y1)); 106ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov recursive_bezier(x1, y1, x2, y2, x3, y3, x4, y4, 0); 107ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_points.add(point_type(x4, y4)); 108ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 109ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 110