From: Martin Baker
Subject: Mesh reduction

 
 
 

Newsgroups: comp.graphics.algorithms
Date: 2003-12-09 13:11:02 PST

Mesh reduction

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: https://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

Message 5 in thread

From: Dave Eberly (eberly@magic-software.com)
Subject: Re: Mesh reduction

 
 
 

Newsgroups: comp.graphics.algorithms
Date: 2003-12-09 14:17:36 PST

"Martin Baker"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 eberly@magic-software.com

http://www.magic-software.com

http://www.wild-magic.com

Message 6 in thread

From: Martin Baker
Subject: Re: Mesh reduction

 
 
 

Newsgroups: comp.graphics.algorithms
Date: 2003-12-10 09:10:35 PST

Dave,

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

Message 7 in thread

From: Dave Eberly (eberly@magic-software.com)
Subject: Re: Mesh reduction

 
 
 

Newsgroups: comp.graphics.algorithms
Date: 2003-12-10 22:06:22 PST

"Martin Baker" wrote in message news:14f4f692.0312100910.28bdb0df@posting.google.com...

> 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?

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.

-- Dave Eberly eberly@magic-software.com http://www.magic-software.com http://www.wild-magic.com

Message 8 in thread

From: Martin Baker
Subject: Re: Mesh reduction

 
 
 

Newsgroups: comp.graphics.algorithms
Date: 2003-12-11 03:02:25 PST

> Yes.  The value d is a signed distance (could be negative)
> 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

Message 9 in thread

From: Dave Eberly (eberly@magic-software.com)
Subject: Re: Mesh reduction

 
 
 

Newsgroups: comp.graphics.algorithms
Date: 2003-12-11 05:47:06 PST

"Martin Baker" <bakerm@btinternet.com> wrote in message news:14f4f692.0312110302.766cfb7a@posting.google.com... > 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).   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   -- Dave Eberly eberly@magic-software.com http://www.magic-software.com http://www.wild-magic.com

Post a follow-up to this message

Message 10 in thread

From: Martin Baker
Subject: Re: Mesh reduction

 
 
 

Newsgroups: comp.graphics.algorithms
Date: 2003-12-11 08:29:06 PST

Dave,   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

From: Dave Eberly (eberly@magic-software.com)
Subject: Re: Mesh reduction

 
 
 

Newsgroups: comp.graphics.algorithms
Date: 2003-12-11 08:34:48 PST

"Martin Baker" wrote in message news:bra5vb$89k$1@sparta.btinternet.com...
> 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.

-- Dave Eberly eberly@magic-software.com

http://www.magic-software.com

http://www.wild-magic.com