Boolean operations on objects, using scaling + copying

This is a quickie… I’m writing in a flash before sleep, so this is a bit confusing probably due to lack of time. But here we go.

In the world of the computer graphics, there is the idea of “Boolean operations” on two objects, for example a cylinder subtracted from a cube, gives you a hole in the cube.

This is also called “CSG ops” sometimes, which is short for Computational Solid Geometry or something like that.

It is very similar to the idea of Venn Diagram, if you are familiar with that. (Google it… )

So, what happens in 1 dimension? Imagine two line segments, A-B and C-D in 1 dimension.

 

         A----------B 
             C---D 

Say A=1, B=5, C=3, D=4
What is the intersection of the two line segments? 

             C---D
3 to 4


What is the union?

        A-----------B

1 to 5

What if you subtract CD from AB?

       A---C   D---B

Two line segments. 

1 to 3 and 4 to 5



Great! That seems pretty simple right? But what if we have this?

             A---B 
         C---D
Say C is 1, A is 2, D is also 2, B is 3

AB union CD is C-----B, or 1 to 3

AB intersection CD is.....    

not a line segment anymore? It's a point. At 2.

Well… is that a big deal? So you get  a point. Cool right?

 

Well… what if you didn’t want a point? What if you want the result of Boolean Operations on your objects to be the same kind of objects you started out with in the first place?

OK… here is a solution to that. Let’s say that points are really line segments with length 0. So we could say the above example can be rewritten like so

 


             A---B 
         C---D
Say C is 1, A is 2, D is also 2, B is 3

AB intersection CD is AD, a line segment from 2 to 2.

 


 

That is interesting.

It would make programming the algorithms a lot simpler. Now you don’t have to worry about two types of data structures… one for Points and one for Line Segments. Everything is a line segment. In some situations, that might be nice. Simplicity is a Feature, after all.

 

 


 

But what does this have to do with Objects? Nobody does CSG ops on one dimensional lines. Right? Well… funny you should ask.

First of all, every hard disk and every block of RAM in every computer in the world is basically a 1 dimensional object. Now, granted there are systems where things get complicated, especially with multiple drives etc. But basically, a “block device” in a modern computer is presented to the machine as a single massive list of numbers, for example 100 billion spots to store data, each spot holding 8 bits of information… could also be called a 100 gigibyte disk drive. Anyways. That’s not too relevant here, mostly because I have no idea how those things work. But dig into them and you will find 1 dimensional geometry algorithms I would wager.

But here is the trick with 2 dimensional and 3 dimensional geometry and higher. It’s a little idea whose name I don’t know, but surely someone else has described before.

Every algorithm that performs CSG ops in n dimensions, has to perform them in n-1 dimensions

Tricky eh? Why is that. Because imagine for example two triangles. What happens if they are right up against each other, and only intersect on one line?

 

 


        /|
       / |\        A intersection B = ???
      /__|_\

        /|
       / |  A
      /__|
       
        |\    B
        |_\
        |
        |    A intersection B

 

 


As you can see, the intersection of two triangles, back to back, where one is slightly smaller, means that the resulting “Intersection” is in fact simply a line segment.

And how does an algorithm arrive at such a solution, as we humans have when drawing pictures such as above?

Well, surely the algorithm must recognize at some point that the two triangles intersect only in a line segment, and then generate that line segment. In other words, it must perform a CSG operation with a one dimensional object. Even though it started out with 2 dimensional CSG input objects.

Think about this a while and I’m sure you can come up with more examples. What if two triangles intersect at only a single vertex? Why, then we have 0 dimensional geometry!  A point itself!

What if two tetrahedrons (4 sided objects in 3 dimensions) intersect face to face? Then we have a plane-plane intersection… we started in 3 dimensions but the algorithm must give us a result of a 2 dimensional situation!

And if two cubes, for example, touch only on a single straight edge? And one is slightly larger than the other? Then we are back to one dimensional CSG operations! And we started with two 3 dimensional objects!

That is why the idea / theorem above is recursive. If you have an algorithm to solve 3 dimensional CSG operations, it will solve 2 dimensional, and that algorithm, in turn, will have to solve CSG ops of one-dimension. Which, in turn, will solve 0 dimensional ops.

 


A side note… what are zero dimensional ops? Well, there are many ways to think of it, but imagine this. Consider if a point can be called “on” or “off”. This is all of space in the 0 dimensional world. A single point at origin. But as with any space, it can either have matter, or emptiness within it. So, “on” = matter, “off” = emptiness. (Again with the Tao Te Ching and Emptiness as a Valuable Thing idea).

Now, consider two 0 dimensional points. One is “off” and the other is “on”. Can you do a CSG operation on them? Sure! It’s just boolean algebra. On intersection Off is the same thing as “1 and 0” or “True and False”, which, if you work it out in Boolean logic rules, results in “False”.

How about “on” union with “off”? Again, thanks to George Boole, we can describe this as “1 or 0”, “True or False”, which results in the single value of “True”.

So 0 dimensional geometry, ain’t necessarily that boring. If you think of it in a certain way. (And i’d imagine there are many other fun and imaginative ways to think of it… what if the point has “color” for example?)


 

 

 

That’s all for now.

The rest shall come later if possible.

The essential idea is that when you go up into higher dimensions, the idea of “Clipping” or “subtracting one object from another” becomes more complicated. It is not so clear how to maintain the type of object you are dealing with, when creating your output. You begin calculating intersection points, and then “cutting” to them…

Unless.

Unless instead of chopping and cutting at intersection points… instead you Scale your existing objects to fit.

But that’s gonna be part two, updated in the future hopefully. I just have to write this down now in case it gets lost in a dream or something.

 

 

 

Advertisements

About donbright

don bright http://github.com/donbright
This entry was posted in Uncategorized. Bookmark the permalink.

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