gdalgorithms-list

RE: [Algorithms] "N-Patches" (ATI/DX8 triangle bezier heuristic)

[Patrick E. H. <hu...@tr...>]

>joint, but it would suddenly change speed (which it wouldn't do with
>C1).  G1 or G2 is really what we care about for graphics, C1 and C2
>are unecessarily strong constraints.

Unless you're doing chrome mapping in which case you'd see the anomaly as
the object moved..

Re: [Algorithms] C1 vs G1 (Was: "N-Patches")

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

I don't thing there is any meaning of "G0".  In equations,
C(n) and G(n) conditions for connecting parametric lines
are:

let V(u) be a vector-valued function of the scalar parameter u,
with u in [0,1]
similarly for W(u).

Then C0/G0 is V(1) = W(0)

C1 is V'(1) = W'(0)

where a prime (') indicates differentiation with respect to the
parameter, and V'(1) implicitly means

  [ d/du V(u) ] @ u=1

Then G1 is

Normalize[ V'(1) ] = Normalize[ W'(0) ]

Similarly for Cn, just do n differentiations.

At 01:00 PM 7/26/2000 -0700, you wrote:
>>As for G1 vs. C1, G1 means that the tangents of the two connecting
>>patches are identical.  C1 means that the parametric velocities of
>>the two connecting patches are identical.  eg. if you had a particle
>>flying along a bezier curve at a constant speed in parametric
>>coordinates, then it would keep going the same direction at a G1
>>joint, but it would suddenly change speed (which it wouldn't do with
>>C1).  G1 or G2 is really what we care about for graphics, C1 and C2
>>are unecessarily strong constraints.
>
>So, if I have this right:
>
>Define g(x) = f(x)/|f(x)| for all |f(x)| != 0
>
>Then g C0 continuous at y => f is G0 at y?
>
>What would you call that property, i.e. if C0 == "continuous", what is G0?
>
>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
>
>
--------------------------------------
Charles Bloom           www.cbloom.com

[Algorithms] 1 texture/face -> 1 texture/object

[Ryan E. <ry...@in...>]

First a bit of background.  For my case an "object" is defined as a =
connected polygonal mesh with one base texture projected onto it using =
UVs.  These objects are scaled in geometric detail in real-time using =
progressive mesh techniques.  Currently I am also able to generate one =
lightmap per -face- on these objects.  This is less than desirable for a =
couple reasons.  If I scale the mesh I get holes where new seams don't =
meet up exactly in the mesh and the enormous amount of texture state =
changes kills performance.  Thus what I'm trying to accomplish is to =
generate 1 lightmap per object with it's own set of UVs from the face =
lightmaps for best visual quality and performance.

My current thinking is to use the XYZ values of each vertex/face and =
render/rasterize the lightmap for that face to a new, large texture and =
generate a new set of UVs for each vertex.  The question is how do I map =
XYZ -> UV in the most seamless, space efficient manner?  Seems like a =
nice linear algebra problem ;)

I'm sure this topic must have been covered before, so I'd be most =
appreciative for pointing me to any good resources.

Thanks in advance,
Ryan Earl

[Algorithms] C1 vs G1 (Was: "N-Patches")

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

>As for G1 vs. C1, G1 means that the tangents of the two connecting
>patches are identical.  C1 means that the parametric velocities of
>the two connecting patches are identical.  eg. if you had a particle
>flying along a bezier curve at a constant speed in parametric
>coordinates, then it would keep going the same direction at a G1
>joint, but it would suddenly change speed (which it wouldn't do with
>C1).  G1 or G2 is really what we care about for graphics, C1 and C2
>are unecessarily strong constraints.

So, if I have this right:

Define g(x) = f(x)/|f(x)| for all |f(x)| != 0

Then g C0 continuous at y => f is G0 at y?

What would you call that property, i.e. if C0 == "continuous", what is G0?

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

RE: [Algorithms] "N-Patches" (ATI/DX8 triangle bezier heuristic)

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

Yeah, Tony, I agree with you completely, and I think it's a great
direction for DX & IHV's (that is, adding features that improve
the gfx without any real work from developers).

As for G1 vs. C1, G1 means that the tangents of the two connecting
patches are identical.  C1 means that the parametric velocities of
the two connecting patches are identical.  eg. if you had a particle
flying along a bezier curve at a constant speed in parametric
coordinates, then it would keep going the same direction at a G1
joint, but it would suddenly change speed (which it wouldn't do with
C1).  G1 or G2 is really what we care about for graphics, C1 and C2
are unecessarily strong constraints.


