Skip to content

PRF: Speed up point_in_path and friends #6450

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 4 commits into from
May 19, 2016
Merged

PRF: Speed up point_in_path and friends #6450

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
4 commits
Select commit Hold shift + click to select a range
27d1199
Revert 2c1bc6b for performance
mdboom May 19, 2016
2c5d292
Use ( , ) instead of [] for indexing
mdboom May 19, 2016
7976970
Rename operator[] to subarray...
mdboom May 19, 2016
aef86ad
Don't use contouring on the path unless necessary
mdboom May 19, 2016
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
1 change: 0 additions & 1 deletion lib/matplotlib/tests/test_path.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -39,7 +39,6 @@ def test_contains_points_negative_radius():
expected = [True, False, False]
result = path.contains_points(points, radius=-0.5)

assert result.dtype == np.bool
assert np.all(result == expected)


Expand Down
26 changes: 13 additions & 13 deletions src/_backend_agg.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -961,13 +961,13 @@ inline void RendererAgg::_draw_path_collection_generic(GCAgg &gc,
typename PathGenerator::path_iterator path = path_generator(i);

if (Ntransforms) {
typename TransformArray::sub_t subtrans = transforms[i % Ntransforms];
trans = agg::trans_affine(subtrans(0, 0),
subtrans(1, 0),
subtrans(0, 1),
subtrans(1, 1),
subtrans(0, 2),
subtrans(1, 2));
int it = i % Ntransforms;
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

here you are using int's, but elsewhere, you use size_t. Any particular reason for that?

trans = agg::trans_affine(transforms(it, 0, 0),
transforms(it, 1, 0),
transforms(it, 0, 1),
transforms(it, 1, 1),
transforms(it, 0, 2),
transforms(it, 1, 2));
trans *= master_transform;
} else {
trans = master_transform;
Expand All @@ -989,13 +989,13 @@ inline void RendererAgg::_draw_path_collection_generic(GCAgg &gc,
trans *= agg::trans_affine_translation(0.0, (double)height);

if (Nfacecolors) {
typename ColorArray::sub_t facecolor = facecolors[i % Nfacecolors];
face.second = agg::rgba(facecolor(0), facecolor(1), facecolor(2), facecolor(3));
int ic = i % Nfacecolors;
face.second = agg::rgba(facecolors(ic, 0), facecolors(ic, 1), facecolors(ic, 2), facecolors(ic, 3));
}

if (Nedgecolors) {
typename ColorArray::sub_t edgecolor = edgecolors[i % Nedgecolors];
gc.color = agg::rgba(edgecolor(0), edgecolor(1), edgecolor(2), edgecolor(3));
int ic = i % Nedgecolors;
gc.color = agg::rgba(edgecolors(ic, 0), edgecolors(ic, 1), edgecolors(ic, 2), edgecolors(ic, 3));

if (Nlinewidths) {
gc.linewidth = linewidths(i % Nlinewidths);
Expand Down Expand Up @@ -1274,8 +1274,8 @@ inline void RendererAgg::draw_gouraud_triangles(GCAgg &gc,
bool has_clippath = render_clippath(gc.clippath.path, gc.clippath.trans);

for (int i = 0; i < points.dim(0); ++i) {
typename PointArray::sub_t point = points[i];
typename ColorArray::sub_t color = colors[i];
typename PointArray::sub_t point = points.subarray(i);
typename ColorArray::sub_t color = colors.subarray(i);

_draw_gouraud_triangle(point, color, trans, has_clippath);
}
Expand Down
28 changes: 12 additions & 16 deletions src/_image.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -126,14 +126,12 @@ Image *from_color_array(ArrayType &array, bool isoutput)

for (size_t rownum = 0; rownum < (size_t)array.dim(0); rownum++) {
for (size_t colnum = 0; colnum < (size_t)array.dim(1); colnum++) {
typename ArrayType::sub_t::sub_t color = array[rownum][colnum];

r = color(0);
g = color(1);
b = color(2);
r = array(rownum, colnum, 0);
g = array(rownum, colnum, 1);
b = array(rownum, colnum, 2);

if (rgba) {
alpha = color(3);
alpha = array(rownum, colnum, 3);
}

*buffer++ = int(255 * r); // red
Expand Down Expand Up @@ -164,13 +162,12 @@ Image *frombyte(ArrayType &array, bool isoutput)

for (size_t rownum = 0; rownum < (size_t)array.dim(0); rownum++) {
for (size_t colnum = 0; colnum < (size_t)array.dim(1); colnum++) {
typename ArrayType::sub_t::sub_t color = array[rownum][colnum];
r = color(0);
g = color(1);
b = color(2);
r = array(rownum, colnum, 0);
g = array(rownum, colnum, 1);
b = array(rownum, colnum, 2);

if (rgba) {
alpha = color(3);
alpha = array(rownum, colnum, 3);
}

*buffer++ = r; // red
Expand Down Expand Up @@ -295,13 +292,12 @@ Image *pcolor(CoordinateArray &x,
a10 = (1.0 - alpha) * beta;
a11 = 1.0 - a00 - a01 - a10;

typename ColorArray::sub_t::sub_t start00 = d[rowstart[i]][colstart[j]];
typename ColorArray::sub_t::sub_t start01 = d[rowstart[i]][colstart[j] + 1];
typename ColorArray::sub_t::sub_t start10 = d[rowstart[i] + 1][colstart[j]];
typename ColorArray::sub_t::sub_t start11 = d[rowstart[i] + 1][colstart[j] + 1];
for (size_t k = 0; k < 4; ++k) {
position[k] =
start00(k) * a00 + start01(k) * a01 + start10(k) * a10 + start11(k) * a11;
d(rowstart[i], colstart[j], k) * a00 +
d(rowstart[i], colstart[j] + 1, k) * a01 +
d(rowstart[i] + 1, colstart[j], k) * a10 +
d(rowstart[i] + 1, colstart[j] + 1, k) * a11;
}
position += 4;
}
Expand Down
87 changes: 44 additions & 43 deletions src/_path.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -18,6 +18,7 @@

#include "path_converters.h"
#include "_backend_agg_basic_types.h"
#include "numpy_cpp.h"

struct XY
{
Expand Down Expand Up @@ -79,7 +80,7 @@ struct XY
template <class PathIterator, class PointArray, class ResultArray>
void point_in_path_impl(PointArray &points, PathIterator &path, ResultArray &inside_flag)
{
bool yflag1;
uint8_t yflag1;
double vtx0, vty0, vtx1, vty1;
double tx, ty;
double sx, sy;
Expand All @@ -89,13 +90,13 @@ void point_in_path_impl(PointArray &points, PathIterator &path, ResultArray &ins

size_t n = points.size();

std::vector<bool> yflag0(n);
std::vector<bool> subpath_flag(n);
std::vector<uint8_t> yflag0(n);
std::vector<uint8_t> subpath_flag(n);

path.rewind(0);

for (i = 0; i < n; ++i) {
inside_flag[i] = false;
inside_flag[i] = 0;
}

unsigned code = 0;
Expand All @@ -112,13 +113,13 @@ void point_in_path_impl(PointArray &points, PathIterator &path, ResultArray &ins
sy = vty0 = vty1 = y;

for (i = 0; i < n; ++i) {
ty = points[i][1];
ty = points(i, 1);

if (std::isfinite(ty)) {
// get test bit for above/below X axis
yflag0[i] = (vty0 >= ty);

subpath_flag[i] = false;
subpath_flag[i] = 0;
}
}

Expand All @@ -135,8 +136,8 @@ void point_in_path_impl(PointArray &points, PathIterator &path, ResultArray &ins
}

for (i = 0; i < n; ++i) {
tx = points[i][0];
ty = points[i][1];
tx = points(i, 0);
ty = points(i, 1);

if (!(std::isfinite(tx) && std::isfinite(ty))) {
continue;
Expand Down Expand Up @@ -164,7 +165,7 @@ void point_in_path_impl(PointArray &points, PathIterator &path, ResultArray &ins
// Haigh-Hutchinson's different polygon inclusion
// tests.
if (((vty1 - ty) * (vtx0 - vtx1) >= (vtx1 - tx) * (vty0 - vty1)) == yflag1) {
subpath_flag[i] = subpath_flag[i] ^ true;
subpath_flag[i] ^= 1;
}
}

Expand All @@ -183,8 +184,8 @@ void point_in_path_impl(PointArray &points, PathIterator &path, ResultArray &ins

all_done = true;
for (i = 0; i < n; ++i) {
tx = points[i][0];
ty = points[i][1];
tx = points(i, 0);
ty = points(i, 1);

if (!(std::isfinite(tx) && std::isfinite(ty))) {
continue;
Expand All @@ -196,8 +197,8 @@ void point_in_path_impl(PointArray &points, PathIterator &path, ResultArray &ins
subpath_flag[i] = subpath_flag[i] ^ true;
}
}
inside_flag[i] = inside_flag[i] || subpath_flag[i];
if (inside_flag[i] == false) {
inside_flag[i] |= subpath_flag[i];
if (inside_flag[i] == 0) {
all_done = false;
}
}
Expand Down Expand Up @@ -232,21 +233,23 @@ inline void points_in_path(PointArray &points,
transformed_path_t trans_path(path, trans);
no_nans_t no_nans_path(trans_path, true, path.has_curves());
curve_t curved_path(no_nans_path);
contour_t contoured_path(curved_path);
contoured_path.width(r);

point_in_path_impl(points, contoured_path, result);
if (r != 0.0) {
contour_t contoured_path(curved_path);
contoured_path.width(r);
point_in_path_impl(points, contoured_path, result);
} else {
point_in_path_impl(points, curved_path, result);
}
}

template <class PathIterator>
inline bool point_in_path(
double x, double y, const double r, PathIterator &path, agg::trans_affine &trans)
{
std::vector<double> point;
std::vector<std::vector<double> > points;
point.push_back(x);
point.push_back(y);
points.push_back(point);
npy_intp shape[] = {1, 2};
numpy::array_view<double, 2> points(shape);
points(0, 0) = x;
points(0, 1) = y;

int result[1];
result[0] = 0;
Expand Down Expand Up @@ -285,11 +288,10 @@ template <class PathIterator>
inline bool point_on_path(
double x, double y, const double r, PathIterator &path, agg::trans_affine &trans)
{
std::vector<double> point;
std::vector<std::vector<double> > points;
point.push_back(x);
point.push_back(y);
points.push_back(point);
npy_intp shape[] = {1, 2};
numpy::array_view<double, 2> points(shape);
points(0, 0) = x;
points(0, 1) = y;

int result[1];
result[0] = 0;
Expand Down Expand Up @@ -385,13 +387,13 @@ void get_path_collection_extents(agg::trans_affine &master_transform,
for (i = 0; i < N; ++i) {
typename PathGenerator::path_iterator path(paths(i % Npaths));
if (Ntransforms) {
typename TransformArray::sub_t subtrans = transforms[i % Ntransforms];
trans = agg::trans_affine(subtrans(0, 0),
subtrans(1, 0),
subtrans(0, 1),
subtrans(1, 1),
subtrans(0, 2),
subtrans(1, 2));
size_t ti = i % Ntransforms;
trans = agg::trans_affine(transforms(ti, 0, 0),
transforms(ti, 1, 0),
transforms(ti, 0, 1),
transforms(ti, 1, 1),
transforms(ti, 0, 2),
transforms(ti, 1, 2));
} else {
trans = master_transform;
}
Expand Down Expand Up @@ -437,13 +439,13 @@ void point_in_path_collection(double x,
typename PathGenerator::path_iterator path = paths(i % Npaths);

if (Ntransforms) {
typename TransformArray::sub_t subtrans = transforms[i % Ntransforms];
trans = agg::trans_affine(subtrans(0, 0),
subtrans(1, 0),
subtrans(0, 1),
subtrans(1, 1),
subtrans(0, 2),
subtrans(1, 2));
size_t ti = i % Ntransforms;
trans = agg::trans_affine(transforms(ti, 0, 0),
transforms(ti, 1, 0),
transforms(ti, 0, 1),
transforms(ti, 1, 1),
transforms(ti, 0, 2),
transforms(ti, 1, 2));
trans *= master_transform;
} else {
trans = master_transform;
Expand Down Expand Up @@ -771,8 +773,7 @@ int count_bboxes_overlapping_bbox(agg::rect_d &a, BBoxArray &bboxes)

size_t num_bboxes = bboxes.size();
for (size_t i = 0; i < num_bboxes; ++i) {
typename BBoxArray::sub_t bbox_b = bboxes[i];
b = agg::rect_d(bbox_b(0, 0), bbox_b(0, 1), bbox_b(1, 0), bbox_b(1, 1));
b = agg::rect_d(bboxes(i, 0, 0), bboxes(i, 0, 1), bboxes(i, 1, 0), bboxes(i, 1, 1));

if (b.x2 < b.x1) {
std::swap(b.x1, b.x2);
Expand Down
4 changes: 2 additions & 2 deletions src/_path_wrapper.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -93,7 +93,7 @@ static PyObject *Py_points_in_path(PyObject *self, PyObject *args, PyObject *kwd
}

npy_intp dims[] = { (npy_intp)points.size() };
numpy::array_view<bool, 1> results(dims);
numpy::array_view<uint8_t, 1> results(dims);

CALL_CPP("points_in_path", (points_in_path(points, r, path, trans, results)));

Expand Down Expand Up @@ -152,7 +152,7 @@ static PyObject *Py_points_on_path(PyObject *self, PyObject *args, PyObject *kwd
}

npy_intp dims[] = { (npy_intp)points.size() };
numpy::array_view<bool, 1> results(dims);
numpy::array_view<uint8_t, 1> results(dims);

CALL_CPP("points_on_path", (points_on_path(points, r, path, trans, results)));

Expand Down
2 changes: 1 addition & 1 deletion src/_png.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -91,7 +91,7 @@ static PyObject *Py_write_png(PyObject *self, PyObject *args, PyObject *kwds)
int channels = buffer.dim(2);
std::vector<png_bytep> row_pointers(height);
for (png_uint_32 row = 0; row < (png_uint_32)height; ++row) {
row_pointers[row] = (png_bytep)buffer[row].data();
row_pointers[row] = (png_bytep)&buffer(row, 0, 0);
}

FILE *fp = NULL;
Expand Down
4 changes: 2 additions & 2 deletions src/numpy_cpp.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -284,7 +284,7 @@ class array_view_accessors<AV, T, 2>
self->m_strides[1] * j);
}

sub_t operator[](npy_intp i) const
sub_t subarray(npy_intp i) const
{
const AVC *self = static_cast<const AVC *>(this);

Expand Down Expand Up @@ -318,7 +318,7 @@ class array_view_accessors<AV, T, 3>
self->m_strides[1] * j + self->m_strides[2] * k);
}

sub_t operator[](npy_intp i) const
sub_t subarray(npy_intp i) const
{
const AVC *self = static_cast<const AVC *>(this);

Expand Down