gdalgorithms-list

Re: [Algorithms] Thermal infrared techniques?

[Jon W. <jw...@gm...>]

Ron Hay wrote:
> Anyone have points to papers/tutorials/explanations of some algorithms 
> for rendering a scene as it would appear through a thermal IR camera?  
> As in military operations stuff.  Anything ranging from "good enough" to 
> a decent approximation of reality is usable.
>   

What the military guys do is generally build a second set of textures 
for everything, where the texture values correspond to frequencies in 
the IR spectrum instead of the visible RGB spectrum. Additionally, as 
this is usually done for night vision, you render without lighting, but 
instead using fullbright (or some variation thereof) textures. The 
reason for this is that materials typically have very different behavior 
in the IR spectrum than in the visible spectrum -- a lawn, a garden 
hose, and a painted metal grate can all be "green," but they behave 
really differently in IR.
Depending on what kind of simulation you're doing, you might want to use 
a texture channel or two for parameters such as "decay," such that you 
can pass in a parameter like "time since last exposure to sunlight" and 
get a better emulation of how a scene will change over time -- different 
materials cool differently.
Finally, if you want to emulate the "look" of a particular IR sensor or 
display, you should get a copy of the real thing, or barring that, some 
video of the real thing, and add whatever artifacts you can see 
(striping, bright bands, knock-out, ringing, etc) as shader effects, 
until it's close enough.

Sincerely,

jw

Re: [Algorithms] Thermal infrared techniques?

[<lo...@fr...>]

Hello, 

can't you just use grayscale textures that represent body heat + some 
fancy pixel shader to get the result you want ? It should be decent 
enough to be acceptable (but will require you to use another set of 
textures). If you want to get some reference images, I believe that 
some Sony camera and recorders have IR sensors. 
(see http://www.maxmax.com/camcorders.htm).

BTW, what kind of effect to you want to get ? An colorized image like
http://www.jenoptik-los.com/img/323/1/hauptbild.30.bmp or a grayscale, 
possibly greenish image like 
http://www.dreamshine.com/images/MaxMax/Sam%20Outcalt/NFF_ir_1.JPG 
(difficult to see, but the reason why leaves are so bright is because 
they are warmed by the sunlight; the trunk is less hot. I believe 
this picture has been taken during the day, which would explain the
general bright tone) ?

-- Emmanuel

----- Mail Original -----
De: "Ron Hay" <rh...@cy...>
À: "Game Development Algorithms" <gda...@li...>
Envoyé: Jeudi 28 Mai 2009 15h18:04 GMT
Objet: [Algorithms] Thermal infrared techniques?

Anyone have points to papers/tutorials/explanations of some algorithms 
for rendering a scene as it would appear through a thermal IR camera?  
As in military operations stuff.  Anything ranging from "good enough" to 
a decent approximation of reality is usable.

Thanks!



------------------------------------------------------------------------------
Register Now for Creativity and Technology (CaT), June 3rd, NYC. CaT 
is a gathering of tech-side developers & brand creativity professionals. Meet
the minds behind Google Creative Lab, Visual Complexity, Processing, & 
iPhoneDevCamp as they present alongside digital heavyweights like Barbarian 
Group, R/GA, & Big Spaceship. http://p.sf.net/sfu/creativitycat-com 
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] Thermal infrared techniques?

[Andy F. <an...@si...>]

Ron Hay wrote:
> Anyone have points to papers/tutorials/explanations of some algorithms 
> for rendering a scene as it would appear through a thermal IR camera?  
> As in military operations stuff.  Anything ranging from "good enough" to 
> a decent approximation of reality is usable.
>
> Thanks!
>
>   

Intuitively, render luminance (0.0 - 1.0) mapped to green with some 
overbrightness / glow effect.  How do you think that would work?

andy

[Algorithms] Thermal infrared techniques?

[Ron H. <rh...@cy...>]

Anyone have points to papers/tutorials/explanations of some algorithms 
for rendering a scene as it would appear through a thermal IR camera?  
As in military operations stuff.  Anything ranging from "good enough" to 
a decent approximation of reality is usable.

Thanks!

Re: [Algorithms] Best fit of polygon inside another polygon

[Jon W. <jw...@gm...>]

Fabian Giesen wrote:
> translation nor rotation of the polygon will change its area. So the 
> remaining area is not helpful at all in comparing which is a better fit.
>   

If the point is that you have many polygons to choose from, then the 
largest polygon that fits would "fit best."

Sincerely,

jw

Re: [Algorithms] Best fit of polygon inside another polygon

[Fabian G. <f.g...@49...>]

