On adding colors to CGAL’s Nef Polyhedron

CGAL is a big bunch of computer code that can do Geometry in a computer.

Some folks are wanting to add Color to it so that 3d-printing with multiple colors and/or materials can be accomplished from CGAL shapes, within Marius Kintel and Clifford Wolf’s OpenSCAD program.

It’s a bit tricky though! Color is not built into CGALs CGAL Nef Polyhedron shape … so it would have to be added. But how?

The problem with doing this is that when you have colored shapes, you change the meaning of what union and intersection actually mean.

Example. Consider two rectangles, a and b. They overlap.

1

If they are both the same color it is pretty obvious what Union and Intersection mean. Union looks like this:2

Intersection is that little bit in between them.

3

It’s alot like Venn Diagrams. Actually it’s exactly like Venn Diagrams. Although just because I’m trying to get this done before the sun sets, I have ignored the entire issue of the Boundary Line and how it fits into the whole picture (important topic by the way, but it’s another story for another time).

OK. So far so good.

Fun things to notice about this

A union B  is the same thing as B union A.

A intersection B is the same thing as B intersection A

Keep that in mind.

———————–

Now…

What happens when A and B have different colors?

4

Ahhh…

What happens to that little bit in the middle? What color should it be? Right now I left it blank with a Question Mark in the middle.

Let’s try A Union B… errrr

Should it be this?

5

Or this?

6

Or what about this?

7

Lols, I have no idea!

What would you prefer if you were doing some 3d printing, and had two blocks, one green, and one blue? How would you like to specify what that middle bit should be?

Let’s also consider this fact. If you choose the first two options, then we lose that commutativity thingy. Instead,

A union B is not the same as B union A

But if you consider the third option, then your printer better be able to print mixed colors, which most printers won’t. Consider for example the Makerbot Dual Extrustion Thingy. Currently it just uses two different filaments of plastic that it melts… it’s not like it can magically mix them together at a single nozzle and produce blue-green or mauve or puse or cornflower or whatever other color you want.

Crayonsman from Wikimedia Commons

Like these (Courtesy Crayonsman @ Wikimedia Commons)

In other words,

Green Printer head + Blue Printer head doesn’t mean you have a Blue-Green printer

Note that we now also have the same problem for intersection. There are at least three different ways to do it.  131211

And of course, possibly more. The first two ways, of course mean this:

A intersection B is not the same as B intersection A

Again, we are just breaking all kinds of rules here. We are breaking Geometry itself! Oh the horror! What would Venn say! and Boole?

Chances are that someone, somewhere, has already thought about these problems but I simply haven’t run across them. But what is the solution really?

What does this mean for adding Color to CGAL’s Nef Polyhedron?

It means we have to modify not just the data structure, to add some ‘color’ object, we have to modify intersection and union themselves. How do we do that?

We can’t just simply do A union B anymore.

We have to do something like this:

A color_union B

For our first option, where A ‘takes over’ the middle, color_union is going to look something like this:

New B = B minus (A intersection B)

Hey. That doesn’t seem too bad. It’s relatively simple to do, and relatively simple to explain to someone trying to use it. The one on the left ‘takes over’. I’m sure someone will want things different, then we could make something like color_union2 or … or some other more elegant naming scheme.

But is that the only problem? No. We have more problems.

Remember back to ‘old fashioned’ unions and intersections, when both shapes are the same color?

3

2

The result was always a simple polygon. There is a clear outline, and there is only one of them. There is a clear ‘inside’. There is a clear border between ’emptiness’ and ‘fullness’. We are back to the Tao Te Ching 11 – on the Usefulness of Emptyness . But what happens when we throw in color? How about our ‘A takes over’ color_union?

5

We no longer have one simple boundary between ’emptiness’ and ‘object’. We now have two different border lines. Here, let me emphasize them.

111

Some of each border is between ‘substance’ and ‘nothing’, but then part of it is between ‘substance a’ and ‘substance b’. They are butting up right against each other, even sharing some of the same vertexes. I know this examples are all 2d, but this stuff is all the same in 3d – just imagine two cubes instead of two rectangles. Same issues, same questions, same problems.

Butting against each other, and sharing vertexes are all things that people try to avoid when they are creating normal 3d shapes in 3d programs like OpenSCAD, because they usually result in weird bugs and crashes. OpenSCAD in particular gets rather confused when two objects share a vertex. How do you deal with that?

Now, besides that, 3d printer programs typically feed their output to something called a slicer. An example is http://slic3r.org/ and another is http://reprap.org/wiki/Skeinforge

How will Slicers be able to deal with this sort of weird dual boundary situation? I don’t know – I’ve never even used a slicer let alone a 3d printer. Surely the Makerbot Replicator software must have some ability to do something like this, because they have a bunch of models on their website that appear to have been 2-color printed somehow. But from what I understand, they have simply produced two different STL files and magically combined them, assigning a single color to each.

——————-

How could we do this in OpenSCAD?

AMF can do Volumes.

CGAL’s Nef Polyhedron is based on Volumes

In fact, I wrote a whole rambling blog on this topic just today, which you can view here:

https://sozvyezdami.wordpress.com/2012/11/01/hello-world/

We have, essentially the following unusual facts

For two single color shapes that overlap

A union B equals B union A

A union B produces a single resulting volume

However. For two different color shapes that overlap

A color_union B produces A union (B-A)

A color_union B produces two separate resulting volumes

Clearly, the issue will come down to implementing color_union. By these means, perhaps, then, we encapsulate AMF Volume colors inside of CGAL Volumes.

