Transform jaggy paths into smooth curves. More...

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include "global.h"
#include "potracelib.h"
#include "curve.h"
#include "lists.h"
#include "auxiliary.h"
#include "trace.h"
#include "pcb-printf.h"

Include dependency graph for trace.c:

Go to the source code of this file.

Data Structures
struct	opti_s
	A private type for the result of opti_penalty. More...
Defines
#define	INFTY 10000000
	It suffices that this is longer than any path; it need not be really infinite.
#define	COS179 -0.999847695156
	The cosine of 179 degrees.
#define	SAFE_MALLOC(var, n, typ) if ((var = (typ )malloc((n)sizeof(typ))) == NULL) goto malloc_error
#define	TRY(x) if (x) goto try_error
Typedefs
typedef double	quadform_t [3][3]
	The type of (affine) quadratic forms, represented as symmetric 3x3 matrices.
typedef struct opti_s	opti_t
Functions
static point_t	dorth_infty (dpoint_t p0, dpoint_t p2)
	Return a direction that is 90 degrees counterclockwise from p2-p0, but then restricted to one of the major wind directions (n, nw, w, etc).
static double	dpara (dpoint_t p0, dpoint_t p1, dpoint_t p2)
	Return (p1-p0)x(p2-p0), the area of the parallelogram.
static double	ddenom (dpoint_t p0, dpoint_t p2)
	ddenom/dpara have the property that the square of radius 1 centered at p1 intersects the line p0p2 if \|dpara(p0,p1,p2)\| <= ddenom(p0,p2).
static int	cyclic (int a, int b, int c)
	Return 1 if a <= b < c < a, in a cyclic sense (mod n).
static void	pointslope (privpath_t pp, int i, int j, dpoint_t ctr, dpoint_t *dir)
	Determine the center and slope of the line i..j.
static double	quadform (quadform_t Q, dpoint_t w)
	Apply quadratic form Q to vector w = (w.x,w.y).
static int	xprod (point_t p1, point_t p2)
	Calculate p1 x p2.
static double	cprod (dpoint_t p0, dpoint_t p1, dpoint_t p2, dpoint_t p3)
	Calculate (p1-p0)x(p3-p2).
static double	iprod (dpoint_t p0, dpoint_t p1, dpoint_t p2)
	Calculate (p1-p0)*(p2-p0).
static double	iprod1 (dpoint_t p0, dpoint_t p1, dpoint_t p2, dpoint_t p3)
	Calculate (p1-p0)*(p3-p2).
static double	ddist (dpoint_t p, dpoint_t q)
	Calculate distance between two points.
static dpoint_t	bezier (double t, dpoint_t p0, dpoint_t p1, dpoint_t p2, dpoint_t p3)
	Calculate point of a bezier curve.
static double	tangent (dpoint_t p0, dpoint_t p1, dpoint_t p2, dpoint_t p3, dpoint_t q0, dpoint_t q1)
	Calculate the point t in [0..1] on the (convex) bezier curve (p0,p1,p2,p3) which is tangent to q1-q0.
static int	calc_sums (privpath_t *pp)
	Preparation: fill in the sum* fields of a path (used for later rapid summing).
static int	calc_lon (privpath_t *pp)
	Stage 1: Determine the straight subpaths (Sec. 2.2.1).
static double	penalty3 (privpath_t *pp, int i, int j)
	Stage 2: Calculate the optimal polygon (Sec. 2.2.2-2.2.4).
static int	bestpolygon (privpath_t *pp)
	Find the optimal polygon.
static int	adjust_vertices (privpath_t *pp)
	Stage 3: Vertex adjustment (Sec. 2.3.1).
static int ATTRIBUTE_UNUSED	smooth (privcurve_t *curve, int sign, double alphamax)
	Stage 4: Smoothing and corner analysis (Sec. 2.3.3).
static int	opti_penalty (privpath_t pp, int i, int j, opti_t res, double opttolerance, int convc, double areac)
	Calculate best fit from i+.5 to j+.5.
static int ATTRIBUTE_UNUSED	opticurve (privpath_t *pp, double opttolerance)
	Optimize the path p, replacing sequences of Bezier segments by a single segment when possible.