> not at all - if you think of the physical world rather than a 
> mathematical one, this search for 'best fit' is one that a child might 
> use playing with a set of odd-shape blocks and a box.  Ask him which 
> shape 'best fits' in the box and he won't think of scale...

The basic point remains though that this is still just a binary test as 
requested (i.e. using translation and rotation only). Either the other 
polygon fits into the quad or it doesn't, but when it does, the 
remaining area is always Area(Quad)-Area(Polygon), since neither 
translation nor rotation of the polygon will change its area. So the 
remaining area is not helpful at all in comparing which is a better fit.

-Fabian Giesen

Re: [Algorithms] Best fit of polygon inside another polygon

[Peter L. <pe...@to...>]

-- I thought I should quote from the problem definition, too:

I have different polygons with varying shape and size and I want
> to find the polygon and according transformation of the polygon which
> best fits it into the given quad. 

  -- so it's not a question of "find the tightest bounding quadrilateral on a given polygon". It's "find the polygon that matches the given quad".



Peter Lipson wrote:
> not at all - if you think of the physical world rather than a 
> mathematical one, this search for 'best fit' is one that a child might 
> use playing with a set of odd-shape blocks and a box.  Ask him which 
> shape 'best fits' in the box and he won't think of scale...
>
> Nicholas "Indy" Ray wrote:
>> Without scaling this seems to be an odd request... as what defines any
>> one fit better then another, so long as the polygon does fit within
>> the quad, there lacks a metric for "best" as any fit will take the
>> same area and have the same excess area
>

Re: [Algorithms] Best fit of polygon inside another polygon

[Peter L. <pe...@to...>]

not at all - if you think of the physical world rather than a 
mathematical one, this search for 'best fit' is one that a child might 
use playing with a set of odd-shape blocks and a box.  Ask him which 
shape 'best fits' in the box and he won't think of scale...

Nicholas "Indy" Ray wrote:
> Without scaling this seems to be an odd request... as what defines any
> one fit better then another, so long as the polygon does fit within
> the quad, there lacks a metric for "best" as any fit will take the
> same area and have the same excess area

Re: [Algorithms] Best fit of polygon inside another polygon

[Nicholas \Indy\ R. <ar...@gm...>]

Except with Scaling you can define best fit to be the fit that takes
up the most amount of area, which is a pretty standard metric for best
fit, no such standard metric exists without scaling IMO.

Nicholas "Indy" Ray

On Mon, May 25, 2009 at 2:04 AM, Fabian Giesen <f.g...@49...> wrote:
>> Without scaling this seems to be an odd request... as what defines any
>> one fit better then another, so long as the polygon does fit within
>> the quad, there lacks a metric for "best" as any fit will take the
>> same area and have the same excess area.
>
> Same goes for scaling though - just let the scaling factor run towards 0
> and your metric will look better and better.
>
> -Fabian Giesen
>
> ------------------------------------------------------------------------------
> Register Now for Creativity and Technology (CaT), June 3rd, NYC. CaT
> is a gathering of tech-side developers & brand creativity professionals. Meet
> the minds behind Google Creative Lab, Visual Complexity, Processing, &
> iPhoneDevCamp asthey present alongside digital heavyweights like Barbarian
> Group, R/GA, & Big Spaceship. http://www.creativitycat.com
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

Re: [Algorithms] Best fit of polygon inside another polygon

[Fabian G. <f.g...@49...>]

> Without scaling this seems to be an odd request... as what defines any
> one fit better then another, so long as the polygon does fit within
> the quad, there lacks a metric for "best" as any fit will take the
> same area and have the same excess area.

Same goes for scaling though - just let the scaling factor run towards 0 
and your metric will look better and better.

-Fabian Giesen

Re: [Algorithms] Best fit of polygon inside another polygon

[Nicholas \Indy\ R. <ar...@gm...>]

Without scaling this seems to be an odd request... as what defines any
one fit better then another, so long as the polygon does fit within
the quad, there lacks a metric for "best" as any fit will take the
same area and have the same excess area.

Indy

