gdalgorithms-list

[Algorithms] Res: Simple algorithm for regular polygon union

[Jose M. <jos...@ya...>]

Thank you very much, Eric!
Very usefull tips...




________________________________
De: Eric Haines <eri...@gm...>
Para: Game Development Algorithms <gda...@li...>
Enviadas: Terça-feira, 5 de Maio de 2009 15:03:04
Assunto: Re: [Algorithms] Simple algorithm for regular polygon union

[Trying again, since I moved my email address and my reply got filtered out.]
I don't know of a "stripped down" union library for this particular problem.

It sounds like you've already found some of these, but the best page I know that lists a few 2D polygon union packages is the one linked from Jeremy's: http://www.cs.man.ac.uk/~toby/alan/software/links.html. Eberly's had the least restrictive licensing, though wasn't particularly efficient (but gave solid results - he uses exact integer arithmetic). I've used this package in shipping software, it works well. I found most of the other packages listed had "For non-commercial use only" or other limitations, which was annoying. 

The Eberly link from the GPC page is broken, and you'll have to dig on Eberly's site a bit for the code:

Classes here, and paper on his algorithm at the bottom: http://www.geometrictools.com/LibFoundation/ComputationalGeometry/ComputationalGeometry.html

Actual code here: http://www.geometrictools.com/SampleFoundation/Boolean2D/Boolean2D.html


Eric


On Tue, May 5, 2009 at 1:48 PM, Jeremy <jsw...@gm...> wrote:

Something like this? http://www.cs.man.ac.uk/~toby/alan/software/gpc.html 




On Tue, May 5, 2009 at 9:30 AM, Jose Marin <jos...@ya...> wrote:


Hi,

I have found some libraries in the net to perform polygon operations, but I need a very simple one: union of closed convex polygons.


      Veja quais são os assuntos do momento no Yahoo! +Buscados
http://br.maisbuscados.yahoo.com

Re: [Algorithms] Simple algorithm for regular polygon union

[Eric H. <eri...@gm...>]

[Trying again, since I moved my email address and my reply got filtered
out.]

I don't know of a "stripped down" union library for this particular problem.

It sounds like you've already found some of these, but the best page I know
that lists a few 2D polygon union packages is the one linked from Jeremy's:
http://www.cs.man.ac.uk/~toby/alan/software/links.html. Eberly's had the
least restrictive licensing, though wasn't particularly efficient (but gave
solid results - he uses exact integer arithmetic). I've used this package in
shipping software, it works well. I found most of the other packages listed
had "For non-commercial use only" or other limitations, which was annoying.
The Eberly link from the GPC page is broken, and you'll have to dig on
Eberly's site a bit for the code:

Classes here, and paper on his algorithm at the bottom:
http://www.geometrictools.com/LibFoundation/ComputationalGeometry/ComputationalGeometry.html

Actual code here:
http://www.geometrictools.com/SampleFoundation/Boolean2D/Boolean2D.html

Eric

On Tue, May 5, 2009 at 1:48 PM, Jeremy <jsw...@gm...> wrote:

> Something like this? http://www.cs.man.ac.uk/~toby/alan/software/gpc.html
>
>
>
> On Tue, May 5, 2009 at 9:30 AM, Jose Marin <jos...@ya...>wrote:
>
>>
>> Hi,
>>
>> I have found some libraries in the net to perform polygon operations, but
>> I need a very simple one: union of closed convex polygons.
>>
>

[Algorithms] Res: Simple algorithm for regular polygon union

[Jose M. <jos...@ya...>]

Yes, but looks like that lib have some restrictions for commercial use.




________________________________
De: Jeremy <jsw...@gm...>
Para: Game Development Algorithms <gda...@li...>
Enviadas: Terça-feira, 5 de Maio de 2009 14:48:13
Assunto: Re: [Algorithms] Simple algorithm for regular polygon union

Something like this? http://www.cs.man.ac.uk/~toby/alan/software/gpc.html



On Tue, May 5, 2009 at 9:30 AM, Jose Marin <jos...@ya...> wrote:


Hi,

I have found some libraries in the net to perform polygon operations, but I need a very simple one: union of closed convex polygons.

Do you know any?

Thank you.

Jose


     Veja quais são os assuntos do momento no Yahoo! +Buscados
http://br.maisbuscados.yahoo.com

