gdalgorithms-list

RE: [Algorithms] 256 colour palette

[Jason B. <jba...@ig...>]

> I don't need to convert a 24-bit image to 256 colours using 
> quantisation.  I
> need to have a consistent single palette which doesn't 
> restrict me too much
> to the colours I can have in my textures.

This is the same thing isn't it - imagine all your 24bit art as one image;
find the best fit palette for that.

In the past I worked on a game that need to support 8,16 and 24bit;
all the art was designed at 24bit and then I batch calculated a fixed
8bit palette at the end and pre-converted 8bit versions of all the art.

Actually, I had an 8bit palette per game level.

This works well where you start with 24bit art;
but if your final game is 8bit only then, as you say, it might be better
to specify a fixed palette to prevent the artists getting carried away.

If you do need to calc a palette I can recommend a useful freeware DOS
graphic utility
called Display that will do the palette calculation for a number of
high-colour images. Has user selectable methods too - median, neural, oct
etc.

regards,
Jason Barstow

RE: [Algorithms] 256 colour palette

[Sasha P. <sa...@pr...>]

Hi Matt,

One way to go is to use so-called "6-6-6" palette, which gives you 6 shades
of red, green and blue color. You basically divide 255 by 6, and ~42 is your
shade step. This means, colors in your palette are:

0, 0, 0
0, 0, 42
0, 0, 85 (I rounded up here)
...
0, 42, 0
0, 42, 42
0, 42, 85
...
255, 255, 255

6-6-6 palette takes 216 colors, this is good for Windows as you still have
room for standard Windows colors. If you don't care about this, you can use
6-7-6 palette, having 7 shades for green, this takes 252 colors.

Such palettes are good because when you need to find nearest palette index
for a given 24-bit RGB color, you don't search for the nearest color,
instead you calculate it using trivial math:
Rindex = R / (255 / 6);
Gindex = G / (255 / 6);
Bindex = B / (255 / 6);

And then something like (Rindex * 6 * 6) + Gindex * 6 + Bindex gives you the
palette index. I hope I didn't make any mistakes in math here, but anyway
you should get the idea! :)

Regards,

Sasha Prokhorov.
(sa...@pr.../ICQ 4772797)

-----Original Message-----
From: Matthew Davies [mailto:MD...@ac...]
Sent: Wednesday, August 30, 2000 10:40 AM
To: Algorithms List (E-mail)
Subject: [Algorithms] 256 colour palette


Hi,
 
Can any of you guys give me some hints on choosing a decent 256 colour
palette so that I can get a nice spread of colours.  I need it for a simple
3d game so basically I need to cover common colours and shades thereof.  
 
Do any of you have experience in this area.  I've had it so easy with 24-bit
graphics up until now!  :-)
 
Thanks in advance for any help that you might provide.
 
Cheers!
Matt Davies
Programmer
Acclaim Studios, Cheltenham
+44 (0) 1242 533682
ICQ: 78711743

RE: [Algorithms] 256 colour palette

[Matthew D. <MD...@ac...>]

Hi,

Sorry, I may have not been clear.

I don't need to convert a 24-bit image to 256 colours using quantisation.  I
need to have a consistent single palette which doesn't restrict me too much
to the colours I can have in my textures.  For example, DOOM used a 256
colour palette to display all its graphics.

One idea is to have 32 different colours and 8 shades of them.  I could
design my textures in those 32 colours and 32 of a darker shade.

But I just wondered if anyone had a generic palette that they knew worked
well.

Best regards,
Matt.

> -----Original Message-----
> From: Tom Nettleship [mailto:to...@ar...]
> Sent: Wednesday, August 30, 2000 10:47
> To: 'gda...@li...'
> Subject: RE: [Algorithms] 256 colour palette
> 
> 
> The problem you're referring to is commonly called quantization. Doing
> a web search on that might glean some results.
> 
> The two main algorithms people often use are called 'Median Cut' and
> 'Octree Quantization'. Both of these are efficient, and produce good
> results.
> 
> Get hold of a copy of Graphics Gems 1... this has a paper describing
> how to implement Octree Quantization, and also (i think) source code,
> though there may be some bugs in it.
> 
> Tom Nettleship
> 
> P.S. I turned this mail into plain text from the HTML you 
> sent... please
> don't
> send HTML posts to mailing lists; people using some mail readers can't
> decipher
> them.
> 
> > From: Matthew Davies [mailto:MD...@ac...]
> > 
> > Hi,
> > 
> > Can any of you guys give me some hints on choosing a decent 
> 256 colour
> > palette so that I can get a nice > spread of colours.  I 
> need it for a
> simple
> > 3d game so basically I need to cover common colours and 
> shades thereof.  
> >  
> > Do any of you have experience in this area.  I've had it so 
> easy with
> 24-bit graphics up until now!  :-)
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

Re: [Algorithms] 256 colour palette

[Ivan-Assen I. <as...@ha...>]