On Sun, May 24, 2009 at 3:52 PM, Stefan Dänzer <ste...@gm...> wrote:
> Sorry Jon, I stated the allowed transformations incorrectly in my last
> email. The following part:
> "The allowed transformations which can be applied to the polygon are
> translation and scaling"
> should read:
> The allowed transformations which can be applied to the polygon are
> translation and rotation."
> Sorry for the confusion.
>
> On Sun, May 24, 2009 at 6:42 PM, Jon Watte <jw...@gm...> wrote:
>>
>> Stefan Dänzer wrote:
>> > size. I have different polygons with varying shape and size and I want
>> > to find the polygon and according transformation of the polygon which
>> > best fits it into the given quad. The allowed transformations which
>> > can be applied to the polygon are translation and scaling.
>> >
>>
>> But you could just as easily try to fit the rectangle around the
>> polygon, using translation and rotation, and then just invert that
>> transform to go from polygon to rectangle.
>>
>> In general, I believe you can show that the optimal fit will have one
>> side of the polygon parallel with one side of the rectangle. If that is
>> indeed the case, a very straightforward algorithm (but slow) would be:
>>
>> foreach polygon:
>>  foreach side in the polygon
>>    for lengthwise and heightwise sides in rectangle
>>      translate and rotate polygon so that it fits as well as possible
>> with the polygon side snug to the rectangle side
>>      test whether fully inside, and calculate coverage
>>
>> Then pick the one with the best coverage value while being fully inside.
>> To calculate the "snug fit" you rotate the polygon to match the side to
>> the rectangle, rotate your frame of reference to make this side "right,"
>> and then slide it so that the uppermost vertex just touches the
>> uppermost side of the rectangle.
>>
>> Sincerely,
>>
>> jw
>>
>>
>>
>> ------------------------------------------------------------------------------
>> Register Now for Creativity and Technology (CaT), June 3rd, NYC. CaT
>> is a gathering of tech-side developers & brand creativity professionals.
>> Meet
>> the minds behind Google Creative Lab, Visual Complexity, Processing, &
>> iPhoneDevCamp asthey present alongside digital heavyweights like Barbarian
>> Group, R/GA, & Big Spaceship. http://www.creativitycat.com
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDA...@li...
>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> Archives:
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>
>
>
> --
> --
> Stefan Daenzer
> Körnerplatz 8
> 04107 Leipzig
>
> Tel.: +49-176-61157550
>
> "Work like you don't need the money, love like you've never been hurt and
> dance like no one is watching." - Randall G Leighton
>
> ------------------------------------------------------------------------------
> Register Now for Creativity and Technology (CaT), June 3rd, NYC. CaT
> is a gathering of tech-side developers & brand creativity professionals.
> Meet
> the minds behind Google Creative Lab, Visual Complexity, Processing, &
> iPhoneDevCamp asthey present alongside digital heavyweights like Barbarian
> Group, R/GA, & Big Spaceship. http://www.creativitycat.com
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

Re: [Algorithms] Best fit of polygon inside another polygon

[Jon W. <jw...@gm...>]

That's what I actually thought, so that's what I answered.

Sincerely,

jw

Stefan Dänzer wrote:
> Sorry Jon, I stated the allowed transformations incorrectly in my last 
> email. The following part:
>
> "The allowed transformations which can be applied to the polygon are 
> translation and scaling"
>
> should read:
>
> The allowed transformations which can be applied to the polygon are 
> translation and rotation."
>
> Sorry for the confusion.
>
> On Sun, May 24, 2009 at 6:42 PM, Jon Watte <jw...@gm... 
> <mailto:jw...@gm...>> wrote:
>
>     Stefan Dänzer wrote:
>     > size. I have different polygons with varying shape and size and
>     I want
>     > to find the polygon and according transformation of the polygon
>     which
>     > best fits it into the given quad. The allowed transformations which
>     > can be applied to the polygon are translation and scaling.
>     >
>
>     But you could just as easily try to fit the rectangle around the
>     polygon, using translation and rotation, and then just invert that
>     transform to go from polygon to rectangle.
>
>     In general, I believe you can show that the optimal fit will have one
>     side of the polygon parallel with one side of the rectangle. If
>     that is
>     indeed the case, a very straightforward algorithm (but slow) would be:
>
>     foreach polygon:
>      foreach side in the polygon
>        for lengthwise and heightwise sides in rectangle
>          translate and rotate polygon so that it fits as well as possible
>     with the polygon side snug to the rectangle side
>          test whether fully inside, and calculate coverage
>
>     Then pick the one with the best coverage value while being fully
>     inside.
>     To calculate the "snug fit" you rotate the polygon to match the
>     side to
>     the rectangle, rotate your frame of reference to make this side
>     "right,"
>     and then slide it so that the uppermost vertex just touches the
>     uppermost side of the rectangle.
>
>     Sincerely,
>
>     jw
>
>
>     ------------------------------------------------------------------------------
>     Register Now for Creativity and Technology (CaT), June 3rd, NYC. CaT
>     is a gathering of tech-side developers & brand creativity
>     professionals. Meet
>     the minds behind Google Creative Lab, Visual Complexity, Processing, &
>     iPhoneDevCamp asthey present alongside digital heavyweights like
>     Barbarian
>     Group, R/GA, & Big Spaceship. http://www.creativitycat.com
>     _______________________________________________
>     GDAlgorithms-list mailing list
>     GDA...@li...
>     <mailto:GDA...@li...>
>     https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>     Archives:
>     http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>
>
>
>
> -- 
> --
> Stefan Daenzer
> Körnerplatz 8
> 04107 Leipzig
>
> Tel.: +49-176-61157550
>
> "Work like you don't need the money, love like you've never been hurt 
> and dance like no one is watching." - Randall G Leighton
> ------------------------------------------------------------------------
>
> ------------------------------------------------------------------------------
> Register Now for Creativity and Technology (CaT), June 3rd, NYC. CaT
> is a gathering of tech-side developers & brand creativity professionals. Meet
> the minds behind Google Creative Lab, Visual Complexity, Processing, & 
> iPhoneDevCamp asthey present alongside digital heavyweights like Barbarian
> Group, R/GA, & Big Spaceship. http://www.creativitycat.com 
> ------------------------------------------------------------------------
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] Best fit of polygon inside another polygon

