Happy weekend has come again and let me put a new result which I got from today’s working using a new script which still needs a big improvement.
Please click to see a larger image:
I upgraded the script and let me call its version script t7. It can take into account the existing faces that have been already made and avoid intersection of faces. It’s at midnight now so I want to continue this tomorrow…
I applied script t7 to a part of topology’s data as seen in the image below, following yesterday.
But it looks like the same as the previous result. To know why it caused the same result, I looked into the script, and found out the reason when I used a simpler point cloud. It didn’t work well because the script still has a lot of bugs which I couldn’t know when developing so it didn’t do the things that I expected.
So… It has become clear that I have to keep working for the bugs fixed and taking lots of tests.
I’m very pleased because Clem gave me another data. I’m going to make an effort for my development using it and I will also place a result when I have a test with it. Thanks a lot, Clem.
I think there would be people who have come up with an idea for point cloud and want to apply that to some data of point cloud. I’ll put topology’s data of point cloud here for them. If someone does an experiment using it, post it here and let me know, please. Any reports or comments would be appreciated and help people in this thread and me.
Hans, that data file will be very difficult to skin since there is a tremendous amount of spatial “noise” in it. There’s only one way to deal with noisy data…filter it! I know, it’s tough to live with…but that’s about all you can do. Here’s a couple of ways to do that.
Filter the data. A simple averaging of the values will get it smoother. Obviously, you’ll lose high frequency information.
Equivalently, calculate the average normal (or average slope) of a group of points. If you’re trying to make a face whoes normal (or slope) is far off (45 degrees or more) from the average normal (or slope) then it probably shouldn’t be there and you can discard this point
Both of the ways you mentioned appear to be helpful and it’s easy to imagine how to implement it. I wondered if a pre-processing method would be needed for the data when I first visualized it importing into Blender, as seen in the bottom of #39 post. I think I can use either or both of the ways to do that.
If you’re trying to make a face whoes normal (or slope) is far off (45 degrees or more) from the average normal (or slope) then it probably shouldn’t be there and you can discard this point
This could reduce more errors of making incorrect faces and keep the final mesh smoother. I want to try it right now, but I have many bugs in the new script, so I will go with your idea after fixing the bugs.
Discarding the point that shouldn’t be there means that you no longer consider about the point and you leave it with doing nothing? The point might have no chance to be connected to others to form a face. But ignoring several points will be ok if they have a too noisy location.
I wonder how I can calculate the average normal from some points around a center. I thought it is not so easy to get the average of normals because there are yet no faces in the points and you have no normal vectors. I don’t come up with a way for now…
Yes, discarding the point means don’t use for anything.
The average slope (tangent) or normal considers every point in a region. The region can be as small or large as desired. I would start with enough points to form 3 to 5 faces and work from there.
As you mentioned, using those points would probably make it possible to get the average normal, but I still have no idea for a mathematical formulation.
If you wanted to get a center position instead, then it would be easy for the formulation, like calculating vc = (v1+v2+…+v5)/5 as is well known. But… to get the average normal, what could the formulation for that be like…
Use a least squares fit for the planes…which is a pseudo-inverse. Do you understand that term? If not, no problem, it’s easy to do.
Form a matrix of the planes you want to fit (the planes are the rows of the matrix, it will be rectangular with dimensions # of planes x 3, since a plane is Ax + By +Cz = D)
Multiply the transpose of this matrix times itself (now will be square with dimension 3 x 3 and can be solved) and invert
Multiply the transpose, the inverse, and D…done!
Ok, now to implement this…I have no idea what functions are available in the python math library. Do you know? Surely the library has matrix multiplication and can solve a matrix (either through the inverse or guassian elimination). I will try to find out…and get back to you.
Wow, what a kind explanation! I have understood the way so clearly. It’s easy to understand. I have to say to you, thank you so much!
I see. What I had to consider was least squares method but it would be the last thing that I could. Thank you for your suggestion. I’m considering it for scripting.
I tried implementing grimey’s suggestion at post #68 and created a test script that can produce results like the image below. It has a group of vertices and a line that represents the direction of the average normal calculated based on grimey’s suggestion. It looks like a proper direction.
However I didn’t use exactly the same way of the least square method that grimey stated. I used the formulation z = a x + b y for the plane to fit. (Ax + By + Cz = D; z = -A/C x - B/C y + D/C; relation of the values is: D=0, -A/C=a, -B/C=b.) Could there be a difference between the both ways…
What you’ve done appears to work, but there is a difference between the two methods. For D=0, the plane goes through the origin. You must include D not equal 0 for the general case.
I repeated having tests for the script with several configurations and it was found out that it would produce two different normals even though they should be the same. The two is the yellow and red normals in the image below.
I guess that it is because I used the formulation z = a x + b y for the plane to fit. It would mean that the evaluation function for the least square is like:
But I wonder if it is better to use another evaluation function like:
It means that the square summation of the scalar product between an unit vector for the average normal (a, b, c) and each vertex (xi, yi, zi) can be minimized, and it would follow that it can minimize the square summation of the distance between the plane to fit and each vertex. This would enable the yellow and red normals in that image to be the same.
But it’s including the parameters nonlinearly like sqrt(1 - a^2 - b^2), so it makes things difficult.
Hans, you’re describing a method that is appears close to least squares. LS minimizes the error between the best fit plane and the other planes.
Here is a paper describing how to find the plane with three points (http://www.nagt.org/files/nagt/jge/abstracts/Fienen_v53n3p257.pdf) See equation 11.
I don’t like his extension to the n-point problem since it requires the solution of a cubic equation. The method I desribed above will work without solving a cubic!
Now that I became to be able to find the normal with three points, making average of all the normals calculated selecting each three points with that way (there would be n(n-1)(n-2)/(321) normals in n points) could be a way to get the average normal?
I’m thinking the second evaluation function including the parameters nonlinearly and I’m wondering if it can be solved with Lagrange’s method of undetermined multipliers…
Last weekend I have improved the script seen at post #62. I fixed the main bug that prevented the script from working well and then it started to work as I expected. Here is what I got with it. Another two bugs still remain in it, so fixing those all could probably make it possible to get the result a bit better than now.
Watching the mesh in MeshMode shows clearly whether or not the faces are overlapping, since the more times the faces have overlapped, the darker the purple color of the faces gets. So you can easily understand where the overlapping faces are existing when you see how dark purple color the faces have.
As you can see in the image above, the area where points are arranged closely or where points have a heavy noise can still cause problems. For these area, grimey’s suggestion will be needed to implement.
What do you feel like with this result? Do you think it has got better from post #62?
If I understand what you’re trying to do, No, the normal is a vector and won’t multiply like that…e.g.
[3x1] times [3x1] times [3x1]
which can’t be done.
You could add three normals and divide to 3 to get an average, although I don’t believe an average is the best method. It’s better than doing nothing, LOL!
I would have understood the way to find a normal when I selected three points. I thought the way could produce a single normal with three points. And using it repeatedly for any three points, adding the calculated normals all and dividing it by its number, I wanted to get a total average normal of a group of n points like your saying at post #64-2.
I saw that I would have to solve a cubic equation if I use Lagrange’s method for the second evaluation function to get the average normal. Mmm… It could make the scripting difficult.
The skinning is much improved now
Thank you. The number of created faces has been reduced well.
Solving a cubic difficult…oh yeah! The reference I gave above requires a cubic solution as well. A pseudo-inverse doesn’t require that though. :yes:
Remember, an average will often yield the correct normal…a least squares approach will always yield the correct normal (with minimum total error to all the other normals). I think in the long-run it is easier to program as well since python has all the needed functions. Basically, 5 or 6 lines of code for you to do once you found the normal of each plane.
