gdalgorithms-list

Re: [Algorithms] Some question about "Lighting and Material of Halo3" and "Lightmap compression in Halo 3"

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

Hi Peter,

 

Do you have a link to a paper/slides explaining why they store an "optimal linear" direction separately? I'm not sure why you wouldn't want to just use the L1 coeffs as a vector?

 

I couldn't find an explanation in the links below. 

 

Thanks,

Sam

 

From: Peter-Pike Sloan [mailto:pet...@ho...] 
Sent: 01 February 2010 21:45
To: gda...@li...
Subject: Re: [Algorithms] Some question about "Lighting and Material of Halo3" and "Lightmap compression in Halo 3"

 

Hi,

 

I believe the source of confusion is that in this equation (5) things are expressed in the local coordinate frame, the fact that they show 3 coefficients implies they are using quadratic SH (so when rotated into the local frame and integrated against a clamped cosine function you only need the 3 ZH coefficients.)  The general case (where you don't know the coordinate frame, or you want to evaluate for any normal) requires all 9 coefficients.

I think the "5*3" comes from the compression mentioned in Hao's slides (linear SH + RGB for directional light in "optimal linear" direction.  Which is 5*3 scalars.)

 

The compression work is Wang et al, I think Yaohua's slides are more indicative of what was actually used...

 

Peter-Pike Sloan

 

________________________________

Date: Fri, 29 Jan 2010 16:28:57 +0100
From: seb...@do...
To: gda...@li...
Subject: [Algorithms] Some question about "Lighting and Material of Halo3" and "Lightmap compression in Halo 3"

Hello all, 

 

I tried to contact the author of this two (now old) paper, without success,:

"Lighting and Material of Halo 3" published at siggraph 2008 (http://ati.amd.com/developer/SIGGRAPH08/Chapter01-Chen-Lighting_and_Material_of_Halo3.pdf)

and GDC 2008 conference "Lightmap compression in Halo 3" (http://toomuchlogic.com/Lightmap_Compression_2008_02_22.pdf)

so I will ask some question to the list, if anyone is interested by the subject and has better understanding of math than me :)

 

1. "Lighting and Material of Halo 3"  About equation (5) the diffuse reflectance using SH basis

the diffuse reflectance using SH basis is : k_d R_d Sum Lambda_i A_i

A_i is the projection of the cosine lobe in SH, and as it is radially symetric.

all coefficient with m != 0 are 0.

After that the author give the first three term of A_i.

I wondering how many band are use for this calculation  ? (order 3, 4 or more ?)

 

I read from "Stupid spherical harmonics tricks" from Perter Pike sloan (http://www.ppsloan.org/publications/StupidSH36.pdf)

that order 3 SH is sufficient for approximate light source

but for HDR light sources he recommand order 5.

As order 4 is 0 (From paper http://www.eecs.berkeley.edu/~ravir/lighting.pdf I get the formula for A_i)

This mean 4 coefficient to store by color channel.

As I am pretty sure the author store  HDR data, can someone lighten me ?

 

2. About texture storage (which are deduced from above statement)

 

I try to figure out how are encoded the incident radiance in their SHLightmap.

>From GDC 2008 conference "Lightmap compression in Halo 3" I can read that the author need to

store for each texel a vector of 5 * 3 float values.

I don't figure what are the values exactly.

 

My assumption is that "3" is for each channel color RGB,

But I can't figure what's the 5 is ?

Are they 5 first band of SH order like I suppose above (but as I said, we only need 4 coefficient in this case)

or maybe order 6 ?

 

In this same paper later I found:

A. Two DXT5 texture for each SH coefficient channel (HDR, positive/negative)

And

B. Each band of the SH coefficients (RGB) are converted to Luvw space

 

I suppose that Luvw space is what is describe in this paper "Rendering from Compressed High Dynamic Range Textures on

Programmable Graphics Hardware" by Peter Pike sloan and al.(ftp://ftp.research.microsoft.com/pub/tr/TR-2006-152.pdf)

 

What I don't understand is that A and B seem different. I can't understand what is store.

Are they storing for each band the triplet RGB of SH coeeficient, mean 3 float value for two DXT5 x order

or do they store store 5 SH coefficient for channel color R in two DXT5 ?

 

So what are the total storage cost of all the 5 * 3 float value in term of DXT5 texture ?

Cause It looks like to be pretty big.

 

Thanks for anyone interested by this post

 

Best regards

 

Lagarde Sébastien

Re: [Algorithms] Algorithm to return point to surface of concave volume

[pontus b. <her...@ho...>]

Andreas,

Since the capsules are mathematically defined by a length and a radius there are no surfaces so I suggest using standard collision detection instead. There are standard intersection tests that return a collision normal along with a intersection distance. I'm guessing you can find it in most open source physics libraries or just google it.

If you need increased performance you can always attempt to use proxy objects or perhaps switch primitive from capsule to something easier.

Hope that helps,
Pontus


Date: Wed, 3 Feb 2010 11:54:45 +0100
From: and...@gm...
To: gda...@li...
Subject: [Algorithms] Algorithm to return point to surface of concave volume

Hi,

I have a point inside a concave volume, does anyone know of an algorithm to find the shortest vector from the point to the surface of the volume? The volume in this case is defined as the union of a number of overlapping capsules (lines with radius).


Thanks 

Andreas Brinck
 		 	   		  
_________________________________________________________________
Hitta kärleken!
http://dejting.se.msn.com/channel/index.aspx?trackingid=1002952

Re: [Algorithms] incremental triangulation for 2D collision detection broadphase

[Samuel M. <sam...@go...>]

@Ben: Thanks for the link, but I wanted to avoid doing full Delauney
triangulation since everything remotely Delauney-like suffices for
me... but I can probably use some of the methods in this paper.
@ Erwin: Thought I read somewhere that Box2D uses a hash... but the
source code looks alot like a AABB tree ;)


But I think I found something better, because I realized that I don't
really need a triangulation, only some partition for example using
polygons...

Okay, here's the outline to my approach:
Every objects center is a "node", around the node is this objects
bounding volume (I think I'll use circles).
Then you build a graph that partitions the plane into (convex and
concave) polygons (You could make the graph so that only triangles are
used). On every corner of a polygon is an object, no object is on the
inside of a polygon.

Now you test for every object which polygon its bounding volume
intersects. Obviously it intersects at least all polygons adjacent to
its node; if the bounding volumes are relatively tight, it should not
intersect more than these.
I think the average number of bounding volume tests for each object
should be around 6.

Now all nodes move, and if the graph changes its topology, it needs to
be repaired. This is the part where I have no concrete algorithm
yet... but I guess I'll find one. I'm relatively sure that this step
should be fast ;)

Then the graph is optimized: a few edges are swapped, inserted etc. to
avoid slivers and such. This should be easy.

Greets,
Samuel



On Wed, Feb 3, 2010 at 6:39 AM, Erwin Coumans <erw...@gm...> wrote:
>
> Hi Samuel,
>
> Box2d uses a dynamic AABB tree for the broadphase, based on the original
> implementation from our Bullet library in 3d.
>
> This tree is incrementally updated, faster than sweep and prune.
>
> No spatial hash.
>
> I'm interested in your approach. How do you 'triangulate' the centers, and
> compute connectivity?
>
> Thanks,
> Erwin
>
> Feel free to forward this to the list, I cannot mail to the list because of
> mail server issues.
>
> Sent from my iPhone
>
> On Feb 2, 2010, at 16:54, Samuel Moll <sam...@go...> wrote:
>
>> Hello all,
>>
>> I need a broadphase collision detection algorithm for 2D rigid body
>> physics (continuous collision detection, but that shouldn't matter for
>> the broadphase...).
>>
>> I have objects of wildly varying sizes, lots of free space and
>> possibly lots of clustering or even a single object very far away from
>> all the others, so a Quadtree (without some strange modifications,
>> wrapping the world came to mind) is not the best option.
>>
>> What I came up with is to take all the objects positions and
>> triangulate this point set. Then for each triangle I determine which
>> objects it overlaps and test all these objects for collision.
>>
>> This has a number of advantages, and I believe it could be competitive
>> to sweep and prune or Quadtrees (at least in 2D, in 3D its probably
>> not cool, but who knows?). I couldn't find anything about this method,
>> but if somebody already invented it I'd appreciate some pointers.
>>
>> What I need now is an (efficient :D) algorithm for updating the
>> triangulation when the points move. i.e. given a valid triangulation
>> (no triangles overlap, triangulates the convex hull of all points) and
>> movement vectors for all points, how can I "repair" the old
>> triangulation?
>>
>> The first part of the problem is how to maintain fat triangles
>> (slivers lead to poor collision rejection). I'm sure there are already
>> good algorithms to incrementally maintain a good triangulation, but I
>> couldn't find them. Also, the union of all triangles must stay convex.
>>
>> The second problem is how to detect and remove triangle overlaps that
>> arise due to fast-moving objects. I have no idea how to do this
>> robustly (theoretically, the points could teleport arbitrarily)
>>
>> I guess somebody already has solved this problem, but I could find no
>> relevant paper...
>>
>> Of course I'll release the finished implementation as open source, or
>> try to incorporate it into Box2D if they want it and if it proves
>> faster than their existing spatial hashing ;)
>>
>>
>> Sincerely,
>> Samuel Moll
>>
>>
>> ------------------------------------------------------------------------------
>> The Planet: dedicated and managed hosting, cloud storage, colocation
>> Stay online with enterprise data centers and the best network in the
>> business
>> Choose flexible plans and management services without long-term contracts
>> Personal 24x7 support from experience hosting pros just a phone call away.
>> http://p.sf.net/sfu/theplanet-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] Algorithm to return point to surface of concave volume

[Andreas B. <and...@gm...>]

Hi,

I have a point inside a concave volume, does anyone know of an algorithm to
find the shortest vector from the point to the surface of the volume? The
volume in this case is defined as the union of a number of overlapping
capsules (lines with radius).

Thanks

Andreas Brinck

Re: [Algorithms] Some question about "Lighting and Material ofHalo3" and "Lightmap compression in Halo 3"

[Sébastien L. <seb...@do...>]

> even if the compression get a 4:1 ratio,

=> even if the compression get a 6:1 ratio,

 

De : Sébastien Lagarde 
Envoyé : mercredi 3 février 2010 11:01
À : Game Development Algorithms
Objet : Re: [Algorithms] Some question about "Lighting and Material ofHalo3" and "Lightmap compression in Halo 3"

 

Hi all, 

 

I take some time to try to fully understand what was saying :),

I have increase my level of understanding, thanks to both of you Sam and David ,

I made the difference between incoming lighting and diffuse irradiance now, and better understand the convolution with cosine lobe.

 

Alright for this part. Thanks to you Peter-Pike, for pointing the problem, in fact I didn't notice the rotation in local frame, and now I think I have 

more question than before :)

 