[Stefan D. <ste...@gm...>]

Sorry Jon, I stated the allowed transformations incorrectly in my last
email. The following part:
"The allowed transformations which can be applied to the polygon are
translation and scaling"

should read:

The allowed transformations which can be applied to the polygon are
translation and rotation."

Sorry for the confusion.

On Sun, May 24, 2009 at 6:42 PM, Jon Watte <jw...@gm...> wrote:

> Stefan Dänzer wrote:
> > size. I have different polygons with varying shape and size and I want
> > to find the polygon and according transformation of the polygon which
> > best fits it into the given quad. The allowed transformations which
> > can be applied to the polygon are translation and scaling.
> >
>
> But you could just as easily try to fit the rectangle around the
> polygon, using translation and rotation, and then just invert that
> transform to go from polygon to rectangle.
>
> In general, I believe you can show that the optimal fit will have one
> side of the polygon parallel with one side of the rectangle. If that is
> indeed the case, a very straightforward algorithm (but slow) would be:
>
> foreach polygon:
>  foreach side in the polygon
>    for lengthwise and heightwise sides in rectangle
>      translate and rotate polygon so that it fits as well as possible
> with the polygon side snug to the rectangle side
>      test whether fully inside, and calculate coverage
>
> Then pick the one with the best coverage value while being fully inside.
> To calculate the "snug fit" you rotate the polygon to match the side to
> the rectangle, rotate your frame of reference to make this side "right,"
> and then slide it so that the uppermost vertex just touches the
> uppermost side of the rectangle.
>
> Sincerely,
>
> jw
>
>
>
> ------------------------------------------------------------------------------
> Register Now for Creativity and Technology (CaT), June 3rd, NYC. CaT
> is a gathering of tech-side developers & brand creativity professionals.
> Meet
> the minds behind Google Creative Lab, Visual Complexity, Processing, &
> iPhoneDevCamp asthey present alongside digital heavyweights like Barbarian
> Group, R/GA, & Big Spaceship. http://www.creativitycat.com
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>



-- 
--
Stefan Daenzer
Körnerplatz 8
04107 Leipzig

Tel.: +49-176-61157550

"Work like you don't need the money, love like you've never been hurt and
dance like no one is watching." - Randall G Leighton

Re: [Algorithms] Best fit of polygon inside another polygon

[Osman, B. <BO...@vv...>]

So what's your precise metric for "best fit"? Earlier you mentioned the area of the polygon that doesn't fit into the quad... But if scale (even uniform scale) is a permitted transformation then that must only be part of the metric. It's trivial to scale all polygons down to a point, such that they all fit perfectly into ANY quadrilateral.

-Brian

-----Original Message-----
From: Stefan Dänzer [mailto:ste...@gm...] 
Sent: Saturday, May 23, 2009 12:08 PM
To: Game Development Algorithms
Subject: Re: [Algorithms] Best fit of polygon inside another polygon

Hi Emil,

that's not exactly the problem I am trying to solve. Maybe I have
stated it incorrectly. In my case the surrounding quad is of fixed
size. I have different polygons with varying shape and size and I want
to find the polygon and according transformation of the polygon which
best fits it into the given quad. The allowed transformations which
can be applied to the polygon are translation and scaling.

regards,

Stefan

