crayon - a 2D opengl curve renderer, with Reactive animations - Reactive

crayon - a 2D opengl curve renderer, with Reactive animations

Jules Bean

25 Mar 2009 25 Mar '09

2:59 p.m.

Hi, I have just uploaded another little proof-of-concept reactive toy. http://roobarb.jellybean.co.uk/~jules/crayon.8.tgz The important part is the beginnings of an OpenGL accelerated 2D rendering engine, for rendering parametric curves and in particular bezier curves. The way it works at the moment is: * A sampling step tries to adaptively generate points on the curve to approximate it as a polygon. This is done on the CPU, isn't as clever as it could be, but turns out to be not the bottleneck right now * For stroked regions, this is 'thickened' out to a stroke using difference-based approximations to a tangent. This works well for smooth curves but poorly at end points and sharp corners. For filled regions the GLU tessellator is used to convert it to GL primitives, normally triangles. * Then this is rendered by openGL in either immediate mode or using VAs. Currently the sampling and GLU tessellation can be cached and not redone every frame, if the appropriate part of the structure doesn't change each frame. You need to use standard GHC sharing to make this work - define constant picture fragments at a high enough scope that they get shared. The stroke generation is not cached and this turns out to be pretty expensive. You may need to compile with -fno-state-hack to get proper sharing (GHC "issue"/bug). I discovered a bug in the HOpenGL GLU binding. I don't think this demo tickles the bug so it should run on a standard build, details of that bug on the hopengl list. The immediate mode renderer turns out to be faster than the VA based renderer, at least for these small demos. I think that's because the extra pass over the data structure (to generate the VAs) is a relatively high cost, the number of vertices is small, and I'm not smart about sharing vertices. I then plugged all this into Reactive and set up three simple animations - some spinning flowers, some business-like charts, and a classic pong game. You can switch between them using your left + right arrows keys, and they spin in + out using a simple animation, whilst their own animations continue independently. Exactly the kind of thing Reactive is supposed to make easy! The framerate is artificially limited to save battery life when developing. As before, this code uses my incomplete Reactive implementation not Conal's; it should be easy to port although I think some of my primitives have slightly different names. I'm not going to work on this code for a bit, but I have in mind various possible extensions, including using the GPU to do some of the heavy lifting, using a fragment shader to support gradients and other kinds of procedural texturing, supporting implicit curves as well as parametric ones. I'm interested in any thoughts on how to design a useful attractive combinator library for 2D graphics. The real target is to have something fast enough to make an expressive library for complex smooth animations, e.g. 2D games. Jules

Show replies by date

Tom Poliquin

25 Mar 25 Mar

2:33 p.m.

Jules Bean wrote:

...

Hi,

I have just uploaded another little proof-of-concept reactive toy.

http://roobarb.jellybean.co.uk/~jules/crayon.8.tgz

The important part is the beginnings of an OpenGL accelerated 2D rendering engine, for rendering parametric curves and in particular bezier curves.

