Mesh reduction
Martin Baker
I am trying to work out a mesh reduction algorithm by collapsing edges in
turn and measuring the error from the distance from the vertex removed to
the plane (or its square?).
However the equations that I worked out to do this are quite complex which
would make the algorithm very slow and I suspect it would not be very
resilient (for example if a face has 3 vertices in a line).
Does anyone know a way to improve this method?
I really need diagrams to explain this, so I have done so here:
http://www.euclideanspace.com/threed/solidmodel/boundary/mesh/
I suspect that, instead of working out the error from the vertex position
removed and the 3 vertices at the corners of a triangular section of plane,
it might be simpler to take these 4 points and calculate the minimum
curvature of a plane to make it pass through all 4 points? I've no idea how
to work this out, can anyone help me?
Alternatively does anyone have any ideas how I could simplify the algorithm
on my web page.
I would appreciate any help.
Martin
Dave Eberly
"Martin Baker" <bak...@btinternet.com> wrote in message
news:br5dnl$pen$1...@sparta.btinternet.com...
> I am trying to work out a mesh reduction algorithm by collapsing edges in
> turn and measuring the error from the distance from the vertex removed to
> the plane (or its square?).
>
> However the equations that I worked out to do this are quite complex which
> would make the algorithm very slow and I suspect it would not be very
> resilient (for example if a face has 3 vertices in a line).
>
> Does anyone know a way to improve this method?
Have you looked at the Garland-Heckbert algorithm for
edge collapsing? They measure the error in a fairly simple
manner.
\bibitem{Garland1}
Michael Garland and Paul Heckbert,
{\em Surface simplification using quadric error metrics},
Proceedings of SIGGRAPH 1997,
pp. 209--216.
\bibitem{Garland2}
Michael Garland and Paul Heckbert,
{\em Simplifying surfaces with color and texture using quadric error
metrics},
IEEE Visualization 1998,
pp. 263--269.
--
Dave Eberly
ebe...@magic-software.com
http://www.magic-software.com
http://www.wild-magic.com
Martin Baker
Thanks for your help, I think I did come across Garlands papers before
but I didn't understand the maths first time round. I could not find a
definition of the Q matrix, I've had another try and I think I'm
working it out, is [Q] a 4x4 matrix where:
q00,q01,q02, q10,q11,q12,q20,q21,q22 = n nT
q03,q13,q23 = d*n
q03,q13,q23 = (d*n)T
q33 = d*d
where n=normal vector at original point
and I'm not sure about d, is it the scalar distance from the original
point from the origin?
Then the error at point v is given by:
vT [Q] v
Do you think I'm on the right track?
Martin
Dave Eberly
Yes. The value d is a signed distance (could be negative) as
long as "n" is unit length. What you mention is one term
of the error metric. The full metric is the sum of such
terms over all such planes of the triangles that share the
vertex.
Martin Baker
> as long as "n" is unit length
So rather than d being the distance from the origin to the point, it
is the distance from the origin in the direction of n until it
intersects the plane which is tangential to the point. (in other words
it is the d from the definition of the tangential plane as a x + b y +
c z + d = 0).
So given that I am starting with a mesh defined by an array of points
(p) and unit length normals (n), is it correct that I can calculate
each d by:
d = p dot n
Thanks,
Martin
Dave Eberly
> is the distance from the origin in the direction of n until it
> intersects the plane which is tangential to the point. (in other words
> it is the d from the definition of the tangential plane as a x + b y +
> c z + d = 0).
This is how the Garland and Heckbert SIGGRAPH paper
formulates the problem. The 4-by-4 matrix is
Q = sum_{k=1}^{m} A_k * Transpose(A_k)
where A_k is the 4-by-1 vector of coefficients for the plane
equation.
> So given that I am starting with a mesh defined by an array of points
> (p) and unit length normals (n), is it correct that I can calculate
> each d by:
> d = p dot n
If n = (a,b,c) is unit-length and p = (x,y,z),
0 = a*x+b*y+c*z+d = (p dot n) + d
Martin Baker
So if we multiply out the terms we get:
[Q] =
aa ab ac ad
ba bb bc bd
ca cb cc cd
da db dc dd
where:
a = n.x
b = n.y
c = n.z
d = -(p dot n)
p = position vector
n = unit normal
and the error is given by the sum of every: vT [Q] v
where v = [p.x p.y p.z 1.0] i.e. p padded out with an extra 1
So if I multiply out these terms before collapsing any edges I must get
zero. I think I'll try that just to satisfy myself that it works.
Then when I collapse an edge I just add together the corresponding [Q] for
each vertex to give [Q] for the new vertex.
Thank you very much for this, I was working from quadrics.pdf and
quadric2.pdf which I got from:
http://graphics.cs.uiuc.edu/~garland/research/quadrics.html
and these papers did not make this clear (or they assumed a level of
knowledge I don't have). I can never get papers from SIGGRAPH does it need
some sort of subscription?
Anyway I really appreciate your help, this does look like a powerful method,
I will implement it and see what results I get, thanks,
Martin
Dave Eberly
> I can never get papers from SIGGRAPH does it need
> some sort of subscription?
You can download articles from the ACM Digital Library,
but this requires a paid subscription.
> Anyway I really appreciate your help, this does look like a powerful
method,
> I will implement it and see what results I get, thanks,
I have an implementation in my graphics engine available at
my web sites (at the "Graphics" source page, "continuous
level of detail" section). However, I use a different error
metric than what Garland and Heckbert proposed.