On Fri, May 22, 2009 at 8:27 PM, Emil Persson <hu...@co...> wrote:
> I'm tired and I have a headache, but if I understand your problem right then
> it sounds like a special case of a problem I just solved last night and
> wrote a tool for:
>
> http://www.humus.name/index.php?page=News&ID=266
>
>
>
> So you'd just input your polygon directly (instead of inputting a particle
> texture and generate a polygon from that) and optimize for 4 vertices and
> that would solve it, no?
>
>
>
> -Emil
>
>
>
>
>
> From: Ste...@gm... [mailto:Ste...@gm...]
> Sent: 22 May 2009 14:59
> To: Game Development Algorithms
> Subject: [Algorithms] Best fit of polygon inside another polygon
>
>
>
> Hi,
>
> I've been thinking about an algorithm which fits a given polygon into a
> quad. I've stumbled upon this while trying to fit the largest possible
> polygon out of a set of different polygons into a quadliteral. What I want
> to find is the best-fit-polygon which can be contained completely in the
> quadliteral. The polygon and quad can be assumed to be convex. An nice
> feature would be to calculate the error as a function of the area which
> doesn't fit into the quad for every polygon I throw at the quad.
>
> I'm working in 2D right now, but might want to expand the problem for a
> later application into a 3D case (fit a polyhedra into a hexahedron).
>
> Any ideas how to solve this problem?
>
> Stefan
>
> ------------------------------------------------------------------------------
> Register Now for Creativity and Technology (CaT), June 3rd, NYC. CaT
> is a gathering of tech-side developers & brand creativity professionals.
> Meet
> the minds behind Google Creative Lab, Visual Complexity, Processing, &
> iPhoneDevCamp asthey present alongside digital heavyweights like Barbarian
> Group, R/GA, & Big Spaceship. http://www.creativitycat.com
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>



-- 
--
Stefan Daenzer
Körnerplatz 8
04107 Leipzig

Tel.: +49-176-61157550

"Work like you don't need the money, love like you've never been hurt
and dance like no one is watching." - Randall G Leighton

------------------------------------------------------------------------------
Register Now for Creativity and Technology (CaT), June 3rd, NYC. CaT
is a gathering of tech-side developers & brand creativity professionals. Meet
the minds behind Google Creative Lab, Visual Complexity, Processing, & 
iPhoneDevCamp asthey present alongside digital heavyweights like Barbarian
Group, R/GA, & Big Spaceship. http://www.creativitycat.com 
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] Best fit of polygon inside another polygon

[Jon W. <jw...@gm...>]

Stefan Dänzer wrote:
> size. I have different polygons with varying shape and size and I want
> to find the polygon and according transformation of the polygon which
> best fits it into the given quad. The allowed transformations which
> can be applied to the polygon are translation and scaling.
>   

But you could just as easily try to fit the rectangle around the 
polygon, using translation and rotation, and then just invert that 
transform to go from polygon to rectangle.

In general, I believe you can show that the optimal fit will have one 
side of the polygon parallel with one side of the rectangle. If that is 
indeed the case, a very straightforward algorithm (but slow) would be:

foreach polygon:
  foreach side in the polygon
    for lengthwise and heightwise sides in rectangle
      translate and rotate polygon so that it fits as well as possible 
with the polygon side snug to the rectangle side
      test whether fully inside, and calculate coverage

Then pick the one with the best coverage value while being fully inside.
To calculate the "snug fit" you rotate the polygon to match the side to 
the rectangle, rotate your frame of reference to make this side "right," 
and then slide it so that the uppermost vertex just touches the 
uppermost side of the rectangle.

Sincerely,

jw

Re: [Algorithms] Best fit of polygon inside another polygon

[Stefan D. <ste...@gm...>]

Hi Emil,

that's not exactly the problem I am trying to solve. Maybe I have
stated it incorrectly. In my case the surrounding quad is of fixed
size. I have different polygons with varying shape and size and I want
to find the polygon and according transformation of the polygon which
best fits it into the given quad. The allowed transformations which
can be applied to the polygon are translation and scaling.

regards,

Stefan

On Fri, May 22, 2009 at 8:27 PM, Emil Persson <hu...@co...> wrote:
> I’m tired and I have a headache, but if I understand your problem right then
> it sounds like a special case of a problem I just solved last night and
> wrote a tool for:
>
> http://www.humus.name/index.php?page=News&ID=266
>
>
>
> So you’d just input your polygon directly (instead of inputting a particle
> texture and generate a polygon from that) and optimize for 4 vertices and
> that would solve it, no?
>
>
>
> -Emil
>
>
>
>
>
> From: Ste...@gm... [mailto:Ste...@gm...]
> Sent: 22 May 2009 14:59
> To: Game Development Algorithms
> Subject: [Algorithms] Best fit of polygon inside another polygon
>
>
>
> Hi,
>
> I've been thinking about an algorithm which fits a given polygon into a
> quad. I've stumbled upon this while trying to fit the largest possible
> polygon out of a set of different polygons into a quadliteral. What I want
> to find is the best-fit-polygon which can be contained completely in the
> quadliteral. The polygon and quad can be assumed to be convex. An nice
> feature would be to calculate the error as a function of the area which
> doesn't fit into the quad for every polygon I throw at the quad.
>
> I'm working in 2D right now, but might want to expand the problem for a
> later application into a 3D case (fit a polyhedra into a hexahedron).
>
> Any ideas how to solve this problem?
>
> Stefan
>
> ------------------------------------------------------------------------------
> Register Now for Creativity and Technology (CaT), June 3rd, NYC. CaT
> is a gathering of tech-side developers & brand creativity professionals.
> Meet
> the minds behind Google Creative Lab, Visual Complexity, Processing, &
> iPhoneDevCamp asthey present alongside digital heavyweights like Barbarian
> Group, R/GA, & Big Spaceship. http://www.creativitycat.com
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>



