CSG

[Negrini085]

The objective of this pull request is to implement csg, which allows complex geometric figures to be created from boolean operations of union, difference and intersection. The history of this pull request is very dense with commits because it was opened at a fairly early stage of PhotoNim's development and therefore has commits linked to different versions and code logics. The situation now in master with regard to csg is as follows:

• csgUnion
• csgDiff
• csgInt

Actually, during the development of PhotoNim (and in particular within this pull request) there was a time when all three types of csg were present: those are images produced using PhotoNim and actually committed.

The change tree traversal modality using getClosestHit made the old implementation incompatible with the state of the art of PhotoNim. As a result, we aim in the future to make the ability to create csgInt and csgDiff usable again for the user. Let's first look at the old implementation:

    Shape* = ref object
        material*: Material

        case kind*: ShapeKind 
        of skAABox: 
            aabb*: Interval[Point3D]

        of skTriangle: 
            vertices*: array[3, Point3D]            

        of skSphere:
            radius*: float32
        
        of skEllipsoid:
            axis*: tuple[a: float32, b: float32, c: float32]

        of skCylinder:
            R*, phiMax*: float32
            zSpan*: Interval[float32]

        of skPlane: discard

        of skTriangularMesh:
            nodes*: seq[Point3D]
            edges*: seq[int]
            tree*: SceneNode

        of skCSGUnion, skCSGInt, skCSGDiff:
            shapes*: tuple[primary, secondary: Shape]
            shTrans*: tuple[tPrimary, tSecondary: Transformation]

CSGs where a shape kind, which is not a case in version 1.0.0 PhotoNim. In order to create a csg object, it was necessary to work with recursive calls, as a csg shape actually consisted of two shapes and two transformations (the local shapes) of which the first had all privileges. In order to get hits, we used getHitPayload and getAllHitPayload such as following, where we report only the code regarding CSGs.

proc getAllHitPayload*(handler: ShapeHandler, worldInvRay: Ray): Option[seq[HitPayload]] =
    ........................................
    ........................................           
    of skCSGUnion: 
        var 
            hitS: seq[Option[seq[HitPayload]]]
            appo: seq[HitPayload]

        hitS.add getAllHitPayload(
            ShapeHandler(shape: handler.shape.shapes.primary, transformation: handler.shape.shTrans.tPrimary),
            worldInvRay.transform(handler.shape.shTrans.tPrimary.inverse)
            )
        
        hitS.add getAllHitPayload(
            ShapeHandler(shape: handler.shape.shapes.secondary, transformation: handler.shape.shTrans.tSecondary),
            worldInvRay.transform(handler.shape.shTrans.tSecondary.inverse)
            )
        
        appo = hitS.filterIt(it.isSome).mapIt(it.get).concat
        if appo.len == 0: return none seq[HitPayload]
        return some appo

    of skCSGInt:
            
        var 
            hitS: seq[Option[seq[HitPayload]]]
            hit1: seq[HitPayload]
            hit2: seq[HitPayload]
            appo: seq[HitPayload]

        let
            sh1 = ShapeHandler(shape: handler.shape.shapes.primary, transformation: handler.shape.shTrans.tPrimary)
            sh2 = ShapeHandler(shape: handler.shape.shapes.secondary, transformation: handler.shape.shTrans.tSecondary)

        hitS.add getAllHitPayload(sh1, worldInvRay.transform(sh1.transformation.inverse))

        hit1 = hitS.filterIt(it.isSome).mapIt(it.get).concat
        hit1 = hit1.filterIt(sh2.shape.inShape(worldInvRay.transform(sh2.transformation.inverse).at(it.t)))
        
        hitS = @[]
        hitS.add getAllHitPayload(sh2, worldInvRay.transform(sh2.transformation.inverse))
        
        hit2 = hitS.filterIt(it.isSome).mapIt(it.get).concat
        hit2 = hit2.filterIt(sh1.shape.inShape(worldInvRay.transform(sh1.transformation.inverse).at(it.t)))        
        
        appo = hit1 & hit2
        if appo.len == 0: return none seq[HitPayload]

        appo = appo.sorted(proc(a, b: HitPayload): int = cmp(a.t, b.t))
        return some appo

    of skCSGDiff:
        var 
            hitS: seq[Option[seq[HitPayload]]]
            hit1: seq[HitPayload]
            hit2: seq[HitPayload]
            appo: seq[HitPayload]

        let
            sh1 = ShapeHandler(shape: handler.shape.shapes.primary, transformation: handler.shape.shTrans.tPrimary)
            sh2 = ShapeHandler(shape: handler.shape.shapes.secondary, transformation: handler.shape.shTrans.tSecondary)

        hitS.add getAllHitPayload(sh1, worldInvRay.transform(sh1.transformation.inverse))

        hit1 = hitS.filterIt(it.isSome).mapIt(it.get).concat
        hit1 = hit1.filterIt(not sh2.shape.inShape(worldInvRay.transform(sh2.transformation.inverse).at(it.t)))
        
        hitS = @[]
        hitS.add getAllHitPayload(sh2, worldInvRay.transform(sh2.transformation.inverse))
        
        hit2 = hitS.filterIt(it.isSome).mapIt(it.get).concat
        hit2 = hit2.filterIt(sh1.shape.inShape(worldInvRay.transform(sh1.transformation.inverse).at(it.t)))        
        
        appo = hit1 & hit2
        if appo.len == 0: return none seq[HitPayload]

        appo = appo.sorted(proc(a, b: HitPayload): int = cmp(a.t, b.t))
        return some appo


