next »

[Hima]

I've been wondering about how to do a curving and continuous laser like this. The keyword I found on a Japanese website is 'Poly Line' but I still don't get it   I think you have to use 3D somehow? Is that how ZUN did with his new curvy lasers in the new Touhou's?

Thank you in advance!

[Zaphos]

A "poly-line" is just a bunch of little straight line segments chained together to make a smooth curve.

What you'll usually use to draw a curve is a parametric formula for generating points on the curve.  In other words, some function that you can pass a time t, and it'll say "at time t, you should be at position x,y,z".  Or, in code:

Code:

vec3 sampleCurve(float t) {
  return vec3(t,t^2,0); // put whatever formula you want here
}

Then you can draw your curve by just calling that function for increasing values of "t":

Code:

for (float t = 0; t < 1; t += .01) {
  vec3 p1 = sampleCurve(t);
  vec3 p2 = sampleCurve(t+.01);
  drawLine(p1,p2);
}

Now the only question is, what's a good function to put in "sampleCurve"?

The simplest and least-interesting sampleCurve formula is "linear interpolation," or "lerp," which just gives you a straight line between two points.  This function looks like this:

Code:

// cp1 and cp2 are the two end points of the line
// I call them the "control points" of the curve
vec3 lerp(vec3 cp1, vec3 cp2, float t) { 
  vec3 dir = cp2-cp1;
  return cp1 + t * dir;
}

We can use this function as a building block to make a nicer, smoothly bending curve.

A common formula you may want to try out is the "quadratic bezier curve".  You use this when you want to get from point a to point c, but you want to curve towards point b in-between.  The function looks like this:

Code:

void quad_bezier(vec3 cp1, vec3 cp2, vec3 cp3, float t) {
  lerp(  lerp(a,b,t),  lerp(b,c,t),  t);
}

Looking at this function you can see what it's doing: it start out moving along the "directly from a to b" line, then uses a lerp to gradually switch to moving along the "directly from b to c" line.

You can add get even more control over the bezier curve by doing a "cubic" bezier curve instead: just do lerp(quad_bezier(a,b,c,t),quad_bezier(b,c,d,t),t);  And you can keep going -- a lerp of two cubic beziers is a 4th-order bezier, and a lerp of two 4th-orders is a fifth order bezier ... usually people stop at cubic though

[bateleur]

Further to Zaphos' excellent guide, it's worth noting that Bezier curves of this kind have some very nice properties.

In particular, a quadratic bezier quad_bezier(a,b,c) has a gradient at point a which exactly matches the line a -> b and similarly the gradient at c matches b -> c. This is great, because it means that the "chaining together" Zaphos describes is automatically nice and smooth without any need to do arcane calculus to work out whether you have a gradient match.

(Flash uses quadratic bezier curves for all of its 2D curve drawing, for example.)

[drChengele]

Hey, this will come in handy in the near future.

Thank you.

[Hima]

Wow, thank you so much. I've never thought it'll be as easy as that. I'll try my hand on bezier curve. Let's see if I can apply this to 3D :D

[J. Kyle Pittman]

Bezier curves are definitely the way to go here.  I implemented a "curvy laser" in Arc as a single Bezier curve (two endpoints and two intermediate control points).  The trickiest part as I recall was making the beam appear to be the correct width from any viewing angle.  To do this, I passed in a reference to the player's camera so that I could billboard the laser at each segment.

This is some of the code I used for writing to the vertex stream:

Code:

// ...lock dynamic vertex stream to PosVerts[] array...

for (int i = 0; i < NumSegments; ++i)
{
	int VertIndex = i * 2;

	// t is the position along the Bezier curve, in the range [0,1]
	float t = float(i) / float(NumSegments);

	Vector3 ThisPos = MyBezier.EvalPos(t);
	Vector3 ThisTan = MyBezier.EvalTan(t);

	// To find the beam's normal at this point,
	// take the cross product between the beam's tangent at this point
	// and the direction from the camera's eye to this point.
	Vector3 ThisNorm = Normalize(Cross(
		Normalize(ThisTan),
		Normalize(ThisPos - PlayerCamera->GetPos())));

	PosVerts[VertIndex] =   ThisPos + (ThisNorm * BeamWidth);
	PosVerts[VertIndex+1] = ThisPos - (ThisNorm * BeamWidth);
}

