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

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

There are 2 cases for fans.
The first is where the first vertex is on the edge of the fan. In this case
the list of fan vertices is just a convex polygon. This is what I tend to
think of as fans. They output of clipping to a convex boundary will remain a
fan.
The second type of fan is one where the first vertex is in the middle of the
fan rather than being on the edge. I think you're right that in this case
the clipping won't produce a single fan.
For generating fans offline you could test whether the angle between the
first and last edges from the common vertex is greater that 180 degrees if
the triangles are planar. If it is less than 180 degrees then its the first
type of fan and normal polygon clipping against a convex boundary will take
a fan and produce at most one fan.
I can't think of any algorithm I've come across off hand that handles
clipping type 2 fans...I think it might have to be done using something
similar to the clipping techniques for concave polygons - if you think of a
type 1 vrs type 2 fan then type 1 is convex and type 2 is concave. (Trace
the edges between successive vertices to get the idea).

I'm glad I don't have to deal with type 2!

-Brian.
> -----Original Message-----
> From: gda...@li...
> [mailto:gda...@li...]On Behalf Of Aaron
> Drew
> Sent: Wednesday, July 26, 2000 12:02 PM
> To: gda...@li...
> Subject: RE: [Algorithms] Polygon clipping
>
>
> 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
> >
>
>
> _______________________________________________
> 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

[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] 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

[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