------------------------------------------------------------------------------
The NEW KODAK i700 Series Scanners deliver under ANY circumstances! Your
production scanning environment may not be a perfect world - but thanks to
Kodak, there's a perfect scanner to get the job done! With the NEW KODAK i700
Series Scanner you'll get full speed at 300 dpi even with all image
processing features enabled. http://p.sf.net/sfu/kodak-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


      Veja quais são os assuntos do momento no Yahoo! +Buscados
http://br.maisbuscados.yahoo.com

Re: [Algorithms] Simple algorithm for regular polygon union

[Jeremy <jsw...@gm...>]

Something like this? http://www.cs.man.ac.uk/~toby/alan/software/gpc.html


On Tue, May 5, 2009 at 9:30 AM, Jose Marin <jos...@ya...> wrote:

>
> Hi,
>
> I have found some libraries in the net to perform polygon operations, but I
> need a very simple one: union of closed convex polygons.
>
> Do you know any?
>
> Thank you.
>
> Jose
>
>
>      Veja quais são os assuntos do momento no Yahoo! +Buscados
> http://br.maisbuscados.yahoo.com
>
>
> ------------------------------------------------------------------------------
> The NEW KODAK i700 Series Scanners deliver under ANY circumstances! Your
> production scanning environment may not be a perfect world - but thanks to
> Kodak, there's a perfect scanner to get the job done! With the NEW KODAK
> i700
> Series Scanner you'll get full speed at 300 dpi even with all image
> processing features enabled. http://p.sf.net/sfu/kodak-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
>

[Algorithms] Simple algorithm for regular polygon union

[Jose M. <jos...@ya...>]

Hi,

I have found some libraries in the net to perform polygon operations, but I need a very simple one: union of closed convex polygons.

Do you know any?

Thank you.

Jose


      Veja quais são os assuntos do momento no Yahoo! +Buscados
http://br.maisbuscados.yahoo.com

Re: [Algorithms] Undershooting in spherical harmonics generated bycubemap convolution

[Alen L. <ale...@cr...>]

Sam wrote at 5/5/2009:
> I'm not quite sure what you mean by diffuse radiance?
Eh, sorry. This radiometry terminology always gets somehow mixed up in
my head. :) I was refering to irradiance, whereas I think that method of
testing would work e.g. for incoming radiance.

> If you start with a SH function in a cube map (say, an L1 term),
> "do your thing" to get it into SH, and then regenerate a cube map
> (or similar) from your generated SH data you can still check whether
> it's correct as the end result should just be a scaled version of
> the original. The scaling should depend on which of the 3 of the
> above you are working with in the "do your thing" step.

Am I wrong to think that the difference is not just a scaler in some
of those cases? When trying to get irradiance SH from a cubemap which
represents radiance, I'm convolving not just by the SH, but also by
clamped cosine. When convolving with cosine, I'm effectively
generating a "blurry" SH from a "non-blurry" cubemap. Converting that
"blurry" SH into a cubemap will generate a "blurry" cubemap, which
cannot be easily compared to the "non-blurry" original (save for doing
O(P^2) convolution in the cubemap space and comparing to that).

I'm not very proficient with SHs, so it's all a bit hand-wavy on my
side, but... Such test passes if I use the c0-c4 coefficients as
intended for irradiance (without the 2/3 and 1/4 parts), but not if
I use the coefficients that incorporate cosine convolution (those with
2/3 and 1/4). This leads me to believe that my hunch makes sense.

Granted, I could generate a cubemap from synthetic SHs, convolve them
back and check that the result is exactly different by the 2/3 and 1/4
factors in the correct places. But I fear it kind of defeats the
purpose of testing.

> If it's radiance it should be exactly the same, if it's irradiance
> it should be scaled by the cosine terms (see the ramamoorthi paper)
> and if it's exit radiance it'll be the irradiance * albedo. 

> Even if you ignore scaling you should still be able to check that if
> you put a single SH term in you get a single SH term back - all
> other terms should remain 0.

That passes. But it seems like (and is intuitive to be that way) this
kind of test covers only existence of correct x/y/z powers in the
polynomials. Putting any coefficients in front passes the test. (E.g.
if c0-c4 are all 1, this test passes.) Or am I missing something?

In general I'd be very happy if I could test whether the convolution
actually generates SHs that are equivalent (to within approximation
error) to the source cubemap _with_ cosine term already included. I
guess there is no other way than to convolve the old-fashioned way?

Thanks,
Alen

Re: [Algorithms] Undershooting in spherical harmonics generated bycubemap convolution

[Sam M. <sam...@ge...>]

Hi Alen,

I'm not quite sure what you mean by diffuse radiance?