-- 
--
Stefan Daenzer
Körnerplatz 8
04107 Leipzig

Tel.: +49-176-61157550

"Work like you don't need the money, love like you've never been hurt
and dance like no one is watching." - Randall G Leighton

Re: [Algorithms] Best fit of polygon inside another polygon

[Emil P. <hu...@co...>]

I'm tired and I have a headache, but if I understand your problem right then
it sounds like a special case of a problem I just solved last night and
wrote a tool for:

http://www.humus.name/index.php?page=News
<http://www.humus.name/index.php?page=News&ID=266> &ID=266

 

So you'd just input your polygon directly (instead of inputting a particle
texture and generate a polygon from that) and optimize for 4 vertices and
that would solve it, no?

 

-Emil

 

 

From: Ste...@gm... [mailto:Ste...@gm...] 
Sent: 22 May 2009 14:59
To: Game Development Algorithms
Subject: [Algorithms] Best fit of polygon inside another polygon

 

Hi,

I've been thinking about an algorithm which fits a given polygon into a
quad. I've stumbled upon this while trying to fit the largest possible
polygon out of a set of different polygons into a quadliteral. What I want
to find is the best-fit-polygon which can be contained completely in the
quadliteral. The polygon and quad can be assumed to be convex. An nice
feature would be to calculate the error as a function of the area which
doesn't fit into the quad for every polygon I throw at the quad.

I'm working in 2D right now, but might want to expand the problem for a
later application into a 3D case (fit a polyhedra into a hexahedron). 

Any ideas how to solve this problem?

Stefan

Re: [Algorithms] Best fit of polygon inside another polygon

[Robin G. <rob...@gm...>]

On Fri, May 22, 2009 at 8:41 AM, Peter Lipson <pe...@to...> wrote:

> sounds like a question from one of my take-home final exams....
>
>
Welcome to the world of R&D, where it's like taking an exam every day of the
week.
Only there are no right answers, no scores at the end, and it's not clear
whether the question is even possible.

- R.

Re: [Algorithms] Best fit of polygon inside another polygon

[Peter L. <pe...@to...>]

sounds like a question from one of my take-home final exams....

Ste...@gm... wrote:
> Hi,
>
> I've been thinking about an algorithm which fits a given polygon into 
> a quad. I've stumbled upon this while trying to fit the largest 
> possible polygon out of a set of different polygons into a 
> quadliteral. What I want to find is the best-fit-polygon which can be 
> contained completely in the quadliteral. The polygon and quad can be 
> assumed to be convex. An nice feature would be to calculate the error 
> as a function of the area which doesn't fit into the quad for every 
> polygon I throw at the quad.
>
> I'm working in 2D right now, but might want to expand the problem for 
> a later application into a 3D case (fit a polyhedra into a hexahedron).
>
> Any ideas how to solve this problem?
>
> Stefan
> ------------------------------------------------------------------------
>
> ------------------------------------------------------------------------------
> Register Now for Creativity and Technology (CaT), June 3rd, NYC. CaT
> is a gathering of tech-side developers & brand creativity professionals. Meet
> the minds behind Google Creative Lab, Visual Complexity, Processing, & 
> iPhoneDevCamp asthey present alongside digital heavyweights like Barbarian
> Group, R/GA, & Big Spaceship. http://www.creativitycat.com 
> ------------------------------------------------------------------------
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] Best fit of polygon inside another polygon

[Fabian G. <f.g...@49...>]

Ste...@gm... wrote:
> Hi,
> 
> I've been thinking about an algorithm which fits a given polygon into a 
> quad. I've stumbled upon this while trying to fit the largest possible 
> polygon out of a set of different polygons into a quadliteral. What I 
> want to find is the best-fit-polygon which can be contained completely 
> in the quadliteral. The polygon and quad can be assumed to be convex. An 
> nice feature would be to calculate the error as a function of the area 
> which doesn't fit into the quad for every polygon I throw at the quad.
> 
> I'm working in 2D right now, but might want to expand the problem for a 
> later application into a 3D case (fit a polyhedra into a hexahedron).
> 
> Any ideas how to solve this problem?
> 
> Stefan

