From CloudModding OoT Wiki

MN for the algorithm, JSA for implementing it originally

Contents

C

Python code translated to C by spinout.

#include <math.h>

#define U16(a,p)	(((a)[p]<<8)|((a)[p+1]))
#define S16(a,p)	(signed short)U16(a,p)

void FixCollision(unsigned char * data, int vertOff, int TriOff, int TriCount)
{
    int i, pos, end = TriOff + (TriCount << 4);
    int v1, v2, v3, p1[3], p2[3], p3[3], dx[2], dy[2], dz[2], dn, ni[3];
    float nf[3], nd;
    for(pos=TriOff;pos<end;pos+=0x10)
    {
        v1 = U16(data, pos + 2);
        v2 = U16(data, pos + 4);
        v3 = U16(data, pos + 6);
        for(i=0;i<3;i++)
        {
            p1[i] = S16(data, vertOff + (v1 * 0x6) + (i << 1));
            p2[i] = S16(data, vertOff + (v2 * 0x6) + (i << 1));
            p3[i] = S16(data, vertOff + (v3 * 0x6) + (i << 1));
        }
        dx[0] = p1[0] - p2[0]; dx[1] = p2[0] - p3[0];
        dy[0] = p1[1] - p2[1]; dy[1] = p2[1] - p3[1];
        dz[0] = p1[2] - p2[2]; dz[1] = p2[2] - p3[2];
        
        ni[0] = (dy[0] * dz[1]) - (dz[0] * dy[1]);
        ni[1] = (dz[0] * dx[1]) - (dx[0] * dz[1]);
        ni[2] = (dx[0] * dy[1]) - (dy[0] * dx[1]);
        
        
        for(i=0;i<3;i++)
            nf[i] = (float)ni[i] * ni[i];
        
        nd = nf[0] + nf[1] + nf[2];
        
        for(i=0;i<3;i++)
        {
            if (nd)
                nf[i] /= nd;
            nf[i] *= 0x3FFF0001;
            nf[i] = sqrt(nf[i]);
            if(ni[i] < 0)
                nf[i] *= -1;
        }
        
        dn = (int)( (nf[0] / 0x7FFF * p1[0]) + (nf[1] / 0x7FFF * p1[1]) + (nf[2] / 0x7FFF * p1[2]) ) * -1;
        
        if(dn < 0)
            dn+=0x10000;
        data[pos+0xE] = (dn>>8)&0xFF;
        data[pos+0xF] = dn&0xFF;
        
        for(i=0;i<3;i++)
        {
            ni[i] = (int)nf[i];
            if(ni[i] < 0)
                ni[i] += 0x10000;
            data[pos+8+(i<<1)] = (ni[i]>>8)&0xFF;
            data[pos+9+(i<<1)] = ni[i]&0xFF;
        }
    }
}

C#

C# implementation by xdaniel, based on above C code. Non-standard functions ("Helpers" class) should be self-explanatory:

private void FixCollision(ref List<byte> Data, int VertOff, int TriOff, int TriCount)
{
    int i, pos, end = TriOff + (TriCount << 4);
    int v1, v2, v3, dn;
    int[] p1 = new int[3], p2 = new int[3], p3 = new int[3], dx = new int[2], dy = new int[2], dz = new int[2], ni = new int[3];
    float nd;
    float[] nf = new float[3];

    for (pos = TriOff; pos < end; pos += 0x10)
    {
        v1 = Helpers.Read16(Data, pos + 2);
        v2 = Helpers.Read16(Data, pos + 4);
        v3 = Helpers.Read16(Data, pos + 6);

        for (i = 0; i < 3; i++)
        {
            p1[i] = Helpers.Read16S(Data, VertOff + (v1 * 0x6) + (i << 1));
            p2[i] = Helpers.Read16S(Data, VertOff + (v2 * 0x6) + (i << 1));
            p3[i] = Helpers.Read16S(Data, VertOff + (v3 * 0x6) + (i << 1));
        }

        dx[0] = p1[0] - p2[0]; dx[1] = p2[0] - p3[0];
        dy[0] = p1[1] - p2[1]; dy[1] = p2[1] - p3[1];
        dz[0] = p1[2] - p2[2]; dz[1] = p2[2] - p3[2];

        ni[0] = (dy[0] * dz[1]) - (dz[0] * dy[1]);
        ni[1] = (dz[0] * dx[1]) - (dx[0] * dz[1]);
        ni[2] = (dx[0] * dy[1]) - (dy[0] * dx[1]);

        for (i = 0; i < 3; i++)
            nf[i] = (float)ni[i] * ni[i];

        nd = nf[0] + nf[1] + nf[2];

        for (i = 0; i < 3; i++)
        {
            if (nd != 0)
                nf[i] /= nd;
            nf[i] *= 0x3FFF0001;
            nf[i] = (float)Math.Sqrt((double)nf[i]);
            if (ni[i] < 0)
                nf[i] *= -1;
        }

        dn = (int)( (nf[0] / 0x7FFF * p1[0]) + (nf[1] / 0x7FFF * p1[1]) + (nf[2] / 0x7FFF * p1[2]) ) * -1;
        
        if (dn < 0)
            dn += 0x10000;

        Helpers.Overwrite16(ref Data, pos + 0xE, (ushort)(dn & 0xFFFF));

        for (i = 0; i < 3; i++)
        {
            ni[i] = (int)nf[i];
            if (ni[i] < 0)
                ni[i] += 0x10000;
            Helpers.Overwrite16(ref Data, (pos + 8 + (i << 1)), (ushort)(ni[i] & 0xFFFF));
        }
    }
}

Python

Deciphered from VB spaghetti to Python by spinout.

from struct import pack, unpack

def FixCollision(data, vertOff, TriOff, TriCount):
    for pos in range(TriOff, TriOff + (TriCount << 4), 0x10):
        v1,v2,v3 = unpack(">HHH", data[pos+0x2:][:0x6])
        p1 = unpack(">hhh", data[vertOff + (v1 * 0x6):][:0x6])
        p2 = unpack(">hhh", data[vertOff + (v2 * 0x6):][:0x6])
        p3 = unpack(">hhh", data[vertOff + (v3 * 0x6):][:0x6])
        
        dx = [p1[0] - p2[0], p2[0] - p3[0]]
        dy = [p1[1] - p2[1], p2[1] - p3[1]]
        dz = [p1[2] - p2[2], p2[2] - p3[2]]
        
        n = [(dy[0] * dz[1]) - (dz[0] * dy[1]),
             (dz[0] * dx[1]) - (dx[0] * dz[1]),
             (dx[0] * dy[1]) - (dy[0] * dx[1])]
        
        n_ = n[:]
        
        for i in range(3):
            n[i] *= float(n[i])
        
        nd = n[0] + n[1] + n[2]
        
        for i in range(3):
            if nd:
                n[i] /= nd
            n[i] *= 0x3FFF0001
            n[i] = sqrt(n[i])
            if(n_[i] < 0):
                n[i] *= -1
        
        dn = int(((n[0] / 0x7FFF * p1[0]) + (n[1] / 0x7FFF * p1[1]) + (n[2] / 0x7FFF * p1[2]) ) * -1)
        
        if(dn < 0):
            dn+=0x10000
        dn = dn & 0xFFFF
        
        for i in range(3):
            n[i] = int(n[i])
            if(n[i] < 0):
                n[i] += 0x10000
            n[i] = n[i] & 0xFFFF
        
        norms = pack(">HHHH", n[0], n[1], n[2], dn)
        
        if (norms != data[pos+0x8][:0x8]):
            data = data[:pos+0x8]+norms+data[pos+0x10:]
        
    return data