Pasted

class CSG(object):
    def __init__(self):
        self.polygons = []
    
    def fromPolygons(polygons):
        csg = CSG()
        csg.polygons = polygons
        return csg
        
    def clone(self):
        csg = CSG()
        csg.polygons = copy.deepcopy(self.polygons)
        return csg
    
    def toPolygons(self):
        return self.polygons
        
    
    def union(self, csg):
        a = CSG_Node(self.clone().polygons)
        b = CSG_Node(csg.clone().polygons)
        a.clipTo(b)
        b.clipTo(a)
        b.invert()
        b.clipTo(a)
        b.invert()
        a.build(b.allPolygons())
        return CSG.fromPolygons(a.allPolygons())
        
    def subtract(self, csg):
        a = CSG_Node(self.clone().polygons)
        b = CSG_Node(csg.clone().polygons)
        a.invert()
        a.clipTo(b)
        b.clipTo(a)
        b.invert()
        b.clipTo(a)
        b.invert()
        a.build(b.allPolygons())
        a.invert()
        return CSG.fromPolygons(a.allPolygons())
        
    def intersect(self, csg):
        a = CSG_Node(self.clone().polygons)
        b = CSG_Node(csg.clone().polygons)
        a.invert()
        b.clipTo(a)
        b.invert()
        a.clipTo(b)
        b.clipTo(a)
        a.build(b.allPolygons())
        a.invert()
        CSG.fromPolygons(a.allPolygons())
        
    def inverse(self):
        csg = self.clone()
        for poly in csg.polygons:
            poly.flip()
        return csg
        
    def CSG_Cube(self, origin, size):
        s = [1.0, 1.0, 1.0]
        if len(size) == 3:
            s[0] = size[0]
            s[1] = size[1]
            s[2] = size[2]
        elif 'x' in size:
            s[0] = size.x
            s[1] = size.y
            s[2] = size.z
        c = CSG_Vector(origin)
        xNorm = 1 if s[0] >= 0 else -1
        yNorm = 1 if s[1] >= 0 else -1
        zNorm = 1 if s[2] >= 0 else -1
        a = CSG.fromPolygons([
            [[0, 4, 6, 2], [-xNorm, 0, 0]],
            [[1, 3, 7, 5], [xNorm, 0, 0]],
            [[0, 1, 5, 4], [0, -yNorm, 0]],
            [[2, 6, 7, 3], [0, yNorm, 0]],
            [[0, 2, 3, 1], [0, 0, -zNorm]],
            [[4, 5, 7, 6], [0, 0, zNorm]]])
        b = []
        for poly in a.toPolygons():
            d = []
            for i in poly[0]:
                pos = CSG_Vector(
                    c.x + (s[0] if i & 1 != 0 else 0),
                    c.y + (s[1] if i & 2 != 0 else 0),
                    c.z + (s[2] if i & 4 != 0 else 0)
                )
                d.append(CSG_Vertex(pos, CSG_Vector(poly[1])))
            b.append(CSG_Polygon(d, None))
        self.polygons = b
               
class CSG_Vector(object):
    def __init__(self, *arg):
        if len(arg) == 3:
            self.x = arg[0]
            self.y = arg[1]
            self.z = arg[2]
        elif hasattr(arg[0], 'x'):
            self.x = arg[0].x
            self.y = arg[0].y
            self.z = arg[0].z
        else:
            self.x = arg[0][0]
            self.y = arg[0][1]
            self.z = arg[0][2]
        
    def clone(self):
        return CSG_Vector(self.x, self.y, self.z)
    
    def negated(self):
        return CSG_Vector(-sefl.x, -self.y, -self.z)
    
    def plus(self, a):
        return CSG_Vector(self.x + a.x, self.y + a.y, self.z + a.z)
    
    def minus(self, a):
        return CSG_Vector(self.x - a.x, self.y - a.y, self.z - a.z)
    
    def times(self, a):
        return CSG_Vector(self.x * a, self.y * a, self.z * a)
    
    def dividedBy(self, a):
        return CSG_Vector(self.x / a, self.y / a, self.z / a)
    
    def dot(self, a):
        return ((self.x * a.x) + (self.y * a.y) + (self.z * a.z))
    
    def lerp(self, a, t):
        return self.plus(a.minus(self).times(t))
        
    def length(self):
        return math.sqrt(self.dot(self))
        
    def unit(self):
        return self.dividedBy(self.length())
        
    def cross(self, a):
        return CSG_Vector((self.y * a.z) - (self.z * a.y), (self.z * a.x) - (self.x * a.z), (self.x * a.y) - (self.y * a.x))
    
class CSG_Vertex(object):
    def __init__(self, pos, normal):
        self.pos = CSG_Vector(pos)
        self.normal = CSG_Vector(normal)
    
    def clone(self):
        return CSG_Vertex(copy.deepcopy(self.pos), copy.deepcopy(self.normal))
        
    def flip(self):
        self.normal = self.normal.negated()
        
    def interpolate(self, other, t):
        return CSG_Vertex(self.pos.lerp(other.pos, t), self.normal.lerp(other.normal, t))
        
