I guess you all have and AMD-chipset based graphic card. I had the exact same problem on 2 PC's running 16.04 and neither would run SH3D. However, I changed for an nVidia one, and it now works flawlessly.

It must have to do with the dropped support for 3D drivers, and the fall-back to default X.org.

Just my 2cents.