double	plotpolygon (privpath_t pp, FILE f, double scale, const char var_cutdepth, const char var_safeZ, const char var_plunge, const char var_feedrate)
double	process_path (path_t plist, const potrace_param_t param, const potrace_bitmap_t bm, FILE f, double scale, const char var_cutdepth, const char var_safeZ, const char var_plunge, const char var_feedrate)
	Process path.

Detailed Description

Transform jaggy paths into smooth curves.

This file was slightly modified by Alberto Maccioni to be used with PCB G-CODE exporter.

Copyright.

PCB, interactive printed circuit board design

This file is part of Potrace. It is free software and it is covered by the GNU General Public License. See the file COPYING for details.

Definition in file trace.c.

Define Documentation

#define COS179 -0.999847695156

The cosine of 179 degrees.

Definition at line 44 of file trace.c.

Referenced by opti_penalty().

#define INFTY 10000000

It suffices that this is longer than any path; it need not be really infinite.

Definition at line 40 of file trace.c.

Referenced by calc_lon().

#define SAFE_MALLOC	(	var,
		n,
		typ
	)	if ((var = (typ )malloc((n)sizeof(typ))) == NULL) goto malloc_error

Definition at line 47 of file trace.c.

Referenced by adjust_vertices(), bestpolygon(), calc_lon(), calc_sums(), and opticurve().

#define TRY ( x ) if (x) goto try_error

Definition at line 1515 of file trace.c.

Referenced by process_path().

Typedef Documentation

typedef struct opti_s opti_t

Definition at line 1126 of file trace.c.

typedef double quadform_t[3][3]

The type of (affine) quadratic forms, represented as symmetric 3x3 matrices.

The value of the quadratic form at a vector (x,y) is v^t Q v, where v = (x,y,1)^t.

Definition at line 205 of file trace.c.

Function Documentation

static int adjust_vertices ( privpath_t * pp ) [static]

Stage 3: Vertex adjustment (Sec. 2.3.1).

Adjust vertices of optimal polygon: calculate the intersection of the two "optimal" line segments, then move it into the unit square if it lies outside.

Returns:: 1 with errno set on error; 0 on success.

Definition at line 803 of file trace.c.

References corners, potrace_privpath_s::curve, det(), potrace_privpath_s::len, potrace_privpath_s::m, m, min, mod(), n, potrace_privpath_s::po, pointslope(), privcurve_init(), potrace_privpath_s::pt, quadform(), s, SAFE_MALLOC, sq, privcurve_s::vertex, point_s::x, potrace_dpoint_s::x, x, potrace_privpath_s::x0, point_s::y, potrace_dpoint_s::y, y, and potrace_privpath_s::y0.

Referenced by process_path().

Here is the call graph for this function:

static int bestpolygon ( privpath_t * pp ) [static]

Find the optimal polygon.

Fill in the m and po components.

Non-cyclic version: assumes i=0 is in the polygon.

Todo:: Implement cyclic version.

Returns:: 1 on failure with errno set, else 0.

Definition at line 672 of file trace.c.

References c, potrace_privpath_s::len, potrace_privpath_s::lon, potrace_privpath_s::m, m, mod(), n, penalty3(), potrace_privpath_s::po, and SAFE_MALLOC.

Referenced by process_path().

Here is the call graph for this function:

static dpoint_t bezier	(	double	t,
		dpoint_t	p0,
		dpoint_t	p1,
		dpoint_t	p2,
		dpoint_t	p3
	)		`[inline, static]`

Calculate point of a bezier curve.

Definition at line 302 of file trace.c.

References s, potrace_dpoint_s::x, and potrace_dpoint_s::y.

Referenced by opti_penalty().

static int calc_lon ( privpath_t * pp ) [static]

Stage 1: Determine the straight subpaths (Sec. 2.2.1).

Fill in the "lon" component of a path object (based on pt/len). For each i, lon[i] is the furthest index such that a straight line can be drawn from i to lon[i].

This algorithm depends on the fact that the existence of straight subpaths is a triplewise property. I.e., there exists a straight line through squares i0,...,in iff there exists a straight line through i,j,k, for all i0<=i<j<k<=in. (Proof?).

