Jump to content
  • Advertisement
Sign in to follow this  
snaileri

OpenGL Fast way to smooth a 2D polygon

This topic is 2344 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello,
I've made a small demo showing a softbody which is created with the JBox2D physics engine (rendered with Slick2D / LWJGL / OpenGL).
[media]
[/media]

As you can see the shape is made of 20 circle bodies that are connected to each other.
I need a fast algorithm for real-time rendering that smooths the surface of the shape, so that you can't see how many corners there are.

I can think of two ways for how this could be achieved:
The polygon can be blurred with a shader, and then use another shader to cut out the pixels with certain transparency, similar to how metaballs are usually done. The problem with this solution is the amount of blur it takes to smooth out some of the edges in certain situations - The blur might destroy the shape's fine details. Also, heavy blurring requires more processing power, I think.

Or, some bezier curve -algorithm could be used to calculate the curves between each corner-point of the shape. This sounds highly complex and slow, but I could be wrong.

I'm not a very experienced programmer, so the more detailed help you can give the better.

I'm also looking for a way to make a few pixel think border around the shape. Edited by pekhe

Share this post


Link to post
Share on other sites
Advertisement
Subdivision? A simple approach would be to take each edge and split it in half, then take each original vertice and move it towards the midpoints of its edges. Can of course be done recursively until it is smooth enough.

I imagine there is a way to tessellate it on the gpu, but I am not sure how one would implement that.

I also recall a GPU Gems article about drawing smooth vector shapes. http://http.developer.nvidia.com/GPUGems3/gpugems3_ch25.html

Share this post


Link to post
Share on other sites
Could you tell in more detail how the subdivision approach works?
"...[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

[background=rgb(250, 251, 252)]then take each original vertice and move it towards the midpoints of its edges." [/background]

[/font][color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

[background=rgb(250, 251, 252)]You mean towards the newly created points? As I try to grasp this idea on paper I don't understand how this would help.[/background]

[/font]

The GPU Gems article explains bezier curves that use 4 control points each. It's difficult to do an algorithm which would calculate the positions of those control points.
While googling, I found a method called "natural cubic spline" which uses only one control point per curve - the cornerpoint in the polygon.
http://www.cse.unsw.edu.au/~lambert/splines/
There's also a source-code available, but I can't get it to work (some errors when I try to run the project in Eclipse). The math looks too complex for me, and I'd rather just copy&paste the code once I've found the right part. I hope someone could help me with this.
And even if I understood the math, I'd have problems trying to turn the math into a code. Still waiting for more help with these approaches, and I'd also like to know if there are even more methods.

Share this post


Link to post
Share on other sites
I won't go into to much detail, I am terrible at explaining things.
But here is a simple diagram:
[attachment=10020:the best diagram of all time.jpg]

Each edge is split in half, adding new vertices at their mid points (see green dots). Then we move the original vertices(in blue) closer to the mean of its newly added neighbours.

This is a very simple approach, no fancy math, I will surprised if a simpler method appears.

Share this post


Link to post
Share on other sites
This is the easiest way?
Q2gte.jpg
I'll start making this, but I'm still hoping that someone can explain to me how the natural cubic spline works. Or if shaders can be used for smoothing the polygon. Edited by pekhe

Share this post


Link to post
Share on other sites
What about a simple Catmull-Rom spline? It has the advantage of passing through all of the control points and is fairly easy to implement. You could subdivide every edge into two or more edges and use Catmull-Rom to calculate the points in between.

Share this post


Link to post
Share on other sites
I'd recomment JimC's subdivision algorithms. it's like the 2d version of catmull clark: http://en.wikipedia.org/wiki/Catmull–Clark_subdivision_surface
the 'movement' of the original point can be quite well defined, maybe you can adapt the formula from wiki for 2d. in simplest case I'd use the average of the two center points and the edge (P1+E0+E1)/3 :)

the nice thing bout that subdivision sheme is that you can do it recurvise, especially in 2d it's simple to make it even adaptive, subdividing lines just above some special treshold, to still keep the poly count limited.

Share this post


Link to post
Share on other sites
Since you do a soft body simulation, you must have "pressure" vectors at every vertex already, in some form. That's the vectors used to push/pull a control points away from the center of mass, calculated in some way.

The arithmetic mean of the pressure vectors on two control points is an approximation of the value on the ball's surface in the middle between the two points. It is of course not precise due to curvature and surface stretch, but it generally points in the right direction, and its length is more or less the same ballpark unless the tesselation is extremely poor so vectors of adjacent points point away when they shouldn't. Create a point in the middle between two control points (simple arithmetic mean of cartesian coordiantes) and offset this point by a fraction (I'd try something between 1/3 and 1/2) of the approximated vector.

This is not precise science, but it is ultra fast, does not alter the correctly integrated and collision-checked original control points (which may be important), and moves points in the correct direction. If not precise, it should still should give a believeable approximation. Edited by samoth

Share this post


Link to post
Share on other sites

[background=rgb(250, 251, 252)]I went with JimC's subdivision algo. Here's the result:[/background]



VCt77.png
1x subdivision was enough to hide the corners. It looks beautiful in motion.

samoth, could you please explain your approach visually? I don't understand what kind of vector you mean.
If I have to optimize the smoothing algorithm later, I'd be interested to try out yours.

Also, as I mentioned in the first post, I need a way to render an outline (~5 pixels thick) for the shape. How can I achieve this? Edited by pekhe

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!