gdalgorithms-list

[Algorithms] Some N-Patch questions...

[Peter W. <Pet...@vi...>]

I've been following the discussion on N-Patches, and whilst I was at home
this weekend, I had a few ideas for modifications, and I thought I'd throw
them open for discussion.

I use the same method as ATI to calculate the 9 control points of the bezier
lines along each edge of each tri, except I change their 'divide projection
of edge onto plane by 3' into a multiplication by an arbitrary tangent scale
factor, which works best in the range 0 to 0.5.(*1)

We now have 9 control points effectively forming 3, 3D bezier lines along
each edge. I then use the bezier curve convex hull subdivision formula from
Watt&Watt, 3.4.1, page 81, to calculate the midpoint of each bezier
curve.(*2)

I use each of these midpoints as a new vertex to split the original triangle
into 4. To calculate the normals at each new vertex, I interpolate halfway
between the two adjacent original normals, eg
MidNorm=Cos(45)*Norm0+Sin(45)*Norm1.

I then keep doing this recursively on each of the four triangles, either to
a fixed level or until some heuristic is satisfied.

I've tried a test implementation, and it seems to give quite pretty results
on the single tetrahedron I've tried. It also tends towards a surface with
G1 continuity, I think, which ATI's patches don't.

One other nice thing about this scheme is that if information is only used
from a single edge in the 'should we split this edge' heuristic, you
automatically get no cracking since no per-face info is involved.

Thoughts? Does it make sense? I'm not on the DirectX beta, so I haven't seen
any discussion of N-patches apart from this list, and I'm just getting to
grips with subdivision surfaces, so if anyone can point me in the direction
of prior work on schemes like this, I'd be grateful.

Peter Warden

(*1) The tangent scale works a bit like a weight, a small value gives a
bevelled appearance, and it tends towards blobbyness as it increases. Out of
the range 0-0.5, you get some very weird and wonderful stuff!

(*2) This formula only involves additions, multiplies and divisions by 2, so
it's quite efficient. I always wanted to use it for something, since it is
so elegant, but those darn floating point units always made it faster to
calculate the full formula than use recursion on the machines I've
implemented beziers on.

RE: [Algorithms] Some N-Patch questions...

[Akbar A. <sye...@ea...>]

welcome to the world of subdivision.

there was a zip file somewhere on the web.
the name of the actual file was sig99notes.pdf
there was a big presention done and they just wrapped all the "mini"
presenations into one big file.
_very_ handy.
the "booklet" goes from "begginer" material all the way to a closing
thoughts on surface subdivision with geri (pixars' model, the short can be
found in Bugs' Life). For some weird reason the file takes a long time to
"draw" the models. i never knew that adobe acrobat could load model data?
you will understand if you see the paper.

the lectures are
Denis Zorin
Tony DeRose (pixar)
Leif Kobbelt
Peter Schroder
Jos Stam
Joe Warren		http://www.cs.rice.edu/~jwarren/ (there should be a link at his
site. he has a lot of mathamteical represention material)

eric, you should add this to your site if it's not up there already :-)

peace.
akbar A.

"We want technology for the sake of the story, not for its own sake. When
you look back, say 10 years from now, current technology will seem quaint"
Pixars' Edwin Catmull.


-----Original Message-----
From: gda...@li...
[mailto:gda...@li...]On Behalf Of Peter
Warden
Sent: Sunday, August 06, 2000 12:13 PM
To: gda...@li...
Subject: [Algorithms] Some N-Patch questions...


I've been following the discussion on N-Patches, and whilst I was at home
this weekend, I had a few ideas for modifications, and I thought I'd throw
them open for discussion.

I use the same method as ATI to calculate the 9 control points of the bezier
lines along each edge of each tri, except I change their 'divide projection
of edge onto plane by 3' into a multiplication by an arbitrary tangent scale
factor, which works best in the range 0 to 0.5.(*1)

We now have 9 control points effectively forming 3, 3D bezier lines along
each edge. I then use the bezier curve convex hull subdivision formula from
Watt&Watt, 3.4.1, page 81, to calculate the midpoint of each bezier
curve.(*2)

I use each of these midpoints as a new vertex to split the original triangle
into 4. To calculate the normals at each new vertex, I interpolate halfway
between the two adjacent original normals, eg
MidNorm=Cos(45)*Norm0+Sin(45)*Norm1.

I then keep doing this recursively on each of the four triangles, either to
a fixed level or until some heuristic is satisfied.

I've tried a test implementation, and it seems to give quite pretty results
on the single tetrahedron I've tried. It also tends towards a surface with
G1 continuity, I think, which ATI's patches don't.

