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.

———————

So.

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:

http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Partition_2/Chapter_main.html

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

for example:

http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Mesh_2/Chapter_main.html

(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:

http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Straight_skeleton_2/Chapter_main.html

(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:

http://www.graphics.rwth-aachen.de/publication/44/

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='http://www.w3.org/2000/svg' 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(10,0)); body.push_back(Point_2(5,5)); */ 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(8,1)); hole.push_back(Point_2(5,4)); */ 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) holes[i].reverse_orientation(); 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 ; ssb.enter_contour(body.vertices_begin(),body.vertices_end()); for (int i=0;i<holes.size();i++) { ssb.enter_contour(holes[i].vertices_begin(),holes[i].vertices_end()); } 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.

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.

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

Yay!

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:

Three holes with a lil’ bit odd shapes:

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

Pingback: Straight Skeleton of polygons in 3d | Cake Baby