gdalgorithms-list

Re: [Algorithms] Spherical harmonics for room acoustic modelling

[Veikko E. <vei...@ik...>]

From: Oscar Forth <os...@tr...>
> Spherical harmonics for room acoustic modelling
 > [...]

Not exactly directly related to the original question, but to feed the 
discussion and curious minds regarding sound waves also in games, I 
thought to share that Intel just recently published a paper on this.

Interactive Geometric Sound Propagation and Rendering
by Micah Taylor, Anish Chandak, Lakulish Antani, Dinesh Manocha
available at 
http://software.intel.com/en-us/articles/interactive-geometric-sound-propagation-and-rendering/

"
*Abstract*

We describe a novel algorithm and system for sound propagation and 
rendering in virtual environments and media applications. Our approach 
uses geometric propagation techniques for fast computation of 
propagation paths from a source to a listener and takes into account 
specular reflections, diffuse reflections, and edge diffraction. In 
order to perform fast path computation, we use a unified ray-based 
representation to efficiently trace discrete rays as well as volumetric 
ray-frusta. Furthermore, our propagation algorithm scales well with the 
number of cores, and uses interactive audio rendering technique to 
generate spatialized audio signals. The overall approach can render 
sound in dynamic scenes, allowing source, listener, and obstacle motion, 
and we show its performance on game-like and architectural environments. 
To the best of our knowledge, this is the first interactive sound 
rendering system that can perform plausible sound propagation and 
rendering in dynamic virtual environments.
"


Cheers,
Veikko Eeva

Re: [Algorithms] Spherical harmonics for room acoustic modelling

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

OK maybe not spherical harmonic based but gives the same sorta results and,
therefore, just as interesting :)

On 17 July 2010 22:13, Veikko Eeva <vei...@ik...> wrote:

>
> From: Oscar Forth <os...@tr...>
> > Spherical harmonics for room acoustic modelling
>  > [...]
>
> Not exactly directly related to the original question, but to feed the
> discussion and curious minds regarding sound waves also in games, I
> thought to share that Intel just recently published a paper on this.
>
> Interactive Geometric Sound Propagation and Rendering
> by Micah Taylor, Anish Chandak, Lakulish Antani, Dinesh Manocha
> available at
>
> http://software.intel.com/en-us/articles/interactive-geometric-sound-propagation-and-rendering/
>
> "
> *Abstract*
>
> We describe a novel algorithm and system for sound propagation and
> rendering in virtual environments and media applications. Our approach
> uses geometric propagation techniques for fast computation of
> propagation paths from a source to a listener and takes into account
> specular reflections, diffuse reflections, and edge diffraction. In
> order to perform fast path computation, we use a unified ray-based
> representation to efficiently trace discrete rays as well as volumetric
> ray-frusta. Furthermore, our propagation algorithm scales well with the
> number of cores, and uses interactive audio rendering technique to
> generate spatialized audio signals. The overall approach can render
> sound in dynamic scenes, allowing source, listener, and obstacle motion,
> and we show its performance on game-like and architectural environments.
> To the best of our knowledge, this is the first interactive sound
> rendering system that can perform plausible sound propagation and
> rendering in dynamic virtual environments.
> "
>
>
> Cheers,
> Veikko Eeva
>
>
>
> ------------------------------------------------------------------------------
> This SF.net email is sponsored by Sprint
> What will you do first with EVO, the first 4G phone?
> Visit sprint.com/first -- http://p.sf.net/sfu/sprint-com-first
> _______________________________________________
> 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] Spherical harmonics for room acoustic modelling

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

>  I'd have doubts you'd get good enough response time on CPU alone



Actually, the CPU can give you excellent response times if you're using a
convolution based solution. DJBFFT is a very high performance, unencumbered
convolution implementation, and it takes a minimal amount of CPU for a
single sound stream. The problem comes when you want to combine delay lines
to do overlap-add long convolution (or use the variable-window-size that's
allegedly still patented by Lake DSP). It starts adding up! The GPU might be
good at larger convolutions, but it has higher latency than the CPU.

I'm not sure Spherical Harmonics is the right solution. Sound reflection is
a function of frequency mapping to absorption and directional spread. And
whereas the eye is only sensitive to three separate frequencies, the ear is
sensitive to thousands... And in SH based PRT, you often collapse the
direction-dependent response into a single term, and filter the three
frequencies using a separate RGB "diffuse reflectance" texture. If you
applied the same to sound, you'd probably get a better than nothing, but you
might only get good enough that the problems start to become obvious :-)
(Bass, Mid and Treble, with a fixed reflectance function)

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.



On Sat, Jul 17, 2010 at 2:23 PM, Oscar Forth <
os...@tr...> wrote:

> OK maybe not spherical harmonic based but gives the same sorta results and,
> therefore, just as interesting :)
>
>

Re: [Algorithms] Spherical harmonics for room acoustic modelling

[Ken N. <ni...@gm...>]

Actually I implemented a basic beam tree that used the material properties
to estimate reverb in closed environments. The beam tree was too large for
detailed outdoor environments, but I suppose if you have a decent mesh
reduction algorithm you could scale it down, I just never had the time to
finish this work.

Cheers,
-Ken Noland

On Sun, Jul 18, 2010 at 11:03 AM, Jon Watte <jw...@gm...> wrote:

>
>  I'd have doubts you'd get good enough response time on CPU alone
>
>
>
> Actually, the CPU can give you excellent response times if you're using a
> convolution based solution. DJBFFT is a very high performance, unencumbered
> convolution implementation, and it takes a minimal amount of CPU for a
> single sound stream. The problem comes when you want to combine delay lines
> to do overlap-add long convolution (or use the variable-window-size that's
> allegedly still patented by Lake DSP). It starts adding up! The GPU might be
> good at larger convolutions, but it has higher latency than the CPU.
>
> I'm not sure Spherical Harmonics is the right solution. Sound reflection is
> a function of frequency mapping to absorption and directional spread. And
> whereas the eye is only sensitive to three separate frequencies, the ear is
> sensitive to thousands... And in SH based PRT, you often collapse the
> direction-dependent response into a single term, and filter the three
> frequencies using a separate RGB "diffuse reflectance" texture. If you
> applied the same to sound, you'd probably get a better than nothing, but you
> might only get good enough that the problems start to become obvious :-)
> (Bass, Mid and Treble, with a fixed reflectance function)
>
> 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.
>
>
>
> On Sat, Jul 17, 2010 at 2:23 PM, Oscar Forth <
> os...@tr...> wrote:
>
>> OK maybe not spherical harmonic based but gives the same sorta results
>> and, therefore, just as interesting :)
>>
>>
>
> ------------------------------------------------------------------------------
> This SF.net email is sponsored by Sprint
> What will you do first with EVO, the first 4G phone?
> Visit sprint.com/first -- http://p.sf.net/sfu/sprint-com-first
> _______________________________________________
> 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] Spherical harmonics for room acoustic modelling

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