This implementation of calc_lon is O(n^2). It replaces an older O(n^3) version. A "constraint" means that future points must satisfy xprod(constraint[0], cur) >= 0 and xprod(constraint[1], cur) <= 0.

Note:: Remark for Potrace 1.1: the current implementation of calc_lon is more complex than the implementation found in Potrace 1.0, but it is considerably faster. The introduction of the "nc" data structure means that we only have to test the constraints for "corner" points. On a typical input file, this speeds up the calc_lon function by a factor of 31.2, thereby decreasing its time share within the overall Potrace algorithm from 72.6% to 7.82%, and speeding up the overall algorithm by a factor of 3.36. On another input file, calc_lon was sped up by a factor of 6.7, decreasing its time share from 51.4% to 13.61%, and speeding up the overall algorithm by a factor of 1.78. In any case, the savings are substantial.

Returns:: 1 on error with errno set, else 0.

Definition at line 439 of file trace.c.

References abs, c, cyclic(), floordiv(), INFTY, potrace_privpath_s::len, potrace_privpath_s::lon, min, mod(), n, potrace_privpath_s::pt, SAFE_MALLOC, sign, point_s::x, x, xprod(), point_s::y, and y.

Referenced by process_path().

Here is the call graph for this function:

static int calc_sums ( privpath_t * pp ) [static]

Preparation: fill in the sum* fields of a path (used for later rapid summing).

Returns:: 0 on success, 1 with errno set on failure.

Definition at line 376 of file trace.c.

References potrace_privpath_s::len, n, potrace_privpath_s::pt, SAFE_MALLOC, potrace_privpath_s::sums, sums_s::x, point_s::x, x, potrace_privpath_s::x0, sums_s::x2, sums_s::xy, sums_s::y, point_s::y, y, potrace_privpath_s::y0, and sums_s::y2.

Referenced by process_path().

static double cprod	(	dpoint_t	p0,
		dpoint_t	p1,
		dpoint_t	p2,
		dpoint_t	p3
	)		`[inline, static]`

Calculate (p1-p0)x(p3-p2).

Definition at line 245 of file trace.c.

References potrace_dpoint_s::x, and potrace_dpoint_s::y.

Referenced by opti_penalty(), and tangent().

static int cyclic	(	int	a,
		int	b,
		int	c
	)		`[inline, static]`

Return 1 if a <= b < c < a, in a cyclic sense (mod n).

Definition at line 102 of file trace.c.

Referenced by calc_lon().

static double ddenom	(	dpoint_t	p0,
		dpoint_t	p2
	)		`[inline, static]`

ddenom/dpara have the property that the square of radius 1 centered at p1 intersects the line p0p2 if |dpara(p0,p1,p2)| <= ddenom(p0,p2).

Definition at line 91 of file trace.c.

References dorth_infty(), point_s::x, potrace_dpoint_s::x, potrace_dpoint_s::y, and point_s::y.

Referenced by smooth().

Here is the call graph for this function:

static double ddist	(	dpoint_t	p,
		dpoint_t	q
	)		`[inline, static]`

Calculate distance between two points.

Definition at line 293 of file trace.c.

References potrace_dpoint_s::x, and potrace_dpoint_s::y.

Referenced by opti_penalty().

static point_t dorth_infty	(	dpoint_t	p0,
		dpoint_t	p2
	)		`[inline, static]`

Return a direction that is 90 degrees counterclockwise from p2-p0, but then restricted to one of the major wind directions (n, nw, w, etc).

Definition at line 59 of file trace.c.

References sign, point_s::x, potrace_dpoint_s::x, potrace_dpoint_s::y, and point_s::y.

Referenced by ddenom().

static double dpara	(	dpoint_t	p0,
		dpoint_t	p1,
		dpoint_t	p2
	)		`[inline, static]`

Return (p1-p0)x(p2-p0), the area of the parallelogram.

Definition at line 73 of file trace.c.

References potrace_dpoint_s::x, and potrace_dpoint_s::y.

Referenced by opti_penalty(), opticurve(), and smooth().

static double iprod	(	dpoint_t	p0,
		dpoint_t	p1,
		dpoint_t	p2
	)		`[inline, static]`

Calculate (p1-p0)*(p2-p0).

Definition at line 261 of file trace.c.