Jules, thanks for uploading the code! As a reactive newbie, examples are a gigantic help .. It works great .. about 40FPS on my ATI Technologies Inc RV515GL [FireGL V3350] using about 3% of my AMD Athlon(tm) 64 X2 Dual Core Processor 6000+ CPU. I had to make a small change to get it to work on my system (perhaps I'm down rev somewhere) .. but I thought I'd share in case other newbies have the same issue .. crayon.hs:689:57: Constructor `WeightedProperties' should have 4 arguments, but has been given 1 crayon.hs:699:8: Constructor `WeightedProperties' should have 4 arguments, but has been given 1 I just changed the WeightedProperties args in each case to, (WeightedProperties (_,p) _ _ _) from (WeightedProperties ((_, p) : _)) That seems to work. Thanks again, Tom

...

The way it works at the moment is:

* A sampling step tries to adaptively generate points on the curve to approximate it as a polygon. This is done on the CPU, isn't as clever as it could be, but turns out to be not the bottleneck right now * For stroked regions, this is 'thickened' out to a stroke using difference-based approximations to a tangent. This works well for smooth curves but poorly at end points and sharp corners. For filled regions the GLU tessellator is used to convert it to GL primitives, normally triangles. * Then this is rendered by openGL in either immediate mode or using VAs.

Currently the sampling and GLU tessellation can be cached and not redone every frame, if the appropriate part of the structure doesn't change each frame. You need to use standard GHC sharing to make this work - define constant picture fragments at a high enough scope that they get shared. The stroke generation is not cached and this turns out to be pretty expensive. You may need to compile with -fno-state-hack to get proper sharing (GHC "issue"/bug).

I discovered a bug in the HOpenGL GLU binding. I don't think this demo tickles the bug so it should run on a standard build, details of that bug on the hopengl list.

The immediate mode renderer turns out to be faster than the VA based renderer, at least for these small demos. I think that's because the extra pass over the data structure (to generate the VAs) is a relatively high cost, the number of vertices is small, and I'm not smart about sharing vertices.

I then plugged all this into Reactive and set up three simple animations - some spinning flowers, some business-like charts, and a classic pong game. You can switch between them using your left + right arrows keys, and they spin in + out using a simple animation, whilst their own animations continue independently. Exactly the kind of thing Reactive is supposed to make easy!

The framerate is artificially limited to save battery life when developing.

As before, this code uses my incomplete Reactive implementation not Conal's; it should be easy to port although I think some of my primitives have slightly different names.

I'm not going to work on this code for a bit, but I have in mind various possible extensions, including using the GPU to do some of the heavy lifting, using a fragment shader to support gradients and other kinds of procedural texturing, supporting implicit curves as well as parametric ones. I'm interested in any thoughts on how to design a useful attractive combinator library for 2D graphics.

The real target is to have something fast enough to make an expressive library for complex smooth animations, e.g. 2D games.

Jules

_______________________________________________ Reactive mailing list Reactive@haskell.org http://www.haskell.org/mailman/listinfo/reactive

Jules Bean

5:56 p.m.

New subject: crayon - a 2D opengl curve renderer, with Reactive animations

Tom Poliquin wrote:

...

Jules, thanks for uploading the code!

You're most welcome.

...

As a reactive newbie, examples are a gigantic help ..

It works great .. about 40FPS on my ATI Technologies Inc RV515GL [FireGL V3350] using about 3% of my AMD Athlon(tm) 64 X2 Dual Core Processor 6000+ CPU.

Yes, capped to 40fps by the "25" (25 milliseconds = 1/40 seconds) in line 115 inside the idle callback. If you change that to "0" then it will take up more or less 100% of your CPU and framerates will be much higher. On my machine (nvidia m 8xxx) it does 1000fps (!) for Pong, 400fps for the charts and 100fps for the flowers.

...

I had to make a small change to get it to work on my system (perhaps I'm down rev somewhere) .. but I thought I'd share in case other newbies have the same issue ..

crayon.hs:689:57: Constructor `WeightedProperties' should have 4 arguments, but has been given 1 crayon.hs:699:8: Constructor `WeightedProperties' should have 4 arguments, but has been given 1

I just changed the WeightedProperties args in each case to, (WeightedProperties (_,p) _ _ _) from (WeightedProperties ((_, p) : _))

D'OH That is the correct fix, yes. I forgot that my HOpenGL bugfix actually changed the API. Jules

Peter Verswyvelen

7:21 p.m.

New subject: crayon - a 2D opengl curve renderer, with Reactive animations

Excellent work! I have been looking into curve rendering myself lately, and found some links that you might find interesting (besides the Loop/Blinn article Bob already forwarded to you) Maxim Shemanarev, the author of the open source anti-grain 2D rendering engine, seems to have tackled the curve stroking (dealing with cusps etc) pragmatically: http://www.antigrain.com/mcseem/index.html http://www.antigrain.com/mcseem/index.html http://www.antigrain.com/research/adaptive_bezier/index.html#PAGE_ADAPTIVE_B... I also came across a kind of curve that I didn't know about yet, named "Pythagorean hodograph curves http://www.research.ibm.com/journal/rd/345/ibmrd3405J.pdf ". These are subsets of Bezier polynomials for which arclength is expressible as a polynomial, and for which offset curves (aka parallel curves) are rational polynomials again (for regular curves arclength and offsets must be approximated numerically). Offset curves could be used to avoid generating all those line segments to stroke a curve, even rendering them directly on the GPU, but I haven't found a fast way for doing this. There's even a full book about PH curves from his inventor: http://www.amazon.com/Pythagorean-Hodograph-Curves-Geometry-Inseparable-Comp... Personally I'm trying to do stroking by approximating cubic Bezier curves and their offset curves with simple quadratic polynomial curves, performing Delaunay triangulation, converting the quadratic curve segments to implicit form, and directly rendering the triangles that form the control points of the quadratics on the GPU. This is more for fun since it is most likely more computationally expensive than just doing very fine subdivision and rendering stroked line segments (although the implicits on the GPU is fully resolution independent of course) On Wed, Mar 25, 2009 at 10:56 PM, Jules Bean wrote:

...

Tom Poliquin wrote:

...
Jules, thanks for uploading the code!

You're most welcome.

...
As a reactive newbie, examples are a gigantic help ..

It works great .. about 40FPS on my ATI Technologies Inc RV515GL [FireGL V3350] using about 3% of my AMD Athlon(tm) 64 X2 Dual Core Processor 6000+ CPU.

Yes, capped to 40fps by the "25" (25 milliseconds = 1/40 seconds) in line 115 inside the idle callback.

If you change that to "0" then it will take up more or less 100% of your CPU and framerates will be much higher. On my machine (nvidia m 8xxx) it does 1000fps (!) for Pong, 400fps for the charts and 100fps for the flowers.

...
I had to make a small change to get it to work on my system (perhaps I'm down rev somewhere) .. but I thought I'd share in case other newbies have the same issue ..

crayon.hs:689:57: Constructor `WeightedProperties' should have 4 arguments, but has been given 1 crayon.hs:699:8: Constructor `WeightedProperties' should have 4 arguments, but has been given 1

I just changed the WeightedProperties args in each case to, (WeightedProperties (_,p) _ _ _) from (WeightedProperties ((_, p) : _))

D'OH

That is the correct fix, yes.

I forgot that my HOpenGL bugfix actually changed the API.

Jules

_______________________________________________ Reactive mailing list Reactive@haskell.org http://www.haskell.org/mailman/listinfo/reactive

Patai Gergely

26 Mar 26 Mar

5:43 a.m.

New subject: crayon - a 2D opengl curve renderer, with Reactive animations

...

Maxim Shemanarev, the author of the open source anti-grain 2D rendering engine, seems to have tackled the curve stroking (dealing with cusps etc) pragmatically: http://www.antigrain.com/mcseem/index.html http://www.antigrain.com/mcseem/index.html http://www.antigrain.com/research/adaptive_bezier/index.html#PAGE_ADAPTIVE_B...

I did something similar in my car racing game (currently under development, naturally in Haskell ;), where the track is defined with B-splines. I keep subdividing those parts where the cosine of the angle between subsequent segments is below a certain limit. I also found that by adding well-chosen textures, this limit--hence the polygon count--can be decreased drastically without any perceivable loss in quality. Gergely -- http://www.fastmail.fm - Or how I learned to stop worrying and love email again

Peter Verswyvelen

10:26 a.m.

New subject: crayon - a 2D opengl curve renderer, with Reactive animations

Good you used B-splines to model your road, since simple Bezier curves don't have continuous curvature between segments, which results in all kinds of trouble. It's really great to see many bright people like you and Quicksilver working on code like this. This is really something Haskell desperately needs IMHO :) 2009/3/26 Patai Gergely

...

...
Maxim Shemanarev, the author of the open source anti-grain 2D rendering engine, seems to have tackled the curve stroking (dealing with cusps etc) pragmatically: http://www.antigrain.com/mcseem/index.html http://www.antigrain.com/mcseem/index.html

http://www.antigrain.com/research/adaptive_bezier/index.html#PAGE_ADAPTIVE_B...

I did something similar in my car racing game (currently under development, naturally in Haskell ;), where the track is defined with B-splines. I keep subdividing those parts where the cosine of the angle between subsequent segments is below a certain limit. I also found that by adding well-chosen textures, this limit--hence the polygon count--can be decreased drastically without any perceivable loss in quality.

Gergely

-- http://www.fastmail.fm - Or how I learned to stop worrying and love email again

_______________________________________________ Reactive mailing list Reactive@haskell.org http://www.haskell.org/mailman/listinfo/reactive

Jules Bean

10:39 a.m.

New subject: crayon - a 2D opengl curve renderer, with Reactive animations

Peter Verswyvelen wrote:

...

Excellent work! I have been looking into curve rendering myself lately, and found some links that you might find interesting (besides the Loop/Blinn article Bob already forwarded to you)

Hey! I showed that article to Bob, not the other way around. Mind you, he was already aware of the technique, of course.

...

Maxim Shemanarev, the author of the open source anti-grain 2D rendering engine, seems to have tackled the curve stroking (dealing with cusps etc) pragmatically: http://www.antigrain.com/mcseem/index.html http://www.antigrain.com/mcseem/index.html http://www.antigrain.com/research/adaptive_bezier/index.html#PAGE_ADAPTIVE_B...

That looks very interesting.

...

I also came across a kind of curve that I didn't know about yet, named "Pythagorean hodograph curves http://www.research.ibm.com/journal/rd/345/ibmrd3405J.pdf ". These are subsets of Bezier polynomials for which arclength is expressible as a polynomial, and for which offset curves (aka parallel curves) are rational polynomials again (for regular curves arclength and offsets must be approximated numerically). Offset curves could be used to avoid generating all those line segments to stroke a curve, even rendering them directly on the GPU, but I haven't found a fast way for doing this. There's even a full book about PH curves from his inventor: http://www.amazon.com/Pythagorean-Hodograph-Curves-Geometry-Inseparable-Comp...

Personally I'm trying to do stroking by approximating cubic Bezier curves and their offset curves with simple quadratic polynomial curves, performing Delaunay triangulation, converting the quadratic curve segments to implicit form, and directly rendering the triangles that form the control points of the quadratics on the GPU. This is more for fun since it is most likely more computationally expensive than just doing very fine subdivision and rendering stroked line segments (although the implicits on the GPU is fully resolution independent of course)

I'm concerned about the cost of repeated triangulation; I'm trying to find an algorithm fast enough for realtime animation (where the control points may move every frame). Mind you some kind of repeated calculation can't be avoided - it's interesting to consider algorithms which can reduce the work for 'small perturbation' (e.g. where the topology hasn't changed) but it's not obvious how to make that efficient. Loop-Blinn is obvious a good way to go for a fixed vector input (e.g. a font) which can be preprocessed. Jules

Thomas Davie

10:46 a.m.

On 26 Mar 2009, at 15:39, Jules Bean wrote:

...

Peter Verswyvelen wrote:

...
Excellent work! I have been looking into curve rendering myself lately, and found some links that you might find interesting (besides the Loop/Blinn article Bob already forwarded to you)

Hey! I showed that article to Bob, not the other way around. Mind you, he was already aware of the technique, of course.

No, I think peter is confusing this and the vector-texture article I pointed you at. Bob

Peter Verswyvelen

11 a.m.

New subject: crayon - a 2D opengl curve renderer, with Reactive animations

On Thu, Mar 26, 2009 at 3:39 PM, Jules Bean wrote:

...

Peter Verswyvelen wrote:

...
Excellent work! I have been looking into curve rendering myself lately, and found some links that you might find interesting (besides the Loop/Blinn article Bob already forwarded to you)

Hey! I showed that article to Bob, not the other way around. Mind you, he was already aware of the technique, of course.

Oh, I also told Bob about that article, which is published in GPU GEMS 3. I must have misunderstood. It is of course a very famous article ( but the technique is patented :| )

...

Maxim Shemanarev, the author of the open source anti-grain 2D rendering

...
engine, seems to have tackled the curve stroking (dealing with cusps etc) pragmatically: http://www.antigrain.com/mcseem/index.html http://www.antigrain.com/mcseem/index.html

http://www.antigrain.com/research/adaptive_bezier/index.html#PAGE_ADAPTIVE_B...

That looks very interesting.

Yes, I think what Maxim accomplished is insane. I also came across a kind of curve that I didn't know about yet, named

...

...
"Pythagorean hodograph curves < http://www.research.ibm.com/journal/rd/345/ibmrd3405J.pdf> ". These are subsets of Bezier polynomials for which arclength is expressible as a polynomial, and for which offset curves (aka parallel curves) are rational polynomials again (for regular curves arclength and offsets must be approximated numerically). Offset curves could be used to avoid generating all those line segments to stroke a curve, even rendering them directly on the GPU, but I haven't found a fast way for doing this. There's even a full book about PH curves from his inventor: http://www.amazon.com/Pythagorean-Hodograph-Curves-Geometry-Inseparable-Comp...

Personally I'm trying to do stroking by approximating cubic Bezier curves and their offset curves with simple quadratic polynomial curves, performing Delaunay triangulation, converting the quadratic curve segments to implicit form, and directly rendering the triangles that form the control points of the quadratics on the GPU. This is more for fun since it is most likely more computationally expensive than just doing very fine subdivision and rendering stroked line segments (although the implicits on the GPU is fully resolution independent of course)

I'm concerned about the cost of repeated triangulation; I'm trying to find an algorithm fast enough for realtime animation (where the control points may move every frame). Mind you some kind of repeated calculation can't be avoided - it's interesting to consider algorithms which can reduce the work for 'small perturbation' (e.g. where the topology hasn't changed) but it's not obvious how to make that efficient.

Loop-Blinn is obvious a good way to go for a fixed vector input (e.g. a font) which can be preprocessed.

Yep indeed. Only solves halve of the "animated stroked curves" problem

Jules Bean

11:10 a.m.

New subject: crayon - a 2D opengl curve renderer, with Reactive animations

Peter Verswyvelen wrote:

...

On Thu, Mar 26, 2009 at 3:39 PM, Jules Bean mailto:jules@jellybean.co.uk> wrote:

Peter Verswyvelen wrote:

Excellent work! I have been looking into curve rendering myself lately, and found some links that you might find interesting (besides the Loop/Blinn article Bob already forwarded to you)

Hey! I showed that article to Bob, not the other way around. Mind you, he was already aware of the technique, of course.

Oh, I also told Bob about that article, which is published in GPU GEMS 3. I must have misunderstood. It is of course a very famous article ( but the technique is patented :| )

It would be interesting to know whether or not the patent is aggressively enforced. I don't know if anyone (Conal?) has contacts who would know.

Achim Schneider

11:58 a.m.

Jules Bean wrote:

...

Peter Verswyvelen wrote:

...
On Thu, Mar 26, 2009 at 3:39 PM, Jules Bean mailto:jules@jellybean.co.uk> wrote:

Peter Verswyvelen wrote:

Excellent work! I have been looking into curve rendering myself lately, and found some links that you might find interesting (besides the Loop/Blinn article Bob already forwarded to you)

Hey! I showed that article to Bob, not the other way around. Mind you, he was already aware of the technique, of course.

Oh, I also told Bob about that article, which is published in GPU GEMS 3. I must have misunderstood. It is of course a very famous article ( but the technique is patented :| )

It would be interesting to know whether or not the patent is aggressively enforced. I don't know if anyone (Conal?) has contacts who would know.

You know, every time I hear something like that I can't help but to think "just ignore the bleeding American market" -- (c) this sig last receiving data processing entity. Inspect headers for copyright history. All rights reserved. Copying, hiring, renting, performance and/or quoting of this signature prohibited.

Jason Dusek

9:32 p.m.

New subject: crayon - a 2D opengl curve renderer, with Reactive animations

Theses Pythagorean Hodograph curves are interesting stuff. -- Jason Dusek

Peter Verswyvelen

27 Mar 27 Mar

6:47 a.m.

New subject: crayon - a 2D opengl curve renderer, with Reactive animations

Oh yeah, they are! They seem to reduce a bit of freedom in the design space, but give lots and lots of benefits for computation. For games, these are excellent curves I think (fast arc length reparametrization, simple offset curves, ...) On Fri, Mar 27, 2009 at 2:32 AM, Jason Dusek wrote:

...

Theses Pythagorean Hodograph curves are interesting stuff.

-- Jason Dusek

5898

Age (days ago)

5900

Last active (days ago)

List overview

Download

12 comments

7 participants

participants (7)

Achim Schneider
Jason Dusek
Jules Bean
Patai Gergely
Peter Verswyvelen
Thomas Davie
Tom Poliquin