There are roughly 3 diffuse values that I think about:
- incoming radiance (ie. an environment cube map)
- irradiance (ie. a blurry cube map: the radiance convolved with the cosine)
- exit radiance (ie. irradiance multiplied by the surface albedo)

I definitely left off those details in my email :) 

If you start with a SH function in a cube map (say, an L1 term), "do your thing" to get it into SH, and then regenerate a cube map (or similar) from your generated SH data you can still check whether it's correct as the end result should just be a scaled version of the original. The scaling should depend on which of the 3 of the above you are working with in the "do your thing" step. 

If it's radiance it should be exactly the same, if it's irradiance it should be scaled by the cosine terms (see the ramamoorthi paper) and if it's exit radiance it'll be the irradiance * albedo. 

Even if you ignore scaling you should still be able to check that if you put a single SH term in you get a single SH term back - all other terms should remain 0. 

Cheers,
Sam


-----Original Message-----
From: Alen Ladavac [mailto:ale...@cr...]
Sent: Tue 05/05/2009 09:56
To: Sam Martin
Cc: Game Development Algorithms
Subject: Re: [Algorithms] Undershooting in spherical harmonics generated bycubemap convolution
 
Sam wrote at 4/28/2009:
>> Do you mean to generate a cubemap by evaluating SHs with synthetic
>> values like (1, 0, 0,..., 0) and see if they transform back to
>> themselves? Sounds interesting. Will have to try that.
> Yep, exactly. You can turn this into a proper unit test.

Unfortunately, it seems that this is not a correct test for my case.
Perhaps I haven't specifically mentioned a "slight" detail: this used
to specify diffuse radiance, not irradiance. As this includes the
cosine term, I believe that such two-way transformation is not
possible. Right?

Alen

Re: [Algorithms] Undershooting in spherical harmonics generated bycubemap convolution

[Alen L. <ale...@cr...>]

Sam wrote at 4/28/2009:
>> Do you mean to generate a cubemap by evaluating SHs with synthetic
>> values like (1, 0, 0,..., 0) and see if they transform back to
>> themselves? Sounds interesting. Will have to try that.
> Yep, exactly. You can turn this into a proper unit test.

Unfortunately, it seems that this is not a correct test for my case.
Perhaps I haven't specifically mentioned a "slight" detail: this used
to specify diffuse radiance, not irradiance. As this includes the
cosine term, I believe that such two-way transformation is not
possible. Right?

Alen

Re: [Algorithms] Keeping an object's label on the screen

[Monteleone, N. <nat...@lm...>]

The hard part is figuring out the screen area I want to allow it to live
in - the overlay in question is rendered to a texture and then pasted on
the terrain.

I think I know how to do it though - I know the 2d bound of my overlay.
I can combine that with the min/max height of the terrain underneath to
get a pretty good bounding box, then project that to screen space like
Mr. Watte said.

-Nathan


-----Original Message-----
From: Tom Plunket [mailto:ga...@fa...] 
Sent: Sunday, May 03, 2009 8:26 PM
To: Game Development Algorithms
Subject: Re: [Algorithms] Keeping an object's label on the screen


> I have to draw some billboard text over some shapes we've "painted"
onto
> our terrain via multitexturing.  Normally this is easy enough - just
> plop the label in an auto-rotated billboard and float it above the
> center of the geometry.  But I need to keep the label on screen at all
> times if any part of the painted geometry is visible.  I.e. if I have
a
> square painted on the terrain, but I can only see a small corner of
it,
> I still need to show the whole label.

Draw the text if the object isn't culled.

You know where you want the text drawn (if you were to draw onto the
center of the object), and if you've got the text rect you can just move
it so it's within the screen area you want to allow it to live in.

-tom!

-- 



------------------------------------------------------------------------
------
Register Now & Save for Velocity, the Web Performance & Operations 
Conference from O'Reilly Media. Velocity features a full day of 
expert-led, hands-on workshops and two days of sessions from industry 
leaders in dedicated Performance & Operations tracks. Use code vel09scf 
and Save an extra 15% before 5/3. http://p.sf.net/sfu/velocityconf
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-lis
t

Re: [Algorithms] Keeping an object's label on the screen

[Tom P. <ga...@fa...>]

> I have to draw some billboard text over some shapes we've "painted" onto
> our terrain via multitexturing.  Normally this is easy enough - just
> plop the label in an auto-rotated billboard and float it above the
> center of the geometry.  But I need to keep the label on screen at all
> times if any part of the painted geometry is visible.  I.e. if I have a
> square painted on the terrain, but I can only see a small corner of it,
> I still need to show the whole label.