References potrace_dpoint_s::x, and potrace_dpoint_s::y.

Referenced by opti_penalty().

static double iprod1	(	dpoint_t	p0,
		dpoint_t	p1,
		dpoint_t	p2,
		dpoint_t	p3
	)		`[inline, static]`

Calculate (p1-p0)*(p3-p2).

Definition at line 277 of file trace.c.

References potrace_dpoint_s::x, and potrace_dpoint_s::y.

Referenced by opti_penalty().

static int opti_penalty	(	privpath_t *	pp,
		int	i,
		int	j,
		opti_t *	res,
		double	opttolerance,
		int *	convc,
		double *	areac
	)		`[static]`

Calculate best fit from i+.5 to j+.5.

Assume i<j (cyclically).

Returns:: 0 and set badness and parameters (alpha, beta), if possible. Return 1 if impossible.

Definition at line 1137 of file trace.c.

References privcurve_s::alpha, opti_s::alpha, bezier(), opti_s::c, privcurve_s::c, COS179, cprod(), potrace_privpath_s::curve, ddist(), dpara(), interval(), iprod(), iprod1(), m, mod(), privcurve_s::n, opti_s::pen, opti_s::s, s, sign, sq, opti_s::t, tangent(), and privcurve_s::vertex.

Referenced by opticurve().

Here is the call graph for this function:

static int ATTRIBUTE_UNUSED opticurve	(	privpath_t *	pp,
		double	opttolerance
	)		`[static]`

Optimize the path p, replacing sequences of Bezier segments by a single segment when possible.

Returns:: 0 on success, 1 with errno set on failure.

Definition at line 1314 of file trace.c.

References privcurve_s::alpha, opti_s::alpha, privcurve_s::alpha0, privcurve_s::alphacurve, privcurve_s::beta, opti_s::c, privcurve_s::c, potrace_privpath_s::curve, dpara(), interval(), len, m, mod(), privcurve_s::n, potrace_privpath_s::ocurve, opti_penalty(), opti_s::pen, POTRACE_CURVETO, privcurve_init(), opti_s::s, s, SAFE_MALLOC, sign, opti_s::t, privcurve_s::tag, and privcurve_s::vertex.

Here is the call graph for this function:

static double penalty3	(	privpath_t *	pp,
		int	i,
		int	j
	)		`[static]`

Stage 2: Calculate the optimal polygon (Sec. 2.2.2-2.2.4).

Auxiliary function: calculate the penalty of an edge from i to j in the given path. This needs the "lon" and "sum*" data.

Definition at line 620 of file trace.c.

References c, ex, ey, potrace_privpath_s::len, n, potrace_privpath_s::pt, px, py, s, potrace_privpath_s::sums, point_s::x, sums_s::x, x, sums_s::x2, sums_s::xy, point_s::y, sums_s::y, y, and sums_s::y2.

Referenced by bestpolygon().

double plotpolygon	(	privpath_t *	pp,
		FILE *	f,
		double	scale,
		const char *	var_cutdepth,
		const char *	var_safeZ,
		const char *	var_plunge,
		const char *	var_feedrate
	)

Definition at line 1481 of file trace.c.

References potrace_privpath_s::m, m, pcb_fprintf(), potrace_privpath_s::po, potrace_privpath_s::pt, x, and y.

Referenced by process_path().

Here is the call graph for this function:

static void pointslope	(	privpath_t *	pp,
		int	i,
		int	j,
		dpoint_t *	ctr,
		dpoint_t *	dir
	)		`[static]`

Determine the center and slope of the line i..j.

Assume i<j. Needs "sum" components of p to be set.

Definition at line 120 of file trace.c.

References c, potrace_privpath_s::len, n, potrace_privpath_s::sums, potrace_dpoint_s::x, sums_s::x, x, sums_s::x2, sums_s::xy, potrace_dpoint_s::y, sums_s::y, y, and sums_s::y2.

Referenced by adjust_vertices().

double process_path	(	path_t *	plist,
		const potrace_param_t *	param,
		const potrace_bitmap_t *	bm,
		FILE *	f,
		double	scale,
		const char *	var_cutdepth,
		const char *	var_safeZ,
		const char *	var_plunge,
		const char *	var_feedrate
	)