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