<p>I'm working on improving an open source rasterization library called Gudni that I started a few years ago. It's source repository and the branch I'm currently working on are here: 
<a href="https://github.com/ianmbloom/gudni/tree/texturetransformation" rel="nofollow noreferrer">https://github.com/ianmbloom/gudni/tree/texturetransformation</a>. </p>

<p>I'm trying to implement a function that maps a quadratic bezier curve onto another curve (see illustration below). This is important for the library because it will not only allow one to describe things like dotted lines as just a series of rectangles projected onto a bezier path, but the same mechanism can (hopefully) be used to make text that follows a path or to make arrowheads etc and many other useful things. Using unified operation to do all of these things will hopefully make the library really easy to use and make a lot of useful figures very easy to describe.</p>

<p>But I've run into a bit of an impasse and I'm looking for some help.</p>

<p>The function I need has this description:</p>

<p>Given two quadratic bezier curves, a source and a target curve, transform the target curve such that the targets x-axis corresponds to the arc-distance along the source curve and the targets y-axis corresponds to the distance from the curve.
In other words given a point (x,y) in the target curves coordinate space find a point and a normal vector that is x units along the arc-length of the source curve then take that point and add it to the normal vector * y.</p>

<p>This works great for points but it doesn't work for quadratic bezier curves because the control point must be transformed such that each point on the resulting curve approximates a projected point. I'm trying to find method of calculating a control point such that the resulting curve is consistent, well behaved, doesn't require excessive computation, and is visually pleasing (though not necessarily precisely accurate) and can be applied to arbitrary target curves. Probably the most important requirement for the result is that two consecutive bezier segments that share the same tangent, share the same tangent in the projected curves.</p>

<p>Since the control point of a quadratic bezier is always the intersection of the tangent lines through its start and end point, my solution so far is to take the tangent vectors from the original target curve, transform them relative to the source normal vectors and then calculate the intersection of the lines defined by these transformed tangent vectors. Unfortunately this appears to work well for horizontal target curves but somehow it is often wrong for diagonal curves. I think this is because of the arc-length transformation but I haven't figured it out yet.</p>

<p>I'm curious if anyone has any thoughts on how to approach this problem.
The current (incorrect) implementation of the function in question can be found here:
<a href="https://github.com/ianmbloom/gudni/blob/c65daed3e74a24c47db9d0488159104dbd1b8b62/src/Graphics/Gudni/Figure/Projection.hs#L243" rel="nofollow noreferrer">https://github.com/ianmbloom/gudni/blob/c65daed3e74a24c47db9d0488159104dbd1b8b62/src/Graphics/Gudni/Figure/Projection.hs#L243</a></p>

<p>Let me know if reading haskell is a problem and I can find a way to walk you through it.</p>

<p>Upon request, here is a link to a formalization of the problem:
<a href="https://medium.com/@ianbloom/-6e88ea8e8888" rel="nofollow noreferrer">https://medium.com/@ianbloom/-6e88ea8e8888</a></p>

<p>Kind regards,
Ian Bloom</p>

<p><a href="https://i.sstatic.net/Mbmpq.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Mbmpq.jpg" alt="Projection of one quadratic bezier onto another."></a></p>

