Auxiliary bitmap manipulations. More...

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include "potracelib.h"
#include "curve.h"
#include "lists.h"
#include "auxiliary.h"
#include "bitmap.h"
#include "decompose.h"

Include dependency graph for decompose.c:

Go to the source code of this file.

Data Structures
struct	bbox_s
Typedefs
typedef struct bbox_s	bbox_t
Functions
static void	bm_clearexcess (potrace_bitmap_t *bm)
	Set the excess padding to 0.
static void	clear_bm_with_bbox (potrace_bitmap_t bm, bbox_t bbox)
	Clear the bm, assuming the bounding box is set correctly.
static int	detrand (int x, int y)
	Deterministically and efficiently hash (x,y) into a pseudo- random bit.
static int	majority (potrace_bitmap_t *bm, int x, int y)
	Return the "majority" value of bitmap bm at intersection (x,y).
static void	xor_to_ref (potrace_bitmap_t *bm, int x, int y, int xa)
	Efficiently invert bits [x,infty) and [xa,infty) in line y.
static void	xor_path (potrace_bitmap_t bm, path_t p)
	xor the given pixmap with the interior of the given path.
static void	setbbox_path (bbox_t bbox, path_t p)
	Find the bounding box of a given path.
static path_t *	findpath (potrace_bitmap_t *bm, int x0, int y0, int sign, int turnpolicy)
	Compute a path in the given pixmap, separating black from white.
static void	pathlist_to_tree (path_t plist, potrace_bitmap_t bm)
	Give a tree structure to the given path list, based on "insideness" testing.
static int	findnext (potrace_bitmap_t bm, int xp, int *yp)
	Find the next set pixel in a row <= y.
int	bm_to_pathlist (const potrace_bitmap_t bm, path_t plistp, const potrace_param_t param)
	Decompose the given bitmap into paths.

Detailed Description

Auxiliary bitmap manipulations.

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 decompose.c.

Typedef Documentation

typedef struct bbox_s bbox_t

Definition at line 56 of file decompose.c.

Function Documentation

static void bm_clearexcess ( potrace_bitmap_t * bm ) [static]

Set the excess padding to 0.

Definition at line 37 of file decompose.c.

References BM_ALLBITS, bm_index, BM_WORDBITS, potrace_bitmap_s::h, potrace_bitmap_s::w, and y.

Referenced by bm_to_pathlist().

int bm_to_pathlist	(	const potrace_bitmap_t *	bm,
		path_t **	plistp,
		const potrace_param_t *	param
	)

Decompose the given bitmap into paths.

Returns a linked list of path_t objects with the fields len, pt, area, sign filled in.

Returns:: 0 on success with plistp set, or -1 on error with errno set.

Definition at line 578 of file decompose.c.

References potrace_path_s::area, bm_clearexcess(), bm_dup(), bm_free(), BM_GET, error, findnext(), findpath(), potrace_bitmap_s::h, list_forall_unlink, list_insert_beforehook, path_free(), pathlist_to_tree(), sign, potrace_param_s::turdsize, potrace_param_s::turnpolicy, x, xor_path(), and y.

Referenced by gcode_do_export().

Here is the call graph for this function:

static void clear_bm_with_bbox	(	potrace_bitmap_t *	bm,
		bbox_t *	bbox
	)		`[static]`

Clear the bm, assuming the bounding box is set correctly.

This is faster than clearing the whole bitmap.

Definition at line 64 of file decompose.c.

References bm_scanline, BM_WORDBITS, bbox_s::x0, bbox_s::x1, y, bbox_s::y0, and bbox_s::y1.

Referenced by pathlist_to_tree().

static int detrand	(	int	x,
		int	y
	)		`[inline, static]`

Deterministically and efficiently hash (x,y) into a pseudo- random bit.

Definition at line 87 of file decompose.c.

References x.

Referenced by findpath().

static int findnext	(	potrace_bitmap_t *	bm,
		int *	xp,
		int *	yp
	)		`[static]`

Find the next set pixel in a row <= y.