Haven't read the whole thread, but here is a paper that will be presented at siggraph this year:
http://gamma.cs.unc.edu/PrecompWaveSim/
You would clearly need to scale back both memory usage and run-time to make this viable for games of course.
Peter-Pike

Date: Tue, 20 Jul 2010 17:13:06 +0100
From: ni...@gm...
To: gda...@li...
Subject: Re: [Algorithms] Spherical harmonics for room acoustic modelling

Actually I implemented a basic beam tree that used the material properties to estimate reverb in closed environments. The beam tree was too large for detailed outdoor environments, but I suppose if you have a decent mesh reduction algorithm you could scale it down, I just never had the time to finish this work.


Cheers,
-Ken Noland

On Sun, Jul 18, 2010 at 11:03 AM, Jon Watte <jw...@gm...> wrote:




 I'd have doubts you'd get good enough response time on CPU alone


Actually, the CPU can give you excellent response times if you're using a convolution based solution. DJBFFT is a very high performance, unencumbered convolution implementation, and it takes a minimal amount of CPU for a single sound stream. The problem comes when you want to combine delay lines to do overlap-add long convolution (or use the variable-window-size that's allegedly still patented by Lake DSP). It starts adding up! The GPU might be good at larger convolutions, but it has higher latency than the CPU.

I'm not sure Spherical Harmonics is the right solution. Sound reflection is a function of frequency mapping to absorption and directional spread. And whereas the eye is only sensitive to three separate frequencies, the ear is sensitive to thousands... And in SH based PRT, you often collapse the direction-dependent response into a single term, and filter the three frequencies using a separate RGB "diffuse reflectance" texture. If you applied the same to sound, you'd probably get a better than nothing, but you might only get good enough that the problems start to become obvious :-) (Bass, Mid and Treble, with a fixed reflectance function)


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. 






On Sat, Jul 17, 2010 at 2:23 PM, Oscar Forth <os...@tr...> wrote:


OK maybe not spherical harmonic based but gives the same sorta results and, therefore, just as interesting :)


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

This SF.net email is sponsored by Sprint

What will you do first with EVO, the first 4G phone?

Visit sprint.com/first -- http://p.sf.net/sfu/sprint-com-first
_______________________________________________


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] Spherical harmonics for room acoustic modelling

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

Somehow OT, I think what was missing in the video for the mentioned
siggraph paper (http://gamma.cs.unc.edu/PrecompWaveSim/), was some
sort of model for the human ear. I strongly suspect that for the
virtual recording they just placed two undirected virtual microphones
some 20cm apart, because with headphones it still sounded as though
every sound source was inside your head (Though the sense of space was
great). And I guess that's because in the virtual recording the
virtual external ear is missing, which is mainly responsible for
directional hearing in the real world. Just listen to these videos
(with earphones!) if you have no idea what I'm talking about (these
both model the external ear in some way, I'm not sure if they also
have real room acoustic modelling):

binaurial demonstration video:
http://www.youtube.com/watch?v=vfViBtIjK4c&feature=related <-- watch
out for the telephone ;)
virtual haircut: http://www.youtube.com/watch?v=8IXm6SuUigI&feature=related

Unfortunately there are very little details available publicly, and
those videos have been around for a long time, so I guess the research
around the subject somehow died.


BTW, I'm all for better, more sophisticated and computationally
expensive sound in games! Ego-shooters, horror games, how they could
benefit from the equivalent of the telephone above! ;)


Samuel


On Wed, Jul 21, 2010 at 8:39 PM, Peter-Pike Sloan
<pet...@ho...> wrote:
> Haven't read the whole thread, but here is a paper that will be presented at
> siggraph this year:
> http://gamma.cs.unc.edu/PrecompWaveSim/
> You would clearly need to scale back both memory usage and run-time to make
> this viable for games of course.
> Peter-Pike
>
> ________________________________
> Date: Tue, 20 Jul 2010 17:13:06 +0100
> From: ni...@gm...
> To: gda...@li...
> Subject: Re: [Algorithms] Spherical harmonics for room acoustic modelling
>
> Actually I implemented a basic beam tree that used the material properties
> to estimate reverb in closed environments. The beam tree was too large for
> detailed outdoor environments, but I suppose if you have a decent mesh
> reduction algorithm you could scale it down, I just never had the time to
> finish this work.
>
> Cheers,
> -Ken Noland
>
> On Sun, Jul 18, 2010 at 11:03 AM, Jon Watte <jw...@gm...> wrote:
>
>  I'd have doubts you'd get good enough response time on CPU alone
>
> Actually, the CPU can give you excellent response times if you're using a
> convolution based solution. DJBFFT is a very high performance, unencumbered
> convolution implementation, and it takes a minimal amount of CPU for a
> single sound stream. The problem comes when you want to combine delay lines
> to do overlap-add long convolution (or use the variable-window-size that's
> allegedly still patented by Lake DSP). It starts adding up! The GPU might be
> good at larger convolutions, but it has higher latency than the CPU.
> I'm not sure Spherical Harmonics is the right solution. Sound reflection is
> a function of frequency mapping to absorption and directional spread. And
> whereas the eye is only sensitive to three separate frequencies, the ear is
> sensitive to thousands... And in SH based PRT, you often collapse the
> direction-dependent response into a single term, and filter the three
> frequencies using a separate RGB "diffuse reflectance" texture. If you
> applied the same to sound, you'd probably get a better than nothing, but you
> might only get good enough that the problems start to become obvious :-)
> (Bass, Mid and Treble, with a fixed reflectance function)
> 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.
>
>
>
> On Sat, Jul 17, 2010 at 2:23 PM, Oscar Forth
> <os...@tr...> wrote:
>
> OK maybe not spherical harmonic based but gives the same sorta results and,
> therefore, just as interesting :)
>
> ------------------------------------------------------------------------------
> This SF.net email is sponsored by Sprint
> What will you do first with EVO, the first 4G phone?
> Visit sprint.com/first -- http://p.sf.net/sfu/sprint-com-first
> _______________________________________________
> 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 SF.net email is sponsored by Sprint
> What will you do first with EVO, the first 4G phone?
> Visit sprint.com/first -- http://p.sf.net/sfu/sprint-com-first
> _______________________________________________
> 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] Spherical harmonics for room acoustic modelling

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

>
> I guess the research around the subject somehow died.


