gdalgorithms-list

RE: [Algorithms] VIPM and UV texturing

[Tom F. <to...@mu...>]

Er... with the usual type of VIPM, you don't generate texture coords, or
indeed any new vertices,  at all. All you do is throw one point away and
collapse the edge onto the other one.

There are variants where you generate some sort of new "average" midpoint,
but (a) the quality improvement isn't very large and (b) it is quite a bit
less efficient to render, because for a given LoD, you have vertices that
are used by lower LoDs, but not the current one, which causes problems.

A related question is how to calculate texture coords (and other attributes)
when creating subdiv surfaces. I just use linear - seems to work OK with my
data, but others prefer to use other methods, such as use the subdiv surface
method, but on the attributes data. This gives excellent results BUT it is
possibly covered by a sneaky Pixar patent. It's still unclear exactly what
this patent covers (as with all patents, it's extremely vague), but there
may be some prior art that we can hide behind :-) In any case, simpler
methods such as Loop subdivision is often perfectly acceptable for
attributes, since perfect C1/G1 is not actually needed in most cases.

Tom Forsyth - Muckyfoot bloke.
Whizzing and pasting and pooting through the day.

> -----Original Message-----
> From: Mark Wayland [mailto:mwa...@to...]
> Sent: 08 August 2000 00:58
> To: gda...@li...
> Subject: [Algorithms] VIPM and UV texturing
> 
> 
> Hey all,
> 
> For those of you who are using/experimenting with VIPM, how are you
> generating your texture coords when the mesh is reduced ?  Do 
> you all assume
> planar mapping or what ?
> Any info or discussion on this topic would be appreciated.
> 
> Thanks,
> 
> Mark

RE: [Algorithms] VIPM and UV texturing

[Tom F. <to...@mu...>]

> From: Mark Wayland [mailto:mwa...@to...]
[snip]
> I cite different vertices because the actual UV coords are different
> (eg. a vertex is NOT just gemoetry, as in the D3D definition)
> 
> Doesn't anyone use large meshes that are textured using 
> multiple textures
> with VIPM,
> in that you would want the mesh as a whole to reduce, not the 
> similarly
> textured "pieces" ?

Ugh - no. Who would want to do that? :-)

Actually, yes. Edges where two textures meet (or indeed any discontinuous
data - colours, normals, etc) are what I call "feature" edges. The way I
deal with them is that you find all your feature eges, and then only allow
collapses _along_ edges and _onto_ edges. But I never allow collapses of a
vertex on a feature edge onto a another vertex that isn't on the same edge
(remember to disallow collapses of one feature vertex to another feature
vertex that _isn't_ on the same edge, e.g. between two parallel feature
edges).

But the fewer feature edges you have on your model, the better VIPM can cope
with it, and the better it collapses.

> What I'm tending to now assume is that most users of VIPM are 
> using it on
> trivially textured
> objects ... would this be a fair assumption, or once again 
> have I missed
> something ?

I dunno about "trivially" - mapping textures onto humanoid models (and
indeed the not-so-humanoid - we have slugs, two-headed creatures and ones
with four arms in Startopia) can get quite tricky.

But yes, VIPM only works well when there are comparatively few feature
edges.

There are some schemes that try to perform collapses across feature edges.
One is Jan Svarovsky's (follow the GDC link from the ultra-minimalist
homepage: http://www.svarovsky.com/), which has a discussion of these
collapses. But they're not pretty, and they complicate the collapse process.
By far the best way to proceed is to use friendly persuasion and Pavlovian
conditioning (a big stick is handy for this) until the artists to create
models with few feature edges.

Tom Forsyth - Muckyfoot bloke.
Whizzing and pasting and pooting through the day.

Re: [Algorithms] VIPM and UV texturing

[Mark W. <mwa...@to...>]

Thanks Tom,

The feature edges were what I am referring to ... what I'm trying to get at
is
that simple edge collapsing doesn't work _across_ a feature edge (yielding
the
undesired incorrect texture interpolation performed _by the card_, not me).

Fortunately you're a bit more eloquent (spelling?) than I :)

Your explanation is very much appreciated.

Thanks,

Mark

----- Original Message -----
From: "Tom Forsyth" <to...@mu...>
To: <gda...@li...>
Sent: Wednesday, August 09, 2000 7:19 PM
Subject: RE: [Algorithms] VIPM and UV texturing


