Getting the real bounds of a Bezier curve
Hi,
I'm doing a vectorial drawing program and I want to draw a rectangle around a shape when it is selected. I actually get the rectangle by calling Shape.getBounds2D().
However, if the shape is a Bezier curve (GeneralPath), the returned rectangle is not what the user is expecting since the rectangle encloses the convex hull of the Bezier curve, instead of enclosing only what the displayed curve. indeed, GeneralPath.getBounds2D() considers that the control points are part of the bounds.
How to get the bounds of a displayed Bezier curve? I even wonder if it's possible to get it in a JRE portable way since it seems to me that it depends on SunGraphics2D. What do you think?
# 1
import java.awt.*;
import java.awt.geom.*;
import javax.swing.*;
public class BezierBounds extends JPanel {
protected void paintComponent(Graphics g) {
super.paintComponent(g);
Graphics2D g2 = (Graphics2D)g;
g2.setRenderingHint(RenderingHints.KEY_ANTIALIASING,
RenderingHints.VALUE_ANTIALIAS_ON);
double w = getWidth();
double h = getHeight();
CubicCurve2D.Double curve =
new CubicCurve2D.Double(w/4,h*15/16,
w*4/3, h/64,
w/16, h/64,
w*3/4, h*2/3);
g2.setPaint(Color.blue);
g2.draw(curve);
g2.setPaint(Color.red);
g2.draw(curve.getBounds2D());
g2.setPaint(Color.green.darker());
g2.draw(getCurveBounds(curve));
}
private Rectangle2D.Double getCurveBounds(CubicCurve2D.Double curve) {
double flatness = 0.01;
PathIterator pit = curve.getPathIterator(null, flatness);
double[] coords = new double[2];
double minX = Double.MAX_VALUE, minY = Double.MAX_VALUE;
double maxX = Double.MIN_VALUE, maxY = Double.MIN_VALUE;
while(!pit.isDone()) {
int type = pit.currentSegment(coords);
switch(type) {
case PathIterator.SEG_MOVETO:
// fall through
case PathIterator.SEG_LINETO:
if(coords[0] < minX) minX = coords[0];
if(coords[0] > maxX) maxX = coords[0];
if(coords[1] < minY) minY = coords[1];
if(coords[1] > maxY) maxY = coords[1];
break;
}
pit.next();
}
return new Rectangle2D.Double(minX, minY, maxX-minX, maxY-minY);
}
public static void main(String[] args) {
JFrame f = new JFrame();
f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
f.getContentPane().add(new BezierBounds());
f.setSize(500,400);
f.setLocation(200,200);
f.setVisible(true);
}
}
# 2
Thanks for your response,
However, I suspect that you don't have tried to draw many curves. If you use the following curve in your program you will see the problem:
GeneralPath curve = new GeneralPath();
curve.moveTo(336, 448);
curve.curveTo(379, 380, 355, 536, 391, 477);
curve.quadTo(427, 418, 446, 479);
So, any idea how to get the real bounds?
# 3
I tried your GeneralPath and it worked okay. Make these changes in BezierBounds:
protected void paintComponent(Graphics g) {
...
/*
CubicCurve2D.Double curve =
new CubicCurve2D.Double(w/4,h*15/16,
w*4/3, h/64,
w/16, h/64,
w*3/4, h*2/3);
*/
GeneralPath curve = new GeneralPath();
curve.moveTo(336, 448);
curve.curveTo(379, 380, 355, 536, 391, 477);
curve.quadTo(427, 418, 446, 479);
g2.setPaint(Color.blue);
...
}
private Rectangle2D.Double getCurveBounds(//CubicCurve2D.Double curve) {
GeneralPath curve) {
...
public static void main(String[] args) {
...
// Frame height was too small for your GeneralPath to show up.
f.setSize(500,600);
# 4
We used the same code. You should see at the bottom of the curve that the curve exceeds the bounds of 1 pixel. What platform do you use? I'm using Windows XP and have tried the JRE 5 and 6.
Here is another curve that you can try that show (at least to me) the same problem:
GeneralPath curve = new GeneralPath();
curve.moveTo(16, 146);
curve.curveTo(83, 65, 68, 344, 125, 225);
I wlll try to post a link to show a screen capture of the problem.
Otherwise, a solution could be to look at the SunGraphics2D class to know how the curve is rendered and infer the bounds based on this knowledge. However, I don't know if Sun has open sourced rt.jar or even if it will do it in the future. Do you know?
Or, is there another mean to compute the real bounds?
# 5
Here is pure mathematical solution (without flattenization). It's based on splitting bezier curves into monotonic parts. Please, have a look.
import java.awt.*;
import java.awt.geom.*;
import java.util.Arrays;
import javax.swing.*;
public class BezierBounds extends JPanel {
protected void paintComponent(Graphics g) {
super.paintComponent(g);
Graphics2D g2 = (Graphics2D)g;
g2.setRenderingHint(RenderingHints.KEY_ANTIALIASING,
RenderingHints.VALUE_ANTIALIAS_ON);
double w = getWidth();
double h = getHeight();
CubicCurve2D.Double curve =
new CubicCurve2D.Double(w/4,h*15/16,
w*4/3, h/64,
w/16, h/64,
w*3/4, h*2/3);
g2.setPaint(Color.blue);
g2.draw(curve);
g2.setPaint(Color.red);
g2.draw(curve.getBounds2D());
g2.setPaint(Color.green.darker());
g2.draw(getCurveBounds(curve));
}
private static void ProcessMonotonicCubic(double[] coords, double[] bbox ) {
if (bbox[0] > coords[0]) bbox[0] = coords[0];
if (bbox[1] > coords[1]) bbox[1] = coords[1];
if (bbox[2] < coords[0]) bbox[2] = coords[0];
if (bbox[3] < coords[1]) bbox[3] = coords[1];
if (bbox[0] > coords[6]) bbox[0] = coords[6];
if (bbox[1] > coords[7]) bbox[1] = coords[7];
if (bbox[2] < coords[6]) bbox[2] = coords[6];
if (bbox[3] < coords[7]) bbox[3] = coords[7];
}
/*
* Bite the piece of the cubic curve from start point till the point
* corresponding to the specified parameter then call ProcessCubic for the
* bitten part.
* Note: coords array will be changed
*/
private static void ProcessFirstMonotonicPartOfCubic(double[] coords,
double[] bbox,
double t)
{
double[] coords1 = new double[8];
double tx, ty;
coords1[0] = coords[0];
coords1[1] = coords[1];
tx = coords[2] + t*(coords[4] - coords[2]);
ty = coords[3] + t*(coords[5] - coords[3]);
coords1[2] = coords[0] + t*(coords[2] - coords[0]);
coords1[3] = coords[1] + t*(coords[3] - coords[1]);
coords1[4] = coords1[2] + t*(tx - coords1[2]);
coords1[5] = coords1[3] + t*(ty - coords1[3]);
coords[4] = coords[4] + t*(coords[6] - coords[4]);
coords[5] = coords[5] + t*(coords[7] - coords[5]);
coords[2] = tx + t*(coords[4] - tx);
coords[3] = ty + t*(coords[5] - ty);
coords[0]=coords1[6]=coords1[4] + t*(coords[2] - coords1[4]);
coords[1]=coords1[7]=coords1[5] + t*(coords[3] - coords1[5]);
ProcessMonotonicCubic(coords1, bbox);
}
/*
* Split cubic curve into monotonic in X and Y parts. Calling
* ProcessMonotonicCubic for each monotonic piece of the curve.
*
* Note: coords array could be changed
*/
private static void ProcessCubic(double[] coords, double[] bbox) {
/* Temporary array for holding parameters corresponding to the extreme
* in X and Y points
*/
double params[] = new double[4];
double eqn[] = new double[3];
double res[] = new double[2];
int cnt = 0;
/* Simple check for monotonicity in X before searching for the extreme
* points of the X(t) function. We first check if the curve is
* monotonic in X by seeing if all of the X coordinates are strongly
* ordered.
*/
if ((coords[0] > coords[2] || coords[2] > coords[4] ||
coords[4] > coords[6]) &&
(coords[0] < coords[2] || coords[2] < coords[4] ||
coords[4] < coords[6]))
{
/* Searching for extreme points of the X(t) function by solving
* dX(t)
* - = 0 equation
* dt
*/
eqn[2] = -coords[0] + 3*coords[2] - 3*coords[4] + coords[6];
eqn[1] = 2*(coords[0] - 2*coords[2] + coords[4]);
eqn[0] = -coords[0] + coords[2];
int nr = QuadCurve2D.solveQuadratic(eqn, res);
/* Following code also correctly works in degenerate case of
* the quadratic equation (nr = -1) because we do not need
* splitting in this case.
*/
for (int i = 0; i < nr; i++) {
if (res[i] > 0 && res[i] < 1) {
params[cnt++] = res[i];
}
}
}
/* Simple check for monotonicity in Y before searching for the extreme
* points of the Y(t) function. We first check if the curve is
* monotonic in Y by seeing if all of the Y coordinates are strongly
* ordered.
*/
if ((coords[1] > coords[3] || coords[3] > coords[5] ||
coords[5] > coords[7]) &&
(coords[1] < coords[3] || coords[3] < coords[5] ||
coords[5] < coords[7]))
{
/* Searching for extreme points of the Y(t) function by solving
* dY(t)
* -- = 0 equation
* dt
*/
eqn[2] = -coords[1] + 3*coords[3] - 3*coords[5] + coords[7];
eqn[1] = 2*(coords[1] - 2*coords[3] + coords[5]);
eqn[0] = -coords[1] + coords[3];
int nr = QuadCurve2D.solveQuadratic(eqn, res);
/* Following code also correctly works in degenerate case of
* the quadratic equation (nr = -1) because we do not need
* splitting in this case.
*/
for (int i = 0; i < nr; i++) {
if (res[i] > 0 && res[i] < 1) {
params[cnt++] = res[i];
}
}
}
if (cnt > 0) {
/* Sorting parameter values corresponding to the extreme points
* of the curve
*/
Arrays.sort(params, 0, cnt);
/* Processing obtained monotonic parts */
ProcessFirstMonotonicPartOfCubic(coords, bbox,
(float)params[0]);
for (int i = 1; i < cnt; i++) {
double param = params[i] - params[i-1];
if (param > 0) {
ProcessFirstMonotonicPartOfCubic(coords, bbox,
/* Scale parameter to match with rest of the curve */
(float)(param/(1.0 - params[i - 1])));
}
}
}
ProcessMonotonicCubic(coords, bbox);
}
private Rectangle2D.Double getCurveBounds(CubicCurve2D curve) {
double minX = Double.MAX_VALUE, minY = Double.MAX_VALUE;
double maxX = Double.MIN_VALUE, maxY = Double.MIN_VALUE;
double [] bbox = new double[] {Double.MAX_VALUE, Double.MAX_VALUE, Double.MIN_VALUE, Double.MIN_VALUE};
ProcessCubic(new double[] {curve.getP1().getX(), curve.getP1().getY(),
curve.getCtrlP1().getX(), curve.getCtrlP1().getY(), curve.getCtrlP2().getX(),
curve.getCtrlP2().getY(), curve.getP2().getX(), curve.getP2().getY()}, bbox);
return new Rectangle2D.Double(bbox[0], bbox[1], bbox[2] - bbox[0], bbox[3] - bbox[1]);
}
public static void main(String[] args) {
JFrame f = new JFrame();
f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
f.getContentPane().add(new BezierBounds());
f.setSize(500,400);
f.setLocation(200,200);
f.setVisible(true);
}
}
# 6
Nice try but your code don't work for many curves. By exemple, you can try with this curve:
new CubicCurve2D.Double(16, 146, 83, 65, 68, 344, 125, 225);
It appears to me that SunGraphics2D don't always paint the curve where it should be, likely for speed purpose. The precision is not good enough for some kind of application. We should have a mean to change the rendering algorithm used by the Graphics2D instance to say that we prefer precison over speed, something like RenderingHints.KEY_CUBIC_PRECISION. Do you agree?
As a weird workaround, we could paint the curve on a blank image and analyse the image to detect the bounds of the curve. Is-it achievable and if yes, do you know how to do that?
Or again, does someone have another mean to compute the real bounds?
# 7
You might want to try switch AA off or change stroke control rendering hint to disable normalization of the coordinates that leads to exceeding calculated boundaries.
g2.setRenderingHint(RenderingHints.KEY_STROKE_CONTROL,
RenderingHints.VALUE_STROKE_PURE);
Actually, the code that I've post is similar to one that used in java2d non-AA software renderer. It's used when you are drawing on BufferedImage or even on screen through OpenGL and X11 pipelines.
# 8
I tried to turn off AA and to use differents rendering hints as stroke control, wihtout success.
> Actually, the code that I've post is similar to one
> that used in java2d non-AA software renderer. It's
> used when you are drawing on BufferedImage or even on
> screen through OpenGL and X11 pipelines.
So, it should work on a Linux OS. I only have a Windows machine actually. Can someone test it on a Linux OS please? If it really works, your code may be part of the solution. Do you have the same kind of code for DirectX / Windows?
Another solution that I'm considering as last resort is to render myself the curve using only Graphics.drawLine(). That would imply reinventing the wheel and a lot of work. The benefit is that the rendering would be the same on all platforms. I wish that there is a simpler solution to have identical cross-platform rendering.
Graphics2D should behave the same on all platforms, do you agree? If yes, this issue should be considered as a bug.
# 9
> It appears to me that SunGraphics2D don't always
> paint the curve where it should be, likely for speed
> purpose.
This is wrong. The reason is because you have two different algorithms
that are doing the sampling of points from the curve. The first algorithm
is the draw method that draws the curve. The second algorithm is the
flattening path iterator algorithm. Since different sample points are
used, the bounds are going to be slightly different.
GeneralPath uses float precision. When you're dealing with Bezier
curves on 4 control points, the computation is trivial and speed is
not an issue. n point Bezier curves require O(n) computation for
each sampled point.
> something like RenderingHints.KEY_CUBIC_PRECISION. Do
> you agree?
No. Again it's just that two different sampling algorithms are used.
> As a weird workaround, we could paint the curve on a
> blank image and analyse the image to detect the
> bounds of the curve. Is-it achievable and if yes, do
> you know how to do that?
This is a bad idea on so many levels. First, it gets complicated if
there are other graphics on the screen, second, it will be magnitudes
slower and inefficient.
If you're really concerned about getting the exact bounds, then compute
the points on the bezier curve yourself, and then compute the bounding
box. The curve API on sourceforge already has this functionality.
# 10
> Another solution that I'm considering as last resort is to render> myself the curve using only Graphics.drawLine(). Just turn the curve into a flattened path, draw it, and get the boundingbox of the flattened path iterator.
# 11
> Just turn the curve into a flattened path, draw it,
> and get the bounding
> box of the flattened path iterator.
While this would work, it would also look ugly. I want the same drawing quality as Adobe Illustrator or Inkscape.
For an idea of the complexity involved in the painting of a good-looking Bezier curve only with lines, take a look here:
http://www.antigrain.com/research/adaptive_bezier/index.html#PAGE_ADAPTIVE_BEZIER
Do you know where I can get the source code of SunGraphics2D, so I could investigate more this issue?
# 12
Ya, you're right, it looks bad. They did a good job
on the 4 point bezier curve.
Try setting the bounds on the returned bounding box as:
return new Rectangle2D.Double(minX, minY, Math.ceil(maxX-minX), Math.ceil(maxY-minY));
If it's still outside the box, try adding 1 to the width and height. It's
probably just the antialiasing going outside the box.
One note about the code posted to compute the bounding box,
the following code is wrong:
double maxX = Double.MIN_VALUE, maxY = Double.MIN_VALUE;
It should be -Double.MAX_VALUE. MIN_VALUE is actually just the
smallest non-zero positive number. Java should have came up
with a different name, because this is a common mistake.
# 13
While your idea helps to keep the curve into the bounds, it does not provide the exact bounds of the painted curve. If you want to see the problem in action, you can try the webstart program here: https://jcanvas.dev.java.net/
Draw a Bezier curve and select it. Then resize and/or move it. You will see that the curve exceeds often the selection rectangle. As well, the rectangle should have the same size as the real bounds of the curve.
Note that I would be happy to have a solution that get the visible bounds of the curve even with AA off. Does someone have a working solution?
# 14
You will have to account for the stroke width when computing the bounding box then. So if the stroke width is 10, then you need to account that the overall size of the bounding box should be increased by 10, and translated -5, -5.
If you want the exact exact bounds, then it becomes a lot more complicated.
Another idea that is simpler is to first compute the bounds, then set the clipping area of the graphics object to be the rectangle, then draw the curve.
I took a lot at your app. It looks good. For that type of app, I am sure your users won't care about the small details like if the antialiasing on the curve going outside the rectangle.
One suggestion, I found that it was difficult to terminate the bezier curve where I wanted to. I had to double click a new point that I didn't want. Try allowing a right click to terminate.
# 15
> You will have to account for the stroke width when
> computing the bounding box then.
Right. Actually, I'm only worried with the simpler case where the stroke is 1 and AA off.
> I took a lot at your app. It looks good.
I'm happy that you use JCanvas; just don't forget to respect the LGPL license.
For that
> type of app, I am sure your users won't care about
> the small details like if the antialiasing on the
> curve going outside the rectangle.
Note that the curve can exceed its selection rectangle even if AA is tuned off. Also, I want to explore all the problem space before convincing myself that this is not really important.
As another mean to compute the exact exact bounds, I tried this:
new Area(myPath2D).getBounds2D()
wihtout more succes however...
> One suggestion, I found that it was difficult to
> terminate the bezier curve where I wanted to...
Thanks for your comments, I noted it. I would be more than happy to talk futher with you about this project on the jcanvas dev mailing list.
# 16
Hi,
> You will have to account for the stroke width when
> computing the bounding box then. So if the stroke
if this is the problem, you can create the outline of the stroke by calling
BasicStroke.createStrokedShape(). Then you can get the bounds for the generated shape.
bye
Marcus
