Re: [Algorithms] Geodesic Sphere
Brought to you by:
vexxed72
From: Dave E. <eb...@ma...> - 2000-08-23 03:17:16
|
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 |