garye@hp-ptp.HP.COM (Gary_Ericson) (09/16/89)
I was talking with someone once about a computer-based drawing system that
would help the user draw by 'cleaning up' the things he/she draws.
What I mean is this. Suppose I want to draw a straight line. When I move the
digitizing pen (or mouse), I will undoubtedly not keep my hand steady and the
line will be crooked. If the computer follows faithfully, I will end up with a
multi-segmented or curved line. But what if the system decided that because
all the points I've digitized lie within a certain tolerance of a straight line
that I really wanted a straight line and it draws one for me. I'm thinking of
maybe giving the pen a certain "thickness" (tolerance) and any points that lie
within that thickness of a straight line really represent a straight line.
Kind of like drawing with a fat felt-tip pen versus a fine pencil point.
It's a little harder for curves or splines, but I wonder if the same idea would
hold: if all the points, within the tolerance, lie along an arc or elipse or
spline of some kind, then the computer translates my sketch into that figure.
The idea is to smooth-out or straighten-out sketches input freehand. Plus, if
the system knows it's generating a line or arc or whatever figure, it can treat
it as such a unit, rather than as a long series of individual points.
The question is: Has anyone developed algorithms (or, better yet, software) for
this kind of thing? Is this possible or ridiculously difficult?
Disclaimer: I'm not a graphics expert of mathematician, just curious.
Gary Ericson - Hewlett-Packard
phone: (408)746-5098 mailstop: 101N email: gary@hpdsla9.hp.comdiomidis@ecrcvax.UUCP (Diomidis Spinellis) (09/22/89)
In article <1580002@hp-ptp.HP.COM> garye@hp-ptp.HP.COM (Gary_Ericson) writes: >I was talking with someone once about a computer-based drawing system that >would help the user draw by 'cleaning up' the things he/she draws. ... [Describes the problem of freehand drawing beautification] ... >The question is: Has anyone developed algorithms (or, better yet, software) for >this kind of thing? Is this possible or ridiculously difficult? A paper in SIGGRAPH describes some techniques and software developed based on them: @InProceedings {Pavlidis:85, Author="Theo Pavlidis and Christopher J. Van Wyk", Title="An Automatic Beautifier for Drawings and Illustrations", Booktitle="Computer Graphics", Editor="Brian A. Barsky", Month="July", Organization="ACM SIGGRAPH", Pages="225-243", Publisher="ACM", Year="1985" } Diomidis -- Diomidis Spinellis European Computer-Industry Research Centre (ECRC) Arabellastrasse 17, D-8000 Muenchen 81, West Germany +49 (89) 92699199 USA: diomidis%ecrcvax.uucp@pyramid.pyramid.com ...!pyramid!ecrcvax!diomidis Europe: diomidis@ecrcvax.uucp ...!unido!ecrcvax!diomidis
sleat@ez.ardent.com (Michael Sleator) (09/23/89)
In article <1580002@hp-ptp.HP.COM> garye@hp-ptp.HP.COM (Gary_Ericson) writes: >What I mean is this. Suppose I want to draw a straight line. When I move the >digitizing pen (or mouse), I will undoubtedly not keep my hand steady and the >line will be crooked. If the computer follows faithfully, I will end up with a >multi-segmented or curved line. But what if the system decided that because >all the points I've digitized lie within a certain tolerance of a straight line >that I really wanted a straight line and it draws one for me. I'm thinking of >maybe giving the pen a certain "thickness" (tolerance) and any points that lie >within that thickness of a straight line really represent a straight line. >Kind of like drawing with a fat felt-tip pen versus a fine pencil point. >It's a little harder for curves or splines, but I wonder if the same idea would >hold: if all the points, within the tolerance, lie along an arc or elipse or >spline of some kind, then the computer translates my sketch into that figure. I think that the threshold approach might be a little awkward. For example, if you do happen to stray out of the fit zone, then you get an abrupt deviation in your curve which you have to go back and correct somehow. It's also not clear to me how you decide what curve to use as a reference. Offhand, it seems that you might run into serious dynamic instabilities in trying to adaptively fit a curve while simultaneously performing this threshold function against it. On the other hand, I don't see how you could choose the curve a priori. Of course, you could specify the curve in some way, such as using spline control points, but that's not freehand drawing. Perhaps you are trying to solve the problem in the wrong domain. It seems to me that what you really want is a low pass filter on the curvature. In general, the "jigglies" (to coin a term) will be significantly higher frequency curvature components than the intended curves. This suggests that there is ample room for choosing a filter cutoff frequency that will kill the jigglies and still allow the desired curves to be drawn. It does imply that if you actually want to create an inflection point, you probably need to do it with two different strokes, but that seems intuitively sensible. I haven't thought very hard about it, but it seems that an algorithm for doing this could be quite simple. As you get each point from the input device, you recompute the local curvature at the growing end of the curve. You then bias the placement of the point according to the filter function. I wonder what it would be like to draw with a high pass curvature filter rather than a low pass. One could also experiment with bandpass and notch filters. A broad notch filter might work to eliminate the jigglies when drawing lines or large-radius curve, yet still allow inflections. Enough speculation. I'd like to hear about it if you try (or anyone else tries or has already tried) this. Michael Sleator Ardent Computer 880 W. Maude Sunnyvale, CA 94086 408-732-0400 ...!{decwrl | hplabs | ubvax | uunet}!ardent!sleat
cdl@mplvax.EDU (Carl Lowenstein) (09/24/89)
In article <1580002@hp-ptp.HP.COM> garye@hp-ptp.HP.COM (Gary_Ericson) writes: >What I mean is this. Suppose I want to draw a straight line. When I move the >digitizing pen (or mouse), I will undoubtedly not keep my hand steady and the >line will be crooked. A little history: Sutherland, Ivan E. "SKETCHPAD: A Man-Machine Graphical Communication System", MIT, 1962. "The single event that did most to promote interactive computer graphics as an important new field." say Newman & Sproull -- carl lowenstein marine physical lab u.c. san diego {decvax|ucbvax} !ucsd!mplvax!cdl cdl@mpl.ucsd.edu
paj@hrc63.uucp (Mr P Johnson "Baddow") (09/25/89)
In article <8387@ardent.UUCP>, sleat@ez.ardent.com (Michael Sleator) writes: > ... > Perhaps you are trying to solve the problem in the wrong domain. It seems > to me that what you really want is a low pass filter on the curvature. In > general, the "jigglies" (to coin a term) will be significantly higher > frequency curvature components than the intended curves. This suggests > that there is ample room for choosing a filter cutoff frequency that will > kill the jigglies > ... How about this? Have the mouse cursor attached by a rubber band to a heavy cursor. The heavy cursor draws the line and is dragged about by the mouse cursor. The rubber band between them might be pure rubber or there might be damping in the system. I have never seen a system like this, let alone used one, but if I ever want to implement freehand drawing I will try it. It has the advantage of being simple and intuitive (hence easy to get the hang of) while providing exactly the sort of smoothing you want. Sharp corners can be implemented by large mouse movements, straight or nearly straight lines by giving a pull to start the weight and then following it with the mouse. -- Paul Johnson, | `The moving finger writes, And having writ, moves on,' GEC-Marconi Research | Omar Kyham when contemplating `vi'. ------------------------------------------------------------------------------ The company has put a radio inside my head: it controls everything I say!
sleat@sim (10/06/89)
In article <694@hrc63.uucp> paj@hrc63.uucp (Mr P Johnson "Baddow") writes: >How about this? > >Have the mouse cursor attached by a rubber band to a heavy cursor. The >heavy cursor draws the line and is dragged about by the mouse cursor. The >rubber band between them might be pure rubber or there might be damping in >the system. I have never seen a system like this, let alone used one, but >if I ever want to implement freehand drawing I will try it. It has the >advantage of being simple and intuitive (hence easy to get the hang of) >while providing exactly the sort of smoothing you want. Sharp corners can >be implemented by large mouse movements, straight or nearly straight lines >by giving a pull to start the weight and then following it with the mouse. The problem I see with this, if I correctly understand what you are saying, is that it introduces a time lag in the hand-eye feedback loop. Or to look at it another way, it splits the loop into two separate loops, which I'll call the primary and secondary loops -- the primary being feedback from the cursor or mouse pointer, and the secondary being feedback from the actual curve drawn. There is a time delay between the two, which I would expect to cause all of the usual problems of delayed feedback, such as overshoot. I think this would make the system slow and frustrating to use. What I had in mind was putting the filter directly in the primary feedback loop. This is a bit radical in the sense that it violates a dictum which I have generally held as true, namely that the primary hand-eye loop is sacrosanct and anything which mucks with it is evil. However, in thinking about it, I realize that the sins against which I rail are temporal ones. That is, things like failing to update the mouse pointer because the system is busy with paging activity are in fact evil because they introduce a time delay into the feedback loop (and a randomly varying time delay, at that). What I am proposing is purely a spatial filter. There is no delay introduced. The filter will introduce some spatial non-linearity in the mapping between the mouse position and the screen pointer, but this is precisely what the feedback loop continuously compensates for anyway. In fact, it might even be practical to leave the filter in the loop for normal point-and-click operations, depending on the how extreme the filter is. To get back to the drawing problem, this approach avoids the complication of multiple feedback loops. The drawing point is at the cursor, just as with a normal system, rather than once removed from it, as in the mass-and-spring model. Michael Sleator Ardent Computer 880 W. Maude Sunnyvale, CA 94086 408-732-0400 ...!{apple | decwrl | hplabs | ubvax | uunet}!ardent!sleat
shf@well.UUCP (Stuart H. Ferguson) (10/10/89)
+-- sleat@ez.ardent.com (Michael Sleator) writes: | In article <> garye@hp-ptp.HP.COM (Gary_Ericson) writes: | >What I mean is this. Suppose I want to draw a straight line. When I move | >the digitizing pen (or mouse), I will undoubtedly not keep my hand steady | >and the line will be crooked. If the computer follows faithfully, I | >will end up with a multi-segmented or curved line. But what if the | >system decided that because all the points I've digitized lie within a | >certain tolerance of a straight line that I really wanted a straight line | >and it draws one for me. [ ... ] | | [ ... ] It seems | to me that what you really want is a low pass filter on the curvature. In | general, the "jigglies" (to coin a term) will be significantly higher | frequency | curvature components than the intended curves. This suggests that there is | ample room for choosing a filter cutoff frequency that will kill the jigglies | and still allow the desired curves to be drawn. It does imply that if you | actually want to create an inflection point, you probably need to do it with | two different strokes, but that seems intuitively sensible. I saw some interesting research presented a few years ago by some folks from Schlumberger(sp?) in Palo Alto, I think (same folks who did the "Cooking with Curt" Siggraph video). They were using "strings" or "snakes" or something like that to do some image analysis tasks. The snakes were basically spring and mass models that reacted to some feature of an image as if it were a potential field. For example, if you take the gradient of an image, negate it and call it a potential, then the snakes will tend to "fall" into the potential wells caused by sharp changes in the image, such as lines. But since they also have some stiffness, they will actually make a nice fit of the line despite noise in the image. This might make an interesting basis for a nice curve drawing tool. Let the user draw the noisy line that a shakey hand will draw, but then lay down a snake along the same path and let it relax into a nice curve. The speed of the mouse at different places along the path could map into the stiffness of the snake at those places so that where the mouse moved slowly the snake would fit more exactly (like inflection points), and where the mouse moved quickly there would be more smoothing. The user could tune the stiffness or perhaps go back and manipulate the snake directly. There's a paper about these beasts as well as their 3D and phase-space counterparts by the same folks whose name I couldn't remember very well above. The real-time demos they showed looked fast enough for the purpose proposed. -- Stuart Ferguson (shf@well.UUCP) Action by HAVOC (ferguson@metaphor.com)