Splitting Bezier curves using deCasteljau algorithm...
I am trying to modify my attached Beziers7d program in a way to add a node (adjustment) point to an arbitrary point on a Bezier curve, splitting the curve in two while retaining the same curve shape.
I have done some research and the algorithm needed was released in 1959 by a frenchman named Paul deCasteljau.
What I basically need is someway to get the X and Y values of the 4 control points that define the two split curve halves.
Here are some links I was able to find that have math equations involved with splitting bezier curves:
This is my first post on this forum and I'm hoping I'll get lucky...hopefully someone will be able to untangle the math enough to give me a few hints of where to go with the coding...or if the math can be boiled down to one or more algebraic algorithms I think I can translate the equation(s) into VB Code, however, I'm looking for all the help I can get..any help appreciated. Thanks in advance.
Last edited by rpgnewbie; Jul 4th, 2004 at 08:40 PM.
And I was looking in the other bezier thread where you posted that bezier animation exe wondering how you did the anti-aliasing and you've included the DrawAntiAliasPixel with your post as well!!
In answer to your question:
I'm trying to create something like a "mini-CorelDraw" vector- drawing-module to add to my VB Drawing program.
I did check out the FAQ anti-aliasing tutorial - good info!
I had one little question (which I hate to ask because you've already provided so much already), but is there a way to slightly tweak your code so that instead of breaking the bezier curve into two UNJOINED segments, your excellent code could be modified to break the bezier curve into two JOINED segments?
You should change the split code to arrange the curves in order or else the joined move code doesnt work properly...
It works fine if you split into only 2 curve, but try and split it again and you'll see the poblem.
"Just change the code in my program to make every curve share the 4th point with the 1st point in the second curve..."
Yes - you read my mind. Thanks for writing out the whole thing instead of posting just a snippet. Although I "sort of" understand most of the code you use a different technique for generating the curve then in other bezier curves routines I've written.
Right now I'm working through your code while working on another routine --when the user moves the endpoints of two curves close together (or on top one another), he/she should be able to select the two endpoints with a rubberbanding rectangular box and manually join them into one curve segment..
"It works fine if you split into only 2 curve, but try and split it again and you'll see the poblem"
--Yes, I do, but the code won't be called twice in a row....in-between the user will select a new point so it's not a problem...
But that brings me to what is needed to mark this thread as Resolved.
In my first post I asked for "add a node (adjustment) point to an arbitrary point" and this means I still have to find a way to tell whether a arbitrary MouseDown X,Y point is on the curve or (to allow for sloppy mouse handling) within plus or minus 2 pixels.
Hopefully this can be done without looping through all the points on the curve. I'd be willing to abandon any anti-aliasing to get this "Hit Test" code working properly.
Any Ideas? Thanks for all your help to date
Last edited by rpgnewbie; Jul 11th, 2004 at 10:43 PM.
Yes, your looping statement is basically what I did, but testing with 100 beziers curves the performance on my old Pentium II is REALLY bad.
There must be an algorithmic way.
Here is a wireframe picture (The Huntress") from CorelDraw with many, many, line segments (including curves). Yet you can click anywhere within a few pixels of any of these lines and Corel puts a node edit point on the curve in a fraction of a second.
Granted its probably written in C/C++, but even then I now CorelDraw is looping through every point on every line segement -- I just have a feel a better way is out there...
You can probably also first check something like a bounding box around the curves, and if the mouse is inside it then check every point...
You just have to work out how to calculate the boundaries of the box.
Thanks for the taking the time to make up and post the bounding box code. Unfortunately my feeling is I don't think it will really totally solve either of these two issues I'm still struggling with:
1.) How to find out if a point is on the curve WITHOUT having to loop through points (and take a performance hit)
2.) How to tell which cruve you are trying to add a split point to --especially if the curves are very close together (for instance two curves of exactly the same shape with one displaced 3 pixels above the other) Using a bounding box sloppily could catch both curves at once..
But I will try to test your boundary box code tonight when I get home. Maybe I'm wrong
Edit : Tested bounding box - didn't help
I'm working on trying to reduce the amount of points that have to be searched through by splitting the set of points into sub groups.
I had an idea. What if, as the curve points were being generated, a set of RECT structures surrounding each point could also be set up to create 2 pixel wide regions for every 100 points or so along the curve. Then use PtInRect to test if the point lies close to (alongside0 that section of curve. Then I would only have to search that particular sub-section of curve points looking for the closest point. Here's the API Declares:
VB Code:
Private Type RECT
Left As Long
Top As Long
Right As Long
Bottom As Long
End Type
Private Declare Function SetRect Lib "user32" (lpRect As RECT, ByVal X1 As Long, ByVal Y1 As Long, ByVal X2 As Long, ByVal Y2 As Long) As Long
Private Declare Function UnionRect Lib "user32.dll" (lpDestRect As RECT, lpSrc1Rect As RECT, lpSrc2Rect As RECT) As Long
Private Declare Function PtInRect Lib "user32" (lpRect As RECT, ByVal x As Long, ByVal y As Long) As Long
...and if that doesn't work I might try Regions and PtInRegion to test:
VB Code:
Public Declare Function CreateRectRgn Lib "GDI32" (ByVal X1 As Long, ByVal Y1 As Long, ByVal X2 As Long, ByVal Y2 As Long) As Long
Declare Function CombineRgn Lib "gdi32" Alias "CombineRgn" (ByVal hDestRgn As Long, ByVal hSrcRgn1 As Long, ByVal hSrcRgn2 As Long, ByVal nCombineMode As Long) As Long
Private Declare Function PtInRegion Lib "gdi32" (ByVal hRgn As Long, ByVal x As Long, ByVal y As Long) As Long
Then I just have to figure out the code to JOIN together the endpoints of two bezier curves to make them into one and the mini-CorelDraw module will be complete
Well, I guess I have my work cut out for me...Thanks again Cyborg for all your help.
<Edited by Moderator (Electroman), added VBCode tags>
Last edited by Electroman; Jul 17th, 2004 at 10:26 PM.
Re: Splitting Bezier curves using deCasteljau algorithm...
Strange to see a response to a message on this thread posted almost 18 years ago!
Still, if it's a matter of finding the nearest point along a curve, which rpgNewbie wanted, it's fairly easy to code in VB.Net without resorting to Bezier maths. I recall posting something on that topic a mere 12 years ago: take a look at this thread posts #8 and #12. Any use?
BB
Last edited by boops boops; May 29th, 2022 at 06:46 PM.