If you google "how to implement a pencil tool in Java" you get a few results that basically tell you how to implement the right MouseListeners to record the mouse points. Then you have a giant polygon. (Or polyline, technically).The problem is: this is ugly. It's acceptable for beginners, or prototypes: but we can do better.
What I want to do is smooth out this data. To replace the series of lines with attractive bezier curves. To the right is an image of what I'm looking for.
I'm not entirely sure what to call this project. (Is there an official word for this? Does anyone know?) It's a mix between "Vectorization" and "Beautification"? For now I created a simple interface called Vectorizer:
public interface Vectorizer {
public void add(float x,float y,long t);
public void reset();
public GeneralPath getShape();
public void getShape(GeneralPath path);
public boolean isEmpty();
}Results
I ended up with the following applet.
You can download this applet here (source included).
Implementation
The applet above demos the
BasicVectorizer. In pseudocode it goes likes this:currentPoint = 0;
while more points remain:
lastPoint = currentPoint + 1;
create cubic arc from currentPoint to lastPoint
while arc is within the allowed error:
lastPoint++;
create cubic arc from currentPoint to lastPoint
write arc
currentPoint = lastPoint;
This seems to work well for far-away points, but it starts to suffer when several points are clustered together. The problem (for me) is it's hard to guess what the user is trying to do when the mouse moves in a small area: is the user drawing a sharp corner? Just drawing slowly? They might not be using a mouse at all -- maybe an assistive device doesn't track the way mice do?
So there's room for improvement, but it's a start.
Other Resources
The only other open-source pencil tool I'm familiar with is Werner's in JHotDraw. (The license is LGPL. I believe the classes involved are
org.jhotdraw.geom.Bezier and org.jhotdraw.geom.BezierPath.)Does anyone have other examples handy on the subject?
For now this meets my immediate needs, but maybe in the future I'll touch it up a little.
Posts
Hi Jeremy, this is fantastic! The word you are looking for is smoothing, http://en.wikipedia.org/wiki/Smoothing . Would it help if there was an algorithm that analyzes the distances between points in the path and then removes those points that the algorithm sees as redundant? For instance, the algorithm can analyze the second derivative and given that the distance between three points is less than a certain cutoff and the second derivative through those points is consistent within some tolerance (or the tolerance is based on the inter-point distances), then the middle point is removed? This may help to reduce jaggies in slowly drawn segments.
ReplyDeleteBests,
Kevin Theisen
Hi Jeremy,
ReplyDeleteI think 'bezier curve fitting' is the official term for this. :-)
The algorithm in JHotDraw throws a digitized point away if the distance to the previous point is too small. For mouse input, it uses a minimal distance of two screen pixel units.
Best,
Werner
I just finished a first version of a line smoother for my new comic art program... I think my algorithm was a bit simpler than this one.
ReplyDeleteI recorded all the points, then looped over them and set bezier points for each one. I created the bezier points by getting a bounding rectangle that contained the point before and the point after the current point, scaled the rectangle's size to half and moved it to a place where its center is on the original point.
In this case there's no increasing or decreasing the amount of smoothing... but in practice it seems to work pretty well for both smoothing when you want it to and not butchering corners if the user draws them. The faster the user moves the pen, the more the line is smoothed, which I think works well. If they're drawing slowly, that probably means they're being pretty careful about it, and you really don't want to correct too much if they're already being very careful about their stroke. On the other hand if they're drawing quickly, they probably would rather a smoother line versus the angular lines produced by the raw polygon.
Incidentally, although the official term may be "smoothing" (which is what I generally call it) or "bezier curve fitting" (really? seems pretty cryptic) I named my class Freehand. Okay it's not a class -- I'm writing in Scala, so it's a trait, but that's neither here nor there. ;P
hey hi, can u plzz upload the source code too
ReplyDeleteThe source code is available in the jar. (There is a link to the jar just under the applet itself on this page.)
ReplyDelete