Page 1 of 1 [ 14 posts ] 

MyFutureSelfnMe
Veteran
Veteran

User avatar

Joined: 26 Feb 2010
Age: 41
Gender: Male
Posts: 1,385

13 Jul 2012, 9:55 pm

I need a math guru to help me with a problem related to cubic bezier curves.

Say I have a cubic bezier with control points a,b,c,d, and I want to build a second cubic bezier from that with control points e,f,g,h, where the second bezier follows a path that is offset exactly 1 unit left of the first bezier. In other words, at any point on the first bezier, you can calculate the normal and follow the normal 1 unit in the positive (or negative in a flip case) direction and you will meet the second bezier.

Obviously, control points e and h are trivial to generate from points a and d. I just offset them directly since the curve passes directly through them. The middle control points are where I'm curious.

Does anyone know an equation that I can use to generate points f and g, or the process that would work? If the result is off by a few % in either direction at any point, in the name of simplifying the process, that's okay.

Cheers



Declension
Veteran
Veteran

User avatar

Joined: 20 Jan 2012
Age: 32
Gender: Male
Posts: 1,807

13 Jul 2012, 10:24 pm

According to Wiki, the offset of a Bezier is not necessarily a Bezier:

Wikipedia wrote:
The curve at a fixed offset from a given Bézier curve, often called an offset curve (lying "parallel" to the original curve, like the offset between rails in a railroad track), cannot be exactly formed by a Bézier curve (except in some trivial cases). However, there are heuristic methods that usually give an adequate approximation for practical purposes.


Here is a starting point (but I guess maybe it was you who asked this question?):

http://stackoverflow.com/questions/4148831/how-to-offset-a-cubic-bezier-curve

EDIT: Seems that I might have found the sort of thing you were looking for:

http://seant23.wordpress.com/2010/11/12/offset-bezier-curves/



MyFutureSelfnMe
Veteran
Veteran

User avatar

Joined: 26 Feb 2010
Age: 41
Gender: Male
Posts: 1,385

13 Jul 2012, 10:54 pm

Thanks I found the first page you posted, apparently this is not an uncommon problem to want to solve. Since it's an academic document I was hoping to find some source code so I wouldn't have to spend the whole weekend digesting the academic document. The second guy solved the problem in a way I'm not totally comfortable with (first tessellate the curve then add or remove line segments) but someone posted a response on the page to another page that seems to have a solution for the problem. Now I have to figure out that page :) I'm a programmer and don't want to hear about the math, I prefer to see the code :)



MyFutureSelfnMe
Veteran
Veteran

User avatar

Joined: 26 Feb 2010
Age: 41
Gender: Male
Posts: 1,385

13 Jul 2012, 11:01 pm

Actually it seems tessellating, offsetting lines and clipping/expanding is the only decent way. You can't adequately represent an offset Bezier with another Bezier.



Tomatoes
Sea Gull
Sea Gull

User avatar

Joined: 25 Jun 2012
Gender: Male
Posts: 200

13 Jul 2012, 11:32 pm

MyFutureSelfnMe
Veteran
Veteran

User avatar

Joined: 26 Feb 2010
Age: 41
Gender: Male
Posts: 1,385

13 Jul 2012, 11:38 pm

Thanks, that's the one I was just looking at. I've already realized though that I cannot adequately represent the offset as a Bezier curve so I'm going to attempt to do it by offsetting a set of line segments and then cutting out ones that intersect. The new question is what the fastest way is to cull the "between" segments or partial segments of intersections. That issue is illustrated here:

http://cagd.cs.byu.edu/~557/text/ch8.pdf



marshall
Veteran
Veteran

User avatar

Joined: 14 Apr 2007
Gender: Male
Posts: 10,752
Location: Turkey

18 Jul 2012, 3:49 pm

You could also offset a set of points on the curve by a certain distance and then fit a cubic spline through them.



MyFutureSelfnMe
Veteran
Veteran

User avatar

Joined: 26 Feb 2010
Age: 41
Gender: Male
Posts: 1,385

24 Jul 2012, 12:18 pm

marshall wrote:
You could also offset a set of points on the curve by a certain distance and then fit a cubic spline through them.


Yeah I looked at that, but I was hoping for something with a smaller O. Especially since I'd have to snip off and detect hard edges where the offset curve crosses itself.