> > From: Mark Wayland [mailto:mwa...@to...]
> [snip]
> > I cite different vertices because the actual UV coords are different
> > (eg. a vertex is NOT just gemoetry, as in the D3D definition)
> >
> > Doesn't anyone use large meshes that are textured using
> > multiple textures
> > with VIPM,
> > in that you would want the mesh as a whole to reduce, not the
> > similarly
> > textured "pieces" ?
>
> Ugh - no. Who would want to do that? :-)
>
> Actually, yes. Edges where two textures meet (or indeed any discontinuous
> data - colours, normals, etc) are what I call "feature" edges. The way I
> deal with them is that you find all your feature eges, and then only allow
> collapses _along_ edges and _onto_ edges. But I never allow collapses of a
> vertex on a feature edge onto a another vertex that isn't on the same edge
> (remember to disallow collapses of one feature vertex to another feature
> vertex that _isn't_ on the same edge, e.g. between two parallel feature
> edges).
>
> But the fewer feature edges you have on your model, the better VIPM can
cope
> with it, and the better it collapses.
>
> > What I'm tending to now assume is that most users of VIPM are
> > using it on
> > trivially textured
> > objects ... would this be a fair assumption, or once again
> > have I missed
> > something ?
>
> I dunno about "trivially" - mapping textures onto humanoid models (and
> indeed the not-so-humanoid - we have slugs, two-headed creatures and ones
> with four arms in Startopia) can get quite tricky.
>
> But yes, VIPM only works well when there are comparatively few feature
> edges.
>
> There are some schemes that try to perform collapses across feature edges.
> One is Jan Svarovsky's (follow the GDC link from the ultra-minimalist
> homepage: http://www.svarovsky.com/), which has a discussion of these
> collapses. But they're not pretty, and they complicate the collapse
process.
> By far the best way to proceed is to use friendly persuasion and Pavlovian
> conditioning (a big stick is handy for this) until the artists to create
> models with few feature edges.
>
> Tom Forsyth - Muckyfoot bloke.
> Whizzing and pasting and pooting through the day.
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] VIPM and UV texturing

[Jeff L. <je...@di...>]

Hi all.  New to this discussion but I have recently had a couple of projects where this issue has been very important.

The issue you bring up about texture coordinates and any sort of mesh LOD system is critical.  That is why I insist that the LOD tools allow artists to hand designate edges that will not collapse.  Any algorithmic method you try and find will fail in certain cases.  The algorithms handle texture projections like sphere and cylinder wraps pretty well but arbitrary UV texturing is a real problem.

One particular problem I will share that comes up often is when texturing characters.  My system automatically will preserve vertices that have texture coordinate discontinuities.  However, artists will often model a character with only half of the texture (particularly in the face) then just reflect the texture coords to save texture space.

Now the problem as you would guess is you have the face with coordinates like (1,0) -----  (0,0) ---- (1,0).  Obviously more granular then that. There are no texture coordinate discontinuities so the algorithm says it is ok.  The surface of the face is roughly flat so the internal vertex and edges are good candidates for collapse.  However, you then get the nice situation of  (1,0) ------ (1,0).  Doesn't look so hot.  I have the artists tag reflected seam vertices as uncollapsable until very late in the order.

Let me paraphrase you by saying the algorithms are most efficient when working on trivially textured objects.  Anything else requires good artist tools and some TLC.

-Jeff

At 06:44 PM 8/9/2000 +1000, you wrote:
> >     Well, I think the thing you missed is that VIPM is mainly aimed
>towards
> > meshes that are more like skinned meshes (ie, all points only have a
>single
> > vertex associated with them - Hence each set of adjacent triangles must be
> > specifiable as a strip). I like to call these sort of meshes, highly
> > connected meshes (HCM), for the simple purpose that with appearance to the
> > renderer, they share vertices, and are therefore connected.
>
>I cite different vertices because the actual UV coords are different
>(eg. a vertex is NOT just gemoetry, as in the D3D definition)
>
>Doesn't anyone use large meshes that are textured using multiple textures
>with VIPM,
>in that you would want the mesh as a whole to reduce, not the similarly
>textured "pieces" ?
>
>What I'm tending to now assume is that most users of VIPM are using it on
>trivially textured
>objects ... would this be a fair assumption, or once again have I missed
>something ?

Re: [Algorithms] VIPM and UV texturing

[Charles B. <cb...@cb...>]

Hi Jeff,

really, you should be including UV's and RGB's and Normals as 
part of the quadric error metric, so that this kind of thing
should be detected automagically, and should be put late in
the collapse list by the system.  I've found that if you
use a proper (eg. comprehensive and robust) error metric,
then almost zero artist intervention is necessary.  In fact,
I find that the system is generally much better at ordering
collapses than artists are.  Of course, there are exceptions,
which usually occur because of the fact that I'm not actually
looking in the texture bits; eg. changing the uv's slightly
in a region of the texture which is very high frequency
produces much more visual error than if you change the uv's in
a very low frequency region of the texture.  To handle this
correctly, you do need some sort of artist cue, as you propose.
I like Tom's method of reducing to a specific mesh.

