Milestone: .Net Boolean Path Engine

Well, today I am celebrating bit of a milestone with regard to my graphics project. I finally have an operational 2D vector path engine which is capable of boolean operations. It supports union, intersection and subtraction of bezier and straight line paths with holes and seems to be working really well, at long last!

One of the things that has really helped develop this engine is the vast suite of unit tests. It's amazing just how many tricky path operations you can devise that can really stress the engine. What may originally seem a relatively simple task reveals itself to have many complications with several degenerate or special cases.

There have been a number of 'what if?' test cases I have thrown at the engine that have revealed areas that need to be improved. Particularly tricky problems include: subtraction of a subpath from a path, e.g. half a hexagon from a hexagon, union and subtraction operations on paths which include shared edges, paths that contain perfectly overlapping bezier sections, bezier curves that lie almost on top of each other and many more. In fact, I now have nearly 100 test cases for path operations, which I will continue to add to.

One thing I am really pleased about is just how well my engine compares to other commercial and non commercial engines. It's fun to take some of the trickiest test cases to see how the results compare to dedicated vector applications such as Xara X, Inkscape and Expression Blend. Because I have tweaked my engine to cope with these test cases, I can say that the output compares very favourably with each of the other applications - so I must be doing something right. That's not to say that the engine is perfect, there are bound to be new test cases that expose some limitations, but overall I am pleased. However, if you have any ideas for tricky operations, please let me know and I'll add them to my tests. I'll also try and post some images of some of the trickiest tests.

Certainly, one area that could still do with some extra tweaks is the performance with asymptotic paths, which can be slow. However, overall I'm in the mood to celebrate.

Comments

Post a Comment

Popular posts from this blog

Welcome to my World

Hi and welcome to my world! This is my new blog, where I intend to chat about graphics. More specifically, the challenges of creating a new graphics product that can be used to automatically generate 3D models of rooms - the output of which is aimed at the graphics professional. I already have some experience at this, having written a tool I use myself to generate 3D models that look great - but it's now time for some improvements and to make it more useable. Join me for the ride, if you're interested. In this blog, I'll post some thoughts about graphics, software and usability and hopefully a few tasters and screenshots of what 'RoomBuilder2' can do. Perhaps I need a more catchy name, but so many are already taken ... Ok let's call it Xyecco. Thanks, Max
Read more

Holographic Capture using Multiple Kinect - A DIY Approach with Lessons Learned!

Image
Lessons Learned Creating a DIY Holographic Capture Rig using Multiple Kinect Sensors I’ve always had a strong interest in technology and photography and consider myself to be an early adopter. I also have a passion for graphics, virtual reality and have a background in software architecture and development. Several years ago, I acquired a Kinect for Windows device, but because of USB issues on my main PC, I didn’t get around to playing with the hardware for a long time. Kinect can be notoriously fussy about which USB 3 controllers it will work with, this is a well-documented issue .   Eventually, I managed to get a USB expansion card that played nicely with the Kinect and I fired up the SDK examples to see what it could do. I was impressed, even if there was a lot of depth noise, particularly at the edge of objects - so called flying pixels. I’m not sure when it happened, whether it was prompted by getting an Oculus VR kickstarter headset (DK1) or by the birth of my daughte...
Read more

Straight Skeleton Madness (a plea for help)

Image
After completing my work on boolean path operations, I have moved on to looking at algorithms for offsetting polygons. One of the ones that stands out is known as the 'straight skeleton' algorithm. This computes a set of connected paths which describe the position of verticies as the polygon offset size is altered. Unfortunately, it's only directly applicable to straight line paths (with mitre joins), but that's good enough for now. The algorithm is straightforward for convex polygons, but gets a little bit more complex when dealing with concave points, since this can lead to the creation of sub paths. In theory, while the straight skeleton is not directly applicable to offsetting, it produces a structure which can be used to calculate an offset path. As an aside, the straight skeleton of a polygon is ideal for determining its 'roof structure' - which will be of use elsewhere in my software. Progress on my .NET straight skeleton code has been slow but fairly dec...
Read more