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
- 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 ).
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.
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.
He is a good reference and has a lot of research on mesh simplification and
reconstruction on his sight. It looks like he has been responsible for a lot
of definitive progressive/LOD mesh reasearch.
There was also a potentially helpful mesh library at http://zerowing.idsoftware.com/GtkSDK/
I think thats right if not use google to look for something like
It is a mesh library with structures like K-Dtrees and other utilities built
in. You still have to put together your algorithms it does have tools though.
I am do not understand the gnu public licensing well. I always though it
meant you could not distribute for commerical profit or copyright work
dervied from something which was already GNU licensed. You could charge a
distribution fee to cover cost of distribution and a maintenance or warranty
fee. Anything you you build you also have to have full source code avalaible
for whoever want it.
Here is something else from the end of the licensing message
"This General Public License does not permit incorporating your program
proprietary programs. If your program is a subroutine library, you may
consider it more useful to permit linking proprietary applications with the
library. If this is what you want to do, use the GNU Library General
Public License instead of this License."
Using this you could still have code which remained hidden from people so
long as the GNU licensed stuff remained in the library. That is my
understanding at least.
So I built a mesh simplifier that was collapsing edges. There still are a lot
- The hardest thing about collapsing edges is finding which edge is the next
to collapse. Assign an edge weight based on how much of a difference there is
between the original and resulting mesh. How to measure this difference is a
problem. And how to place the collapse point to minimize this difference is
If a vertex lies on a sharp corner or edge and you collapse a linked edge you
will can put a divot in your object. It might look better to bias the point
resulting from a collapsed edge torwards a sharp corner.
Thank you, I will have a look at the references and link a
copy of your messages if that’s alright.
Do you have an algorithm, or set of rules, for your mesh simplifier? Is it
something like this:
1) Remove each vertex in turn by moving it along an edge to merge with
2) For each case calculate weight from distance between original point and
nearest polygon surface.
3) Choose vertexes to remove which minimise weight.
I guess I should really read the references before I take up you time asking
Where I can, I have put links to Amazon for books that are relevant to
the subject, click on the appropriate country flag to get more details
of the book or to buy it from them.
Curves and Surfaces for CAGD
Commercial Software Shop
Where I can, I have put links to Amazon for commercial software, not
directly related to this site, but related to the subject being discussed,
click on the appropriate country flag to get more details of the software
or to buy it from them.
Dark Basic Professional Edition - It is better to get this professional
This is a version of basic designed for building games, for example to
rotate a cube you might do the following:
make object cube 1,100
for x=1 to 360
rotate object 1,x,x,0
Game Programming with Darkbasic - book for above software