gdalgorithms-list

Re: [Algorithms] Fast SH squaring

[Dan G. <dan...@gm...>]

I implemented the algorithm from that paper, with the help of
Peter-Pike Sloan for a yet unreleased replacement of the functions in
DX. Would people want to see such a library?

cheers
DanG

On Mon, Oct 19, 2009 at 11:14 AM,
<chr...@pl...> wrote:
> Ben Yeoh wrote:
>
>> There's one paragraph however where it's mentioned that "SH squares
>> are also cheaper than general SH products" (ie, computing F * F is
>> more efficient than F * G), but which is not elaborated on. Sadly,
>> the details are not immediately obvious to me. Can someone shed some
>> light on how and why? Apparently, this is efficient enough to
>> compute in the GPU (unlike a general SH triple product).
>
> Googling for "sh squaring"
>
> http://www.google.com/search?hl=en&ie=UTF-8&q=%22sh+squaring%22&btnG=Search
>
> returns exactly ONE hit.
>
>
> Christer Ericson, Director of Tools and Technology
> Sony Computer Entertainment, Santa Monica
>
>
> ------------------------------------------------------------------------------
> Come build with us! The BlackBerry(R) Developer Conference in SF, CA
> is the only developer event you need to attend this year. Jumpstart your
> developing skills, take BlackBerry mobile applications to market and stay
> ahead of the curve. Join us from November 9 - 12, 2009. Register now!
> http://p.sf.net/sfu/devconference
> _______________________________________________
> 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
>