Draw the text if the object isn't culled.

You know where you want the text drawn (if you were to draw onto the
center of the object), and if you've got the text rect you can just move
it so it's within the screen area you want to allow it to live in.

-tom!

-- 

Re: [Algorithms] Keeping an object's label on the screen

[Monteleone, N. <nat...@lm...>]

Ok thanks.  Using the bounding box like that seems a lot faster than
trying to analyze an ID buffer.

Not worried about overlapping for now :)

-----Original Message-----
From: Jon Watte [mailto:jw...@gm...] 
Sent: Wednesday, April 29, 2009 1:56 PM
To: Game Development Algorithms
Subject: Re: [Algorithms] Keeping an object's label on the screen

Monteleone, Nathan wrote:
>
> What's a good algorithm to figure out where to draw the label?
>

In general, this is easy, by projecting the desired location to screen 
space. However, you can get into situations where a corner is visible on

the screen, but the center of the object is behind the camera, which may

lead to poorly behaved labels.

Just project the corners of the bounding box of the object to screen 
space; take the average of the corners that are in front of the camera, 
and project that to screen space. Form the rectangle around that, and 
clamp that rectangle to screen space to force it onto the screen.

If you also want multiple labels to sort themselves out without 
overlapping, it gets slightly more twisty.

Sincerely,

jw


------------------------------------------------------------------------
------
Register Now & Save for Velocity, the Web Performance & Operations 
Conference from O'Reilly Media. Velocity features a full day of 
expert-led, hands-on workshops and two days of sessions from industry 
leaders in dedicated Performance & Operations tracks. Use code vel09scf 
and Save an extra 15% before 5/3. http://p.sf.net/sfu/velocityconf
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-lis
t

Re: [Algorithms] Keeping an object's label on the screen

[Monteleone, N. <nat...@lm...>]

Unfortunately the terrain isn't very flat :-(

 

________________________________

From: Jeff Russell [mailto:je...@8m...] 
Sent: Wednesday, April 29, 2009 1:43 PM
To: Game Development Algorithms
Subject: Re: [Algorithms] Keeping an object's label on the screen

 

The idea I had in mind was to do something in screen space...  I'd write
out an object ID version of the projected texture, apply it, render the
terrain geometry into a low-res buffer, then compute min/max screen
coords for each object.  Then I could just draw my text label in screen
space based on that information.  Is this a sane approach?

Could be, if your object counts are reasonably small. If this is just
sections of the terrain we're talking about, and your terrain is at
least sort of flat, you could just project the bounds of these shapes
into screen space and center your label accordingly.


-- 
--------------------------------------------
Jeff Russell
Engineer, 8monkey Labs
www.8monkeylabs.com
--------------------------------------------

Re: [Algorithms] Keeping an object's label on the screen

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

Monteleone, Nathan wrote:
>
> What’s a good algorithm to figure out where to draw the label?
>

In general, this is easy, by projecting the desired location to screen 
space. However, you can get into situations where a corner is visible on 
the screen, but the center of the object is behind the camera, which may 
lead to poorly behaved labels.

Just project the corners of the bounding box of the object to screen 
space; take the average of the corners that are in front of the camera, 
and project that to screen space. Form the rectangle around that, and 
clamp that rectangle to screen space to force it onto the screen.

If you also want multiple labels to sort themselves out without 
overlapping, it gets slightly more twisty.

Sincerely,

jw

Re: [Algorithms] Keeping an object's label on the screen

[Jeff R. <je...@8m...>]

*The idea I had in mind was to do something in screen space...  I’d write
out an object ID version of the projected texture, apply it, render the
terrain geometry into a low-res buffer, then compute min/max screen coords
for each object.  Then I could just draw my text label in screen space based
on that information.  Is this a sane approach?*

Could be, if your object counts are reasonably small. If this is just
sections of the terrain we're talking about, and your terrain is at least
sort of flat, you could just project the bounds of these shapes into screen
space and center your label accordingly.


-- 
--------------------------------------------
Jeff Russell
Engineer, 8monkey Labs
www.8monkeylabs.com
--------------------------------------------

[Algorithms] Keeping an object's label on the screen

[Monteleone, N. <nat...@lm...>]

I have to draw some billboard text over some shapes we've "painted" onto
our terrain via multitexturing.  Normally this is easy enough - just
plop the label in an auto-rotated billboard and float it above the
center of the geometry.  But I need to keep the label on screen at all
times if any part of the painted geometry is visible.  I.e. if I have a
square painted on the terrain, but I can only see a small corner of it,
I still need to show the whole label.

 

