The fundamental problem I'm facing is finding the normal given a polygon, its vertex normals and a random point in the polygon - I need to calculate the normal at that point. I'm having some serious trouble doing this, so if anyone can go a little further than just providing an outline, that'd be awesome. Am I right that I need to find the primary axis plane, project the vertices onto it and use bilinear interpolation for all vertex components based on the origin of the polygon on the projected plane? NOTE: I'm not a student (this is not a school task), I'm just stupid.

Assuming the polygon is convex, one approach would be to triangulate the polygon, find the triangle in which the point lies, and then compute the normal using the barycentric coordinates of the point with respect to the triangle as the weights for the triangle vertex normals. I've used this method for computing more accurate collision normals for curved patches represented by triangle meshes, and it seems to work quite nicely.

I remember there being a paper that was linked to recently that tells you how to find general barycentric coordinates for an arbitrary convex polygon. Using all the weights might give you a better normal, since if you only choose a single triangle then your normal will vary depending on how your polygon is triangulated and which three vertex normals are chosen.

This isn't the paper I was referring to, but it does present a general construction for barycentric coordinates:
A general construction of barycentric coordinates over convex polygons

Is that the standard approach? At first glance it seems horribly inaccurate (because it divides the polygon up, thus returning more of an estimate) given that I need this for a non-realtime application. I'll have better look at it soon, though.

Okay - silly me, making silly assumptions. I'll have a look into this. I glanced somewhere that this is method is probably the most convenient one. Can anyone comment on the speed factor?