I tried to understand what Halo 3 do cause this is a real XBOX360 shipped game with SH lighting in it with all console constraint on memory and shader performance.

So I try to figure what tricks they used :)

 

What I think now for halo 3 for their SH lightmap is:

Incoming lighting generated by global illumination solver are projected in 9S H coefficient by color channel

SH coefficient are rotated in tangent space

Then they extract dominant light (intensity and direction).

I suppose they store the DC + linear SH term , so 4 coefficient by channel, (as stated by Peter-Pike)

And they store the intensity (RGB). This give the 5 * 3 float value

 

At runtime, I suppose they used the linear SH term to retrieve the dominant light direction, 

the dominant light is used for the analytic cook torrance specular model.

the dominant light should be used for diffuse part too:

I think they need to extract dominant light intensity from SH, so they light with one diffuse directional light, 

and SH coefficient remaining after extraction of dominant light intensities. I think the extraction is done in shader and not in SH lightmap in order to be

able to recover the right dominant light direction (I am certainly wrong :) ).

 

But after that, I am lost with the rotation in local frame:

 

I don't get the thing for the equation (5). which only require the 3 ZH coefficient.

As my SH coefficient are store in tangent space, I am already in the case of equation (5).

so I don't need to rotate SH coefficient once again (maybe I am wrong here, do I need to rotate with the tangent space normal extract from normal map ?),

and so I only require SH coefficient for i = 0, 2, 6 ?

The convolution by cosine lobe seems to be applied at this time, but two thing are missing, 

the constant: sqrt(4 pi / (2l + 1)) and the divide by PI to turn irradiance into the exit radiance.

(But in their shader code provided, they divided lightprobe_color by Pi at end of diffuse_reflectance, so maybe they just not say it)

 

But doing the convolution at this time mean that we store incoming lighting in SH lightmap, and not diffuse irradiance.

So extracting dominant light from incoming lighting is maybe wrong ?

 

Last though, with their 15 float to store, they said they used two DXT5 by SH band, 

mean we require 10 DXT5 to store only one lightmap. even if the compression get a 4:1 ratio, this require 10Mo for a SH lightmap of 1024x1024 without mipmap

Which seems very huge for console memory even with a good streaming texture system...

 

I am just curious about all these SH tricks, 

Anyway, thanks for the help you already provide to me.

 

Lagarde Sébastien

 

De : Peter-Pike Sloan [mailto:pet...@ho...] 
Envoyé : lundi 1 février 2010 22:46
À : gda...@li...
Objet : Re: [Algorithms] Some question about "Lighting and Material of Halo3" and "Lightmap compression in Halo 3"

 

Hi,

 

I believe the source of confusion is that in this equation (5) things are expressed in the local coordinate frame, the fact that they show 3 coefficients implies they are using quadratic SH (so when rotated into the local frame and integrated against a clamped cosine function you only need the 3 ZH coefficients.)  The general case (where you don't know the coordinate frame, or you want to evaluate for any normal) requires all 9 coefficients.

I think the "5*3" comes from the compression mentioned in Hao's slides (linear SH + RGB for directional light in "optimal linear" direction.  Which is 5*3 scalars.)

 

The compression work is Wang et al, I think Yaohua's slides are more indicative of what was actually used...

 

Peter-Pike Sloan

 

________________________________

Date: Fri, 29 Jan 2010 16:28:57 +0100
From: seb...@do...
To: gda...@li...
Subject: [Algorithms] Some question about "Lighting and Material of Halo3" and "Lightmap compression in Halo 3"

Hello all, 

 

I tried to contact the author of this two (now old) paper, without success,:

"Lighting and Material of Halo 3" published at siggraph 2008 (http://ati.amd.com/developer/SIGGRAPH08/Chapter01-Chen-Lighting_and_Material_of_Halo3.pdf)

and GDC 2008 conference "Lightmap compression in Halo 3" (http://toomuchlogic.com/Lightmap_Compression_2008_02_22.pdf)

so I will ask some question to the list, if anyone is interested by the subject and has better understanding of math than me :)

 

1. "Lighting and Material of Halo 3"  About equation (5) the diffuse reflectance using SH basis

the diffuse reflectance using SH basis is : k_d R_d Sum Lambda_i A_i

A_i is the projection of the cosine lobe in SH, and as it is radially symetric.

all coefficient with m != 0 are 0.

After that the author give the first three term of A_i.

I wondering how many band are use for this calculation  ? (order 3, 4 or more ?)

 

I read from "Stupid spherical harmonics tricks" from Perter Pike sloan (http://www.ppsloan.org/publications/StupidSH36.pdf)

that order 3 SH is sufficient for approximate light source

but for HDR light sources he recommand order 5.

As order 4 is 0 (From paper http://www.eecs.berkeley.edu/~ravir/lighting.pdf I get the formula for A_i)

This mean 4 coefficient to store by color channel.

As I am pretty sure the author store  HDR data, can someone lighten me ?

 

2. About texture storage (which are deduced from above statement)

 

I try to figure out how are encoded the incident radiance in their SHLightmap.

>From GDC 2008 conference "Lightmap compression in Halo 3" I can read that the author need to

store for each texel a vector of 5 * 3 float values.

I don't figure what are the values exactly.

 

My assumption is that "3" is for each channel color RGB,

But I can't figure what's the 5 is ?

Are they 5 first band of SH order like I suppose above (but as I said, we only need 4 coefficient in this case)

or maybe order 6 ?

 

In this same paper later I found:

A. Two DXT5 texture for each SH coefficient channel (HDR, positive/negative)

And

B. Each band of the SH coefficients (RGB) are converted to Luvw space

 

I suppose that Luvw space is what is describe in this paper "Rendering from Compressed High Dynamic Range Textures on

Programmable Graphics Hardware" by Peter Pike sloan and al.(ftp://ftp.research.microsoft.com/pub/tr/TR-2006-152.pdf)

 

What I don't understand is that A and B seem different. I can't understand what is store.

Are they storing for each band the triplet RGB of SH coeeficient, mean 3 float value for two DXT5 x order

or do they store store 5 SH coefficient for channel color R in two DXT5 ?

 

So what are the total storage cost of all the 5 * 3 float value in term of DXT5 texture ?

Cause It looks like to be pretty big.

 

Thanks for anyone interested by this post

 

Best regards

 

Lagarde Sébastien

Re: [Algorithms] Some question about "Lighting and Material of Halo3" and "Lightmap compression in Halo 3"

[Sébastien L. <seb...@do...>]

Hi all, 

 

I take some time to try to fully understand what was saying :),

I have increase my level of understanding, thanks to both of you Sam and David ,

I made the difference between incoming lighting and diffuse irradiance now, and better understand the convolution with cosine lobe.

 

Alright for this part. Thanks to you Peter-Pike, for pointing the problem, in fact I didn't notice the rotation in local frame, and now I think I have 

more question than before :)

 

I tried to understand what Halo 3 do cause this is a real XBOX360 shipped game with SH lighting in it with all console constraint on memory and shader performance.

So I try to figure what tricks they used :)

 

What I think now for halo 3 for their SH lightmap is:

Incoming lighting generated by global illumination solver are projected in 9S H coefficient by color channel

SH coefficient are rotated in tangent space

Then they extract dominant light (intensity and direction).

I suppose they store the DC + linear SH term , so 4 coefficient by channel, (as stated by Peter-Pike)

And they store the intensity (RGB). This give the 5 * 3 float value

 

At runtime, I suppose they used the linear SH term to retrieve the dominant light direction, 

the dominant light is used for the analytic cook torrance specular model.

the dominant light should be used for diffuse part too:

I think they need to extract dominant light intensity from SH, so they light with one diffuse directional light, 

and SH coefficient remaining after extraction of dominant light intensities. I think the extraction is done in shader and not in SH lightmap in order to be

able to recover the right dominant light direction (I am certainly wrong :) ).

 