At 12:15 PM 7/26/2000 -0700, you wrote:
>Refresh my memory, what's the difference between G1 and C1 continuity?
>
>Anyway, no matter. The key points about this technique are:
>
>1: It works with a lot of existing content, and gives surprisingly good
>results in many cases. Argue about the theoreticals all you like, but it
>*looks* pretty good.
>
>2: Since it's completely per-triangle, it's very friendly for hardware
>acceleration, which is why we're actually seeing hardware that does it.
>
>Sure, the more advanced subdivision surface techniques are the way to go in
>the long term, but as games developers pragmatism has a certain merit. If
>you can bolt this technique on late in the day to give your some of your
>existing artwork a better look on systems with appropriate hardware (or fast
>CPUs) with very little effort, then why not?
>
>Tony Cox - DirectX Luminary
>Windows Gaming Developer Relations Group
>http://msdn.microsoft.com/directx 
>
>-----Original Message-----
>From: Charles Bloom [mailto:cb...@cb...]
>Sent: 26 July 2000 19:51
>To: gda...@li...
>Cc: cb...@su...
>Subject: [Algorithms] "N-Patches" (ATI/DX8 triangle bezier heuristic)
>
>
>
>Well, ATI's posted this on their website, so I guess we
>can talk about it freely now.
>
>http://www.ati.com/na/pages/resource_centre/dev_rel/devrel.html
>
>I don't give a hoot about the DX8 implementation of this, I
>want to talk about the algorithm of making a curved triangle
>only using its vertices and normals.  I worked on this for
>a while, and decided it wasn't such a hot thing to do, because
>you can't even guarantee G1 continuity, so I abandonded
>it and moved on to butterfly subdivision, where continuity 
>can be gauranteed.
>
>So, first of all, I remember hearing that this heuristic was
>invented by the wise Charles Loop.  Is that correct?  Are there
>any papers on this?  I imagine there aren't, because it's a 
>little trick that's not exactly up to Pixar quality standards.
>
>BTW you can see easily the problems with this scheme.  Each
>triangle is made into a cubic Bezier Triangle.  There are two
>new control points associated with each original vertex, and
>one in the middle.  The two control points at each vertex
>are made to lie on the plane defined by the vertex and its
>normal.  This gaurantees that the final Bezier surface is
>tangent to that same plane at that vertex, thereby giving
>you G1 (but actually not C1, if you want to be nit-picky)
>at that vertex.  However, at every other point on the triangle,
>G1 is in trouble.  Let me try to draw a little picture :
>
>    a
>   /|\
>  / | \
> /  |  \
>b---c---d
>
>So we have two neighboring triangles,  abc and acd.
>At the points a and c, they smoothly meet after Bezier
>tesselation.  However, everywhere else along the edge ac
>they are not G1 in general, because the slope coming
>into the edge ac from triangle acd depends on the point
>d, and the slope coming in from triangle abc depends on
>the point b, so that you can't have G1 unless b and d
>are related in some very restrictive way.  
>
>To get G1, you need to go to Quartic Bezier Triangles,
>and you need to find the control points of each triangle
>by looking at its neighbors.  See, for example, Charles
>Loop's papers on finding the Quartic Bezier Triangles
>that are equivalent to Catmull-Clark subdivision (in
>Siggraph).
>
>I can see why hardware manufacturers like this scheme,
>because it is totally per-triangle (eg. you don't need
>any connectivity information).  However, we are much
>smarter, and we know how are triangles are connected,
>so we can use the fast subdivision tesselation scheme
>of Kari Pulli (for example), or we can use Tom's
>subdivision + displacement + VIPM technique.  (I'm
>imagining for the moment that I don't have a GPU that
>can do these Patches in hardware, so I would have to
>implement them in software, obviously they are cool/free
>when the hardware does them for you).
>
>--------------------------------------
>Charles Bloom           www.cbloom.com
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
>
--------------------------------------
Charles Bloom           www.cbloom.com

RE: [Algorithms] "N-Patches" (ATI/DX8 triangle bezier heuristic)

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

Refresh my memory, what's the difference between G1 and C1 continuity?

Anyway, no matter. The key points about this technique are:

1: It works with a lot of existing content, and gives surprisingly good
results in many cases. Argue about the theoreticals all you like, but it
*looks* pretty good.

2: Since it's completely per-triangle, it's very friendly for hardware
acceleration, which is why we're actually seeing hardware that does it.

Sure, the more advanced subdivision surface techniques are the way to go in
the long term, but as games developers pragmatism has a certain merit. If
you can bolt this technique on late in the day to give your some of your
existing artwork a better look on systems with appropriate hardware (or fast
CPUs) with very little effort, then why not?

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

-----Original Message-----
From: Charles Bloom [mailto:cb...@cb...]
Sent: 26 July 2000 19:51
To: gda...@li...
Cc: cb...@su...
Subject: [Algorithms] "N-Patches" (ATI/DX8 triangle bezier heuristic)



Well, ATI's posted this on their website, so I guess we
can talk about it freely now.

http://www.ati.com/na/pages/resource_centre/dev_rel/devrel.html

I don't give a hoot about the DX8 implementation of this, I
want to talk about the algorithm of making a curved triangle
only using its vertices and normals.  I worked on this for
a while, and decided it wasn't such a hot thing to do, because
you can't even guarantee G1 continuity, so I abandonded
it and moved on to butterfly subdivision, where continuity 
can be gauranteed.

