cae-tools/cameo/ops.c

/*
 * ops.c - Higher-level toolpath operations
 *
 * Written 2010-2013, 2015 by Werner Almesberger
 * Copyright 2010-2013, 2105 Werner Almesberger
 *
 * This program is free software; you can redistribute it and/or 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.
 */


#include <stddef.h>
#include <stdbool.h>
#include <math.h>

#include "path.h"
#include "shape.h"
#include "ops.h"


static struct path *tool_comp_1(const struct path *path, int inside,
    int dog_bone)
{
	int left;

	left = path_tool_is_left(path);
	if (inside)
		return path_offset(path, !left, path->notch);
	else
		return path_offset(path, left, path->notch || dog_bone);
}


struct path *tool_comp_paths(const struct path *paths, int dog_bone,
    int all_inside)
{
	const struct path *leftmost, *path;
	struct path *new = NULL, **anchor = &new;

	/*
	 * We don't have an algorithm (yet) that can detect which paths are
	 * inside other paths. Therefore, we fake it by looking for the path
	 * that contains the lowest x coordinate. This ought to be the outer
	 * boundary of the piece.
	 *
	 * Note that this heuristic falls apart when a job consists of
	 * multiple pieces. In this case, the #%outside hint can be used to
	 * explicitly tell cameo to treat the path as an outside edge.
	 */

	if (!paths)
		return NULL;
	leftmost = path_find_leftmost(paths);
	for (path = paths; path; path = path->next)
		if (path != leftmost && (all_inside || !path->outside)) {
			*anchor = tool_comp_1(path, 1, dog_bone);
			anchor = &(*anchor)->next;
		}
	if (!all_inside)
		for (path = paths; path; path = path->next)
			if (path != leftmost && path->outside) {
				*anchor = tool_comp_1(path, 0, dog_bone);
				anchor = &(*anchor)->next;
			}
	*anchor = tool_comp_1(leftmost, all_inside, dog_bone);
	return new;
}


struct path *try_drill(struct path *path, double d_min, double d_max)
{
	struct path *new;

	if (path->r_tool*2 < d_min || path->r_tool*2 > d_max)
		return NULL;
	if (!path->first || path->first != path->last)
		return NULL;
	new = path_new((d_min+d_max)/2, path->id); /* @@@ fishy */
	path_add(new, path->first->x, path->first->y, path->first->z);
	return new;
}


struct path *try_mill(struct path *path, double diam, double step, int any)
{
	if (!any && path->r_tool*2 < diam)
		return NULL;
	if (!path->first)
		return NULL;
	if (path->first == path->last)
		return circle(path->first->x, path->first->y, path->first->z,
		    path->r_tool, diam/2, step, path->id);
	if (path->first->next == path->last)
		return slot(path->first->x, path->first->y,
		    path->first->next->x, path->first->next->y,
		    path->first->z, path->r_tool, diam/2, step, path->id);
	return NULL;
}


/*
 * This isn't a perfect solution for the traveling salesman problem, but it's
 * easy to implement and usually produces results that don't look overly
 * offensive.
 */

struct path *optimize_paths(struct path *paths)
{
	struct path **walk, **best = NULL;
	struct path *res = NULL, **anchor = &res;
	struct path *curr;
	struct point *p;
	double best_d = 0, d;

	for (walk = &paths; *walk; walk = &(*walk)->next) {
		p = (*walk)->first;
		if (!p)
			continue;
		d = hypot(p->x, p->y);
		if (!best || d  < best_d) {
			best = walk;
			best_d = d;
		}
	}
	while (best) {
		curr = *best;
		*anchor = *best;
		anchor = &curr->next;
		*best = curr->next;
		best = NULL;
		for (walk = &paths; *walk; walk = &(*walk)->next) {
			p = (*walk)->first;
			if (!p)
				continue;
			d = hypot(p->x-curr->last->x, p->y-curr->last->y);
			if (!best || d < best_d) {
				best = walk;
				best_d = d;
			}
		}
	}
	return res;
}


struct path *reverse_paths(const struct path *paths)
{
	const struct path *path;
	struct path *res = NULL, **last = &res;

	for (path = paths; path; path = path->next) {
		*last = path_reverse(path);
		last = &(*last)->next;
	}
	return res;
}


static int select_path(const struct path *path, double xa, double ya,
    double xb, double yb, int inside)
{
	const struct point *p;

	for (p = path->first; p; p = p->next) {
		if (p->x >= xa && p->x <= xb && p->y >= ya && p->y <= yb) {
			if (!inside)
				return 0;
		} else {
			if (inside)
				return 0;
		}
	}
	return 1;
}


struct path *select_paths(const struct path *paths, double xa, double ya,
    double xb, double yb, int inside)
{
	struct path *res = NULL, **last = &res;

	if (xa > xb)
		return select_paths(paths, xb, ya, xa, yb, inside);
	if (ya > yb)
		return select_paths(paths, xa, yb, xb, ya, inside);
	while (paths) {
		if (select_path(paths, xa, ya, xb, yb, inside)) {
			*last = path_clone(paths);
			last = &(*last)->next;
		}
		paths = paths->next;
	}
	return res;
}


static double cross_area(double ax, double ay, double az, double bx, double by,
    double bz)
{
	double x, y, z;

	x = ay * bz - by * az;
	y = az * bx - ax * bz;
	z = ax * by - ay * bx;
	return hypot(hypot(x, y), z);
}


struct path *purge_paths(const struct path *paths, double len)
{
	const struct path *path;
	struct path *p = NULL, **anchor = &p, *new;
	struct point *a, *b, *c;
	struct point *end;
	double area, t;
	bool closed;

	if (!len)
		len = EPSILON_PURGE;
	area = len * len;
	for (path = paths; path; path = path->next) {
		if (!path->first)
			continue;
		closed = path_is_closed(path);
		if (closed) {
			end = path->first;
			while (end->next != path->last)
				end = end->next;
		} else {
			end = path->last;
		}
		a = end;
		b = path->first;
		c = b->next;
		if (!c)
			continue;
		new = path_from(path);
		while (1) {
			t = cross_area(a->x - b->x, a->y - b->y, a->z - b->z,
			    c->x - b->x, c->y - b->y, c->z - b->z);
			if (t >= area) {
				path_add(new, b->x, b->y, b->z);
				a = b;
			}
			b = c;
			if (closed) {
				c = c == end ? path->first : c->next;
			} else {
				c = c->next;
			}
			if (b == path->first || !c)
				break;
		}
		if (new->first) {
			if (closed)
				path_add(new, new->first->x, new->first->y,
				    new->first->z);
			*anchor = new;
			anchor = &new->next;
		} else {
			path_free(new);
		}
	}
	return p;
}