CC BY-SA 4.0
2020-01-18T22:18:30.723Z
Could you rewrite this formally as a mathematical problem? It seems you have problems with the math, in which case the rest is irrelevant and honestly (at least for me) confusing.
lightxbulb
CC BY-SA 4.0
2020-01-18T23:39:20.247Z
Sure, I actually wrote a Maple worksheet describing the problem in an effort to find a way to solve for the control point. But the math for quadratic beziers gets very complicated very quickly and so I'm looking first and foremost for a conceptual approach. In other words, I don't think the right solution is mathematically perfect, that may be impossible, but instead just a "well behaved" solution that looks good.
Ian Bloom
CC BY-SA 4.0
2020-01-18T23:54:53.733Z
In any case let me look into a better way to describe this. But basically if you understand the case of "stroking" a bezier curve as just mapping a long rectangle of the appropriate length onto a source curve, this is just a generalization of that to any shape that you can make out of bezier curves and might want to map onto another curve path. Let me know if that makes any sense.
Ian Bloom
CC BY-SA 4.0
2020-01-19T07:09:48.803Z
"mapping a long rectangle of the appropriate length onto a source curve" - there are infinitely many ways to do this, that is why I believe a formalization will help.
lightxbulb
CC BY-SA 4.0
2020-01-19T19:43:22.610Z
Have you read the pomax bezier info?
joojaa
CC BY-SA 4.0
2020-01-19T19:50:14.483Z
Here is a link to an attempt at formalizing the problem. Let me know if this link is good: https://medium.com/@ianbloom/-6e88ea8e8888
Ian Bloom
CC BY-SA 4.0
2020-01-19T19:58:15.923Z
I have read most of the pomax info, I think this relates closest to section 40, graduated curve offsetting, but it's not exactly the same problem since we would need to assume that the control point in the curve we are trying to transform is collinear.
Ian Bloom
CC BY-SA 4.0
2020-01-20T19:04:05.203Z
Why dont you formulate the exact curve and then fit to it. Its not like this has a analytical solution in arbitrary cases.
joojaa
CC BY-SA 4.0
2020-01-20T19:07:13.077Z
Oh and btw you should add @username then people get a ping when you answer otherwise the might not notice yoir talking.
joojaa
CC BY-SA 4.0
2020-01-21T02:33:01.647Z
How do you consider your current result wrong? Is it because your straight diagonal becomes a curve? Or because it's not the correct curve? Meaning the one you'd get by applying your transform to every one of its points.
Olivier
CC BY-SA 4.0
2020-01-21T14:05:23.283Z
@Olivier, in the current implementation it's possible to get a control point that is outside the horizontal range of the original curve, so I think my tangent-intersection solution was just wrong.
Ian Bloom
CC BY-SA 4.0
2020-01-21T14:08:20.363Z
@Joojaa, I'm looking for a solution that can be computed very quickly. The end goal for this library is to handle images that have millions of arbitrary curves (it does that now but without the projection operation.)
Ian Bloom
CC BY-SA 4.0
2020-01-21T14:09:16.210Z
@lightxbulb here is a link to an attempt at formalizing the problem: medium.com/@ianbloom/-6e88ea8e8888
Ian Bloom
CC BY-SA 4.0
2020-01-21T15:36:20.257Z
Tangent intersection is about as heavy operation. Just produces bad fit because it cant split the curve if curvature needs it. Anyway this is a embarassingly parallel job so consider doing it on a gpu.
joojaa
CC BY-SA 4.0
2020-01-22T02:04:53.243Z
@Joojaa can you explain a little more exactly how the fitting operation could work.
Ian Bloom
<rasterizer><curve><bezier-curve><opencl>
Projecting one Quadratic Bezier Curve Onto Another
Ian Bloom
# Projecting one Quadratic Bezier Curve Onto Another

(Asked by: username_0 on 2020-01-18)

I'm working on improving an open source rasterization library called Gudni that I started a few years ago. It's source repository and the branch I'm currently working on are here:
<https://github.com/ianmbloom/gudni/tree/texturetransformation>.

I'm trying to implement a function that maps a quadratic bezier curve onto another curve (see illustration below). This is important for the library because it will not only allow one to describe things like dotted lines as just a series of rectangles projected onto a bezier path, but the same mechanism can (hopefully) be used to make text that follows a path or to make arrowheads etc and many other useful things. Using unified operation to do all of these things will hopefully make the library really easy to use and make a lot of useful figures very easy to describe.

But I've run into a bit of an impasse and I'm looking for some help.

The function I need has this description:

Given two quadratic bezier curves, a source and a target curve, transform the target curve such that the targets x-axis corresponds to the arc-distance along the source curve and the targets y-axis corresponds to the distance from the curve.
In other words given a point (x,y) in the target curves coordinate space find a point and a normal vector that is x units along the arc-length of the source curve then take that point and add it to the normal vector \* y.