I remember binaural demonstrations in the early '80s. I also remember being
able to buy special heads with a modeled ear and cavities to insert
microphones of your choice. Bright orange, in best 70's fashion, if memory
serves :-)
To find the research that led to those products, I think you have to dig up
(gasp!) offline sources, like the Journal of the AES from 30-50 years ago.

Obligatory old-man rant:
Remember what it was like back when research required spending months
traveling to libraries, ordering back issues of journals, and tracking down
too-vague references through legwork?
I fear those skills are being lost now, because it's easier to believe that
something doesn't exist if you can't find it on Google or Citeseer ;-)
And I'm not even that old!

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.



On Sun, Jul 25, 2010 at 5:12 AM, Samuel Moll <sam...@go...>wrote:

> Somehow OT, I think what was missing in the video for the mentioned
> siggraph paper (http://gamma.cs.unc.edu/PrecompWaveSim/), was some
> sort of model for the human ear. I strongly suspect that for the
> virtual recording they just placed two undirected virtual microphones
> some 20cm apart, because with headphones it still sounded as though
> every sound source was inside your head (Though the sense of space was
> great). And I guess that's because in the virtual recording the
> virtual external ear is missing, which is mainly responsible for
> directional hearing in the real world. Just listen to these videos
> (with earphones!) if you have no idea what I'm talking about (these
> both model the external ear in some way, I'm not sure if they also
> have real room acoustic modelling):
>
> binaurial demonstration video:
> http://www.youtube.com/watch?v=vfViBtIjK4c&feature=related <-- watch
> out for the telephone ;)
> virtual haircut:
> http://www.youtube.com/watch?v=8IXm6SuUigI&feature=related
>
> Unfortunately there are very little details available publicly, and
> those videos have been around for a long time, so I guess the research
> around the subject somehow died.
>
>
> BTW, I'm all for better, more sophisticated and computationally
> expensive sound in games! Ego-shooters, horror games, how they could
> benefit from the equivalent of the telephone above! ;)
>
>
> Samuel
>
>
> On Wed, Jul 21, 2010 at 8:39 PM, Peter-Pike Sloan
> <pet...@ho...> wrote:
> > Haven't read the whole thread, but here is a paper that will be presented
> at
> > siggraph this year:
> > http://gamma.cs.unc.edu/PrecompWaveSim/
> > You would clearly need to scale back both memory usage and run-time to
> make
> > this viable for games of course.
> > Peter-Pike
> >
> > ________________________________
> > Date: Tue, 20 Jul 2010 17:13:06 +0100
> > From: ni...@gm...
> > To: gda...@li...
> > Subject: Re: [Algorithms] Spherical harmonics for room acoustic modelling
> >
> > Actually I implemented a basic beam tree that used the material
> properties
> > to estimate reverb in closed environments. The beam tree was too large
> for
> > detailed outdoor environments, but I suppose if you have a decent mesh
> > reduction algorithm you could scale it down, I just never had the time to
> > finish this work.
> >
> > Cheers,
> > -Ken Noland
> >
> > On Sun, Jul 18, 2010 at 11:03 AM, Jon Watte <jw...@gm...> wrote:
> >
> >  I'd have doubts you'd get good enough response time on CPU alone
> >
> > Actually, the CPU can give you excellent response times if you're using a
> > convolution based solution. DJBFFT is a very high performance,
> unencumbered
> > convolution implementation, and it takes a minimal amount of CPU for a
> > single sound stream. The problem comes when you want to combine delay
> lines
> > to do overlap-add long convolution (or use the variable-window-size
> that's
> > allegedly still patented by Lake DSP). It starts adding up! The GPU might
> be
> > good at larger convolutions, but it has higher latency than the CPU.
> > I'm not sure Spherical Harmonics is the right solution. Sound reflection
> is
> > a function of frequency mapping to absorption and directional spread. And
> > whereas the eye is only sensitive to three separate frequencies, the ear
> is
> > sensitive to thousands... And in SH based PRT, you often collapse the
> > direction-dependent response into a single term, and filter the three
> > frequencies using a separate RGB "diffuse reflectance" texture. If you
> > applied the same to sound, you'd probably get a better than nothing, but
> you
> > might only get good enough that the problems start to become obvious :-)
> > (Bass, Mid and Treble, with a fixed reflectance function)
> > 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.
> >
> >
> >
> > On Sat, Jul 17, 2010 at 2:23 PM, Oscar Forth
> > <os...@tr...> wrote:
> >
> > OK maybe not spherical harmonic based but gives the same sorta results
> and,
> > therefore, just as interesting :)
> >
> >
> ------------------------------------------------------------------------------
> > This SF.net email is sponsored by Sprint
> > What will you do first with EVO, the first 4G phone?
> > Visit sprint.com/first -- http://p.sf.net/sfu/sprint-com-first
> > _______________________________________________
> > 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 SF.net email is sponsored by Sprint
> > What will you do first with EVO, the first 4G phone?
> > Visit sprint.com/first -- http://p.sf.net/sfu/sprint-com-first
> > _______________________________________________
> > 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 SF.net email is sponsored by Sprint
> What will you do first with EVO, the first 4G phone?
> Visit sprint.com/first -- http://p.sf.net/sfu/sprint-com-first
> _______________________________________________
> 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] Spherical harmonics for room acoustic modelling

[Andy F. <pad...@ob...>]

On Sun, 25 Jul 2010 13:01:38 -0700
Jon Watte <jw...@gm...> wrote:

> Remember what it was like back when research required spending months
> traveling to libraries, ordering back issues of journals, and tracking down
> too-vague references through legwork?

Actually those were the good old days. The library
would eventually get them for you. There are too many walled 
gardens now. Research is under seige in new ways that 
reveal the electronic information revolution to be a mixed 
blessing.

Anyway a good side is it re-humanises discourse. 
I email authors, ask for a copy of their paper (which any 
true scientist is always eager to supply), discuss the 
approaches and compare ideas, swap PDF's of other papers.
That's how real research gets done these days, even if
nobody admits it. 


-- 
Andy Farnell <pad...@ob...>

Re: [Algorithms] Spherical harmonics for room acoustic modelling

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

May I introduce you to the "Audio Anecdotes" series of books, designed to
mirror Graphics Gems for audio. They make a special point of producing
digests of exactly these papers with the aim if getting people up to speed
without all the mess and fuss.

http://www.audioanecdotes.com/

- Robin Green.

On Jul 25, 2010 1:05 PM, "Jon Watte" <jw...@gm...> wrote:

> I guess the research around the subject somehow died.

I remember binaural demonstrations in the early '80s. I also remember being
able to buy special heads with a modeled ear and cavities to insert
microphones of your choice. Bright orange, in best 70's fashion, if memory
serves :-)
To find the research that led to those products, I think you have to dig up
(gasp!) offline sources, like the Journal of the AES from 30-50 years ago.

Obligatory old-man rant:
Remember what it was like back when research required spending months
traveling to libraries, ordering back issues of journals, and tracking down
too-vague references through legwork?
I fear those skills are being lost now, because it's easier to believe that
something doesn't exist if you can't find it on Google or Citeseer ;-)
And I'm not even that old!

Sincerely,

jw


--
Americans might object: there is no way we would sacrifice our living
standards for the benefit ...

On Sun, Jul 25, 2010 at 5:12 AM, Samuel Moll <sam...@go...>
wrote:
>
> Somehow OT, I thin...

------------------------------------------------------------------------------
This SF.net email is sponsored by Sprint
What will you do first with EVO, the first 4G phone?
Visit sprint.com/first -- http://p.sf.net/sfu/sprint-com-first
_______________________________________________
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] Spherical harmonics for room acoustic modelling

[Andy F. <pad...@ob...>]

Nice to see an interest in audio on this list guys.

I lurk here enjoying much of the conversiation
from what I assume are mainly graphics and AI people.


On Sun, 25 Jul 2010 13:01:38 -0700
Jon Watte <jw...@gm...> wrote:

> >
> > I guess the research around the subject somehow died.
> 
> 
> I remember binaural demonstrations in the early '80s. I also remember being
> able to buy special heads with a modeled ear and cavities to insert
> microphones of your choice. Bright orange, in best 70's fashion, if memory
> serves :-)

Dummy heads are still used. Head transfer response and binaural research
is still a very important area, and enjoying a revival because
of mobile gaming.

[Algorithms] Sphere to Triangle overlap check

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

Hi,
This is a very old question but I can't seem to find a good answer for it and I've searched the net for quite a while.

I need a precise way of checking if a sphere and a given triangle have _any_ overlap.
Specifically, the case I'm struggling with is when the sphere just overlaps one of the edges.
Also, I need to cater for when the sphere is completely inside the triangle, and vice-versa

Help please? Or a decent internet link would be much appreciated

Cheers
Zaf

**********************************************************************************
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] Sphere to Triangle overlap check

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

Generally, you first compute whether the triangle plane culls the sphere.

If not, then you can calculate point-to-triangle distance between the
projection of the sphere center to the triangle plane and the triangle
(edges). One way of doing this is to calculate the projection of the center
of the sphere as a barycentric combination of two of the triangle base
edges.

There are two good references for collision information:

1) Christer Ericson's book "Real-time Collision Detection"
2) Wild Magic, Dave Eberly's game library also used as a basis for his books

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.



On Wed, Jul 28, 2010 at 4:34 AM, Zafar Qamar <zaf...@co...>wrote:

> Hi,
> This is a very old question but I can't seem to find a good answer for it
> and I've searched the net for quite a while.
>
> I need a precise way of checking if a sphere and a given triangle have
> _any_ overlap.
> Specifically, the case I'm struggling with is when the sphere just overlaps
> one of the edges.
> Also, I need to cater for when the sphere is completely inside the
> triangle, and vice-versa
>
> Help please? Or a decent internet link would be much appreciated
>
> Cheers
> Zaf
>
>
> **********************************************************************************
> 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.
>
> **********************************************************************************
>
>
>
> ------------------------------------------------------------------------------
> The Palm PDK Hot Apps Program offers developers who use the
> Plug-In Development Kit to bring their C/C++ apps to Palm for a share
> of $1 Million in cash or HP Products. Visit us here for more details:
> http://ad.doubleclick.net/clk;226879339;13503038;l?
> http://clk.atdmt.com/CRS/go/247765532/direct/01/
> _______________________________________________
> 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] Sphere to Triangle overlap check

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

http://realtimerendering.com/intersections.html is a good place to look, it
has a number of references and links. I *know* I've found the ERIT paper
online in the past, but can't find the link right now. Like Jon says, the
Ericson book has the answer - my page gives the page numbers. It also gives
the link to the Wild Magic code page.

Eric

On Wed, Jul 28, 2010 at 7:34 AM, Zafar Qamar <zaf...@co...>wrote:

> Hi,
> This is a very old question but I can't seem to find a good answer for it
> and I've searched the net for quite a while.
>
> I need a precise way of checking if a sphere and a given triangle have
> _any_ overlap.
> Specifically, the case I'm struggling with is when the sphere just overlaps
> one of the edges.
> Also, I need to cater for when the sphere is completely inside the
> triangle, and vice-versa
>
> Help please? Or a decent internet link would be much appreciated
>
> Cheers
> Zaf
>
>
> **********************************************************************************
> 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.
>
> **********************************************************************************
>
>
>
> ------------------------------------------------------------------------------
> The Palm PDK Hot Apps Program offers developers who use the
> Plug-In Development Kit to bring their C/C++ apps to Palm for a share
> of $1 Million in cash or HP Products. Visit us here for more details:
> http://ad.doubleclick.net/clk;226879339;13503038;l?
> http://clk.atdmt.com/CRS/go/247765532/direct/01/
> _______________________________________________
> 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] Sphere to Triangle overlap check

[Mark W. <wa...@in...>]

Zaf,

First find the distance of the sphere center from the plane. If the abs distance is greater than the radius then  there is no overlap.
You then need to find the radius of the circle of intersection with the plane which is much easier than you think. The radius of intersection is simply sqrt(sphereRadiusSqr + centerDistFromPlane). Then find the distance from the sphere center projected onto the plane to each edge. If the distance is less than the radius of intersection then there's an overlap.
To find the distance to the edge, calc edgeNormal via normalize(cross(faceNormal, edge)) then calc (projectedCenter - edgeStartVertex) dot edgeNormal.
This was all from memory and a quick scribble so hopefully it's correct :-)

Cheers,
Mark


On 28/07/2010, at 9:34 PM, Zafar Qamar <zaf...@co...> wrote:

> Hi,
> This is a very old question but I can't seem to find a good answer for it and I've searched the net for quite a while.
> 
> I need a precise way of checking if a sphere and a given triangle have _any_ overlap.
> Specifically, the case I'm struggling with is when the sphere just overlaps one of the edges.
> Also, I need to cater for when the sphere is completely inside the triangle, and vice-versa
> 
> Help please? Or a decent internet link would be much appreciated
> 
> Cheers
> Zaf
> 
> **********************************************************************************
> 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.
> **********************************************************************************
> 
> 
> ------------------------------------------------------------------------------
> The Palm PDK Hot Apps Program offers developers who use the
> Plug-In Development Kit to bring their C/C++ apps to Palm for a share 
> of $1 Million in cash or HP Products. Visit us here for more details:
> http://ad.doubleclick.net/clk;226879339;13503038;l?
> http://clk.atdmt.com/CRS/go/247765532/direct/01/
> _______________________________________________
> 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] Sphere to Triangle overlap check

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