At 10:06 AM 8/9/2000 -0700, you wrote:
>Now the problem as you would guess is you have the face with coordinates
like (1,0) -----  (0,0) ---- (1,0).  Obviously more granular then that.
There are no texture coordinate discontinuities so the algorithm says it is
ok.  The surface of the face is roughly flat so the internal vertex and
edges are good candidates for collapse.  However, you then get the nice
situation of  (1,0) ------ (1,0).  Doesn't look so hot.  I have the artists
tag reflected seam vertices as uncollapsable until very late in the order.>
--------------------------------------
Charles Bloom           www.cbloom.com

Re: [Algorithms] VIPM and UV texturing

[Mark W. <mwa...@to...>]

Thanks one and all for your contributions, things are infinitely clearer now
...

Mark

----- Original Message -----
From: "Charles Bloom" <cb...@cb...>
To: <gda...@li...>
Sent: Thursday, August 10, 2000 4:15 AM
Subject: Re: [Algorithms] VIPM and UV texturing


>
> Hi Jeff,
>
> really, you should be including UV's and RGB's and Normals as
> part of the quadric error metric, so that this kind of thing
> should be detected automagically, and should be put late in
> the collapse list by the system.  I've found that if you
> use a proper (eg. comprehensive and robust) error metric,
> then almost zero artist intervention is necessary.  In fact,
> I find that the system is generally much better at ordering
> collapses than artists are.  Of course, there are exceptions,
> which usually occur because of the fact that I'm not actually
> looking in the texture bits; eg. changing the uv's slightly
> in a region of the texture which is very high frequency
> produces much more visual error than if you change the uv's in
> a very low frequency region of the texture.  To handle this
> correctly, you do need some sort of artist cue, as you propose.
> I like Tom's method of reducing to a specific mesh.
>
> At 10:06 AM 8/9/2000 -0700, you wrote:
> >Now the problem as you would guess is you have the face with coordinates
> like (1,0) -----  (0,0) ---- (1,0).  Obviously more granular then that.
> There are no texture coordinate discontinuities so the algorithm says it
is
> ok.  The surface of the face is roughly flat so the internal vertex and
> edges are good candidates for collapse.  However, you then get the nice
> situation of  (1,0) ------ (1,0).  Doesn't look so hot.  I have the
artists
> tag reflected seam vertices as uncollapsable until very late in the
order.>
> --------------------------------------
> Charles Bloom           www.cbloom.com
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

[Algorithms] Texturing Terrain

[Pai-Hung C. <pa...@ac...>]

Hi,

I generate a huge, complicated terrain mesh from a heightmap.  How can I
generate a realistic texture bitmap and corresponding UV coords for the
mesh?  I was directed to search the archive with some subject titles.  But
the archive search seems not to work properly and I always get nothing in
return.  Could someone give some help on this?

Thanks in advance,

Pai-Hung Chen

RE: [Algorithms] VIPM and UV texturing

[Sim D. <SDi...@nv...>]

This mirroring is a huge problem when doing per-pixel lighting with DOT3
bump mapping, because texels don't have a facing.  In some cases, you can
detect backwards facing textures and just flip the local coordinate system,
but not in the case you mention below.

-----Original Message-----
From: Jeff Lander [mailto:je...@di...]
Sent: Wednesday, August 09, 2000 10:06 AM
To: gda...@li...
Subject: Re: [Algorithms] VIPM and UV texturing


Hi all.  New to this discussion but I have recently had a couple of projects
where this issue has been very important.

The issue you bring up about texture coordinates and any sort of mesh LOD
system is critical.  That is why I insist that the LOD tools allow artists
to hand designate edges that will not collapse.  Any algorithmic method you
try and find will fail in certain cases.  The algorithms handle texture
projections like sphere and cylinder wraps pretty well but arbitrary UV
texturing is a real problem.

One particular problem I will share that comes up often is when texturing
characters.  My system automatically will preserve vertices that have
texture coordinate discontinuities.  However, artists will often model a
character with only half of the texture (particularly in the face) then just
reflect the texture coords to save texture space.

Now the problem as you would guess is you have the face with coordinates
like (1,0) -----  (0,0) ---- (1,0).  Obviously more granular then that.
There are no texture coordinate discontinuities so the algorithm says it is
ok.  The surface of the face is roughly flat so the internal vertex and
edges are good candidates for collapse.  However, you then get the nice
situation of  (1,0) ------ (1,0).  Doesn't look so hot.  I have the artists
tag reflected seam vertices as uncollapsable until very late in the order.

Let me paraphrase you by saying the algorithms are most efficient when
working on trivially textured objects.  Anything else requires good artist
tools and some TLC.

-Jeff