This works great for points but it doesn't work for quadratic bezier curves because the control point must be transformed such that each point on the resulting curve approximates a projected point. I'm trying to find method of calculating a control point such that the resulting curve is consistent, well behaved, doesn't require excessive computation, and is visually pleasing (though not necessarily precisely accurate) and can be applied to arbitrary target curves. Probably the most important requirement for the result is that two consecutive bezier segments that share the same tangent, share the same tangent in the projected curves.

Since the control point of a quadratic bezier is always the intersection of the tangent lines through its start and end point, my solution so far is to take the tangent vectors from the original target curve, transform them relative to the source normal vectors and then calculate the intersection of the lines defined by these transformed tangent vectors. Unfortunately this appears to work well for horizontal target curves but somehow it is often wrong for diagonal curves. I think this is because of the arc-length transformation but I haven't figured it out yet.

I'm curious if anyone has any thoughts on how to approach this problem.
The current (incorrect) implementation of the function in question can be found here:
<https://github.com/ianmbloom/gudni/blob/c65daed3e74a24c47db9d0488159104dbd1b8b62/src/Graphics/Gudni/Figure/Projection.hs#L243>

Let me know if reading haskell is a problem and I can find a way to walk you through it.

Upon request, here is a link to a formalization of the problem:
<https://medium.com/@username_0/-6e88ea8e8888>

Kind regards,
Ian username_0

[![Projection of one quadratic bezier onto another.](https://i.sstatic.net/Mbmpq.jpg)](https://i.sstatic.net/Mbmpq.jpg)

**Tags:** rasterizer, curve, bezier-curve, opencl

> **Comments:**
> **username_1**: Could you rewrite this formally as a mathematical problem? It seems you have problems with the math, in which case the rest is irrelevant and honestly (at least for me) confusing.  
> **username_0**: Sure, I actually wrote a Maple worksheet describing the problem in an effort to find a way to solve for the control point. But the math for quadratic beziers gets very complicated very quickly and so I'm looking first and foremost for a conceptual approach. In other words, I don't think the right solution is mathematically perfect, that may be impossible, but instead just a "well behaved" solution that looks good.  
> **username_0**: In any case let me look into a better way to describe this. But basically if you understand the case of "stroking" a bezier curve as just mapping a long rectangle of the appropriate length onto a source curve, this is just a generalization of that to any shape that you can make out of bezier curves and might want to map onto another curve path. Let me know if that makes any sense.  
> **username_1**: "mapping a long rectangle of the appropriate length onto a source curve" - there are infinitely many ways to do this, that is why I believe a formalization will help.  
> **username_2**: Have you read the pomax bezier info?  
> **username_0**: Here is a link to an attempt at formalizing the problem. Let me know if this link is good: https://medium.com/@username_0/-6e88ea8e8888  
> **username_0**: I have read most of the pomax info, I think this relates closest to section 40, graduated curve offsetting, but it's not exactly the same problem since we would need to assume that the control point in the curve we are trying to transform is collinear.  
> **username_2**: Why dont you formulate the exact curve and then fit to it. Its not like this has a analytical solution in arbitrary cases.  
> **username_2**: Oh and btw you should add @username then people get a ping when you answer otherwise the might not notice yoir talking.  
> **username_3**: How do you consider your current result wrong? Is it because your straight diagonal becomes a curve? Or because it's not the correct curve? Meaning the one you'd get by applying your transform to every one of its points.  
> **username_0**: @username_3, in the current implementation it's possible to get a control point that is outside the horizontal range of the original curve, so I think my tangent-intersection solution was just wrong.  
> **username_0**: @username_2, I'm looking for a solution that can be computed very quickly. The end goal for this library is to handle images that have millions of arbitrary curves (it does that now but without the projection operation.)  
> **username_0**: @username_1 here is a link to an attempt at formalizing the problem: medium.com/@username_0/-6e88ea8e8888  
> **username_2**: Tangent intersection is about as heavy operation. Just produces bad fit because it cant split the curve if curvature needs it. Anyway this is a embarassingly parallel job so consider doing it on a gpu.  
> **username_0**: @username_2 can you explain a little more exactly how the fitting operation could work.  

---

## 0 answers

