Hello world!

My First Blog Post. On Word Press. Yay.

In case you don’t know me, I spend an inordinate amount of time farting around with a computer program called OpenSCAD, created by Marius Kintel and Clifford Wolf. OpenSCAD is used in ‘3d printing’ which lets you print things off the computer in 3d.

One thing people want with OpenSCAD is to export the AMF file format, which is a fancy acronym based buzz thing that can do more than the old format, called STL. Anyways in order to actually do that with any kind of interesting results we need to deal with the fact that AMF is made up of something called Volumes.

For example if you have, say, two blocks in your ‘scene’ that you want to 3d print, that would be, presumably, two Volumes.

That is pretty cool. But its really cool because OpenSCAD might have a nice way to do this. Because OpenSCAD is based on something called CGAL which was invented by a whole bunch of people in Europe getting together and pooling their algorithms about 10 years past.  Check it out at http://cgal.org

CGAL has a thing called a Nef Polyhedron, which is basically another way to say “a shape”. However, these are special shapes. They are based on the work of Walter Nef , who wrote a book in the 1970s about this stuff. He figured out that you could describe a shape by saying it was an intersection of half-spaces. Lets for a moment imagine a cube. It’s really, you know, 6 planes that have been intersected with each other.. isn’t it? Well, lets not just say planes, let’s say “half spaces”. Because of course every plane separates the universe into two parts, or at least we can imagine it to be so. These two parts, half spaces, then, are separated by a plane. One side of the plane is considered ‘mass’ or ‘inside’, and the other side is considered ‘space’ or ’emptiness’ or ‘outside’. Now you can imagine if you intersect 6 of these together, you have yourself a solid cube. Similar to what the Tao Te Ching says, the thing that makes this interesting is the concept of Emptiness – what is a cup without a hole in it? What are shapes without the space outside of them?

So we come back to CGAL. It uses Cgal Nef Polyhedron3 to represent these Nef polyhedrons within a computer. But how exactly? You can read the details here

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

But to make it short, they have Volumes, each of which has Shells, which in turn have Facets (which you might think of as ‘faces’, or flat polygons), and those are our planes. Now each of these things is given a mark which indicates something about their relationship to  ‘inside’/’mass’/’body’ versus ‘outside’/’emptiness’/’space’.

How exactly do the CGAL Volumes work though? Are they the same as AMF volumes?

No, not really. Let’s take OpenSCAD example004.scad which is basically a solid cube subtracted by a solid sphere.

Снимок экрана от 2013-02-03 14:03:18

OK. Cool. That’s how it looks inside OpenSCAD using Florian Kirsch’s OpenCSG rendering algorithm. ( http://www.opencsg.org ). It looks the same if you render with CGAL. See all those flat planes? We have created the illusion of a spherical shape, using only flat polygons (planes) — dividing, as stated above, half spaces. There are a lot of them here. But that’s all they are. Flat planes dividing half spaces.

But where are the volumes? Where is the CGAL Nef Polyhedron?? Well, this next picture shows it. It turns out you can ‘dump’ the structure of the Nef Poylhedron into an SVG picture if you compile OpenSCAD’s source code and insert a nef_poly->dump(); command into the right place. Here is Example001’s Nef Polyhedron, dumped.

Снимок экрана от 2013-02-03 12:45:54

On the left, we have the ‘ordinary’ Inner volume. It’s hard to see, but there is the gold ‘cube’, and the green ‘sphere’ that has been subtracted from the cube. Where does the color come from? As mentioned above, all of CGAL’s things, the volume, shells, and facets, have a Mark.  Some have mark ‘1’ and some have mark ‘0’, (or ‘true’ and ‘false’). Gold represents facets of mark 1. Green represents facets of mark 0.  I am not really sure why those specific facets are 0 and 1 – but it’s obviously something to do with the ‘subtraction’ operation done between the sphere and cube.

OK. Great! But what is this blue business on the right?

The blue actually represents the Outer Volume. Apparently,  a  CGAL Nef Polyhedron that represents a 3d shape has at least two volumes for that shape, the ‘inside’ and the ‘outside’. The ‘negative’ or ‘outer’ volume is made of basically all the same facets as the ‘inner’ volume, and all of these facets have marks too. In this case I just chose to color them all blue regardless of facet mark.

Wait, how did I know which was Inner and Outer in the data structure?

Inner Volumes have a mark of 1. Outer volumes have a mark of 0. That’s how you tell.

—————-

OK. Great so far. What about a scene with two cubes, like you were talking about above? Yes. What about it! Let’s try it. Here is the .scad code:

cube(5);

translate([10,10]) cube(5);

Now, here is the Nef Polyhedron dump

Снимок экрана от 2013-02-03 13:44:33

Wow… so what is that all about?

There are actually Three Volumes here.  (Hard to see the Yellow, but it’s there on the second and third panel).

The first volume, the blue volume, the Volume With Mark 0, is acutally the Outer Volume. I am not exactly sure how to imagine this, but it’s almost like, if you want to imagine ’empty space’ as a ‘thing’, then This is the Boundary where Empty Space actually ‘ends’ and where the ‘stuff’ begins. Perhaps that is why there are two ‘shells’ inside of one ‘volume’, because ’empty space’, as a thing, is all just one thing.

The second volume is a Volume with Mark 1. It is one of our cubes. The third volume is another  Volume with Mark 1it is our second cube.

Neato. So CGAL actually makes several volumes in these situations. One for the ‘outer’ and several for each ‘thing’ sitting out there in space.

————-

Great, but what does that mean for AMF?

It means that we only want to take the CGAL Inner Volumes and somehow export them as individual AMF volumes.

This is a bit tricky ——- The only way to access the CGAL Nef Polyhedron Volume is through a complicated ‘visitor’ doohickey – and it doesn’t by default allow you to just extract the data within it in some ordinary format like another CGAL Nef Polyhedron. It only gives you things like Shells and Facets and Vertexes that lie within the volume. All of the infrastructure we have, like code that converts CGAL Nef Polyhedron to ordinary CGAL Polyhedron 3, will not immediately ‘plug in’ here with out a bunch of ‘glue code’.

But I think that glue code wouldn’t be impossible to write. You just have to spend some quality time with the OpenSCAD source code, and these web pages.

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

http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Nef_3_ref/Class_Nef_polyhedron_3.html

http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Polyhedron_ref/Class_Polyhedron_3.html

http://www.stackoverflow.com

http://www.cplusplus.com

And of course this could all be wrong…

Advertisements

About donbright

https://patreon.com/donbright https://github.com/donbright http://dwitter.net/u/donbright
This entry was posted in Uncategorized. Bookmark the permalink.

One Response to Hello world!

  1. Pingback: On adding colors to CGAL’s Nef Polyhedron | Cake Baby

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s