// ...unlock dynamic vertex stream and render...

And for reference, my EvalPos() and EvalTan() functions look like this:

Code:

// Where p[4] is a fixed-size array of the four control points,
// and a, b, and c are pre-calculated coefficients:
// c = (p[1] - p[0]) * 3.0f;
// b = ((p[2] - p[1]) * 3.0f) - c;
// a = p[3] - p[0] - c - b;

Vector3 EvalPos(float t) const
{
	return ((a*t + b)*t + c)*t + p[0];
}

Vector3 EvalTan(float t) const
{
	return (a*t*3.0f + b*2.0f)*t + c;
}

This method works pretty well from most viewing angles, but it does have some artifacts when the beam is pointing directly at the camera.



As the beam begins to align with the camera, you can see the individual segments start to appear as their triangles overlap.



And finally, they start jutting out in crazy directions.



I did a few experiments with fading out the beam at segments which were near-parallel with the camera's facing vector, but I never landed on anything I was totally happy with, so ultimately I just decided to accept this artifact.

[skyy]

Another vote for Bezier curves. Simple to use in most cases and gives the nice continuity(eh, did I get the word right?). Epic screenshots there.

[Zaphos]

In particular, a quadratic bezier quad_bezier(a,b,c) has a gradient at point a which exactly matches the line a -> b and similarly the gradient at c matches b -> c. This is great, because it means that the "chaining together" Zaphos describes is automatically nice and smooth without any need to do arcane calculus to work out whether you have a gradient match.

(Flash uses quadratic bezier curves for all of its 2D curve drawing, for example.)

Oh, I didn't actually describe "chaining together" of separate bezier segments (which is what you're thinking of, I think?); I described how to make a single "higher-order" bezier.  But you're right that beziers make chaining easy

Notes on "chaining together" curves:
For efficiency, people usually use the lowest order bezier curves they can get away with -- either quadratic or cubic bezier curves.  But with only 3 or 4 control points to work with, those "low-order" bezier curves have limited flexibility.  To draw a more interesting curve, you can glue together several smaller, simpler curves.

Just setting the end-point of the first curve on top of the start-point of the second ensures they connect up.  But to ensure they connect up smoothly -- with no sudden change in direction between the curves -- you need to worry about where you put the neighboring control points as well.  Specifically, if your first curve ends with control points b,c and your second curve starts with control points c,d, then you need to place points b, c, and d all lie on the same line.

Note that for a chain of quadratic bezier curves, moving one control point and keeping the chain smooth may force you to move a whole bunch of control points: the position of the middle control point of one bezier curve affects the middle control points of its neighbors, who affect their neighbors, and so on down the whole chain.  This is one reason people use cubic bezier curves instead: there when you move one control point you'll only ever have to move one more control point to maintain smoothness.

(edit: quick note on terms -- a "chain of bezier curves" like this is called a "bezier spline")

[ChevyRay]

Note that for a chain of quadratic bezier curves, moving one control point and keeping the chain smooth may force you to move a whole bunch of control points: the position of the middle control point of one bezier curve affects the middle control points of its neighbors, who affect their neighbors, and so on down the whole chain.  This is one reason people use cubic bezier curves instead: there when you move one control point you'll only ever have to move one more control point to maintain smoothness.

(edit: quick note on terms -- a "chain of bezier curves" like this is called a "bezier spline")

I was experimenting with this the other day. I had a chain of points that I could move around (see SWF here) and I then just used a quadratic bezier spline to draw it smoothed out (see SWF here) to achieve a ropelike effect. I basically did it like this:



Where the blue represents the original polyline, and the red the bezier curves drawn. Basically, the midpoints of each line segment represent the ends of each of the quadratic beziers, and then I use the endpoints of the polyline segments as the control points for those curves. Then, to finish it off, I just draw straight lines to attach the beginning and end, so it ends up like this:



All the points connect smoothly this way (these diagrams were hand-drawn in paint, so they're a bit off). I don't know if this is a good method or not, I came up with it on my own while just messing around, but are there any good tutorials on doing this with cubic beziers you can point me to? There are a couple problems with this method, mainly that the curve itself doesn't actually intersect any of the original polyline points so if the curve is being used for collision purposes, it could look strange where it's not colliding, and also that the straight lines on the ends sometimes result in odd-looking finishes to the curves. But other than that, it's a pretty easy way to do it.

[Zaphos]

Oh neat, it looks like you re-invented uniform quadratic b-splines.  B-splines are certainly a good method; they're very popular.

For joining together cubic bezier curves in a somewhat automatic way, you just need some way of picking a "tangent" at each control point.  One popular choice is the "catmull-rom spline" ...

[ChevyRay]

Cool thanks, looking that up now.

The points that define a spline are known as "Control Points".  One of the features of the Catmull-Rom spline is that the specified curve will pass through all of the control points - this is not true of all types of splines.

That's sort of what I've been looking for.

[Zaphos]

Cool  Also, if you just wanted to fix the end segments being straight on your original scheme, you could just change the scheme slightly -- skip the straight line segments on the ends, and, for the very first curved segment, instead of using the edge midpoint as the first bezier control point, use the actual first spline control point as your first bezier control point.  (And do the symmetrical thing for the last curve segment and last control point)

[Rob Lach]

Wikipedia has a pretty broad albeit dense article on splines.

[Glaiel-Gamer]

quadratic bezier curves are pretty fun

(click and drag them around)

[ChevyRay]

@Zaphos: Right, I actually didn't think of that. That's probably a better solution than the one I'm doing anyways. Will try it out, thanks.

Wikipedia has a pretty broad albeit dense article on splines.

I gave up.

[TobiasW]

Since this is just tech-talk, I am unsure how relevant it is, but I just found this C++ library and thought I should share it: http://www.geometrictools.com/LibFoundation/Curves/Curves.html

Didn't have time and need to test it yet, but it looks kind of promising

[Rob Lach]

@Zaphos: Right, I actually didn't think of that. That's probably a better solution than the one I'm doing anyways. Will try it out, thanks.

Wikipedia has a pretty broad albeit dense article on splines.

I gave up.

lol.

t = time, or more accurately in this case, how far along between the two points you want to be.
a and b are the points.

[Glaiel-Gamer]

@Zaphos: Right, I actually didn't think of that. That's probably a better solution than the one I'm doing anyways. Will try it out, thanks.

Wikipedia has a pretty broad albeit dense article on splines.

I gave up.

lol.

t = time, or more accurately in this case, how far along between the two points you want to be.
a and b are the points.

nope. t0 through tK is a knot sequence which basically defines how much weight individual control points on a spline in effecting the shape of the final curve (has stuff to do with how many derivatives need to match, etc), and [a,b] is the interval. Splines and curves are all defined 1 dimensionally (i.e. X in relation to T) so you generally need to have 2 curves (one for x in relation to t and one for y in relation to t)

but thanks for trying
(it does get a little confusing when t with a subscript = knots and t without a subscript = time)

[Zaphos]

Knots are points in time; they say when to change the polynomial you're using.

Also, people do define curves in ways other than parametrically; for example there are algebraic curves.

[Rob Lach]

@Zaphos: Right, I actually didn't think of that. That's probably a better solution than the one I'm doing anyways. Will try it out, thanks.

Wikipedia has a pretty broad albeit dense article on splines.

I gave up.

lol.

t = time, or more accurately in this case, how far along between the two points you want to be.
a and b are the points.

nope. t0 through tK is a knot sequence which basically defines how much weight individual control points on a spline in effecting the shape of the final curve (has stuff to do with how many derivatives need to match, etc), and [a,b] is the interval. Splines and curves are all defined 1 dimensionally (i.e. X in relation to T) so you generally need to have 2 curves (one for x in relation to t and one for y in relation to t)

but thanks for trying
(it does get a little confusing when t with a subscript = knots and t without a subscript = time)

Right right. I figured I shouldn't introduce more terminology but you're technically correct on all accounts. In hindsight I probably should have clarified.