Revision: 4875
http://matplotlib.svn.sourceforge.net/matplotlib/?rev=4875&view=rev
Author: mdboom
Date: 2008-01-18 06:44:10 -0800 (Fri, 18 Jan 2008)
Log Message:
-----------
Add line simplification, to cut down on the number of line segments
that need to be stroked. Affects *Agg and Gdk backends.
Modified Paths:
--------------
trunk/matplotlib/lib/matplotlib/backends/backend_gdk.py
trunk/matplotlib/lib/matplotlib/path.py
trunk/matplotlib/src/_backend_agg.cpp
trunk/matplotlib/src/_path.cpp
trunk/matplotlib/src/agg_py_path_iterator.h
Modified: trunk/matplotlib/lib/matplotlib/backends/backend_gdk.py
===================================================================
--- trunk/matplotlib/lib/matplotlib/backends/backend_gdk.py 2008-01-17
04:13:27 UTC (rev 4874)
+++ trunk/matplotlib/lib/matplotlib/backends/backend_gdk.py 2008-01-18
14:44:10 UTC (rev 4875)
@@ -84,7 +84,7 @@
def draw_path(self, gc, path, transform, rgbFace=None):
transform = transform + Affine2D(). \
scale(1.0, -1.0).translate(0, self.height)
- polygons = path.to_polygons(transform)
+ polygons = path.to_polygons(transform, self.width, self.height)
for polygon in polygons:
# draw_polygon won't take an arbitrary sequence -- it must be a
list
# of tuples
Modified: trunk/matplotlib/lib/matplotlib/path.py
===================================================================
--- trunk/matplotlib/lib/matplotlib/path.py 2008-01-17 04:13:27 UTC (rev
4874)
+++ trunk/matplotlib/lib/matplotlib/path.py 2008-01-18 14:44:10 UTC (rev
4875)
@@ -283,7 +283,7 @@
new_codes = None
return Path(vertices, new_codes)
- def to_polygons(self, transform=None):
+ def to_polygons(self, transform=None, width=0, height=0):
"""
Convert this path to a list of polygons. Each polygon is an
Nx2 array of vertices. In other words, each polygon has no
@@ -292,13 +292,13 @@
if transform is not None:
transform = transform.frozen()
# Deal with the common and simple case
- if self.codes is None:
+ if self.codes is None and len(self.vertices) < 100:
if len(self.vertices):
return [transform.transform(self.vertices)]
return []
# Deal with the case where there are curves and/or multiple
# subpaths (using extension code)
- return convert_path_to_polygons(self, transform)
+ return convert_path_to_polygons(self, transform, width, height)
_unit_rectangle = None
[EMAIL PROTECTED]
Modified: trunk/matplotlib/src/_backend_agg.cpp
===================================================================
--- trunk/matplotlib/src/_backend_agg.cpp 2008-01-17 04:13:27 UTC (rev
4874)
+++ trunk/matplotlib/src/_backend_agg.cpp 2008-01-18 14:44:10 UTC (rev
4875)
@@ -20,6 +20,7 @@
#include "agg_span_image_filter_gray.h"
#include "agg_span_image_filter_rgba.h"
#include "agg_span_interpolator_linear.h"
+#include "agg_conv_shorten_path.h"
#include "util/agg_color_conv_rgb8.h"
#include "ft2font.h"
@@ -84,31 +85,6 @@
return Py::String(PyString_FromStringAndSize((const char*)data,
height*stride), true);
}
-template<class VertexSource> class conv_quantize
-{
-public:
- conv_quantize(VertexSource& source, bool quantize) :
- m_source(&source), m_quantize(quantize) {}
-
- void rewind(unsigned path_id) {
- m_source->rewind(path_id);
- }
-
- unsigned vertex(double* x, double* y) {
- unsigned cmd = m_source->vertex(x, y);
- if (m_quantize && agg::is_vertex(cmd)) {
- *x = round(*x) + 0.5;
- *y = round(*y) + 0.5;
- }
- return cmd;
- }
-
-private:
- VertexSource* m_source;
- bool m_quantize;
-};
-
-
GCAgg::GCAgg(const Py::Object &gc, double dpi) :
dpi(dpi), isaa(true), linewidth(1.0), alpha(1.0),
dashOffset(0.0)
@@ -358,8 +334,8 @@
template<class Path>
bool should_snap(Path& path, const agg::trans_affine& trans) {
- // If this contains only straight horizontal or vertical lines, quantize to
nearest
- // pixels
+ // If this contains only straight horizontal or vertical lines, it should be
+ // quantized to the nearest pixels
double x0, y0, x1, y1;
unsigned code;
@@ -392,6 +368,11 @@
return true;
}
+template<class Path>
+bool should_simplify(Path& path) {
+ return !path.has_curves() && path.total_vertices() > 5;
+}
+
Py::Object
RendererAgg::copy_from_bbox(const Py::Tuple& args) {
//copy region in bbox to buffer and return swig/agg buffer object
@@ -479,7 +460,7 @@
Py::Object
RendererAgg::draw_markers(const Py::Tuple& args) {
typedef agg::conv_transform<PathIterator> transformed_path_t;
- typedef conv_quantize<transformed_path_t> quantize_t;
+ typedef SimplifyPath<transformed_path_t> simplify_t;
typedef agg::conv_curve<transformed_path_t> curve_t;
typedef agg::conv_stroke<curve_t> stroke_t;
typedef agg::pixfmt_amask_adaptor<pixfmt, alpha_mask_type> pixfmt_amask_type;
@@ -510,8 +491,8 @@
bool snap = should_snap(path, trans);
transformed_path_t path_transformed(path, trans);
GCAgg gc = GCAgg(gc_obj, dpi);
- quantize_t path_quantized(path_transformed, snap);
- path_quantized.rewind(0);
+ simplify_t path_simplified(path_transformed, snap, false, width, height);
+ path_simplified.rewind(0);
facepair_t face = _get_rgba_face(face_obj, gc.alpha);
@@ -564,7 +545,7 @@
agg::serialized_scanlines_adaptor_aa8::embedded_scanline sl;
if (has_clippath) {
- while (path_quantized.vertex(&x, &y) != agg::path_cmd_stop) {
+ while (path_simplified.vertex(&x, &y) != agg::path_cmd_stop) {
pixfmt_amask_type pfa(*pixFmt, *alphaMask);
amask_ren_type r(pfa);
amask_aa_renderer_type ren(r);
@@ -579,7 +560,7 @@
agg::render_scanlines(sa, sl, ren);
}
} else {
- while (path_quantized.vertex(&x, &y) != agg::path_cmd_stop) {
+ while (path_simplified.vertex(&x, &y) != agg::path_cmd_stop) {
if (face.first) {
rendererAA->color(face.second);
sa.init(fillCache, fillSize, x, y);
@@ -881,8 +862,8 @@
Py::Object
RendererAgg::draw_path(const Py::Tuple& args) {
typedef agg::conv_transform<PathIterator> transformed_path_t;
- typedef conv_quantize<transformed_path_t> quantize_t;
- typedef agg::conv_curve<quantize_t> curve_t;
+ typedef SimplifyPath<transformed_path_t> simplify_t;
+ typedef agg::conv_curve<simplify_t> curve_t;
_VERBOSE("RendererAgg::draw_path");
args.verify_length(3, 4);
@@ -906,9 +887,11 @@
trans *= agg::trans_affine_scaling(1.0, -1.0);
trans *= agg::trans_affine_translation(0.0, (double)height);
bool snap = should_snap(path, trans);
+ bool simplify = should_simplify(path);
+
transformed_path_t tpath(path, trans);
- quantize_t quantized(tpath, snap);
- curve_t curve(quantized);
+ simplify_t simplified(tpath, snap, simplify, width, height);
+ curve_t curve(simplified);
if (snap)
gc.isaa = false;
@@ -934,8 +917,8 @@
const Py::SeqBase<Py::Object>& linestyles_obj,
const Py::SeqBase<Py::Int>& antialiaseds) {
typedef agg::conv_transform<typename PathGenerator::path_iterator>
transformed_path_t;
- typedef conv_quantize<transformed_path_t> quantize_t;
- typedef agg::conv_curve<quantize_t>
quantized_curve_t;
+ typedef SimplifyPath<transformed_path_t> simplify_t;
+ typedef agg::conv_curve<simplify_t>
simplified_curve_t;
typedef agg::conv_curve<transformed_path_t> curve_t;
GCAgg gc(dpi);
@@ -1068,12 +1051,12 @@
gc.isaa = bool(Py::Int(antialiaseds[i % Naa]));
transformed_path_t tpath(path, trans);
- quantize_t quantized(tpath, snap);
+ simplify_t simplified(tpath, snap, false, width, height);
if (has_curves) {
- quantized_curve_t curve(quantized);
+ simplified_curve_t curve(simplified);
_draw_path(curve, has_clippath, face, gc);
} else {
- _draw_path(quantized, has_clippath, face, gc);
+ _draw_path(simplified, has_clippath, face, gc);
}
} else {
gc.isaa = bool(Py::Int(antialiaseds[i % Naa]));
Modified: trunk/matplotlib/src/_path.cpp
===================================================================
--- trunk/matplotlib/src/_path.cpp 2008-01-17 04:13:27 UTC (rev 4874)
+++ trunk/matplotlib/src/_path.cpp 2008-01-18 14:44:10 UTC (rev 4875)
@@ -1102,17 +1102,23 @@
Py::Object _path_module::convert_path_to_polygons(const Py::Tuple& args)
{
typedef agg::conv_transform<PathIterator> transformed_path_t;
- typedef agg::conv_curve<transformed_path_t> curve_t;
+ typedef SimplifyPath<transformed_path_t> simplify_t;
+ typedef agg::conv_curve<simplify_t> curve_t;
typedef std::vector<double> vertices_t;
- args.verify_length(2);
+ args.verify_length(4);
PathIterator path(args[0]);
agg::trans_affine trans = py_to_agg_transformation_matrix(args[1], false);
+ double width = Py::Float(args[2]);
+ double height = Py::Float(args[3]);
+ bool simplify = !path.has_curves();
+
transformed_path_t tpath(path, trans);
- curve_t curve(tpath);
+ simplify_t simplified(tpath, false, simplify, width, height);
+ curve_t curve(simplified);
Py::List polygons;
vertices_t polygon;
Modified: trunk/matplotlib/src/agg_py_path_iterator.h
===================================================================
--- trunk/matplotlib/src/agg_py_path_iterator.h 2008-01-17 04:13:27 UTC (rev
4874)
+++ trunk/matplotlib/src/agg_py_path_iterator.h 2008-01-18 14:44:10 UTC (rev
4875)
@@ -6,6 +6,7 @@
#include "numpy/arrayobject.h"
#include "agg_path_storage.h"
#include "MPL_isnan.h"
+#include <deque>
class PathIterator
{
@@ -46,11 +47,16 @@
static const unsigned code_map[];
private:
- inline unsigned vertex(unsigned idx, double* x, double* y)
+ inline void vertex(const unsigned idx, double* x, double* y)
{
char* pair = (char*)PyArray_GETPTR2(m_vertices, idx, 0);
*x = *(double*)pair;
*y = *(double*)(pair + PyArray_STRIDE(m_vertices, 1));
+ }
+
+ inline unsigned vertex_with_code(const unsigned idx, double* x, double* y)
+ {
+ vertex(idx, x, y);
if (m_codes)
{
return code_map[(int)*(char *)PyArray_GETPTR1(m_codes, idx)];
@@ -65,11 +71,12 @@
inline unsigned vertex(double* x, double* y)
{
if (m_iterator >= m_total_vertices) return agg::path_cmd_stop;
- unsigned code = vertex(m_iterator++, x, y);
+ unsigned code = vertex_with_code(m_iterator++, x, y);
while ((MPL_isnan64(*x) || MPL_isnan64(*y)) &&
- m_iterator < m_total_vertices) {
- vertex(m_iterator++, x, y);
- code = agg::path_cmd_move_to;
+ m_iterator < m_total_vertices)
+ {
+ vertex(m_iterator++, x, y);
+ code = agg::path_cmd_move_to;
}
return code;
}
@@ -100,4 +107,368 @@
agg::path_cmd_end_poly | agg::path_flags_close
};
+#define DEBUG_SIMPLIFY 0
+
+template<class VertexSource>
+class SimplifyPath
+{
+public:
+ SimplifyPath(VertexSource& source, bool quantize, bool simplify,
+ double width = 0.0, double height = 0.0) :
+ m_source(&source), m_quantize(quantize), m_simplify(simplify),
+ m_width(width), m_height(height),
+ m_moveto(true), m_lastx(0.0), m_lasty(0.0), m_clipped(false),
+ m_do_clipping(width > 0.0 && height > 0.0),
+ m_origdx(0.0), m_origdy(0.0),
+ m_origdNorm2(0.0), m_dnorm2Max(0.0), m_dnorm2Min(0.0),
+ m_haveMin(false), m_lastMax(false), m_maxX(0.0), m_maxY(0.0),
+ m_minX(0.0), m_minY(0.0), m_lastWrittenX(0.0), m_lastWrittenY(0.0),
+ m_done(false)
+#if DEBUG_SIMPLIFY
+ , m_pushed(0), m_skipped(0)
+#endif
+ {
+ // empty
+ }
+
+#if DEBUG_SIMPLIFY
+ ~SimplifyPath()
+ {
+ printf("%d %d\n", m_pushed, m_skipped);
+ }
+#endif
+
+ void rewind(unsigned path_id)
+ {
+ m_source->rewind(path_id);
+ }
+
+ unsigned vertex(double* x, double* y)
+ {
+ unsigned cmd;
+
+ // The simplification algorithm doesn't support curves or compound
paths
+ // so we just don't do it at all in that case...
+ if (!m_simplify)
+ {
+ cmd = m_source->vertex(x, y);
+ if (m_quantize && agg::is_vertex(cmd))
+ {
+ *x = round(*x) + 0.5;
+ *y = round(*y) + 0.5;
+ }
+ return cmd;
+ }
+
+ //idea: we can skip drawing many lines: lines < 1 pixel in length,
lines
+ //outside of the drawing area, and we can combine sequential parallel
lines
+ //into a single line instead of redrawing lines over the same points.
+ //The loop below works a bit like a state machine, where what it does
depends
+ //on what it did in the last looping. To test whether sequential lines
+ //are close to parallel, I calculate the distance moved perpendicular
to the
+ //last line. Once it gets too big, the lines cannot be combined.
+
+ // This code was originally written by someone else (John Hunter?) and
I
+ // have modified to work in-place -- meaning not creating an entirely
+ // new path list each time. In order to do that without too much
+ // additional code complexity, it keeps a small queue around so that
+ // multiple points can be emitted in a single call, and those points
+ // will be popped from the queue in subsequent calls. The following
+ // block will empty the queue before proceeding to the main loop below.
+ if (m_queue.size())
+ {
+ const item& front = m_queue.front();
+ unsigned cmd = front.cmd;
+ *x = front.x;
+ *y = front.y;
+ m_queue.pop_front();
+ return cmd;
+ }
+
+ // If the queue is now empty, and the path was fully consumed
+ // in the last call to the main loop, return agg::path_cmd_stop to
+ // signal that there are no more points to emit.
+ if (m_done)
+ return agg::path_cmd_stop;
+
+ // The main simplification loop. The point is consume only as many
+ // points as necessary until some have been added to the outbound
+ // queue, not to run through the entire path in one go. This
+ // eliminates the need to allocate and fill an entire additional path
+ // array on each draw.
+ while ((cmd = m_source->vertex(x, y)) != agg::path_cmd_stop)
+ {
+ // Do any quantization if requested
+ if (m_quantize && agg::is_vertex(cmd))
+ {
+ *x = round(*x) + 0.5;
+ *y = round(*y) + 0.5;
+ }
+
+ //if we are starting a new path segment, move to the first point
+ // + init
+ if (m_moveto)
+ {
+ m_queue.push_back(item(agg::path_cmd_move_to, *x, *y));
+ m_lastx = *x;
+ m_lasty = *y;
+ m_moveto = false;
+ m_origdNorm2 = 0.0;
+#if DEBUG_SIMPLIFY
+ m_pushed++;
+#endif
+ break;
+ }
+
+ // Don't render line segments less than one pixel long
+ if (fabs(*x - m_lastx) < 1.0 && fabs(*y - m_lasty) < 1.0)
+ {
+#if DEBUG_SIMPLIFY
+ m_skipped++;
+#endif
+ continue;
+ }
+
+ //skip any lines that are outside the drawing area. Note: More
lines
+ //could be clipped, but a more involved calculation would be needed
+ if (m_do_clipping &&
+ ((*x < -1 && m_lastx < -1) ||
+ (*x > m_width + 1 && m_lastx > m_width + 1) ||
+ (*y < -1 && m_lasty < -1) ||
+ (*y > m_height + 1 && m_lasty > m_height + 1)))
+ {
+ m_lastx = *x;
+ m_lasty = *y;
+ m_clipped = true;
+ continue;
+ }
+
+ // if we have no orig vector, set it to this vector and
+ // continue.
+ // this orig vector is the reference vector we will build
+ // up the line to
+
+ if (m_origdNorm2 == 0)
+ {
+ if (m_clipped)
+ {
+ m_queue.push_back(item(agg::path_cmd_move_to, m_lastx,
m_lasty));
+ m_clipped = false;
+ }
+
+ m_origdx = *x - m_lastx;
+ m_origdy = *y - m_lasty;
+ m_origdNorm2 = m_origdx*m_origdx + m_origdy+m_origdy;
+
+ //set all the variables to reflect this new orig vecor
+ m_dnorm2Max = m_origdNorm2;
+ m_dnorm2Min = 0;
+ m_haveMin = false;
+ m_lastMax = true;
+
+ m_maxX = *x;
+ m_maxY = *y;
+ m_minX = m_lastx;
+ m_minY = m_lasty;
+
+ m_lastWrittenX = m_lastx;
+ m_lastWrittenY = m_lasty;
+
+ // set the last point seen
+ m_lastx = *x;
+ m_lasty = *y;
+ continue;
+ }
+
+ //if got to here, then we have an orig vector and we just got
+ //a vector in the sequence.
+
+ //check that the perpendicular distance we have moved from the
+ //last written point compared to the line we are building is not
too
+ //much. If o is the orig vector (we are building on), and v is the
+ //vector from the last written point to the current point, then the
+ //perpendicular vector is p = v - (o.v)o, and we normalize o (by
+ //dividing the second term by o.o).
+
+ // get the v vector
+ double totdx = *x - m_lastWrittenX;
+ double totdy = *y - m_lastWrittenY;
+ double totdot = m_origdx*totdx + m_origdy*totdy;
+
+ // get the para vector ( = (o.v)o/(o.o))
+ double paradx = totdot*m_origdx/m_origdNorm2;
+ double parady = totdot*m_origdy/m_origdNorm2;
+ double paradNorm2 = paradx*paradx + parady*parady;
+
+ // get the perp vector ( = v - para)
+ double perpdx = totdx - paradx;
+ double perpdy = totdy - parady;
+ double perpdNorm2 = perpdx*perpdx + perpdy*perpdy;
+
+ //if the perp vector is less than some number of (squared)
+ //pixels in size, then merge the current vector
+ if (perpdNorm2 < 0.25)
+ {
+ //check if the current vector is parallel or
+ //anti-parallel to the orig vector. If it is parallel, test
+ //if it is the longest of the vectors we are merging in that
+ //direction. If anti-p, test if it is the longest in the
+ //opposite direction (the min of our final line)
+
+ m_lastMax = false;
+ if (totdot >= 0)
+ {
+ if (paradNorm2 > m_dnorm2Max)
+ {
+ m_lastMax = true;
+ m_dnorm2Max = paradNorm2;
+ m_maxX = m_lastWrittenX + paradx;
+ m_maxY = m_lastWrittenY + parady;
+ }
+ }
+ else
+ {
+ m_haveMin = true;
+ if (paradNorm2 > m_dnorm2Min)
+ {
+ m_dnorm2Min = paradNorm2;
+ m_minX = m_lastWrittenX + paradx;
+ m_minY = m_lastWrittenY + parady;
+ }
+ }
+
+ m_lastx = *x;
+ m_lasty = *y;
+ continue;
+ }
+
+ //if we get here, then this vector was not similar enough to the
+ //line we are building, so we need to draw that line and start the
+ //next one.
+
+ //if the line needs to extend in the opposite direction from the
+ //direction we are drawing in, move back to we start drawing from
+ //back there.
+ if (m_haveMin)
+ m_queue.push_back(item(agg::path_cmd_line_to, m_minX, m_minY));
+ m_queue.push_back(item(agg::path_cmd_line_to, m_maxX, m_maxY));
+
+ //if we clipped some segments between this line and the next line
+ //we are starting, we also need to move to the last point.
+ if (m_clipped)
+ {
+ m_queue.push_back(item(agg::path_cmd_move_to, m_lastx,
m_lasty));
+ }
+ else if (!m_lastMax)
+ {
+ //if the last line was not the longest line, then move back to
+ //the end point of the last line in the sequence. Only do this
+ //if not clipped, since in that case lastx,lasty is not part of
+ //the line just drawn.
+
+ //Would be move_to if not for the artifacts
+ m_queue.push_back(item(agg::path_cmd_line_to, m_lastx,
m_lasty));
+ }
+
+ //now reset all the variables to get ready for the next line
+
+ m_origdx = *x - m_lastx;
+ m_origdy = *y - m_lasty;
+ m_origdNorm2 = m_origdx*m_origdx + m_origdy*m_origdy;
+
+ m_dnorm2Max = m_origdNorm2;
+ m_dnorm2Min = 0;
+ m_haveMin = false;
+ m_lastMax = true;
+ m_maxX = *x;
+ m_maxY = *y;
+ m_minX = m_lastx;
+ m_minY = m_lasty;
+
+ m_lastWrittenX = m_lastx;
+ m_lastWrittenY = m_lasty;
+
+ m_clipped = false;
+
+ m_lastx = *x;
+ m_lasty = *y;
+#if DEBUG_SIMPLIFY
+ m_pushed++;
+#endif
+ break;
+ }
+
+ // Fill the queue with the remaining vertices if we've finished the
+ // path in the above loop. Mark the path as done, so we don't call
+ // m_source->vertex again and segfault.
+ if (cmd == agg::path_cmd_stop)
+ {
+ if (m_origdNorm2 != 0)
+ {
+ if (m_haveMin)
+ m_queue.push_back(item(agg::path_cmd_line_to, m_minX,
m_minY));
+ m_queue.push_back(item(agg::path_cmd_line_to, m_maxX, m_maxY));
+ }
+ m_done = true;
+ }
+
+ // Return the first item in the queue, if any, otherwise
+ // indicate that we're done.
+ if (m_queue.size())
+ {
+ const item& front = m_queue.front();
+ unsigned cmd = front.cmd;
+ *x = front.x;
+ *y = front.y;
+ m_queue.pop_front();
+ return cmd;
+ }
+ else
+ {
+ return agg::path_cmd_stop;
+ }
+ }
+
+private:
+ VertexSource* m_source;
+ bool m_quantize;
+ bool m_simplify;
+ double m_width, m_height;
+
+ struct item
+ {
+ item(unsigned cmd_, const double& x_, double& y_) :
+ cmd(cmd_), x(x_), y(y_) {}
+ unsigned cmd;
+ double x;
+ double y;
+ };
+ typedef std::deque<item> ItemQueue;
+ ItemQueue m_queue;
+ bool m_moveto;
+ double m_lastx, m_lasty;
+ bool m_clipped;
+ bool m_do_clipping;
+
+ double m_origdx;
+ double m_origdy;
+ double m_origdNorm2;
+ double m_dnorm2Max;
+ double m_dnorm2Min;
+ bool m_haveMin;
+ bool m_lastMax;
+ double m_maxX;
+ double m_maxY;
+ double m_minX;
+ double m_minY;
+ double m_lastWrittenX;
+ double m_lastWrittenY;
+ bool m_done;
+
+#if DEBUG_SIMPLIFY
+ unsigned m_pushed;
+ unsigned m_skipped;
+#endif
+};
+
#endif // __AGG_PY_PATH_ITERATOR_H__
This was sent by the SourceForge.net collaborative development platform, the
world's largest Open Source development site.
-------------------------------------------------------------------------
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2008.
http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
_______________________________________________
Matplotlib-checkins mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/matplotlib-checkins
