Triangles show up when baking?

I’m baking a full render to a UV mapped image… and I can’t seem to get rid of these triangle artifacts. Image size doesn’t matter, and subsurf at level 6 only gets rid of most of the problem- but not all (far right, tiny pixellated mess).

Anybody know what’s going on here?

Subsurf 6 seems to be way too high. 2 should be sufficient enough.
Is your mesh made up of tris or quads? Cause subsurf doesn’t work well with tris and can and will produce artifacts.
Did you turn on smooth on your object?

It’s all quads, and smooth is activated.

I had the same problem. It was solved when I hit the smooth button and then used edgeSplit modifier. After that there was no visible triangles.