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
- 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
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
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
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 of problems.
- 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 also hard.
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
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
execute_edge_collapse( highest_priority_edge )
this function joins the 2 points on either end of the edge. The 2 old
points now point to a new point which has been calculated to minimize
distortion of the object. If you draw a picture of this (most papers will
show pictures) you will see you also lose 2 triangles.
prioritize_all_edge( metric )
this builds a list of prioritized edges. The hardest part here is the
metric. What the metric does is it assigns higher priority to edges which
when collapsed will minimize the distortion of the original object.
One of the simple metrics to use is the quadric metric. It is not so simple
there is a paper by Michael Garland describing this and *** Source Code
***. If you go on google you can find this.
Basically a quadric is a 3d conterpart to a 2d quadratic curve. Quadric
objects typically look spheres hyperboles, half hyperboles, ... there
are pictures on other web sites. What happens is you build a Quadric which
approximates a small piece of your original object. It covers the edge
you are evaluating and the neighboring triangles. So it would look like
a convex or concave bowl. Then the collapsed point is calculated (*??
I am not sure how you could just try to split the difference between edge
endpoints but I think there is a better way described in the paper above.)
Then you find the distance from the collapsed point to the Quadric and
use that as a priority.
As edges are collapsed you need to keep quadrics up to date. Michael Garland
describes a way of doing this by assiging an initial Quadric to each vertex.
He then shows how to combine quadrics to to build a quadric which encompasses
both previous ones. In this way you can combine quadrics for the endpoints
of an edge to find the quadric for an edge.
There are other metrics for prioritizing edges but they look harder.
I am working on this now but am using Michael Garlands code just as reference
because of copyright rules. I also need to brush up on my linear algebra
some. It is hard to draw quadrics for reference. He does something where
he draws a gluSphere. This is puzzling to me. The gluSphere is the basic
form of a quadric with something like x*x + y*y + z*z = 0; He takes a
matrix representation of a Quadric and then multiplies the MODELVIEW matrix
by a matrix derived from the Quadric matrix representation. I know that
the basic Quadric matrix is the Identity matrix so this would be correct
for the basic case. I am not sure if this is a 100% accurate way to draw
quadrics or if he just did this for speed. He uses a function cholesky
which I dont really understand to obtain a new matrix and a number. Here
I am at a loss as to what is going on.