Thanks so much for all of the replies. Looks like some great stuff there.

Much appreciated
Zaf

-----Original Message-----
From: Mark Wayland [mailto:wa...@in...] 
Sent: 28 July 2010 15:42
To: Game Development Algorithms
Subject: Re: [Algorithms] Sphere to Triangle overlap check

Zaf,

First find the distance of the sphere center from the plane. If the abs distance is greater than the radius then  there is no overlap.
You then need to find the radius of the circle of intersection with the plane which is much easier than you think. The radius of intersection is simply sqrt(sphereRadiusSqr + centerDistFromPlane). Then find the distance from the sphere center projected onto the plane to each edge. If the distance is less than the radius of intersection then there's an overlap.
To find the distance to the edge, calc edgeNormal via normalize(cross(faceNormal, edge)) then calc (projectedCenter - edgeStartVertex) dot edgeNormal.
This was all from memory and a quick scribble so hopefully it's correct :-)

Cheers,
Mark


On 28/07/2010, at 9:34 PM, Zafar Qamar <zaf...@co...> wrote:

> Hi,
> This is a very old question but I can't seem to find a good answer for it and I've searched the net for quite a while.
> 
> I need a precise way of checking if a sphere and a given triangle have _any_ overlap.
> Specifically, the case I'm struggling with is when the sphere just overlaps one of the edges.
> Also, I need to cater for when the sphere is completely inside the triangle, and vice-versa
> 
> Help please? Or a decent internet link would be much appreciated
> 
> Cheers
> Zaf
> 
> **********************************************************************************
> 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.
> **********************************************************************************
> 
> 
> ------------------------------------------------------------------------------
> The Palm PDK Hot Apps Program offers developers who use the
> Plug-In Development Kit to bring their C/C++ apps to Palm for a share 
> of $1 Million in cash or HP Products. Visit us here for more details:
> http://ad.doubleclick.net/clk;226879339;13503038;l?
> http://clk.atdmt.com/CRS/go/247765532/direct/01/
> _______________________________________________
> 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

------------------------------------------------------------------------------
The Palm PDK Hot Apps Program offers developers who use the
Plug-In Development Kit to bring their C/C++ apps to Palm for a share
of $1 Million in cash or HP Products. Visit us here for more details:
http://p.sf.net/sfu/dev2dev-palm
_______________________________________________
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
**********************************************************************************
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] Sphere to Triangle overlap check

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

If memory serves, you don't need to do all those square roots and normalizes
if you use the barycentric coordinate method.
Also, the radius of the projected circle is sqrt(sphereRadius -
abs(distanceToPlane)) -- you have a sign error in the case the sphere is
above the plane (and the distance is positive).

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.



On Wed, Jul 28, 2010 at 7:41 AM, Mark Wayland <wa...@in...>wrote:

> Zaf,
>
> First find the distance of the sphere center from the plane. If the abs
> distance is greater than the radius then  there is no overlap.
> You then need to find the radius of the circle of intersection with the
> plane which is much easier than you think. The radius of intersection is
> simply sqrt(sphereRadiusSqr + centerDistFromPlane). Then find the distance
> from the sphere center projected onto the plane to each edge. If the
> distance is less than the radius of intersection then there's an overlap.
> To find the distance to the edge, calc edgeNormal via
> normalize(cross(faceNormal, edge)) then calc (projectedCenter -
> edgeStartVertex) dot edgeNormal.
> This was all from memory and a quick scribble so hopefully it's correct :-)
>
> Cheers,
> Mark
>
>
> On 28/07/2010, at 9:34 PM, Zafar Qamar <zaf...@co...>
> wrote:
>
> > Hi,
> > This is a very old question but I can't seem to find a good answer for it
> and I've searched the net for quite a while.
> >
> > I need a precise way of checking if a sphere and a given triangle have
> _any_ overlap.
> > Specifically, the case I'm struggling with is when the sphere just
> overlaps one of the edges.
> > Also, I need to cater for when the sphere is completely inside the
> triangle, and vice-versa
> >
> > Help please? Or a decent internet link would be much appreciated
> >
> > Cheers
> > Zaf
> >
> >
> **********************************************************************************
> > 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.
> >
> **********************************************************************************
> >
> >
> >
> ------------------------------------------------------------------------------
> > The Palm PDK Hot Apps Program offers developers who use the
> > Plug-In Development Kit to bring their C/C++ apps to Palm for a share
> > of $1 Million in cash or HP Products. Visit us here for more details:
> > http://ad.doubleclick.net/clk;226879339;13503038;l?
> > http://clk.atdmt.com/CRS/go/247765532/direct/01/
> > _______________________________________________
> > 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
>
>
> ------------------------------------------------------------------------------
> The Palm PDK Hot Apps Program offers developers who use the
> Plug-In Development Kit to bring their C/C++ apps to Palm for a share
> of $1 Million in cash or HP Products. Visit us here for more details:
> http://p.sf.net/sfu/dev2dev-palm
> _______________________________________________
> 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] Sphere to Triangle overlap check

[Mark W. <wa...@in...>]

I'm pretty sure the sign of the dist doesn't matter because I meant to write sqrt(sphereRadiusSqr + centerDistFromPlaneSqr), using simple Pythagorus. I'm also sure that there's probably better ways too :-)

Cheers,
Mark

On 29/07/2010, at 6:20 PM, Jon Watte <jw...@gm...> wrote:

> If memory serves, you don't need to do all those square roots and normalizes if you use the barycentric coordinate method.
> Also, the radius of the projected circle is sqrt(sphereRadius - abs(distanceToPlane)) -- you have a sign error in the case the sphere is above the plane (and the distance is positive).
> 
> 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. 
> 
> 
> 
> On Wed, Jul 28, 2010 at 7:41 AM, Mark Wayland <wa...@in...> wrote:
> Zaf,
> 
> First find the distance of the sphere center from the plane. If the abs distance is greater than the radius then  there is no overlap.
> You then need to find the radius of the circle of intersection with the plane which is much easier than you think. The radius of intersection is simply sqrt(sphereRadiusSqr + centerDistFromPlane). Then find the distance from the sphere center projected onto the plane to each edge. If the distance is less than the radius of intersection then there's an overlap.
> To find the distance to the edge, calc edgeNormal via normalize(cross(faceNormal, edge)) then calc (projectedCenter - edgeStartVertex) dot edgeNormal.
> This was all from memory and a quick scribble so hopefully it's correct :-)
> 
> Cheers,
> Mark
> 
> 
> On 28/07/2010, at 9:34 PM, Zafar Qamar <zaf...@co...> wrote:
> 
> > Hi,
> > This is a very old question but I can't seem to find a good answer for it and I've searched the net for quite a while.
> >
> > I need a precise way of checking if a sphere and a given triangle have _any_ overlap.
> > Specifically, the case I'm struggling with is when the sphere just overlaps one of the edges.
> > Also, I need to cater for when the sphere is completely inside the triangle, and vice-versa
> >
> > Help please? Or a decent internet link would be much appreciated
> >
> > Cheers
> > Zaf
> >
> > **********************************************************************************
> > 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.
> > **********************************************************************************
> >
> >
> > ------------------------------------------------------------------------------
> > The Palm PDK Hot Apps Program offers developers who use the
> > Plug-In Development Kit to bring their C/C++ apps to Palm for a share
> > of $1 Million in cash or HP Products. Visit us here for more details:
> > http://ad.doubleclick.net/clk;226879339;13503038;l?
> > http://clk.atdmt.com/CRS/go/247765532/direct/01/
> > _______________________________________________
> > 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
> 
> ------------------------------------------------------------------------------
> The Palm PDK Hot Apps Program offers developers who use the
> Plug-In Development Kit to bring their C/C++ apps to Palm for a share
> of $1 Million in cash or HP Products. Visit us here for more details:
> http://p.sf.net/sfu/dev2dev-palm
> _______________________________________________
> 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
> 
> ------------------------------------------------------------------------------
> The Palm PDK Hot Apps Program offers developers who use the
> Plug-In Development Kit to bring their C/C++ apps to Palm for a share
> of $1 Million in cash or HP Products. Visit us here for more details:
> http://p.sf.net/sfu/dev2dev-palm
> _______________________________________________
> 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] Sphere to Triangle overlap check

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

That's still not right -- you need to subtract the square of the shorter
edge!
Assuming D is the distance from plane to sphere:
R*R = D*D + X*X
X = sqrt(R*R - D*D)

(And, yes, I was not paying attention -- I already thought you were squaring
the values)

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.



On Thu, Jul 29, 2010 at 4:23 AM, Mark Wayland <wa...@in...>wrote:

> I'm pretty sure the sign of the dist doesn't matter because I meant to write
> sqrt(sphereRadiusSqr + centerDistFromPlaneSqr), using simple Pythagorus. I'm
> also sure that there's probably better ways too :-)
>
> Cheers,
> Mark
>
> On 29/07/2010, at 6:20 PM, Jon Watte <jw...@gm...> wrote:
>
> If memory serves, you don't need to do all those square roots and
> normalizes if you use the barycentric coordinate method.
> Also, the radius of the projected circle is sqrt(sphereRadius -
> abs(distanceToPlane)) -- you have a sign error in the case the sphere is
> above the plane (and the distance is positive).
>
> 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.
>
>
>
> On Wed, Jul 28, 2010 at 7:41 AM, Mark Wayland < <wa...@in...>
> wa...@in...> wrote:
>
>> Zaf,
>>
>> First find the distance of the sphere center from the plane. If the abs
>> distance is greater than the radius then  there is no overlap.
>> You then need to find the radius of the circle of intersection with the
>> plane which is much easier than you think. The radius of intersection is
>> simply sqrt(sphereRadiusSqr + centerDistFromPlane). Then find the distance
>> from the sphere center projected onto the plane to each edge. If the
>> distance is less than the radius of intersection then there's an overlap.
>> To find the distance to the edge, calc edgeNormal via
>> normalize(cross(faceNormal, edge)) then calc (projectedCenter -
>> edgeStartVertex) dot edgeNormal.
>> This was all from memory and a quick scribble so hopefully it's correct
>> :-)
>>
>> Cheers,
>> Mark
>>
>>
>> On 28/07/2010, at 9:34 PM, Zafar Qamar < <zaf...@co...>
>> zaf...@co...> wrote:
>>
>> > Hi,
>> > This is a very old question but I can't seem to find a good answer for
>> it and I've searched the net for quite a while.
>> >
>> > I need a precise way of checking if a sphere and a given triangle have
>> _any_ overlap.
>> > Specifically, the case I'm struggling with is when the sphere just
>> overlaps one of the edges.
>> > Also, I need to cater for when the sphere is completely inside the
>> triangle, and vice-versa
>> >
>> > Help please? Or a decent internet link would be much appreciated
>> >
>> > Cheers
>> > Zaf
>> >
>> >
>> **********************************************************************************
>> > 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.
>> >
>> **********************************************************************************
>> >
>> >
>> >
>> ------------------------------------------------------------------------------
>> > The Palm PDK Hot Apps Program offers developers who use the
>> > Plug-In Development Kit to bring their C/C++ apps to Palm for a share
>> > of $1 Million in cash or HP Products. Visit us here for more details:
>> > <http://ad.doubleclick.net/clk;226879339;13503038;l>
>> http://ad.doubleclick.net/clk;226879339;13503038;l?
>> > <http://clk.atdmt.com/CRS/go/247765532/direct/01/>
>> http://clk.atdmt.com/CRS/go/247765532/direct/01/
>> > _______________________________________________
>> > GDAlgorithms-list mailing list
>> > <GDA...@li...>
>> GDA...@li...
>> > <https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list>
>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> > Archives:
>> >
>> <http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list>
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>
>>
>> ------------------------------------------------------------------------------
>> The Palm PDK Hot Apps Program offers developers who use the
>> Plug-In Development Kit to bring their C/C++ apps to Palm for a share
>> of $1 Million in cash or HP Products. Visit us here for more details:
>>  <http://p.sf.net/sfu/dev2dev-palm>http://p.sf.net/sfu/dev2dev-palm
>> _______________________________________________
>> GDAlgorithms-list mailing list
>>  <GDA...@li...>
>> GDA...@li...
>>  <https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list>
>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> Archives:
>> <http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list>
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>
>
>
> ------------------------------------------------------------------------------
> The Palm PDK Hot Apps Program offers developers who use the
> Plug-In Development Kit to bring their C/C++ apps to Palm for a share
> of $1 Million in cash or HP Products. Visit us here for more details:
> http://p.sf.net/sfu/dev2dev-palm
>
> _______________________________________________
> 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
>
>
>
> ------------------------------------------------------------------------------
> The Palm PDK Hot Apps Program offers developers who use the
> Plug-In Development Kit to bring their C/C++ apps to Palm for a share
> of $1 Million in cash or HP Products. Visit us here for more details:
> http://p.sf.net/sfu/dev2dev-palm
> _______________________________________________
> 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] Sphere to Triangle overlap check