Which transformations are allowed? "Only translations", "translations 
and rotations", "translations, rotations and uniform scaling" and 
"general affine transformation" are all sensible choices but lead to 
very different approaches.

Also, is the quad a general convex quad, or is it a rectangle or 
parallelogram?

Kind regards,
-Fabian Giesen

[Algorithms] Best fit of polygon inside another polygon

[<Ste...@gm...>]

Hi,

I've been thinking about an algorithm which fits a given polygon into a  
quad. I've stumbled upon this while trying to fit the largest possible  
polygon out of a set of different polygons into a quadliteral. What I want  
to find is the best-fit-polygon which can be contained completely in the  
quadliteral. The polygon and quad can be assumed to be convex. An nice  
feature would be to calculate the error as a function of the area which  
doesn't fit into the quad for every polygon I throw at the quad.

I'm working in 2D right now, but might want to expand the problem for a  
later application into a 3D case (fit a polyhedra into a hexahedron).

Any ideas how to solve this problem?

Stefan

Re: [Algorithms] Leafy BSP Tree Contruction

[<chr...@pl...>]

Manolache Adrian wrote:

> I checked and there are a lot of cases when vertices are very close to
> a lot of planes, and this causes problems when splitting with these
> planes.

If the vertex is sufficiently close to a plane it should
be considered ON the plane; this is what it meant by a
fat/thick plane.

It sounds to me that you might not be correctly handling
the thick planes.

The introduction of thick planes changes not only how you
clip/split polygons to the plane but also how you classify
polygons w.r.t. being in front/on/behind the plane.

You can find a short outline of the problems in my GDC
lecture on robustness:

http://realtimecollisiondetection.net/pubs/

There's a lot more detail in my book on both splitting
and classifying to thick planes (pp 364-373).


Christer Ericson, Director of Tools and Technology
Sony Computer Entertainment, Santa Monica
http://realtimecollisiondetection.net/blog/

Re: [Algorithms] Leafy BSP Tree Contruction

[Manolache A. <pro...@ya...>]

