CSG Complement

TODO: Look into and handle when intersecting two complemented solids

• hmm what happens with an intersect of two complemented solids ?? UNDEFINED BEHAVIOR ??

FIXED ISSUE : complemented solids via normal flip yields unexpected intersections (mirror object)

• fixed by special casing complement solid MISS, changing the MISS to an EXIT ... as it is impossible to MISS the unbounded complementd solid
• see tboolean-complement for testing this

csg_intersect_part.h:

164     if(complement)  // flip normal, even for miss need to signal the complement with a -0.f
165     {
166         // For valid_intersects this flips the normal
167         // otherwise for misses all tt.xyz values should be zero
168         // but nevertheless proceed to set signbits to signal a complement miss
169         // to the caller... csg_intersect_boolean
170
171         tt.x = -tt.x ;
172         tt.y = -tt.y ;
173         tt.z = -tt.z ;
174     }
175
176 }

csg_intersect_boolean.h:

709                 IntersectionState_t l_state = CSG_CLASSIFY( csg.data[left], ray.direction, tmin );
710                 IntersectionState_t r_state = CSG_CLASSIFY( csg.data[right], ray.direction, tmin );
711
712
713                 float t_left  = fabsf( csg.data[left].w );
714                 float t_right = fabsf( csg.data[right].w );
715
716                 bool leftIsCloser = t_left <= t_right ;
717
718 #define WITH_COMPLEMENT 1
719 #ifdef WITH_COMPLEMENT
720                 // complements (signalled by -0.f) cannot Miss, only Exit, see opticks/notes/issues/csg_complement.rst
721
722                 // these are only valid (and only needed) for misses
723                 bool l_complement = signbit(csg.data[left].x) ;
724                 bool r_complement = signbit(csg.data[right].x) ;
725
726                 bool l_complement_miss = l_state == State_Miss && l_complement ;
727                 bool r_complement_miss = r_state == State_Miss && r_complement ;
728
729                 if(r_complement_miss)
730                 {
731                     r_state = State_Exit ;
732                     leftIsCloser = true ;
733                 }
734
735                 if(l_complement_miss)
736                 {
737                     l_state = State_Exit ;
738                     leftIsCloser = false ;
739                 }
740
741 #endif
742                 int ctrl = boolean_ctrl_packed_lookup( typecode , l_state, r_state, leftIsCloser ) ;
743                 history_append( hist, nodeIdx, ctrl );

Background

• Translating DYB Near site geometry yields 22/249 excessively deep(greater that height 3) CSG trees
• tree modification mostly requires positive form (ie with no subtractions, only intersect and union operators which are easier to handle as they are commutative)
• making positive trees requires applying De Morgan’s laws which require complements

CSG Single Hit Ray Trace Sub-object combination tables

• http://xrt.wikidot.com/doc:csg

UNION	Enter B	Exit B	Miss B
Enter A	ReturnAIfCloser, ReturnBIfCloser	ReturnBIfCloser, AdvanceAAndLoop	ReturnA
Exit A	ReturnAIfCloser, AdvanceBAndLoop	ReturnAIfFarther, ReturnBIfFarther	ReturnA
Miss A	ReturnB	ReturnB	ReturnMiss

DIFFERENCE	Enter B	Exit B	Miss B
Enter A	ReturnAIfCloser, AdvanceBAndLoop	AdvanceAAndLoopIfCloser, AdvanceBAndLoopIfCloser	ReturnA
Exit A	ReturnAIfCloser, ReturnBIfCloser, FlipB	ReturnBIfCloser, FlipB AdvanceAAndLoop	ReturnA
Miss A	ReturnMiss	ReturnMiss	ReturnMiss

INTERSECTION	Enter B	Exit B	Miss B
Enter A	AdvanceAAndLoopIfCloser, AdvanceBAndLoopIfCloser	ReturnAIfCloser, AdvanceBAndLoop	ReturnMiss
Exit A	ReturnBIfCloser, AdvanceAAndLoop	ReturnAIfCloser, ReturnBIfCloser	ReturnMiss
Miss A	ReturnMiss	ReturnMiss	ReturnMiss

Difference is Equivalent to intersect with complement

Logical identity:

A - B  = A INTERSECT !B

DIFFERENCE(A,B)  = INTERSECT(A,!B)

can single hit CSG implementation handle complements ?

• it must be possible, as it can handle difference
• BUT: previous attempts to use unbounded CSG sub-objects (like infinite half-spaces defined by planes) failed ... the single-hit-CSG algorithm relies on intersecting with the “other” side of sub-objects
• so long as intersects at infinity are shrouded by “ReturnTheOtherIfCloser” might manage to get away with unbounded ?
• Enter/Exit classification comes from comparison of normal and ray directions

From within !B:

• intersects at infinity will be Exit(!B)
• close intersects (with the bubble) will also be Exit(!B)
• ... seems no possibility to miss !B ?
• PERHAPS FOR COMPLEMENT-B NEED TO RECLASSIFY, MISS-B -> EXIT-B ? MISS-B means it didnt intersect with the local bubble but when its a complement, the unbounded nature of !B converts that into EXIT-B ?
• for DIFFERENCE(A,B) MISS-B -> ReturnA, need to get the INTERSECT(A,-B) table to ReturnA, intersects at infinity are always going to be further...
• INTERSECT(A,B) ExitB column bother EnterA,ExitA shrouded by ReturnAIfCloser which will always be true.... HENCE SEEMS THAT IT WILL WORK ...
  • FOR COMPLEMENTS RE-CLASSIFY MISS TO EXIT

INTERSECT(A, !B)

Transposes “EnterB” with “ExitB”, getting close to DIFFERENCE(A,B) table

Mismatches being:

• presence of “FlipB” together with both “ReturnBIfCloser” in DIFFERENCE (but B is already flipped, so not a difference ?)
• presence of “ReturnA” in the “MissB” column of DIFFERENCE vs “ReturnMiss” in INTERSECTION(A,!B)

What does (MISS !B) mean ...

Think of an inside out sphere (air bubble in water), in some sense there is no way to miss !B,

• from inside the bubble (outside !B)... close intersect is inevitable
• from outside the bubble (inside !B)
  • either close intersect with the !B bubble surface
  • OR intersect at infinity with surface of !B

oxrap/cu/csg_intersect_boolean.h:

267 #define CSG_CLASSIFY( ise, dir, tmin )   (fabsf((ise).w) > (tmin) ?  ( (ise).x*(dir).x + (ise).y*(dir).y + (ise).z*(dir).z < 0.f ? State_Enter : State_Exit ) : State_Miss )
...
705                 int left  = firstLeft ? csg.curr   : csg.curr-1 ;
706                 int right = firstLeft ? csg.curr-1 : csg.curr   ;
707
708                 IntersectionState_t l_state = CSG_CLASSIFY( csg.data[left], ray.direction, tmin );
709                 IntersectionState_t r_state = CSG_CLASSIFY( csg.data[right], ray.direction, tmin );
710
711                 float t_left  = fabsf( csg.data[left].w );
712                 float t_right = fabsf( csg.data[right].w );
713
714                 int ctrl = boolean_ctrl_packed_lookup( typecode , l_state, r_state, t_left <= t_right ) ;
715                 history_append( hist, nodeIdx, ctrl );
716