Results 1 to 20 of 20

Thread: Splitting Bezier curves using deCasteljau algorithm...

  1. #1

    Thread Starter
    New Member
    Join Date
    Apr 2004
    Location
    Portland, OR
    Posts
    9

    Question 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:

    deCasteljau algorithm and Linear Interpolation (lerp-ing) with C code:
    http://www.cubic.org/~submissive/sourcerer/bezier.htm

    Adaptive Sub Division through Blossoming Principle using systolic arrays and Epsilon criteria checking..
    http://kingkong.me.berkeley.edu/~ke...som/blossom.pdf

    Computational Aspects of Geometric Design (NOTE:CAGD is Computed Aided Geometric Design)
    http://www1.cs.columbia.edu/cagd/cagd_class3.pdf

    Degree Elevation of a Bézier Curve
    http://www.cs.mtu.edu/~shene/COURSE...ezier-elev.html

    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.
    Attached Files Attached Files
    Last edited by rpgnewbie; Jul 4th, 2004 at 08:40 PM.

  2. #2

    Thread Starter
    New Member
    Join Date
    Apr 2004
    Location
    Portland, OR
    Posts
    9

    Additonal gif describing problem...

    Here's the gif that show the four points mentioned above:
    Attached Images Attached Images  

  3. #3

    Thread Starter
    New Member
    Join Date
    Apr 2004
    Location
    Portland, OR
    Posts
    9

    Additional gif of math equations...

    Here's the jpg with what I think (?) are the necessary math equations:
    Attached Images Attached Images  

  4. #4
    Frenzied Member cyborg's Avatar
    Join Date
    May 2000
    Location
    Sweden
    Posts
    1,755
    Here you go. This should work.

    The code is not much commented, but feel free to ask about anything.
    Attached Files Attached Files
    Check out the FAQ and do a search before you post.
    My tutorials: Anti-Alias Pixels, Accurate Game Loop, Resource File

  5. #5

    Thread Starter
    New Member
    Join Date
    Apr 2004
    Location
    Portland, OR
    Posts
    9

    Wink Thanks!

    You are genius!

    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!!

    Thank you so much

  6. #6
    Frenzied Member cyborg's Avatar
    Join Date
    May 2000
    Location
    Sweden
    Posts
    1,755
    You're welcome!

    I've also made a tutorial on anti-alias in the FAQ if you wanna know more.

    Btw, what kind of program are you making?
    Check out the FAQ and do a search before you post.
    My tutorials: Anti-Alias Pixels, Accurate Game Loop, Resource File

  7. #7

    Thread Starter
    New Member
    Join Date
    Apr 2004
    Location
    Portland, OR
    Posts
    9

    Bezier split

    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?

    Thanks again for any assistence

  8. #8
    Frenzied Member cyborg's Avatar
    Join Date
    May 2000
    Location
    Sweden
    Posts
    1,755
    I've never worked on joined curves before, but that should not be too hard...
    Let me have a look.
    Check out the FAQ and do a search before you post.
    My tutorials: Anti-Alias Pixels, Accurate Game Loop, Resource File

  9. #9
    Frenzied Member cyborg's Avatar
    Join Date
    May 2000
    Location
    Sweden
    Posts
    1,755
    Just change the code in my program to make every curve share the 4th point with the 1st point in the second curve...

    Something like this when changing curve 1:

    Last point:
    BezierLine(2).X(0) = BezierLine(1).X(3)
    BezierLine(2).Y(0) = BezierLine(1).Y(43

    Handle to last point:
    BezierLine(2).X(1) = BezierLine(1).X(3) + BezierLine(1).X(3) - BezierLine(1).X(2)
    BezierLine(2).Y(1) = BezierLine(1).Y(3) + BezierLine(1).Y(3) - BezierLine(1).Y(2)
    Last edited by cyborg; Jul 11th, 2004 at 02:33 PM.
    Check out the FAQ and do a search before you post.
    My tutorials: Anti-Alias Pixels, Accurate Game Loop, Resource File

  10. #10
    Frenzied Member cyborg's Avatar
    Join Date
    May 2000
    Location
    Sweden
    Posts
    1,755
    Damn! I couldn't resist! Here's a modified MovePoint for you:

    VB Code:
    1. Public Sub MovePoint(X As Single, Y As Single)
    2.     With BezierLine(CurrentLine)
    3.         .X(CurrentPoint) = X
    4.         .Y(CurrentPoint) = Y
    5.     End With
    6.    
    7.     If CurrentLine < LineCount And CurrentLine <> 0 Then
    8.         If CurrentPoint = 3 Then
    9.             BezierLine(CurrentLine + 1).X(0) = BezierLine(CurrentLine).X(3)
    10.             BezierLine(CurrentLine + 1).Y(0) = BezierLine(CurrentLine).Y(3)
    11.         ElseIf CurrentPoint = 2 Then
    12.             BezierLine(CurrentLine + 1).X(1) = BezierLine(CurrentLine).X(3) + BezierLine(CurrentLine).X(3) - BezierLine(CurrentLine).X(2)
    13.             BezierLine(CurrentLine + 1).Y(1) = BezierLine(CurrentLine).Y(3) + BezierLine(CurrentLine).Y(3) - BezierLine(CurrentLine).Y(2)
    14.         End If
    15.     End If
    16.    
    17.     If CurrentLine > 0 Then
    18.         If CurrentPoint = 0 Then
    19.             BezierLine(CurrentLine - 1).X(3) = BezierLine(CurrentLine).X(0)
    20.             BezierLine(CurrentLine - 1).Y(3) = BezierLine(CurrentLine).Y(0)
    21.         ElseIf CurrentPoint = 1 Then
    22.             BezierLine(CurrentLine - 1).X(2) = BezierLine(CurrentLine).X(0) + BezierLine(CurrentLine).X(0) - BezierLine(CurrentLine).X(1)
    23.             BezierLine(CurrentLine - 1).Y(2) = BezierLine(CurrentLine).Y(0) + BezierLine(CurrentLine).Y(0) - BezierLine(CurrentLine).Y(1)
    24.         End If
    25.     End If
    26.    
    27.     Draw
    28. End Sub

    Here's another one... You decide which one is better.
    VB Code:
    1. Public Sub MovePoint(X As Single, Y As Single)
    2.     With BezierLine(CurrentLine)
    3.         .X(CurrentPoint) = X
    4.         .Y(CurrentPoint) = Y
    5.     End With
    6.    
    7.     If CurrentLine < LineCount And CurrentLine <> 0 Then
    8.         BezierLine(CurrentLine + 1).X(0) = BezierLine(CurrentLine).X(3)
    9.         BezierLine(CurrentLine + 1).Y(0) = BezierLine(CurrentLine).Y(3)
    10.         BezierLine(CurrentLine + 1).X(1) = BezierLine(CurrentLine).X(3) + BezierLine(CurrentLine).X(3) - BezierLine(CurrentLine).X(2)
    11.         BezierLine(CurrentLine + 1).Y(1) = BezierLine(CurrentLine).Y(3) + BezierLine(CurrentLine).Y(3) - BezierLine(CurrentLine).Y(2)
    12.     End If
    13.    
    14.     If CurrentLine > 0 Then
    15.         BezierLine(CurrentLine - 1).X(3) = BezierLine(CurrentLine).X(0)
    16.         BezierLine(CurrentLine - 1).Y(3) = BezierLine(CurrentLine).Y(0)
    17.         BezierLine(CurrentLine - 1).X(2) = BezierLine(CurrentLine).X(0) + BezierLine(CurrentLine).X(0) - BezierLine(CurrentLine).X(1)
    18.         BezierLine(CurrentLine - 1).Y(2) = BezierLine(CurrentLine).Y(0) + BezierLine(CurrentLine).Y(0) - BezierLine(CurrentLine).Y(1)
    19.     End If
    20.    
    21.     Draw
    22. End Sub

    Keep 'em comming!
    Check out the FAQ and do a search before you post.
    My tutorials: Anti-Alias Pixels, Accurate Game Loop, Resource File

  11. #11
    Frenzied Member cyborg's Avatar
    Join Date
    May 2000
    Location
    Sweden
    Posts
    1,755
    Oh... One small bug in this code...

    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.
    Check out the FAQ and do a search before you post.
    My tutorials: Anti-Alias Pixels, Accurate Game Loop, Resource File

  12. #12

    Thread Starter
    New Member
    Join Date
    Apr 2004
    Location
    Portland, OR
    Posts
    9

    Joined point

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

  13. #13
    Frenzied Member cyborg's Avatar
    Join Date
    May 2000
    Location
    Sweden
    Posts
    1,755
    That's a bit harder... I think you'll have to loop through all the points in the curve. You don't need to remove the anti-aliasing.

    For each point, do a 2D collition check... Something like this:

    If MouseX >= X(i) - 2 And MouseX <= X(i) + 2 And MouseY >= Y(i) - 2 And MouseY <= Y(i) + 2 Then
    Check out the FAQ and do a search before you post.
    My tutorials: Anti-Alias Pixels, Accurate Game Loop, Resource File

  14. #14

    Thread Starter
    New Member
    Join Date
    Apr 2004
    Location
    Portland, OR
    Posts
    9

    Going Loopy

    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...
    Attached Images Attached Images  

  15. #15
    Frenzied Member cyborg's Avatar
    Join Date
    May 2000
    Location
    Sweden
    Posts
    1,755
    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.
    Check out the FAQ and do a search before you post.
    My tutorials: Anti-Alias Pixels, Accurate Game Loop, Resource File

  16. #16
    Frenzied Member cyborg's Avatar
    Join Date
    May 2000
    Location
    Sweden
    Posts
    1,755
    Once again I couldn't resist!
    Change the mousemove code in my program to this:

    VB Code:
    1. Private Sub PicDisp_MouseMove(Button As Integer, Shift As Integer, X As Single, Y As Single)
    2.     Dim i As Long
    3.     Dim MinX As Long
    4.     Dim MinY As Long
    5.     Dim MaxX As Long
    6.     Dim MaxY As Long
    7.     If Button = 1 Then
    8.         MovePoint X, Y
    9.         If LineCount = 1 Then
    10.             With BezierLine(1)
    11.                 MinX = .X(0) 'reset values
    12.                 MinY = .Y(0)
    13.                 MaxX = .X(0)
    14.                 MaxY = .Y(0)
    15.                
    16.                 For i = 1 To 3 'check all other points
    17.                     If .X(i) < MinX Then MinX = .X(i)
    18.                     If .Y(i) < MinY Then MinY = .Y(i)
    19.                     If .X(i) > MaxX Then MaxX = .X(i)
    20.                     If .Y(i) > MaxY Then MaxY = .Y(i)
    21.                 Next
    22.                 PicDisp.Line (MinX, MinY)-(MaxX, MinY)
    23.                 PicDisp.Line (MaxX, MinY)-(MaxX, MaxY)
    24.                 PicDisp.Line (MaxX, MaxY)-(MinX, MaxY)
    25.                 PicDisp.Line (MinX, MaxY)-(MinX, MinY)
    26.                 PicDisp.Refresh
    27.             End With
    28.         End If
    29.     End If
    30. End Sub

    This will show you a valid bounding box that you can check first and if the mouse is inside it, then check all points.
    Check out the FAQ and do a search before you post.
    My tutorials: Anti-Alias Pixels, Accurate Game Loop, Resource File

  17. #17

    Thread Starter
    New Member
    Join Date
    Apr 2004
    Location
    Portland, OR
    Posts
    9

    Bounding 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:
    1. Private Type RECT
    2.         Left As Long
    3.         Top As Long
    4.         Right As Long
    5.         Bottom As Long
    6. End Type
    7. 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
    8. Private Declare Function UnionRect Lib "user32.dll" (lpDestRect As RECT, lpSrc1Rect As RECT, lpSrc2Rect As RECT) As Long
    9. 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:
    1. Public Declare Function CreateRectRgn Lib "GDI32" (ByVal X1 As Long, ByVal Y1 As Long, ByVal X2 As Long, ByVal Y2 As Long) As Long
    2. 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
    3. 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.

  18. #18

    Thread Starter
    New Member
    Join Date
    Apr 2004
    Location
    Portland, OR
    Posts
    9

    Solving the Nearest Point-on-Curve Problem

    Sorry about the tags above and thanks to the moderator who was thoughful enough to add them.

    I found the C code for "Solving the Nearest Point-on-Curve Problem and A Bezier Curve-Based Root-Finder". It's on this page:
    http://www.acm.org/pubs/tog/Graphics...NearestPoint.c

    Too bad I don't know how to convert it to VB

  19. #19
    Lively Member
    Join Date
    Jun 2016
    Posts
    106

    Re: Splitting Bezier curves using deCasteljau algorithm...

    Quote Originally Posted by cyborg View Post
    Here you go. This should work.

    The code is not much commented, but feel free to ask about anything.
    the file bezier.zip do not download, wrong file (.gif file clear.gif)

  20. #20
    PowerPoster boops boops's Avatar
    Join Date
    Nov 2008
    Location
    Holland/France
    Posts
    3,201

    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

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width