gdalgorithms-list

Re: [Algorithms] 2D in a 3D world

[Matthew H. <ma...@ev...>]

Hi Jason:

IIRC you're not guaranteed that the hardware won't filter even when you are
at a perfect 1:1.  You may need to add some higher-level logic to manage
your filtering states.  I could be wrong about this, but looking at our
code, we're set to point-sampling for all HUD, UI overlays, etc.

And you likely will need the 1/2 pixel adjustment.

Double check to be sure you don't have anything strange going on with the
mip range adjustments, etc.  Build your textures without mips just to be
sure.

Matt


On Sat, Aug 7, 2010 at 4:20 PM, Jason Hughes <jh...@st...>wrote:

> I've been trying to resolve an issue where full screen textures being
> drawn through the 3D system appear blurry.  I feel like I'm probably not
> considering something.  Any ideas would be welcome!
>
> - I'm using an orthographic projection matrix along Z, a view matrix
> that is pretty much identity except for some negations on various axes
> to correct for LH/RH differences in the engine.
> - The quad is mapped to the full screen both for vertex positions and
> UVs (0,0,1) to (1,1,1), since the ortho matrix is 0..1, not in screen
> pixels.
> - The texture has the exactly the same number of pixels in both
> directions as the back buffer.
> - Back buffer and window match resolution exactly.
> - Resolution is 1024x600 (but problem exists in other resolutions)
> - Texture sampling is bilinear or anisotropic (shouldn't matter).  Both
> show the problem.  Sometimes my 2D stuff needs to cleanly scale, so I
> can't force point sampling globally.  Texture matrix is disabled.
>
> Steps I've taken to debug:
> - I made a simple texture with regions that are alternating white and
> black columns and rows that are 1, 2, and 4 pixels wide, so I could see
> what was happening with texture sampling.  The result is an even gray in
> the 1-pixel wide areas, but can be made brighter and darker depending on
> the offset I put into the matrices.  Half-pixel adjustment didn't fix
> it.  I never get white or black lines.
> - I checked to make sure that the test image wasn't being munged by the
> texture processing tools and it's perfectly clean (no GIGO).
>
> I can understand not getting perfect rasterization vertically due to the
> height being a non-power-of-two, but I expected columns to be cleanly
> mapped.  What else should I be looking for?
>
> Most appreciated,
> JH
>
> Jason Hughes
> President
> Steel Penny Games
> Austin, TX
>
>
>
> ------------------------------------------------------------------------------
> This SF.net email is sponsored by
>
> Make an app they can't live without
> Enter the BlackBerry Developer Challenge
> http://p.sf.net/sfu/RIM-dev2dev
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>
>

Re: [Algorithms] 2D in a 3D world

[Colin B. <bar...@gm...>]

Direct3D texel offset perchance?

http://msdn.microsoft.com/en-us/library/bb219690(VS.85).aspx

On 7 August 2010 22:20, Jason Hughes <jh...@st...> wrote:

> I've been trying to resolve an issue where full screen textures being
> drawn through the 3D system appear blurry.  I feel like I'm probably not
> considering something.  Any ideas would be welcome!
>
> - I'm using an orthographic projection matrix along Z, a view matrix
> that is pretty much identity except for some negations on various axes
> to correct for LH/RH differences in the engine.
> - The quad is mapped to the full screen both for vertex positions and
> UVs (0,0,1) to (1,1,1), since the ortho matrix is 0..1, not in screen
> pixels.
> - The texture has the exactly the same number of pixels in both
> directions as the back buffer.
> - Back buffer and window match resolution exactly.
> - Resolution is 1024x600 (but problem exists in other resolutions)
> - Texture sampling is bilinear or anisotropic (shouldn't matter).  Both
> show the problem.  Sometimes my 2D stuff needs to cleanly scale, so I
> can't force point sampling globally.  Texture matrix is disabled.
>
> Steps I've taken to debug:
> - I made a simple texture with regions that are alternating white and
> black columns and rows that are 1, 2, and 4 pixels wide, so I could see
> what was happening with texture sampling.  The result is an even gray in
> the 1-pixel wide areas, but can be made brighter and darker depending on
> the offset I put into the matrices.  Half-pixel adjustment didn't fix
> it.  I never get white or black lines.
> - I checked to make sure that the test image wasn't being munged by the
> texture processing tools and it's perfectly clean (no GIGO).
>
> I can understand not getting perfect rasterization vertically due to the
> height being a non-power-of-two, but I expected columns to be cleanly
> mapped.  What else should I be looking for?
>
> Most appreciated,
> JH
>
> Jason Hughes
> President
> Steel Penny Games
> Austin, TX
>
>
>
> ------------------------------------------------------------------------------
> This SF.net email is sponsored by
>
> Make an app they can't live without
> Enter the BlackBerry Developer Challenge
> http://p.sf.net/sfu/RIM-dev2dev
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

Re: [Algorithms] 2D in a 3D world

[Marco S. <mar...@gm...>]

Hi Jason,

Does your texture come with a full mipmap chain? If that's the case it would
be better to see what happens without mipmaps and just point filtering.

On which platform are you working?

Some drivers with low quality settings may set by default a positive LOD
bias. Are you (inadvertently?) modifying the textures LOD bias at all?

Marco

On Sat, Aug 7, 2010 at 2:20 PM, Jason Hughes <jh...@st...>wrote:

> I've been trying to resolve an issue where full screen textures being
> drawn through the 3D system appear blurry.  I feel like I'm probably not
> considering something.  Any ideas would be welcome!
>
> - I'm using an orthographic projection matrix along Z, a view matrix
> that is pretty much identity except for some negations on various axes
> to correct for LH/RH differences in the engine.
> - The quad is mapped to the full screen both for vertex positions and
> UVs (0,0,1) to (1,1,1), since the ortho matrix is 0..1, not in screen
> pixels.
> - The texture has the exactly the same number of pixels in both
> directions as the back buffer.
> - Back buffer and window match resolution exactly.
> - Resolution is 1024x600 (but problem exists in other resolutions)
> - Texture sampling is bilinear or anisotropic (shouldn't matter).  Both
> show the problem.  Sometimes my 2D stuff needs to cleanly scale, so I
> can't force point sampling globally.  Texture matrix is disabled.
>
> Steps I've taken to debug:
> - I made a simple texture with regions that are alternating white and
> black columns and rows that are 1, 2, and 4 pixels wide, so I could see
> what was happening with texture sampling.  The result is an even gray in
> the 1-pixel wide areas, but can be made brighter and darker depending on
> the offset I put into the matrices.  Half-pixel adjustment didn't fix
> it.  I never get white or black lines.
> - I checked to make sure that the test image wasn't being munged by the
> texture processing tools and it's perfectly clean (no GIGO).
>
> I can understand not getting perfect rasterization vertically due to the
> height being a non-power-of-two, but I expected columns to be cleanly
> mapped.  What else should I be looking for?
>
> Most appreciated,
> JH
>
> Jason Hughes
> President
> Steel Penny Games
> Austin, TX
>
>
>
> ------------------------------------------------------------------------------
> This SF.net email is sponsored by
>
> Make an app they can't live without
> Enter the BlackBerry Developer Challenge
> http://p.sf.net/sfu/RIM-dev2dev
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

[Algorithms] 2D in a 3D world

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

I've been trying to resolve an issue where full screen textures being 
drawn through the 3D system appear blurry.  I feel like I'm probably not 
considering something.  Any ideas would be welcome!

- I'm using an orthographic projection matrix along Z, a view matrix 
that is pretty much identity except for some negations on various axes 
to correct for LH/RH differences in the engine.
- The quad is mapped to the full screen both for vertex positions and 
UVs (0,0,1) to (1,1,1), since the ortho matrix is 0..1, not in screen 
pixels.
- The texture has the exactly the same number of pixels in both 
directions as the back buffer.
- Back buffer and window match resolution exactly.
- Resolution is 1024x600 (but problem exists in other resolutions)
- Texture sampling is bilinear or anisotropic (shouldn't matter).  Both 
show the problem.  Sometimes my 2D stuff needs to cleanly scale, so I 
can't force point sampling globally.  Texture matrix is disabled.

Steps I've taken to debug:
- I made a simple texture with regions that are alternating white and 
black columns and rows that are 1, 2, and 4 pixels wide, so I could see 
what was happening with texture sampling.  The result is an even gray in 
the 1-pixel wide areas, but can be made brighter and darker depending on 
the offset I put into the matrices.  Half-pixel adjustment didn't fix 
it.  I never get white or black lines.
- I checked to make sure that the test image wasn't being munged by the 
texture processing tools and it's perfectly clean (no GIGO).

I can understand not getting perfect rasterization vertically due to the 
height being a non-power-of-two, but I expected columns to be cleanly 
mapped.  What else should I be looking for?

Most appreciated,
JH

Jason Hughes
President
Steel Penny Games
Austin, TX

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

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

[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

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

I'm guessing many of the search misses were about
vibrating musical strings under tension, but you might be
able to work with that well established basis of 1D of
coupling relationships between nominally unit masses
and get something out of papers on finite difference
schemes. Some of the musical stuff could inform you about 
tricks for viscous damping, boundary behaviour and other 
loss in the model. 




On Mon, 2 Aug 2010 21:03:23 -0500
Jeff Russell <je...@8m...> wrote:

> Googling for "rope physics" proved a bit more fruitful. "Verlet Integration"
> may be a helpful search term as well.
> 
> A Simple demo with source code:
> http://www.functionblog.com/?p=134
> 
> Also of possible relevance to this list: If you google image search for
> string you will get a lot of pictures of girls in string bikinis.
> 
> Jeff
> 
> On Mon, Aug 2, 2010 at 8:33 PM, Ron Hay <rh...@cy...> 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
> >
> 
> 
> 
> -- 
> Jeff Russell
> Engineer, 8monkey Labs
> www.8monkeylabs.com


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

Re: [Algorithms] String simulation

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

Googling for "rope physics" proved a bit more fruitful. "Verlet Integration"
may be a helpful search term as well.

A Simple demo with source code:
http://www.functionblog.com/?p=134

Also of possible relevance to this list: If you google image search for
string you will get a lot of pictures of girls in string bikinis.

Jeff

On Mon, Aug 2, 2010 at 8:33 PM, Ron Hay <rh...@cy...> 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
>



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

[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] 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

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, 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...>]

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...>]

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

[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...>]

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

[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

[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

[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] 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.

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

[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
>