Resolution independent cubic bezier drawing on GPU (Blinn/Loop)

Question

Based on the following resources, I have been trying to get resolution independent cubic bezier rendering on the GPU to work:

GPU Gems 3 Chapter 25

Curvy Blues

Resolution Independent Curve Rendering using Programmable Graphics Hardware

But as stated in the Curvy Blues website, there are errors in the documents on the other two websites. Curvy Blues tells me to look at the comments, but I don't seem to be able to find those comments. Another forum somewhere tells me the same, I don't remember what that forum was. But there is definitely something I am missing.

Anyway, I have tried to regenerate what is happening and I fail to understand the part where the discriminant is calculated from the determinants of a combination of transformed coordinates.

So I have the original coordinates, I stick them in a 4x4 matrix, transform this matrix with the M3-matrix and get the C-matrix. Then I create 3x3 matrices from the coordinates in the C-matrix and calculate the determinants, which then can be combined to create the a, b and c of the quadratic equation that will help me find the roots.

Problem is, when I do it exactly like that: the discriminant is incorrect. I clearly put in coordinates for a serpentine (a symmetric one, but a correct serpentine), but it states it is a cusp. When I calculate it myself using wxMaxima, deriving to 1st and 2nd order and then calculating the cross-product, simplifying to a quadratic equation, the discriminant of that equation seems to be correct when I put in the same coordinates. When I force the code to use my own discriminant to determine if it's a serpentine or not, but I use the determinants to calculate the further k,l,m texture coordinates, the result is also incorrect. So I presume there must be an error in the determinants.

Can anyone help me get this right?

Greatcoat

Answer 1

I think I have managed to solve it. The results are near to perfect (sometimes inverted, but that's probably a different problem).

This is where I went wrong, and I hope I can help other people to not waste all the time I have wasted searching this.

I have based my code on the blinn-phong document. I had coordinates b0, b1, b2, b3. I used to view them as 2D coordinates with a w, but I have changed this view, and this solved the problem. By viewing them as 3D coordinates with z = 0, and making them homogenous 4D coordinates for transformation (w = 1), the solution arrived.

By calculating the C matrix: C = M3 * B, I got these new coordinates. When calculating the determinants d0, d1, d2, d3, I used to take the x, y coordinates from columns 0 and 1 in the C matrix, and the w factor from column 2. WRONG! When you think of it, the coordinates are actually 3D coordinates, so, for the w-factors, one should take column 3 and ignore column 2.

This gave me correct determinants, resulting in a discriminant that was able to sort out what type of curve I was handling.

But beware, what made my search even longer was the fact that I assumed that when it is visibly a serpentine, the result of the discriminant should always be > 0 (serpentine). But this is not always the case, when you have a mathematically perfect sepentine (coordinates are so that the mean is exact middle), the determinant will say it's a cusp (determinant = 0). I used to think that this result was wrong, but it isn't. So don't be fooled by this.

Greatcoat

great, I read your answer, It helped a lot. Do you know how to solve the artifact on Loop case? I have a question in here: #20971173 – Brei

No, sadly enough I had some unsolved issues and I stopped trying to fix it... But I see now that you just solved it in that thread, maybe your solution helps with my issues... I'll look into it! – Greatcoat

I have one more issue actually, the rendered curves can be either convex or concave, I'm still wondering if there's a testing to determine this. – Brei

I actually believe I can help you with that: when det1 < 0 then flip the signs on all the k and l factors of the 4 resulting klm's, leaving the m factor unchanged. This has something to do with that the Hessian should be negative but my math is not good enough to understand what the Hessian is. – Greatcoat

By the way: this sign-solution is only for serpentines (see documentation part about serpentines), I don't think you will have the convex/concave problem with other curve types. – Greatcoat

Hi, I get a chance to revisit my project again, too bad before I wasn't aware about artifact on serpentine curve. can you describe more clearly in flipping the sign? I'm quite confused about that – Brei

I don't understand the theory behind it, but in practice this is what you should do: When you have figured out that you are drawing a 'serpentine' or 'cusp with inflection at infinity', after you have calculated the klm factors, test that if determinant1 < 0. When it is, flip the signs (negate them) on all the k and l factors. Do this before you untransform them. – Greatcoat

I tried to detect this if(curveType == SERPENTINE && d1 < 0) then flip (if previously k^3 - lm <= 0 it should becomes k^3 - lm > 0) but it doesn't work. another strange thing is the problem also occurs when d1 > 0, I almost give up – Brei

Oh I also made a new question on here: gamedev.stackexchange.com/questions/70178/… perhaps you can take a look – Brei

I think you're misunderstanding. You should not change your k^3-lm <= 0 equation. You should just have the GPU hardware interpolate between -k, -l and m factors, so you need to change the texture-coordinates that you are sending to the shader. And, even that's not really true, because the k, l and m factors need to be transformed back first, so they might not even be -k, -l, m after the transformation. – Greatcoat

Thanks man, I think you're correct, I need to change k and l to -k and -l. Actually I almost gave up since checking d1 < 1 doesn't detect the artifact, but fortunately I got a really good source code here: opensource.apple.com/source/WebCore/WebCore-1298.39/platform/…. It's much more stable now – Brei

Great link! I'll look into it as I also still have artifacts. – Greatcoat

Answer 2

The book GPU Gem 3 has a mistake here, and the page on nVidia's website has the mistake too:

a3 = b2 * (b1 x b1)

It's actually a3 = b2 * (b1 x b0).

There're other problems about this algorithm: the exp part of the floating point will overflow during the calculation, so you should be cautious and add normalize operations into your code.

Pliam

I have never found a perfectly working solution, so what you are saying might be it. Maybe I'll dig into this again someday, because resolution independent cubic beziers are cool... – Greatcoat