G
Gavin Kistner
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
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