# Fastest solution to compute normal

A physics engine return a deformed mesh (only geometry vertices). I take this mesh to render the geometry (~500000 vertices). What is the fastest solution and the least expensive to compute normal vertices every frame? OpenCL? Geometry Shaders? In a CPU thread? Other?

-
then what are you going to do with it? is this a typical object in your game (I really really hope not if you want to calculate the whole thing every frame, and not just store it)? how often will this object be "deformed"? – gardian06 May 4 '12 at 7:20
It's on a medical simulation. The object is deformed every frame. I need normals for rendering the mesh. – urza57 May 4 '12 at 7:25
I will assume that you mean vector, and not actual vertices (I do not know what that would even mean). find all faces (determine adjacent points). for each face take any 3 points on the face, and create 2 vectors (V1=p1-p2, V2=p1-p3) then take their cross product. keep in mind that if your camera is right, and nothing shows up try reversing your cross product this will give you a vector normal to the plane of the face. rinse, and repeat for each face. seriously try with a pyramid, or cube first – gardian06 May 4 '12 at 7:30
is that an actual question, or a statement? (I will go with question) the most complex part will be determining where the faces are (this is the big problem with collision detection on complex-convex polyhedrons), and once that is done constructing 2 vectors, and doing a cross product is relatively trivial. – gardian06 May 4 '12 at 7:40
This question cannot be answered as asked. What the "fastest solution" is will vary wildly with hardware and implementations. Not to mention that, regardless of what you're coming up with, you'll have to stream 500k+ vertices per frame. The best you can do is try out several techniques and benchmark them. That being said, are you sure your physics system can't be made to spit out normals? It must have most of the information needed to generate them when it does its deformation. – Nicol Bolas May 4 '12 at 19:23

A lot of this depends if you need interpolated normals over the polygon or can live with a the 'faceted look' of per-triangle normals.

The per-triangle normals are a lot easier to compute: a simple cross prod of the three vertices with one of them being made a local-origin by subtracting it from the other two first.

Smooth per-vertex require finding all the triangles that share a vertex, and averaging their per-triangle normals, by weighting their angle by some factor, typically the angle of the corner made at the vertex for that triangle.

If your mesh can have an arbitrary number of triangles meeting in a corner this can be rather difficult implement on a GPU.

-

Try looking at implementing it in either OpenCL or CUDA. A lot of medical applications are going towards that field because of the insane amount of data they have to process per frame.

The problem you have should be easy to parallelize (run on the multiple cores of a videocard). You have a fixed input (three vertices) and a fixed output (one normal). So, a version of the program could be:

• Physics simulation deforms the mesh.
• Upload data to OpenGL using vertex buffers.
• Lock buffers for OpenCL processing.
• OpenCL writes to normal buffer, keeping everything in video memory.
• Unlock buffers for OpenGL usage.
• Rendering using vertex data with normals.
-

So I coded simple C++ test program that calculates normal for pair of vectors using cross product 500000 times. Source highlights are:

``````struct Vector3
{
float x, y, z;

Vector3();
};

const int n = 500000;

Vector3 a[n], b[n], c[n];

void CalculateNormals()
{
for (int i = 0; i < n; ++i)
{
c[i].x = a[i].y * b[i].z - a[i].z * b[i].y;
c[i].y = a[i].z * b[i].x - a[i].x * b[i].z;
c[i].z = a[i].x * b[i].y - a[i].y * b[i].x;
}
}
``````

I've executed 1000 passes on random data. And average time of `CalculateNormals()` function to finish is `3.11` ticks. So I think the idea to calculate this stuff on CPU is straithforward and efficient. By the way my CPU is `Intel Core i5-2400 @ 3.10 GHz`.

-
Interpolation between triangle normals also needs to be done in order to get smooth shading. The cross-product approach will only give flat shading. – ktodisco May 4 '12 at 8:20
@iodiot the result vectors are not normalized! – Maik Semder May 4 '12 at 8:43
@iodiot a few things `a`, and `b` should be determined for the current face not just given as values, and could very well be static to the current iteration of the for loop. And, `500000` was not the face count it was the number of vertices (the number of faces will be some fraction of the number of vertices, and typically higher) – gardian06 May 4 '12 at 9:02
@Maik Semder Normal attached to the vertex can be normalized trivially in vertex shader. Sorry I forgot about this, cause was surprised by CPU performance. – iodiot May 4 '12 at 9:07
@iodiot no problem. However, it would be good to update the post, measure the timing including normalizing. – Maik Semder Jun 20 '12 at 10:31