Now when it comes time to Export AMF…. we have to somehow export the CGAL Volumes separately.

———————-

What will this look like? And where are we now? Let’s test OpenSCAD with some examples.

color(“blue”) cube(5);

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

Ok. That’s our “a”. Now “b”

color(“green”) translate([2,2,2]) cube(5);

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

Great. Now, what does A union B look like in current OpenSCAD?

Снимок экрана от 2013-02-03 16:16:49

Great. But that is OpenCSG – it is not really a 3d render. It is a visual image based on clever algorithms (SCS and Goldfeather) that use OpenGL features like Stencil Buffers to ‘fake’ CSG operations.

What does a CGAL render look like?

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

Great.. OK. CGAL doesn’t have color. But it’s a union. But what is it really?

It is , in fact, no longer two separate cubes.

The first hint is by looking at the “Volumes:” line in the log window in the bottom right of the OpenSCAD screen. It says ‘two’. What are those two? As I describe in my ‘Hello World / Volumes’ post the two volumes are really the ‘Inner’ and ‘Outer’ volume of a single shape.

To verify this, just do a CGAL render of two separate cubes. You will see there are three volumes – one for each cube shape, and then a third ‘outer’ volume to represent the boundary between “space” itself and the objects (Again, back to the Tao Te Ching, http://www.yellowbridge.com/onlinelit/daodejing11.php “The Use of What Has No Substantive Existence: The Function of the Non-Existent / The Value of Non-Existence”)

Снимок экрана от 2013-02-03 16:23:31

Right. So back to our two unioned cubes, which have two volumes, which means they are actually one single shape. What do they really represent? Let’s switch to View/CGAL Grid Only mode in OpenSCAD.

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

As you can see from these two examples, there are no points representing the little ‘middle’ that we saw in our color_union examples. It is just one big gangly shape.

So what happens if we try to ‘simulate color_union’?

As above, A color_union B = A union (B – A), or in OpenSCAD language,

union() {

a();

difference(){ b(); a(); }

}

Снимок экрана от 2013-02-03 16:34:37

OpenCSG looks the same… OK. What about CGAL?

Снимок экрана от 2013-02-03 16:34:32

CGAL has produced exactly the same results as we had above when we did an ordinary union() of the two cubes. Same edges (lines), same vertexes, same surfaces, same number of volumes (2), same everything.

So here is what we expect to see different if color_union were to be implemented. This second example here, should, in fact, have two separate volumes (total of 3 volumes), and the CGAL Grid View should, in fact, show these two volumes in some fashion.

Theoretically.

And then those two distinct CGAL volumes could be exported in AMF as distinct AMF volumes.

And then, maybe, the Makerbot Replicator software could somehow figure that out, and glue/shoehorn that into their ‘two separate STL’ files software routines.

And then, then! Maybe. We might have some improved multi color ability in the Open Source 3d Printing world. And maybe, eventually, some day, even multi material.

Because, after all, what is multi color, currently, really, but two different materials? Two different filaments of plastic. Imagine mixing two types of plastic. Or, in Ceramic printers, two types of Ceramic. Or Plastic and Ceramic.

Or Chocolate and Peanut Butter.

———

So what are the steps to actually implement this in OpenSCAD?

1. Get AMF export working

Logxen ( https://github.com/logxen ) posted a patch for OpenSCAD to do AMF a bout a year ago. It was basically “STL-ish” AMF, with no volumes. But it was a start! Unfortunately it was not merged, perhaps  because I found it to be crashy. But it is a good base to build on.

2. Get ‘color’ added to CGAL Nef Polyhedron

Ai chihuahua, I don’t know if this can be done by using a feature of the C++ computer language (which CGAL is written in) called Inheritance, or if we would have to fork the source code of CGAL itself. Which would be annoying as a maintenance issue. However the good news is that CGAL’s “Mark” feature is already, sorta-kinda, like what ‘color’ would be – a sort of ‘attribute’ attached to volumes. So things could be worse.

3. get ‘color_union’ added to CGAL Nef Polyhedron

Again, can we use C++ inheritance or do we have to rip out the guts and fork the whole source code tree? The latter is not a pleasant prospect.

4. Figure out how you go from color CGAL Nef Polyhedron into CGAL Polyhedron

The thing about CGAL Nef Polyhedron is that you don’t use it “Raw” in OpenSCAD. Instead, OpenSCAD converts it into an ordinary CGAL Polyhedron. Then it gets exported to AMF/STL.

I think this is actually part of 1. In order to get AMF to output volumes at all (the simple case being two separate cubes that dont overlap), you will have to solve this problem. I think it might be nice to start trying to solve that simple problem (which you can solve without mucking around with color), and then move on to trying to add the colorization bits.

Imagine, AMF Export simply exports the CGAL Nef Polyhedra Volumes … and then it just grabs the color. Once you have the ‘exporting volumes’ thing working, and the color stuff working within Cgal Nef Polyhedra, its probably like 2 lines of code to get AMF volume color export.

Anyways.

Then maybe we can look forward to a Chocolate and Peanut Butter future.

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.

2 Responses to On adding colors to CGAL’s Nef Polyhedron

  1. G says:

    awesome explanations!
    What I don’t understand is why is appears as if all of this is implemented in the preview of openscad (color-difference seems to work for me).

    • donbright says:

      it doesnt generate 3-dimensional shapes. Preview is ‘fake rendering’ using OpenGL tricks from the OpenCSG project. if you combine two differently colored 3d cubes, you wind up with 3 new cuboids and you have to figure out what color the ‘middle’ object shoud be.

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