Try Neuquant - a simple Kohonen NN based method.
http://www.ozemail.com.au/~dekker/NEUQUANT.HTML
there you will find sources (ANSI C, yuck), the paper itself is not available on the
Web, but the source is pretty straightforward and easy to rewrite in a simpler
manner. A bit slow, but perfectly passable for offline use. Produces much, much
better results than the other two methods I tried - Heckbert quantization and
a simple elimination of the closest colors.

RE: [Algorithms] 256 colour palette

[Tom N. <to...@ar...>]

The problem you're referring to is commonly called quantization. Doing
a web search on that might glean some results.

The two main algorithms people often use are called 'Median Cut' and
'Octree Quantization'. Both of these are efficient, and produce good
results.

Get hold of a copy of Graphics Gems 1... this has a paper describing
how to implement Octree Quantization, and also (i think) source code,
though there may be some bugs in it.

Tom Nettleship

P.S. I turned this mail into plain text from the HTML you sent... please
don't
send HTML posts to mailing lists; people using some mail readers can't
decipher
them.

> From: Matthew Davies [mailto:MD...@ac...]
> 
> Hi,
> 
> Can any of you guys give me some hints on choosing a decent 256 colour
> palette so that I can get a nice > spread of colours.  I need it for a
simple
> 3d game so basically I need to cover common colours and shades thereof.  
>  
> Do any of you have experience in this area.  I've had it so easy with
24-bit graphics up until now!  :-)