So, first of all, I remember hearing that this heuristic was
invented by the wise Charles Loop.  Is that correct?  Are there
any papers on this?  I imagine there aren't, because it's a 
little trick that's not exactly up to Pixar quality standards.

BTW you can see easily the problems with this scheme.  Each
triangle is made into a cubic Bezier Triangle.  There are two
new control points associated with each original vertex, and
one in the middle.  The two control points at each vertex
are made to lie on the plane defined by the vertex and its
normal.  This gaurantees that the final Bezier surface is
tangent to that same plane at that vertex, thereby giving
you G1 (but actually not C1, if you want to be nit-picky)
at that vertex.  However, at every other point on the triangle,
G1 is in trouble.  Let me try to draw a little picture :

    a
   /|\
  / | \
 /  |  \
b---c---d

So we have two neighboring triangles,  abc and acd.
At the points a and c, they smoothly meet after Bezier
tesselation.  However, everywhere else along the edge ac
they are not G1 in general, because the slope coming
into the edge ac from triangle acd depends on the point
d, and the slope coming in from triangle abc depends on
the point b, so that you can't have G1 unless b and d
are related in some very restrictive way.  

To get G1, you need to go to Quartic Bezier Triangles,
and you need to find the control points of each triangle
by looking at its neighbors.  See, for example, Charles
Loop's papers on finding the Quartic Bezier Triangles
that are equivalent to Catmull-Clark subdivision (in
Siggraph).

I can see why hardware manufacturers like this scheme,
because it is totally per-triangle (eg. you don't need
any connectivity information).  However, we are much
smarter, and we know how are triangles are connected,
so we can use the fast subdivision tesselation scheme
of Kari Pulli (for example), or we can use Tom's
subdivision + displacement + VIPM technique.  (I'm
imagining for the moment that I don't have a GPU that
can do these Patches in hardware, so I would have to
implement them in software, obviously they are cool/free
when the hardware does them for you).

--------------------------------------
Charles Bloom           www.cbloom.com

[Algorithms] "N-Patches" (ATI/DX8 triangle bezier heuristic)

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

Well, ATI's posted this on their website, so I guess we
can talk about it freely now.

http://www.ati.com/na/pages/resource_centre/dev_rel/devrel.html

I don't give a hoot about the DX8 implementation of this, I
want to talk about the algorithm of making a curved triangle
only using its vertices and normals.  I worked on this for
a while, and decided it wasn't such a hot thing to do, because
you can't even guarantee G1 continuity, so I abandonded
it and moved on to butterfly subdivision, where continuity 
can be gauranteed.

So, first of all, I remember hearing that this heuristic was
invented by the wise Charles Loop.  Is that correct?  Are there
any papers on this?  I imagine there aren't, because it's a 
little trick that's not exactly up to Pixar quality standards.

BTW you can see easily the problems with this scheme.  Each
triangle is made into a cubic Bezier Triangle.  There are two
new control points associated with each original vertex, and
one in the middle.  The two control points at each vertex
are made to lie on the plane defined by the vertex and its
normal.  This gaurantees that the final Bezier surface is
tangent to that same plane at that vertex, thereby giving
you G1 (but actually not C1, if you want to be nit-picky)
at that vertex.  However, at every other point on the triangle,
G1 is in trouble.  Let me try to draw a little picture :

    a
   /|\
  / | \
 /  |  \
b---c---d

So we have two neighboring triangles,  abc and acd.
At the points a and c, they smoothly meet after Bezier
tesselation.  However, everywhere else along the edge ac
they are not G1 in general, because the slope coming
into the edge ac from triangle acd depends on the point
d, and the slope coming in from triangle abc depends on
the point b, so that you can't have G1 unless b and d
are related in some very restrictive way.  

To get G1, you need to go to Quartic Bezier Triangles,
and you need to find the control points of each triangle
by looking at its neighbors.  See, for example, Charles
Loop's papers on finding the Quartic Bezier Triangles
that are equivalent to Catmull-Clark subdivision (in
Siggraph).

I can see why hardware manufacturers like this scheme,
because it is totally per-triangle (eg. you don't need
any connectivity information).  However, we are much
smarter, and we know how are triangles are connected,
so we can use the fast subdivision tesselation scheme
of Kari Pulli (for example), or we can use Tom's
subdivision + displacement + VIPM technique.  (I'm
imagining for the moment that I don't have a GPU that
can do these Patches in hardware, so I would have to
implement them in software, obviously they are cool/free
when the hardware does them for you).

--------------------------------------
Charles Bloom           www.cbloom.com

Re: [Algorithms] Polygon clipping

[Jim O. <j.o...@in...>]

> The point is this... I intend to write a polygon clipper for 2D games
using
> the 3D hardware (the vertices are already in screen space). Of course, in
2D
> ...
> again. Actually, this is one of those rare cases where I'd say "source
code
> appreciated" ;-)

Can't you just set up a pass through projection system (i.e. coordinates in
= coordinates out) and rely on the clippers of either the underlying
hardware and/or those from the API your using?

Jim Offerman

Innovade
- designing the designer

Re: [Algorithms] Polygon clipping

