# 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.

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. – kevintodisco 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

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.

If you're doing this on the CPU with indexed meshes and I'm assuming smooth vertex normals, then the fastest way I've come up with is:

1. Make sure polygon->vertex access is cache-friendly. This makes a world of difference if you minimize cache misses here. You can look at Tom Forsythe's Linear-Speed Vertex Cache Optimization as a start.
2. If the mesh is super high res like millions of vertices, it might take too long to do these vertex cache optimizations and their results might not be so great. In that case, split your big mesh into multiple smaller sub-meshes with special handling of the vertices at the boundary of each sub-mesh to produce seamless results. That will also allow you to do these vertex cache optimizations in parallel.
3. Use fast SIMD inverse square root if you're okay with an approximation of the normal like rsqrtps.
4. This is a little bit dirty and could lead to noticeable artifacts if you aren't careful but sometimes you can delay the normal computations and do them in parallel/async with deforming objects without the user noticing. This way you might deform the mesh for a few iterations before you update the normals once. Now I'm not sure if this would be acceptable for a game engine. I'm coming at this from the VFX side of the industry when users do things like sculpt deformations on meshes with 10 million polygons (and not necessarily triangles). I've found in those cases at least that you can be sneaky and not update the normals necessarily with every single frame rendered and get away with it, using a separate thread for updating normals which tends to lag a frame or two behind the deformations.