geom.cpp revision 67f99662f87c33667b30388bfa111a7ff93d2ef4
/*
* Specific geometry functions for Inkscape, not provided my lib2geom.
*
* Author:
* Johan Engelen <goejendaagh@zonnet.nl>
*
* Copyright (C) 2008 Johan Engelen
*
* Released under GNU GPL
*/
#include <algorithm>
#include "helper/geom-curves.h"
#include <typeinfo>
#include <math.h> // for M_PI
using Geom::X;
using Geom::Y;
//#################################################################################
// BOUNDING BOX CALCULATIONS
/* 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)
{
// It already contains (x000,y000) and (x111,y111)
// All points of the Bezier lie in the convex hull of (x000,y000), (x001,y001), (x011,y011) and (x111,y111)
// So, if it also contains (x001,y001) and (x011,y011) we don't have to compute anything else!
// Note that we compute it for the X and Y range separately to make it easier to use them below
/*
* 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)
*/
if (!containsXrange) {
/*
* s = (-b +/- sqrt (b * b - 4 * a * c)) / 2 * a;
*/
/* s = -c / b */
double s;
s = -c / b;
if ((s > 0.0) && (s < 1.0)) {
double t = 1.0 - s;
}
}
} else {
/* s = (-b +/- sqrt (b * b - 4 * a * c)) / 2 * a; */
D = b * b - 4 * a * c;
if (D >= 0.0) {
/* Have solution */
d = sqrt (D);
s = (-b + d) / (2 * a);
if ((s > 0.0) && (s < 1.0)) {
t = 1.0 - s;
}
s = (-b - d) / (2 * a);
if ((s > 0.0) && (s < 1.0)) {
t = 1.0 - s;
}
}
}
}
if (!containsYrange) {
/* s = -c / b */
double s;
s = -c / b;
if ((s > 0.0) && (s < 1.0)) {
double t = 1.0 - s;
}
}
} else {
/* s = (-b +/- sqrt (b * b - 4 * a * c)) / 2 * a; */
D = b * b - 4 * a * c;
if (D >= 0.0) {
/* Have solution */
d = sqrt (D);
s = (-b + d) / (2 * a);
if ((s > 0.0) && (s < 1.0)) {
t = 1.0 - s;
}
s = (-b - d) / (2 * a);
if ((s > 0.0) && (s < 1.0)) {
t = 1.0 - s;
}
}
}
}
}
{
// return Geom::bounds_fast(pv * t);
}
{
// don't loop including closing segment, since that segment can never increase the bbox
if( is_straight_curve(c) )
{
}
{
bbox );
}
else
{
// should handle all not-so-easy curves:
delete ctemp;
}
}
}
//return Geom::bounds_exact(pv * t);
return bbox;
}
static void
geom_line_wind_distance (Geom::Coord x0, Geom::Coord y0, Geom::Coord x1, Geom::Coord y1, Geom::Point const &pt, int *wind, Geom::Coord *best)
{
/* Find distance */
if (best) {
if (s <= 0.0) {
} else if (s >= 1.0) {
} else {
}
}
if (wind) {
/* Find wind */
/* Ctach upper y bound */
return;
return;
} else {
/* Have to calculate intersection */
}
}
}
}
static void
{
needdist = 0;
needwind = 0;
needline = 0;
if (best) {
/* Quickly adjust to endpoints */
/* Point is inside sloppy bbox */
/* Now we have to decide, whether subdivide */
/* fixme: (Lauris) */
needdist = 1;
} else {
needline = 1;
}
}
}
/* Possible intersection at the left */
/* Now we have to decide, whether subdivide */
/* fixme: (Lauris) */
needwind = 1;
} else {
needline = 1;
}
}
}
t = 0.5;
s = 1 - t;
geom_cubic_bbox_wind_distance (x000, y000, x00t, y00t, x0tt, y0tt, xttt, yttt, pt, NULL, wind, best, tolerance);
geom_cubic_bbox_wind_distance (xttt, yttt, x1tt, y1tt, x11t, y11t, x111, y111, pt, NULL, wind, best, tolerance);
} else if (1 || needline) {
}
}
static void
Geom::Point &p0) // pass p0 through as it represents the last endpoint added (the finalPoint of last curve)
{
if( is_straight_curve(c) )
{
if (bbox) {
}
if (wind) { // we need to pick fill, so do what we're told
} else { // only stroke is being picked; skip this segment if it's totally outside the viewbox
}
}
}
// get approximate bbox from handles (convex hull property of beziers):
pt,
} else {
if (wind) { // if we need fill, we can just pretend it's a straight line
} else { // otherwise, skip it completely
}
}
} else {
//this case handles sbasis as well as all other curve types
//recurse to convert the new path resulting from the sbasis to svgd
}
}
}
/* Calculates...
and returns ... in *wind and the distance to ... in *dist.
Returns bounding box in *bbox if bbox!=NULL.
*/
void
pathv_matrix_point_bbox_wind_distance (Geom::PathVector const & pathv, Geom::Affine const &m, Geom::Point const &pt,
{
return;
}
// remember last point of last curve
// remembering the start of subpath
bool start_set = false;
if (start_set) { // this is a new subpath
}
start_set = true;
if (bbox) {
}
// loop including closing segment if path is closed
}
}
if (start_set) {
}
}
//#################################################################################
/*
* Converts all segments in all paths to Geom::LineSegment or Geom::HLineSegment or
* Geom::VLineSegment or Geom::CubicBezier.
*/
{
if (is_straight_curve(*cit)) {
} else {
} else {
// convert all other curve types to cubicbeziers
}
}
}
}
return output;
}
/*
* Converts all segments in all paths to Geom::LineSegment. There is an intermediate
* stage where some may be converted to beziers. maxdisp is the maximum displacement from
* the line segment to the bezier curve; ** maxdisp is not used at this moment **.
*
* This is NOT a terribly fast method, but it should give a solution close to the one with the
* fewest points.
*/
{
// Now all path segments are either already lines, or they are beziers.
if (is_straight_curve(*cit)) {
}
else { /* all others must be Bezier curves */
A[X], A[Y],
B[X], B[Y],
C[X], C[Y],
D[X], D[Y],
0);
}
}
}
}
return output;
}
// The next routine is modified from curv4_div::recursive_bezier from file agg_curves.cpp
//----------------------------------------------------------------------------
// Anti-Grain Geometry (AGG) - Version 2.5
// A high quality rendering engine for C++
// Copyright (C) 2002-2006 Maxim Shemanarev
// Contact: mcseem@antigrain.com
// mcseemagg@yahoo.com
//
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// AGG is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with AGG; if not, write to the Free Software
// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
// MA 02110-1301, USA.
//----------------------------------------------------------------------------
void
int level)
{
// some of these should be parameters, but do it this way for now.
const double curve_collinearity_epsilon = 1e-30;
const double curve_angle_tolerance_epsilon = 0.01;
double m_cusp_limit = 0.0;
double m_angle_tolerance = 0.0;
double m_approximation_scale = 1.0;
#define calc_sq_distance(A,B,C,D) ((A-C)*(A-C) + (B-D)*(B-D))
if(level > curve_recursion_limit)
{
return;
}
// Calculate all the mid-points of the line segments
//----------------------
// Try to approximate the full cubic curve by a single straight line
//------------------
int(d3 > curve_collinearity_epsilon))
{
case 0:
// All collinear OR p1==p4
//----------------------
if(k == 0)
{
}
else
{
k = 1 / k;
{
// Simple collinear case, 1---2---3---4
// We can leave just two endpoints
return;
}
}
{
{
return;
}
}
else
{
{
return;
}
}
break;
case 1:
// p1,p2,p4 are collinear, p3 is significant
//----------------------
{
{
return;
}
// Angle Condition
//----------------------
if(da1 < m_angle_tolerance)
{
return;
}
if(m_cusp_limit != 0.0)
{
if(da1 > m_cusp_limit)
{
return;
}
}
}
break;
case 2:
// p1,p3,p4 are collinear, p2 is significant
//----------------------
{
{
return;
}
// Angle Condition
//----------------------
if(da1 < m_angle_tolerance)
{
return;
}
if(m_cusp_limit != 0.0)
{
if(da1 > m_cusp_limit)
{
return;
}
}
}
break;
case 3:
// Regular case
//-----------------
{
// If the curvature doesn't exceed the distance_tolerance value
// we tend to finish subdivisions.
//----------------------
{
return;
}
// Angle & Cusp Condition
//----------------------
{
// Finally we can stop the recursion
//----------------------
return;
}
if(m_cusp_limit != 0.0)
{
if(da1 > m_cusp_limit)
{
return;
}
if(da2 > m_cusp_limit)
{
return;
}
}
}
break;
}
// Continue subdivision
//----------------------
}
/**
* rounds all corners of the rectangle 'outwards', i.e. x0 and y0 are floored, x1 and y1 are ceiled.
*/
for (int i=0; i < 2; i++) {
}
}
namespace Geom {
return
}
}
}
} //end namespace Geom
/*
Local Variables:
mode:c++
c-file-style:"stroustrup"
c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
indent-tabs-mode:nil
fill-column:99
End:
*/
// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :