gdalgorithms-list

RE: [Algorithms] Geodesic Sphere

[Peter W. <Pet...@vi...>]

Here's a link I've used (found on Dave Eberly's site,
www.magic-software.com, in the Other Links section);

http://forum.swarthmore.edu/dr.math/problems/matz12.15.96.html

> I'm looking for an algoritm to create a geodesic sphere(is the name 
> correct?), a sphere made of equilateral triangles. I would be 
> nice if I 
> could choose the resolution(more or less triangles).
> 
> Aldo Spanghero

RE: [Algorithms] Geodesic Sphere

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

I don't think the geodesic is made of equilateral triangles ... in fact I
believe the only solid of vaguely spherical shape that you can make with
equilateral triangles is the icosahedron (20 tri's)

Apart from that I can't help, but I'd have thought a quick search on the web
would throw up several.

Robert

> -----Original Message-----
> From: Aldo . [mailto:al...@ho...]
> Sent: 22 August 2000 13:45
> To: gda...@li...
> Subject: [Algorithms] Geodesic Sphere
> 
> 
> 
> Hi!
> 
> I'm looking for an algoritm to create a geodesic sphere(is the name 
> correct?), a sphere made of equilateral triangles. I would be 
> nice if I 
> could choose the resolution(more or less triangles).
> 
> 
> 
> Thanks in advance.
> 
> Aldo Spanghero
> 
> 
> ______________________________________________________________
> __________
> Get Your Private, Free E-mail from MSN Hotmail at 
http://www.hotmail.com


_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] Geodesic Sphere

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

From: "Robert Dibley" <RD...@ac...>
> I don't think the geodesic is made of equilateral triangles ... in fact I
> believe the only solid of vaguely spherical shape that you can make with
> equilateral triangles is the icosahedron (20 tri's)

Yes.  The code I mentioned in an earlier post generates a
mesh of triangles that are not equilateral.  But a related
question might be the following.  Given a scalar function
that determines how 'close' a triangle is to equilateral, can
you construct a triangle mesh such that all its triangles
have metric smaller than a prescribed tolerance?  Such
a scalar function is F(T) = sum_{i=1}^3 |A_i - pi/3|^2 where
the A_i are the angles of the triangle T.  Or maybe a function
that is zero when all three sides have same length, positive
otherwise.  Or a combination of the two.

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

RE: [Algorithms] Geodesic Sphere

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

This problem is difficult since all three sides of all triangles will be
equal.  It requires dividing a sphere longitudinally by X number of
triangles while dividing it laterally by Xsin(pi/3) = X * [sqr(3)/2] and
where sqr(3)/2 * X is a whole number or whole fraction...and offhand I can't
think of any whole number X where multiplying it by sqr(3)/2 will result in
something like 8 or 1/2.

I suggest using isosceles triangles since the algorithm is much simpler and
I posted it earlier concerning spherical texture mapping...here's a clip
from it (yes it's in basic...hope you can read it):

For example here's how I create a sphere:

Dim pi as single
Dim pi2 as single

Dim spherecount as long
Dim spherename() As String
Dim spherevertexcount As Long

Dim sphereradius(1) As Single
Dim spherecenter(1) As D3DVERTEX
Dim spheredx7vertex(1100) As D3DVERTEX

pi=3.14159265
pi2=pi * 2

spherecount = 1
spherename(1) = "Sphere 1"
spherecenter(1).x = 0
spherecenter(1).y = 4
spherecenter(1).z = 6
sphereradius(1) = 1			'radius

c = 16	'number of sections...smaller c means larger triangles, larger c
means smaller triangles
b = 0
For cameraangle.x = 0 To pi * (c - 1) / c + 0.0001 Step pi / c
 For cameraangle.y = 0 To pi2 + 0.0001 Step pi / c
  b = b + 1
  dx7.CreateD3DVertex sphereradius(1) * Sin(cameraangle.y) *
Sin(cameraangle.x) + spherecenter(1).x, sphereradius(1) * Cos(cameraangle.x)
+ spherecenter(1).y, sphereradius(1) * Cos(cameraangle.y) *
Sin(cameraangle.x) + spherecenter(1).z, Sin(cameraangle.y) *
Sin(cameraangle.x), Cos(cameraangle.x), Cos(cameraangle.y) *
Sin(cameraangle.x), cameraangle.y / pi2, cameraangle.x / pi,
spheredx7vertex(b)
  b = b + 1
  dx7.CreateD3DVertex sphereradius(1) * Sin(cameraangle.y) *
Sin(cameraangle.x + pi / c) + spherecenter(1).x, sphereradius(1) *
Cos(cameraangle.x + pi / c) + spherecenter(1).y, sphereradius(1) *
Cos(cameraangle.y) * Sin(cameraangle.x + pi / c) + spherecenter(1).z,
Sin(cameraangle.y) * Sin(cameraangle.x + pi / c), Cos(cameraangle.x + pi /
c), Cos(cameraangle.y) * Sin(cameraangle.x + pi / c), cameraangle.y / pi2,
(cameraangle.x + pi / c) / pi, spheredx7vertex(b)
 Next
Next

spherevertexcount = b
vertexperstrip = c * 4 + 2

d3d7device.SetTexture 0, dd7surface(7)  'sphere
For b = 1 To spherevertexcount - vertexperstrip + 1 Step vertexperstrip
 Call d3d7device.DrawPrimitive(D3DPT_TRIANGLESTRIP, D3DFVF_VERTEX,
spheredx7vertex(b), vertexperstrip, D3DDP_DEFAULT)
Next



> -----Original Message-----
> From: Aldo . [mailto:al...@ho...]
> Sent: Tuesday, August 22, 2000 5:45 AM
> To: gda...@li...
> Subject: [Algorithms] Geodesic Sphere
> 
> 
> 
> Hi!
> 
> I'm looking for an algoritm to create a geodesic sphere(is the name 
> correct?), a sphere made of equilateral triangles. I would be 
> nice if I 
> could choose the resolution(more or less triangles).
> 
> 
> 
> Thanks in advance.
> 
> Aldo Spanghero
> 
> 
> ______________________________________________________________
> __________
> Get Your Private, Free E-mail from MSN Hotmail at 
http://www.hotmail.com


_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] Geodesic Sphere

[Adam M. <amo...@dp...>]

The classic way to subdivide quadruples your number of triangles with every
step.  You might find Leif Kobbelt's sqrt(3) subdivision paper from this
year's siggraph interesting.  While the paper focuses on subdivision
surfaces, he describes a method of subdividing which could be applied to
arbitrary problems of tessellation.  His approach triples the number of
triangles with every step, allowing for finer LOD control.  It is in fact
very simple -- I would be surprised if no one was using this scheme before
him.

--
--Adam Moravanszky
http://www.n.ethz.ch/student/adammo

-----Original Message-----
From: Dave Eberly <eb...@ma...>
To: gda...@li...
<gda...@li...>
Date: Tuesday, August 22, 2000 3:11 PM
Subject: Re: [Algorithms] Geodesic Sphere


>From: "Aldo ." <al...@ho...>
>> I'm looking for an algoritm to create a geodesic sphere(is the name
>> correct?), a sphere made of equilateral triangles. I would be nice if I
>> could choose the resolution(more or less triangles).
>
>From: "Peter Warden" <Pet...@vi...>
>> Here's a link I've used (found on Dave Eberly's site,
>> www.magic-software.com, in the Other Links section);
>>
>> http://forum.swarthmore.edu/dr.math/problems/matz12.15.96.html
>
>Or you could just use the code (with MS Windows test program)
>at http://www.magic-software.com/gr_dcmp.htm , section with
>files sphrtesl.{h,cpp,pdf} and sptstest.cpp.  The tessellation is
>by recursive subdivision.  You start with any inscribed convex
>polyhedron.  If you want the 'classic' cases, start with an
>octahedron (part of the sptstest program) or an icosahedron.
>
>--
>Dave Eberly
>eb...@ma...
>http://www.magic-software.com
>
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] Geodesic Sphere

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

From: "Adam Moravanszky" <amo...@dp...>
> The classic way to subdivide quadruples your number of triangles with
every
> step.  You might find Leif Kobbelt's sqrt(3) subdivision paper from this
> year's siggraph interesting.  While the paper focuses on subdivision
> surfaces, he describes a method of subdividing which could be applied to
> arbitrary problems of tessellation.  His approach triples the number of
> triangles with every step, allowing for finer LOD control.  It is in fact
> very simple -- I would be surprised if no one was using this scheme before
> him.

I thought the 'classic' way replaced each triangle by three triangles?
I have not seen Kobbelt's paper, so perhaps he is replacing each
triangle by two?  An algorithm I describe in my game engine book and
that was implemented for continuous level of detail of surfaces in
NetImmerse uses a generalization of Peter Lindstrom's terrain
system.  For an arbitrary triangle mesh you subdivide each triangle
once by computing its centroid and adding edges from the three
vertices to the centroid.  Each subtriangle shares a 'hypotenuse'
(probably an abuse of the word since the subtriangles are not
necessarily right-angled) with a subtriangle in the originally
neighboring triangle.  Once you have this correspondence, you
attempt to subdivide each hypotenuse based on some heuristic
like curvature (or curvature + screen space metric).  If the
subdivision is allowed, you replace each triangle sharing the
hypotenuse with two triangles formed by drawing an edge from
the vertex opposite the hypotenuse to the 'midpoint' added by
the subdivision.  Each subtriangle formed has a hypotenuse that
is the edge opposite the midpoint.

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

Re: [Algorithms] Geodesic Sphere

[Adam M. <amo...@dp...>]

If I understand your explanation correctly (creating a new vertex inside the
triangle, then replacing the original edges of the triangles with different
ones), this is pretty much what Kobbelt does.  The 1->4 way I had in mind
was the common tessellation approach of splitting each of the three edges of
the original to create 3 new vertices, then adding 3 new edges to form 4
triangles.
--
--Adam Moravanszky
http://www.n.ethz.ch/student/adammo

-----Original Message-----
From: Dave Eberly <eb...@ma...>
To: gda...@li...
<gda...@li...>
Date: Wednesday, August 23, 2000 5:23 AM
Subject: Re: [Algorithms] Geodesic Sphere


>From: "Adam Moravanszky" <amo...@dp...>
>> The classic way to subdivide quadruples your number of triangles with
>every
>> step.  You might find Leif Kobbelt's sqrt(3) subdivision paper from this
>> year's siggraph interesting.  While the paper focuses on subdivision
>> surfaces, he describes a method of subdividing which could be applied to
>> arbitrary problems of tessellation.  His approach triples the number of
>> triangles with every step, allowing for finer LOD control.  It is in fact
>> very simple -- I would be surprised if no one was using this scheme
before
>> him.
>
>I thought the 'classic' way replaced each triangle by three triangles?
>I have not seen Kobbelt's paper, so perhaps he is replacing each
>triangle by two?  An algorithm I describe in my game engine book and
>that was implemented for continuous level of detail of surfaces in
>NetImmerse uses a generalization of Peter Lindstrom's terrain
>system.  For an arbitrary triangle mesh you subdivide each triangle
>once by computing its centroid and adding edges from the three
>vertices to the centroid.  Each subtriangle shares a 'hypotenuse'
>(probably an abuse of the word since the subtriangles are not
>necessarily right-angled) with a subtriangle in the originally
>neighboring triangle.  Once you have this correspondence, you
>attempt to subdivide each hypotenuse based on some heuristic
>like curvature (or curvature + screen space metric).  If the
>subdivision is allowed, you replace each triangle sharing the
>hypotenuse with two triangles formed by drawing an edge from
>the vertex opposite the hypotenuse to the 'midpoint' added by
>the subdivision.  Each subtriangle formed has a hypotenuse that
>is the edge opposite the midpoint.
>
>--
>Dave Eberly
>eb...@ma...
>http://www.magic-software.com

Re: [Algorithms] Geodesic Sphere

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

From: "Adam Moravanszky" <amo...@dp...>
> If I understand your explanation correctly (creating a new vertex inside
the
> triangle, then replacing the original edges of the triangles with
different
> ones), this is pretty much what Kobbelt does.  The 1->4 way I had in mind
> was the common tessellation approach of splitting each of the three edges
of
> the original to create 3 new vertices, then adding 3 new edges to form 4
> triangles.

Of course 4 is correct.  This is what my code does that I mentioned in
an earlier post (subdivide inscribed convex polyhedron).  I was thinking
ahead to the first subdivision in my algorithm where I split into 3.

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

RE: [Algorithms] Geodesic Sphere

[Aldo S. <al...@ho...>]

Hi.

An icosahedron would be fine. I will use it to create 3D explosion for my 
game.
Do you know some algoritm to generate an icosahedron?

Thank you.

And thanks to the other guys for the answers!

>
>I don't think the geodesic is made of equilateral triangles ... in fact I
>believe the only solid of vaguely spherical shape that you can make with
>equilateral triangles is the icosahedron (20 tri's)
>
>Apart from that I can't help, but I'd have thought a quick search on the 
>web
>would throw up several.
>
>Robert

________________________________________________________________________
Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com

Re: [Algorithms] Geodesic Sphere

[Odin J. <od...@it...>]

Can't you just have a mesh of half a circle and scale it? (Or interpolate
between 2 frames if it would screw up your dynamic lights)

Odin
----- Original Message -----
From: "Aldo Spanghero" <al...@ho...>
To: <gda...@li...>
Sent: Wednesday, August 23, 2000 3:44 PM
Subject: RE: [Algorithms] Geodesic Sphere


> Hi.
>
> An icosahedron would be fine. I will use it to create 3D explosion for my
> game.
> Do you know some algoritm to generate an icosahedron?
>
> Thank you.
>
> And thanks to the other guys for the answers!
>
> >
> >I don't think the geodesic is made of equilateral triangles ... in fact I
> >believe the only solid of vaguely spherical shape that you can make with
> >equilateral triangles is the icosahedron (20 tri's)
> >
> >Apart from that I can't help, but I'd have thought a quick search on the
> >web
> >would throw up several.
> >
> >Robert
>
> ________________________________________________________________________
> Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

Re: [Algorithms] Geodesic Sphere (explosion)

[Michael S. H. <mic...@ud...>]

I've found it easiest and most convincing just to use a static half-sphere which is billboarded and scaled as the explosion expands.  Since the texture used is typically an alpha texture which represents an object that has its own "light", I don't worry about the normal going a bit whacky.  Combine the scaling with a bit of texture animation and you end up with good looking explosions.

At 03:52 PM 8/23/00, you wrote:
>Can't you just have a mesh of half a circle and scale it? (Or interpolate
>between 2 frames if it would screw up your dynamic lights)
>
>Odin
>----- Original Message -----
>From: "Aldo Spanghero" <al...@ho...>
>To: <gda...@li...>
>Sent: Wednesday, August 23, 2000 3:44 PM
>Subject: RE: [Algorithms] Geodesic Sphere
>
>
>> Hi.
>>
>> An icosahedron would be fine. I will use it to create 3D explosion for my
>> game.
>> Do you know some algoritm to generate an icosahedron?
>>
>> Thank you.
>>
>> And thanks to the other guys for the answers!
>>
>> >
>> >I don't think the geodesic is made of equilateral triangles ... in fact I
>> >believe the only solid of vaguely spherical shape that you can make with
>> >equilateral triangles is the icosahedron (20 tri's)
>> >
>> >Apart from that I can't help, but I'd have thought a quick search on the
>> >web
>> >would throw up several.
>> >
>> >Robert
>>
>> ________________________________________________________________________
>> Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com
>>
>>
>> _______________________________________________
>> 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] Geodesic Sphere

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

From: "Aldo Spanghero" <al...@ho...>
> Do you know some algoritm to generate an icosahedron?

MgcReal = float
MgcVector3 is struct { float x, y, z }

    const MgcReal fGold = 0.5*(MgcMath::Sqrt(5.0)+1.0);

    unsigned int uiVertexQuantity = 12;
    MgcVector3* akVertex = new MgcVector3[12];
    akVertex[0] = MgcVector3( fGold,  1.0,  0.0 );
    akVertex[1] = MgcVector3(-fGold,  1.0,  0.0 );
    akVertex[2] = MgcVector3( fGold, -1.0,  0.0 );
    akVertex[3] = MgcVector3(-fGold, -1.0,  0.0 );
    akVertex[4] = MgcVector3( 1.0,  0.0,  fGold );
    akVertex[5] = MgcVector3( 1.0,  0.0, -fGold );
    akVertex[6] = MgcVector3(-1.0,  0.0,  fGold );
    akVertex[7] = MgcVector3(-1.0,  0.0, -fGold );
    akVertex[8] = MgcVector3( 0.0,  fGold,  1.0 );
    akVertex[9] = MgcVector3( 0.0, -fGold,  1.0 );
    akVertex[10] = MgcVector3( 0.0,  fGold, -1.0 );
    akVertex[11] = MgcVector3( 0.0, -fGold, -1.0 );

    unsigned int uiTriangleQuantity = 20;
    unsigned int* auiConnect = new unsigned int[3*20];
    auiConnect[ 0] =  0;  auiConnect[ 1] =  8;  auiConnect[ 2] =  4;
    auiConnect[ 3] =  0;  auiConnect[ 4] =  5;  auiConnect[ 5] = 10;
    auiConnect[ 6] =  2;  auiConnect[ 7] =  4;  auiConnect[ 8] =  9;
    auiConnect[ 9] =  2;  auiConnect[10] = 11;  auiConnect[11] =  5;
    auiConnect[12] =  1;  auiConnect[13] =  6;  auiConnect[14] =  8;
    auiConnect[15] =  1;  auiConnect[16] = 10;  auiConnect[17] =  7;
    auiConnect[18] =  3;  auiConnect[19] =  9;  auiConnect[20] =  6;
    auiConnect[21] =  3;  auiConnect[22] =  7;  auiConnect[23] = 11;
    auiConnect[24] =  0;  auiConnect[25] = 10;  auiConnect[26] =  8;
    auiConnect[27] =  1;  auiConnect[28] =  8;  auiConnect[29] = 10;
    auiConnect[30] =  2;  auiConnect[31] =  9;  auiConnect[32] = 11;
    auiConnect[33] =  3;  auiConnect[34] = 11;  auiConnect[35] =  9;
    auiConnect[36] =  4;  auiConnect[37] =  2;  auiConnect[38] =  0;
    auiConnect[39] =  5;  auiConnect[40] =  0;  auiConnect[41] =  2;
    auiConnect[42] =  6;  auiConnect[43] =  1;  auiConnect[44] =  3;
    auiConnect[45] =  7;  auiConnect[46] =  3;  auiConnect[47] =  1;
    auiConnect[48] =  8;  auiConnect[49] =  6;  auiConnect[50] =  4;
    auiConnect[51] =  9;  auiConnect[52] =  4;  auiConnect[53] =  6;
    auiConnect[54] = 10;  auiConnect[55] =  5;  auiConnect[56] =  7;
    auiConnect[57] = 11;  auiConnect[58] =  7;  auiConnect[59] =  5;

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

Re: [Algorithms] Geodesic Sphere

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

From: "Aldo ." <al...@ho...>
> I'm looking for an algoritm to create a geodesic sphere(is the name 
> correct?), a sphere made of equilateral triangles. I would be nice if I 
> could choose the resolution(more or less triangles).

From: "Peter Warden" <Pet...@vi...>
> Here's a link I've used (found on Dave Eberly's site,
> www.magic-software.com, in the Other Links section);
> 
> http://forum.swarthmore.edu/dr.math/problems/matz12.15.96.html

Or you could just use the code (with MS Windows test program)
at http://www.magic-software.com/gr_dcmp.htm , section with
files sphrtesl.{h,cpp,pdf} and sptstest.cpp.  The tessellation is
by recursive subdivision.  You start with any inscribed convex
polyhedron.  If you want the 'classic' cases, start with an
octahedron (part of the sptstest program) or an icosahedron.

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