Pixels are searched first left-to-right, then top-down. In other words, (x,y)<(x',y') if y>y' or y=y' and x<x'. If found, return 0 and store pixel in (*xp,*yp). Else return 1.

Note:: This function assumes that excess bytes have been cleared with bm_clearexcess.

Definition at line 543 of file decompose.c.

References BM_GET, bm_index, BM_WORDBITS, potrace_bitmap_s::w, x, and y.

Referenced by bm_to_pathlist().

static path_t* findpath	(	potrace_bitmap_t *	bm,
		int	x0,
		int	y0,
		int	sign,
		int	turnpolicy
	)		`[static]`

Compute a path in the given pixmap, separating black from white.

Start path at the point (x0,x1), which must be an upper left corner of the path. Also compute the area enclosed by the path. Return a new path_t object, or NULL on error (note that a legitimate path cannot have length 0). Sign is required for correct interpretation of turnpolicies.

Definition at line 274 of file decompose.c.

References potrace_path_s::area, BM_GET, c, detrand(), error, potrace_privpath_s::len, len, majority(), path_new(), POTRACE_TURNPOLICY_BLACK, POTRACE_TURNPOLICY_MAJORITY, POTRACE_TURNPOLICY_MINORITY, POTRACE_TURNPOLICY_RANDOM, POTRACE_TURNPOLICY_RIGHT, POTRACE_TURNPOLICY_WHITE, potrace_path_s::priv, potrace_privpath_s::pt, realloc(), sign, potrace_path_s::sign, point_s::x, x, bbox_s::x0, point_s::y, y, and bbox_s::y0.

Referenced by bm_to_pathlist().

Here is the call graph for this function:

static int majority	(	potrace_bitmap_t *	bm,
		int	x,
		int	y
	)		`[static]`

Return the "majority" value of bitmap bm at intersection (x,y).

We assume that the bitmap is balanced at "radius" 1.

Definition at line 122 of file decompose.c.

References BM_GET.

Referenced by findpath().

static void pathlist_to_tree	(	path_t *	plist,
		potrace_bitmap_t *	bm
	)		`[static]`

Give a tree structure to the given path list, based on "insideness" testing.

I.e., path A is considered "below" path B if it is inside path B. The input pathlist is assumed to be ordered so that "outer" paths occur before "inner" paths. The tree structure is stored in the "childlist" and "sibling" components of the path_t structure. The linked list structure is also changed so that negative path components are listed immediately after their positive parent.

Note:: Some backends may ignore the tree structure, others may use it e.g. to group path components. We assume that in the input, point 0 of each path is an "upper left" corner of the path, as returned by bm_to_pathlist. This makes it easy to find an "interior" point. The bm argument should be a bitmap of the correct size (large enough to hold all the paths), and will be used as scratch space.

Returns:: 0 on success or -1 on error with errno set.

Definition at line 400 of file decompose.c.

References bm_clear(), BM_GET, potrace_path_s::childlist, clear_bm_with_bbox(), list_append, list_forall, list_forall_unlink, list_insert_beforehook, potrace_path_s::next, potrace_path_s::priv, potrace_privpath_s::pt, setbbox_path(), potrace_path_s::sibling, point_s::x, xor_path(), point_s::y, and bbox_s::y0.

Referenced by bm_to_pathlist().

Here is the call graph for this function:

static void setbbox_path	(	bbox_t *	bbox,
		path_t *	p
	)		`[static]`

Find the bounding box of a given path.

Path is assumed to be of non-zero length.

Definition at line 229 of file decompose.c.

References potrace_privpath_s::len, potrace_path_s::priv, potrace_privpath_s::pt, point_s::x, x, bbox_s::x0, bbox_s::x1, point_s::y, y, bbox_s::y0, and bbox_s::y1.

Referenced by pathlist_to_tree().

static void xor_path	(	potrace_bitmap_t *	bm,
		path_t *	p
	)		`[static]`

xor the given pixmap with the interior of the given path.

A path is represented as an array of points, which are thought to lie on the corners of pixels (not on their centers). The path point (x,y) is the lower left corner of the pixel (x,y). Paths are represented by the len/pt components of a path_t object (which also stores other information about the path).