[Klaus H. <k_h...@os...>]

----- Original Message -----
From: Brian Marshall <bma...@ra...>
To: <gda...@li...>
Sent: Wednesday, July 26, 2000 2:39 PM
Subject: RE: [Algorithms] Polygon clipping


> Different from the normal. I was assuming that the fan was for a convex
> polygon. DOH! For a convex polygon the vertices are in fan order anyway
and
> remain so after clipping. This example is not convex so I guess you could
> use more general polygon clipping.

The point is this... I intend to write a polygon clipper for 2D games using
the 3D hardware (the vertices are already in screen space). Of course, in 2D
games, polygons are usually convex (like particles, or simple textured
blocks), but... In my opinion, polygon clipping is not exactly one of the
most interesting topics, and thus I want to write a clipper that handles all
the standard primitive types (concave, and convex), and never think about it
again. Actually, this is one of those rare cases where I'd say "source code
appreciated" ;-)

> Sutherland-Hodgham will clip concave
> polygons, in this case giving 2 polygons out, or a degenerate triangle
(zero
> area) connecting the 2 fragments. There is some info on this in FvD etc.

Yes, I do have all these standard books, like the Graphics Gems, FvDFH, and
so on... but they are pretty old. Of course, 'old' doesn't make them bad,
but I'd like to know if there are newer/better/faster clipping algorithms
than Sutherland Hodgman and the like, before I start to implement an 'old'
algorithm. Maybe some clipping algorithm that operates in screen space?
(i.e. no need for back-transforms)

Anyway, I'll now move over to a D3D group for my API-specific questions, and
try to ask non-API-specific questions here.

Thanks,
Niki

> If your generating the strips/fans offline it may be worthwhile only
> allowing convex fans - you'd have to time the benefits of bigger fans
> against more complex clipping code.
>
> -Brian.

RE: [Algorithms] Polygon clipping

[Brian M. <bma...@ra...>]

	Different from the normal. I was assuming that the fan was for a convex
polygon. DOH! For a convex polygon the vertices are in fan order anyway and
remain so after clipping. This example is not convex so I guess you could
use more general polygon clipping. Sutherland-Hodgham will clip concave
polygons, in this case giving 2 polygons out, or a degenerate triangle (zero
area) connecting the 2 fragments. There is some info on this in FvD etc.
	If your generating the strips/fans offline it may be worthwhile only
allowing convex fans - you'd have to time the benefits of bigger fans
against more complex clipping code.

-Brian.

> -----Original Message-----
> From: gda...@li...
> [mailto:gda...@li...]On Behalf Of Klaus
> Hartmann
> Sent: Wednesday, July 26, 2000 1:25 PM
> To: gda...@li...
> Subject: Re: [Algorithms] Polygon clipping
>
>
> Tom, and Brian.... thanks for your help.
>
> I realize now, that this becomes API-specific, so I'm going to move this
> thread over to some D3D group, because I still have some questions.
>
> There's just one thing I'd like to mention here...
>
> ----- Original Message -----
> From: Tom Forsyth <to...@mu...>
> To: <gda...@li...>
>
> > Fans remain fans (though it may be knarly to find the ordering), strips
> > don't - they can become multiple strips (think about a U-shaped strip
> where
> > the bottom of the U is off-screen).
>
> Your U-shape example, tells me, that I can also get multiple fans. Have a
> look at the following image that shows a V-shaped fan:
> http://www.thecore.de/TheCore/fan.jpg
>
>
> Thanks,
> Niki
>
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

RE: [Algorithms] VB vs primitives (was Polygon clipping)

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

>Can anybody explain me, why rendering untransformed, unlit, single-textured
>stripes from a huge optimized wr-only vertex buffer is about 50% slower
versus
>rendering them from a huge primitive? Is it something related to the
software
>T&L? We are using ATI Fury 128, DirectX 7 and DrawIndexedPrimitiveVB vs.
>DrawIndexedPrimitive. The vertex percent of total vertices per D3D call is
>about 0.5%. Any idea?

Most definitely OT. Repost on the DirectXDev list and I'll try to help you
out.

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

Re: [Algorithms] VB vs primitives (was Polygon clipping)

[Martin G. <bz...@wi...>]

Can anybody explain me, why rendering untransformed, unlit, single-textured
stripes from a huge optimized wr-only vertex buffer is about 50% slower versus
rendering them from a huge primitive? Is it something related to the software
T&L? We are using ATI Fury 128, DirectX 7 and DrawIndexedPrimitiveVB vs.
DrawIndexedPrimitive. The vertex percent of total vertices per D3D call is
about 0.5%. Any idea?

Thanks in advance,
Martin

P.S. apologies if this is OT


-----Original Message-----
From: Tom Forsyth <to...@mu...>
To: gda...@li...
<gda...@li...>
Date: 26 Þëè 2000 ã. 12:58
Subject: RE: [Algorithms] Polygon clipping