I'm thinking about building polygons *around* the line and using a fragment shader to rasterize the curve detail. A fragment shader can decide how close it is to the center curve. Not positive on performance or details of the algorithm.



marshall
Veteran
Veteran

User avatar

Joined: 14 Apr 2007
Gender: Male
Posts: 10,752
Location: Turkey

28 Jul 2012, 12:15 pm

MyFutureSelfnMe wrote:
marshall wrote:
You could also offset a set of points on the curve by a certain distance and then fit a cubic spline through them.


Yeah I looked at that, but I was hoping for something with a smaller O. Especially since I'd have to snip off and detect hard edges where the offset curve crosses itself.

I'm thinking about building polygons *around* the line and using a fragment shader to rasterize the curve detail. A fragment shader can decide how close it is to the center curve. Not positive on performance or details of the algorithm.


I guess the standard way to render a mathematical curve with some small but finite thickness is to draw an offset polygon surrounding the line. As long you can calculate the derivatives of the parametric curve, you have an exact formula for the tangent and normal vectors at each point along the curve. Then the main issues is deciding how many points to use and how to deal with the offset curve possibly intersecting itself and turning "inside out" on the concave side of the curve.



mycats
Raven
Raven

User avatar

Joined: 13 Nov 2005
Age: 53
Gender: Male
Posts: 111
Location: Allentown, Pennysylvania

02 Oct 2012, 7:13 pm

Those tests of determining a pattern. Sometimes it is several examples of images. There is multiple choice to select the correct image that fits the pattern.

This test is also done with numbers. It shows several numbers, and then to pick the correct number from multiple choice that is the next number in the pattern.

What if someone who has an extraordinary talent to look at the winning results from the lottery and see a pattern in the randomness of numbers, and, be able to see the most probable next result.



ruveyn
Veteran
Veteran

User avatar

Joined: 21 Sep 2008
Age: 84
Gender: Male
Posts: 31,502
Location: New Jersey

05 Oct 2012, 3:10 pm

mycats wrote:
Those tests of determining a pattern. Sometimes it is several examples of images. There is multiple choice to select the correct image that fits the pattern.

This test is also done with numbers. It shows several numbers, and then to pick the correct number from multiple choice that is the next number in the pattern.

What if someone who has an extraordinary talent to look at the winning results from the lottery and see a pattern in the randomness of numbers, and, be able to see the most probable next result.


Fill in the blanks:

3 _ 4 _ 5 _ next (fill in this blank -)

If you said 6 you are a pedestrian. If you said 9 you are probably a mathematician. Pi = 3.1415962...

ruveyn



mycats
Raven
Raven

User avatar

Joined: 13 Nov 2005
Age: 53
Gender: Male
Posts: 111
Location: Allentown, Pennysylvania

07 Oct 2012, 7:47 pm

Ahhhh, that is brilliant.

I am not being sarcastic.



ruveyn
Veteran
Veteran

User avatar

Joined: 21 Sep 2008
Age: 84
Gender: Male
Posts: 31,502
Location: New Jersey

08 Oct 2012, 5:08 am

mycats wrote:
Ahhhh, that is brilliant.

I am not being sarcastic.


Now you know why I don't necessarily take I.Q. testing seriously.

A truly outstanding brilliant genius would probably fail most I.Q. tests. (not that I am such a person, I am not)

ruveyn



Last edited by ruveyn on 08 Oct 2012, 5:17 am, edited 1 time in total.

Species5618
Yellow-bellied Woodpecker
Yellow-bellied Woodpecker

User avatar

Joined: 17 Apr 2012
Age: 35
Gender: Male
Posts: 55

08 Oct 2012, 5:14 am

mycats wrote:
What if someone who has an extraordinary talent to look at the winning results from the lottery and see a pattern in the randomness of numbers, and, be able to see the most probable next result.


There is no pattern in randomness. That's why it's random.

But to continue with your example of the lottery. Suppose that the official that draws the lottery numbers pushes a button to generate a number. The computer the button is attached to looks at the time in microseconds that the button was pushed, takes the last 2 digits and uses this as the next number. The official then takes a sip of his drink, checks his watch, reloads a news-website, or whatever and repeats the process. How are you going to predict anything if the sequences of numbers are generated in this way?

Note that this is obviously not how lottery numbers are generated, but it is a decent enough example of a random number generator that is extremely easy to implement and that will be more than random enough so that no human will ever be able to predict the next result.