Script to make a bezier line segment touch several specified points?


#1

To preface, I’m speaking here as someone who is not any kind of math genius.

What I want to make is a script where, taking 2 ends of a bezier spline segment, and specifying several points between, the bezier in/out handles will be adjusted such that the spline segment touches all the intervening points. If I have figured this correctly, it should be theoretically possible to make the spline segment touch up to 3 specified points (with some restrictions on where those points can be.)

I’ve figured out several ways to access and manipulate a spline’s bezier curve data, and plan on building a matrix based on the 2 splines ends and the world up vector. So, just assuming that end points A and B of a spline segment are laying flat along the x-axis, what kind of formula do I need to control the bezier curve to touch the points?


#2

could you give us some more information, maybe draw an example and post the image?


#3

Okay, here’s the setup I’m looking for: What I have are a spline segment, and 3 points. What the script does is move the bezier handles to where they have to be in order to hit those points.


#4

Someone pointed me to this link. I’m trying to figure it out but it makes my head spin. Can anyone figure out a way to “reverse engineer” the formula shown into MaxScript?

http://en.wikipedia.org/wiki/Bézier_curve


#5

That article is only to understand how the bezier curve is constructed. Then, to make it go through a number of given points, you’re going to need a polynomial interpolation formula
then you’ll need to figure out how to put both formulas together and code it in maxscript.

Sounds like a nice challenge


#6

hmm, I dont know, is that possible that you build an other type of curve and then convert it to bezier? Because in some other type of curves the points are actually representing the curve knot points.

Edit
yes indeed its possible, after creating the spline just cycle through the curve’s knot points with SetKnotType command, where you should use #bezier as the type.

piece of cake!

:wink:


#7

Wait what? Sorry LB, you lost me there…

I think you’re under the impression that I want to divide up my spline segment using additional spline knots, which I don’t. I want to move ONLY the bezier handles, and by doing so make the spline segment intersect the reference points.

Unless I am completely misunderstanding you, in which case I will need some clarification. :slight_smile:


#8

in my understanding there are points in which trough you need to have a bezier spline. This is your target. This is your end result. Am I right?

now, that, how you define the points in between those two endpoints is an other story. On end I you just have a bezier spline.

However if you want to manually move the bezier control points on the ends then you need an other method.

Still if you only need the bezier spline on the end, without bothering with the controll points then my method is just perfect for you and all bezier contoll points will be on the right place along with the knots.

just for clarification here is the method.

you have the points, in which through we can draw a general spline with as many knots and segments as we want. So if your original spline has two segments then you draw segments. through the knots. You can also check which segment belongs to which knots.
So we can conclude that segments and point count doesn’t matter.

Next, so we have the spline with the knots, and segments or segment. Now we cycle trough all of these points and convert them to bezier knots, and then we update the shape and what we have a nice bezier spline which goes exactly through the control points. So it have exactly that much knots plus the two endpoints, exactly the same amount of segments etc.
Plus we dont need to bother with the bezier controll points, which is quite a complicated task.


#9

My ultimate goal in doing this is to have as few points in the spline as possible, and control the shape using the bezier handles instead.

So I will take an existing spline with many points, and run the script. Then I select which of the points I want to keep, and it 3 additional points in between for each set to use as references for the bezier handles. Then a new spline will be created, with an appoximation of the original spline, but with many fewer points on it (for example,12 points instead of 45).

So, what you’re talking about is more or less the opposite of what I am trying to do…


#10

in the last pot basically what you talking about is a spline simplification, nothing more. I dont understand how your first post and the images connected toghether. Spline simplification you can find in this forum. Good luck with it.


#11

I’ve found a couple of other spline optimization scripts, but I don’t really like the results they get. Hence, writing my own. But I need to understand better the relationship between the bezier controllers and the spline segments they control. So, I’m reading up on it.

In the meantime, I’d be thankful for any help anyone can offer!


#12

