## gdalgorithms-list

 [Algorithms] Best fit of polygon inside another polygon From: - 2009-05-22 12:58:57 Attachments: Message as HTML ```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 From: Fabian Giesen - 2009-05-22 13:15:13 ```Stefan.Daenzer@... 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 ```
 Re: [Algorithms] Best fit of polygon inside another polygon From: Peter Lipson - 2009-05-22 16:08:17 ```sounds like a question from one of my take-home final exams.... Stefan.Daenzer@... 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 > GDAlgorithms-list@... > 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 From: Robin Green - 2009-05-22 17:33:41 Attachments: Message as HTML ```On Fri, May 22, 2009 at 8:41 AM, Peter Lipson 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 From: Emil Persson - 2009-05-22 18:28:31 Attachments: Message as HTML ```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: Stefan.Daenzer@... [mailto:Stefan.Daenzer@...] 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 From: Stefan Dänzer - 2009-05-23 16:08:52 ```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 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: Stefan.Daenzer@... [mailto:Stefan.Daenzer@...] > 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 > GDAlgorithms-list@... > 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 From: Jon Watte - 2009-05-24 16:42:21 ```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 From: Stefan Dänzer - 2009-05-24 22:53:11 Attachments: Message as HTML ```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 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 > GDAlgorithms-list@... > 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 From: Jon Watte - 2009-05-25 03:02:26 ```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 > 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 > GDAlgorithms-list@... > > 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 > GDAlgorithms-list@... > 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 From: Nicholas \Indy\ Ray - 2009-05-25 03:23:15 ```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 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 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 >> GDAlgorithms-list@... >> 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 > GDAlgorithms-list@... > 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 From: Peter Lipson - 2009-05-26 15:33:01 ```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 From: Peter Lipson - 2009-05-26 15:36:29 ```-- 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 From: Osman, Brian - 2009-05-24 17:20:57 ```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:stefan.daenzer@...] 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 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: Stefan.Daenzer@... [mailto:Stefan.Daenzer@...] > 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 > GDAlgorithms-list@... > 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 GDAlgorithms-list@... 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 From: Fabian Giesen - 2009-05-25 09:04:18 ```> 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 From: Nicholas \Indy\ Ray - 2009-05-25 21:34:12 ```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 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 > GDAlgorithms-list@... > 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 From: Fabian Giesen - 2009-05-26 15:46:17 ```> 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 From: Jon Watte - 2009-05-27 04:52:52 ```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 ```
 [Algorithms] Thermal infrared techniques? From: Ron Hay - 2009-05-28 14:13:42 ```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] Thermal infrared techniques? From: Andy Finkenstadt - 2009-05-28 15:07:51 ```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 ```
 Re: [Algorithms] Thermal infrared techniques? From: Jon Watte - 2009-05-28 19:16:52 ```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? From: Ron Hay - 2009-05-28 20:15:40 ```Thanks for the response - to answer some questions, it's the "colorful" variant of IR that's probably going to be emulated. They additionally want night vision (which is an easier effect, in general). I'm looking for a bit more than a different set of textures, which is, as Jon stated, pretty much all they have been doing. We want to do it better, so I was try to edu-macate myself on some other possibilities using "modern" (aka "not 10 years old") hardware. Some of the ideas you through out are a good start Jon :) Ron Jon Watte wrote: > 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 > > ------------------------------------------------------------------------------ > 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 > GDAlgorithms-list@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > ```
 Re: [Algorithms] Thermal infrared techniques? From: Jon Watte - 2009-05-29 16:01:27 ```Ron Hay wrote: > stated, pretty much all they have been doing. We want to do it better, > so I was try to edu-macate myself on some other possibilities using > "modern" (aka "not 10 years old") hardware. Some of the ideas you > through out are a good start Jon :) > The "colorful" IR is simply a palette map at the end of the shader. Once you have "intensity" then you map that to the S texture coordinate of a color ramp texture, and out comes the display color. Depending on which piece of hardware you want to emulate, typically you apply bloom BEFORE the palettization, which means you need some render target ping-pong-ing. Sincerely, jw ```
 [Algorithms] Formula for Damping f times From: Zafar Qamar - 2009-06-05 10:08:14 ```Hi, This is a semi-trivial but I can't quite remember the answer, even though I've done it before. I have an update function sort of like this.. void updateX( float deltaTime) { x = x*k; } k is a constant less than 1.0. Now to do the damping properly I need to perform "x=x*k" deltaTime times, where deltaTime is a fraction. Can anyone help with this please? I recall it just being a log or something. Cheers Zafar Qamar ********************************************************************************** Disclaimer The information and attached documentation in this e-mail is intended for the use of the addressee only and is confidential. If you are not the intended recipient please delete it and notify us immediately by telephoning or e-mailing the sender. Please note that without Codemasters’ prior written consent any form of distribution, copying or use of this communication or the information in it is strictly prohibited and may be unlawful. Attachments to this e-mail may contain software viruses. You are advised to take all reasonable precautions to minimise this risk and to carry out a virus check on any documents before they are opened. Any offer contained in this communication is subject to Codemasters’ standard terms & conditions and must be signed by both parties. Except as expressly provided otherwise all information and attached documentation in this e-mail is subject to contract and Codemasters’ board approval. Any views or opinions expressed are solely those of the author and do not necessarily represent those of Codemasters. This footnote also confirms that this email message has been swept by SurfControl for the presence of computer viruses. ********************************************************************************** ```
 Re: [Algorithms] Formula for Damping f times From: Fabian Giesen - 2009-06-05 10:21:37 ```> Hi, > This is a semi-trivial but I can't quite remember the answer, even > though I've done it before. > > I have an update function sort of like this.. > > void updateX( float deltaTime) > { > x = x*k; > } > > k is a constant less than 1.0. > > Now to do the damping properly I need to perform "x=x*k" deltaTime > times, where deltaTime is a fraction. > > Can anyone help with this please? I recall it just being a log or > something. x *= pow(k,deltaTime); Kind regards, -Fabian Giesen ```
 Re: [Algorithms] Formula for Damping f times From: - 2009-06-05 10:31:24 ```-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 > Hi, > This is a semi-trivial but I can't quite remember the answer, even > though I've done it before. > > I have an update function sort of like this.. > > void updateX( float deltaTime) > { > x = x*k; > } > > k is a constant less than 1.0. > > Now to do the damping properly I need to perform "x=x*k" deltaTime > times, where deltaTime is a fraction. > > Can anyone help with this please? I recall it just being a log or > something. We just do something very simple: x *= 1.0f-(k*deltaTime); So k = 1 = damped to zero velocity over 1 second at 30fps. Cheers, Paul. ********************************************************************** This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify postmaster@... This footnote also confirms that this email message has been checked for all known viruses. Sony Computer Entertainment Europe Limited Registered Office: 10 Great Marlborough Street, London W1F 7LP, United Kingdom Registered in England: 3277793 ********************************************************************** P Please consider the environment before printing this e-mail -----BEGIN PGP SIGNATURE----- Version: PGP Universal 2.9.1 (Build 287) Charset: US-ASCII wsBVAwUBSijz83ajGqjtoMHxAQh+mwgAgByk+DsOHJIg2O411+jQwAialPE3VZ7x QMb1t6mG2Ujx8niel3gT9u1PoGEMNiV1rjAvV2O9mCeGgEI4NE9ZDcgB3JF9DJbB eq/lNz/EJDaL+deC8wYyyW5TGJoTKW5fz2WvpYmia0RniH1wuLDmjQJR0d2aGbIM knI7FpZVEDjMtRvK5nwGJNWkoaiBInSTLJ3+rYrZbtVxeC0AVPgp4lrPL9zGQmpE M8CKMs67cwn7xZJnJOTqfdAbnavapIxSvDtAZBDNB7Ba/kX552mv0E+0nMgj4bzC 9ft1PoF+05psOXKvCGJXDX3uVpJSJM9OL3SVfC57i114dnDsgfiNTA== =tza9 -----END PGP SIGNATURE----- ```
1 2 > >> (Page 1 of 2)