View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# Inaccurate y values in the distance function for Bezier clipping

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

No replies to this topic

### #1Zorrent  Members

Posted 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.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.