What's a good algorithm to figure out where to draw the label?

 

The idea I had in mind was to do something in screen space...  I'd write
out an object ID version of the projected texture, apply it, render the
terrain geometry into a low-res buffer, then compute min/max screen
coords for each object.  Then I could just draw my text label in screen
space based on that information.  Is this a sane approach?

 

Otherwise I'd have to create a geometric representation of our shapes
that conforms to the terrain and choose a 3d location for my text based
on the view frustum.  That seems painful to implement efficiently.

 

Thanks,

Nathan

Re: [Algorithms] Complexity of new hardware

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

Last I checked, the SquirrelFish Extreme engine was built
comparatively well for embedding in applications other then the
browser.

Nicholas "Indy" Ray

On Tue, Apr 28, 2009 at 9:17 AM, Jon Watte <jw...@gm...> wrote:
> Philip Taylor wrote:
>> On Tue, Apr 28, 2009 at 5:24 AM, Jon Watte <jw...@gm...> wrote:
>>
>
>> There's JavaScript, which has pretty huge adoption (outside of games),
>>
>> and all that stuff) it typically runs in), and is designed to be
>> embedded into another application and to execute untrusted (often
>> malicious) code.
>>
>>
>
> Except the available implementations are, by and large, terrible for
> embedding -- even worse than Python. Given that JS is found mostly in
> web browser, the actual implementations I've seen are all terribly
> browser-centric, and not even factored or documented for separate embedding.
>
> Although V8 looks good -- I hadn't looked at that previously.
>
> Sincerely,
>
> jw
>
>
> ------------------------------------------------------------------------------
> Register Now & Save for Velocity, the Web Performance & Operations
> Conference from O'Reilly Media. Velocity features a full day of
> expert-led, hands-on workshops and two days of sessions from industry
> leaders in dedicated Performance & Operations tracks. Use code vel09scf
> and Save an extra 15% before 5/3. http://p.sf.net/sfu/velocityconf
> _______________________________________________
> 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
>

<div><br></div>

Re: [Algorithms] Complexity of new hardware

[Mike S. <mik...@gm...>]

On Tue, Apr 28, 2009 at 9:17 AM, Jon Watte <jw...@gm...> wrote:
> Except the available implementations are, by and large, terrible for
> embedding -- even worse than Python. Given that JS is found mostly in
> web browser, the actual implementations I've seen are all terribly
> browser-centric, and not even factored or documented for separate embedding.

Which implementations?  The Mozilla JS engine has been embedded in
non-browser environments since I started working on it in 1997, and
indeed before.  V8 is pretty browser-independent as well, not sure
about Squirrelfish/Nitro.

Mike

Re: [Algorithms] Complexity of new hardware

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

Philip Taylor wrote:
> On Tue, Apr 28, 2009 at 5:24 AM, Jon Watte <jw...@gm...> wrote:
>   

> There's JavaScript, which has pretty huge adoption (outside of games),
>   
> and all that stuff) it typically runs in), and is designed to be
> embedded into another application and to execute untrusted (often
> malicious) code.
>
>   

Except the available implementations are, by and large, terrible for 
embedding -- even worse than Python. Given that JS is found mostly in 
web browser, the actual implementations I've seen are all terribly 
browser-centric, and not even factored or documented for separate embedding.

Although V8 looks good -- I hadn't looked at that previously.

Sincerely,

jw

Re: [Algorithms] Complexity of new hardware

[Philip T. <ex...@gm...>]

On Tue, Apr 28, 2009 at 1:26 PM, Rachel Blum <r....@gm...> wrote:
>>
>> There's JavaScript, which has pretty huge adoption (outside of games),
>> C-like syntax, closures, prototype-based inheritance, active
>> communities working on the language spec and on implementations and on
>> applications, is reasonably elegant and powerful (see some articles on
>> http://www.crockford.com/javascript/), is quite small (the language
>> itself, distinct from the web browser environment (with DOM and AJAX
>> and all that stuff) it typically runs in),
>
> The downside: If you want to include additional JavaScript libraries you
> have to (as far as I know) resort to the web browser as preprocessor. Which
> kind of destroys any idea of modularity.

There's no need to get a web browser involved; but you do need your
embedding application to provide some functionality, since JS has no
built-in API for accessing files or networks. (The core language does
arrays, strings, regexps, dates, maths, etc, but little else.)

