Straight Skeleton into SVG

So (I love starting with ‘so’). So.

So im trying to add Subdivision Surfaces to OpenSCAD. There
is already a stub of the code put in there (presumably)
by the original authors, Clifford Wolf and Marius Kintel.

The issue with Subdivision Surfaces is that they
are very, very picky about what the ‘input mesh’
is to them. The GuerillaCG project has a great
video about this, here:

The problem with OpenSCAD right now
is that it is not very careful about it’s meshes,
to be specific, CGAL’s Nef Polyhedra to Polyhedra
converter uses triangulation of all surfaces. This
triangulation, when fed to Subdivision Surface
algorithms, makes the result strangely ‘twisted’
and odd looking. It is not nice and symmetrical
like you see in Subdivision Surface examples you
find on the internet in some places. For example,
subdiving a cube doesn’t result in a nice spherical
shape but instead an interesting cuboid-sphere shape
that has weird non-symmetrical parts on it.

A similar problem can be found when doing a subdivision
on a cylinder – since CGAL’s Nef->Polyhedron converter
does a triangulation on all surfaces so that the triangles ‘fan out’
from a single point on one ‘side’ of the face,
we get a cylinder that subdivides down into a lopsided
‘seashell’ shape instead of an ordinary blobby symmetrical
smooth cylinder thing.

Now, it can be interesting to have these weird twist shapes,
but I’m trying to make it ‘intuitive’ so that people who
look up “subdivision surfaces” on the web, or do one
in blender or something, will ‘get it’ when they type

subdiv() cube();

into OpenSCAD.



The first step was to modify the NefPolyhedron->Polyhedron
converter. Get rid of the non-symmetrical triangulation
and just feed straight out polygons to the Subdivision
algorithm. This actually works pretty easily – for
simple Nef Polyhedra – like a Cube or a Cylinder.

The problem is you have a Polyhedron with a ‘hole’
in one of it’s faces. For example, a cube subtracted
from a cube – sort of a like a ‘cup’ shape. A ‘crate’
thing with one of it’s sides torn off.

The problem here is that the Polyhedron construction
code can only accept ‘simple’ polygons as input.
Polygons with holes wont work. So the issue is

how to convert Polygons With Holes into a bunch of
Polygons Without Holes (aka Simple Polygons?)


So I wind up trying to take a Polygon With Holes and change it into a
sequence of Simple Polygons. This is a bit of a challenging
Problem Of Geometry, but there are many solutions.

For example. One is ‘convex decomposition’ also known
as “Partitioning”. For example:

Another way to do it is ‘Triangulation’, aka Tessellation with Triangles,
for example:

(Scroll down to the “With Holes” part).

And … also. We have the Skeletonization thing. a “Straight Skeleton”
is sort of like ‘shrinking’ a polygon over and over. For example:

(Note that last example doesn’t have an actual picture of
a skeletonization with a real polygon with holes. They have
a skeletonization of something that looks like holes, but
if you look closely, its actually a “keyhole polygon”,
a polygon with holes where the holes have been
“connected” (see CGAL’s connect_holes() function)
and it’s actually one polygon that ‘wraps around’
the holes and has edges that touch each other.

And finally there is Tessellation with Quadrilaterals instead of Triangles. This is also called Quadrangulation. Example:

CGAL Doesn’t Do quadrangulation though, that I know of, so I’m skipping it.

So which one, of the available methods, do we choose? Well, recall from above that the whole point of this is Subdivision Surface
algorithms. They, again, are very sensitive to
the mesh given as input. In fact, I am going to
go on a limb and assume they need ‘symmetrical’
meshes as input. I wont know for sure till im
done, but I’m going to guess this is what we do.
Go for symmetric. And that means Skeletons.

How do we do this? Triangulation isn’t really
symmetrical. Neither is partitioning, although
theoretically partitioning could be made
‘more symmetrical’. But Im trying to avoid
inventing new algorithms.

Now what about Skeleton? It’s true – it inserts
vertexes that we dont need. On the other hand,
it’s symmetrical. Let’s try it.

But how? The first step is to get a basic 2d
version working. And to be able to actually
look at results.

Here is some example code.


Follows is a highly experimental (rough) snip of code, based on code in
CGAL’s examples directory, that takes a Polygon With Holes
and outputs a Decomposition based on the
Straight Skeleton code.

The code is very rough, but it shows the basic idea.
You create a polygon, two holes, run the Straight
Skeleton algorithm, and then iterate through the
resulting Faces, dumping them as SVG paths.

It seems simple, but it’s a bit unclear in the
CGAL documentation how to do this exactly. The
iteration around the faces of the Skeleton is
essentially based on guess work, hoping that it worked
similarly to the “halfedge around facet circulators”
that are usedin the 3d Nef Polyhedron code elsewhere
in CGAL.

A result picture is included at the end.
The colors have been added by hand by editing
the resulting SVG.

Viewing the SVG can be done in a browser like
Firefox (File/Open).

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Partition_traits_2.h>
#include <CGAL/partition_2.h>
#include <CGAL/connect_holes.h>
#include <CGAL/enum.h>
#include <CGAL/Straight_skeleton_builder_2.h>
#include <cassert>
#include <list>
#include <iostream>

typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef Kernel::Point_2                                     Point_2;
typedef CGAL::Polygon_2<Kernel>                                   Polygon_2;
typedef CGAL::Polygon_2<Kernel>::Vertex_iterator             Vertex_iterator;
typedef CGAL::Polygon_with_holes_2<Kernel> Polygon_with_holes_2;
typedef CGAL::Partition_traits_2<Kernel>::Polygon_2 Partition_Polygon_2;
typedef Partition_Polygon_2::Vertex_iterator Partition_Vertex_iterator;

typedef CGAL::Straight_skeleton_2<Kernel> Ss;
typedef boost::shared_ptr<Ss> SsPtr;
typedef CGAL::Straight_skeleton_builder_traits_2<Kernel>      SsBuilderTraits;
typedef CGAL::Straight_skeleton_builder_2<SsBuilderTraits,Ss> SsBuilder;

int main()
std::cout << "<svg xmlns='' version='1.1'>";
std::cout << "<g transform='scale(20 -20) translate(0 -10)'>";
std::cout << "<!-- \n";

   Polygon_2    body;
/*	body.push_back(Point_2(0,0));
   body.push_back(Point_2(0, 0));
   body.push_back(Point_2(10, 0));
   body.push_back(Point_2(10, 10));
   body.push_back(Point_2(0, 10));

	Polygon_2 hole;
/*	hole.push_back(Point_2(2,1));
   hole.push_back(Point_2(1, 1));
   hole.push_back(Point_2(4, 1));
   hole.push_back(Point_2(4, 4));
   hole.push_back(Point_2(1, 4));

	Polygon_2 hole2;
   hole2.push_back(Point_2(6, 9));
   hole2.push_back(Point_2(9, 9));
   hole2.push_back(Point_2(9, 6));
   hole2.push_back(Point_2(6, 6));

	Polygon_2 hole3;
   hole3.push_back(Point_2(1, 6));
   hole3.push_back(Point_2(4, 6));
   hole3.push_back(Point_2(4, 9));
   hole3.push_back(Point_2(1, 9));

	std::vector<Polygon_2> holes;
	holes.push_back( hole );
	holes.push_back( hole2 );
//	holes.push_back( hole3 );

	if (body.orientation() != CGAL::COUNTERCLOCKWISE) body.reverse_orientation();
	std::cout << "\norientation body: " << body.orientation() << "\n";

	for (int i=0;i<holes.size();i++) {
		if (holes[i].orientation() != CGAL::CLOCKWISE)
		std::cout << "orientation hole " << i << ":" << holes[i].orientation() << "\n";

	// original points = holes + body
//	Polygon_with_holes_2 pgon( body, holes.begin(), holes.end() );

	std::cout << "\n_________________-\n";

    SsBuilder ssb ;

	for (int i=0;i<holes.size();i++) {

    boost::shared_ptr<Ss> ss = ssb.construct_skeleton();
	std::vector<Polygon_2> output_polys;

	if ( ss ) {
		Ss::Face_const_iterator fi;
		for (fi = ss->faces_begin(); fi!=ss->faces_end(); fi++ ) {
			Polygon_2 tmp;
			std::cout << " face..\n";
			Ss::Halfedge_const_handle v1(fi->halfedge());
			Ss::Halfedge_const_handle vi(v1);
			do {
				std::cout << "  circ.. " ;
				std::cout << vi->vertex()->point();
				std::cout << "\n" ;
				tmp.push_back( vi->vertex()->point() );
				vi = vi->next();
			} while (vi != v1 );
			output_polys.push_back( tmp );
// Ss::Vertex_const_iterator vi;
// for ( vi = fi->vertices_begin(); vi != fi->vertices_end(); vi++ ) { // }
	} else {
		std::cout << "construction of skeleton failed\n";
//    if ( ss ) print_straight_skeleton(*ss);

	std::cout << "\n--> \n";

	for (int i=0;i<output_polys.size();i++) {
		Polygon_2 pgon = output_polys[i];
		std::cout << "<path d='M";
		std::cout << pgon.vertices_begin()->x();
		std::cout << ",";
		std::cout << pgon.vertices_begin()->y() << " ";
		for ( Vertex_iterator j = pgon.vertices_begin(); j != pgon.vertices_end(); j++ ) {
			std::cout << "L";
			std::cout << j->x();
			std::cout << ",";
			std::cout << j->y();
			std::cout << " ";
		} std::cout << "Z' fill='none' stroke='black' stroke-width='0.1'/>\n\n";
	} std::cout << "\n";

	std::cout << "\n</g> </svg>\n";
   return 0;


A polygon with holes. 1: A big square (also known as ‘border’ or ‘body’ or ‘outline contour’ or whatever)

2: Two little ‘holes’ inside of it.

Screenshot from 2013-04-06 22:33:29

The results of the Skeletonization: 12 small faces that, together, make up the same shape as the ‘polygon with holes’ above. Three of these faces have been highlighted by hand with color.

Screenshot from 2013-04-06 22:29:12

So here we have it. The Polygon With Holes has been converted to some relatively symmetrical looking sequence of Polygons Without Holes.


Next up – how to do this on 3d polygons? Ai chihuahua.

And will it even work? Will it totally mess up the subdivision algorithm? Ai chihuahua.


PS. Here are some more examples.

Three holes:

Screenshot from 2013-04-06 23:21:08

Three holes with a lil’ bit odd shapes:

Screenshot from 2013-04-06 23:23:28

And the same three holes, with one vertex moved ‘up’ quite a bit:

Screenshot from 2013-04-06 23:28:27


One thought on “Straight Skeleton into SVG

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s