Convert 4 point in Bezier curve isn’t simple and the cubic interpolation is not easy way.
Try to understand this: http://www.tinaja.com/glib/bez4pts.pdf
in the exemple he convert a 4 Bezier’s point ( p0 and p3 are the point , p1 and p2 the control point) into 4 polinomial point ( p0 and p3 are the same point and p4 and p5 the new interpolated point )


#13

You can’t draw a Cubic Bezier curve with only 4 point because there are infinite curve; simple exemple with windows “paint.exe” ( the paint’s curve are a Bezier cubic curve):

You must also define the angle of tangent of first and last point.
I think you can write a script what inputs are: 4 points and 2 tangents (es only angle) and after with a recursive search algorithm you can search the the best tangent’s length (p2-p1 and p3-p4). Or you can write a script that lenght tangent are fixed and it search the best tangents angle.
But in both case to find the exact Bezier’s control point are very difficult…
the more simple algorithm to find a value in a range is the binary algorithm:
http://en.wikipedia.org/wiki/Binary_search_algorithm
In attachment i put a simple bezier curve with 4 control points


#14

Hmm… I’m afraid I really didn’t understand what you were trying to show me with the excel file. I can see that you’re making bezier curves with a sequence of points, but beyond that I’d need a little more explanation.

One thing I should point out, is that in the picture you included in the last post looks like it shows only 2 intermediate points rather than 3 as in the case I am working with. After some testing I found that there still do seem to be an infinite number of curves that will intersect 3 points using only 2 points and their handles, but maybe the attached file will help to show what I am trying to do.

The frozen light-blue spline represents the original spline I am trying to emulate, the points are selected points along that spline (which here happen to be the same as the ones used to build it.) The dark blue spline is the one I want to manipulate to match the light blue spline.

The green coordinates text represents the location of the bezier in and out controllers (the yellow and red text represent the length and angle of the handles respectively). And I’m considering that what I probably want is the shortest possible spline segment that still hits the points. Any alternate curves that I tried which still matched the points but were not what I was looking for, seemed to result in a longer spline segment.


#15

ah ok, 5 points define only one bezier cubic curve…
I search in internet but i find nothing, i found only an exemple of search algorithm for a quadratic bezier (one control point or 2 control point in the same position)
http://www.physicsforums.com/showthread.php?t=180711
I think is the only way:
1th step: put a random control points (p1 p2)
2th step: calculate the minimum distance from curve to each intermediate points ( i call Dmin)
3th step: update the two control points with some algoritm (this is the most important thing)
4th step: go to 1th step
end step: when Dmin^2 is minimized
this algorithm is :link


#16

Hey, I’ve updated the last scene to include the intermediary points and lines for finding the bezier curve. I find this much simpler to understand than the mathematical generalization, and it also takes advantage of the fact that, hey, Max already uses bezier curves.

So now that I see and understand how this is done (i.e. how points along a bezier spline are determined from the initial points), I’m more convinced than ever that it can be made to work backwards.

For the next step:

If 3 of the 4 bezier control points (i.e. both line vertices and one of the bezier handles) are determined to begin with, a curve can be created showing all possible locations the remaining bezier handle is allowed to be, as illustrated below (in actuality this would continue to trail off in both directions, but in most practical circumstances I don’t think that it will be necessary to go very far). Any suggestions on a formula for what I’ve shown here?


#17

Actually, I just found a link to someone who figured out how to solve the math issues in C. Is there anyone knowledgeable enough to build a MaxScript based on the provided formula whereby, as the target points are moved, the bezier handles adjust themselves accordingly?

EDIT: Right, it would help to include that link, wouldn’t it?

http://polymathprogrammer.com/2007/06/27/reverse-engineering-bezier-curves/


#18

uhm, interesting, at weekend i try to create the script.


#19

here is my go on this according to Vincent Tan Wai Lip’s work

/* 
	Original C code Author : Vincent Tan Wai Lip
	URL : http://polymathprogrammer.com
	
	Maxscript Author: Matan Halberstadt
	URL : http://www.snowballvfx.com
*/