[Mark W. <wa...@in...>]

Yes, but if the sphere is intersecting the plane then the plane fist is guaranteed to be smaller in magnitude than the radius, is it not?

Cheers,
Mark



On 29/07/2010, at 10:00 PM, Jon Watte <jw...@gm...> wrote:

> 
> That's still not right -- you need to subtract the square of the shorter edge!
> Assuming D is the distance from plane to sphere:
> R*R = D*D + X*X
> X = sqrt(R*R - D*D)
> 
> (And, yes, I was not paying attention -- I already thought you were squaring the values)
> 
> 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. 
> 
> 
> 
> On Thu, Jul 29, 2010 at 4:23 AM, Mark Wayland <wa...@in...> wrote:
> I'm pretty sure the sign of the dist doesn't matter because I meant to write sqrt(sphereRadiusSqr + centerDistFromPlaneSqr), using simple Pythagorus. I'm also sure that there's probably better ways too :-)
> 
> Cheers,
> Mark
> 
> On 29/07/2010, at 6:20 PM, Jon Watte <jw...@gm...> wrote:
> 
>> If memory serves, you don't need to do all those square roots and normalizes if you use the barycentric coordinate method.
>> Also, the radius of the projected circle is sqrt(sphereRadius - abs(distanceToPlane)) -- you have a sign error in the case the sphere is above the plane (and the distance is positive).
>> 
>> 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. 
>> 
>> 
>> 
>> On Wed, Jul 28, 2010 at 7:41 AM, Mark Wayland <wa...@in...> wrote:
>> Zaf,
>> 
>> First find the distance of the sphere center from the plane. If the abs distance is greater than the radius then  there is no overlap.
>> You then need to find the radius of the circle of intersection with the plane which is much easier than you think. The radius of intersection is simply sqrt(sphereRadiusSqr + centerDistFromPlane). Then find the distance from the sphere center projected onto the plane to each edge. If the distance is less than the radius of intersection then there's an overlap.
>> To find the distance to the edge, calc edgeNormal via normalize(cross(faceNormal, edge)) then calc (projectedCenter - edgeStartVertex) dot edgeNormal.
>> This was all from memory and a quick scribble so hopefully it's correct :-)
>> 
>> Cheers,
>> Mark
>> 
>> 
>> On 28/07/2010, at 9:34 PM, Zafar Qamar <zaf...@co...> wrote:
>> 
>> > Hi,
>> > This is a very old question but I can't seem to find a good answer for it and I've searched the net for quite a while.
>> >
>> > I need a precise way of checking if a sphere and a given triangle have _any_ overlap.
>> > Specifically, the case I'm struggling with is when the sphere just overlaps one of the edges.
>> > Also, I need to cater for when the sphere is completely inside the triangle, and vice-versa
>> >
>> > Help please? Or a decent internet link would be much appreciated
>> >
>> > Cheers
>> > Zaf
>> >
>> > **********************************************************************************
>> > 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.
>> > **********************************************************************************
>> >
>> >
>> > ------------------------------------------------------------------------------
>> > The Palm PDK Hot Apps Program offers developers who use the
>> > Plug-In Development Kit to bring their C/C++ apps to Palm for a share
>> > of $1 Million in cash or HP Products. Visit us here for more details:
>> > http://ad.doubleclick.net/clk;226879339;13503038;l?
>> > http://clk.atdmt.com/CRS/go/247765532/direct/01/
>> > _______________________________________________
>> > 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
>> 
>> ------------------------------------------------------------------------------
>> The Palm PDK Hot Apps Program offers developers who use the
>> Plug-In Development Kit to bring their C/C++ apps to Palm for a share
>> of $1 Million in cash or HP Products. Visit us here for more details:
>> http://p.sf.net/sfu/dev2dev-palm
>> _______________________________________________
>> 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
>> 
>> ------------------------------------------------------------------------------
>> The Palm PDK Hot Apps Program offers developers who use the
>> Plug-In Development Kit to bring their C/C++ apps to Palm for a share
>> of $1 Million in cash or HP Products. Visit us here for more details:
>> http://p.sf.net/sfu/dev2dev-palm
>> _______________________________________________
>> 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
> 
> ------------------------------------------------------------------------------
> The Palm PDK Hot Apps Program offers developers who use the
> Plug-In Development Kit to bring their C/C++ apps to Palm for a share
> of $1 Million in cash or HP Products. Visit us here for more details:
> http://p.sf.net/sfu/dev2dev-palm
> _______________________________________________
> 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
> 
> ------------------------------------------------------------------------------
> The Palm PDK Hot Apps Program offers developers who use the
> Plug-In Development Kit to bring their C/C++ apps to Palm for a share
> of $1 Million in cash or HP Products. Visit us here for more details:
> http://p.sf.net/sfu/dev2dev-palm
> _______________________________________________
> 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] Sphere to Triangle overlap check

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

I don't see where I claim otherwise?
You still need to subtract the edge from the hypotenuse, not add.

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.



On Thu, Jul 29, 2010 at 2:57 PM, Mark Wayland <wa...@in...>wrote:

> Yes, but if the sphere is intersecting the plane then the plane fist is
> guaranteed to be smaller in magnitude than the radius, is it not?
>
> Cheers,
> Mark
>
>
>
> On 29/07/2010, at 10:00 PM, Jon Watte <jw...@gm...> wrote:
>
>
> That's still not right -- you need to subtract the square of the shorter
> edge!
> Assuming D is the distance from plane to sphere:
> R*R = D*D + X*X
> X = sqrt(R*R - D*D)
>
> (And, yes, I was not paying attention -- I already thought you were
> squaring the values)
>
> 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] Sphere to Triangle overlap check

[Mark W. <wa...@in...>]

Yes, you are indeed correct - my mistake. I'm thinking subtraction and writing addition. That's what I get for posting on my phone after midnight ;-) Thanks for setting me straight!

Cheers,
Mark


On 31/07/2010, at 12:13 AM, Jon Watte <jw...@gm...> wrote:

> I don't see where I claim otherwise?
> You still need to subtract the edge from the hypotenuse, not add.
> 
> 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. 
> 
> 
> 
> On Thu, Jul 29, 2010 at 2:57 PM, Mark Wayland <wa...@in...> wrote:
> Yes, but if the sphere is intersecting the plane then the plane fist is guaranteed to be smaller in magnitude than the radius, is it not?
> 
> Cheers,
> Mark
> 
> 
> 
> On 29/07/2010, at 10:00 PM, Jon Watte <jw...@gm...> wrote:
> 
>> 
>> That's still not right -- you need to subtract the square of the shorter edge!
>> Assuming D is the distance from plane to sphere:
>> R*R = D*D + X*X
>> X = sqrt(R*R - D*D)
>> 
>> (And, yes, I was not paying attention -- I already thought you were squaring the values)
>> 
>> 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. 
>> 
> 
> 
> ------------------------------------------------------------------------------
> The Palm PDK Hot Apps Program offers developers who use the
> Plug-In Development Kit to bring their C/C++ apps to Palm for a share
> of $1 Million in cash or HP Products. Visit us here for more details:
> http://p.sf.net/sfu/dev2dev-palm
> _______________________________________________
> 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] String simulation

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

Turns out searching for "string simulation" turns up a lot of things *not* about simulating little pieces of yarn and twine.  Does anyone have pointers to papers/techniques for simulating string/rope/twine?  

On the plus side I've read a couple interesting papers on String Theory!

Thanks...

   Ron

Re: [Algorithms] String simulation

[Gino v. d. B. <gin...@gm...>]

  There's an article "Ropes as Constraints" by Anton Knyazyev in Game 
Physics Pearls 
<http://www.amazon.com/Game-Physics-Pearls-Gino-Bergen/dp/1568814747> 
that offers a method for simulating inelastic ropes. It differs from the 
usual Jakobsen Verlet relaxation method in that it solves the rope as a 
single system of rigid components rather than a set of point masses with 
distance constraints that are solved iteratively.

Gino

PS: Apologies for the shameless plug...

On 8/3/2010 3:33 AM, Ron Hay wrote:
> Turns out searching for "string simulation" turns up a lot of things *not* about simulating little pieces of yarn and twine.  Does anyone have pointers to papers/techniques for simulating string/rope/twine?
>
> On the plus side I've read a couple interesting papers on String Theory!
>
> Thanks...
>
>     Ron
>
> ------------------------------------------------------------------------------
> The Palm PDK Hot Apps Program offers developers who use the
> Plug-In Development Kit to bring their C/C++ apps to Palm for a share
> of $1 Million in cash or HP Products. Visit us here for more details:
> http://p.sf.net/sfu/dev2dev-palm
> _______________________________________________
> 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] String simulation

[metanet s. <met...@ya...>]

Here are some more esoteric examples spanning a range of behaviours (the references will hopefully be helpful):

Section 4.1.12 of Barenbrug's thesis presents a "multi-bar" constraint (a series of distance constraints that can be used to model cable/rope): 
http://www.win.tue.nl/dynamo/publications/bartbthesis.pdf

Massless Cable for Realtime Simulation
http://www.vrlab.umu.se/research/flexible/Massless.pdf

Simulated Knot Tying
http://www.cs.duke.edu/~jeffp/papers/rope-icra.pdf
http://www.cs.duke.edu/~jeffp/research/icra-rope.pps

Real-Time Knot Tying Simulation
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.14.5543&rep=rep1&type=pdf

One-Dimensional Elastic Objects
http://cg.informatik.uni-freiburg.de/people/spillma/corde.htm

Unified Simulation of Elastic Rods, Shells, and Solids
http://graphics.ethz.ch/~smartin/data/elastons.pdf

Linear Time Super-Helices
http://www.inrialpes.fr/bipop/people/bertails/Papiers/fastsuperhelixWeb.pdf

A Mass Spring Model for Hair Simulation
http://physbam.stanford.edu/~aselle/papers/9/hair.pdf

Discrete Elastic Rods
http://www.cs.columbia.edu/cg/rods/


Most games seem to just use a chain of particles+distance constraints (or bodies+pin constraints), possibly with some tricks (such as solving the constraints in order from the free end to the anchored end, or adding a max-distance constraint between the first and last links so that the rope can't stretch too much).

raigan




--- On Mon, 8/2/10, Ron Hay <rh...@cy...> wrote:



> From: Ron Hay <rh...@cy...>
> Subject: [Algorithms] String simulation
> To: "Game Development Algorithms" <gda...@li...>
> Received: Monday, August 2, 2010, 9:33 PM
> Turns out searching for "string
> simulation" turns up a lot of things *not* about simulating
> little pieces of yarn and twine.  Does anyone have
> pointers to papers/techniques for simulating
> string/rope/twine?  
> 
> On the plus side I've read a couple interesting papers on
> String Theory!
> 
> Thanks...
> 
>    Ron
> 
> ------------------------------------------------------------------------------
> The Palm PDK Hot Apps Program offers developers who use
> the
> Plug-In Development Kit to bring their C/C++ apps to Palm
> for a share
> of $1 Million in cash or HP Products. Visit us here for
> more details:
> http://p.sf.net/sfu/dev2dev-palm
> _______________________________________________
> 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] String simulation

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

On Tue, Aug 3, 2010 at 9:02 AM, metanet software <met...@ya...> wrote:
> Here are some more esoteric examples spanning a range of behaviours (the references will hopefully be helpful):
>
> Section 4.1.12 of Barenbrug's thesis presents a "multi-bar" constraint (a series of distance constraints that can be used to model cable/rope):
> http://www.win.tue.nl/dynamo/publications/bartbthesis.pdf
>
> Massless Cable for Realtime Simulation
> http://www.vrlab.umu.se/research/flexible/Massless.pdf
>
> Simulated Knot Tying
> http://www.cs.duke.edu/~jeffp/papers/rope-icra.pdf
> http://www.cs.duke.edu/~jeffp/research/icra-rope.pps
>
> Real-Time Knot Tying Simulation
> http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.14.5543&rep=rep1&type=pdf
>
> One-Dimensional Elastic Objects
> http://cg.informatik.uni-freiburg.de/people/spillma/corde.htm
>
> Unified Simulation of Elastic Rods, Shells, and Solids
> http://graphics.ethz.ch/~smartin/data/elastons.pdf
>
> Linear Time Super-Helices
> http://www.inrialpes.fr/bipop/people/bertails/Papiers/fastsuperhelixWeb.pdf
>
> A Mass Spring Model for Hair Simulation
> http://physbam.stanford.edu/~aselle/papers/9/hair.pdf
>
> Discrete Elastic Rods
> http://www.cs.columbia.edu/cg/rods/

Nice list!

Bergou et al published an update to this last one at SIGGRAPH last week.
http://www.cs.columbia.edu/cg/threads/
The new paper is mainly about simulating "viscous threads" of liquid,
but also includes an update to the math that can make Discrete Elastic
Rods much faster too.

--bb