Update of Algebra System

The move to supporting FLUKA has resulted in the need to express the object geometry in a minimal number brackets and literals. It is currently not known if that will be supported completely, but mechanisms are being put in place that might allow a simplification or the production of a DNF form for each cell, to be carried out. Again returning to a CombLayer principle, a user will want to look at the geometry many times before running the problem, so whatever is in place should be quick to avoid disrupting the workflow.

Shannon Expansion

The Shannon expansion is a simple way to identify surfaces that are not needed in a boolean expression. Consider a logical rule e.g. F, that is an expression of variables e.g.

F(a,b,c,d) = ab+(c'd+b'a')

This expression can be resolved into two components, the on-set and the off-set [Note within Shannon's papers the "do-not-care set" (designated F(a:2)) is considered as well, but we will restrict ourselves to only the on and off sets.]

F = a F(a:1) + a' F(a:0)

were F(a:1) is the expression with a always true and F(a:0) is the expression with a always false. In our example:

F = a (b+c'd) + a'(c'd+b')

This is the same logical expression as the original F. However, the key useful component is that if and only if, F(a:1) is logically identical to F(a:0) then the literal a can be completely removed from F without lose of scope.

This alone is not very powerful, but in conjunction with surface implicates is very powerful indeed.

Surface Implicates

 In boolean geometry, certain surfaces are able to be mutually exclusive, e.g. two planes that are parallel or for many shapes if bound by a region (which is true for all objects within a CVG geometry system which CombLayer uses). Consider the case of two cylinders with common central axis , a  , and b, which differ only by their radii. Let b be the bigger cylinder. We see that 

b → a    [ outside of b also means outside of a]
a' → b'  [ inside of a also means inside of b ]

These implicates can be expressed in terms of an intersection with an object, F

b → a   is (b'+a)
a' → b' is (a+b')

So we have two identical intersections that can be appied to the object , F.

Use cases

• Removing redundant surfaces
• Splitting a large geometry into two sub-components about  a surface

This is carried out the simple Shannon expansion e.g. about surface a we get:

F= a F(a :1) + a'F(a:0)

assuming that we currently have the surface in the object. However, it is completely possible to inject any surface consider a rule , F that does not contain surface a, but surface a bisects the volume described by the rule F. If the volume is build with implicates then a much greater search space can be covered.

Removal of redundant surfaces via implicate search

The removal of extra surfaces from a complex cell is clearly extremely time consuming. A less optimal way but significantly faster, is paired Shannon implicate. First consider taking two Shannon expansions on variables a and b.

F=a'b' F(a:0,b:0)+a'b F(a:0,b:1)+ab' F(a:1,b:0) + ab F(a:1,b:1)

and consider an implicate that we express without lose of generality as a→b, and for all quadratic surfaces, b'→a'.

Now the third term [ab'F(a:1,b:0) ] is always false, and we can express F as,

F=a' F(a:0,b:0)+a'b F(a:0,b:1)+ b F(a:1,b:1)

If F(a:0,b:1) is null and either F(a:0,b:0) or F(a:1,b:1) are null, then we have determined that  variable a or b is unnecessary in the function. [if both are null, then both a and b are unnecessary].

This methods is implemented in Algebra::constructShannonExpansion() as a method to remove literals. It is not as comprehensive as the original version with all the implicates but does not have the problem that the problem is uncomputable for large cells.

Status

The current status is that significant machinery for the above actions has been written. There is a simple minimization method in class Simulation that can allow a cell to be minimized via Shannon-Expansion. There is currently no splitting method for a cell, although a simple one based on the above approach could be done if a cell contains a viable surface however, that is not the useful case.

Consider a cell F, and we wish to add a splitting surface a. Now we construct two cell  aF and a'F which would be correct. Now using all the implicates from a e.g. with planes/cylinders (that are parallel or not that far out) and the removal of surfaces in aF or a'F that are not needed would potentially result in two useful separated objects which have a lower literal size expansion cost as a pair than the single cell, i.e. we want   2^N>>  2^N_a + 2^N_a' were N_a is the number of literals in the aF set, and N_a' is the number of literals in the a'F set.