•      Sign In
• Create Account

# Zorrent

Member Since 20 Dec 2011
Offline Last Active Apr 22 2012 09:12 PM

### Inaccurate y values in the distance function for Bezier clipping

17 April 2012 - 06:54 PM

I'm currently working on implementing a curve intersection algorithm known as Bezier clipping, which is described towards the end of this article. I've been following through the article and source code (which can be found here) to implement it myself. A central part of this algorithm is the calculation of a "distance function" between curve2 and the baseline (a line running from start point to end point) of curve1. This seems to be where I've run into some trouble. When I draw out the distance function, the curve isn't anywhere near the other two curves, despite both clearly intersecting.

From what I can gather from the article (and my understanding could quite possibly be wrong), the calculation of the distance function is as follows.

The baseline is represented in the form x*a + y*b + c = 0, where a2 + b2 = 1. The coefficients a, b and c are calculated by rearranging the representation y = u*x + v, where u is the slope of the baseline ((y2 - y1)/(x2 - x1)), and x and y are any coordinate pairs that lie on the baseline. The formula can then be rearranged to v = y - u*x, and then rearranged to -u*x + 1*y - v = 0, meaning that a = -u, b = 1, and c = -v. To assure a2 + b2 = 1, all three coefficients are divided by a scalar of Math.sqrt(u2 + 1). This function is then substituted into the parametric formula of curve2, resulting in a bezier curve with Yi = a*xi + b*yi + c (where xi and yi are the control points of curve2)and Xi = (1 - t)3*y1 + 3*( - t)2*t*y2 + 3*(1 - t)*t2*y3 + t3*y3 for t = {0, 1/3, 2/3, 3}.

Below are some excerpts from the code of the example program on the article (written in a language called Processing) which, oddly, uses a slightly different approach to calculating the alternative representation of the curve,:

```	/**
* Set up four points, to form a cubic curve, and a static curve that is used for intersection checks
*/
void setupPoints()
{
points = new Point[4];
points[0] = new Point(85,30);
points[1] = new Point(180,50);
points[2] = new Point(30,155);
points[3] = new Point(130,160);

curve = new Bezier3(175,25,  55,40,  140,140,  85,210);
curve.setShowControlPoints(false);
}

...

flcurve = new Bezier3(points[0].getX(), points[0].getY(),
points[1].getX(), points[1].getY(),
points[2].getX(), points[2].getY(),
points[3].getX(), points[3].getY());

...

void drawClipping()
{
double[] bounds = flcurve.getBoundingBox();

// get the distances from C1's baseline to the two other lines
Point p0 = flcurve.points[0];
// offset distances from baseline
double dx = p0.x - bounds[0];
double dy = p0.y - bounds[1];
double d1 = sqrt(dx*dx+dy*dy);
dx = p0.x - bounds[2];
dy = p0.y - bounds[3];
double d2 = sqrt(dx*dx+dy*dy);

...

double a, b, c;
a = dy / dx;
b = -1;
c = -(a * flcurve.points[0].x - flcurve.points[0].y);
// normalize so that a² + b² = 1
double scale = sqrt(a*a+b*b);
a /= scale; b /= scale; c /= scale;

// set up the coefficients for the Bernstein polynomial that
// describes the distance from curve 2 to curve 1's baseline
double[] coeff = new double[4];
for(int i=0; i<4; i++) { coeff[i] = a*curve.points[i].x + b*curve.points[i].y + c; }
double[] vals = new double[4];
for(int i=0; i<4; i++) { vals[i] = computeCubicBaseValue(i*(1/3), coeff[0], coeff[1], coeff[2], coeff[3]); }

translate(0,100);

...

// draw the distance Bezier function
double range = 200;
for(float t = 0; t<1.0; t+=1.0/range) {
double y = computeCubicBaseValue(t, coeff[0], coeff[1], coeff[2], coeff[3]);
params.drawPoint(t*range, y, 0,0,0,255); }

...

translate(0,-100);
}

...

/**
* compute the value for the cubic bezier function at time=t
*/
double computeCubicBaseValue(double t, double a, double b, double c, double d) {
double mt = 1-t;
return mt*mt*mt*a + 3*mt*mt*t*b + 3*mt*t*t*c + t*t*t*d; }```

And below is the source code (written in Java) for my attempt to recreate the above process:

```import java.awt.BasicStroke;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;

import javax.swing.JPanel;

public class ReplicateBezierClippingPanel extends JPanel {

CubicCurveExtended curve1, curve2;

public ReplicateBezierClippingPanel(CubicCurveExtended curve1, CubicCurveExtended curve2) {

this.curve1 = curve1;
this.curve2 = curve2;

}

public void paint(Graphics g) {

super.paint(g);
Graphics2D g2d = (Graphics2D) g;
g2d.setStroke(new BasicStroke(1));
g2d.setColor(Color.black);
drawCurve1(g2d);
drawCurve2(g2d);
drawDistanceFunction(g2d);

}

public void drawCurve1(Graphics2D g2d) {

double range = 200;

double t = 0;

double prevx = curve1.x1*(1 - t)*(1 - t)*(1 - t) + 3*curve1.ctrlx1*(1 - t)*(1 - t)*t + 3*curve1.ctrlx2*(1 - t)*t*t + curve1.x2*t*t*t;
double prevy = curve1.y1*(1 - t)*(1 - t)*(1 - t) + 3*curve1.ctrly1*(1 - t)*(1 - t)*t + 3*curve1.ctrly2*(1 - t)*t*t + curve1.y2*t*t*t;

for(t += 1.0/range; t < 1.0; t += 1.0/range) {

double x = curve1.x1*(1 - t)*(1 - t)*(1 - t) + 3*curve1.ctrlx1*(1 - t)*(1 - t)*t + 3*curve1.ctrlx2*(1 - t)*t*t + curve1.x2*t*t*t;
double y = curve1.y1*(1 - t)*(1 - t)*(1 - t) + 3*curve1.ctrly1*(1 - t)*(1 - t)*t + 3*curve1.ctrly2*(1 - t)*t*t + curve1.y2*t*t*t;

g2d.draw(new LineExtended(prevx, prevy, x, y));

prevx = x;
prevy = y;

}

}

public void drawCurve2(Graphics2D g2d) {

double range = 200;

double t = 0;

double prevx = curve2.x1*(1 - t)*(1 - t)*(1 - t) + 3*curve2.ctrlx1*(1 - t)*(1 - t)*t + 3*curve2.ctrlx2*(1 - t)*t*t + curve2.x2*t*t*t;
double prevy = curve2.y1*(1 - t)*(1 - t)*(1 - t) + 3*curve2.ctrly1*(1 - t)*(1 - t)*t + 3*curve2.ctrly2*(1 - t)*t*t + curve2.y2*t*t*t;

for(t += 1.0/range; t < 1.0; t += 1.0/range) {

double x = curve2.x1*(1 - t)*(1 - t)*(1 - t) + 3*curve2.ctrlx1*(1 - t)*(1 - t)*t + 3*curve2.ctrlx2*(1 - t)*t*t + curve2.x2*t*t*t;
double y = curve2.y1*(1 - t)*(1 - t)*(1 - t) + 3*curve2.ctrly1*(1 - t)*(1 - t)*t + 3*curve2.ctrly2*(1 - t)*t*t + curve2.y2*t*t*t;

g2d.draw(new LineExtended(prevx, prevy, x, y));

prevx = x;
prevy = y;

}

}

public void drawDistanceFunction(Graphics2D g2d) {

double a = (curve1.y2 - curve1.y1)/(curve1.x2 - curve1.x1);
double b = -1;
double c = -(a*curve1.x1 - curve1.y1);

double scale = Math.sqrt(a*a + b*b);

a /= scale;
b /= scale;
c /= scale;

double y1 = a*curve2.x1 + b*curve2.y1 + c;
double y2 = a*curve2.ctrlx1 + b*curve2.ctrly1 + c;
double y3 = a*curve2.ctrlx1 + b*curve2.ctrly2 + c;
double y4 = a*curve2.x2 + b*curve2.y2 + c;

double range = 200;
double t = 0;
double prevx = t*range;
double prevy = (1 - t)*(1 - t)*(1 - t)*y1 + 3*(1 - t)*(1 - t)*t*y2 + 3*(1 - t)*t*t*y3 + t*t*t*y4;

for(t += 1.0/range; t < 1.0; t += 1.0/range) {

double x = t*range;
double y = (1 - t)*(1 - t)*(1 - t)*y1 + 3*(1 - t)*(1 - t)*t*y2 + 3*(1 - t)*t*t*y3 + t*t*t*y4;

g2d.draw(new LineExtended(prevx, prevy, x, y));

prevx = x;
prevy = y;

}
}

}```

Where CubicCurveExtended and LineExtended are simple extensions of CubicCurve2D.Double and Line2D.Double. Curves 1 and 2 are rotated so that the slope of curve1's baseline is zero before they are passed into the constructor. The output for this panel for curve1 defined as (485, 430, 580, 60, 430, 115, 530, 160) and curve2 (575, 25, 455, 60, 541, 140, 486, 210) defined as is shown below (the distance function is the curve in the upper left corner):

As you can see, the distance function is nowhere near the two curves, despite both clearly intersecting. I recognize I may need to calculate the x values at intervals of the baseline rather than the function itself, but what I'm really confused about is the y values. I've been working at this for a while with no luck. If someone could explain to me why the y values are so far off, I'd be extremely grateful. Sorry if this is in the incorrect forum or the question is generally not suitable for this site.

### Issues with Bezier Clipping

20 December 2011 - 06:59 PM

Hello. I'm currently working on an experimental graphics API idea I had and have run into some trouble with an algorithm called bezier clipping (an algorithm for finding points of intersection between two bezier curves).

Up to this point I had been teaching myself what I need to know to implement this algorithm. I've written out the code, but there seems to be an error. I'm not completely sure where this is, but I believe it's to do with the convex hull. The two articles I looked at didn't go into great detail about this portion of the algorithm, and I'm not entirely sure I've defined it correctly.

Here's a rough outline of my algorithm:
•A line from start to end point of curve one is defined, along with two parallel lines of the same length that bound the curve.
•A new curve called a distance function is defined using the y values of curve 2's points and x values that are at 0/3, 1/3, 2/3 and 3/3 of the previously defined baseline.
•The convex hull of the distance function is defined by drawing two lines from the start point of the curve to the control points, and then two lines from the endpoint of the distance function to the control points.
•A loop goes over each convex hull line, with an inner loop that checks the current convex hull line for intersection against the two outer bounding lines
-While the loop is checking the first two convex hull lines for intersection (which originate from the start point of the distance function) the lowest value is kept; while checking the final two convex hull lines (which originate from the endpoint of the distance function), the highest value is kept.

As I said, I'm unsure if I've correctly defined the convex hull. I've tried switching the start points of the final lines from the endpoint to the control points, but that didn't seem to correct the problem. I've been at this algorithm for a while now, and I'd really appreciate any help (or even a link that could help me out which I somehow missed in the searches I've done) at this point. Thank you for your time.

Edit: Nevermind. I've found a very specific way to define a convex hull.

PARTNERS