>Fans remain fans (though it may be knarly to find the ordering), strips
>don't - they can become multiple strips (think about a U-shaped strip where
>the bottom of the U is off-screen).
>
>You might also want to try sending objects that intersect the frustum edges
>through the non-VB path, so that D3D clips them for you - it's actually
>pretty fast. Things that don't need clipping should still go through the VB
>path of course.
>
>Oh, and I really recommend indexed lists instead of lots of little strips
>and fans - you get far too many D3D calls that way, and if you're going to
>do your own clipping, indexed lists are very easy to handle.
>
>Tom Forsyth - Muckyfoot bloke.
>Whizzing and pasting and pooting through the day.
>
>> -----Original Message-----
>> From: Klaus Hartmann [mailto:k_h...@os...]
>> Sent: 25 July 2000 23:49
>> To: gda...@li...
>> Subject: [Algorithms] Polygon clipping
>>
>>
>> Hi all,
>>
>> Even though this is not an API-specific question, I'd like to use an
>> API-specific example to explain my problem.
>>
>> In Direct3D, when using *vertex buffer* with pre-transformed
>> and pre-lit
>> vertices, then Direct3D does not perform any clipping. So I
>> have to do this
>> myself. I could probably go ahead an clip single triangles
>> with a Sutherland
>> Hodgman algorithm, but...
>>
>> How do you people clip triangle strips and triangle fans? Is
>> it possible to
>> clip them so, that strips remain strips, and fans remain
>> fans, or is this
>> impossible?
>>
>> Also, which is the prefered clipping algorithm? Is it
>> Sutherland Hodgman?
>>
>> When you answer, please keep in mind that I also need to clip texture
>> coordinates and the diffuse/specular colors.
>>
>> Any help is greatly appreciated,
>> Niki
>>
>>
>> _______________________________________________
>> 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] Polygon clipping

[Klaus H. <k_h...@os...>]

Tom, and Brian.... thanks for your help.

I realize now, that this becomes API-specific, so I'm going to move this
thread over to some D3D group, because I still have some questions.

There's just one thing I'd like to mention here...

----- Original Message -----
From: Tom Forsyth <to...@mu...>
To: <gda...@li...>

> Fans remain fans (though it may be knarly to find the ordering), strips
> don't - they can become multiple strips (think about a U-shaped strip
where
> the bottom of the U is off-screen).

Your U-shape example, tells me, that I can also get multiple fans. Have a
look at the following image that shows a V-shaped fan:
http://www.thecore.de/TheCore/fan.jpg


Thanks,
Niki

RE: [Algorithms] Polygon clipping

[Aaron D. <ri...@ho...>]

I might be overlooking something here but I can imagine a case where a fan
would not remain a fan after clipping that might complicate this method.

What happens when the centre of the fan is out of the view frustum? I can't
see how the fan can be preserved. It would be cut into a series of quads
which would no longer share a common vertex. Unless I'm thinking of
something wrongly, these can't be arranged in a fan-like fashion.

- Aaron

> -----Original Message-----
> From: gda...@li...
> [mailto:gda...@li...]On Behalf Of Tom
> Forsyth
> Sent: Wednesday, July 26, 2000 7:50 PM
> To: gda...@li...
> Subject: RE: [Algorithms] Polygon clipping
>
>
>
> Fans remain fans (though it may be knarly to find the ordering), strips
> don't - they can become multiple strips (think about a U-shaped
> strip where
> the bottom of the U is off-screen).
>
> You might also want to try sending objects that intersect the
> frustum edges
> through the non-VB path, so that D3D clips them for you - it's actually
> pretty fast. Things that don't need clipping should still go
> through the VB
> path of course.
>
> Oh, and I really recommend indexed lists instead of lots of little strips
> and fans - you get far too many D3D calls that way, and if you're going to
> do your own clipping, indexed lists are very easy to handle.
>
> Tom Forsyth - Muckyfoot bloke.
> Whizzing and pasting and pooting through the day.
>
> > -----Original Message-----
> > From: Klaus Hartmann [mailto:k_h...@os...]
> > Sent: 25 July 2000 23:49
> > To: gda...@li...
> > Subject: [Algorithms] Polygon clipping
> >
> >
> > Hi all,
> >
> > Even though this is not an API-specific question, I'd like to use an
> > API-specific example to explain my problem.
> >
> > In Direct3D, when using *vertex buffer* with pre-transformed
> > and pre-lit
> > vertices, then Direct3D does not perform any clipping. So I
> > have to do this
> > myself. I could probably go ahead an clip single triangles
> > with a Sutherland
> > Hodgman algorithm, but...
> >
> > How do you people clip triangle strips and triangle fans? Is
> > it possible to
> > clip them so, that strips remain strips, and fans remain
> > fans, or is this
> > impossible?
> >
> > Also, which is the prefered clipping algorithm? Is it
> > Sutherland Hodgman?
> >
> > When you answer, please keep in mind that I also need to clip texture
> > coordinates and the diffuse/specular colors.
> >
> > Any help is greatly appreciated,
> > Niki
> >
> >
> > _______________________________________________
> > 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] Polygon clipping

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