But after that, I am lost with the rotation in local frame:

 

I don't get the thing for the equation (5). which only require the 3 ZH coefficient.

As my SH coefficient are store in tangent space, I am already in the case of equation (5).

so I don't need to rotate SH coefficient once again (maybe I am wrong here, do I need to rotate with the tangent space normal extract from normal map ?),

and so I only require SH coefficient for i = 0, 2, 6 ?

The convolution by cosine lobe seems to be applied at this time, but two thing are missing, 

the constant: sqrt(4 pi / (2l + 1)) and the divide by PI to turn irradiance into the exit radiance.

(But in their shader code provided, they divided lightprobe_color by Pi at end of diffuse_reflectance, so maybe they just not say it)

 

But doing the convolution at this time mean that we store incoming lighting in SH lightmap, and not diffuse irradiance.

So extracting dominant light from incoming lighting is maybe wrong ?

 

Last though, with their 15 float to store, they said they used two DXT5 by SH band, 

mean we require 10 DXT5 to store only one lightmap. even if the compression get a 4:1 ratio, this require 10Mo for a SH lightmap of 1024x1024 without mipmap

Which seems very huge for console memory even with a good streaming texture system...

 

I am just curious about all these SH tricks, 

Anyway, thanks for the help you already provide to me.

 

Lagarde Sébastien

 

De : Peter-Pike Sloan [mailto:pet...@ho...] 
Envoyé : lundi 1 février 2010 22:46
À : gda...@li...
Objet : Re: [Algorithms] Some question about "Lighting and Material of Halo3" and "Lightmap compression in Halo 3"

 

Hi,

 