At 06:44 PM 8/9/2000 +1000, you wrote:
> >     Well, I think the thing you missed is that VIPM is mainly aimed
>towards
> > meshes that are more like skinned meshes (ie, all points only have a
>single
> > vertex associated with them - Hence each set of adjacent triangles must
be
> > specifiable as a strip). I like to call these sort of meshes, highly
> > connected meshes (HCM), for the simple purpose that with appearance to
the
> > renderer, they share vertices, and are therefore connected.
>
>I cite different vertices because the actual UV coords are different
>(eg. a vertex is NOT just gemoetry, as in the D3D definition)
>
>Doesn't anyone use large meshes that are textured using multiple textures
>with VIPM,
>in that you would want the mesh as a whole to reduce, not the similarly
>textured "pieces" ?
>
>What I'm tending to now assume is that most users of VIPM are using it on
>trivially textured
>objects ... would this be a fair assumption, or once again have I missed
>something ?


_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

RE: [Algorithms] VIPM and UV texturing

[Tom F. <to...@mu...>]

This is also solved if you start with a low-poly mesh from the artists,
tesselate and displace up to a high-poly mesh, then VIPM down again, but
preserving the original edges. Because the tesselation only uses linear
interpolation for non-geometry attributes, you don't have to deal with nasty
cases like this. Fortunately, coz they are a real pain.

http://www.muckyfoot.com/downloads/tom.shtml

Tom Forsyth - Muckyfoot bloke.
Whizzing and pasting and pooting through the day.

> -----Original Message-----
> From: Jeff Lander [mailto:je...@di...]
> Sent: 09 August 2000 18:06
> To: gda...@li...
> Subject: Re: [Algorithms] VIPM and UV texturing
> 
> 
> Hi all.  New to this discussion but I have recently had a 
> couple of projects where this issue has been very important.
> 
> The issue you bring up about texture coordinates and any sort 
> of mesh LOD system is critical.  That is why I insist that 
> the LOD tools allow artists to hand designate edges that will 
> not collapse.  Any algorithmic method you try and find will 
> fail in certain cases.  The algorithms handle texture 
> projections like sphere and cylinder wraps pretty well but 
> arbitrary UV texturing is a real problem.
> 
> One particular problem I will share that comes up often is 
> when texturing characters.  My system automatically will 
> preserve vertices that have texture coordinate 
> discontinuities.  However, artists will often model a 
> character with only half of the texture (particularly in the 
> face) then just reflect the texture coords to save texture space.
> 
> Now the problem as you would guess is you have the face with 
> coordinates like (1,0) -----  (0,0) ---- (1,0).  Obviously 
> more granular then that. There are no texture coordinate 
> discontinuities so the algorithm says it is ok.  The surface 
> of the face is roughly flat so the internal vertex and edges 
> are good candidates for collapse.  However, you then get the 
> nice situation of  (1,0) ------ (1,0).  Doesn't look so hot.  
> I have the artists tag reflected seam vertices as 
> uncollapsable until very late in the order.
> 
> Let me paraphrase you by saying the algorithms are most 
> efficient when working on trivially textured objects.  
> Anything else requires good artist tools and some TLC.
> 
> -Jeff

Re: [Algorithms] VIPM and UV texturing

[Mark W. <mwa...@to...>]

Now this sounds like a cool idea :)

Mark

----- Original Message -----
From: "Tom Forsyth" <to...@mu...>
To: <gda...@li...>
Sent: Thursday, August 10, 2000 3:32 AM
Subject: RE: [Algorithms] VIPM and UV texturing


> This is also solved if you start with a low-poly mesh from the artists,
> tesselate and displace up to a high-poly mesh, then VIPM down again, but
> preserving the original edges. Because the tesselation only uses linear
> interpolation for non-geometry attributes, you don't have to deal with
nasty
> cases like this. Fortunately, coz they are a real pain.
>
> http://www.muckyfoot.com/downloads/tom.shtml
>
> Tom Forsyth - Muckyfoot bloke.
> Whizzing and pasting and pooting through the day.
>
> > -----Original Message-----
> > From: Jeff Lander [mailto:je...@di...]
> > Sent: 09 August 2000 18:06
> > To: gda...@li...
> > Subject: Re: [Algorithms] VIPM and UV texturing
> >
> >
> > Hi all.  New to this discussion but I have recently had a
> > couple of projects where this issue has been very important.
> >
> > The issue you bring up about texture coordinates and any sort
> > of mesh LOD system is critical.  That is why I insist that
> > the LOD tools allow artists to hand designate edges that will
> > not collapse.  Any algorithmic method you try and find will
> > fail in certain cases.  The algorithms handle texture
> > projections like sphere and cylinder wraps pretty well but
> > arbitrary UV texturing is a real problem.
> >
> > One particular problem I will share that comes up often is
> > when texturing characters.  My system automatically will
> > preserve vertices that have texture coordinate
> > discontinuities.  However, artists will often model a
> > character with only half of the texture (particularly in the
> > face) then just reflect the texture coords to save texture space.
> >
> > Now the problem as you would guess is you have the face with
> > coordinates like (1,0) -----  (0,0) ---- (1,0).  Obviously
> > more granular then that. There are no texture coordinate
> > discontinuities so the algorithm says it is ok.  The surface
> > of the face is roughly flat so the internal vertex and edges
> > are good candidates for collapse.  However, you then get the
> > nice situation of  (1,0) ------ (1,0).  Doesn't look so hot.
> > I have the artists tag reflected seam vertices as
> > uncollapsable until very late in the order.
> >
> > Let me paraphrase you by saying the algorithms are most
> > efficient when working on trivially textured objects.
> > Anything else requires good artist tools and some TLC.
> >
> > -Jeff
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

