# 3D Theory - Polygonal Modeling

 By: nobody ( Nobody/Anonymous ) Do you have plans to add some mesh utils??   2003-06-15 21:58 I am working on am mesh animator and it is coming along nice but I have just run into some mesh utilties which I was saving til the end. I thought these should not be too difficult to create but now I think it is harder: - Mesh normal repair utility: makes sure normals are pointing the right way. Since many meshes have this problem. I started by build a program which starts on a correctly oriented triangle. It then starts crawling to neighboring triangles and reorienting them is necessary so their normals point the right direction. This strategy is based on triangle sharing edges. This is a good idea except for problem # 2. - Mesh repair utility which gets rid of redundant points, edges triangles. Meshes also have some cracks in them or even unconnected peices ( maybe someone created a box and placed it so it bisected a sphere for example ). In this case the crawling algorithm from #1 doesn't work since the object don't share edges. One thing that can be done is to merge all points which are within a certain distance but this still doesn't resolve all issues. - Mesh simplification utility: This means you need a data structure which contains edges as well as vertices and facets. Weights need to be assigned to edges so you can choose the least expensive edges to collapse. Some data alos has to be stored so you can uncollapse edges. My method of doing this is working poorly right now mostly due to lack of effective data structures. I just don't know the best way to do this. Through all this I want to preserve material boundries so a boundry edge must be left alone. - All of these are time consuming processes. Comparing a point against all other points in a set to see if it is within a distance can get very slow with large meshes. K-d trees are used speed things up. This is a tree which can organize things by relative ranges of distance. I found a GNU licensed mesh repairer called AdMesh and there is a description of how it works. It is free for non-commercial use. If you want to distribute your stuff you would have to roll your own version from scratch ( They do have some whitepapers on it ).
 By: martinbaker ( Martin Baker ) RE: Do you have plans to add some mesh utils??   2003-06-16 08:52 I would very much like to include mesh reduction, subdivision, repair and generation in the website and program. As you say, this does seem to be a complex subject, especially if we include performance (speed) issues. As a start it would be good to find definitions of the above terms and some simple algorithms to implement them. I had a look at AdMesh here: http://www.varlog.com/products/admesh/ As you say it says that it is distributed under the terms of the GNU General Public License (GPL) but it says that it is not in the public domain and its source code cannot be used in commercial software. This seems contradictory? I thought that GNU software could be used by anyone provided that they comply with the GPL licence? I could not find the whitepapers you mentioned, the only documents that I could find seem to be about how to use the program as opposed to the theory. Martin