pouët.net

Signed distance to quadratic bezier

category: code [glöplog]
mind = blown
added on the 2012-11-19 20:49:32 by revival revival
does this thread means that we will see some smooth raymarched boobs in asm compos next year ?
added on the 2012-11-19 22:07:54 by Tigrou Tigrou
I'd be in for some raymarched scenepoetry.
added on the 2012-11-19 22:13:30 by Preacher Preacher
what is SDF ?
T21 : how do you render your last image ? is it a pixel shader who access to all your Quadratic curves segment ?
beacuse I don't undertstand the meaning of your x += .. parameter in a pixel shader.
added on the 2012-11-19 22:36:52 by u2 u2
SDF = signed distance field.
Once you have evaluated distances you can perform interesting operations. Those might become texture the GPU can render using trivial shaders.

BTW, you might have noticed that the distance function doesn't return negative value, but I do have crossing test that turn distance negative inside shapes.

The code is currently running on the CPU, making this screen based skipping possible.
On the GPU you would render in multiple pass. If you use plain pixel shaders, you would use regular grids. Possibly start at 32x32 resolution and go down to 4x4. (4 pass)


added on the 2012-11-19 23:27:14 by T21 T21
T21: ok it was my thougth. Because i have already implemented quadratic curve rendering with pixel shader with the same technic ( sdf )
added on the 2012-11-20 00:25:38 by u2 u2
Well, if you are not limited to pixel shader this could be leveraged as an early out in a compute kernel.
I haven't tried to optimize the pants off this yet, I usually let this type of code simmer for weeks before I truly go parallel.

BTW, cool UI ;)
I actually downloaded your app earlier today after seeing your post in the "work in progress" thread.









added on the 2012-11-20 01:07:33 by T21 T21
friggin cool work :)
added on the 2012-11-20 01:33:59 by kusma kusma
I have a numerical approximation for the distance to cubic bezier splines - it's pretty straight forward to implement - just some mix instructions and a little loop - all you need is a "distance to line" segment and some subdivision approach. In case there's a common interest in that code I'm willing to share it - it's "future proof" code - as in - it's slow as f*ck - depending on the number of subdivisions.

Did anyone try yet to rewrite the here proposed distance to quadratic in GLSL/HLSL? I would like to see some copy-pasteable code - because I'm lazy.
added on the 2012-11-20 09:39:58 by las las
with Quadratic rendering in a pixel shader you must be carefull with the numerical stability to handle all case of the distance computing.
Because you can have numerical rounding error or cancellation of the term "r[0] = offset + u + v;"
see this link for more infos
added on the 2012-11-20 10:08:38 by u2 u2
the code can be translated super easily, and it worked just wonderfully here in GLSL (#version 330 core):

Code:float findNearestPoint( in vec3 P0, in vec3 P1, in vec3 P2, in vec3 x ) { float d0 = length( P0-x ); float d2 = length( P2-x ); float dis = min( d0, d2 ); vec3 a = P0 - 2.0*P1 + P2; vec3 b = 2.0*(P1 - P0); vec3 c = P0; float k3 = 2.0*dot(a,a); float k2 = 3.0*dot(a,b); float k1 = dot(b,b) + 2.0*dot(c-x,a); float k0 = dot(c-x,b); float res[3]; int n = solveCubic( k3, k2, k1, k0, res ); for( int i=0; i<n; i++ ) { float t = res[i]; if( t>=0.0 && t <=1.0 ) { vec3 pos = (1.0-t)*(1.0-t)*P0 + 2.0*t*(1.0-t)*P1 + t*t*P2; dis = min( dis, length( pos - x ) ); } } return dis; }
added on the 2012-11-20 16:00:09 by iq iq
does this help performance?

Code: float findNearestPoint( in vec3 P0, in vec3 P1, in vec3 P2, in vec3 x ) { float d0 = length( P0-x ); float d2 = length( P2-x ); float dis = min( d0, d2 ); vec3 a = P0 - 2.0*P1 + P2; vec3 b = 2.0*(P1 - P0); vec3 c = P0; float k3 = 2.0*dot(a,a); float k2 = 3.0*dot(a,b); float k1 = dot(b,b) + 2.0*dot(c-x,a); float k0 = dot(c-x,b); float res[3]; int n = solveCubic( k3, k2, k1, k0, res ); float t = saturate(res[0]); vec3 pos = (1.0-t)*(1.0-t)*P0 + 2.0*t*(1.0-t)*P1 + t*t*P2; dis = min( dis, length( pos - x ) ); if(n>1) { t = saturate(res[1]); pos = (1.0-t)*(1.0-t)*P0 + 2.0*t*(1.0-t)*P1 + t*t*P2; dis = min( dis, length( pos - x ) ); t = saturate(res[2]); pos = (1.0-t)*(1.0-t)*P0 + 2.0*t*(1.0-t)*P1 + t*t*P2; dis = min( dis, length( pos - x ) ); } return dis; }
added on the 2012-11-20 18:38:32 by T21 T21
Here is a full GLSL sample of the code outlined here for reference.
Because all the math is so obvious there is no comments :)