I believe the source of confusion is that in this equation (5) things are expressed in the local coordinate frame, the fact that they show 3 coefficients implies they are using quadratic SH (so when rotated into the local frame and integrated against a clamped cosine function you only need the 3 ZH coefficients.)  The general case (where you don't know the coordinate frame, or you want to evaluate for any normal) requires all 9 coefficients.

I think the "5*3" comes from the compression mentioned in Hao's slides (linear SH + RGB for directional light in "optimal linear" direction.  Which is 5*3 scalars.)

 

The compression work is Wang et al, I think Yaohua's slides are more indicative of what was actually used...

 

Peter-Pike Sloan

 

________________________________

Date: Fri, 29 Jan 2010 16:28:57 +0100
From: seb...@do...
To: gda...@li...
Subject: [Algorithms] Some question about "Lighting and Material of Halo3" and "Lightmap compression in Halo 3"

Hello all, 

 

I tried to contact the author of this two (now old) paper, without success,:

"Lighting and Material of Halo 3" published at siggraph 2008 (http://ati.amd.com/developer/SIGGRAPH08/Chapter01-Chen-Lighting_and_Material_of_Halo3.pdf)

and GDC 2008 conference "Lightmap compression in Halo 3" (http://toomuchlogic.com/Lightmap_Compression_2008_02_22.pdf)

so I will ask some question to the list, if anyone is interested by the subject and has better understanding of math than me :)

 

1. "Lighting and Material of Halo 3"  About equation (5) the diffuse reflectance using SH basis

the diffuse reflectance using SH basis is : k_d R_d Sum Lambda_i A_i

A_i is the projection of the cosine lobe in SH, and as it is radially symetric.

all coefficient with m != 0 are 0.

After that the author give the first three term of A_i.

I wondering how many band are use for this calculation  ? (order 3, 4 or more ?)

 

I read from "Stupid spherical harmonics tricks" from Perter Pike sloan (http://www.ppsloan.org/publications/StupidSH36.pdf)

that order 3 SH is sufficient for approximate light source

but for HDR light sources he recommand order 5.

As order 4 is 0 (From paper http://www.eecs.berkeley.edu/~ravir/lighting.pdf I get the formula for A_i)

This mean 4 coefficient to store by color channel.

As I am pretty sure the author store  HDR data, can someone lighten me ?

 

2. About texture storage (which are deduced from above statement)

 

I try to figure out how are encoded the incident radiance in their SHLightmap.

>From GDC 2008 conference "Lightmap compression in Halo 3" I can read that the author need to

store for each texel a vector of 5 * 3 float values.

I don't figure what are the values exactly.

 

My assumption is that "3" is for each channel color RGB,

But I can't figure what's the 5 is ?

Are they 5 first band of SH order like I suppose above (but as I said, we only need 4 coefficient in this case)

or maybe order 6 ?

 

In this same paper later I found:

A. Two DXT5 texture for each SH coefficient channel (HDR, positive/negative)

And

B. Each band of the SH coefficients (RGB) are converted to Luvw space

 

I suppose that Luvw space is what is describe in this paper "Rendering from Compressed High Dynamic Range Textures on

Programmable Graphics Hardware" by Peter Pike sloan and al.(ftp://ftp.research.microsoft.com/pub/tr/TR-2006-152.pdf)

 

What I don't understand is that A and B seem different. I can't understand what is store.

Are they storing for each band the triplet RGB of SH coeeficient, mean 3 float value for two DXT5 x order

or do they store store 5 SH coefficient for channel color R in two DXT5 ?

 

So what are the total storage cost of all the 5 * 3 float value in term of DXT5 texture ?

Cause It looks like to be pretty big.

 

Thanks for anyone interested by this post

 

Best regards

 

Lagarde Sébastien

Re: [Algorithms] incremental triangulation for 2D collision detection broadphase

[Ben Sunshine-H. <sn...@gm...>]

On Tue, Feb 2, 2010 at 7:54 PM, Samuel Moll <sam...@go...> wrote:
> What I need now is an (efficient :D) algorithm for updating the
> triangulation when the points move. i.e. given a valid triangulation
> (no triangles overlap, triangulates the convex hull of all points) and
> movement vectors for all points, how can I "repair" the old
> triangulation?

Take a look at "Voronoi Diagrams of Moving Points", link below.
Remember that the Voronoi tessellation is the dual of the Delaunay
triangulation, which in general tends not to produce many slivers.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.8944

Ben

[Algorithms] incremental triangulation for 2D collision detection broadphase

[Samuel M. <sam...@go...>]

Hello all,

I need a broadphase collision detection algorithm for 2D rigid body
physics (continuous collision detection, but that shouldn't matter for
the broadphase...).

I have objects of wildly varying sizes, lots of free space and
possibly lots of clustering or even a single object very far away from
all the others, so a Quadtree (without some strange modifications,
wrapping the world came to mind) is not the best option.

What I came up with is to take all the objects positions and
triangulate this point set. Then for each triangle I determine which
objects it overlaps and test all these objects for collision.

This has a number of advantages, and I believe it could be competitive
to sweep and prune or Quadtrees (at least in 2D, in 3D its probably
not cool, but who knows?). I couldn't find anything about this method,
but if somebody already invented it I'd appreciate some pointers.

What I need now is an (efficient :D) algorithm for updating the
triangulation when the points move. i.e. given a valid triangulation
(no triangles overlap, triangulates the convex hull of all points) and
movement vectors for all points, how can I "repair" the old
triangulation?

The first part of the problem is how to maintain fat triangles
(slivers lead to poor collision rejection). I'm sure there are already
good algorithms to incrementally maintain a good triangulation, but I
couldn't find them. Also, the union of all triangles must stay convex.

The second problem is how to detect and remove triangle overlaps that
arise due to fast-moving objects. I have no idea how to do this
robustly (theoretically, the points could teleport arbitrarily)

I guess somebody already has solved this problem, but I could find no
relevant paper...

Of course I'll release the finished implementation as open source, or
try to incorporate it into Box2D if they want it and if it proves
faster than their existing spatial hashing ;)


Sincerely,
Samuel Moll

Re: [Algorithms] Some question about "Lighting and Material of Halo3" and "Lightmap compression in Halo 3"

[Peter-Pike S. <pet...@ho...>]

Hi,
I believe the source of confusion is that in this equation (5) things are expressed in the local coordinate frame, the fact that they show 3 coefficients implies they are using quadratic SH (so when rotated into the local frame and integrated against a clamped cosine function you only need the 3 ZH coefficients.)  The general case (where you don't know the coordinate frame, or you want to evaluate for any normal) requires all 9 coefficients.

I think the "5*3" comes from the compression mentioned in Hao's slides (linear SH + RGB for directional light in "optimal linear" direction.  Which is 5*3 scalars.)
The compression work is Wang et al, I think Yaohua's slides are more indicative of what was actually used...
Peter-Pike Sloan
Date: Fri, 29 Jan 2010 16:28:57 +0100
From: seb...@do...
To: gda...@li...
Subject: [Algorithms] Some question about "Lighting and Material of Halo3"	and "Lightmap compression in Halo 3"
















Hello all, 

 

I tried to contact the author of this two
(now old) paper, without success,:

"Lighting and Material of Halo 3"
published at siggraph 2008 (http://ati.amd.com/developer/SIGGRAPH08/Chapter01-Chen-Lighting_and_Material_of_Halo3.pdf)

and GDC 2008
conference "Lightmap compression in Halo 3" (http://toomuchlogic.com/Lightmap_Compression_2008_02_22.pdf)

so I will ask some question to the list, if
anyone is interested by the subject and has better understanding of math than
me :)

 

1. "Lighting and Material of Halo 3"
 About equation (5) the diffuse reflectance using SH basis

the diffuse reflectance using SH basis is :
k_d R_d Sum Lambda_i A_i

A_i is the projection of the cosine lobe in
SH, and as it is radially symetric.

all coefficient with m != 0 are 0.

After that the author give the first three
term of A_i.

I wondering how many band are use for this
calculation  ? (order 3, 4 or more ?)

 

I read from "Stupid spherical
harmonics tricks" from Perter Pike sloan (http://www.ppsloan.org/publications/StupidSH36.pdf)

that order 3 SH is sufficient for
approximate light source

but for HDR light sources he recommand
order 5.

As order 4 is 0 (From paper
http://www.eecs.berkeley.edu/~ravir/lighting.pdf I get the formula for A_i)

This mean 4 coefficient to store by color
channel.

As I am pretty sure the author store  HDR
data, can someone lighten me ?

 

2. About texture storage (which are deduced
from above statement)

 

I try to figure out how are encoded the
incident radiance in their SHLightmap.

>From GDC 2008 conference "Lightmap
compression in Halo 3" I can read that the author need to

store for each texel a vector of 5 * 3 float
values.

I don't figure what are the values exactly.

 

My assumption is that "3" is for
each channel color RGB,

But I can't figure what's the 5 is ?

Are they 5 first band of SH order like I suppose
above (but as I said, we only need 4 coefficient in this case)

or maybe order 6 ?

 

In this same paper later I found:

A. Two DXT5 texture for each SH coefficient
channel (HDR, positive/negative)

And

B. Each band of the SH coefficients (RGB)
are converted to Luvw space

 

I suppose that Luvw space is what is
describe in this paper "Rendering from Compressed High Dynamic Range
Textures on

Programmable Graphics Hardware" by
Peter Pike sloan and al.(ftp://ftp.research.microsoft.com/pub/tr/TR-2006-152.pdf)

 

What I don't understand is that A and B
seem different. I can't understand what is store.

Are they storing for each band the triplet
RGB of SH coeeficient, mean 3 float value for two DXT5 x order

or do they store store 5 SH coefficient for
channel color R in two DXT5 ?

 

So what are the total storage cost of all
the 5 * 3 float value in term of DXT5 texture ?

Cause It looks like to be pretty big.

 

Thanks for anyone interested by this post

 

Best regards

 

Lagarde Sébastien

 		 	   		  

Re: [Algorithms] Some question about "Lighting andMaterialofHalo3"and "Lightmap compression in Halo 3"

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

Hi Sébastien,

Yeah, the maths is a bit of a headache...

I think I see where you might be getting stuck. The clamped cosine, projected into SH, is a radially symmetric SH (ie. a zonal harmonic with no rotation). But the fact it is radially symmetric is a requirement if the convolution to produce another SH as an output. Convolving two arbitrary SH functions together doesn't actually produce another SH - it produces a higher dimensional object, which isn't so useful. It's only when one (or both) of the SH are radially symmetric that the result is still an SH. And by a similar argument, both SH need to be radially symmetric to get a radially symmetric output (in general). 

Convolution with a clamped cosine has some additional properties though. The 'clamp' part of the function produces a lot* of high frequency harmonics, but only even-numbered ones - all the odd-numbered levels vanish apart from L1. The coefficients also tail off very quickly so you don't need to store anything beyond L2 in practice (L3 is 0 anyway). The very best way to test this is to completely ignore the maths, and show people screenshots with different versions. You can see there is a difference, but it's extremely hard to tell which one is the mathematically more accurate version. They all look good, just different.

Completely separate to that, you can sometimes represent a non-radially symmetric spherical function by accumulating several independently rotated radially symmetric functions. It's not all that different from storing a list of separate directional lights in some sense. I don't know if this what Halo are doing, although I'll probably have to read that paper now :)


It's also worth making the distinction between incoming radiance, which is high frequency and isn't well represented by any kind of SH, and diffuse irradiance, which has the cosine integrated in already. SH are really great at diffuse stuff, but don't handle complexity well. 

Hope that helps!

Thanks,
Sam

* = non-rigorous terminology :)

From: Sébastien Lagarde [mailto:seb...@do...] 
Sent: 01 February 2010 17:55
To: Game Development Algorithms
Subject: Re: [Algorithms] Some question about "Lighting andMaterialofHalo3"and "Lightmap compression in Halo 3"

 

Hi Sam

 

> does not produce a radially symmetric SH

In fact I am not sure to understand fully the SH math, that why I ask, 

I attached a picture showing the part of the "Lighting and MaterialofHalo3" which I will highlight.

 

The equation (4) is the projection of incoming lighting in SH.

The equation (5) is the diffuse reflectance equation used in Halo3

They sum the SH coefficient of the incoming lighting multiply by the SH coefficient of the projection of the cosine lobe.

 

As you said, this is a convolution, 

>From Precomputed radiance transfer for real-time rendering in Dynamic, low-frequency lighting environments

(http://research.microsoft.com/en-us/um/people/johnsny/papers/prt.pdf) in the section "convolution" we can read:

 

"

In other words, the coefficients of the projected convolution are

simply scaled products of the separately projected functions.

Note that because h is circularly symmetric about z, its projection

coefficients are nonzero only for m=0. The convolution property

provides a fast way to convolve an environment map with a

hemispherical cosine kernel, defined as h(z) = max(z,0)

"

So I am a little lost here, I think I misunderstanding the math, 

in the case of the convolution, as said in the Halo3 paper you get a non nul result when you multiply the coefficient  for i = 0, 2 and 6 (based on order 3 SH)

so you don't need to store more than 9 SH coefficient ( 3 zonal harmonic for 3 color channel) for the incoming lighting, right ?

 

Is that statement mean that the lighting is radially symmetric SH, I am not sure.

 

> "Zonal" harmonics, where m != 0 are 0

Sorry for the unclarity of my word, I mean that A3 = 0 (notation from halo3 picture joint). 

the coefficient for A3, A4 etc... can be found in this paper (http://www.eecs.berkeley.edu/~ravir/lighting.pdf) and are not given in halo paper for order > 3

that why I said the zonal hamonic SH coefficient of the 4 band don't need to be store.

 

Thanks to enlighten me :)

 

Lagarde Sébastien

Re: [Algorithms] Some question about "Lighting andMaterialofHalo3"and "Lightmap compression in Halo 3"

[David N. <da...@re...>]

Hi,

 

I can't access that paper as the website seems to be down right now but I can talk about convolving the signal with a cosine function.

 

Check out the paper "An Effecient Representation for Irradiance Environment Maps" by Ravi Ramamoorthi and Pat Hanrahan.

 

As Sam pointed out while the cosine function is circularly symmetric the input lighting is very complex. You can think of the cosine function as a low pass filter. It leaves you with a non-symmetric function. Now, where I think you are getting confused is how coefficients are getting through when the odd terms > 1 are 0 for the cosine coefficients projected against the associated legendre functions.

 

The derivation is in the environment map paper so I won't explain it here but the key equation is (7).

 

$E(\theta, \phi) = \sum _l_m [A_l * L_l_m * Y_l_m(\theta, \phi)]$

(you can copy the above LaTeX equation into an online viewer such as http://www.codecogs.com/components/equationeditor/equationeditor.php if you can't read LaTeX)

 

Notice, how l is defined for l <= 2 and it does contribute to the equation and as l gets higher it quickly dampens the function. As you can see for the first 9 coefficients cosine will not zero out any terms.

 

Mind you this is 9 coefficients for just one color channel multiply that by 3 for RGB.

 

-= Dave

 

From: Sébastien Lagarde [mailto:seb...@do...] 
Sent: Monday, February 01, 2010 9:55 AM
To: Game Development Algorithms
Subject: Re: [Algorithms] Some question about "Lighting andMaterialofHalo3"and "Lightmap compression in Halo 3"

 

Hi Sam

 

> does not produce a radially symmetric SH

In fact I am not sure to understand fully the SH math, that why I ask, 

I attached a picture showing the part of the "Lighting and MaterialofHalo3" which I will highlight.

 

The equation (4) is the projection of incoming lighting in SH.

The equation (5) is the diffuse reflectance equation used in Halo3

They sum the SH coefficient of the incoming lighting multiply by the SH coefficient of the projection of the cosine lobe.

 

As you said, this is a convolution, 

From Precomputed radiance transfer for real-time rendering in Dynamic, low-frequency lighting environments

(http://research.microsoft.com/en-us/um/people/johnsny/papers/prt.pdf) in the section "convolution" we can read:

 

"

In other words, the coefficients of the projected convolution are

simply scaled products of the separately projected functions.

Note that because h is circularly symmetric about z, its projection

coefficients are nonzero only for m=0. The convolution property

provides a fast way to convolve an environment map with a

hemispherical cosine kernel, defined as h(z) = max(z,0)

"

So I am a little lost here, I think I misunderstanding the math, 

in the case of the convolution, as said in the Halo3 paper you get a non nul result when you multiply the coefficient  for i = 0, 2 and 6 (based on order 3 SH)

so you don't need to store more than 9 SH coefficient ( 3 zonal harmonic for 3 color channel) for the incoming lighting, right ?

 

Is that statement mean that the lighting is radially symmetric SH, I am not sure.

 

> “Zonal” harmonics, where m != 0 are 0

Sorry for the unclarity of my word, I mean that A3 = 0 (notation from halo3 picture joint). 

the coefficient for A3, A4 etc... can be found in this paper (http://www.eecs.berkeley.edu/~ravir/lighting.pdf) and are not given in halo paper for order > 3

that why I said the zonal hamonic SH coefficient of the 4 band don't need to be store.

 

Thanks to enlighten me :)

 

Lagarde Sébastien

Re: [Algorithms] Some question about "Lighting and Material of Halo3" and "Lightmap compression in Halo 3"

[Francis B. <fra...@ub...>]

FWIW there here is a new compression scheme to be presented @ I3D 2010
http://www.cg.tuwien.ac.at/research/publications/2010/Habel-2010-EIN/

@inproceedings\{Habel-2010-EIN,
  title =      "Efficient Irradiance Normal Mapping",
  author =     "Ralf Habel and Michael Wimmer",
  year =       "2010",
  abstract =   "Irradiance normal mapping is a method to combine two popular
               techniques, light mapping and normal mapping, and is used in
               games such as Half-Life 2 or Halo 3. This combination allows
               using low-resolution light caching on surfaces with only a
               few coefficients which are evaluated by normal maps to
               render spatial high-frequency changes in the lighting.
               Though there are dedicated bases for this purpose such as
               the Half-Life 2 basis, higher order basis functions such as
               quadratic Spherical Harmonics are needed for an accurate
               representation. However, a full spherical basis is not
               needed since the irradiance is stored on the surface of a
               scene.  In order to represent the irradiance signals
               efficiently, we propose a novel polynomial, hemispherically
               orthonormal basis function set that is specifically designed
               to carry a directional irradiance signal on the hemisphere
               and which makes optimal use of the number of coefficients.
               To compare our results with previous work, we analyze the
               relations and attributes of previously proposed basis
               systems and show that 6 coefficients are sufficient to
               accurately represent an irradiance signal on the hemisphere.
               To create the necessary irradiance signals, we use Spherical
               Harmonics as an intermediate basis due to their fast
               filtering capabilities.",
  pages =      "%pages_from%--%pages_to%",
  month =      feb,
  location =   "Washington D.C.",
  booktitle =  "Proceedings of I3D 2010",
  keywords =   "real-time rendering, irradiance, lightmap, normal mapping",
  URL =        "http://www.cg.tuwien.ac.at/research/publications/2010/Habel-2010-EIN/",
}


From: Sébastien Lagarde [mailto:seb...@do...]
Sent: Friday, January 29, 2010 10:29 AM
To: gda...@li...
Subject: [Algorithms] Some question about "Lighting and Material of Halo3" and "Lightmap compression in Halo 3"

Hello all,

I tried to contact the author of this two (now old) paper, without success,:
"Lighting and Material of Halo 3" published at siggraph 2008 (http://ati.amd.com/developer/SIGGRAPH08/Chapter01-Chen-Lighting_and_Material_of_Halo3.pdf)
and GDC 2008 conference "Lightmap compression in Halo 3" (http://toomuchlogic.com/Lightmap_Compression_2008_02_22.pdf)
so I will ask some question to the list, if anyone is interested by the subject and has better understanding of math than me :)

1. "Lighting and Material of Halo 3"  About equation (5) the diffuse reflectance using SH basis
the diffuse reflectance using SH basis is : k_d R_d Sum Lambda_i A_i
A_i is the projection of the cosine lobe in SH, and as it is radially symetric.
all coefficient with m != 0 are 0.
After that the author give the first three term of A_i.
I wondering how many band are use for this calculation  ? (order 3, 4 or more ?)

I read from "Stupid spherical harmonics tricks" from Perter Pike sloan (http://www.ppsloan.org/publications/StupidSH36.pdf)
that order 3 SH is sufficient for approximate light source
but for HDR light sources he recommand order 5.
As order 4 is 0 (From paper http://www.eecs.berkeley.edu/~ravir/lighting.pdf I get the formula for A_i)
This mean 4 coefficient to store by color channel.
As I am pretty sure the author store  HDR data, can someone lighten me ?

2. About texture storage (which are deduced from above statement)

I try to figure out how are encoded the incident radiance in their SHLightmap.
>From GDC 2008 conference "Lightmap compression in Halo 3" I can read that the author need to
store for each texel a vector of 5 * 3 float values.
I don't figure what are the values exactly.

My assumption is that "3" is for each channel color RGB,
But I can't figure what's the 5 is ?
Are they 5 first band of SH order like I suppose above (but as I said, we only need 4 coefficient in this case)
or maybe order 6 ?

In this same paper later I found:
A. Two DXT5 texture for each SH coefficient channel (HDR, positive/negative)
And
B. Each band of the SH coefficients (RGB) are converted to Luvw space

I suppose that Luvw space is what is describe in this paper "Rendering from Compressed High Dynamic Range Textures on
Programmable Graphics Hardware" by Peter Pike sloan and al.(ftp://ftp.research.microsoft.com/pub/tr/TR-2006-152.pdf)

What I don't understand is that A and B seem different. I can't understand what is store.
Are they storing for each band the triplet RGB of SH coeeficient, mean 3 float value for two DXT5 x order
or do they store store 5 SH coefficient for channel color R in two DXT5 ?

So what are the total storage cost of all the 5 * 3 float value in term of DXT5 texture ?
Cause It looks like to be pretty big.

Thanks for anyone interested by this post

Best regards

Lagarde Sébastien

Re: [Algorithms] Some question about "Lighting and MaterialofHalo3" and "Lightmap compression in Halo 3"

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

I can’t help you with the “what sh order halo 3..” question, but I think there’s a bit of confusion over the zonal harmonic part.

 

Convolving an arbitrary SH (e.g. your input lighting) against a clamped cosine SH (for the diffuse integral - which is radially symmetric) does not produce a radially symmetric SH. But it does greatly reduce the need for higher order coefficients. Diffuse lighting is very low frequency and in practice I’ve never found a need for more than L2, and L1 is often adequate for most purposes.

 

“Zonal” harmonics, where m != 0 are 0, are a bit of a special case. I’m not sure how they are used in the paper you mentioned, but in general diffuse lighting over a sphere isn’t radially symmetric. 

 

Not sure if that helps or not!

 

Ta,

Sam

 

From: Sébastien Lagarde [mailto:seb...@do...] 
Sent: 01 February 2010 12:23
To: Game Development Algorithms
Subject: Re: [Algorithms] Some question about "Lighting and MaterialofHalo3" and "Lightmap compression in Halo 3"

 

Yes, in fact I was not clear, I will sum up my questions :)

And yes you remember correctly.

 

Question:

What SH order Halo 3 uses for their SH lightmap (2 (4 coeff), 3 (9 coeff), 4 (16 coeff) ), 5 (25 coeff)  etc...) ? And what are the value stored ?

 

From the paper, it seems that they store HDR RGB value.

So multiply the number of SH coefficient by 3

but  they only need to store the integration of the diffuse equation (5) in the paper "lighting and material in halo 3"

which contain the projection of the cosine lobe in SH, which is radially symmetric.

Mean that only zonal harmonic coefficient matter (all coefficient with m != 0 are 0).

So this reduce the number of SH coefficient depend on the order:

(2 (2 coeff), 3 (3 coeff), 4 (3 coeff) ), 5 (4 coeff)  etc...) (note that order 4 zonal harmonic is 0)

So if halo 3 store 3 SH order for RGB we get: 3 *3 = 9 colored SH coefficient

and for order 4 : 3 * 4 = 12 colored SH coefficient

but they saisd that they store 5 * 3 float value, so I am lost. What represent this float value ?

 

Thanks you for any advice :)

 

Lagarde Sébastien

 

 

De : Jon Watte [mailto:jw...@gm...] 
Envoyé : samedi 30 janvier 2010 01:46
À : Game Development Algorithms
Objet : Re: [Algorithms] Some question about "Lighting and Material ofHalo3" and "Lightmap compression in Halo 3"

 

I don't quite understand your coupling between harmonic orders and coefficients.

 

If I remember correctly, spherical harmonics of order 0 is a flat value -- 1 coefficient.

Order 1 adds three cardinal directions -- 3 additional coefficients, for a total of 4.

Order 2 adds another 5, for a total of 9.

Order 3 adds another 7, for a total of 16.

Order 4 adds another 9, for a total of 25.

...

 

You may be able to omit the constant term (calculating it or assuming it) which would get a total harmonic count for order 3 of 15. Perhaps that's where the number comes from (but I have not had time to check the paper, just guessing here).

 

Generally, if you separate out the diffuse/ambient reflection/albedo texture to a "regular" texture, you don't need to store the light response in RGB channels, just like you don't use different light fall-off equations for the different color channels. (Except when you do Rayleigh scattering and similar for atmospherics, I think...)

 

Sincerely,

 

jw

--
Americans might object: there is no way we would sacrifice our living standards for the benefit of people in the rest of the world. Nevertheless, whether we get there willingly or not, we shall soon have lower consumption rates, because our present rates are unsustainable. 



2010/1/29 Sébastien Lagarde <seb...@do...>

Hello all, 

 

I tried to contact the author of this two (now old) paper, without success,:

"Lighting and Material of Halo 3" published at siggraph 2008 (http://ati.amd.com/developer/SIGGRAPH08/Chapter01-Chen-Lighting_and_Material_of_Halo3.pdf)

and GDC 2008 conference "Lightmap compression in Halo 3" (http://toomuchlogic.com/Lightmap_Compression_2008_02_22.pdf)

so I will ask some question to the list, if anyone is interested by the subject and has better understanding of math than me :)

 

1. "Lighting and Material of Halo 3"  About equation (5) the diffuse reflectance using SH basis

the diffuse reflectance using SH basis is : k_d R_d Sum Lambda_i A_i

A_i is the projection of the cosine lobe in SH, and as it is radially symetric.

all coefficient with m != 0 are 0.

After that the author give the first three term of A_i.

I wondering how many band are use for this calculation  ? (order 3, 4 or more ?)

 

I read from "Stupid spherical harmonics tricks" from Perter Pike sloan (http://www.ppsloan.org/publications/StupidSH36.pdf)

that order 3 SH is sufficient for approximate light source

but for HDR light sources he recommand order 5.

As order 4 is 0 (From paper http://www.eecs.berkeley.edu/~ravir/lighting.pdf I get the formula for A_i)

This mean 4 coefficient to store by color channel.

As I am pretty sure the author store  HDR data, can someone lighten me ?

 

2. About texture storage (which are deduced from above statement)

 

I try to figure out how are encoded the incident radiance in their SHLightmap.

From GDC 2008 conference "Lightmap compression in Halo 3" I can read that the author need to

store for each texel a vector of 5 * 3 float values.

I don't figure what are the values exactly.

 

My assumption is that "3" is for each channel color RGB,

But I can't figure what's the 5 is ?

Are they 5 first band of SH order like I suppose above (but as I said, we only need 4 coefficient in this case)

or maybe order 6 ?

 

In this same paper later I found:

A. Two DXT5 texture for each SH coefficient channel (HDR, positive/negative)

And

B. Each band of the SH coefficients (RGB) are converted to Luvw space

 

I suppose that Luvw space is what is describe in this paper "Rendering from Compressed High Dynamic Range Textures on

Programmable Graphics Hardware" by Peter Pike sloan and al.(ftp://ftp.research.microsoft.com/pub/tr/TR-2006-152.pdf)

 

What I don't understand is that A and B seem different. I can't understand what is store.

Are they storing for each band the triplet RGB of SH coeeficient, mean 3 float value for two DXT5 x order

or do they store store 5 SH coefficient for channel color R in two DXT5 ?

 

So what are the total storage cost of all the 5 * 3 float value in term of DXT5 texture ?

Cause It looks like to be pretty big.

 

Thanks for anyone interested by this post

 

Best regards

 

Lagarde Sébastien


------------------------------------------------------------------------------
The Planet: dedicated and managed hosting, cloud storage, colocation
Stay online with enterprise data centers and the best network in the business
Choose flexible plans and management services without long-term contracts
Personal 24x7 support from experience hosting pros just a phone call away.
http://p.sf.net/sfu/theplanet-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] Some question about "Lighting and Material ofHalo3" and "Lightmap compression in Halo 3"

[Sébastien L. <seb...@do...>]

Yes, in fact I was not clear, I will sum up my questions :)

And yes you remember correctly.

 

Question:

What SH order Halo 3 uses for their SH lightmap (2 (4 coeff), 3 (9 coeff), 4 (16 coeff) ), 5 (25 coeff)  etc...) ? And what are the value stored ?

 

From the paper, it seems that they store HDR RGB value.

So multiply the number of SH coefficient by 3

but  they only need to store the integration of the diffuse equation (5) in the paper "lighting and material in halo 3"

which contain the projection of the cosine lobe in SH, which is radially symmetric.

Mean that only zonal harmonic coefficient matter (all coefficient with m != 0 are 0).

So this reduce the number of SH coefficient depend on the order:

(2 (2 coeff), 3 (3 coeff), 4 (3 coeff) ), 5 (4 coeff)  etc...) (note that order 4 zonal harmonic is 0)

So if halo 3 store 3 SH order for RGB we get: 3 *3 = 9 colored SH coefficient

and for order 4 : 3 * 4 = 12 colored SH coefficient

but they saisd that they store 5 * 3 float value, so I am lost. What represent this float value ?

 

Thanks you for any advice :)

 

Lagarde Sébastien

 

 

De : Jon Watte [mailto:jw...@gm...] 
Envoyé : samedi 30 janvier 2010 01:46
À : Game Development Algorithms
Objet : Re: [Algorithms] Some question about "Lighting and Material ofHalo3" and "Lightmap compression in Halo 3"

 

I don't quite understand your coupling between harmonic orders and coefficients.

 

If I remember correctly, spherical harmonics of order 0 is a flat value -- 1 coefficient.

Order 1 adds three cardinal directions -- 3 additional coefficients, for a total of 4.

Order 2 adds another 5, for a total of 9.

Order 3 adds another 7, for a total of 16.

Order 4 adds another 9, for a total of 25.

...

 

You may be able to omit the constant term (calculating it or assuming it) which would get a total harmonic count for order 3 of 15. Perhaps that's where the number comes from (but I have not had time to check the paper, just guessing here).

 

Generally, if you separate out the diffuse/ambient reflection/albedo texture to a "regular" texture, you don't need to store the light response in RGB channels, just like you don't use different light fall-off equations for the different color channels. (Except when you do Rayleigh scattering and similar for atmospherics, I think...)

 

Sincerely,

 

jw

--
Americans might object: there is no way we would sacrifice our living standards for the benefit of people in the rest of the world. Nevertheless, whether we get there willingly or not, we shall soon have lower consumption rates, because our present rates are unsustainable. 




2010/1/29 Sébastien Lagarde <seb...@do...>

Hello all, 

 

I tried to contact the author of this two (now old) paper, without success,:

"Lighting and Material of Halo 3" published at siggraph 2008 (http://ati.amd.com/developer/SIGGRAPH08/Chapter01-Chen-Lighting_and_Material_of_Halo3.pdf)

and GDC 2008 conference "Lightmap compression in Halo 3" (http://toomuchlogic.com/Lightmap_Compression_2008_02_22.pdf)

so I will ask some question to the list, if anyone is interested by the subject and has better understanding of math than me :)

 

1. "Lighting and Material of Halo 3"  About equation (5) the diffuse reflectance using SH basis

the diffuse reflectance using SH basis is : k_d R_d Sum Lambda_i A_i

A_i is the projection of the cosine lobe in SH, and as it is radially symetric.

all coefficient with m != 0 are 0.

After that the author give the first three term of A_i.

I wondering how many band are use for this calculation  ? (order 3, 4 or more ?)

 

I read from "Stupid spherical harmonics tricks" from Perter Pike sloan (http://www.ppsloan.org/publications/StupidSH36.pdf)

that order 3 SH is sufficient for approximate light source

but for HDR light sources he recommand order 5.

As order 4 is 0 (From paper http://www.eecs.berkeley.edu/~ravir/lighting.pdf I get the formula for A_i)

This mean 4 coefficient to store by color channel.

As I am pretty sure the author store  HDR data, can someone lighten me ?

 

2. About texture storage (which are deduced from above statement)

 

I try to figure out how are encoded the incident radiance in their SHLightmap.

From GDC 2008 conference "Lightmap compression in Halo 3" I can read that the author need to

store for each texel a vector of 5 * 3 float values.

I don't figure what are the values exactly.

 

My assumption is that "3" is for each channel color RGB,

But I can't figure what's the 5 is ?

Are they 5 first band of SH order like I suppose above (but as I said, we only need 4 coefficient in this case)

or maybe order 6 ?

 

In this same paper later I found:

A. Two DXT5 texture for each SH coefficient channel (HDR, positive/negative)

And

B. Each band of the SH coefficients (RGB) are converted to Luvw space

 

I suppose that Luvw space is what is describe in this paper "Rendering from Compressed High Dynamic Range Textures on

Programmable Graphics Hardware" by Peter Pike sloan and al.(ftp://ftp.research.microsoft.com/pub/tr/TR-2006-152.pdf)

 

What I don't understand is that A and B seem different. I can't understand what is store.

Are they storing for each band the triplet RGB of SH coeeficient, mean 3 float value for two DXT5 x order

or do they store store 5 SH coefficient for channel color R in two DXT5 ?

 

So what are the total storage cost of all the 5 * 3 float value in term of DXT5 texture ?

Cause It looks like to be pretty big.

 

Thanks for anyone interested by this post

 

Best regards

 

Lagarde Sébastien


------------------------------------------------------------------------------
The Planet: dedicated and managed hosting, cloud storage, colocation
Stay online with enterprise data centers and the best network in the business
Choose flexible plans and management services without long-term contracts
Personal 24x7 support from experience hosting pros just a phone call away.
http://p.sf.net/sfu/theplanet-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] Some question about "Lighting and Material of Halo3" and "Lightmap compression in Halo 3"

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

I don't quite understand your coupling between harmonic orders and
coefficients.

If I remember correctly, spherical harmonics of order 0 is a flat value -- 1
coefficient.
Order 1 adds three cardinal directions -- 3 additional coefficients, for a
total of 4.
Order 2 adds another 5, for a total of 9.
Order 3 adds another 7, for a total of 16.
Order 4 adds another 9, for a total of 25.
...

You may be able to omit the constant term (calculating it or assuming it)
which would get a total harmonic count for order 3 of 15. Perhaps that's
where the number comes from (but I have not had time to check the paper,
just guessing here).

Generally, if you separate out the diffuse/ambient reflection/albedo texture
to a "regular" texture, you don't need to store the light response in RGB
channels, just like you don't use different light fall-off equations for the
different color channels. (Except when you do Rayleigh scattering and
similar for atmospherics, I think...)

Sincerely,

jw

--
Americans might object: there is no way we would sacrifice our living
standards for the benefit of people in the rest of the world. Nevertheless,
whether we get there willingly or not, we shall soon have lower consumption
rates, because our present rates are unsustainable.



2010/1/29 Sébastien Lagarde <seb...@do...>

>  Hello all,
>
>
>
> I tried to contact the author of this two (now old) paper, without
> success,:
>
> "Lighting and Material of Halo 3" published at siggraph 2008 (
> http://ati.amd.com/developer/SIGGRAPH08/Chapter01-Chen-Lighting_and_Material_of_Halo3.pdf
> )
>
> and GDC 2008 conference "Lightmap compression in Halo 3" (
> http://toomuchlogic.com/Lightmap_Compression_2008_02_22.pdf)
>
> so I will ask some question to the list, if anyone is interested by the
> subject and has better understanding of math than me :)
>
>
>
> 1. "Lighting and Material of Halo 3"  About equation (5) the diffuse
> reflectance using SH basis
>
> the diffuse reflectance using SH basis is : k_d R_d Sum Lambda_i A_i
>
> A_i is the projection of the cosine lobe in SH, and as it is radially
> symetric.
>
> all coefficient with m != 0 are 0.
>
> After that the author give the first three term of A_i.
>
> I wondering how many band are use for this calculation  ? (order 3, 4 or
> more ?)
>
>
>
> I read from "Stupid spherical harmonics tricks" from Perter Pike sloan (
> http://www.ppsloan.org/publications/StupidSH36.pdf)
>
> that order 3 SH is sufficient for approximate light source
>
> but for HDR light sources he recommand order 5.
>
> As order 4 is 0 (From paper
> http://www.eecs.berkeley.edu/~ravir/lighting.pdf I get the formula for
> A_i)
>
> This mean 4 coefficient to store by color channel.
>
> As I am pretty sure the author store  HDR data, can someone lighten me ?
>
>
>
> 2. About texture storage (which are deduced from above statement)
>
>
>
> I try to figure out how are encoded the incident radiance in their
> SHLightmap.
>
> From GDC 2008 conference "Lightmap compression in Halo 3" I can read that
> the author need to
>
> store for each texel a vector of 5 * 3 float values.
>
> I don't figure what are the values exactly.
>
>
>
> My assumption is that "3" is for each channel color RGB,
>
> But I can't figure what's the 5 is ?
>
> Are they 5 first band of SH order like I suppose above (but as I said, we
> only need 4 coefficient in this case)
>
> or maybe order 6 ?
>
>
>
> In this same paper later I found:
>
> A. Two DXT5 texture for each SH coefficient channel (HDR,
> positive/negative)
>
> And
>
> B. Each band of the SH coefficients (RGB) are converted to Luvw space
>
>
>
> I suppose that Luvw space is what is describe in this paper "Rendering from
> Compressed High Dynamic Range Textures on
>
> Programmable Graphics Hardware" by Peter Pike sloan and al.(
> ftp://ftp.research.microsoft.com/pub/tr/TR-2006-152.pdf)
>
>
>
> What I don't understand is that A and B seem different. I can't understand
> what is store.
>
> Are they storing for each band the triplet RGB of SH coeeficient, mean 3
> float value for two DXT5 x order
>
> or do they store store 5 SH coefficient for channel color R in two DXT5 ?
>
>
>
> So what are the total storage cost of all the 5 * 3 float value in term of
> DXT5 texture ?
>
> Cause It looks like to be pretty big.
>
>
>
> Thanks for anyone interested by this post
>
>
>
> Best regards
>
>
>
> Lagarde Sébastien
>
>
> ------------------------------------------------------------------------------
> The Planet: dedicated and managed hosting, cloud storage, colocation
> Stay online with enterprise data centers and the best network in the
> business
> Choose flexible plans and management services without long-term contracts
> Personal 24x7 support from experience hosting pros just a phone call away.
> http://p.sf.net/sfu/theplanet-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] Some question about "Lighting and Material of Halo3" and "Lightmap compression in Halo 3"

[Sébastien L. <seb...@do...>]

Hello all, 

 

I tried to contact the author of this two (now old) paper, without success,:

"Lighting and Material of Halo 3" published at siggraph 2008 (http://ati.amd.com/developer/SIGGRAPH08/Chapter01-Chen-Lighting_and_Material_of_Halo3.pdf)

and GDC 2008 conference "Lightmap compression in Halo 3" (http://toomuchlogic.com/Lightmap_Compression_2008_02_22.pdf)

so I will ask some question to the list, if anyone is interested by the subject and has better understanding of math than me :)

 

1. "Lighting and Material of Halo 3"  About equation (5) the diffuse reflectance using SH basis

the diffuse reflectance using SH basis is : k_d R_d Sum Lambda_i A_i

A_i is the projection of the cosine lobe in SH, and as it is radially symetric.

all coefficient with m != 0 are 0.

After that the author give the first three term of A_i.

I wondering how many band are use for this calculation  ? (order 3, 4 or more ?)

 

I read from "Stupid spherical harmonics tricks" from Perter Pike sloan (http://www.ppsloan.org/publications/StupidSH36.pdf)

that order 3 SH is sufficient for approximate light source

but for HDR light sources he recommand order 5.

As order 4 is 0 (From paper http://www.eecs.berkeley.edu/~ravir/lighting.pdf I get the formula for A_i)

This mean 4 coefficient to store by color channel.

As I am pretty sure the author store  HDR data, can someone lighten me ?

 

2. About texture storage (which are deduced from above statement)

 

I try to figure out how are encoded the incident radiance in their SHLightmap.

>From GDC 2008 conference "Lightmap compression in Halo 3" I can read that the author need to

store for each texel a vector of 5 * 3 float values.

I don't figure what are the values exactly.

 

My assumption is that "3" is for each channel color RGB,

But I can't figure what's the 5 is ?

Are they 5 first band of SH order like I suppose above (but as I said, we only need 4 coefficient in this case)

or maybe order 6 ?

 

In this same paper later I found:

A. Two DXT5 texture for each SH coefficient channel (HDR, positive/negative)

And

B. Each band of the SH coefficients (RGB) are converted to Luvw space

 

I suppose that Luvw space is what is describe in this paper "Rendering from Compressed High Dynamic Range Textures on

Programmable Graphics Hardware" by Peter Pike sloan and al.(ftp://ftp.research.microsoft.com/pub/tr/TR-2006-152.pdf)

 

What I don't understand is that A and B seem different. I can't understand what is store.

Are they storing for each band the triplet RGB of SH coeeficient, mean 3 float value for two DXT5 x order

or do they store store 5 SH coefficient for channel color R in two DXT5 ?

 

So what are the total storage cost of all the 5 * 3 float value in term of DXT5 texture ?

Cause It looks like to be pretty big.

 

Thanks for anyone interested by this post

 

Best regards

 

Lagarde Sébastien

Re: [Algorithms] Compose rectangles within another rectangle

[Jetro L. <jl...@gm...>]

In addition to the blackpawn & J.Arevalo references already mentioned,
John Ratcliff has also posted his take on texture atlas creation:
http://codesuppository.blogspot.com/2009/04/texture-packing-code-snippet-to-compute.html

<http://codesuppository.blogspot.com/2009/04/texture-packing-code-snippet-to-compute.html>That
solution adds the twist that you can actually rotate rectangles so that all
rectangle
widths are always >= heights (just rotate uv coordinates as well).


If somebody does comparisons about how much that actually gives additional
help
for texture space usage, I'd be interested in hearing the results...


-- 
Jetro Lauha - http://jet.ro


On Fri, Jan 22, 2010 at 9:18 PM, Arno Gerretsen <ar...@ag...> wrote:

> Hi,
>
> I am looking for an algorithm that can help me to compose a number of
> rectangles, with different sizes, within a bigger rectangle. So I want
> to pack them most efficiently within the bigger rectangle. Does anybody
> know the best approach to this, except for just trial and error.
>
> The background is that I want to compose a big texture sheet from a
> collection of smaller texture pieces automaticaly.
>
> --
> Arno
>
>
>
> ------------------------------------------------------------------------------
> Throughout its 18-year history, RSA Conference consistently attracts the
> world's best and brightest in the field, creating opportunities for
> Conference
> attendees to learn about information security's most important issues
> through
> interactions with peers, luminaries and emerging and established companies.
> http://p.sf.net/sfu/rsaconf-dev2dev
> _______________________________________________
> 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] Compose rectangles within another rectangle

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

Arno Gerretsen schrieb:
> Hi,
> 
> I am looking for an algorithm that can help me to compose a number of 
> rectangles, with different sizes, within a bigger rectangle. So I want 
> to pack them most efficiently within the bigger rectangle. Does anybody 
> know the best approach to this, except for just trial and error.
> 
> The background is that I want to compose a big texture sheet from a 
> collection of smaller texture pieces automaticaly.

This might help you as well:

   http://www.flipcode.com/archives/Rectangle_Placement.shtml

-Fabian Giesen

Re: [Algorithms] Compose rectangles within another rectangle

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

On Sat, Jan 23, 2010 at 2:46 AM, Arno Gerretsen <ar...@ag...> wrote:

> Thank you both for the reply. Knowing the exact scientific name makes it
> a lot easier to find more information on this. So thanks for putting me
> in the right direction. I am sure I will be able to find a way that I
> can implement on my tool.
>
> Arno
>
>
You might also want to search for references to the "knapsack problem,"
which is closely related. It is one of the canonical NP-complete problems,
meaning that there currently exists no know algorithm that will find the
optimal solution in polynomial time (like N^2 or N^3). Thus, most solutions
are approximations that give you "good enough" answers in relatively fast
time, or solutions that take a lot of time to try *all* (or a substantial
subset) of solutions, to get the optional solution.

Sincerely,

jw


--
Americans might object: there is no way we would sacrifice our living
standards for the benefit of people in the rest of the world. Nevertheless,
whether we get there willingly or not, we shall soon have lower consumption
rates, because our present rates are unsustainable.

Re: [Algorithms] Compose rectangles within another rectangle

[Arno G. <ar...@ag...>]

Thank you both for the reply. Knowing the exact scientific name makes it 
a lot easier to find more information on this. So thanks for putting me 
in the right direction. I am sure I will be able to find a way that I 
can implement on my tool.

Arno


On 22/01/2010 22:39, Jason Hughes wrote:
> This is called bin packing.  You'll find much research on it, and even
> this very question has been answered a few times in the archives of this
> list.  To save you a few seconds, some folks suggest an approach similar
> to Tetris.  Personally, I sort rectangles by the longest axis and pack
> from longer to shorter, minimizing the distance to the origin of the
> texture sheet when placing them.  That tends to work pretty well.  If
> you can do it offline, slowly shuffling the order you submit the
> rectangles a little bit can get you some good gains over the simple
> sorting method, but it all depends on how much effort you want to put
> into it.
>
> Best of luck,
> JH
>
> Jason Hughes
> President
> Steel Penny Games, Inc.
> Austin, TX
>
>
>
> Arno Gerretsen wrote:
>    
>> Hi,
>>
>> I am looking for an algorithm that can help me to compose a number of
>> rectangles, with different sizes, within a bigger rectangle. So I want
>> to pack them most efficiently within the bigger rectangle. Does anybody
>> know the best approach to this, except for just trial and error.
>>
>> The background is that I want to compose a big texture sheet from a
>> collection of smaller texture pieces automaticaly.
>>
>>
>>      
> ------------------------------------------------------------------------------
> Throughout its 18-year history, RSA Conference consistently attracts the
> world's best and brightest in the field, creating opportunities for Conference
> attendees to learn about information security's most important issues through
> interactions with peers, luminaries and emerging and established companies.
> http://p.sf.net/sfu/rsaconf-dev2dev
> _______________________________________________
> 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
>    


-- 
Arno

Re: [Algorithms] Compose rectangles within another rectangle

[Jason H. <jh...@st...>]

This is called bin packing.  You'll find much research on it, and even 
this very question has been answered a few times in the archives of this 
list.  To save you a few seconds, some folks suggest an approach similar 
to Tetris.  Personally, I sort rectangles by the longest axis and pack 
from longer to shorter, minimizing the distance to the origin of the 
texture sheet when placing them.  That tends to work pretty well.  If 
you can do it offline, slowly shuffling the order you submit the 
rectangles a little bit can get you some good gains over the simple 
sorting method, but it all depends on how much effort you want to put 
into it.

Best of luck,
JH

Jason Hughes
President
Steel Penny Games, Inc.
Austin, TX



Arno Gerretsen wrote:
> Hi,
>
> I am looking for an algorithm that can help me to compose a number of 
> rectangles, with different sizes, within a bigger rectangle. So I want 
> to pack them most efficiently within the bigger rectangle. Does anybody 
> know the best approach to this, except for just trial and error.
>
> The background is that I want to compose a big texture sheet from a 
> collection of smaller texture pieces automaticaly.
>
>   

Re: [Algorithms] Compose rectangles within another rectangle

[Eric C. <er....@gm...>]

On Fri, Jan 22, 2010 at 2:18 PM, Arno Gerretsen <ar...@ag...> wrote:

> I am looking for an algorithm that can help me to compose a number of
> rectangles, with different sizes, within a bigger rectangle. So I want
> to pack them most efficiently within the bigger rectangle. Does anybody
> know the best approach to this, except for just trial and error.
>

This might be useful...

http://www.blackpawn.com/texts/lightmaps/default.html

[Algorithms] Compose rectangles within another rectangle

[Arno G. <ar...@ag...>]

Hi,

I am looking for an algorithm that can help me to compose a number of 
rectangles, with different sizes, within a bigger rectangle. So I want 
to pack them most efficiently within the bigger rectangle. Does anybody 
know the best approach to this, except for just trial and error.

The background is that I want to compose a big texture sheet from a 
collection of smaller texture pieces automaticaly.

-- 
Arno

Re: [Algorithms] Rotation from 4 points

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

!!!

Sure!

You are right, Paul!

Easy and clever solution, thank you !

Jose


--- Em ter, 19/1/10, Pau...@sc... <Pau...@sc...> escreveu:

> De: Pau...@sc... <Pau...@sc...>
> Assunto: Re: [Algorithms] Rotation from 4 points
> Para: "Game Development Algorithms" <gda...@li...>
> Data: Terça-feira, 19 de Janeiro de 2010, 9:15
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA256
> 
> > How to extract one of these informations:
> > 
> > 1 - A quaternion representing the rotation
> 
> Hi there,
> 
> Just form the basis vectors and you have a matrix right
> away. Convert to 
> quat. Done :)
> 
> I.e. Subtract your corner points from the 'central' point,
> and those are 
> your basis vectors.
> 
> row 0 = D-A
> row 1 = B-A
> row 2 = C-A
> 
> 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 pos...@sc...
> 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
> 
> wsBVAwUBS1WTBnajGqjtoMHxAQhirwgAmWoIGhiqB3qxlkaXVwQR1Tt2btMcJr02
> Rg9mFOv9VeyJS4CbbMIglcAOePpo1C9J/4VWf+f0OE7ZTqEH3iu17ihj8Gr7nuim
> RoDic0ebhbgce8osQquHCEhLEqNtoiUZBxA9VGASHgo/5sKTNHuBM9L45qJUkEPj
> CSTvwMcTNLp07/XSBKVMFiGTX8twTDSSFaK9fuFZS9g81n86E8wC/GbUGN9miygO
> 3onNOhna6VpHGh+di9aE+cHCmoWkW/6grGudPLXEhnEWXV9y1X71ywoNbJxq7obG
> Eet/k/0fNTqwW7RonuelmIBOq+6m+W+jr/QtP+tFhEmpwEb3PHyFFA==
> =WdlI
> -----END PGP SIGNATURE-----
> 
> ------------------------------------------------------------------------------
> Throughout its 18-year history, RSA Conference consistently
> attracts the
> world's best and brightest in the field, creating
> opportunities for Conference
> attendees to learn about information security's most
> important issues through
> interactions with peers, luminaries and emerging and
> established companies.
> http://p.sf.net/sfu/rsaconf-dev2dev
> _______________________________________________
> 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] Rotation from 4 points

[<Pau...@sc...>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

> How to extract one of these informations:
> 
> 1 - A quaternion representing the rotation

Hi there,

Just form the basis vectors and you have a matrix right away. Convert to 
quat. Done :)

I.e. Subtract your corner points from the 'central' point, and those are 
your basis vectors.

row 0 = D-A
row 1 = B-A
row 2 = C-A

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 pos...@sc...
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

wsBVAwUBS1WTBnajGqjtoMHxAQhirwgAmWoIGhiqB3qxlkaXVwQR1Tt2btMcJr02
Rg9mFOv9VeyJS4CbbMIglcAOePpo1C9J/4VWf+f0OE7ZTqEH3iu17ihj8Gr7nuim
RoDic0ebhbgce8osQquHCEhLEqNtoiUZBxA9VGASHgo/5sKTNHuBM9L45qJUkEPj
CSTvwMcTNLp07/XSBKVMFiGTX8twTDSSFaK9fuFZS9g81n86E8wC/GbUGN9miygO
3onNOhna6VpHGh+di9aE+cHCmoWkW/6grGudPLXEhnEWXV9y1X71ywoNbJxq7obG
Eet/k/0fNTqwW7RonuelmIBOq+6m+W+jr/QtP+tFhEmpwEb3PHyFFA==
=WdlI
-----END PGP SIGNATURE-----