Fans remain fans (though it may be knarly to find the ordering), strips
don't - they can become multiple strips (think about a U-shaped strip where
the bottom of the U is off-screen).

You might also want to try sending objects that intersect the frustum edges
through the non-VB path, so that D3D clips them for you - it's actually
pretty fast. Things that don't need clipping should still go through the VB
path of course.

Oh, and I really recommend indexed lists instead of lots of little strips
and fans - you get far too many D3D calls that way, and if you're going to
do your own clipping, indexed lists are very easy to handle.

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

> -----Original Message-----
> From: Klaus Hartmann [mailto:k_h...@os...]
> Sent: 25 July 2000 23:49
> To: gda...@li...
> Subject: [Algorithms] Polygon clipping
> 
> 
> Hi all,
> 
> Even though this is not an API-specific question, I'd like to use an
> API-specific example to explain my problem.
> 
> In Direct3D, when using *vertex buffer* with pre-transformed 
> and pre-lit
> vertices, then Direct3D does not perform any clipping. So I 
> have to do this
> myself. I could probably go ahead an clip single triangles 
> with a Sutherland
> Hodgman algorithm, but...
> 
> How do you people clip triangle strips and triangle fans? Is 
> it possible to
> clip them so, that strips remain strips, and fans remain 
> fans, or is this
> impossible?
> 
> Also, which is the prefered clipping algorithm? Is it 
> Sutherland Hodgman?
> 
> When you answer, please keep in mind that I also need to clip texture
> coordinates and the diffuse/specular colors.
> 
> Any help is greatly appreciated,
> Niki
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

Re: [Algorithms] Cyrus-beck line clipping algorithm

[Jamie F. <j.f...@re...>]

Without any reference to the book (or anything else) at all....

My guess is that he's thinking of it as projecting things onto z = 0 (with
visible things at z = 0 falling in the rectangle of xl, xr, yt, yb), but his
near plane just happens to be closer to the centre of projection than that.

Jamie


Phil Yard wrote:

> I have just been looking through the definition of the Cyrus-Beck line
> clipping algorithm, as defined in 'Procedural elements for computer
> graphics' by David Rogers.
>
> On talking about deriving the normals to the top, bottom and side planes of
> the viewing frustrum, he talks about using the 'cross products of the
> vectors from the centre of projection to the corners at z=0, the plane of
> projection'.
>
> However, he previously defines the view frustrum as a 'perspective volume
> with (xl, xr, yb, yt, zh, zy ) = (-1, 1, -1, 1, 1, -1), with a centre of
> projection at zcp = 5'.
>
> He lists the vectors as:
>         v1 = [ 1, 1, -5 ]
>         v2 = [ -1, 1, -5 ]
>         v3 = [ -1, -1, -5 ]
>         v4 = [ 1, -1, -5 ]
>
> Surely the plane of projection should be z = -1, and therefore the z
> component in the above vectors should be -6?
>
> Or am I (more likely!) missing something obvious here?
>
> _____________________________________
> Phil Yard, Lead Programmer, Climax (Brighton) Ltd
> 01273 764109  mob: 0771 258 1164  web: www.climax.co.uk
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] Can I do this?

[Jim O. <j.o...@in...>]

> That sounds like a great tool if you include the name of the resource...it
> sounds like something that "should" be provided with any multi-tasking
> ...
> of your programs resource requirements as well...and perhaps trust it
more.
> If you do write one...please let me know! :)

Good point... Stuffing it into a seperate .exe file will probably also
result in some cleaner code too.

> Keep in mind this is an Algorithms list, there might already be what you
> need...perhaps in a win32 tool discussion list.

Hmmm... I guess I could check with some of these guys...

I'll keep you posted.

Jim Offerman

Innovade
- designing the designer

RE: [Algorithms] Polygon clipping

[Brian M. <bma...@ra...>]

A triangle fan will remain a triangle fan after clipping to a convex clip
boundary. So if you're clipping to a normal 6 plane view frustrum the fan
stays a fan, though it may have more or less vertices afterwards.

As to triangle strips check out:

	'Three Dimensional Homogenous Clipping of Triangle Strips' Patrick-Gilles
Maillot, Graphics Gems II

If you don't have the book the code is on the net.

When you clip a strip you can get zero or more strips out, or output at most
one strip with degenerate triangles. (The degenerate triangles are used for
jumping along a clip boundary when a hole section of the strip is outside
the clip volume.)

The strip clipping code uses the clip against one plane at a time approach
of Sutherland-Hodgman, but exploits the strip structure to improve
performance.

As to the choice of clipping algorithm - I think that belongs more on a D3D
list for your example, but it may well be worth seeing how quick D3D is at
doing the clipping itself.

-Brian.

