Script to make a bezier line segment touch several specified 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”.


#21

John: the Excel solution seems to be mostly working… I tend to get some glitches with P2 not being -quite- on the spline (is there a type in there somewhere or is it just a bug in Excel?). Also, I see what you mean about the t values, but what method would you use to make the third internal point value control the other 2?

Tz: I haven’t had a chance to take a look at the results of your script yet, hopefully tonight or tomorrow. It -looks- like it should work, but I’ll have to take a closer look. I’ll see if I can figure it out.


#22

i think the imperfection isn’t a bug but it’s propagation of approximated error, infact, if you change the t for “control Pc2” you can have a best solution.
To find now the trirth point i don’t know… you must try to find it with a search algorithm.
Now i’m try to utilize the OLS (http://en.wikipedia.org/wiki/Least_squares) because if you put 5 or more point you can build a nice Bezier Curve.

I also tryed to ask this problem in a lot of “Math’s” forum but no one ask me… there is a mathematician when he’s necessary ???


#23

i fixed 2 mistakes in your code


#24

Thanks Denis,
Now it’s working perfectly :slight_smile:
I think Vincent had the same problem in his code, but I don’t have time to check it right now
Cheers.


#25

Wow, thanks guys, that’s exactly what I needed, and very impressive! You are all unbelievably awesome, and have given me great inspiration to continue improving my own skills. In high school and college I put only the minimal required effort into my math classes, and it’s only recently that I have taken an interest in learning this kind of stuff on my own. I’m going to strive to understand how and why the formulas here work, rather than just copying and pasting the code like a black box.

On an unrelated note, I just noticed that the people who have contributed to this thread are from all over the world. The U.S., Israel, Canada, Denmark, Italy (and Singapore, counting the original C programmer). I suppose that’s not really all that unusual, but it did get me thinking. Tomorrow is Independence Day here in the U.S., a day for taking pride in my country. But I also feel proud to be part of a such a great global community as the one we have here!


#26

i’m from Russia :wink:


#27

Ah really? I just saw that it said New York. Of course in the U.S. are people of every heritage in the world, otherwise I might have guessed your country by your name. :slight_smile:


#28

for who wants to play with 4Points Bezier Spline:


/* 
	Original C code Author : Vincent Tan Wai Lip
	URL : http://polymathprogrammer.com
*/	

try (destroyDialog FourPoints_Rol) catch ()

global FourPoints_Pos = if FourPoints_Pos == undefined then [200,200] else FourPoints_Pos
global FourPoints_Set = if FourPoints_Set == undefined then [1,2]/3 else FourPoints_Set
	
rollout FourPoints_Rol "Four Points Bezier Curve"
(
	spinner sp_u "u: " fieldwidth:50 range:[0.001,FourPoints_Set.y-0.001,FourPoints_Set.x] scale:0.001 align:#right offset:[4,0]
	spinner sp_v "v: " fieldwidth:50 range:[FourPoints_Set.x+0.001,0.999,FourPoints_Set.y] scale:0.001 align:#right offset:[4,0]
	
	button create_bt "Create" width:100 align:#left offset:[-4,0] across:2
	button reset_bt "Reset" width:100 align:#right offset:[4,0]

	fn interpolate pts u:0.33 v:0.66 =
	(
		if u > 0 and u < 1 and v > 0 and v < 1 and u < v do
		(
			a = 3*(1-u)^2*u
			b = 3*(1-u)*u^2
			c = 3*(1-v)^2*v
			d = 3*(1-v)*v^2
			
			det = a*d - b*c
			
			q1 = pts[2] - (1-u)^3*pts[1] - u^3*pts[4]
			q2 = pts[3] - (1-v)^3*pts[1] - v^3*pts[4]
			
			d0 = (d*q1 - b*q2)/det
			d1 = (a*q2 - c*q1)/det
				
			#(d0,d1)
		)
	)
	
	local csize = units.decodevalue "20m", psize = units.decodevalue "0.5m"
	local pts = #([0,0,0],[csize/3,0,0],[2.*csize/3,0,0],[csize,0,0])
	local vec = #([0,0,0],[csize,0,0])
	
	fn updateCurve = if iskindof (sp = getnodebyname "Four_Points") SplineShape and sp.children.count == 4 do 
	(
		pts = for c in sp.children collect c.pos
			
		setKnotPoint sp 1 1 pts[1]
		setInVec sp 1 1 pts[1]
		setKnotPoint sp 1 2 pts[4]
		setOutVec sp 1 2 pts[4]

		if (v = interpolate pts u:FourPoints_Set.x v:FourPoints_Set.y) != undefined do
		(
			vec = v
			setOutVec sp 1 1 vec[1]
			setInVec sp 1 2 vec[2]
		)
		updateShape sp
	)
	on create_bt pressed do undo "Create Bezie System" on
	(
		if (sp = getnodebyname "Four_Points") != undefined do delete $Four_Points/...*
		
		sp = splineShape name:"Four_Points" adaptive:on optimize:off pos:pts[1] --wirecolor:orange
		
		addNewSpline sp
		
		addKnot sp 1 #bezierCorner #curve pts[1] pts[1] vec[1]
		addKnot sp 1 #bezierCorner #curve pts[4] vec[2] pts[4]
		
		pp = for k=1 to 4 collect
		(
			point name:("p" + k as string) pos:pts[k] parent:sp size:psize constantscreensize:on wirecolor:green
		)
		when transform pp change id:#bezier_system handleAt:#redrawViews do updateCurve()
	)
	
	on reset_bt pressed do
	(
		uv = [1,2]/3
		
		sp_u.value = uv.x
		sp_u.range.y = uv.y - 0.001
		sp_v.value = uv.y
		sp_v.range.x = uv.x + 0.001
		
		FourPoints_Set = uv
		updateCurve()
	)
	
	on sp_u changed val do 
	(
		FourPoints_Set.x = val
		sp_v.range.x = val + 0.001
		updateCurve()
	)
	on sp_v changed val do 
	(
		FourPoints_Set.y = val
		sp_u.range.y = val - 0.001
		updateCurve()
	)

	on FourPoints_Rol open do 
	(
	)
	on FourPoints_Rol close do FourPoints_Pos = getdialogpos FourPoints_Rol
) 
createDialog FourPoints_Rol width:220 pos:FourPoints_Pos

… just drag the points


#29

Great stuff! So now all that remains is getting it to use the specific value for T that will force the line to hit an additional point (although suddenly looking at it I wonder if it doesn’t need to be 2 points?)


#30

Just jumping in here and might be missing a point. I have just been writing bezier functions in Max script using Cubic interpolation.

Since you are looking to create a spline that passes through a start p0, an end p4 and three points between I think that you will find that it can’t be done with a Cubic, ie; p0 to p3 through p1 and p2.

In your example if you were to move the middle point, p2, perpendicular to the line p1 to p3 it would not be possible to interpolate through it with the four points of your bezier curve in Max.

I’m not quite sure how to go about your problem how ever without sampling the solution. My problem is I don’t understand the notations used in all the Max sites. I put this together the other day as I was working on it. http://www.paulneale.com/tutorials/bezierCurves/quadraticVSbezierCurve.mov I don’t know if it will help at all.


#31

My last post was way behind the discussion as I didn’t see the second page. I’m going to have a poke at how this worked. Looks interesting.


#32

Anyone have any ideas on a 5-point solution??


#33

This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.