One other nice thing about this scheme is that if information is only used
from a single edge in the 'should we split this edge' heuristic, you
automatically get no cracking since no per-face info is involved.

Thoughts? Does it make sense? I'm not on the DirectX beta, so I haven't seen
any discussion of N-patches apart from this list, and I'm just getting to
grips with subdivision surfaces, so if anyone can point me in the direction
of prior work on schemes like this, I'd be grateful.

Peter Warden

(*1) The tangent scale works a bit like a weight, a small value gives a
bevelled appearance, and it tends towards blobbyness as it increases. Out of
the range 0-0.5, you get some very weird and wonderful stuff!

(*2) This formula only involves additions, multiplies and divisions by 2, so
it's quite efficient. I always wanted to use it for something, since it is
so elegant, but those darn floating point units always made it faster to
calculate the full formula than use recursion on the machines I've
implemented beziers on.


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

[Algorithms] Info about quadtree

[JB <ma...@sd...>]

Hi
I'm looking dor infos about quadtrees. It doesn't seem to be too complex,
but It would be fine if I could find some example... 
Thx
Mandor 

ma...@sd...
SDF Public Access UNIX System - http://sdf.lonestar.org

RE: [Algorithms] Info about quadtree

[Odin J. <od...@it...>]

There's a OpenGL Quadtree engine for download on www.flipcode.com (Or was it
www.gamedev.net ?)


Med venlig hilsen/best regards :

Odin Jensen
R&D Programmer
ITE ApS, Denmark
Work : od...@it...
Home : od...@nu...

(The point of view presented here is solely my own
 and DOES NOT represent that of ITE ApS)


-----Original Message-----
From: gda...@li...
[mailto:gda...@li...]On Behalf Of JB
Sent: 7. august 2000 09:06
To: gda...@li...
Subject: [Algorithms] Info about quadtree


Hi
I'm looking dor infos about quadtrees. It doesn't seem to be too complex,
but It would be fine if I could find some example...
Thx
Mandor

ma...@sd...
SDF Public Access UNIX System - http://sdf.lonestar.org



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

[Algorithms] VIPM and UV texturing

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

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

[Angel P. <ju...@bi...>]

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

This paper by Michael Garland and Paul Heckbert:
"Simplifying Surfaces with Color and Texture using Quadric Error Metrics"
explains an extention to the standart quadratic error metrics alghotithm for
meshes with apearance attributes (texture coordinates, color, normals... )

If you are not familiar with QEM - read this paper first:
"Surface Simplification Using Quadric Error Metrics"

Both papers are avaiable at
http://graphics.cs.uiuc.edu/~garland/research/quadrics.html

A more efficient implementation was developped by Hugues Hoppe:
"New quadric metric for simplifying meshes with appearance attributes"
This paper can be found at
http://www.research.microsoft.com/~hoppe/

Re: [Algorithms] VIPM and UV texturing

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

Angel,

Thanks for the references, I will be sure to check them out.

Mark

----- Original Message -----
From: "Angel Popov" <ju...@bi...>
To: <gda...@li...>
Sent: Tuesday, August 08, 2000 9:11 PM
Subject: Re: [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.
>
> This paper by Michael Garland and Paul Heckbert:
> "Simplifying Surfaces with Color and Texture using Quadric Error Metrics"
> explains an extention to the standart quadratic error metrics alghotithm
for
> meshes with apearance attributes (texture coordinates, color, normals... )
>
> If you are not familiar with QEM - read this paper first:
> "Surface Simplification Using Quadric Error Metrics"
>
> Both papers are avaiable at
> http://graphics.cs.uiuc.edu/~garland/research/quadrics.html
>
> A more efficient implementation was developped by Hugues Hoppe:
> "New quadric metric for simplifying meshes with appearance attributes"
> This paper can be found at
> http://www.research.microsoft.com/~hoppe/
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] VIPM and UV texturing

[Timur D. <ti...@3d...>]

Check Stan Melax feedback page about handling tex coords.
http://www.cs.ualberta.ca/~melax/polychop/feedback/

_______________________
 Timur Davidenko.
 3Dion Inc. (www.3dion.com)
 e-mail: ti...@3d...


----- Original Message -----
From: "Mark Wayland" <mwa...@to...>
To: <gda...@li...>
Sent: Tuesday, August 08, 2000 1:58 AM
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
>
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

RE: [Algorithms] Some N-Patch questions...

[Gil C. <g.c...@ca...>]

At 03:13 AM 8/7/00 -0500, you wrote:
>welcome to the world of subdivision.
>
>there was a zip file somewhere on the web.
>the name of the actual file was sig99notes.pdf
>there was a big presention done and they just wrapped all the "mini"
>presenations into one big file.