The bsp construction is part of a bigger application. Actually it's part of my bachelor's thesis. I chose to implement among others a full BSP PVS 3D engine.This translates in the construction of a solid node leafy bsp tree, automatic portal generation and finally the pvs calculation, rle encoded and further a merge between coplanar adjiacent polygons in every leaf. As a plus i also implemented a portal renderer using the automatically generated portals(it's not lightning fast due to the big number of portals but it was fun to do). 
The BSP/PVS 3D engine works flawlessly until now on 3 levels with tri counts ranging from 1000 to 6000. It seems i have to tweak the EPSILON used when clipping and classifying. I found that an epsilon of 0.01 works well on these three levels because of the range of values in them. The problem arises on the 4th level that has about 15000 triangles on which the construction of the bsp tree fails. I checked and there are a lot of cases when vertices are very close to a lot of planes, and this causes problems when splitting with these planes. The construction of the bsp tree fails because polygons like this one arrive in a back leaf and being used as a splitter in the past:
(-29.467429, 91.150700, -145.998993)
(-29.500788, 91.204792, -146.329036)
(-29.500788, 91.151931, -145.998993)
I have run of ideas trying to tweak the epsilon for this level.

Implementation details:
1.0 Every clipped polygon inherits the normal of the initial polygon
2.0 When clipping edges, Intersection points are calculated in a consistent manner (from front of the plane to back, all the time).
3.0 I treat the planes as being fat.

4.0' I'm using doubles when performing calculations.

I am not quite sure how to tackle the other two things mentioned by Chris (4 and 5).  

> Overall though, WHY are you using a BSP tree?  There are
> some valid uses for them, but for a lot of applications
> they are a bad choice of data structure!

One of my favorite games was quake and i wanted to explore similar techniques used by it and second of all i believe these approaches(or a modification of them) may still be useful on less powerful machines (handheld devices) when dealing with interior, dungeon like environments. I would guess that nowadays portal engines are the norm for interior environments(with portals placed by the artists).



      

Re: [Algorithms] Leafy BSP Tree Contruction

[<chr...@pl...>]

You have to be very careful about the robustness of your
floating-point calculations when working with BSP-trees.

Adrian mentioned several things already, but to summarize:

1. Wherever possible refer back to the original polygon
   instead of the pieces clipped from it. Certainly for
   obtaining the normal.
2. Always clip edges in a consistent direction wrt. a
   plane; e.g. direct the edges to always go into the
   plane befoer you clip.
3. Treat the planes as if they are fat (have thickness).
4. Move your calculations to the origin to retain as
   much precision as possible.
5. Insert objects conservatively into the tree (duplicating
   data if necessary).

Overall though, WHY are you using a BSP tree?  There are
some valid uses for them, but for a lot of applications
they are a bad choice of data structure!

Christer Ericson, Director of Tools and Technology
Sony Computer Entertainment, Santa Monica



                                                                           
             Adrian Bentley                                                
             <ad...@gm...                                             
             >                                                          To 
                                       Game Development Algorithms         
             05/19/2009 09:29          <gda...@li... 
             PM                        e.net>                              
                                                                        cc 
                                                                           
             Please respond to                                     Subject 
             Game Development          Re: [Algorithms] Leafy BSP Tree     
                Algorithms             Contruction                         
             <gdalgorithms-lis                                             
             t...@li...                                             
                  ge.net>                                                  
                                                                           
                                                                           
                                                                           




I seem to remember a thread about this, try searching the archives
(you might need to search Sweng Gamedev too).

One thing important for good results is to generate the plane from the
source triangle and just reference it from all polygons split from
that triangle, that way splitting doesn't dirty your plane equation.
Try combining that with penalizing splitting planes with other
parallel triangles and higher precision math.

Also, Real Time Collision Detection contains a some good guidelines on
"fat" bsp construction (using epsilons and such).  IIRC the key
involves treating transitions from/to side A/B and On in a logically
consistent way so slivers are never created.  You can probably derive
them yourself, but it does take lots of diagrams and brain mangling
about degenerate cases.

Cheers,
Adrian

On Tue, May 19, 2009 at 12:01 PM, Manolache Adrian <pro...@ya...>
wrote:
>              During the bsp tree compilation there happens sometimes that
a
> polygon would be split so much until it becomes very thin with an area
> almost 0. This polygon would further be split and thus obtaining
degenerate
> triangles. The problem is that the construction fails when fed this kind
of
> polygons and full leaves(all polygons used as splitter) arive in back
nodes.
> When clipping triangles or classifying them i used a small epsilon to
> compare to 0(absolute tolerance test). How can i go around avoiding
> degenerate triangle creation, how can these be handled? Is it the sole
duty
> of the artist to avoid such cases?
>
>
------------------------------------------------------------------------------

> Crystal Reports - New Free Runtime and 30 Day Trial
> Check out the new simplified licensing option that enables
> unlimited royalty-free distribution of the report engine
> for externally facing server and web deployment.
> http://p.sf.net/sfu/businessobjects
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

------------------------------------------------------------------------------

Crystal Reports - New Free Runtime and 30 Day Trial
Check out the new simplified licensing option that enables
unlimited royalty-free distribution of the report engine
for externally facing server and web deployment.
http://p.sf.net/sfu/businessobjects
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] Leafy BSP Tree Contruction

[Adrian B. <ad...@gm...>]

I seem to remember a thread about this, try searching the archives
(you might need to search Sweng Gamedev too).

One thing important for good results is to generate the plane from the
source triangle and just reference it from all polygons split from
that triangle, that way splitting doesn't dirty your plane equation.
Try combining that with penalizing splitting planes with other
parallel triangles and higher precision math.

Also, Real Time Collision Detection contains a some good guidelines on
"fat" bsp construction (using epsilons and such).  IIRC the key
involves treating transitions from/to side A/B and On in a logically
consistent way so slivers are never created.  You can probably derive
them yourself, but it does take lots of diagrams and brain mangling
about degenerate cases.

Cheers,
Adrian

On Tue, May 19, 2009 at 12:01 PM, Manolache Adrian <pro...@ya...> wrote:
>              During the bsp tree compilation there happens sometimes that a
> polygon would be split so much until it becomes very thin with an area
> almost 0. This polygon would further be split and thus obtaining degenerate
> triangles. The problem is that the construction fails when fed this kind of
> polygons and full leaves(all polygons used as splitter) arive in back nodes.
> When clipping triangles or classifying them i used a small epsilon to
> compare to 0(absolute tolerance test). How can i go around avoiding
> degenerate triangle creation, how can these be handled? Is it the sole duty
> of the artist to avoid such cases?
>
> ------------------------------------------------------------------------------
> Crystal Reports - New Free Runtime and 30 Day Trial
> Check out the new simplified licensing option that enables
> unlimited royalty-free distribution of the report engine
> for externally facing server and web deployment.
> http://p.sf.net/sfu/businessobjects
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>