try (destroyDialog roll_ReverseBezier) catch ()
rollout roll_ReverseBezier "Reverse engineering Bezier curves"
(
-- Local Variable Declerations
------------------------------------------
	
	local ROLL_WIDTH = 250
	local spl

-- User Interface
------------------------------------------
	
	spinner spnU "u:" range:[0,1,1.0/3] align:#center scale:0.001
	spinner spnV "v:" range:[0,1,2.0/3] align:#center scale:0.001
	
	pickButton pbn1 "Pick point 1" width:(ROLL_WIDTH - 10) autoDisplay:true
	pickButton pbn2 "Pick point 2" width:(ROLL_WIDTH - 10) autoDisplay:true
	pickButton pbn3 "Pick point 3" width:(ROLL_WIDTH - 10) autoDisplay:true
	pickButton pbn4 "Pick point 4" width:(ROLL_WIDTH - 10) autoDisplay:true

-- Functions
------------------------------------------

	fn interpolate pts u v =
	(
		if u <= 0.0 or u >= 1.0 or v <= 0.0 or v >= 1.0 or u >= v then
			undefined
		else (
			local a = 3.0 * (1 - u)^2 * u
			local b = 3.0 * (1 - u) * u^2
			local c = 3.0 * (1 - v)^2 * v
			local d = 3.0 * (1 - v) * v^2
			
			local det = a * d - b * c
			
			if det == 0.0 then
				undefined
			else (
				local q1 = pts[2] - (1 - u)^3 * pts[1] + u^3 * pts[4]
				local q2 = pts[3] - (1 - v)^3 * pts[1] + v^3 * pts[4]
				
				pts[2] = (d * q1 - b * q2) / det
				pts[3] = (a * q2 - c * q1) / det
				
				pts
			)
		)
	)
	
	fn updateSpline =
	(
		local objs = for o in #(pbn1, pbn2, pbn3, pbn4) where isValidNode o.object collect o.object
		if objs.count == 4 then (
			local u = spnU.value
			local v = spnV.value
			
			local pts = for o in objs collect o.pos
			pts = interpolate pts u v
			
			if pts != undefined then (
				if spl == undefined then (
					spl = splineShape()
					spl.adaptive = true
					spl.optimize = false
					
					addNewSpline spl
					addKnot spl 1 #bezierCorner #curve pts[1] pts[2] pts[2]
					addKnot spl 1 #bezierCorner #curve pts[4] pts[3] pts[3]
				) else (
					setKnotPoint spl 1 1 pts[1]
					setInVec spl 1 1 pts[2]
					setOutVec spl 1 1 pts[2]
					
					setKnotPoint spl 1 2 pts[4]
					setInVec spl 1 2 pts[3]
					setOutVec spl 1 2 pts[3]
				)
				
				updateShape spl
				forceCompleteRedraw()
			)
		)
	)
	
	fn openDialog =
	(
		createDialog roll_ReverseBezier width:ROLL_WIDTH
	)

	fn init =
	(
		if selection .count > 0 then
			pbn1.object = selection[1]
		if selection .count > 1 then
			pbn2.object = selection[2]
		if selection .count > 2 then
			pbn3.object = selection[3]
		if selection .count > 3 then
			pbn4.object = selection[4]
		
		updateSpline()
	)

	fn done =
	(
		gc light:true
	)

-- Event Handlers
------------------------------------------

	on spnU changed val do updateSpline()
	on spnV changed val do updateSpline()
	
	on pbn1 picked obj do updateSpline()
	on pbn2 picked obj do updateSpline()
	on pbn3 picked obj do updateSpline()
	on pbn4 picked obj do updateSpline()
	
	on roll_ReverseBezier open do init()
	on roll_ReverseBezier close do done()

) -- end of rollout

roll_ReverseBezier.openDialog()

but I’m afraid it’s still not exactly what you’re looking for :shrug:

EDIT: looks like it’s working only in extreme u, v values


#20

This is the same solution but in Excell
You can see that the problem is the pre-assignment of number t for the two internal points.
If you put a 3th internal point you can re-calculate the two “t”.