> -----Original Message-----
> From: gda...@li...
> [mailto:gda...@li...]On Behalf Of Klaus
> Hartmann
> Sent: Tuesday, July 25, 2000 11:49 PM
> To: gda...@li...
> Subject: [Algorithms] Polygon clipping
>
>
> Hi all,
>
> Even though this is not an API-specific question, I'd like to use an
> API-specific example to explain my problem.
>
> In Direct3D, when using *vertex buffer* with pre-transformed and pre-lit
> vertices, then Direct3D does not perform any clipping. So I have
> to do this
> myself. I could probably go ahead an clip single triangles with a
> Sutherland
> Hodgman algorithm, but...
>
> How do you people clip triangle strips and triangle fans? Is it
> possible to
> clip them so, that strips remain strips, and fans remain fans, or is this
> impossible?
>
> Also, which is the prefered clipping algorithm? Is it Sutherland Hodgman?
>
> When you answer, please keep in mind that I also need to clip texture
> coordinates and the diffuse/specular colors.
>
> Any help is greatly appreciated,
> Niki
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

RE: [Algorithms] Can I do this?

[Steve W. <Ste...@im...>]

> -----Original Message-----
> From: Jim Offerman [mailto:j.o...@in...]
>
[snip]
>
> I could simply compile a list of resource heavy 
> applications and display this in a list box
>

That sounds like a great tool if you include the name of the resource...it
sounds like something that "should" be provided with any multi-tasking
operating system.  However, you might want to refrain from providing a
resource nazi within your game so people won't think your program is just
being a resource hog...perhaps include it as a seperate executable or system
tray program that users can choose to install...that way they can keep track
of your programs resource requirements as well...and perhaps trust it more.
If you do write one...please let me know! :)

Keep in mind this is an Algorithms list, there might already be what you
need...perhaps in a win32 tool discussion list.

R&R

RE: [Algorithms] How to derive transformation matrices

[Steve W. <Ste...@im...>]

> -----Original Message-----
> From: Klaus Hartmann [mailto:k_h...@os...]
> 
> Okay, I know... I said I would exit the thread, but I did a 
> mistake in my last post.
> 

OMG!  :O

> > With this I don't agree. Certainly, in the case of your box, the shear
force
> > is perpendicular to the surface of contact. But that's not necessarily
true
> > for other primitives. What about spheres for example? Imagine a sphere
that
> > is centered at the origin. The fixed plane is the x/z plane of the world
> > coordinate system, and we shear along the x-axis (y, and z are fixed).
So
> > our shear force could be represented as a vector H = <h 0 0>, where h is
the
> > magnitude of the force in x-direction. Would you still say, that the
shear
> > force if perpendicular to the surface of contact? Maybe I just
misunderstand
> > you, but for me it's not perpendicular to the surface of contact.
> 

I see your point and agree with you...I think it has finally dawned on me
why shear forces are described with reference to the shear plane.  Thanks.
Mostly what I remember about my statics class was the endless repository for
laughter called Mohr's circle, just barely edging out the slide rule...which
believe it or not was a required lesson the year before I took geometry (we
were the lucky class to be first to use a calculator), and our instructor's
slide show of when he was called off during 2 weeks of the class to help in
the assesment of the Loma Prieta earthquake of '89.

> Forget the vector H thing, which is quite incorrect, because shearing
> depends on another coordinate. Examples:
> 
> Hxy is a shear matrix that changes x depending on y.
> Hxz is a shear matrix that changes x depending on z.
> Hyx is a shear matrix that changes y depending on x.
> Hyz is a shear matrix that changes y depending on z.
> Hzx is a shear matrix that changes z depending on x.
> Hzy is a shear matrix that changes z depending on y.
> 

I found the vector thing intuitive for me...I don't use matrices but that
might help others understand.

> I hope that at least this time I was faster to correct myself 
> than others ;)
> Niki
> 

Well, I think we'll let it go this time...but one more time and...! ;)

R&R

[Algorithms] Polygon clipping

[Klaus H. <k_h...@os...>]

Hi all,

Even though this is not an API-specific question, I'd like to use an
API-specific example to explain my problem.

In Direct3D, when using *vertex buffer* with pre-transformed and pre-lit
vertices, then Direct3D does not perform any clipping. So I have to do this
myself. I could probably go ahead an clip single triangles with a Sutherland
Hodgman algorithm, but...

How do you people clip triangle strips and triangle fans? Is it possible to
clip them so, that strips remain strips, and fans remain fans, or is this
impossible?

Also, which is the prefered clipping algorithm? Is it Sutherland Hodgman?

When you answer, please keep in mind that I also need to clip texture
coordinates and the diffuse/specular colors.

Any help is greatly appreciated,
Niki

Re: [Algorithms] Can I do this?

[Jim O. <j.o...@in...>]

I am under the distinct impression that I suggested something really bad,
almost feeling sorry for making the suggestion. Some comments though:

> If you prompted "Do you want to close some applications?" and the user
> prompted yes which causes you to kill the 100mb download they've been
> downloading for the last day that's at 99.99%?

That is not what I wanted to do... I was actually thinking about mimicing a
Windows shutdown (which would also be the point where the user finds out
that that download is at 99.99% so that they'd better wait for few more
minutes before shutdown) to give all applications a chance to save etc. etc.

