Login | Register   
LinkedIn
Google+
Twitter
RSS Feed
Download our iPhone app
TODAY'S HEADLINES  |   ARTICLE ARCHIVE  |   FORUMS  |   TIP BANK
Browse DevX
Sign up for e-mail newsletters from DevX


advertisement
 

"Fat" Marching Ants: An Algorithmic Experimentation Using GDI+ : Page 5

"Marching ants" are a common UI feature in image editing programs but giving the ants a little more visual texture is a harder problem than you'd ever dream. This article discusses four different algorithms for making elegant, 3D ants with varying levels of performance, accuracy, and control.


advertisement
Performance
I didn't conduct a serious performance analysis due to the conceptual and technical difficulties. Instead, I just ran Squigler, switched renderers ('spacebar') while increasing and decreasing the radius parameter ('+' and '-'). Note that I use double buffering of the entire form. The results astonished me. All the renderers except the DashRenderer had the same perceived performance (seemed to run at the same speed). The DashRenderer was much faster then any of the others. This may be explained by the fact that the other renderers are doing a lot of work at the managed code level and have to cross back and forth from the managed to the unmanaged world a lot. Maybe. However, playing with various render parameters such smoothing (anti-aliasing) had no noticeable effect. Changing the radius, however, had a dramatic effect since it increases/decreases the number of pixels that need to be massaged and pushed around. Sad but true: You can never get an idea of how well your code will perform without profiling your production system with production input data.

It is also important to know when NOT to optimize. In this case the usage scenario is an animated outline to some arbitrary shape in a potentially rich graphic scene. Higher performance means the animated line will move faster. Here is an idea for improving the performance of the custom FMAs: I will concentrate on the line-based FMA. The basic idea is to draw only the pixels that need to be drawn without repetitions, calculate offsets only once, and avoid crossing the managed-unmanaged bridge as much as possible. The algorithm:

  • Lock the screen buffer and get direct access to the bits
  • For each line segment calculate the arc once (just like in the line-based FMA)
  • Perform a single Bresenham traversal of the line segment
  • For each point along the line belonging to an ant, draw all the pixels at an offset from corresponding points in the base arc
  • Unlock the screen buffer when you are done
This is much better (theoretically speaking) then all the other algorithms. No multiple crossing of the managed unmanaged world, direct memory access, and a single Bresenham traversal per line segment.

The Ants Go Marching On
In this article I attacked a novel algorithmic problem of rendering fat marching ants. My approach was to start from a solution to a close problem (standard marching ants) and then try some variations. When I started I didn't have all these algorithms in mind. Actually, I had exactly one algorithm that I thought of initially: the arc-based FMA. However, while implementing it I was annoyed by some properties of the solution, tried to improve them, and came up with the other algorithms gradually. Many people say that you have to understand a problem before you can solve it. I say that you have to solve a problem in several ways before you can really understand it (at least when it comes to software development).





Gigi Sayfan specializes in cross-platform object-oriented programming in C/C++/C#/Python/Java with an emphasis on large-scale distributed systems. He is currently trying to build brain-inspired intelligent machines at Numenta.
Comment and Contribute

 

 

 

 

 


(Maximum characters: 1200). You have 1200 characters left.

 

 

Sitemap
Thanks for your registration, follow us on our social networks to keep up-to-date