RE: [Algorithms] VIPM and UV texturing

[Tony C. <to...@mi...>]

>One particular problem I will share that comes up often is when texturing
characters.  My >system automatically will preserve vertices that have
texture coordinate discontinuities.  >However, artists will often model a
character with only half of the texture (particularly >in the face) then
just reflect the texture coords to save texture space.
>
>Now the problem as you would guess is you have the face with coordinates
like (1,0) -----  >(0,0) ---- (1,0).  Obviously more granular then that.
There are no texture coordinate 
>discontinuities so the algorithm says it is ok.  The surface of the face is
roughly flat 
>so the internal vertex and edges are good candidates for collapse.
However, you then get >the nice situation of  (1,0) ------ (1,0).  Doesn't
look so hot.  I have the artists tag 
>reflected seam vertices as uncollapsable until very late in the order.

Can you not algorithmically detect this situation as well? Compute the
tangent-normal basis for the polygon, and look at the derivative of the
texture coordinates w.r.t the tangent vector - if this changes sign you have
a seam.

More work, I grant you, and I admit not as flexible as having a tool that
lets the artists do the markup, but still possible.

Tony Cox - DirectX Luminary
Windows Gaming Developer Relations Group
http://msdn.microsoft.com/directx 

RE: [Algorithms] VIPM and UV texturing

[Jeff L. <je...@di...>]

I started adding some code to the metric to try and detect and weight the case but never got it to work well with all the other settings in the metric.  Having the artistic control was just more flexible.  We are doing a new rev on the tool and I have someone else working on it so I will have him revisit that.

There are a lot of aspects to the decimation that I am looking at for the next rev.  Our current metric doesn't take into count the changes brought by animation.  It uses the rest pose which as you know artists can build in strange ways to make weighting easier.  I don't know if anyone else has looked at this.

Also, the current algorithm leads to a bit of hollowness on the low end of the scale.  It does decent at preserving the base shape but things like the legs get a bit thin.  I am thinking about adding in some volume preservation (like Hoppe had in his recent paper on metrics) or trying some image-space stuff from orthogonal angles to address this.

-Jeff

At 05:58 AM 8/10/2000 -0700, you wrote:
>However, you then get >the nice situation of  (1,0) ------ (1,0).  Doesn't
>look so hot.  I have the artists tag 
> >reflected seam vertices as uncollapsable until very late in the order.
>
>Can you not algorithmically detect this situation as well? Compute the
>tangent-normal basis for the polygon, and look at the derivative of the
>texture coordinates w.r.t the tangent vector - if this changes sign you have
>a seam.
>
>More work, I grant you, and I admit not as flexible as having a tool that
>lets the artists do the markup, but still possible.
>
>Tony Cox - DirectX Luminary
>Windows Gaming Developer Relations Group
>http://msdn.microsoft.com/directx 
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

RE: [Algorithms] VIPM and UV texturing

[Tom F. <to...@mu...>]

Hoppe's version of the QEM metric that deals with attributes does help with
these sorts of things, and may well be just what the doctors ordered. It
certainly deals with similar problems with vertex colours, as demonstrated
very convincingly by the "baboon" picture done entirely with untextured
vertex-coloured triangles.

For animation, I have in my brain an idea about having several typical poses
for the character in memory while calculating the QEMs, and using the metric
that gives you the _greatest_ error of all the poses when deciding which
collapse is best to do. That way things like elbows and knees won't vanish
far too early, but the artists don't need any specialist knowledge, or need
to worry about default poses too much.

Tom Forsyth - Muckyfoot bloke.
Whizzing and pasting and pooting through the day.