That's pretty trivial - in SpiderMonkey it's a dozen lines of code to
define a C function that reads your script library files and passes
them to the script evaluation API, and to expose it to scripts so they
can call it themselves to load other scripts. The language has no
built-in support for concepts like namespacing, but you can use the
same tricks that modern web scripting libraries use (e.g. wrapping
files in anonymous functions so they don't pollute the global
namespace, and then exporting everything as properties of a single
namespace-like global value), and you can do some other tricks using
the JS engine's embedding API. But I guess this is the wrong list for
continuing discussion of such things...

-- 
Philip Taylor
ex...@gm...

Re: [Algorithms] Undershooting in spherical harmonics generated bycubemap convolution

[Sam M. <sam...@ge...>]

Hi Alen,

> Do you mean to generate a cubemap by evaluating SHs with synthetic
> values like (1, 0, 0,..., 0) and see if they transform back to
> themselves? Sounds interesting. Will have to try that.

Yep, exactly. You can turn this into a proper unit test.

> Hm, the current result seems to be of correct brightness so perhaps,
> that is not it. 

Worth noting that the overall brightness is controlled by just the L0
(ambient) value. The others all integrate to zero and just 'add shape'
to the signal. So it's possible to get the ambient value correct and the
others wrong. If they are too low in general the lighting will be too
directionless. If they are too high you exaggerate the shape (and
ringing).

Btw, if it does turn out to be ringing, the easiest way to reduce this
is to simply scale down the L1 and L2 terms :). 

> When integrating across a cubemap, I use these
> coefficients:

Off the top of my head, these look ok - the cosine term is the rational
on the right hand side. I note they are identical to the Ramamoorthi
paper: http://graphics.stanford.edu/papers/envmap/. 

Did you learn about SH through a different paper to this? If so I'd
recommend reading the Ramamoorthi paper in some detail. For one, I just
noticed it happens to have some numerical SH values in it for Paul
Debevec's light probes, which you can grab online.

Cheers,
Sam

-----Original Message-----
From: Alen Ladavac [mailto:ale...@cr...] 
Sent: 28 April 2009 13:25
To: Sam Martin; Fabian Giesen
Cc: Game Development Algorithms
Subject: Re: [Algorithms] Undershooting in spherical harmonics generated
bycubemap convolution

Fabian wrote at 4/28/2009:
> The second order SH basis functions aren't (and their symmetries are
> rotations by multiplies of 90 degrees, not 180, around the Z axis),
> so you'll get undershooting in other places too.

That makes sense. Thanks!

Sam wrote at 4/28/2009:
> - Check your maths and implementation to make sure your coeffs are
> scaled appropriately. It can be helpful to project cube maps with the
> single SH basis elements in them to ensure you get the coeffs out you
> expect and at the right scale.

Do you mean to generate a cubemap by evaluating SHs with synthetic
values like (1, 0, 0,..., 0) and see if they transform back to
themselves? Sounds interesting. Will have to try that.

> - Check you are including the scaling for the cosine convolution. If
you
> are missing it your L2 SH will be too bright and can produce this kind
> of artefact.

Hm, the current result seems to be of correct brightness so perhaps,
that is not it. When integrating across a cubemap, I use these
coefficients:

static const FLOAT c[5] = {
  0.282095f*0.282095f * 1.0f,
  0.488603f*0.488603f * 2.0f/3.0f,
  1.092548f*1.092548f * 1.0f/4.0f,
  0.315392f*0.315392f * 1.0f/4.0f,
  0.546274f*0.546274f * 1.0f/4.0f
};

in these equations:

FLOAT SHC[9] = {
c[0],
c[1] * v.x,
c[1] * v.y,
c[1] * v.z,
c[2] * v.x * v.z,
c[2] * v.z * v.y,
c[2] * v.y * v.x,
c[3] * (3.0f* v.z*v.z -1.0f),
c[4] * (v.x*v.x - v.y*v.y)
}

integrated over the cube and additionally weight each pixel by
differential angle expressed as R^(-3/2) (to compensate for the cube
shape).

When approximating just one directional light, I use these
coefficients:

static const FLOAT c[5] = {
  0.282095f*0.282095f * PI*16.0f/17.0f * 1.0f,
  0.488603f*0.488603f * PI*16.0f/17.0f * 2.0f/3.0f,
  1.092548f*1.092548f * PI*16.0f/17.0f * 1.0f/4.0f,
  0.315392f*0.315392f * PI*16.0f/17.0f * 1.0f/4.0f,
  0.546274f*0.546274f * PI*16.0f/17.0f * 1.0f/4.0f
}