http://www.multires.caltech.edu/pubs/sig99notes.pdf

There's a *heap* of subdivision papers at the more general 
http://www.multires.caltech.edu/pubs page, including this year's SIGGRAPH 
notes...

Gil
---------------------------------------------------------------------
3D Graphics Programmer
CSIRO Minesite Imaging Group
Pinjarra Hills, QLD, AUSTRALIA
http://www.cat.csiro.au/automation/projects/SurMap.htm

"Experience is something you don't get until just after you need it"
---------------------------------------------------------------------

[Algorithms] View-Depend vs. View-Independent LOD

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

Hi,

I've heard that there are two kinds of LOD: view-dependent and
view-independent.  Could somebody briefly explain what the essential
difference between the two?

Thanks in advance,

Pai-Hung Chen

Re: [Algorithms] View-Depend vs. View-Independent LOD

[Stephen J B. <sj...@li...>]

On Wed, 9 Aug 2000, Pai-Hung Chen wrote:

> I've heard that there are two kinds of LOD: view-dependent and
> view-independent.  Could somebody briefly explain what the essential
> difference between the two?
 
* View-independent depends only on range to the object.

* View-dependent also depends on the orientation of the object
  with respect to the eye.

Hence, view-independent is generally easier to compute - but
can't reduce the polygon count quite so agressively as
view-dependent LOD can.

Steve Baker                      (817)619-2657 (Vox/Vox-Mail)
L3Com/Link Simulation & Training (817)619-2466 (Fax)
Work: sj...@li...           http://www.link.com
Home: sjb...@ai...       http://web2.airmail.net/sjbaker1

[Algorithms] Up Vector in Projection Matrix

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

Hi,

I am manipulating projection matrix in my D3D program so that the player can
lift up/down his head to view the world.  I do modify the viewing-direction
component of the projection matrix but always leave the "up-direction"
component as (0, 1, 0).  I think this should not work theoretically (at
least introduce some weird effect).  However, it DOES work even I don't
modify the "up-direction" component (such that it is perpendicular to the
"viewing-direction").  I do know different up-vector, when setup reasonably,
can have different effect with the same direction-vector.  But what if
up-vector is setup unreasonably (impossible to happen in the real world)?
Could someone give me some idea?

Thanks in advance,

Pai-Hung Chen

Re: [Algorithms] Up Vector in Projection Matrix

[Stephen J B. <sj...@li...>]

On Wed, 9 Aug 2000, Pai-Hung Chen wrote:

> I am manipulating projection matrix in my D3D program so that the player can
> lift up/down his head to view the world.  I do modify the viewing-direction
> component of the projection matrix but always leave the "up-direction"
> component as (0, 1, 0).  I think this should not work theoretically (at
> least introduce some weird effect).  However, it DOES work even I don't
> modify the "up-direction" component (such that it is perpendicular to the
> "viewing-direction").

I'm no D3D expert - but I'll presume this is similar to the OpenGL 'glLookAt'
stuff.

When you specify a point or direction to "look at",  you have only specified
two of the degrees of freedom of the system.  That object could be in the
middle of the screen - either upside-down - or right way up - or at any
'roll' angle in between.

The 'up' vector only has to be enough to resolve that issue - and only one
of its degrees of freedom is needed.  Hence, there are a wide variety of
vectors that will do the job.  The only constraint is that the up vector
and the 'look direction' are not parallel.

Hence, so long as your character can't look absolutely vertically upwards
or absolutely vertically downwards, an 'up' vector of (0,1,0) will do fine.

Steve Baker                      (817)619-2657 (Vox/Vox-Mail)
L3Com/Link Simulation & Training (817)619-2466 (Fax)
Work: sj...@li...           http://www.link.com
Home: sjb...@ai...       http://web2.airmail.net/sjbaker1

Re: [Algorithms] Up Vector in Projection Matrix

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

> I'm no D3D expert - but I'll presume this is similar to the OpenGL
'glLookAt'
> stuff.
>
> When you specify a point or direction to "look at",  you have only
specified
> two of the degrees of freedom of the system.  That object could be in the
> middle of the screen - either upside-down - or right way up - or at any
> 'roll' angle in between.
>
> The 'up' vector only has to be enough to resolve that issue - and only one
> of its degrees of freedom is needed.  Hence, there are a wide variety of
> vectors that will do the job.  The only constraint is that the up vector
> and the 'look direction' are not parallel.
>
> Hence, so long as your character can't look absolutely vertically upwards
> or absolutely vertically downwards, an 'up' vector of (0,1,0) will do
fine.

That explains everything (though I don't know why/how the underlying math
works).  An ever-confusing question got explained!  Thanks a lot! :-)

Pai-Hung Chen