> -----Original Message-----
> From: Jeff Lander [mailto:je...@di...]
> Sent: 10 August 2000 16:09
> To: gda...@li...
> Subject: RE: [Algorithms] VIPM and UV texturing
> 
> 
> I started adding some code to the metric to try and detect 
> and weight the case but never got it to work well with all 
> the other settings in the metric.  Having the artistic 
> control was just more flexible.  We are doing a new rev on 
> the tool and I have someone else working on it so I will have 
> him revisit that.
> 
> There are a lot of aspects to the decimation that I am 
> looking at for the next rev.  Our current metric doesn't take 
> into count the changes brought by animation.  It uses the 
> rest pose which as you know artists can build in strange ways 
> to make weighting easier.  I don't know if anyone else has 
> looked at this.
> 
> Also, the current algorithm leads to a bit of hollowness on 
> the low end of the scale.  It does decent at preserving the 
> base shape but things like the legs get a bit thin.  I am 
> thinking about adding in some volume preservation (like Hoppe 
> had in his recent paper on metrics) or trying some 
> image-space stuff from orthogonal angles to address this.
> 
> -Jeff
> 
> At 05:58 AM 8/10/2000 -0700, you wrote:
> >However, you then get >the nice situation of  (1,0) ------ 
> (1,0).  Doesn't
> >look so hot.  I have the artists tag 
> > >reflected seam vertices as uncollapsable until very late 
> in the order.
> >
> >Can you not algorithmically detect this situation as well? 
> Compute the
> >tangent-normal basis for the polygon, and look at the 
> derivative of the
> >texture coordinates w.r.t the tangent vector - if this 
> changes sign you have
> >a seam.
> >
> >More work, I grant you, and I admit not as flexible as 
> having a tool that
> >lets the artists do the markup, but still possible.
> >
> >Tony Cox - DirectX Luminary
> >Windows Gaming Developer Relations Group
> >http://msdn.microsoft.com/directx 
> >
> >_______________________________________________
> >GDAlgorithms-list mailing list
> >GDA...@li...
> >http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

Re: [Algorithms] VIPM and UV texturing

[Mark W. <mwa...@to...>]

Thanks for the response:

> Er... with the usual type of VIPM, you don't generate texture coords, or
> indeed any new vertices,  at all. All you do is throw one point away and
> collapse the edge onto the other one.
>
> There are variants where you generate some sort of new "average" midpoint,
> but (a) the quality improvement isn't very large and (b) it is quite a bit
> less efficient to render, because for a given LoD, you have vertices that
> are used by lower LoDs, but not the current one, which causes problems.

But if I have the scenario where one triangle is mapped with UVs : u1,v1,
u2,v2, u3,v3
and an adjacent triangle mapped with u6,v6, u7,v7, u8,v8; the adjacency is
along the edge
of (u1,v1 & u6,v6) - (u3,v3 & u8,v8), where u1,v1 and u6,v6 actual vertices
are coincident, as is the case with u3,v3 and u8,v8.

What happens when I drop out the edge ?

Wouldn't the texture coords will be interpolated from u2,v2 to u7,v7 which
may be totally screwed ?  I must be missing some fundamental stuff here ...

> A related question is how to calculate texture coords (and other
attributes)
> when creating subdiv surfaces. I just use linear - seems to work OK with
my
> data, but others prefer to use other methods, such as use the subdiv
surface
> method, but on the attributes data. This gives excellent results BUT it is
> possibly covered by a sneaky Pixar patent. It's still unclear exactly what
> this patent covers (as with all patents, it's extremely vague), but there
> may be some prior art that we can hide behind :-) In any case, simpler
> methods such as Loop subdivision is often perfectly acceptable for
> attributes, since perfect C1/G1 is not actually needed in most cases.

I've yet to look into subdiv surfs yet, but it'll no doubt arise ;)

Thanks again,

Mark

Re: [Algorithms] VIPM and UV texturing

[Conor S. <cs...@tp...>]

> But if I have the scenario where one triangle is mapped with UVs : u1,v1,
> u2,v2, u3,v3
> and an adjacent triangle mapped with u6,v6, u7,v7, u8,v8; the adjacency is
> along the edge
> of (u1,v1 & u6,v6) - (u3,v3 & u8,v8), where u1,v1 and u6,v6 actual
vertices
> are coincident, as is the case with u3,v3 and u8,v8.
>
> What happens when I drop out the edge ?
>
> Wouldn't the texture coords will be interpolated from u2,v2 to u7,v7 which
> may be totally screwed ?  I must be missing some fundamental stuff here
...
>

    Well, I think the thing you missed is that VIPM is mainly aimed towards
meshes that are more like skinned meshes (ie, all points only have a single
vertex associated with them - Hence each set of adjacent triangles must be
specifiable as a strip). I like to call these sort of meshes, highly
connected meshes (HCM), for the simple purpose that with appearance to the
renderer, they share vertices, and are therefore connected.

    I've moved towards using HCM to describe more things in my engine worlds
now (although, I need to get some art together to show off the benefit - Its
not going to work as well with the incredibly simple cubes etc I  turn out
by hand). This should provide higher performance on complex worlds (due to
more vertex coherancy) and allow more LoD.