[Algorithms] Re: [GDAlgorithms-list digest, Vol 1 #103 - 2 msgs]

[Sohaib A. <soh...@us...>]

There you go David... this is from a raytracer i made... hope you understand
it...
To find out if the ray is tangent to the sphere, the dicriminant must be
zero... i think you'll figure it out.





COLORREF RayTracer::TraceRay(Vector3D endPoint, Vector3D direction, unsigned
int depth)
{
	float Ia, Kd, Ks, Kt, Krg, Ktg;
	float neta1=1.0f, neta2=0.9f, ns=1000.0f, nt=1000.0f, k=20.0f, dist=100.0f;
	Sphere *pSphere;
	Vector3D center, EO, H, H1, L, P, N, normal;
	float radius, v, disc, d, distfactor, LdotN;
	
	float t, tray=200000.0;
	Vector3D Ipoint, Inormal;
	COLORREF Ilocalcolor;
	
	bool Intersection=FALSE;

	for(unsigned int io = 0; io < theScene->objectList.size(); io++)
	{
		pSphere=(Sphere *)(theScene->objectList[io]);
		center=pSphere->center;
		radius=pSphere->radius;
		
		// Intersection Code
//////////////////////////////////////////////////////////////////////////////////////
		EO=center-endPoint;
		v=EO*direction;
		disc=radius*radius-((EO*EO)-v*v);
		if(disc<0)
			continue;			// Rejected, No intersection.
		// Intersection
		d=sqrt(disc);
		
		t=v-d;
		// Reject t if a closer intersection is already found i.e. t > t ray
		if(t<TOL || t>=tray)
			continue;

		P=endPoint+direction*t;
		normal=(P-center)/radius;
		normal.Normalize();
		
		// P: Intersection point, 
		// normal: Normal vector at P
//////////////////////////////////////////////////////////////////////////////////////
		Intersection=TRUE;
		tray=t;
		Ipoint=P;
		Inormal=normal;
		Ilocalcolor=pSphere->color;
		Ia= pSphere->Ia;
		Kd = pSphere->Kd;
		Ks = pSphere->Ks;
		Kt = pSphere->Kt;
		Krg= pSphere->Krg;
		Ktg= pSphere->Ktg;
		
		continue;

	} // End For(Object3D)
........



Regards,
Sohaib Athar.

____________________________________________________________________
Get free email and a permanent address at http://www.netaddress.com/?N=1

Re: [Algorithms] CSG intersection

[Chris P. <bi...@se...>]

Hi,
	Bretton Wades BSP faq describes the basic concepts. There is also
companion CPP source that does CSG union and subtraction. Pretty neat stuff!

http://www.xs4all.nl/~smit/whole.htm

	Regards
	  Chris

At 08:03 AM 8/29/00 -0700, you wrote:
>Gentlefolk:
>
>I have what, if you'll excuse the pun, on the surface seems to be a
>simple problem but I've been beating my head against it for some time
>to no avail.  I have something that sort of works but it runs forever.
>
>I have two (or more) closed surfaces composed of planar polygons of
>which I need to extract the intersections, calculate surface areas,
>volumes, etc.
>
>Someone recently (like yesterday) mentioned using BSP trees as part of
>a method for doing CSG operations.
>
>Could someone be so kind as to point me at a reference (web site,
>publication, or book) that discusses this in some detail.  I've done
>amount of web searching already but haven't come up with anything.
>
>Direct response to me is fine, since this is, I suspect, slightly off
>topic for this list.
>
>Thanks.
>
>							spl
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
>

Re: [Algorithms] Nearest point on plane for 2D IK

[Dave E. <eb...@ma...>]

From: "David Kornmann" <da...@ik...>
> - Take the plane defined with the ray and the center of the sphere.
> - Rotate the ray around its origin and along the plane until it is tangent
to
> the sphere.
> - Compute the tangetial point (easy).

Let C be the center of the sphere and let R be its radius.
Let the ray have origin P and direction vector D.  Assume
the ray does not pass through C.  The plane containing
C and the ray has normal N = Cross(D,C-P).  The plane
itself is Dot(N,X-P) = 0.  Let L = Length(C-P).  The point
you are looking for can be viewed as a point of
intersection of the sphere |X-C|^2 = R^2, the sphere
|X-P|^2 = L^2, and the plane Dot(N,X-P) = 0.  This gives
you three equations (two quadratic, one linear) in three
unknowns.  Alternatively you can think of intersecting each
of the spheres with the plane.  Within the plane you need
to find the intersection of two circles.

You can reduce the two quadratics to one.  Subtract the
sphere equations to get
2*Dot(P-C,X) + |C|^2 - |P|^2 = R^2 - L^2.

Do the algebra to set up the three equations as
p0 = (x-c0)^2 + (y-c1)^2 + (z-c2)^2 - R^2 = 0
p1 = a0*x+a1*y+a2*z+a3
p2 = b0*x+b1*y+b2*z+b3

res0 = Resultant[p0,p1,z] =
  d20*x^2+d11*x*y+d02*y^2+d10*x+d01*y+d00

where
  d00 = a3^2+2*a2*a3*c2+a2^2*(c0^2+c1^2+c2^2-R^2)
  d10 = 2*(a0*a3-a2^2*c0+a0*a2*c2)
  d01 = 2*(a1*a3-a2^2*c1+a1*a2*c2)
  d11 = 2*a0*a2
  d20 = a0^2+a2^2
  d02 = a1^2+a2^2

res1 = Resultant[p1,p2,z] = e0*x+e1*y+e2

where
  e0 = a2*b0-a0*b2
  e1 = a2*b1-a1*b2
  e2 = a2*b3-a3*b2

res2 = Resultant[res0,res1,y] =  f2*x^2 + f1*x + f0

where
  f0 = d00*e1^2 - d01*e1*e2 + d02*e2^2
  f1 = d10*e1^2+2*d02*e0*e2-d01*e0*e1-d11*e1*e2
  f2 = d02*e0^2-d11*e0*e1+d20*e1^2

Solve res2 = 0 for up to 2 values of x.  For each,
solve res1 = 0 for y.  For each pair (x,y) from this
construction, solve p1 = 0 for z.  You get up to
two points (x,y,z).  The one that is in the wedge
formed by the ray P+t*D and P+t*(C-P) is the
solution you want.

--
Dave Eberly
eb...@ma...
http://www.magic-software.com

Re: [Algorithms] Nearest point on plane for 2D IK

[Thatcher U. <tu...@tu...>]

From: David Kornmann <da...@ik...>
>
> > Hmmm ... surely what you want is to find the point on the line closest
to
> > the center of the sphere (easy to do) and then if that is less than R
away
> > from the center you have definite intersection, and proceed to compute
the
> > points at which the line intersects the sphere, and otherwise, you
> > conveniently have a point which is in line with the nearest tangential
point
> > of the sphere, so you can easily find that tangential point.
>
> Well, computing the point when the ray intersect with the sphere is not a
big
> deal.
> The problem comes when the ray does not intersect:
>
>  I am not looking for the closest surface point on the sphere then, but a
point
> that
> can be described as follow:
>
> - Take the plane defined with the ray and the center of the sphere.
> - Rotate the ray around its origin and along the plane until it is tangent
to
> the sphere.
> - Compute the tangetial point (easy).
>
> That's what seems to me complicated and which needs to be very accurate.

The description is a little confusing, but if I understand correctly, this
is not hard to solve.  Lets label the points:

R = ray origin
C = center of circle
T = tangent point you're interested in

If I catch your meaning, you want C, T, and the ray to all be coplanar.

If you make a triangle out of R, C and T, you have a right triangle, with
the right angle at T.  You can compute the length of the hypotenuse, it's
just |RC|, and you know the length of CT because it's equal to the circle's
radius.  So you can compute the angle CRT, it's just arcsin(|CT| / |RC|).
The angle RCT is 90 - CRT.  There's some plane which contains all these
points; compute its normal: n = normalize((C-R) x ray_direction).  To find
T, take the vector CR, rotate about n by angle RCT, and make its length
equal to the sphere radius.

What's the purpose of this?

--
Thatcher Ulrich
http://tulrich.com

Re: [Algorithms] CSG intersection

[Steve L. <sp...@nc...>]

> ...and I asked the very same question on this list (this is not OT) very
> recently - check the archives.
> 
> In short, no way to find the relevant papers (Naylor 87 & 90) on the net.
> Some useful links have been given regarding BSP+CSG (including Dan Royer's
> tutorials, BSP-Solid, etc=> archives)
> 
> Needless to say, if someone knows where to find any of the mentioned
> articles, just let us know.

It turns out that I have the reference in the SIGGRAPH `87
Proceedings.  If anyone wants a copy, they can send me a *stamped*
self-addressed envelope via snail-mail to the following address:

	Steve Lamont
	National Center for Microscopy and Imaging Research
	Mail Code 0608
	University of California, San Diego
	La Jolla, CA 92093-0608

If you're not in the US, it's up to you to figure out the correct
postage and get the right kind of stamps, though.  I don't have the
time or resources to fiddle with International Reply Coupons or the
like. 

It's 10 pages but I'll copy double sided so it shouldn't be excess
postage.

							spl

Re: [Algorithms] CSG intersection

[Pierre T. <p.t...@wa...>]

...and I asked the very same question on this list (this is not OT) very
recently - check the archives.

In short, no way to find the relevant papers (Naylor 87 & 90) on the net.
Some useful links have been given regarding BSP+CSG (including Dan Royer's
tutorials, BSP-Solid, etc=> archives)

Needless to say, if someone knows where to find any of the mentioned
articles, just let us know.

Pierre

----- Original Message -----
From: Dave Smith <Dav...@sd...>
To: <gda...@li...>
Sent: Wednesday, August 30, 2000 12:31 AM
Subject: Re: [Algorithms] CSG intersection


> Yes, that's one I've been looking for as well.
> Couldn't find a copy at our local University.
> If someone has this I would love a copy.
> (Snail mail or whatever.)
>
> Thanks,
> -DaveS
>
> Mark Duchaineau wrote:
> >
> > Steve,
> >
> > For BSP-style CSG, the main paper I know about is Thibault's 87
> > siggraph paper:
> >
> > William C. Thibault and Bruce F. Naylor, "Set Operations on Polyhedra
> > Using Binary Space Partitioning Trees," Computer Graphics
> > (Proceedings of SIGGRAPH 87), 21 (4),  pp. 153-162 (July 1987,
> > Anaheim, California).
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

RE: [Algorithms] Nearest point on plane for 2D IK

[Steve W. <Ste...@im...>]

> -----Original Message-----
> From: Steve Wood 
> That's not the tangent yet because we need to move 
> that point in an arc around the sphere toward the 
> beginning of the ray by the same angle as

Oops!  Not that angle but 90 degrees minus that angle...darn KMart virtual
protractor!
Rockn-Roll

> described by the center of the sphere to the intersection of 
> the ray and the
> plane to the beginning of the ray.

> -----Original Message-----
> From: Steve Wood 
> Sent: Tuesday, August 29, 2000 4:15 PM
> To: 'gda...@li...'
> Subject: RE: [Algorithms] Nearest point on plane for 2D IK
> 
> 
> How about if you use the center of the sphere and the point 
> at the beginning
> of your ray to use as the normal for a plane passing through 
> the center of
> the sphere.  Calculate the intersection of the ray and that plane.
> Calculate the point that is the sphere's radius from it's 
> center along the
> line from the center of the sphere to the intersection of the 
> ray and the
> plane.  That's not the tangent yet because we need to move 
> that point in an
> arc around the sphere toward the beginning of the ray by the 
> same angle as
> described by the center of the sphere to the intersection of 
> the ray and the
> plane to the beginning of the ray.
> 
> Just using my virtual protractor and compass.
> 
> Rockn-Roll
> 
> > -----Original Message-----
> > From: David Kornmann [mailto:da...@ik...]
> > Sent: Tuesday, August 29, 2000 2:43 PM
> > To: gda...@li...
> > Subject: Re: [Algorithms] Nearest point on plane for 2D IK
> > 
> > 
> > 
> > 
> > 
> > > Hmmm ... surely what you want is to find the point on the 
> > line closest to
> > > the center of the sphere (easy to do) and then if that is 
> > less than R away
> > > from the center you have definite intersection, and proceed 
> > to compute the
> > > points at which the line intersects the sphere, and otherwise, you
> > > conveniently have a point which is in line with the nearest 
> > tangential point
> > > of the sphere, so you can easily find that tangential point.
> > 
> > Well, computing the point when the ray intersect with the 
> > sphere is not a big
> > deal.
> > The problem comes when the ray does not intersect:
> > 
> >  I am not looking for the closest surface point on the sphere 
> > then, but a point
> > that
> > can be described as follow:
> > 
> > - Take the plane defined with the ray and the center of the sphere.
> > - Rotate the ray around its origin and along the plane until 
> > it is tangent to
> > the sphere.
> > - Compute the tangetial point (easy).
> > 
> > That's what seems to me complicated and which needs to be 
> > very accurate.
> > 
> > Any idea?
> > 
> > Thanks.
> > 
> > David Kornmann.
> > --
> > 
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> > 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

RE: [Algorithms] Nearest point on plane for 2D IK

[Steve W. <Ste...@im...>]

How about if you use the center of the sphere and the point at the beginning
of your ray to use as the normal for a plane passing through the center of
the sphere.  Calculate the intersection of the ray and that plane.
Calculate the point that is the sphere's radius from it's center along the
line from the center of the sphere to the intersection of the ray and the
plane.  That's not the tangent yet because we need to move that point in an
arc around the sphere toward the beginning of the ray by the same angle as
described by the center of the sphere to the intersection of the ray and the
plane to the beginning of the ray.

Just using my virtual protractor and compass.

Rockn-Roll

> -----Original Message-----
> From: David Kornmann [mailto:da...@ik...]
> Sent: Tuesday, August 29, 2000 2:43 PM
> To: gda...@li...
> Subject: Re: [Algorithms] Nearest point on plane for 2D IK
> 
> 
> 
> 
> 
> > Hmmm ... surely what you want is to find the point on the 
> line closest to
> > the center of the sphere (easy to do) and then if that is 
> less than R away
> > from the center you have definite intersection, and proceed 
> to compute the
> > points at which the line intersects the sphere, and otherwise, you
> > conveniently have a point which is in line with the nearest 
> tangential point
> > of the sphere, so you can easily find that tangential point.
> 
> Well, computing the point when the ray intersect with the 
> sphere is not a big
> deal.
> The problem comes when the ray does not intersect:
> 
>  I am not looking for the closest surface point on the sphere 
> then, but a point
> that
> can be described as follow:
> 
> - Take the plane defined with the ray and the center of the sphere.
> - Rotate the ray around its origin and along the plane until 
> it is tangent to
> the sphere.
> - Compute the tangetial point (easy).
> 
> That's what seems to me complicated and which needs to be 
> very accurate.
> 
> Any idea?
> 
> Thanks.
> 
> David Kornmann.
> --
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

Re: [Algorithms] CSG intersection

[Dave S. <Dav...@sd...>]

Yes, that's one I've been looking for as well.
Couldn't find a copy at our local University.
If someone has this I would love a copy.
(Snail mail or whatever.)

Thanks,
-DaveS

Mark Duchaineau wrote:
> 
> Steve,
> 
> For BSP-style CSG, the main paper I know about is Thibault's 87
> siggraph paper:
> 
> William C. Thibault and Bruce F. Naylor, "Set Operations on Polyhedra
> Using Binary Space Partitioning Trees," Computer Graphics
> (Proceedings of SIGGRAPH 87), 21 (4),  pp. 153-162 (July 1987,
> Anaheim, California).

Re: [Algorithms] CSG intersection

[Mark D. <duc...@ll...>]

Steve,

For BSP-style CSG, the main paper I know about is Thibault's 87
siggraph paper:

William C. Thibault and Bruce F. Naylor, "Set Operations on Polyhedra
Using Binary Space Partitioning Trees," Computer Graphics
(Proceedings of SIGGRAPH 87), 21 (4),  pp. 153-162 (July 1987,
Anaheim, California).

A list of Thibault's papers is at:

http://www.mcs.csuhayward.edu/~tebo/bio.html

I didn't see a link to an electronic version.  Unfortunately
this was before ACM started collecting electronic versions
of all the siggraph papers in their digital library.  Go hunt down
a friend who has the proceedings or email the authors...

--Mark

Steve Lamont wrote:

> Gentlefolk:
>
> I have what, if you'll excuse the pun, on the surface seems to be a
> simple problem but I've been beating my head against it for some time
> to no avail.  I have something that sort of works but it runs forever.
>
> I have two (or more) closed surfaces composed of planar polygons of
> which I need to extract the intersections, calculate surface areas,
> volumes, etc.
>
> Someone recently (like yesterday) mentioned using BSP trees as part of
> a method for doing CSG operations.
>
> Could someone be so kind as to point me at a reference (web site,
> publication, or book) that discusses this in some detail.  I've done
> amount of web searching already but haven't come up with anything.
>
> Direct response to me is fine, since this is, I suspect, slightly off
> topic for this list.
>
> Thanks.
>
>                                                         spl
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] Nearest point on plane for 2D IK

[David K. <da...@ik...>]

> Hmmm ... surely what you want is to find the point on the line closest to
> the center of the sphere (easy to do) and then if that is less than R away
> from the center you have definite intersection, and proceed to compute the
> points at which the line intersects the sphere, and otherwise, you
> conveniently have a point which is in line with the nearest tangential point
> of the sphere, so you can easily find that tangential point.

Well, computing the point when the ray intersect with the sphere is not a big
deal.
The problem comes when the ray does not intersect:

 I am not looking for the closest surface point on the sphere then, but a point
that
can be described as follow:

- Take the plane defined with the ray and the center of the sphere.
- Rotate the ray around its origin and along the plane until it is tangent to
the sphere.
- Compute the tangetial point (easy).

That's what seems to me complicated and which needs to be very accurate.

Any idea?

Thanks.

David Kornmann.
--

Re: [Algorithms] Nearest point on plane for 2D IK

[Jeff L. <je...@di...>]

Plug for Dave Eberly's Magic-Software site goes here:

http://www.magic-software.com/MgcIntersection.html

Looks like the code you need is :
Lin3Sphr.h, Lin3Sphr.cpp 

-Jeff

At 09:56 PM 8/29/2000 +0300, you wrote:
>Hi,
>
>I am looking for an algorithm to compute the intersecting point P between a ray and
>a sphere. I know the center C and the radius R of the sphere, the origin O of the ray
>and its direction V. Basically I need to find the closest intersection from O.
>
>But that's not all: In addition to this, IF the ray does not intersect or is tangent to the
>sphere, I need to know the tangential point with the sphere.
>
>Does anybody know a fast and accurate solution to this problem? maybe a good web
>site or some code would greatly help!...
>
>Thanks,
>
>David Kornmann.
>--
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

RE: [Algorithms] Nearest point on plane for 2D IK

[Robert D. <RD...@ac...>]

> Hi,
> 
> I am looking for an algorithm to compute the intersecting 
> point P between a ray and
> a sphere. I know the center C and the radius R of the sphere, 
> the origin O of the ray
> and its direction V. Basically I need to find the closest 
> intersection from O.
> 
> But that's not all: In addition to this, IF the ray does not 
> intersect or is tangent to the
> sphere, I need to know the tangential point with the sphere.
> 
> Does anybody know a fast and accurate solution to this 
> problem? maybe a good web
> site or some code would greatly help!...

Hmmm ... surely what you want is to find the point on the line closest to
the center of the sphere (easy to do) and then if that is less than R away
from the center you have definite intersection, and proceed to compute the
points at which the line intersects the sphere, and otherwise, you
conveniently have a point which is in line with the nearest tangential point
of the sphere, so you can easily find that tangential point.

Rob

Re: [Algorithms] Nearest point on plane for 2D IK

[David K. <da...@ik...>]

Hi,

I am looking for an algorithm to compute the intersecting point P between a ray and
a sphere. I know the center C and the radius R of the sphere, the origin O of the ray
and its direction V. Basically I need to find the closest intersection from O.

But that's not all: In addition to this, IF the ray does not intersect or is tangent to the
sphere, I need to know the tangential point with the sphere.

Does anybody know a fast and accurate solution to this problem? maybe a good web
site or some code would greatly help!...

Thanks,

David Kornmann.
--

[Algorithms] Nearest point on plane for 2D IK

[Jeff L. <je...@di...>]

Since we were talking about skeleton animation, I have a question.

For my IK system, I prefer to use actual 2D joints where appropriate rather then use the general 3D form and limit with DOF restrictions.  I have received some email asking me how to do this with my CCD IK routine so I wanted to write up a paragraph on the little math routine for the magazine.  I think it is pretty obvious to people familiar with vector math, but I have found that many developers don't have the background and need some help.  I will put this in with my continuing series on why dot product is your friend.

I want to sanity check it to make sure this is a good, fast way to do this.  I know that it works but it may not be the best method.

Given a bone object in 3 space, B, and a desired 3D target to attempt to reach, T.  The method is to determine the plane that B is allowed to rotate, then project T into that plane.  Then I solve for the rotation angle.

To project T onto B's free rotational plane:

N = free axis of rotation

V = T - B		// Creates vector from base to target
P = T - N ( N dot V)	// Project V onto axis and subtract that from the target

Now, P is my new target point for the IK routine.  Continue as usual, dot product to get the angle to rotate, ...
I will explain why this works and such but you get the idea.

-Jeff

RE: [Algorithms] Spline Surface Extremal Points ?

[Steve W. <Ste...@im...>]

Well, I didn't think the original poster wanted to get into a discussion
like this, but now you made me take out my calculus book :)  An extrema of a
function F(x,y,z,...n) will be where the first derivative is zero F' = 0 AND
the product of the partial derivatives minus the square of the sum of the
partial derivatives is greater than zero. Reference: Calculus with analytic
geometry, Earl W. Swokowski.

If you twist a graph around then you also change the function....if it's not
a function then there will be some set of coordinates where F(x,y,z,...n)
can be two or more different values and is not a function and will not be
usefull for much of anything especially in 3D graphics...ie...player
KamaKazi could be in two places at the same time. However, sometimes you can
change the coordinate system to develop a function which will give you a
means to find extrema.  For example, a sphere can not be described by a
function in cartesian coordinates, but we can use polar coordinates to give
us a function for which we could find extrema.

I guess my point is that life will find a way...no wait that's from Jurassic
Park...I guess I don't have any point.

Rockn-Roll

> -----Original Message-----
> From: Dave Eberly [mailto:eb...@ma...]
> Sent: Monday, August 28, 2000 8:04 PM
> To: gda...@li...
> Subject: Re: [Algorithms] Spline Surface Extremal Points ?
> 
> 
> From: "Steve Wood" <Ste...@im...>
> > I don't know anything about spline patches...but extrema is 
> defined as the
> > point where the the slope of the tangent=0 AND the slope of 
> the tangent to
> > the left of that point is the opposite sign from the slope 
> of the tangent
> to
> > the right of that point...ie...it's not an inflection point.
> 
> Your definition is for the graph of a function y = f(x).  A 
> local maximum
> occurs at x0 if f'(x0) = 0 and f"(x0) < 0.  Unfortunately 
> these extrema
> are tied into the coordinate system.  Consider f(x) = 1-x^2 
> for |x| <= 1.
> The local maximum occurs at x = 0.  Now rotate the curve 
> (x,f(x)) about
> the origin a small amount (so that no tangent line becomes vertical).
> The new curve is a graph of another function, but the local maximum
> for it is not at the same point as in the original coordinate system.
> 
> For a graph z = (x,y,f(x,y)), a local maximum occurs at (x0,y0) if
> Gradient(f)(x0,y0) = (0,0) and Hessian(f)(x0,y0) is a negative
> definite matrix.  Just as in the one dimensional case, if the graph
> has no vertical tangents, and if you rotate the graph a small amount
> so that you still have no vertical tangents, the new surface is a
> graph of another function, but the local maxima are not at the
> same location as in the original coordinate system.
> 
> If the original poster has a coordinate system in mind for the
> surface, then the definition above will locate the extremal
> points.  But if the idea is to find some "intrinsic" extrema,
> for example, the vertices of an ellipsoid that do not change
> with orientation of the ellipsoid, you need a different concept
> for extremum.  The usual ones involve measuring principal
> curvatures and deriving some scalar function from them, then
> applying the definition mentioned above for finding extrema
> of that function.  This approach is what is used for defining
> "ridges"  (curves of extreme points) on a surface.
> 
> --
> Dave Eberly
> eb...@ma...
> http://www.magic-software.com
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

[Algorithms] CSG intersection

[Steve L. <sp...@nc...>]

Gentlefolk:

I have what, if you'll excuse the pun, on the surface seems to be a
simple problem but I've been beating my head against it for some time
to no avail.  I have something that sort of works but it runs forever.

I have two (or more) closed surfaces composed of planar polygons of
which I need to extract the intersections, calculate surface areas,
volumes, etc.

Someone recently (like yesterday) mentioned using BSP trees as part of
a method for doing CSG operations.

Could someone be so kind as to point me at a reference (web site,
publication, or book) that discusses this in some detail.  I've done
amount of web searching already but haven't come up with anything.

Direct response to me is fine, since this is, I suspect, slightly off
topic for this list.

Thanks.

							spl

Re: [Algorithms] Skeletal Animation...

[Pierre T. <p.t...@wa...>]

Agreed.
Brandon, you may have a look there: www.codercorner.com\Cloth.htm

I use springs as described by Tom, and I believe it would be just perfect
for a ponytail. Actually the default piece of cloth in the demo could look
like a ponytail once reduced (it's a bit lengthy).

Pierre

----- Original Message -----
From: Tom Forsyth <to...@mu...>
To: <gda...@li...>
Sent: Tuesday, August 29, 2000 11:25 AM
Subject: RE: [Algorithms] Skeletal Animation...


> Use stiff springs between the vertices of the ponytail, and no instant
> propogation down the chain. So each frame, each spring just affects the
ones
> it is attached to. It works just fine for apps like this, where a little
bit
> of deformation is not going to be noticed. Propogating forces/impluses
down
> chains instantly is a real pain, but allowing the springs to do it
> themselves over a few frames makes life much easier. It goes wrong for
some
> apps, but not in this case.
>
> Tom Forsyth - Muckyfoot bloke.
> Whizzing and pasting and pooting through the day.
>
> > -----Original Message-----
> > From: Brandon Moro [mailto:the...@us...]
> > Sent: 29 August 2000 06:59
> > To: gda...@li...
> > Subject: [Algorithms] Skeletal Animation...
> >
> >
> > Hello.
> >
> > I was wondering if anyone had links to some good skeletal animation
> > techniques and perhaps some information about the kinematics involved.
> >
> > For example, if I was a model to have a ponytail which moves
> > realistically.
> > Given gravity and the mass of my character, I should be able
> > to generate the
> > normal force produced by walking (feet hitting the ground).
> >
> > Assuming the ponytail is just a couple bones end-to-end
> > sharing intermediate
> > vertices, the problem I arrive at is the way to correctly
> > propogate a force
> > applied at the origin vertex (ie the one connecting the
> > ponytail to the
> > head) down into the other vertices.
> >
> > Any possible links would be great.  I heard that someone
> > wrote quite a few
> > papers on the physics involved in this, but I can't remember his name
> > exactly.  I know his last name is something like Mirich, but
> > thats not quite
> > it.
> >
> > Thanx!
> > Brandon Moro
> >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> >
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

RE: [Algorithms] Skeletal Animation...

[Tom F. <to...@mu...>]

Use stiff springs between the vertices of the ponytail, and no instant
propogation down the chain. So each frame, each spring just affects the ones
it is attached to. It works just fine for apps like this, where a little bit
of deformation is not going to be noticed. Propogating forces/impluses down
chains instantly is a real pain, but allowing the springs to do it
themselves over a few frames makes life much easier. It goes wrong for some
apps, but not in this case.

Tom Forsyth - Muckyfoot bloke.
Whizzing and pasting and pooting through the day.

> -----Original Message-----
> From: Brandon Moro [mailto:the...@us...]
> Sent: 29 August 2000 06:59
> To: gda...@li...
> Subject: [Algorithms] Skeletal Animation...
> 
> 
> Hello.
> 
> I was wondering if anyone had links to some good skeletal animation
> techniques and perhaps some information about the kinematics involved.
> 
> For example, if I was a model to have a ponytail which moves 
> realistically.
> Given gravity and the mass of my character, I should be able 
> to generate the
> normal force produced by walking (feet hitting the ground).
> 
> Assuming the ponytail is just a couple bones end-to-end 
> sharing intermediate
> vertices, the problem I arrive at is the way to correctly 
> propogate a force
> applied at the origin vertex (ie the one connecting the 
> ponytail to the
> head) down into the other vertices.
> 
> Any possible links would be great.  I heard that someone 
> wrote quite a few
> papers on the physics involved in this, but I can't remember his name
> exactly.  I know his last name is something like Mirich, but 
> thats not quite
> it.
> 
> Thanx!
> Brandon Moro
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

Re: [Algorithms] It looks terrible (was: Lightmap Terrain)

[Klaus H. <k_h...@os...>]

Mark,

From: Mark Wilczynski <mwi...@cy...>
> Hi Niki,
>
> You could also try the trick that many people used when
> making outdoor levels for Quake based games.  They create a
> 2D grid of lightsources on a plane in the sky.  The
> brightness of each light is adjusted based on the sun
> position.  This method approximates an area light source
> (sky/clouds) instead of just a point light (sun).

This would be another option, but if I understand it correctly, then you
lose the properties of a directional light source. I'll have a look at the
modeling sites, though.

>  Search
> around the Quake modeling sites for more details.  By the
> way... I think your lightmap looks fine.  Lightmaps never
> look very good when viewed alone.

I disagree. I have tried the method I described, and the results look great
(including the dark sides of the mountains). The method has all the features
I was looking for, except that the shadows are still sharp (didn't take care
about this, yet). My current implementation of this is sort of brute force,
though:

I specify the position of the sun as a point on a unit sphere (longitude,
latitude). Then for each vertex of the surface, I calculate the vertex
normal, and then use this normal to calculate a second point on the unit
sphere (longitude, latitude). Then I compute the shortest distance between
the two points on the sphere (that is along the great circle). This gives a
distance in the range [0; PI]. I divide this distance by PI to get a
distance in the range [0; 1], and then I apply a bias-function to the
distance in order to compute the light intensity.

I'm sure there's cheaper methods to compute this, but here's some help for
those who'd like to try this:

float GreatCircleDistance(float lon1, float lat1, float lon2, float lat2)
{
    float theta = lon2 - lon1;
    float dist = acos(sin(lat2) * sin(lat1) + cos(lat1) * cos(lat2) *
cos(theta));
    if (dist < 0) dist += PI;
    return dist / PI;
}

A vertex normal can be converted into (lonVertex, latVertex) as follows
(y-component represents elevation):

lonVertex = atan2(normal.z, normal.x)
latVertex = atan2(normal.y, sqrt(normal.x^2 + normal.z^2))

For the shadow casting you may also need to convert the light source's
(lonLight, latLight) into a unit vector:

lightDir.x = cos(lonLight) * cos(latLight);
lightDir.y = sin(latLight);
lightDir.z = sin(lonLight) * cos(latLight);

The intensity is computed as follows:
I = GreatCircleDistance(lonLight, latLigh, lonVertex, latVertex);
I = 1.0f - pow(I, log(b) / log(0.5));

Where b is the bias. In this case, b is some value > 0.5 (I used 0.6). This
basically defines the gradient of the intensity over the sphere. I'll
probably try a couple of other functions, too, and see what yields the best
results.

> You have to blend them
> with a noisy base texture to get a decent effect.

The noisy base texture will further enhance the quality, yes.


Thanks,
Niki