class CSG_Plane(object):
    def __init__(self, normal, w):
        self.normal = normal
        self.w = w
        
    EPSILON = 1e-5
       
    def fromPoints(a, b, c):
        n = b.minus(a).cross(c.minus(a)).unit()
        return CSG_Plane(n, n.dot(a))
        
    def clone(self):
        return CSG_Plane(copy.deepcopy(self.normal), copy.copy(self.w))
        
    def flip(self):
        self.normal = self.normal.negated()
        self.w = -self.w
        
    def splitPolygon(self, polygon, coplanarFront, coplanarBack, front, back):
        COPLANAR = 0
        FRONT = 1
        BACK = 2
        SPANNING = 3
        
        polygonType = 0
        types = []
        for index in range(len(polygon.vertices)):
            t = self.normal.dot(polygon.vertices[index].pos) - self.w
            type = (BACK if t < -GSC_Plane.EPSILON else (FRONT if t > CSG_Plane.EPSILON else COPLANAR))
            polygonType |= type
            types.append(type)
        
        if polygonType == COPLANAR:
            if self.normal.dot(polygon.plane.normal) > 0:
                coplanarFront.append(polygon)   #These should modify the list outside of this scope as well
            else:
                coplanarBack.append(polygon)
        elif polygonType == FRONT:
            front.append(polygon)   
        elif polygonType == BACK:
            back.append(polygon)
        elif polygonType == SPANNING:
            f = []
            b = []
            for index in range(len(polygon.vertices)):
                j = (i + 1) % len(polygon.vertices)
                ti = types[i]
                tj = types[j]
                vi = polygon.vertices[i]
                vj = polygon.vertices[j]
                if ti != BACK:  
                    f.append(vi)
                if ti != FRONT:
                    b.append(vi.clone() if ti != BACK else vi)
                if (ti | tj) == SPANNING:
                    t = (self.w + self.normal.dot(vi.pos)) / self.normal.dot(vj.pos.minus(vi.pos))
                    v = vi.interpolated(vj, t)
                    f.append(v)
                    b.append(v.clone())
            if len(f) >= 3:
                front.append(CSG_Polygon(f, polygon.shared))
            if len(b) >= 3:
                back.append(CSG_Polygon(b, polygon.shared))
                
class CSG_Polygon(object):
    def __init__(self, vertices, shared):
        self.vertices = vertices
        self.shared = shared
        self.plane = CSG_Plane.fromPoints(vertices[0].pos, vertices[1].pos, vertices[2].pos)
    
    def clone(self):
        vertices = copy.deepcopy(self.vertices)
        return CSG_Polygon(vertices, self.shared)
    
    def flip(self):
        self.vertices.reverse()
        for vert in self.vertices:
            vert.flip()
        self.plane.flip()
        
class CSG_Node(object):
    def __init__(self, *args):
        self.plane = None
        self.front = None
        self.back = None
        self.polygons = []
        if len(args) == 1:
            self.build(args[0])
    
    def clone(self):
        node = CSG_Node()
        node.plane = None if self.plane is None else self.plane.clone()
        node.front = None if self.front is None else self.front.clone()
        node.back = None if self.back is None else self.back.clone()
        node.polygons = copy.deepcopy(self.polygons)
        return node
        
    def invert(self):
        for index in range(len(self.polygons)):
            self.polygons[index].flip()
        self.plane.flip()
        if self.front is not None:
            self.front.invert()
        if self.back is not None:
            self.back.invert()
        temp = self.front
        self.front = self.back
        self.back = temp
        
    def clipPolygon(self, polygons):
        if self.plane is None:
            return polygons[:]
        front = []
        back = []
        for index in range(len(polygons)):
            self.plane.splitPolygon(polygons[index], front, back, front, back)
        if self.front is not None:
            front = self.front.clipPolygons(front)
        if self.back is not None:
            back = self.back.clipPolygons(back)
        else:
            back = []
        front += back
        return front
        
    def clipTo(self, bsp):
        self.polygons = bsp.clipPolygons(self.polygons)
        if self.front is not None:
            self.front.clipTo(bsp)
        if self.back is not None:
            self.back.cliptTo(bsp)
            
    def allPolygons(self):
        polygons = self.polygons[:]
        if self.front is not None:
            polygons += self.front.allPolygons()
        if self.back is not None:
            polygons += self.back.allPolygons()
        return polygons
    
    def build(self, polygons):
        if not len(polygons):
            return
        if self.plane is None:
            self.plane = polygons[0].plane.clone()
        front = []
        back = []
        for index in range(len(polygons)):
            self.plane.splitPolygon(polygons[i], self.polygons, self.polygons, front, back)
        if len(front):
            if self.front is None:
                self.front = CSG_Node()
                self.front.build(front)
        if len(back):
            if self.back is None:
                self.back = CSG_Node()
                self.back.build(back)