proc getHitPayload*(handler: ShapeHandler, worldInvRay: Ray): Option[HitPayload] =
    ...........
    ..........
    
    of skCSGUnion: 
        var 
            hitS: seq[Option[HitPayload]]
            appo: seq[HitPayload]

        hitS.add getHitPayload(
            ShapeHandler(shape: handler.shape.shapes.primary, transformation: handler.shape.shTrans.tPrimary),
            worldInvRay.transform(handler.shape.shTrans.tPrimary.inverse)
            )
        
        hitS.add getHitPayload(
            ShapeHandler(shape: handler.shape.shapes.secondary, transformation: handler.shape.shTrans.tSecondary),
            worldInvRay.transform(handler.shape.shTrans.tSecondary.inverse)
            )
        
        appo = hitS.filterIt(it.isSome).mapIt(it.get)
        if appo.len == 0: return none HitPayload

        appo = appo.sorted(proc(a, b: HitPayload): int = cmp(a.t, b.t))
        return some HitPayload(
            handler: ShapeHandler(shape: appo[0].handler.shape, transformation: handler.transformation @ appo[0].handler.transformation),
            ray: worldInvRay.transform(appo[0].handler.transformation.inverse), t: appo[0].t
        )
    
    of skCSGInt:         
        
        var 
            hitS: seq[Option[seq[HitPayload]]]
            hit1: seq[HitPayload]
            hit2: seq[HitPayload]
            appo: seq[HitPayload]

        let
            sh1 = ShapeHandler(shape: handler.shape.shapes.primary, transformation: handler.shape.shTrans.tPrimary)
            sh2 = ShapeHandler(shape: handler.shape.shapes.secondary, transformation: handler.shape.shTrans.tSecondary)

        hitS.add getAllHitPayload(sh1, worldInvRay.transform(sh1.transformation.inverse))

        hit1 = hitS.filterIt(it.isSome).mapIt(it.get).concat
        hit1 = hit1.filterIt(sh2.shape.inShape(worldInvRay.transform(sh2.transformation.inverse).at(it.t)))
        
        hitS = @[]
        hitS.add getAllHitPayload(sh2, worldInvRay.transform(sh2.transformation.inverse))
        
        hit2 = hitS.filterIt(it.isSome).mapIt(it.get).concat
        hit2 = hit2.filterIt(sh1.shape.inShape(worldInvRay.transform(sh1.transformation.inverse).at(it.t)))        
        
        appo = hit1 & hit2
        if appo.len == 0: return none HitPayload

        appo = appo.sorted(proc(a, b: HitPayload): int = cmp(a.t, b.t))
        return some HitPayload(
            handler: ShapeHandler(shape: appo[0].handler.shape, transformation: handler.transformation @ appo[0].handler.transformation),
            ray: worldInvRay.transform(appo[0].handler.transformation.inverse), t: appo[0].t
        )  

    of skCSGDiff:
        var 
            hitS: seq[Option[seq[HitPayload]]]
            hit1: seq[HitPayload]
            hit2: seq[HitPayload]
            appo: seq[HitPayload]

        let
            sh1 = ShapeHandler(shape: handler.shape.shapes.primary, transformation: handler.shape.shTrans.tPrimary)
            sh2 = ShapeHandler(shape: handler.shape.shapes.secondary, transformation: handler.shape.shTrans.tSecondary)

        hitS.add getAllHitPayload(sh1, worldInvRay.transform(sh1.transformation.inverse))

        hit1 = hitS.filterIt(it.isSome).mapIt(it.get).concat
        hit1 = hit1.filterIt(not sh2.shape.inShape(worldInvRay.transform(sh2.transformation.inverse).at(it.t)))
        
        hitS = @[]
        hitS.add getAllHitPayload(sh2, worldInvRay.transform(sh2.transformation.inverse))
        
        hit2 = hitS.filterIt(it.isSome).mapIt(it.get).concat
        hit2 = hit2.filterIt(sh1.shape.inShape(worldInvRay.transform(sh1.transformation.inverse).at(it.t)))        
        
        appo = hit1 & hit2
        if appo.len == 0: return none HitPayload

        appo = appo.sorted(proc(a, b: HitPayload): int = cmp(a.t, b.t))
        return some HitPayload(
            handler: ShapeHandler(shape: appo[0].handler.shape, transformation: handler.transformation @ appo[0].handler.transformation),
            ray: worldInvRay.transform(appo[0].handler.transformation.inverse), t: appo[0].t
        )  

To bring these functions into the code we imagine that it is necessary to define a function that returns all the hit times, one that allows you to evaluate whether a point is inside a shape or not and work to evaluate all the intersections, in order to be able to choose the correct ones for the desired rendering.