Povray mesh smoothing utility. ----------------------------- Sometimes you have a triangle mesh (see section 7.5.3.3 of the Povray documentation for more info in triangle meshes) made of triangles, and want to convert it to smooth_triangles. This utility may help you. It reads a povray file (and outputs it to a file or stdout) and when it finds a mesh with triangles, it converts them to smooth_triangles. Start the program without parameters to see the syntax. By default, it assumes that all the triangles are defined clockwise or counter-clockwise (it doesn't matter which, as long as all the triangles are defined the same way). You can use the -n option to tell the program not to assume this (it's off by default because the algorithm that corrects the triangles is very slow and memory consuming). The program uses quite slow algorithms, so very huge meshes may take time to compute (I really don't know any faster algorithm). The source code is pure ANSI C (at least I hope so), so it should compile in almost any system with almost any C compiler. If you are compiling in UNIX, you may have to include the math library with the -lm option, like this: gcc smooth.c -o smooth -lm If you are getting stack overflow errors when using the -n option on huge meshes, you should increase the stack size (see the help on your compiler). A DOS 32-bit executable is included for those using DOS/Windows without any C compiler. Being a 32-bit pmode executable, it shouldn't run out of memory even with huge meshes. It uses 1M of stack space, so the -n option should work with huge meshes (approximately 50000 triangles). Please send comments, suggestions and bug reports to warp@iki.fi (my english is not very good, so if you want to correct the mistakes in this text, send the corrections too). -- For those interested in the mathematics of the program, here comes an explanation: A normal vector is a vector perpendicular to a plane (or to a triangle in this case). Suppose you have a triangle defined by three points P1, P2 and P3 (so that P1 = , P2 = and P3 = ). To calculate a vector perpendicular to this triangle, you have to calculate the cross-product between the two vectors which define the triangle. These two vectors are P2-P1 and P3-P1 (ie. and ). Let's call the first vector v1 and the second v2, and the unit vectors <1,0,0>, <0,1,0> and <0,0,1> i, j and k respectively. You can calculate the cross-product ixj with this matrix: | i j k | |v1x v1y v1z| = (v1y*v2z-v2y*v1z)i + (v1z*v2x-v2z*v1x)j + (v1x*v2y-v2x*v1y)k |v2x v2y v2z| So the normal vector of the triangle will be: where v1x = x2-x1, v1y = y2-y1, and so on. Let's call this normal vector N = To get the right result smoothing the triangles, all the normal vectors have to be the same size. So we have to normalize the vector, ie. convert it so that its length will be 1. The length of a vector can be calculated with the Pythagoras theorem sqrt(x^2+y^2+z^2). If we divide a vector by its length, we'll get a vector pointing exactly to the same direction and whose length will be 1. So we divide our normal vector by its length: len = sqrt(nx^2+ny^2+nz^2) N = (the program also multiplies it by 10 to scale the normal vectors better) You can see this in the TriangleNormal() function in the source code. Now we have the triangle normals calculated and scaled appropriately, but this isn't enough. We need a normal vector for each point of the triangle, instead of a unique normal vector for the whole triangle (so that povray can make phong normal interpolation between them). Several triangles can use the same point. What we do, is to calculate the average of the normal vectors of all those triangles. So suppose there are for example five triangles in the mesh sharing a common point. To calculate the normal vector of this point, we sum the normal vectors of those five triangles and divide by 5 (ie. we calculate the average). You can see this in the CalculatePointNormals() function in the source code. The idea is that for each point you browse the triangle list and search for triangles that are using that point, sum their normal vectors together and divide by the number of triangles found. To speed things up a bit, I used this idea: The number of triangles that use the point and a pointer to the first triangle in the triangle list that uses the point is stored in the point data (this can be easily done while building the lists). Now instead of browsing the whole triangle list to search for triangles using the point, we start from the triangle stored in the point data and browse until we have find the right amount of triangles (which is also stored there). Since mesh creator programs usually store adjacent triangles one after another, all the triangles using a common point are usually close together in the triangle list, so finding them is a lot faster (and since we know the number of triangles, we can stop after finding the last one). The function AddTriangle() builds the lists. This is fine when all the triangles are defined clockwise or counter-clock- wise. If they aren't, we have to correct them first. I use the following algorithm for this: When building the triangle list, the program sets a mark (actually it gives the value -1 to the nx component of the triangle) to each triangle. It starts from the first triangle, marks it as corrected (it sets the nx to 1) and searches for adjacent triangles (ie. triangles that share at least 2 points with this one) and with its nx set to -1 (it skips triangles with nx set to 1). When it finds one, it checks if it's reversed (the 2 shared points must be defined reversed in the other triangle, for example if the points are the 1st and 2nd points of the actual triangle and the 2nd and 1st points of the found triangle, then the found triangle is correct, but if they are the 1st and 2nd points, it's reversed; we have to check all the 18 possibilities), and if so, it swaps the 1st and 2nd points of the found triangle. Then it calls recursively the same function with the found triangle. When it has found 3 triangles (or it has reached the end of the list), it stops and does the same to the next triangle in the list with nx set to -1. You can see this in the CorrectTriangles() function. This is a very stack memory consuming algorithm because of the recursion.