Also, new today, I actually finally updated my column, on VIPM of all things
:) http://www.flipcode.com/dp/issue04.shtml

Conor Stokes

Re: [Algorithms] VIPM and UV texturing

[Sebastian T. <s....@gm...>]

>     Well, I think the thing you missed is that VIPM is mainly aimed
towards
> meshes that are more like skinned meshes (ie, all points only have a
single
> vertex associated with them

This is very limiting. VIPM can handle vertex attributes very well.

Sebastian

Re: [Algorithms] VIPM and UV texturing

[Sebastian T. <s....@gm...>]

> But if I have the scenario where one triangle is mapped with UVs : u1,v1,
> u2,v2, u3,v3
> and an adjacent triangle mapped with u6,v6, u7,v7, u8,v8; the adjacency is
> along the edge
> of (u1,v1 & u6,v6) - (u3,v3 & u8,v8), where u1,v1 and u6,v6 actual
vertices
> are coincident, as is the case with u3,v3 and u8,v8.
>
> What happens when I drop out the edge ?

I think of edge collapses as edges that shrink into one point.

>
> Wouldn't the texture coords will be interpolated from u2,v2 to u7,v7 which
> may be totally screwed ?  I must be missing some fundamental stuff here
...

You don't interpolate anything. Your vertex data keeps the same for any of
the meshes. The only thing you change is the index list.

Sebastian

Re: [Algorithms] VIPM and UV texturing

[Mark W. <mwa...@to...>]

>     Well, I think the thing you missed is that VIPM is mainly aimed
towards
> meshes that are more like skinned meshes (ie, all points only have a
single
> vertex associated with them - Hence each set of adjacent triangles must be
> specifiable as a strip). I like to call these sort of meshes, highly
> connected meshes (HCM), for the simple purpose that with appearance to the
> renderer, they share vertices, and are therefore connected.

I cite different vertices because the actual UV coords are different
(eg. a vertex is NOT just gemoetry, as in the D3D definition)

Doesn't anyone use large meshes that are textured using multiple textures
with VIPM,
in that you would want the mesh as a whole to reduce, not the similarly
textured "pieces" ?

What I'm tending to now assume is that most users of VIPM are using it on
trivially textured
objects ... would this be a fair assumption, or once again have I missed
something ?

>     I've moved towards using HCM to describe more things in my engine
worlds
> now (although, I need to get some art together to show off the benefit -
Its
> not going to work as well with the incredibly simple cubes etc I  turn out
> by hand). This should provide higher performance on complex worlds (due to
> more vertex coherancy) and allow more LoD.
>
> Also, new today, I actually finally updated my column, on VIPM of all
things
> :) http://www.flipcode.com/dp/issue04.shtml

Cool, saw this, read it, but it didn't address my question :)

Thanks for the feedback,

Mark

Re: [Algorithms] VIPM and UV texturing

[Pierre T. <p.t...@wa...>]

> Doesn't anyone use large meshes that are textured using multiple textures
> with VIPM,
> in that you would want the mesh as a whole to reduce, not the similarly
> textured "pieces" ?
>
> What I'm tending to now assume is that most users of VIPM are using it on
> trivially textured
> objects ... would this be a fair assumption, or once again have I missed
> something ?

There are two obvious ways:
1) don't collapse edges along texture seams. (or even along "smoothing
groups seams"). This is the easiest solution, and it only implies a minimal
number of vertices for the minimal LOD - after which you can't collapse
anything anymore.
2) when you collapse a texture-seam edge, collapse the other edge as well.
By "other edge" I mean, of course, the counterpart edge in the opposite
triangle using another texture.

I don't know what is the "official" method, I don't play in the gamedev
field anymore. But I did both of them, and 1) is often well enough. 2) can
be very tedious to implement, it all depends on your data structures,
architecture, and how you deal with meshes made of multiple textures &
smoothing groups in the first place.

Pierre

Re: [Algorithms] VIPM and UV texturing

[Conor S. <cs...@tp...>]

> >     Well, I think the thing you missed is that VIPM is mainly aimed
> towards
> > meshes that are more like skinned meshes (ie, all points only have a
> single
> > vertex associated with them - Hence each set of adjacent triangles must
be
> > specifiable as a strip). I like to call these sort of meshes, highly
> > connected meshes (HCM), for the simple purpose that with appearance to
the
> > renderer, they share vertices, and are therefore connected.
>
> I cite different vertices because the actual UV coords are different
> (eg. a vertex is NOT just gemoetry, as in the D3D definition)

I agree actually :) A point is the geometry, and a vertex is the other
associated bits.
I was just saying that these meshes are not good candidates for VIPM.

>
> Doesn't anyone use large meshes that are textured using multiple textures
> with VIPM,
> in that you would want the mesh as a whole to reduce, not the similarly
> textured "pieces" ?

    You could probably do that - But it would be more work. I think it would