But that is just a fixed multiplier for all coeficients, and that
should be covered as the current brightness seems correct (testing
with simple blue/red cubemaps etc.)

> - Check for bugs by testing the rotational invariance. Ie. rotate your
> cube map and ensure the projection rotates as expected.
Checked, seems correct.

> I guess you could also test a known cubemap + SH coeffs to compare
your
> output with other peoples?
Sounds like a good idea. Do you know of any such examples? Google
didn't find anything useful.

Thanks,
Alen

Re: [Algorithms] Complexity of new hardware

[Rachel B. <r....@gm...>]

>
> There's JavaScript, which has pretty huge adoption (outside of games),
> C-like syntax, closures, prototype-based inheritance, active
> communities working on the language spec and on implementations and on
> applications, is reasonably elegant and powerful (see some articles on
> http://www.crockford.com/javascript/), is quite small (the language
> itself, distinct from the web browser environment (with DOM and AJAX
> and all that stuff) it typically runs in),

The downside: If you want to include additional JavaScript libraries  
you have to (as far as I know) resort to the web browser as  
preprocessor. Which kind of destroys any idea of modularity.

I like the language a lot, but this one "feature" kills it outright.

If you (the OP) really want a C-like scripting language, see Ch (http://www.softintegration.com/ 
) or CINT (http://root.cern.ch/drupal/content/cint)

Rachel

Re: [Algorithms] Undershooting in spherical harmonics generated bycubemap convolution

[Alen L. <ale...@cr...>]

Fabian wrote at 4/28/2009:
> The second order SH basis functions aren't (and their symmetries are
> rotations by multiplies of 90 degrees, not 180, around the Z axis),
> so you'll get undershooting in other places too.

That makes sense. Thanks!

Sam wrote at 4/28/2009:
> - Check your maths and implementation to make sure your coeffs are
> scaled appropriately. It can be helpful to project cube maps with the
> single SH basis elements in them to ensure you get the coeffs out you
> expect and at the right scale.

Do you mean to generate a cubemap by evaluating SHs with synthetic
values like (1, 0, 0,..., 0) and see if they transform back to
themselves? Sounds interesting. Will have to try that.

> - Check you are including the scaling for the cosine convolution. If you
> are missing it your L2 SH will be too bright and can produce this kind
> of artefact.

Hm, the current result seems to be of correct brightness so perhaps,
that is not it. When integrating across a cubemap, I use these
coefficients:

static const FLOAT c[5] = {
  0.282095f*0.282095f * 1.0f,
  0.488603f*0.488603f * 2.0f/3.0f,
  1.092548f*1.092548f * 1.0f/4.0f,
  0.315392f*0.315392f * 1.0f/4.0f,
  0.546274f*0.546274f * 1.0f/4.0f
};

in these equations:

FLOAT SHC[9] = {
c[0],
c[1] * v.x,
c[1] * v.y,
c[1] * v.z,
c[2] * v.x * v.z,
c[2] * v.z * v.y,
c[2] * v.y * v.x,
c[3] * (3.0f* v.z*v.z -1.0f),
c[4] * (v.x*v.x - v.y*v.y)
}

integrated over the cube and additionally weight each pixel by
differential angle expressed as R^(-3/2) (to compensate for the cube
shape).

When approximating just one directional light, I use these
coefficients:

static const FLOAT c[5] = {
  0.282095f*0.282095f * PI*16.0f/17.0f * 1.0f,
  0.488603f*0.488603f * PI*16.0f/17.0f * 2.0f/3.0f,
  1.092548f*1.092548f * PI*16.0f/17.0f * 1.0f/4.0f,
  0.315392f*0.315392f * PI*16.0f/17.0f * 1.0f/4.0f,
  0.546274f*0.546274f * PI*16.0f/17.0f * 1.0f/4.0f
}

But that is just a fixed multiplier for all coeficients, and that
should be covered as the current brightness seems correct (testing
with simple blue/red cubemaps etc.)

> - Check for bugs by testing the rotational invariance. Ie. rotate your
> cube map and ensure the projection rotates as expected.
Checked, seems correct.

> I guess you could also test a known cubemap + SH coeffs to compare your
> output with other peoples?
Sounds like a good idea. Do you know of any such examples? Google
didn't find anything useful.

Thanks,
Alen

Re: [Algorithms] Undershooting in spherical harmonics generated by cubemap convolution

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

Hi Alen,

> So to ask a concrete question: Is it normal for SH approximation
> errors in such "spiky" cases to generate undershooting in directions
> that are not directly opposite to the brightest point?