However, I think we've covered about every reason why that idea is bad
already... so on to a better idea then: Instead of mimicing the Windows
shutdown, I could simply compile a list of resource heavy applications and
display this in a list box, suggesting to the user that he'd (or she'd)
better close a few of these applications before continuing (and yes, it will
have the oh-so-precious Ignore button... I still remember certain games
which refused to install on a Win2K machine, since they weren't NT
compatible - grrr!). Oh, and maybe with one of those bars, which changes
color from red to orange to green as more and more resources are freed up
:-)

> Finally, it's not your problem (i.e., not a support issue) if they've
> decided to tie up the majority of system resources and thereby have
problems
> running your program.  Add a FAQ entry to your manual if it makes you feel
> better. :p

This is true in the general case, however, in the specific case of family
and or close friends, I somehow end up fixing things afterwards (perhaps I
am just to nice a guy and thus the only developer on the face of this planet
that ever ends up fixing the pc of relatives and friends, in which case
there never was a problem bigf enough to solve, let alone mention...).

Jim Offerman

Innovade
- designing the designer

Re: [Algorithms] How to derive transformation matrices

[Klaus H. <k_h...@os...>]

Okay, I know... I said I would exit the thread, but I did a mistake in my
last post.

> With this I don't agree. Certainly, in the case of your box, the shear
force
> is perpendicular to the surface of contact. But that's not necessarily
true
> for other primitives. What about spheres for example? Imagine a sphere
that
> is centered at the origin. The fixed plane is the x/z plane of the world
> coordinate system, and we shear along the x-axis (y, and z are fixed). So
> our shear force could be represented as a vector H = <h 0 0>, where h is
the
> magnitude of the force in x-direction. Would you still say, that the shear
> force if perpendicular to the surface of contact? Maybe I just
misunderstand
> you, but for me it's not perpendicular to the surface of contact.

Forget the vector H thing, which is quite incorrect, because shearing
depends on another coordinate. Examples:

Hxy is a shear matrix that changes x depending on y.
Hxz is a shear matrix that changes x depending on z.
Hyx is a shear matrix that changes y depending on x.
Hyz is a shear matrix that changes y depending on z.
Hzx is a shear matrix that changes z depending on x.
Hzy is a shear matrix that changes z depending on y.

I hope that at least this time I was faster to correct myself than others ;)
Niki

Re: [Algorithms] How to derive transformation matrices

[Klaus H. <k_h...@os...>]

Okay, I know... I said I would exit the thread, but I did a mistake in my
last post.

> With this I don't agree. Certainly, in the case of your box, the shear
force
> is perpendicular to the surface of contact. But that's not necessarily
true
> for other primitives. What about spheres for example? Imagine a sphere
that
> is centered at the origin. The fixed plane is the x/z plane of the world
> coordinate system, and we shear along the x-axis (y, and z are fixed). So
> our shear force could be represented as a vector H = <h 0 0>, where h is
the
> magnitude of the force in x-direction. Would you still say, that the shear
> force if perpendicular to the surface of contact? Maybe I just
misunderstand
> you, but for me it's not perpendicular to the surface of contact.

Forget the vector H thing, which is quite incorrect, because shearing
depends on another coordinate. Examples:

Hxy is a shear matrix that changes x depending on y.
Hxz is a shear matrix that changes x depending on z.
Hyx is a shear matrix that changes y depending on x.
Hyz is a shear matrix that changes y depending on z.
Hzx is a shear matrix that changes z depending on x.
Hzy is a shear matrix that changes z depending on y.

I hope that at least this time I was faster to correct myself than others ;)
Niki

Re: [Algorithms] How to derive transformation matrices

[Klaus H. <k_h...@os...>]

----- Original Message -----
From: Steve Wood <Ste...@im...>
To: <gda...@li...>
Sent: Tuesday, July 25, 2000 11:10 PM
Subject: RE: [Algorithms] How to derive transformation matrices


> Yes, a "shear plane" describes the plane where two surfaces move by each
> other.  A force causing these surfaces to move is called a shear force and
> is parallel to the shear plane,

I agree here.

> however it is perpendicular to the surface
> of contact.

With this I don't agree. Certainly, in the case of your box, the shear force
is perpendicular to the surface of contact. But that's not necessarily true
for other primitives. What about spheres for example? Imagine a sphere that
is centered at the origin. The fixed plane is the x/z plane of the world
coordinate system, and we shear along the x-axis (y, and z are fixed). So
our shear force could be represented as a vector H = <h 0 0>, where h is the
magnitude of the force in x-direction. Would you still say, that the shear
force if perpendicular to the surface of contact? Maybe I just misunderstand
you, but for me it's not perpendicular to the surface of contact.

> A dictionary sometimes doesn't provide what you might learn in
> an engineering textbook.

Yeah, forget that dictionary thing. I don't even know why I posted this :(

> But, again I don't think the original poster (OP) has an object box
breaking
> apart and just wants to deform it, like turning a box into a trapezoid

I think that's a parallelepiped, but I'm not 100% sure.

But you are right... this really doesn't help the OP author. So I'll just
exit the thread here, unless I decide to provide something more useful.

Niki