polyoverflow.py for Dolphin (Felk's python build)

from dolphin import event, gui, controller, memory, registers, savestate

addr_globalContext = 0x801C9660 + 0xB1C140
addr_colCtx = addr_globalContext + 0x7C0
addr_exitList = addr_globalContext + 0x11E04
colCtx_colHeader = memory.read_u32(addr_colCtx) + 0xB1C140
exitList = memory.read_u32(addr_exitList) + 0xB1C140
colCtx_colHeader_vtxList = memory.read_u32(colCtx_colHeader + 0x10) + 0xB1C140
colCtx_colHeader_polyList = memory.read_u32(colCtx_colHeader + 0x18) + 0xB1C140
colCtx_colHeader_surfaceTypeList = memory.read_u32(colCtx_colHeader + 0x1C) + 0xB1C140
'''
def sign(p1x, p1z, p2x, p2z, p3x, p3z):
    return (p1x - p3x) * (p2z - p3z) - (p2x - p3x) * (p1z - p3z)

def pointInTriangle(px, pz, v1x, v1z, v2x, v2z, v3x, v3z):

    if v1x==v2x and v1z == v2z:
        return False
    if v2x==v3x and v2z == v3z:
        return False
    if v3x==v1x and v3z == v1z:
        return False

    d1 = sign(px, pz, v1x, v1z, v2x, v2z)
    d2 = sign(px, pz, v2x, v2z, v3x, v3z)
    d3 = sign(px, pz, v3x, v3z, v1x, v1z)
    has_neg = (d1 < 0) or (d2 < 0) or (d3 < 0)
    has_pos = (d1 > 0) or (d2 > 0) or (d3 > 0)
    return not (has_neg and has_pos)

def findYPosOfTriangleForXZ(x, z, p1x, p1y, p1z, p2x, p2y, p2z, p3x, p3y, p3z):
    b = (x*(p2z-p1z) - p1x*(p2z-p1z) - z*(p2x-p1x) + p1z*(p2x-p1x))/((p3x-p1x)*(p2z-p1z) - (p3z-p1z)*(p2x-p1x))
    a = (x - p1x - b*(p3x-p1x))/(p2x-p1x)
    return p1y + a*(p2y-p1y) + b*(p3y-p1y)
'''

def IS_ZERO(f):
    return abs(f) < 0.008

def SQ(x):
    return x*x

def Math3D_CirSquareVsTriSquare(x0, y0, x1, y1, x2, y2, centerX, centerY, radius):
    minX = maxX = x0
    minY = maxY = y0
    if x1 < minX:
        minX = x1
    elif maxX < x1:
        maxX = x1
    if y1 < minY:
        minY = y1
    elif maxY < y1:
        maxY = y1
    if x2 < minX:
        minX = x2
    elif maxX < x2:
        maxX = x2
    if y2 < minY:
        minY = y2
    elif maxY < y2:
        maxY = y2
    return (minX - radius) <= centerX and (maxX + radius) >= centerX and (minY - radius) <= centerY and (maxY + radius) >= centerY

def Math3D_PointDistSqToLine2D(x0, y0, x1, y1, x2, y2):
    ret = False
    xDiff = x2 - x1
    yDiff = y2 - y1
    distSq = SQ(xDiff) + SQ(yDiff)
    if IS_ZERO(distSq):
        return False, 0.0
    perpendicularRatio = (((x0 - x1) * xDiff) + (y0 - y1) * yDiff) / distSq
    if perpendicularRatio >= 0.0 and perpendicularRatio <= 1.0:
        ret = True
    perpendicularPoint = [(xDiff * perpendicularRatio) + x1, (yDiff * perpendicularRatio) + y1]
    lineLenSq = SQ(perpendicularPoint[0] - x0) + SQ(perpendicularPoint[1] - y0)
    return ret, lineLenSq

def Math3D_TriChkPointParaYImpl(v0, v1, v2, z, x, detMax, chkDist, ny):
    if not Math3D_CirSquareVsTriSquare(v0[2], v0[0], v1[2], v1[0], v2[2], v2[0], z, x, chkDist):
        return False
    chkDistSq = SQ(chkDist)
    if ((SQ(v0[2] - z) + SQ(v0[0] - x)) < chkDistSq) or ((SQ(v1[2] - z) + SQ(v1[0] - x)) < chkDistSq) or ((SQ(v2[2] - z) + SQ(v2[0] - x)) < chkDistSq):
        return True
    detv0v1 = ((v0[2] - z) * (v1[0] - x)) - ((v0[0] - x) * (v1[2] - z))
    detv1v2 = ((v1[2] - z) * (v2[0] - x)) - ((v1[0] - x) * (v2[2] - z))
    detv2v0 = ((v2[2] - z) * (v0[0] - x)) - ((v2[0] - x) * (v0[2] - z))
    if ((detMax >= detv0v1) and (detMax >= detv1v2) and (detMax >= detv2v0)) or ((-detMax <= detv0v1) and (-detMax <= detv1v2) and (-detMax <= detv2v0)):
        return True
    if abs(ny) > 0.5:
        ret, distToEdgeSq = Math3D_PointDistSqToLine2D(z, x, v0[2], v0[0], v1[2], v1[0])
        if ret and distToEdgeSq < chkDistSq:
            return True
        ret, distToEdgeSq = Math3D_PointDistSqToLine2D(z, x, v1[2], v1[0], v2[2], v2[0])
        if ret and distToEdgeSq < chkDistSq:
            return True
        ret, distToEdgeSq = Math3D_PointDistSqToLine2D(z, x, v2[2], v2[0], v0[2], v0[0])
        if ret and distToEdgeSq < chkDistSq:
            return True
    return False

def Math3D_TriChkPointParaYIntersectInsideTri(v0, v1, v2, nx, ny, nz, originDist, z, x, chkDist):
    if IS_ZERO(ny):
        return False, None
    if Math3D_TriChkPointParaYImpl(v0, v1, v2, z, x, 0.0, chkDist, ny):
        yIntersect = (((-nx * x) - (nz * z)) - originDist) / ny
        return True, yIntersect
    return False, None

def CollisionPoly_CheckYIntersect(polyVertA, polyVertB, polyVertC, polyNormX, polyNormY, polyNormZ, polyDist, x, z, chkDist):
    return Math3D_TriChkPointParaYIntersectInsideTri(polyVertA, polyVertB, polyVertC, polyNormX, polyNormY, polyNormZ, polyDist, z, x, chkDist)

framecount = 0
while True:
    await event.frameadvance()
    framecount = (framecount+1)%2
    if framecount == 0:
        memory.write_u16(0x80CE4340, 1)
    else:
        memory.write_u16(0x80CE4340, 0)
    for i,polyAddr in enumerate([0x80F0CE28-0x25800,0x80F0CE28]):
        polySurfaceTypeId = memory.read_u16(polyAddr)
        vertIdAHex = memory.read_u16(polyAddr+2)
        vertIdBHex = memory.read_u16(polyAddr+4)
        vertIdC = memory.read_u16(polyAddr+6)
        normXHex = memory.read_s16(polyAddr+8)
        normYHex = memory.read_s16(polyAddr+10)
        normZHex = memory.read_s16(polyAddr+12)
        dist = memory.read_s16(polyAddr+14)

        good = True
        surfaceExitIndex = memory.read_u8(colCtx_colHeader_surfaceTypeList + 8*polySurfaceTypeId + 2) & 0x1F
        if surfaceExitIndex == 0 or memory.read_u16(exitList + 2*(surfaceExitIndex-1)) != 0x1E00:
            good = False
        ignoreEntity = vertIdAHex & 0x4000
        if ignoreEntity:
            good = False
        vertAX = memory.read_s16(colCtx_colHeader_vtxList + 6*(vertIdAHex&0x1FFF) + 0)
        vertAY = memory.read_s16(colCtx_colHeader_vtxList + 6*(vertIdAHex&0x1FFF) + 2)
        vertAZ = memory.read_s16(colCtx_colHeader_vtxList + 6*(vertIdAHex&0x1FFF) + 4)
        vertBX = memory.read_s16(colCtx_colHeader_vtxList + 6*(vertIdBHex&0x1FFF) + 0)
        vertBY = memory.read_s16(colCtx_colHeader_vtxList + 6*(vertIdBHex&0x1FFF) + 2)
        vertBZ = memory.read_s16(colCtx_colHeader_vtxList + 6*(vertIdBHex&0x1FFF) + 4)
        vertCX = memory.read_s16(colCtx_colHeader_vtxList + 6*vertIdC + 0)
        vertCY = memory.read_s16(colCtx_colHeader_vtxList + 6*vertIdC + 2)
        vertCZ = memory.read_s16(colCtx_colHeader_vtxList + 6*vertIdC + 4)
        if vertAY > 25 and vertBY > 25 and vertCY > 25:
            good = False
        normX = normXHex / 0x7FFF
        normY = normYHex / 0x7FFF
        normZ = normZHex / 0x7FFF
        if -0.008 < normY < 0.008:
            good = False
        ret, ypos = CollisionPoly_CheckYIntersect([vertAX,vertAY,vertAZ],[vertBX,vertBY,vertBZ],[vertCX,vertCY,vertCZ],normX,normY,normZ,dist,494,-1214,1.0)
        if not ret:
            good = False
            ypos = 9999
        if ypos > 25 or ypos < -32000:
            good = False

        polystr = "%04X %04X(%d,%d,%d) %04X(%d,%d,%d) %04X(%d,%d,%d) %04X %04X %04X %04X - %d"%(polySurfaceTypeId,vertIdAHex,vertAX,vertAY,vertAZ,vertIdBHex,vertBX,vertBY,vertBZ,vertIdC,vertCX,vertCY,vertCZ,normXHex,normYHex,normZHex,dist,ypos)
        if good:
            gui.draw_text((10, 100+10*i), 0xFF00FF00, polystr)
            print("%08X %08X %08X %04X - %s"%(memory.read_u32(0x80CF7D14), memory.read_u32(0x80CF7D18), memory.read_u32(0x80CF7D1C), memory.read_u16(0x80CF7DA6), polystr))
        else:
            gui.draw_text((10, 100+10*i), 0xFFFF0000, polystr)