If you look at the basis functions for l=2:

   http://web.uniovi.es/qcg/harmonics/harmonics.html

you should see what's going on. For first order SH, you will indeed only 
get undershooting in the opposite direction, since all the functions are 
point-symmetric around zero. The second order SH basis functions aren't 
(and their symmetries are rotations by multiplies of 90 degrees, not 
180, around the Z axis), so you'll get undershooting in other places too.

Kind regards,
-Fabian Giesen

Re: [Algorithms] Undershooting in spherical harmonics generated bycubemap convolution

[Sam M. <sam...@ge...>]

Hi Alan,

SH can suffer from ringing and that really bright sun isn't going to
help, but there's a myriad of other things that can go wrong and produce
the same problems. Ringing is usually less of a problem for representing
irradiance as its low frequency (as opposed to radiance or visibility).
>From your description it sounds like you could well have other problems
so it's worth ruling those out first. 

Some suggestions on things to check:

- Check your maths and implementation to make sure your coeffs are
scaled appropriately. It can be helpful to project cube maps with the
single SH basis elements in them to ensure you get the coeffs out you
expect and at the right scale. 

- Check you are including the scaling for the cosine convolution. If you
are missing it your L2 SH will be too bright and can produce this kind
of artefact.

- Check for bugs by testing the rotational invariance. Ie. rotate your
cube map and ensure the projection rotates as expected.

I guess you could also test a known cubemap + SH coeffs to compare your
output with other peoples?

Hope that helps,
Sam

-----Original Message-----
From: Alen Ladavac [mailto:ale...@cr...] 
Sent: 28 April 2009 08:31
To: Game Development Algorithms
Subject: [Algorithms] Undershooting in spherical harmonics generated
bycubemap convolution

Hi all,

When generating 2nd order SHs by convolving environment cubemaps, In
some rare cases I get some strange artefacts that seem as if that is
just a limitation of 2nd order SHs, but I'm not sure, so I figured I'd
ask...

The problematic case is where there is only a handful of very bright
(~2000x the cubemap average) pixels in one narrow direction (~0.5
deg). (This example is generated by a sun disk in the skies, when seen
through a small window in a dark room).

In this case I get large undershooting (manifesting as a black spot)
in some other direction. Depending on the bright direction, the black
spot is sometimes on the opposite side, but sometimes it is e.g. 90 or
135 degrees from the bright side, etc. I was expecting to see
something like this in the exact opposite direction, but I'm a bit
surprised to see it move around. Then again, I'm not an SH expert, so
I'm probably wrong.

So to ask a concrete question: Is it normal for SH approximation
errors in such "spiky" cases to generate undershooting in directions
that are not directly opposite to the brightest point?

Thanks,
Alen



------------------------------------------------------------------------
------
Register Now & Save for Velocity, the Web Performance & Operations 
Conference from O'Reilly Media. Velocity features a full day of 
expert-led, hands-on workshops and two days of sessions from industry 
leaders in dedicated Performance & Operations tracks. Use code vel09scf 
and Save an extra 15% before 5/3. http://p.sf.net/sfu/velocityconf
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-lis
t

Re: [Algorithms] Complexity of new hardware

[Philip T. <ex...@gm...>]

On Tue, Apr 28, 2009 at 5:24 AM, Jon Watte <jw...@gm...> wrote:
> So, how to design a well-adopted, robust, small, powerful language with
> pretty syntax and an effective C integration layer? And what language
> has all that but I've missed? :-)

There's JavaScript, which has pretty huge adoption (outside of games),
C-like syntax, closures, prototype-based inheritance, active
communities working on the language spec and on implementations and on
applications, is reasonably elegant and powerful (see some articles on
http://www.crockford.com/javascript/), is quite small (the language
itself, distinct from the web browser environment (with DOM and AJAX
and all that stuff) it typically runs in), and is designed to be
embedded into another application and to execute untrusted (often
malicious) code.

It has several major independent open-source implementations
(http://www.mozilla.org/js/spidermonkey/ and
http://webkit.org/blog/214/introducing-squirrelfish-extreme/ and
http://code.google.com/p/v8/) all of which include some kind of JIT
(there's been a lot of competition on performance over the past couple
of years) and all of which have their own approaches to C integration.

On the other hand, the implementations vary in their suitability for
real-time use (non-incremental GC pauses), and in support for
multithreading, debugging, non-standard language extensions, non-x86
JIT, etc, so there's always some tradeoffs.

-- 
Philip Taylor
ex...@gm...