http://glsl.heroku.com/e#4966.4
added on the 2012-11-20 20:13:58 by T21 T21
This show how to leverage SDF for thickness & softness

http://glsl.heroku.com/e#4966.9
added on the 2012-11-20 21:01:50 by T21 T21
with an outline mode
http://glsl.heroku.com/e#4966.13
added on the 2012-11-20 21:46:27 by T21 T21
Extending it to draw a curve of splines is a piece of cake:
http://glsl.heroku.com/e#4971.0
added on the 2012-11-20 22:34:46 by xTr1m xTr1m
This is totally awesome work! but oh dear lord - how long till we get endless message scrollers :P
added on the 2012-11-20 23:14:35 by Shabby Shabby
Actually this is real progress : http://glsl.heroku.com/e#4973.0
added on the 2012-11-21 00:13:55 by Tigrou Tigrou
u2: Yes, well clearly you have walked that path before.

Do you have a solution for http://glsl.heroku.com/e#4966.21
Because with
p[1] = vec2(resolution.x*.45,resolution.y*.5);
it breaks exactly for the reason the mentioned.


Tigrou, cant wait for you to complete your Pinocchio.
added on the 2012-11-21 00:31:33 by T21 T21
@T21 : i had some difficulties to implement the mouth...
added on the 2012-11-21 01:02:10 by Tigrou Tigrou
I have an alternative proof of concept of what I mentioned in my first post.
(no for(), if(), acos(), cos(), sin(), cuberoot() in this version)

But because it require the UV gradient, I dont think its any faster...
http://glsl.heroku.com/e#4976.1
For the curious
added on the 2012-11-21 08:13:54 by T21 T21
Tigrou : HAHAHAH you save my day :)

T21 : I use this trick to compute the return parameter D is positive :
Code: if( abs(p3_27) < q2*0.001 ) { if( q <0 ) ret = u + offset + p / ( 3.f * -pow(-q,1.f/3.f) ) ; else ret = v + offset + p / ( 3.f * pow(q,1.f/3.f) ) ; } else { ret = u + v + offset }


sorry my variables perhaps deosn't match yours but the trick is to avoid the float cancellation when substracting little value.
Llittle more thing to say. I have traced with NSight the behavior of float operations on a GTX280 and it's not as accurate as the code generated by the CPU. If I run the same code on the CPU the resulat is less prone to float cancellation than on the GPU.
added on the 2012-11-21 09:39:54 by u2 u2
Thx.

Here is a third method. from
http://research.microsoft.com/en-us/um/people/hoppe/ravg.pdf
(See fig 7)

http://glsl.heroku.com/e#5007.0

Code: vec2 get_distance_vector(vec2 b0, vec2 b1, vec2 b2) { float a=det(b0,b2), b=2.0*det(b1,b0), d=2.0*det(b2,b1); float f=b*d-a*a; vec2 d21=b2-b1, d10=b1-b0, d20=b2-b0; vec2 gf=2.0*(b*d21+d*d10+a*d20); gf=vec2(gf.y,-gf.x); vec2 pp=-f*gf/dot(gf,gf); vec2 d0p=b0-pp; float ap=det(d0p,d20), bp=2.0*det(d10,d0p); float t=clamp((ap+bp)/(2.0*a+b+d), 0.0,1.0); return mix(mix(b0,b1,t),mix(b1,b2,t),t); }

added on the 2012-11-24 10:52:02 by T21 T21
Would it be possible to utilise this (or something similar) for modelling 3d surfaces for raymarching purposes?
added on the 2013-01-01 15:30:56 by raizor raizor
i have had a look in paper. when you construct a biquadratic bezier patch, and you take the squared distance to a given point from it's surface and do the derivative(s) in order to get the closest distance, seems you get a system of two equations in degrees {4,3} and {3,4}, which leads to a solution of a polynomial of degree 7. which is not analytic. so it cannot be done just with a formula as with the quadatic bezier curve.

but i'm sure there are a million approximation and/or iterative solutions.
added on the 2013-01-01 21:26:09 by iq iq

login