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 **Volume**s 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.

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.

On the left, we have the ‘ordinary’ **I****nner**** 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**

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 1**, it 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

And of course this could all be wrong…

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