From: Gavin Kistner Date: 2004-10-17T05:43:04+09:00 Subject: [SUMMARY] Geodesic Faces (#3) There were three major challenges which comprised the meat of this quiz: 1) What the heck was I talking about? ======================================================================== Although finding the answer to #1 was not intended to be part of the quiz, it certainly was. Due to incomplete specification and background, one had to do a bit of searching to understand what a geodesic dome is, and how that related to the supplied information about primitives and faces. A quick search on Wikipedia yields: http://en.wikipedia.org/wiki/Geodesic_dome I won't repeat the information on that page here, but the summary is: A geodesic dome is an approximation of a sphere, made out of triangles connected by straight edges. To create a geodesic dome, start with a platonic solid with triangular faces--tetrahedron, octahedron, or icosahedron. Subdivide each triangular face into a number of smaller triangles, and then push the points of those triangles out from the center of the primitive to the radius of the sphere. This brings us to challenge number 2: 2) How do you find the points on the face, and make triangles from them? ======================================================================== There are various techniques for determining the exact locations of the points for the sub triangles. (Several techniques are described in the white paper "Geodesic Math"[1], starting on page 9. The one chosen for and described by this quiz is the Class 1, Method 1 technique (page 9), which creates small triangles with sides of equal length. Each of the four solutions was unique. Everyone used vectors to solve the problem, although Dennis worked extra hard and created his own Vector class rather than using the one included in the matrix library included with Ruby. Dennis also went his own way and divided the sides of the triangles into equal-angles (as measured from the center of the geodesic), instead of equal-length pieces. This technique is slightly more effective at evenly distributing the triangles across the surface of the sphere. For example, compare an octahedron subdivided with frequency 20, using the linear technique (as outlined by the quiz) versus the angular technique Dennis used in this picture[2]. Note how the linear technique has the triangles piling up along the edges of the original face of the octahedron, where the radial technique does a better job of spacing them out. I was the only one who used a recursive technique to hunt down all the triangles on the face, and was the only one to consider groups of faces as hexagons. The other three solutions all use cleaner methods of using one loop inside another and cleanly navigating the whole face, once. Dennis and I both used a separate class for a face/triangle, while Warren and Martinus keep track of their information in a more 'raw' fashion. 3) How do you provide the results? ======================================================================== The solution by Martinus stands out, as he put the extra effort in to create a simple OpenGL viewer for his solution. While his solution wasn't quite correct (he forgot to normalize the points on the face, pushing them out away from the plane of the face to the surface of the sphere), it was a trivial change to fix it, as Dennis pointed out[3]. Further, Martinus' solution was the fastest (even with the additional code to normalize the points). In calculating the 20,808 faces for an octahedron of frequency 50, the times on my computer were: Martinus: 4.32 seconds Gavin: 8.61 seconds Warren: 12.81 seconds Dennis: 80.49 seconds For reasons I couldn't figure out, Dennis' solution returns a bunch of NaN points when dealing with the icosahedron primitive. (Which is why I used octahedrons to test the output.) Also, I had to add attr_reader :faces to his Dome class; without that (or an #instance_eval call) there was no way to get at the data, once created :) It was difficult to test Warren's output, as the results it provided were not organized into triplets of points. The call to flatten took Warren's array of point-triplet arrays and squashed it into a flat array of points. However, without the call to flatten, the points were stuck in arrays of faces for each original face in the primitive. I had this problem initially with my solution, which is why I created a separate Face class -- so that flattening the arrays of arrays of faces would not squash out the array of points contained within each face. An alternative solution, and I think what Warren intended, is something like Array#flatten_once[4], either through that separate library or by rolling ones' own #flatten_once method. Despite the above 'problems', the quiz didn't specify what to do with the data in the end, or how to provide it. The solutions met the requirements correctly, if not conveniently :) Wrap Up ======================================================================== When I proposed this quiz, I didn't realize how few people were conversant with the concepts of Geodesic domes (although I should have). I apologize for not being more clear with the specifications to the problem, particularly in the lack of background information. I also did not see that the scope of the quizzes is intended to be as short as it is (30-60 minutes). Although this problem took some longer than I had expected, I *did* expect it to be a 2-3 hour problem. So, sorry for supplying a quiz which was perhaps more work than people have time for. As penance, I give you some pretty pictures to end with: showing what the domes look like (using the linear interpolation defined by the quiz) for the three primitive types and with various frequencies. The first picture[5] shows the faces clearly, the second[6] shows how well they approximate spheres when used in a rendering engine that can smooth the shading between the faces. URLs ------------------------------------------------------------------------ [1] http://www.salsburg.com/geod/geodesicmath.pdf [2] http://phrogz.net/CSS/Geodesics/LinearVersusRadial.gif [3] http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/116102 [4] http://www.wobblini.net/ruby/flattenx.html [5] http://phrogz.net/CSS/Geodesics/VariousGeodesics_planar.png [6] http://phrogz.net/CSS/Geodesics/VariousGeodesics_smooth.png -- (-, /\ \/ / /\/