involve making the edge collapse storage more generic. An edge collapse
would have to move more than one vertice, and know in each collapsed
instance which vertice needs to replace it. This should work - But, it would
take more in implementation, and bloat the size a little. It may just be
easiest to force edges between non similarly textured primitives to remain
uncollapsed.

>
> What I'm tending to now assume is that most users of VIPM are using it on
> trivially textured
> objects ... would this be a fair assumption, or once again have I missed
> something ?

Thats a fair assumption. Dead on the money in most cases - And even in the
cases they are not, they tend to force edges adjacent to two objects to stay
uncollapsed. (ie, the joint between a model with a seperate texture for
legs/torso).

> Cool, saw this, read it, but it didn't address my question :)

Well, it was more just a coincidence. :)

>
> Thanks for the feedback,

Anytime :)

Conor Stokes

Re: [Algorithms] VIPM and UV texturing

[Jeff L. <je...@di...>]

Hi all.  New to this discussion but I have recently had a couple of projects where this issue has been very important.

The issue you bring up about texture coordinates and any sort of mesh LOD system is critical.  That is why I insist that the LOD tools allow artists to hand designate edges that will not collapse.  Any algorithmic method you try and find will fail in certain cases.  The algorithms handle texture projections like sphere and cylinder wraps pretty well but arbitrary UV texturing is a real problem.

One particular problem I will share that comes up often is when texturing characters.  My system automatically will preserve vertices that have texture coordinate discontinuities.  However, artists will often model a character with only half of the texture (particularly in the face) then just reflect the texture coords to save texture space.

Now the problem as you would guess is you have the face with coordinates like (1,0) -----  (0,0) ---- (1,0).  Obviously more granular then that. There are no texture coordinate discontinuities so the algorithm says it is ok.  The surface of the face is roughly flat so the internal vertex and edges are good candidates for collapse.  However, you then get the nice situation of  (1,0) ------ (1,0).  Doesn't look so hot.  I have the artists tag reflected seam vertices as uncollapsable until very late in the order.

Let me paraphrase you by saying the algorithms are most efficient when working on trivially textured objects.  Anything else requires good artist tools and some TLC.

-Jeff

At 06:44 PM 8/9/2000 +1000, you wrote:
> >     Well, I think the thing you missed is that VIPM is mainly aimed
>towards
> > meshes that are more like skinned meshes (ie, all points only have a
>single
> > vertex associated with them - Hence each set of adjacent triangles must be
> > specifiable as a strip). I like to call these sort of meshes, highly
> > connected meshes (HCM), for the simple purpose that with appearance to the
> > renderer, they share vertices, and are therefore connected.
>
>I cite different vertices because the actual UV coords are different
>(eg. a vertex is NOT just gemoetry, as in the D3D definition)
>
>Doesn't anyone use large meshes that are textured using multiple textures
>with VIPM,
>in that you would want the mesh as a whole to reduce, not the similarly
>textured "pieces" ?
>
>What I'm tending to now assume is that most users of VIPM are using it on
>trivially textured
>objects ... would this be a fair assumption, or once again have I missed
>something ?

Re: [Algorithms] VIPM and UV texturing

[Charles B. <cb...@cb...>]

Let me just point out how a metric can detect these case automatically.
The basic error metric is something like "deviation from linear interpolation".
Hence, if you have a linear case of (a,b,c) and you're thinking of removing b,
then the error is (b - (a+c)/2).  This error is related to the second
derivative of whatever parameter you're measuring (eg. the curvature).  Hence,
if you have a triangle which is textured normally but highly tesselated, you
will get zero error, because even though the UV's are different, they differ in
a linear way, eg. there's no curvature in UV space.

However, where you have a reflection, the curvature is quite large.  For example,
if u = abs(x), then u'' = 0 for x != 0, and u'' = -1 right at x=0.  Thus, any
collapse away from x=0 will be free, and any collapse across x=0 will be highly
penalized.

Of course you're right that artist intervention will always be more precise (if
you have good artists!!), I just wanted everyone to be sure and understand that
a good collapse error metric is very important, and will give you much higher
quality meshes, by leaving the discontinuities in place where they're needed.

At 10:01 AM 8/9/00 -0700, you wrote:
>Now the problem as you would guess is you have the face with coordinates like (1,0) -----  (0,0) ---- (1,0).  Obviously more granular then that. There are no texture coordinate discontinuities so the algorithm says it is ok.  The surface of the face is roughly flat so the internal vertex and edges are good candidates for collapse.  However, you then get the nice situation of  (1,0) ------ (1,0).  Doesn't look so hot.  I have the artists tag reflected seam vertices as uncollapsable until very late in the order.

-------------------------------------------------------
Charles Bloom    cb...@cb...    http://www.cbloom.com