brief note to future self – on boolean geometry and colors

This is a quick and dirty idea for 3 dimensional boolean geometry using multiple colors by redefining union and intersection to include color.

1. A boolean geometry system is one in which an object is described as a sequence of Boolean operations performed on objects in some space. For example a cube’s intersection with a sphere (a hemisphere), or the union of three spheres (a snowman).

2. You can break down any such system from 1 into binary boolean operations

3. Every such system can be described as a tree of operations

4. Every algorithm that performs a boolean operation in N-dimensional space will include an algorithm that performs a boolean operation in N minus one dimensional space. Down to dimension 0.

5. For example every system that calculates intersections of cubes in 3d space, will have to consider the case of degenerate cubes, which are squares in a plane. If the two squares are on the same plane, the result is a 2 dimensional boolean geometry. If two squares are degenerate, they are lines, and if they are collinear in the plane, then they exist in a 1 dimensional space, so the boolean intersection in one dimensional space will have to be calculated. So on down to 0th dimensional space, where it is necessary to find whether two degenerate lines, or points, intersect.

6. Boolean operations on 0 dimensional geometrical objects can be thought of as equivalent to boolean operations on binary true-false values.

7. A 0 dimensional boolean geometry is equivalent to a extremely simple binary tree of Boolean operations on Boolean values

8. It is possible to consider that such a 0 dimensional geometric object therefore consists of one of two values, true or false, and this can be interpreted geometrically as ‘existence’ or ‘non existence’, both of which are equally important, and, in fact, mirrors of each other. Some disciplines, such as the art of casting molds of objects, have similar concepts like negative and positive space

9. The boolean geometric ideas of union and intersection become equivalent to Boolean logic operations of OR and AND.

9. It is also possible to consider that such a 0 dimensional geometric object, instead of holding two values, true or false, instead holds a color. For example red or blue.

10. If 9 is considered, then it is necessary to define boolean operations on colors. Red union Blue, or Red intersection Blue.

11. if 10 is considered then it is possible to think of colors as numbers. For example, 24 bit numbers in an ordinary computer display system, where the first 8 bits are the level of Red light, the second 8 bits are the level of Green light, and the last are the level of Blue light, an RGB system. Each color has 256 different brightnesses in which it can appear in such a system.

12. This item is long.

If 9 10 and 11 are considered, then the boolean geometry operations on colors can be performed by using boolean operations of a bitwise nature, as found in computer programming languages, such as BITWISE AND and BITWISE OR.

For example if Red is binary

11111111 00000000 00000000

and Blue is binary

00000000 00000000 11111111

Then Red Or Blue becomes the binary OR operation applied to each bit individually using Boolean algebra rules. The result is like this:

11111111 00000000 11111111

This color appears as Purple

Another way to say this is that Red Union Blue is Purple

What of Red Intersection Blue?

Red – 11111111 00000000 00000000

Blue – 00000000 00000000 11111111

Red BITWISE AND Blue = 00000000 00000000 00000000

All zeros? That looks like black on a typical RGB based computer screen.

So Red Intersection Blue is Black.

We now have a boolean geometry system of 0 dimensions for Colors.

13.

If we apply the logic of 12, above to a higher dimensional boolean geometry system, we will have a multi-color boolean geometry system of N dimensions.

For example if we have a red square and a blue square, imagine them in two dimensional space.

redsepblue

Now imagine we move one so it overlaps the other. Then we do a Boolean union on them, the resulting boolean geometrical object will be Purple.

redunionblue

If we have a red square and a blue square and we do Boolean Intersection on them, the resulting square will be Black.

redinterblue

This is because we consider the Color as a sort of 0 dimensional geometric boolean object that is attached to the two dimensional objects.

In this way, we have a sort of boolean operation operating on multiple dimensions simultaneously – the 0 dimensional geometry of object colors, and the 2-dimensional geometry of our square shapes.


15.The Point

The point of all this is that we now can create a multi-color boolean geometry engine that preserves traditional boolean algebra, specifically these two properties:

Please note

A = some geometric object, B = another object, C = a third

