Fog alters the color of polygons based on their distance from the camera. As objects and geometry get farther away from the camera, they start to blend into the background color. This is an easy and useful method to reduce the strain on the N64's RCP, and can improve performance.

If your level still has lag even with fog enabled, try cutting down the amount of polygons and active objects on screen.

To enable fog you first need to make sure that the RDP is set to 2 cycle mode:

Fast3D / Fast3DEX
BA 00 14 02 00 10 00 00

Fast3DEX2 / Fast3DZEX 
E3 00 14 02 00 10 00 00

C/C++
gsDPSetCycleType(G_CYC_2CYCLE)

Next we need to blend the fog in AA ZB mode. (see: http://n64devkit.square7.ch/n64man/gdp/gDPSetRenderMode.htm)

Fast3D / Fast3DEX
B9 00 03 1D C8 11 20 78 (If surface is fully opaque)
B9 00 03 1D C8 11 30 78 (If surface has transparency)

Fast3DEX2 / Fast3DZEX 
E2 00 03 1D C8 11 20 78 (If surface is fully opaque)
E2 00 03 1D C8 11 30 78 (If surface has transparency)

C/C++
gsDPSetRenderMode(G_RM_FOG_SHADE_A, G_RM_AA_ZB_OPA_SURF2) // If surface is fully opaque
gsDPSetRenderMode(G_RM_FOG_SHADE_A, G_RM_AA_ZB_XLU_SURF2) // If surface has transparency

After that we now need to tell the RDP we want to use fog, so we enable the geometry mode flag for fog:

Fast3D / Fast3DEX
B7 00 00 00 00 01 00 00

Fast3DEX2 / Fast3DZEX 
D9 00 00 00 00 01 00 00

C/C++
gsSPSetGeometryMode(G_FOG)

The fog itself works in a range from a minimum to a maximum. Min can go as low as 0 (at near clip plane), and max can go as high as 1000 (at far clip plane). You can adjust these values to get your desired effect.

Fast3D / Fast3DEX
BC 00 00 08 AA AA BB BB

AAAA = 128000 / (max - min)
BBBB = (500 - min) * 256 / (max - min)

Fast3DEX2 / Fast3DZEX 
DB 00 00 08 AA AA BB BB

AAAA = 128000 / (max - min)
BBBB = (500 - min) * 256 / (max - min)

C/C++
gsSPFogPosition(min, max)

For those who have used the SM64Editor tool, here are the corresponding (min, max) values for each fog setting:

SUBTLE_1     = (980, 1000)
SUBTLE_2     = (948, 976)*
MODERATE_1   = (965, 1000)
MODERATE_2   = (960, 1000)
MODERATE_3   = (950, 1000)
MODERATE_4   = (940, 1000)
INTENSE      = (930, 1000)
VERY_INTENSE = (900, 1000)
HARDCORE     = (716, 932)*

* = Not exact, but its as close as I could get.

The fog color is a simple RGBA value that you define in the display list:

Fast3D / Fast3DEX / Fast3DEX2 / Fast3DZEX 
F8 00 00 00 RR GG BB AA

C/C++
gsDPSetFogColor(RED, GREEN, BLUE, ALPHA)

From the N64 Function Reference Manual for gDPSetFogColor:
N64 processes fog by Gouraud-shading the fog attenuation coefficients in the alpha channel of RDP. At that time, the BL adjusts the attenuation of the pipeline pixel colors to the surrounding fog color. Because the alpha channel of RDP is being used for Gouraud-shading the fog attenuation coefficient, normal alpha values cannot be Gouraud-shaded. In other words, you cannot change the transparency inside a single triangle when you are using fog.

What this says is that you cannot use vertex alpha transparency while fog is enabled. Fog is independent of lighting and textures, so you can still use the alpha transparency from those sources.

Because of how fog works, using a background that is not a solid color will make the fog look weird. It is best to use a solid color that matches the fog color.

If you are making or modifying a level in Super Mario 64, then you can change the background to a solid color by modifying the 0x19 command in the level's geometry layout.

• https://level42.ca/projects/ultra64/Documentation/man/pro-man/pro11/index11.8.html
• http://ultra64.ca/files/documentation/online-manuals/man/n64man/gdp/gDPSetFogColor.html
• http://n64devkit.square7.ch/n64man/gdp/gDPSetRenderMode.htm