-- 
Dan Glastonbury, Dan dot Glastonbury at gmail dot com
`Pour encourjay lays ortras'

Re: [Algorithms] Fast SH squaring

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

Ben Yeoh wrote:

> There's one paragraph however where it's mentioned that "SH squares
> are also cheaper than general SH products" (ie, computing F * F is
> more efficient than F * G), but which is not elaborated on. Sadly,
> the details are not immediately obvious to me. Can someone shed some
> light on how and why? Apparently, this is efficient enough to
> compute in the GPU (unlike a general SH triple product).

Googling for "sh squaring"

http://www.google.com/search?hl=en&ie=UTF-8&q=%22sh+squaring%22&btnG=Search

returns exactly ONE hit.


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

Re: [Algorithms] Real-Time Global Illumination

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

Those forums are coming at it from a different perspective then games.
E.g, doing fast raytracing/photon mapping applications. You'll see a lot
of stuff on speeding up kd-tree's, CUDA/openCL etc. Though, there is a
lot of good information and smart people that hang out there

For games it seems like there are two approaches that would work,
1) Radiosity based solutions (or any pre-computed hierarchical light
transport methods, wavelets, clustering, progressive refinement). Most
of them are based on finite element methods.
2) Virtual point light/splatting style methods

Here are some papers that can get you started (just a dump and no
organization),
A Meshless Hierarchical Representation for Light Transport 
Direct-to-Indirect Transfer for Cinematic Relighting
Instant Radiosity
Interactive Rendering of Interior Scenes with Dynamic Environment
Illumination
Precomputed Local Radiance Transfer for Real-Time Lighting Design
Meshless Finite Elements for Hierarchical Global Illumination
An approximate global illumination System for Computer Generated Films
Wavelet Radiance Transport for Interactive Indirect Lighting
http://kesen.huang.googlepages.com/sig2008.html
http://kesen.huang.googlepages.com/sig2009.html
Light Propagation Volumes
Incremental Instant Radiosity for Real-Time Indirect Illumination
A Hardware Architecture for Surface Splatting

I really like the "A Meshless Hierarchical Representation for Light
Transport" paper. A lot of the papers reference each other or reference
lots of other good ones too.

I'm sure there are a bit of people on this list that could help out if
you have any specific questions.

-= Dave

-----Original Message-----
From: Miles Macklin [mailto:mil...@gm...] 
Sent: Monday, October 19, 2009 9:06 AM
To: Game Development Algorithms
Subject: Re: [Algorithms] Real-Time Global Illumination

The forums over at http://ompf.org/ are worth keeping an eye on.

- Miles

On Sun, Oct 18, 2009 at 11:37 PM, Gary Snethen <gsn...@cr...>
wrote:
>
> Hey Gang,
>
> What are the best forums (or mailing lists, etc.) for serious
discussions on
> real-time approximations to global illumination and other advanced
rendering
> techniques?
>
> Is anyone here doing research in the area?
>
> Thanks!
>
> Gary Snethen
> Lead Engine Programmer
> Crystal Dynamics, Inc.
>
> ______________________________________________________________________
> This email has been scanned by the MessageLabs
> ______________________________________________________________________
>
>
------------------------------------------------------------------------
------
> Come build with us! The BlackBerry(R) Developer Conference in SF, CA
> is the only developer event you need to attend this year. Jumpstart
your
> developing skills, take BlackBerry mobile applications to market and
stay
> ahead of the curve. Join us from November 9 - 12, 2009. Register now!
> http://p.sf.net/sfu/devconference
> _______________________________________________
> 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
>

------------------------------------------------------------------------
------
Come build with us! The BlackBerry(R) Developer Conference in SF, CA
is the only developer event you need to attend this year. Jumpstart your
developing skills, take BlackBerry mobile applications to market and
stay 
ahead of the curve. Join us from November 9 - 12, 2009. Register now!
http://p.sf.net/sfu/devconference
_______________________________________________
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] Real-Time Global Illumination

[Miles M. <mil...@gm...>]

The forums over at http://ompf.org/ are worth keeping an eye on.

- Miles

On Sun, Oct 18, 2009 at 11:37 PM, Gary Snethen <gsn...@cr...> wrote:
>
> Hey Gang,
>
> What are the best forums (or mailing lists, etc.) for serious discussions on
> real-time approximations to global illumination and other advanced rendering
> techniques?
>
> Is anyone here doing research in the area?
>
> Thanks!
>
> Gary Snethen
> Lead Engine Programmer
> Crystal Dynamics, Inc.
>
> ______________________________________________________________________
> This email has been scanned by the MessageLabs
> ______________________________________________________________________
>
> ------------------------------------------------------------------------------
> Come build with us! The BlackBerry(R) Developer Conference in SF, CA
> is the only developer event you need to attend this year. Jumpstart your
> developing skills, take BlackBerry mobile applications to market and stay
> ahead of the curve. Join us from November 9 - 12, 2009. Register now!
> http://p.sf.net/sfu/devconference
> _______________________________________________
> 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] Real-Time Global Illumination

[Gary S. <gsn...@cr...>]

Hey Gang,

What are the best forums (or mailing lists, etc.) for serious discussions on real-time approximations to global illumination and other advanced rendering techniques?

Is anyone here doing research in the area?

Thanks!

Gary Snethen
Lead Engine Programmer
Crystal Dynamics, Inc.

______________________________________________________________________
This email has been scanned by the MessageLabs
______________________________________________________________________

[Algorithms] Fast SH squaring

[Ben Y. <shu...@gm...>]

Hi guys,

I've been catching up on some of the global illumination literature
recently, and I found the SH exponentiation paper by Ren et al especially
interesting.

There's one paragraph however where it's mentioned that "SH squares are also
cheaper than general SH products" (ie, computing F * F is more efficient
than F * G), but which is not elaborated on. Sadly, the details are not
immediately obvious to me. Can someone shed some light on how and why?
Apparently, this is efficient enough to compute in the GPU (unlike a general
SH triple product).

Thanks,
Ben Yeoh

Re: [Algorithms] Broad-phase collision detection for dynamic objects

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

Jon Watte wrote:
> You could put bounding volumes of the moving objects into the grid (or
> loose octree, or sweep-and-prune). That would identify possible
> overlapping pairs. It still would be sufficiently tight, unless you have
> multiple objects moving diagonally really fast.

Jon is right (again). For the broad-phase, the simplest
solution is to work with volumes that bound the objects
under motion, and insert these volumes into your
spatial partitioning (hgrid, etc).

This breaks down for very fast moving objects (e.g.
projectiles) which you may want to handle another way,
but only if they actually show up as a bottleneck
(which is unlikely).


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

Re: [Algorithms] Broad-phase collision detection for dynamic objects

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

Stuart Golodetz wrote:
>
> before.) Basically I started out thinking about a hierarchical grid-type 
> scheme (the sort you'd find in e.g. Christer Ericson's Real-Time 
> Collision Detection book) but my understanding was that as written it 
> works by looking only at the objects' positions at the point of 
> collision detection, and doesn't take account of their movements over 
>   

You could put bounding volumes of the moving objects into the grid (or 
loose octree, or sweep-and-prune). That would identify possible 
overlapping pairs. It still would be sufficiently tight, unless you have 
multiple objects moving diagonally really fast.
Also, I believe the Bullet library uses continuous (swept) collision 
detection, so you can find a bunch of code there to read up on.

Sincerely,

jw


-- 

  Revenge is the most pointless and damaging of human desires.

Re: [Algorithms] Comparing apples to apples : compression libraries

[Ralph <sp...@gm...>]

This looks pretty cool! I'm very late to this thread, but, have you 
checked out LZF (http://oldhome.schmorp.de/marc/liblzf.html) - very 
quick, good for repeating data.  Was easy to get setup on the consoles.  
We are using it for network compression and it works well enough and is 
very cheap in term of CPU cost.  Licenses available are GPL and BSD (like).

Ralph

On 3/25/2008 4:30 PM, John W. Ratcliff wrote:
>
> With pretty much every developer there comes a time when you need to 
> use a compression library; not because you want to 'zip' up a massive 
> archive but more because you want to compress some game data on the 
> fly before you transmit it over the network, or to shrink the size of 
> a local cache or something.  And, like pretty much every developer, 
> you end up wandering through a maze of open source libraries on the 
> internet, each of which has entirely different API, source code 
> layout, and license agreement.  Just figuring out to call 
> 'compressData' (if you even can) is often hours of wading through 
> documentation and dealing with build/configuration issues.
>
> For your convenience I am releasing a small code snippet that I wrote 
> when I was trying to evaluate a replacement compression library than 
> the one we are currently using.  The simple fact of the matter is that 
> I don't believe any other programmer should have to waste the same 
> amount of stupid time I did wrestling these libraries into a 
> convenient form.
>
> http://www.amillionpixels.us/test_compression_1.0.exe
>
> Here is the complete API to my wrapper interface:
>
> // Block compression/decompression library wrapper by John W. Ratcliff 
> http://www.codesuppository.blogspot.com/
>
> enum CompressionType
>
> {
>
> CT_INVALID,
>
> CT_CRYPTO_GZIP, // The CryptoPP library implementation of GZIP   
> http://www.cryptopp.com
>
> CT_MINILZO, // The MiniLZO library  
> http://www.oberhumer.com/opensource/lzo/
>
> CT_ZLIB, // The ZLIB library   http://www.zlib.net/
>
> CT_BZIP, // The BZIP library  http://www.bzip.org/
>
> };
>
> void * compressData(const void *source,int len,int 
> &outlen,CompressionType type=CT_ZLIB);
>
> void * decompressData(const void *source,int clen,int &outlen);
>
> void deleteData(void* mem);
>
> CompressionType getCompressionType(const void *mem,int len);
>
> const char      *getCompressionTypeString(CompressionType type);
>
> };
>
> This release supports four open source compression libraries.  The 
> CRYPTOPP implementation of GZIP, MINILZO, ZLIB, and BZIP.
>
> This API simply supports block memory compression and decompression.  
> You can compress a block of memory using any one of the four 
> compressors.  The compressed memory has a small header on it that 
> indicates which compressor was used, the size of the uncompressed 
> memory block, and a CRC so that it can easily and safely decompressed.
>
> The test application, called 'test_compression', loads a roughly 10mb 
> XML file and runs it through each compressor and decompressor and 
> measures the performance characteristcs of each.  The results are as 
> follows:
>
> Testing Compression rate and speed with various compressors.
>
> ---------------------------------------------------------------
>
> Compress:CT_CRYPTO  :FROM: 10,436,335 TO:  2,498,433   23%    1,170 MS
>
> Compress:CT_MINILZO :FROM: 10,436,335 TO:  3,940,072   37%       97 MS
>
> Compress:CT_ZLIB    :FROM: 10,436,335 TO:  3,299,771   31%      157 MS
>
> Compress:CT_BZIP    :FROM: 10,436,335 TO:  2,270,695   21%    1,544 MS
>
> ---------------------------------------------------------------
>
> Testing Decompression speed with various decompressors.
>
> ---------------------------------------------------------------
>
> Decompress:CT_CRYPTO  :FROM:  2,498,433 TO: 10,436,335      258 MS
>
> Decompress:CT_MINILZO :FROM:  3,940,072 TO: 10,436,335       42 MS
>
> Decompress:CT_ZLIB    :FROM:  3,299,771 TO: 10,436,335       69 MS
>
> Decompress:CT_BZIP    :FROM:  2,270,695 TO: 10,436,335      390 MS
>
> As expected, MINILZO is the fastest.  Unfortunately MINILZO uses a GPL 
> license and cannot be used in commercial products.  The rest have 
> licenses which are more flexible.  Check the links for each package to 
> see if it is right for you.  I did include the 'CryptoPP' library for 
> completeness though but, to be frank, I am not very impressed with 
> this package as the compression and decompression rates are very 
> poor.  As you would expect BZIP gets the best compression rate but 
> does not perform as quickly.
>
> I am fairly impressed with ZLIB, especially because you can use it in 
> a streaming mode as well, which is excellent for network 
> communications layers.  (FYI, the assembly language version of the 
> ZLIB decompressor is hardly any faster than the optimized C code and 
> was not included here.)
>
> You might wonder why I'm even bothering to post this little snippet.  
> Beside the fact that I hope to save other programmers a little bit of 
> time in the future, I encourage any other developers of compression 
> libraries to drop them into this framework so we can stop comparing 
> apples to oranges when it comes to these technologies.  A large XML 
> file is a typical use case for the kind of data a game developer might 
> want to squeeze out some space savings for.  I am also happy to modify 
> the installer and include more standardized sample data if that is 
> relevant.
>
> I started to add in support for the LZMA library, however they only 
> offer a simple sample decompressor while the compression code is a lot 
> more difficult to extract into a single C style API call.
>
> This demo comes with an easy to use installer and a solution and 
> project file for visual studio 2005.  All of the compression code 
> itself is multi-platform and only the little demo app makes any OS 
> specific calls.  The libraries are each included as raw source, each 
> located in their own directory.  None of the source has been removed 
> (except for test code) so you are not required to use the compression 
> libraries via the wrapper layer.
>
> If anyone feels compelled to add additional compression libraries to 
> this test framework please let me know and I will make a point to 
> include it in a new drop.
>
> Thanks, I hope somebody finds this useful.
>
> John
>
>
> -------------------------------------------------------------------------
> Check out the new SourceForge.net Marketplace.
> It's the best place to buy or sell services for
> just about anything Open Source.
> http://ad.doubleclick.net/clk;164216239;13503038;w?http://sf.net/marketplace
>
>
> _______________________________________________
> 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] Algo for weight assignment in skinned animation

[Ignacio C. <ica...@nv...>]

Blender also has an implementation of automatic weight assignment based on that paper:

http://www.blender.org/development/release-logs/blender-246/skinning/




-----Original Message-----
From: Bill Baxter [mailto:wb...@gm...] 
Sent: Thursday, October 08, 2009 11:49 AM
To: Game Development Algorithms
Subject: Re: [Algorithms] Algo for weight assignment in skinned animation

Heat diffusion for weights.  Sounds reminiscent of the Harmonic
Coordinates cage-based deformation technique of Joshi et al.

The implementation looks easy enough, so I'll give it a try.   Thanks
for pointing that out!


--bb

On Wed, Oct 7, 2009 at 10:43 PM, Peter-Pike Sloan
<pet...@ho...> wrote:
> Hi Bill,
> I've heard people had good results with this paper:
> http://www.cs.washington.edu/homes/jovan/papers/baran-2007-ara.pdf
> (Just the heat diffusion skinning part, don't know about the other bits...)
> Peter-Pike
>
>> From: wb...@gm...
>> Date: Wed, 7 Oct 2009 17:29:29 -0700
>> To: gda...@li...
>> Subject: [Algorithms] Algo for weight assignment in skinned animation
>>
>> Is there any standard algorithm used for automatically assigning
>> reasonable bone weights to vertices in a mesh, given just the mesh and
>> the skeleton? (I.e. you have no animation data, so you can't use
>> observed deformations to guide how to assign the weights as in James &
>> Twigg's "Skinning Mesh Animations"). And in particular are there any
>> algorithms which work within a per-vertex weight budget constraint, so
>> that you can use hardware skinning effectively? I've been looking
>> around, but haven't been able to find anything.
>>
>> Thanks,
>> --bb
>>
>>
>> ------------------------------------------------------------------------------
>> Come build with us! The BlackBerry(R) Developer Conference in SF, CA
>> is the only developer event you need to attend this year. Jumpstart your
>> developing skills, take BlackBerry mobile applications to market and stay
>> ahead of the curve. Join us from November 9 - 12, 2009. Register now!
>> http://p.sf.net/sfu/devconference
>> _______________________________________________
>> 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
>
> ------------------------------------------------------------------------------
> Come build with us! The BlackBerry(R) Developer Conference in SF, CA
> is the only developer event you need to attend this year. Jumpstart your
> developing skills, take BlackBerry mobile applications to market and stay
> ahead of the curve. Join us from November 9 - 12, 2009. Register now!
> http://p.sf.net/sfu/devconference
> _______________________________________________
> 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
>

------------------------------------------------------------------------------
Come build with us! The BlackBerry(R) Developer Conference in SF, CA
is the only developer event you need to attend this year. Jumpstart your
developing skills, take BlackBerry mobile applications to market and stay 
ahead of the curve. Join us from November 9 - 12, 2009. Register now!
http://p.sf.net/sfu/devconference
_______________________________________________
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
-----------------------------------------------------------------------------------
This email message is for the sole use of the intended recipient(s) and may contain
confidential information.  Any unauthorized review, use, disclosure or distribution
is prohibited.  If you are not the intended recipient, please contact the sender by
reply email and destroy all copies of the original message.
-----------------------------------------------------------------------------------

Re: [Algorithms] Algo for weight assignment in skinned animation

[Bill B. <wb...@gm...>]

Heat diffusion for weights.  Sounds reminiscent of the Harmonic
Coordinates cage-based deformation technique of Joshi et al.

The implementation looks easy enough, so I'll give it a try.   Thanks
for pointing that out!


--bb

On Wed, Oct 7, 2009 at 10:43 PM, Peter-Pike Sloan
<pet...@ho...> wrote:
> Hi Bill,
> I've heard people had good results with this paper:
> http://www.cs.washington.edu/homes/jovan/papers/baran-2007-ara.pdf
> (Just the heat diffusion skinning part, don't know about the other bits...)
> Peter-Pike
>
>> From: wb...@gm...
>> Date: Wed, 7 Oct 2009 17:29:29 -0700
>> To: gda...@li...
>> Subject: [Algorithms] Algo for weight assignment in skinned animation
>>
>> Is there any standard algorithm used for automatically assigning
>> reasonable bone weights to vertices in a mesh, given just the mesh and
>> the skeleton? (I.e. you have no animation data, so you can't use
>> observed deformations to guide how to assign the weights as in James &
>> Twigg's "Skinning Mesh Animations"). And in particular are there any
>> algorithms which work within a per-vertex weight budget constraint, so
>> that you can use hardware skinning effectively? I've been looking
>> around, but haven't been able to find anything.
>>
>> Thanks,
>> --bb
>>
>>
>> ------------------------------------------------------------------------------
>> Come build with us! The BlackBerry(R) Developer Conference in SF, CA
>> is the only developer event you need to attend this year. Jumpstart your
>> developing skills, take BlackBerry mobile applications to market and stay
>> ahead of the curve. Join us from November 9 - 12, 2009. Register now!
>> http://p.sf.net/sfu/devconference
>> _______________________________________________
>> 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
>
> ------------------------------------------------------------------------------
> Come build with us! The BlackBerry(R) Developer Conference in SF, CA
> is the only developer event you need to attend this year. Jumpstart your
> developing skills, take BlackBerry mobile applications to market and stay
> ahead of the curve. Join us from November 9 - 12, 2009. Register now!
> http://p.sf.net/sfu/devconference
> _______________________________________________
> 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] Algo for weight assignment in skinned animation

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

Hi Bill,
I've heard people had good results with this paper:
http://www.cs.washington.edu/homes/jovan/papers/baran-2007-ara.pdf
(Just the heat diffusion skinning part, don't know about the other bits...)
Peter-Pike

> From: wb...@gm...
> Date: Wed, 7 Oct 2009 17:29:29 -0700
> To: gda...@li...
> Subject: [Algorithms] Algo for weight assignment in skinned animation
> 
> Is there any standard algorithm used for automatically assigning
> reasonable bone weights to vertices in a mesh, given just the mesh and
> the skeleton?  (I.e. you have no animation data, so you can't use
> observed deformations to guide how to assign the weights as in James &
> Twigg's "Skinning Mesh Animations").   And in particular are there any
> algorithms which work within a per-vertex weight budget constraint, so
> that you can use hardware skinning effectively?   I've been looking
> around, but haven't been able to find anything.
> 
> Thanks,
> --bb
> 
> ------------------------------------------------------------------------------
> Come build with us! The BlackBerry(R) Developer Conference in SF, CA
> is the only developer event you need to attend this year. Jumpstart your
> developing skills, take BlackBerry mobile applications to market and stay 
> ahead of the curve. Join us from November 9 - 12, 2009. Register now!
> http://p.sf.net/sfu/devconference
> _______________________________________________
> 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] Algo for weight assignment in skinned animation

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

Bill,

I've thought about this on and off for years, but never took the time to 
attempt it, so grain of salt here.  It seems to me that the best smooth 
skinning is generally one that induces the least amount of exaggerated 
motion, and maintain volume as much as possible.  So, perhaps you could 
artificially animate the skeleton by randomly perturbing the joints into 
many different poses (+/- 20 degrees per axis, maybe more) and adjust 
the weighting until you find one that relaxes the skin as much as 
possible (distance to closest point along weighted bones in bind pose is 
as close to fixed in all poses), and the volume of the mesh is as close 
to the original as possible.  Also, make sure that bones being weighted 
to are mostly shared among a given triangle and adjacent triangles.  
That'll help with flip-flopping when picking nearest bones under the skin. 

Not saying this would guarantee a usable skin weighting, but if these 
are salient components of a good skin weighting, it should help the 
artist start somewhere good. 

Problems: Scaling joints used for driven keys/muscle plumping is 
inherently not volume-preserving nor is an affixed distance from vertex 
to associated bone.  Skin sliding, cloth on characters, props, etc... 
there are plenty of places this wouldn't particularly help your artist.  
But for a basic initial skinning, it might do better than closest-bone.

It might also be fun to do a feature analysis of the mesh in bind pose, 
then make sure that those features are neither exaggerated nor 
diminished in other poses.  Might be able to do that by measuring the 
curvature change (with quadrics?) and attempting to retain nearly the 
same degree of curvature over non-extreme pose adjustments.  At least 
that way you'd know if you're attaching to the completely wrong joints 
and reduce their influence down to near-zero.

So, no, there's no standard algorithm.  :-)

JH

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



Bill Baxter wrote:
> Is there any standard algorithm used for automatically assigning
> reasonable bone weights to vertices in a mesh, given just the mesh and
> the skeleton?  (I.e. you have no animation data, so you can't use
> observed deformations to guide how to assign the weights as in James &
> Twigg's "Skinning Mesh Animations").   And in particular are there any
> algorithms which work within a per-vertex weight budget constraint, so
> that you can use hardware skinning effectively?   I've been looking
> around, but haven't been able to find anything.
>
> Thanks,
> --bb
>
>   

Re: [Algorithms] Algo for weight assignment in skinned animation

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

Bill Baxter wrote:
> Is there any standard algorithm used for automatically assigning
> reasonable bone weights to vertices in a mesh, given just the mesh and
> the skeleton?  (I.e. you have no animation data, so you can't use
>   

There is no *good* algorithm.

I've tried finding the closest bone behind the surface, with some 
favoring of bones closer to the reverse vertex normal. In this case, a 
"bone" is not just the rotation center, but an imaginary line from the 
center of the bone rotation matrix to the center of the child rotation 
matrix (and there will be multiple such lines for a single bone with 
multiple children). It is by no means great, but at least it gets the 
skin deforming. Knees, elbows and arm pits will never look good with 
automatic weights. In general, it's really no better than what you get 
when you reset a skin or Physique deformer modifier to all default 
envelopes in 3ds Max... Well, except you can make it so you never end up 
with "floating" vertices :-)

In fact, I know some artists who claim they will never look good with 
only skinning at all, that you need bulge deformers at a minimum :-)

Sincerely,

jw


-- 

  Revenge is the most pointless and damaging of human desires.

[Algorithms] Algo for weight assignment in skinned animation

[Bill B. <wb...@gm...>]

Is there any standard algorithm used for automatically assigning
reasonable bone weights to vertices in a mesh, given just the mesh and
the skeleton?  (I.e. you have no animation data, so you can't use
observed deformations to guide how to assign the weights as in James &
Twigg's "Skinning Mesh Animations").   And in particular are there any
algorithms which work within a per-vertex weight budget constraint, so
that you can use hardware skinning effectively?   I've been looking
around, but haven't been able to find anything.

Thanks,
--bb

Re: [Algorithms] Question to High Quality Antialiased Lines (Shader X7)/ Perspective divide

[Pablo de H. C. <pa...@vi...>]

On Thu, Oct 1, 2009 at 3:22 AM, Jorge Rodriguez <
jro...@ma...> wrote:

> This may be an overly simplistic or unacceptable solution, but the most
> straightforward and easy solution in my mind is to make the triangles a
> little bit thicker when the camera moves away, with a mandatory screen
> thickness so that it always is thick enough to not show that artifact.
>
> --
> Jorge Rodriguez
>
>
Me likey! Simple and practical.

Pablo
-- 
////////////////////////////////////////////////////////////////
Pablo de Heras Ciechomski, PhD, founder
pa...@vi...
phone: +41 22 534 96 25
mobile: +41 797 85 18 72
www.visualbiotech.ch

Re: [Algorithms] Question to High Quality Antialiased Lines (Shader X7)/ Perspective divide

[Jorge R. <jro...@ma...>]

This may be an overly simplistic or unacceptable solution, but the most
straightforward and easy solution in my mind is to make the triangles a
little bit thicker when the camera moves away, with a mandatory screen
thickness so that it always is thick enough to not show that artifact.

-- 
Jorge Rodriguez

Re: [Algorithms] Question to High Quality Antialiased Lines (Shader X7)/ Perspective divide

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

I think the z instead of w is an error in the original code. It would
probably still work fairly OK though most of the time, simply because z and
w usually are fairly close, except close to the camera (which is also why a
depth buffer often looks like plain white when viewed directly without
increasing contrast).

-Emil



-----Original Message-----
From: Christian Heckl [mailto:c....@qu...] 
Sent: 30 September 2009 23:53
To: gda...@li...
Subject: [Algorithms] Question to High Quality Antialiased Lines (Shader
X7)/ Perspective divide

Hi out there,

I am currently working on rendering laser beams through billboards in a 
deferred rendering environment. I have strong aliasing issues when 
viewing these beams from afar as they are pretty thin with respect to 
the overall world geometry. The result is a "marching-ant" stipple-like 
pattern as shown in the attached image.

Inspired by "Simplified High-Quality-Anti-Aliased Lines" (Shader X7) I 
decided that keeping the projected beams from falling below a certain 
pixel threshold when viewed from afar (thus effectively making them 
slightly thicker) would very well solve my problems and be "plausible" 
enough.

Unfortunately, I cannot quite make sense of some of the steps in the 
shader code.

To correctly calculate the position of the corners of the billboard, the 
screen space vector between the start and endpoint is taken as such:

p0 = start * world_view_projection
p1 = end * world_view_projection

//some modifications to p0.y and p1.y according to aspect ratio
...
//Calc vectors between points in screen space <--- Original comment
delta2.xy = p1.xy / p1.z - p0.xy/p0.z;  //<----- I dont quite get why 
the divisor is z and not w (for the homogenization step after the 
projection which is my understanding of screen space)

delta_p.xy = delta2.xy
delta_p.z = p1.z - w1.z;

//Calc UV basis vectors
float len = length(delta2.xy);
float3 U = delta_p / len; //<---- Why would I not use normalize(p1/p1.w 
- p0/p0.w) as a basis for U?

...//offset = (U * factor_u + V * factor_v)


//Undo perspective divide since the hardware will do it // <---- 
Original Comment, though perspective divide to my knowledge is /w not /z
Output.position.xy += offset * Output.position.z; // <---- 
Output.position.z is p0.z or p1.z, I would multiply by Output.position.w 
here

Can somebody shed some light on this? It might be something obvious, I 
just don't see it right now.

Thanks in advance for any pointers,
other solutions for solving the stipple problem are also welcome! (i.e. 
do i need a higher tesselation to avoid rasterizing very long and thin 
triangles?)

Chris

P.S.: I made the two modifications and it still looks "correct" (i.e. I 
can't spot any differences).

[Algorithms] Question to High Quality Antialiased Lines (Shader X7)/ Perspective divide

[Christian H. <c....@qu...>]

Hi out there,

I am currently working on rendering laser beams through billboards in a 
deferred rendering environment. I have strong aliasing issues when 
viewing these beams from afar as they are pretty thin with respect to 
the overall world geometry. The result is a "marching-ant" stipple-like 
pattern as shown in the attached image.

Inspired by "Simplified High-Quality-Anti-Aliased Lines" (Shader X7) I 
decided that keeping the projected beams from falling below a certain 
pixel threshold when viewed from afar (thus effectively making them 
slightly thicker) would very well solve my problems and be "plausible" 
enough.

Unfortunately, I cannot quite make sense of some of the steps in the 
shader code.

To correctly calculate the position of the corners of the billboard, the 
screen space vector between the start and endpoint is taken as such:

p0 = start * world_view_projection
p1 = end * world_view_projection

//some modifications to p0.y and p1.y according to aspect ratio
...
//Calc vectors between points in screen space <--- Original comment
delta2.xy = p1.xy / p1.z - p0.xy/p0.z;  //<----- I dont quite get why 
the divisor is z and not w (for the homogenization step after the 
projection which is my understanding of screen space)

delta_p.xy = delta2.xy
delta_p.z = p1.z - w1.z;

//Calc UV basis vectors
float len = length(delta2.xy);
float3 U = delta_p / len; //<---- Why would I not use normalize(p1/p1.w 
- p0/p0.w) as a basis for U?

...//offset = (U * factor_u + V * factor_v)


//Undo perspective divide since the hardware will do it // <---- 
Original Comment, though perspective divide to my knowledge is /w not /z
Output.position.xy += offset * Output.position.z; // <---- 
Output.position.z is p0.z or p1.z, I would multiply by Output.position.w 
here

Can somebody shed some light on this? It might be something obvious, I 
just don't see it right now.

Thanks in advance for any pointers,
other solutions for solving the stipple problem are also welcome! (i.e. 
do i need a higher tesselation to avoid rasterizing very long and thin 
triangles?)

Chris

P.S.: I made the two modifications and it still looks "correct" (i.e. I 
can't spot any differences).

Re: [Algorithms] Scroll direction algorithm

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

I think it's worth pointing out that unless you've planned ahead (or are
happy with some visual strangeness), this isn't going to work very well
for arbitrary meshes. Without constraints on the UV mapping, you're
going to get really crazy behavior along UV seams of the mesh. Even with
constraints, I don't see any general case where you're going to be able
to keep the mapped texture continuous across the mesh.

 

-Brian

 

From: Sim Dietrich [mailto:si...@gm...] 
Sent: Monday, September 28, 2009 1:44 PM
To: Game Development Algorithms
Subject: Re: [Algorithms] Scroll direction algorithm

 

If you have a tangent space basis for the mesh then this gives you the
information you need.  You can use this to convert from left/right in
world, view or model space, and convert into UV space.

 

You can look up tangent space lighting tutorials, then interpret the
scroll direction as a light direction.  Put the scroll direction vector
in model space, then through the per-vertex or per-pixel tangent space
matrix ( which will account for the texture direction flips ), then
scale the resulting vector based on the scroll speed and time, then add
this to the initial model UVs.

 

That should work...

 

On Mon, Sep 28, 2009 at 9:22 AM, Zafar Qamar
<zaf...@co...> wrote:

Hi,

 

I have a question about an algorithm in a shader. I hope this is the
right place to post. 

 

I basically have a mesh that has a texture on. In my shader I want the
effect to generally look like it is moving across the mesh from left to
right. Imagine it is a simple scrolling texture with some spots on, for
the case of this question.

 

However, the mesh has been UV mapped such that generally the texture
looks like it is scrolling in the right direction, but some areas have
the texture scrolling in completely the wrong direction.

 

Is there some maths algorithm I can use to possibly get around this?

 

I apologise if my question is not clear.

 

Cheers

Zafar Qamar

 


************************************************************************
**********
Disclaimer

The information and attached documentation in this e-mail is intended
for the use of the addressee only and is confidential. If you are not
the intended recipient please delete it and notify us immediately by
telephoning or e-mailing the sender. Please note that without
Codemasters' prior written consent any form of distribution, copying or
use of this communication or the information in it is strictly
prohibited and may be unlawful. 

Attachments to this e-mail may contain software viruses. You are advised
to take all reasonable precautions to minimise this risk and to carry
out a virus check on any documents before they are opened.

Any offer contained in this communication is subject to Codemasters'
standard terms & conditions and must be signed by both parties. Except
as expressly provided otherwise all information and attached
documentation in this e-mail is subject to contract and Codemasters'
board approval.
Any views or opinions expressed are solely those of the author and do
not necessarily represent those of Codemasters.

This footnote also confirms that this email message has been swept by
SurfControl for the presence of computer viruses.
************************************************************************
**********


------------------------------------------------------------------------
------
Come build with us! The BlackBerry&reg; Developer Conference in SF, CA
is the only developer event you need to attend this year. Jumpstart your
developing skills, take BlackBerry mobile applications to market and
stay
ahead of the curve. Join us from November 9&#45;12, 2009. Register
now&#33;
http://p.sf.net/sfu/devconf
_______________________________________________
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] Scroll direction algorithm

[Oscar F. <os...@tr...>]

well the problem comes from the fact a give triangle could be mapped to any
set of UVs.  to know what direction you are scrolling the texture you'd need
to know details about the triangle.
AFAIK, you could do it with a geometry shader, but without adding a load of
info to each certex you wouldn't be able to know the orientation.

2009/9/28 Zafar Qamar <zaf...@co...>

>  Hi,
>
>
>
> I have a question about an algorithm in a shader. I hope this is the right
> place to post.
>
>
>
> I basically have a mesh that has a texture on. In my shader I want the
> effect to generally look like it is moving across the mesh from left to
> right. Imagine it is a simple scrolling texture with some spots on, for the
> case of this question.
>
>
>
> However, the mesh has been UV mapped such that generally the texture looks
> like it is scrolling in the right direction, but some areas have the texture
> scrolling in completely the wrong direction.
>
>
>
> Is there some maths algorithm I can use to possibly get around this?
>
>
>
> I apologise if my question is not clear.
>
>
>
> Cheers
>
> Zafar Qamar
>
>
>
>
> **********************************************************************************
> Disclaimer
>
>
> The information and attached documentation in this e-mail is intended for the use of the addressee only and is confidential. If you are not the intended recipient please delete it and notify us immediately by telephoning or e-mailing the sender. Please note that without Codemasters’ prior written consent any form of distribution, copying or use of this communication or the information in it is strictly prohibited and may be unlawful.
>
>
> Attachments to this e-mail may contain software viruses. You are advised to take all reasonable precautions to minimise this risk and to carry out a virus check on any documents before they are opened.
>
>
> Any offer contained in this communication is subject to Codemasters’ standard terms & conditions and must be signed by both parties. Except as expressly provided otherwise all information and attached documentation in this e-mail is subject to contract and Codemasters’ board approval.
>
> Any views or opinions expressed are solely those of the author and do not necessarily represent those of Codemasters.
>
> This footnote also confirms that this email message has been swept by
> SurfControl for the presence of computer viruses.
>
> **********************************************************************************
>
>
> ------------------------------------------------------------------------------
> Come build with us! The BlackBerry&reg; Developer Conference in SF, CA
> is the only developer event you need to attend this year. Jumpstart your
> developing skills, take BlackBerry mobile applications to market and stay
> ahead of the curve. Join us from November 9&#45;12, 2009. Register now&#33;
> http://p.sf.net/sfu/devconf
> _______________________________________________
> 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] Scroll direction algorithm

[Sim D. <si...@gm...>]

If you have a tangent space basis for the mesh then this gives you the
information you need.  You can use this to convert from left/right in world,
view or model space, and convert into UV space.
You can look up tangent space lighting tutorials, then interpret the scroll
direction as a light direction.  Put the scroll direction vector in model
space, then through the per-vertex or per-pixel tangent space matrix ( which
will account for the texture direction flips ), then scale the resulting
vector based on the scroll speed and time, then add this to the initial
model UVs.

That should work...

On Mon, Sep 28, 2009 at 9:22 AM, Zafar Qamar <zaf...@co...>wrote:

>  Hi,
>
>
>
> I have a question about an algorithm in a shader. I hope this is the right
> place to post.
>
>
>
> I basically have a mesh that has a texture on. In my shader I want the
> effect to generally look like it is moving across the mesh from left to
> right. Imagine it is a simple scrolling texture with some spots on, for the
> case of this question.
>
>
>
> However, the mesh has been UV mapped such that generally the texture looks
> like it is scrolling in the right direction, but some areas have the texture
> scrolling in completely the wrong direction.
>
>
>
> Is there some maths algorithm I can use to possibly get around this?
>
>
>
> I apologise if my question is not clear.
>
>
>
> Cheers
>
> Zafar Qamar
>
>
>
>
> **********************************************************************************
> Disclaimer
>
>
> The information and attached documentation in this e-mail is intended for the use of the addressee only and is confidential. If you are not the intended recipient please delete it and notify us immediately by telephoning or e-mailing the sender. Please note that without Codemasters’ prior written consent any form of distribution, copying or use of this communication or the information in it is strictly prohibited and may be unlawful.
>
>
> Attachments to this e-mail may contain software viruses. You are advised to take all reasonable precautions to minimise this risk and to carry out a virus check on any documents before they are opened.
>
>
> Any offer contained in this communication is subject to Codemasters’ standard terms & conditions and must be signed by both parties. Except as expressly provided otherwise all information and attached documentation in this e-mail is subject to contract and Codemasters’ board approval.
>
> Any views or opinions expressed are solely those of the author and do not necessarily represent those of Codemasters.
>
> This footnote also confirms that this email message has been swept by
> SurfControl for the presence of computer viruses.
>
> **********************************************************************************
>
>
> ------------------------------------------------------------------------------
> Come build with us! The BlackBerry&reg; Developer Conference in SF, CA
> is the only developer event you need to attend this year. Jumpstart your
> developing skills, take BlackBerry mobile applications to market and stay
> ahead of the curve. Join us from November 9&#45;12, 2009. Register now&#33;
> http://p.sf.net/sfu/devconf
> _______________________________________________
> 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] Scroll direction algorithm

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

You can try to project the texture 'U axis' into view space, or world space,
and then you can know which direction you want the texture scrolling in.

Jeff


On Mon, Sep 28, 2009 at 11:22 AM, Zafar Qamar
<zaf...@co...>wrote:

>  Hi,
>
>
>
> I have a question about an algorithm in a shader. I hope this is the right
> place to post.
>
>
>
> I basically have a mesh that has a texture on. In my shader I want the
> effect to generally look like it is moving across the mesh from left to
> right. Imagine it is a simple scrolling texture with some spots on, for the
> case of this question.
>
>
>
> However, the mesh has been UV mapped such that generally the texture looks
> like it is scrolling in the right direction, but some areas have the texture
> scrolling in completely the wrong direction.
>
>
>
> Is there some maths algorithm I can use to possibly get around this?
>
>
>
> I apologise if my question is not clear.
>
>
>
> Cheers
>
> Zafar Qamar
>
>
>
>
> **********************************************************************************
> Disclaimer
>
>
> The information and attached documentation in this e-mail is intended for the use of the addressee only and is confidential. If you are not the intended recipient please delete it and notify us immediately by telephoning or e-mailing the sender. Please note that without Codemasters’ prior written consent any form of distribution, copying or use of this communication or the information in it is strictly prohibited and may be unlawful.
>
>
> Attachments to this e-mail may contain software viruses. You are advised to take all reasonable precautions to minimise this risk and to carry out a virus check on any documents before they are opened.
>
>
> Any offer contained in this communication is subject to Codemasters’ standard terms & conditions and must be signed by both parties. Except as expressly provided otherwise all information and attached documentation in this e-mail is subject to contract and Codemasters’ board approval.
>
> Any views or opinions expressed are solely those of the author and do not necessarily represent those of Codemasters.
>
> This footnote also confirms that this email message has been swept by
> SurfControl for the presence of computer viruses.
>
> **********************************************************************************
>
>
> ------------------------------------------------------------------------------
> Come build with us! The BlackBerry&reg; Developer Conference in SF, CA
> is the only developer event you need to attend this year. Jumpstart your
> developing skills, take BlackBerry mobile applications to market and stay
> ahead of the curve. Join us from November 9&#45;12, 2009. Register now&#33;
> http://p.sf.net/sfu/devconf
> _______________________________________________
> 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
>



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

[Algorithms] Scroll direction algorithm

[Zafar Q. <zaf...@co...>]

Hi,

I have a question about an algorithm in a shader. I hope this is the right place to post.

I basically have a mesh that has a texture on. In my shader I want the effect to generally look like it is moving across the mesh from left to right. Imagine it is a simple scrolling texture with some spots on, for the case of this question.

However, the mesh has been UV mapped such that generally the texture looks like it is scrolling in the right direction, but some areas have the texture scrolling in completely the wrong direction.

Is there some maths algorithm I can use to possibly get around this?

I apologise if my question is not clear.

Cheers
Zafar Qamar
**********************************************************************************
Disclaimer

The information and attached documentation in this e-mail is intended for the use of the addressee only and is confidential. If you are not the intended recipient please delete it and notify us immediately by telephoning or e-mailing the sender. Please note that without Codemasters’ prior written consent any form of distribution, copying or use of this communication or the information in it is strictly prohibited and may be unlawful. 

Attachments to this e-mail may contain software viruses. You are advised to take all reasonable precautions to minimise this risk and to carry out a virus check on any documents before they are opened.

Any offer contained in this communication is subject to Codemasters’ standard terms & conditions and must be signed by both parties. Except as expressly provided otherwise all information and attached documentation in this e-mail is subject to contract and Codemasters’ board approval.
Any views or opinions expressed are solely those of the author and do not necessarily represent those of Codemasters.

This footnote also confirms that this email message has been swept by
SurfControl for the presence of computer viruses.
**********************************************************************************

Re: [Algorithms] New research in SH rotations.

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

Just after sending that GDAlgorithms post, I also found that the
latest September 2009 edition of the ACM Journal of Computational
Physics has a "Short Note" on SH rotations. I don't have the logins to read
that yet unfortunately, but it cites the previous papers.

http://portal.acm.org/citation.cfm?id=1563054.1563203&coll=GUIDE&dl=GUIDE

- Robin Green.


2009/9/22 Grégory Jaegy <g....@fr...>:
> This is very interesting indeed, thanks for pointing it out !
>
> I wish I had some time to implement the paper and compare the
> performance/results to my existing implementation !
>
> Grégory Jaegy