∪ = Union and ∩ = Intersection

  1.  Commutativity —-
    1. A ∪ B = B ∪ A
    2. A ∩ B = B ∩ A
  2. Associativity —
    1. A ∪ ( B ∪ C ) = ( A ∪ B ) ∪ C
    2. A ∩ ( B ∩ C ) = ( A ∩ B ) ∩ C

Now there is a problem… if the entire tree is evaluated down to the last node, then we still end up with a single color object.

This is why for such a system to represent multi-colored 3 dimensional objects,  further consideration must be made.

A simple idea would be to assume the user must keep objects non-touching on the last level of the geometry tree, and then leave out the last ‘implicit union’ of top level objects. Thus if you had 100 complicated objects each a different single color, they could each be their own color as long as they did not touch. It would be like having 100 separate geometry trees.

That’s not enough though. There are other options.

In the case of 2 dimensional objects, it is possible to redefine the boolean operation of Union so that it can create 3 resulting objects in Union – two keep the color, while the third representing the intersection of two objects, takes the union of the colors.

redunionblueispurp

This increases complexity of the tree, and essentially eliminates the idea that at each stage of the tree, you are reducing the number of elements. In fact this form of union increases the number of elements, also known as nodes, in the tree.


Reducability

Essentially these nodes could be thought of as irreducible. If one is to compare it to evaluating an arithmetic expression, which is another use for binary trees, then consider this analogy.

1 + 2 x 3 forms a tree,  the ‘+’ operation at the top, with two branches, one to the number 1, a ‘terminal’ leaf, and the other to the operation ‘x’, with 2 and 3 as terminal leaves of ‘x’.

Every arithmetic expression with numbers and addition, subtraction, multiplication, and division can be reduced to a single number.

However in some systems if you introduce radicals such as square roots, it becomes irreducible without loss of precision, and so it is kept. These are the ‘algebraic systems’ or ‘symbolic systems’ like sympy or Wolfram Alpha. For example say sqrt is square root. Think of this expression:

sqrt(1) + 2 * sqrt(3)

This cannot be reduced, without losing information.

1 + 2 sqrt(3)

Anything lower becomes an approximation. Sometimes you don’t want approximation.

In a similar way consider this expression of three geometrical objects in the picture above:

Red square ∪ Blue square ∪ Purple square

If we consider these squares as above, none overlap each other, then none can be reduced. Without losing information.

We have an irreducible expression.

It can still be expressed as a binary tree, but it is just not going to have 0 leaves anymore.

In this manner, color boolean geometry may be more like symbolic algebra systems than it is like arithmetic expression evaluation systems. Perhaps similar techniques can be used to simplify trees?


So Color Union, in this interpretation, is a fundamentally different form of union. However it is still associative and commutative.

And it still manages to generate a single binary tree.

In theory.


15.5 why Commutativity and Associativity and Binaryness matter

Basically it comes down to simplicity. Simplicity is one of the most important features of any geometry system.

If you have to worry about whether your object is on the left or right hand side of something, then the boolean operations become a tangle of spaghetti.

If you are using libraries of boolean geometry code, this is even more a problem.

If you have to worry about parsing and evaluating non binary trees, it becomes more complicated.

The more simple a machine is, the easier it is to fix and repair.

That is why these things are important. Boolean geometry machines can become incredibly complicated very quickly, to the point that design tweaks can make the difference between computability on a machine, and exhausting it’s resources of memory and processing.

The simpler the machine, the easier it is to diagnose and fix such things. In the objects themselves but also in the engine.

 


16. Theory of Color

Also different definitions of color mathematics could be used, so that instead of additive color theory, subtractive color theory is used. For example in the RGB system Yellow is made of Red and Green, so Yellow Union Blue is White. But in subtractive theory, like that of Paints, yellow and blue make Green. Different representation and/or algebra of color could be used to create this effect.

 

17. End

Thus there is a theoretical possibility to modify a 3d boolean geometry system, such as that found in OpenSCAD ( http://www.openscad.org ) and it’s engine CGAL ( http://www.cgal.org ) so that multi-color 3d printing can work properly in the world of open source 3d geometry algorithms.

From the generation of a multi-color Boolean Union tree, it could be possible to generate multicolor file formats such as AMF ( http://amf.wikispaces.com/ ) which has the notion of ‘Volumes’.

Advertisements
Posted in Uncategorized | Leave a comment