-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- The three rules of Ruby Quiz: 1. Please do not post any solutions or spoiler discussion for this quiz until 48 hours have elapsed from the time this message was sent. 2. Support Ruby Quiz by submitting ideas and responses as often as you can! Visit: <http://rubyquiz.strd6.com> 3. Enjoy! Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone on Ruby Talk follow the discussion. Please reply to the original quiz message, if you can. -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- ## Mathematical Image Generator (#191) This week's quiz is about the generation of images based on mathematical functions. The red, green, and blue values at each point in the image will each be determined by a separate function based on the coordinates at that position. Here are some functions to get started: Math.sin(Math::PI * ?) Math.cos(Math::PI * ?) (? + ?)/2 ? * ? (?) ** 3 The question marks represent the parameters to the functions (x, y, or another function). The x and y values range between 0 and 1: the proportion of the current position to the total width or height. Feel free to add your own functions, but keep in mind that they work best when the inputs and output are between -1 and 1. Example Output: http://strd6.com/?attachment_id=145 depth: 3 red: Math.sin(Math::PI * Math.cos(Math::PI * y * x)) green: Math.sin(Math::PI * (Math.sin(Math::PI * y)) ** 3) blue: (Math.cos(Math::PI * Math.cos(Math::PI * y))) ** 3 The depth is how many layers of functions to combine. The bottom layer is always x or y. Depth 3 is where things begin to get a little bit interesting, but 5 and higher is much more exciting. Performance can be an issue with so many computations per pixel, therefore the solution that performs quickest on a 1600x1200 image with depth of 7 will be the winner of this quiz! Good luck!
on 2009-02-06 18:00
on 2009-02-06 19:26
On Fri, Feb 6, 2009 at 5:59 PM, Daniel Moore <yahivin@gmail.com> wrote: > is always x or y. Depth 3 is where things begin to get a little bit > interesting, but 5 and higher is much more exciting. The link to the example output is dead. Also, I don't get what you mean by 'depth' exactly. I can see the red: as either depth 2: somecomplicatedfunction( times(x, y) ) or depth 5: sin( times( pi, cos( times(pi, times(x,y)))))
on 2009-02-06 20:42
On Fri, Feb 6, 2009 at 10:25 AM, Sander Land <sander.land@gmail.com> wrote: >> The depth is how many layers of functions to combine. The bottom layer > > You're right, I'm sorry for my error. Here is an updated link: http://strd6.com/?p=146 My explanation of function depth is also somewhat confusing. If anyone sees what I'm getting at and wants to try and help me out with another explanation please do! Let me try again in the meantime: Function depth is more of a tree depth in this circumstance. Some functions take two parameters, some take one parameter. So depth of 0 would be either x or y. Depth 1 would be any of the following: (x + x)/2 (x + y)/2 sin(PI * x) sin(PI * y) cos(PI * x) ... Depth 2 could be: (sin(PI * x) + x * y)/2 Part of the difficulty in this quiz is composing functions of different arity. Hopefully this explanation clears things up a little. Thanks for bringing this up and if you have any further questions please continue to ask.
on 2009-02-08 06:11
Di Mo wrote: > My explanation of function depth is also somewhat confusing. If anyone > sees what I'm getting at and wants to try and help me out with another > explanation please do! Let me try again in the meantime: Does "depth" equal "the number of times 'x' (or 'y') appears in the expression" ?
on 2009-02-08 06:25
And is this before or after collection? 2x + x + 5x = 8x, has one term of x at degree 1. 2x^2 -x + 4x^2 + x = 6x^2, has one term of x at degree 2 and none at degree 1.... <quote who="Albert Schlef">
on 2009-02-08 18:45
Daniel Moore wrote: > ## Mathematical Image Generator (#191) > > This week's quiz is about the generation of images based on > mathematical functions. The red, green, and blue values at each point > in the image will each be determined by a separate function based on > the coordinates at that position. ... > Performance can be an issue with so many computations per pixel, > therefore the solution that performs quickest on a 1600x1200 image > with depth of 7 will be the winner of this quiz! I think for a pure speed competition, we'd need a standard set of functions, a reference image, a defined way to translate -1..1 values to colour intensities (eg 0..255). But it seemed like a fun one, so below is my offering: a little desktop (wxRuby) program for generating these maths images interactively. Type the r, g and b functions into the boxes, then click "Render" to update. "Save Image" saves the current image to TIF, PNG or BMP. If there's an error in a function, a cross mark appears next to it; hover over the cross mark to get a hint about the problem. On my system, using Ruby 1.9, it renders the default image at 800 x 600 in about 2.85s. Since the speed is pretty much proportional to the total pixels, I'd guess about 11.5s for a 1600x1200 image. Interestingly, this is one where Ruby 1.9 makes a big difference. a __________ require 'wx' include Wx include Math # A canvas that draws and displays a mathematically generated image class MathsDrawing < Window # The functions which return the colour components at each pixel attr_writer :red, :green, :blue # The time taken to render, whether re-rendering is needed, and the # source image attr_reader :render_time, :done, :img def initialize(parent) super(parent) # Create a dummy image @default_image = Image.new(1, 1) @default_image.data = [255, 255, 255].pack('CCC') @img = @default_image @red = lambda { | x, y | 1 } @green = lambda { | x, y | 1 } @blue = lambda { | x, y | 1 } @done = true evt_size :on_size evt_paint :on_paint evt_idle :on_idle end # Paint the image on the screen. The actual image rendering is done in # idle time, so that the GUI is responsive whilst redrawing - eg, when # resized. Painting is done by quickly rescaling the cached image. def on_paint paint do | dc | draw_img = @img.scale(client_size.x, client_size.y) dc.draw_bitmap(draw_img.convert_to_bitmap, 0, 0, true) end end # Regenerate the image if needed, then do a refresh def on_idle if not @done @img = make_image refresh end @done = true end # Note to regenerate the image if the canvas has been resized def on_size(event) @done = false event.skip end # Call this to force a re-render - eg if the functions have changed def redraw @done = false end # Actually make the image def make_image size_x, size_y = client_size.x, client_size.y if size_x < 1 or size_y < 1 return @default_image end start_time = Time.now # The string holding raw image data data = '' x_factor = size_x.to_f y_factor = size_y.to_f # Input values from the range 0 to 1, with origin in the bottom left size_y.downto(0) do | y | the_y = y.to_f / y_factor 0.upto(size_x - 1) do | x | the_x = x.to_f / x_factor red = @red.call(the_x, the_y) * 255 green = @green.call(the_x, the_y) * 255 blue = @blue.call(the_x, the_y) * 255 data << [red, green, blue].pack("CCC") end end img = Image.new(size_x, size_y) img.data = data @render_time = Time.now - start_time img end end # A helper dialog for saving the image to a file class SaveImageDialog < FileDialog # The image file formats on offer TYPES = [ [ "PNG file (*.png)|*.png", BITMAP_TYPE_PNG ], [ "TIF file (*.tif)|*.tif", BITMAP_TYPE_TIF ], [ "BMP file (*.bmp)|*.bmp", BITMAP_TYPE_BMP ] ] WILDCARD = TYPES.map { | type | type.first }.join("|") def initialize(parent) super(parent, :wildcard => WILDCARD, :message => 'Save Image', :style => FD_SAVE|FD_OVERWRITE_PROMPT) end # Returns the Wx identifier for the selected image type. def image_type TYPES[filter_index].last end end # A Panel for displaying the image and controls to manipulate it class MathsPanel < Panel # Set functions to some nice initial values RED_INITIAL = "cos(x)" GREEN_INITIAL = "cos(y ** x)" BLUE_INITIAL = "(x ** 4) + ( y ** 3 ) - (4.5 * x ** 2 ) + ( y * 2)" # Symbols to show correct and incorrect functions TICK = "\xE2\x9C\x94" CROSS = "\xE2\x9C\x98" attr_reader :drawing def initialize(parent) super(parent) self.sizer = VBoxSizer.new # The canvas @drawing = MathsDrawing.new(self) sizer.add @drawing, 1, GROW sizer.add Wx::StaticLine.new(self) # The text controls for entering functions grid_sz = FlexGridSizer.new(3, 8, 8) grid_sz.add_growable_col(1, 1) grid_sz.add StaticText.new(self, :label => "Red") @red_tx = TextCtrl.new(self, :value => RED_INITIAL) grid_sz.add @red_tx, 0, GROW @red_err = StaticText.new(self, :label => TICK) grid_sz.add @red_err, 0, ALIGN_CENTRE grid_sz.add StaticText.new(self, :label => "Green") @green_tx = TextCtrl.new(self, :value => GREEN_INITIAL) grid_sz.add @green_tx, 0, GROW @green_err = StaticText.new(self, :label => TICK) grid_sz.add @green_err, 0, ALIGN_CENTRE grid_sz.add StaticText.new(self, :label => "Blue") @blue_tx = TextCtrl.new(self, :value => BLUE_INITIAL) grid_sz.add @blue_tx, 0, GROW @blue_err = StaticText.new(self, :label => TICK) grid_sz.add @blue_err, 0, ALIGN_CENTRE # Buttons to save and render grid_sz.add nil butt_sz = HBoxSizer.new render_bt = Button.new(self, :label => "Render") butt_sz.add render_bt, 0, Wx::RIGHT, 8 evt_button render_bt, :on_render save_bt = Button.new(self, :label => "Save Image") butt_sz.add save_bt, 0, Wx::RIGHT, 8 evt_button save_bt, :on_save # Disable the buttons whilst redrawing evt_update_ui(render_bt) { | evt | evt.enable(@drawing.done) } evt_update_ui(save_bt) { | evt | evt.enable(@drawing.done) } grid_sz.add butt_sz # Add the controls sizer to the whole thing sizer.add grid_sz, 0, GROW|ALL, 10 on_render end # Update the functions that generate the image, then re-render it def on_render @drawing.red = make_a_function(@red_tx.value, @red_err) @drawing.green = make_a_function(@green_tx.value, @green_err) @drawing.blue = make_a_function(@blue_tx.value, @blue_err) @drawing.redraw end # Display a dialog to save the image to a file def on_save dlg = SaveImageDialog.new(parent) if dlg.show_modal == ID_OK @drawing.img.save_file(dlg.path, dlg.image_type) end end # A function which doesn't do anything NULL_FUNC = lambda { | x, y | 1 } # Takes a string source +source+, returns a lambda. If the string # source isn't valid, flag this in the GUI static text +error_outlet+ def make_a_function(source, error_outlet) return NULL_FUNC if source.empty? func = nil begin # Create the function and test it, to check for wrong names func = eval "lambda { | x, y | #{source} }" func.call(0, 0) rescue Exception => e error_outlet.label = CROSS error_outlet.tool_tip = e.class.name + ":\n" + e.message.sub(/^\(eval\):\d+: /, '') return NULL_FUNC end error_outlet.label = TICK error_outlet.tool_tip = '' func end end class MathsFrame < Frame def initialize super(nil, :title => 'Maths drawing', :size => [400, 500], :pos => [50, 50]) sb = create_status_bar(1) evt_update_ui sb, :on_update_status @panel = MathsPanel.new(self) end def on_update_status if @panel.drawing.done pixels = @panel.drawing.client_size msg = "[#{pixels.x} x #{pixels.y}] drawing completed in " + "#{@panel.drawing.render_time}s" status_bar.status_text = msg end end end App.run do MathsFrame.new.show end
on 2009-02-08 21:35
I'm still not doing a very good job of explaining this. One more
attempt, this time by a coding example.
CAUTION: Spoiler! If you want to generate random functions on your own
do not read further. This implements the function generation, not
anything specific to image generation.
Here is a class that will generate string representations of functions
given a specified depth. Feel free to use or modify this class in your
solutions.
class FunctionMaker
def initialize()
@functions = ["Math.sin(Math::PI * ?)", "Math.cos(Math::PI * ?)",
"(? + ?)/2", "? * ?", "(?) ** 3"]
end
# Create a string representation of a function at the given
def create_function(depth)
#if depth is 0, return either x or y randomly
if depth == 0
return "x" if rand > 0.5
return "y"
end
#grab a random function from the list
function = @functions[rand(@functions.length)]
#for each instance of ? in the function, replace with a function
at the next shallower depth
return function.gsub("?") { create_function(depth - 1) }
end
end
Usage:
fm = FunctionMaker.new
fm.create_function(5)
=> "(Math.sin(Math::PI * ((Math.cos(Math::PI * y) + y * y)/2 + y * x *
y * y)/2)) ** 3"
on 2009-02-08 22:09
On Sun, Feb 8, 2009 at 9:33 PM, Daniel Moore <yahivin@gmail.com> wrote:
> @functions = ["Math.sin(Math::PI * ?)", "Math.cos(Math::PI * ?)",
I think this is what caused the confusion, at least for me. You
consider "Math.sin(Math::PI * ?)" one depth level extra instead of
two.
on 2009-02-11 00:01
This is my first quiz submission. Any comments appreciated.
I opted for RMagick to generate the image from raw pixels. There
might be faster options (GD?), but the time spent converting pixel
values to an image and writing this to file is negligible compared
to actually generating the pixels, especially when the functions
get more complex.
I found I could shave some time off the pixel generation by wrapping
the whole iteration process inside a single eval instead of calling
functions (or worse, doing an eval) for each iteration.
$ cat gen_image.rb
#!/usr/bin/env ruby
require 'rubygems'
require 'RMagick'
class FunctionGenerator
def initialize
@functions = []
end
def <<(function)
@functions << function
end
def random_function_of_depth(depth)
if depth == 0
['x', 'y', '-x', '-y'][rand(4)]
else
function = @functions[rand(@functions.size)]
function.gsub('expr') { random_function_of_depth(depth - 1) }
end
end
end
class ImageGenerator
include Math
# Functions for red, green and blue
attr_accessor :red, :green, :blue
# Generate image and store to file
def generate_image(filename, width, height)
@width = width
@height = height
generate_pixels
store_image(filename)
end
private
# Generate pixels of image
def generate_pixels
@pixels = ""
eval <<"."
0.upto(@height - 1) do |y_pos|
y = (y_pos.to_f / @height)
0.upto(@width - 1) do |x_pos|
x = (x_pos.to_f / @width)
@pixels << (127.99 + 127.99 * #{@red}).to_i.chr
@pixels << (127.99 + 127.99 * #{@green}).to_i.chr
@pixels << (127.99 + 127.99 * #{@blue}).to_i.chr
end
end
.
end
# Store generated image to file
def store_image(filename)
image = Magick::Image.new(@width, @height)
image.import_pixels(0, 0, @width, @height, 'RGB', @pixels)
image.opacity = 0
image.write(filename)
end
end
func_gen = FunctionGenerator.new
func_gen << '(expr + expr) / 2'
func_gen << '(expr) ** 3'
func_gen << 'expr * expr'
func_gen << 'sin(expr * PI)'
func_gen << 'cos(expr * PI)'
image_gen = ImageGenerator.new
image_gen.red = func_gen.random_function_of_depth(4)
image_gen.green = func_gen.random_function_of_depth(4)
image_gen.blue = func_gen.random_function_of_depth(4)
puts "r: #{image_gen.red}"
puts "g: #{image_gen.green}"
puts "b: #{image_gen.blue}"
image_gen.generate_image('image.png', 800, 800)
--
Lars Haugseth
"If anyone disagrees with anything I say, I am quite prepared not only
to
retract it, but also to deny under oath that I ever said it." -Tom
Lehrer
on 2009-02-15 20:47
This week's quiz was about creating interesting mathematical images
using randomly generated formulae. Visit
http://rubyquiz.strd6.com/quizzes/191/#summary to view the summary
with images included.
The overall architecture of the application is straightforward:
* generate (or accept as input) mathematical formulae
* compute the RGB values for each pixel
* output an image
Lars's solution provides a simple shell script which randomly
generates formulae of depth 4 and saves image out as a png file.
Lars's solution also makes it easy to add custom functions to the
generator by pushing them on to an array.
Alex Fenton provides a desktop application (using [wxRuby][1]) that
allows for custom input of formulae and can save the images in
multiple formats. If you are interested in learning wxRuby do examine
Alex's solution as it provides a good example of a wxRuby application
and is well commented.
The two solutions provided slightly different conversions from
function results to pixel colors. Alex's treated everything <= 0 as 0,
while Lars mapped -1 to 0 and 1 to 255, with 0 being 128 (on an 8-bit
RBG scale). This causes some images to appear wildly different,
observe:
![image with zero at midrange][2a] ![image with zero and less
cutoff][2b]
One aspect of the challenge was to generate the images quickly. Here
are the results of the submissions using ruby-prof to benchmark.
ruby 1.8.6 (2007-09-24 patchlevel 111) [i486-linux]
width: 256
height: 256
r: cos(sin((sin(-x * PI)) ** 3 * PI) * PI)
g: (sin(((-y + y) / 2) ** 3 * PI)) ** 3
b: ((cos(-x * y * PI) + cos(cos(y * PI) * PI)) / 2 + sin(x * PI) *
cos(y * PI) * x * -x * sin(x * PI)) / 2
Lars Haugseth
Total: 6.860000
%self total self wait child calls name
44.61 6.86 3.06 0.00 3.80 256
Integer#upto-1 (ruby_runtime:0}
18.95 1.30 1.30 0.00 0.00 1179648 Float#*
(ruby_runtime:0}
6.71 0.46 0.46 0.00 0.00 327680 Math#cos
(ruby_runtime:0}
5.25 0.36 0.36 0.00 0.00 393216 Float#+
(ruby_runtime:0}
4.96 0.34 0.34 0.00 0.00 327680 Math#sin
(ruby_runtime:0}
4.23 0.29 0.29 0.00 0.00 262400 Float#/
(ruby_runtime:0}
3.50 0.24 0.24 0.00 0.00 196608 Float#**
(ruby_runtime:0}
3.21 0.22 0.22 0.00 0.00 196608 String#<<
(ruby_runtime:0}
2.92 0.20 0.20 0.00 0.00 262144 Float#-@
(ruby_runtime:0}
2.33 0.16 0.16 0.00 0.00 196608 Integer#chr
(ruby_runtime:0}
1.90 0.13 0.13 0.00 0.00 196608 Float#to_i
(ruby_runtime:0}
1.46 0.10 0.10 0.00 0.00 65792 Fixnum#to_f
(ruby_runtime:0}
0.00 6.86 0.00 0.00 6.86 1 Integer#upto
(ruby_runtime:0}
0.00 6.86 0.00 0.00 6.86 1 Kernel#eval
(ruby_runtime:0}
0.00 0.00 0.00 0.00 0.00 257 Fixnum#-
(ruby_runtime:0}
0.00 6.86 0.00 0.00 6.86 1
ImageGenerator#generate_pixels (solution.rb:48}
Alex Fenton
Total: 7.800000
%self total self wait child calls name
41.15 5.90 3.21 0.00 2.69 196608 Proc#call
(ruby_runtime:0}
15.13 1.18 1.18 0.00 0.00 1179648 Float#*
(ruby_runtime:0}
12.18 7.79 0.95 0.00 6.84 256 Integer#upto
(ruby_runtime:0}
6.28 0.62 0.49 0.00 0.13 65536 Array#pack
(ruby_runtime:0}
4.23 0.33 0.33 0.00 0.00 262400 Float#/
(ruby_runtime:0}
4.10 0.32 0.32 0.00 0.00 327680 Math#cos
(ruby_runtime:0}
3.85 0.30 0.30 0.00 0.00 327680 Math#sin
(ruby_runtime:0}
3.72 0.29 0.29 0.00 0.00 262144 Float#-@
(ruby_runtime:0}
3.33 0.26 0.26 0.00 0.00 196608 Float#**
(ruby_runtime:0}
2.31 0.18 0.18 0.00 0.00 196608 Float#+
(ruby_runtime:0}
1.67 0.13 0.13 0.00 0.00 196608 Float#to_int
(ruby_runtime:0}
1.15 0.09 0.09 0.00 0.00 65794 Fixnum#to_f
(ruby_runtime:0}
0.90 0.07 0.07 0.00 0.00 65536 String#<<
(ruby_runtime:0}
0.00 7.80 0.00 0.00 7.80 1
Integer#downto (ruby_runtime:0}
0.00 7.80 0.00 0.00 7.80 1
MathsDrawing#make_image (solution.rb:74}
0.00 0.00 0.00 0.00 0.00 257 Fixnum#-
(ruby_runtime:0}
When I first ran the benchmark I noticed a discrepancy in the number
of times that various Float and Math methods were called. It turns out
that Alex Fenton's solution was computing one extra row of pixels. I
corrected this for the results. Here are the sections of code that
were used in the benchmark:
# Lars Haugseth
@pixels = ""
eval <<"."
0.upto(@height - 1) do |y_pos|
y = (y_pos.to_f / @height)
0.upto(@width - 1) do |x_pos|
x = (x_pos.to_f / @width)
@pixels << (127.99 + 127.99 * #{@red}).to_i.chr
@pixels << (127.99 + 127.99 * #{@green}).to_i.chr
@pixels << (127.99 + 127.99 * #{@blue}).to_i.chr
end
end
.
# Alex Fenton
# The string holding raw image data
data = ''
x_factor = size_x.to_f
y_factor = size_y.to_f
# Input values from the range 0 to 1, with origin in the bottom left
(size_y - 1).downto(0) do | y |
the_y = y.to_f / y_factor
0.upto(size_x - 1) do | x |
the_x = x.to_f / x_factor
red = @red.call(the_x, the_y) * 255
green = @green.call(the_x, the_y) * 255
blue = @blue.call(the_x, the_y) * 255
data << [red, green, blue].pack("CCC")
end
end
After running several several iterations Lars's code was always about
one second faster. I believe this is due to the single `eval` in place
of the multiple (196,608) `Proc#call`s. Note that this is on Ruby
1.8.6 and may have different results on 1.9.1.
No one got really crazy with performance and created a lookup table
for trigonometric functions, but that may be one way to save cycles,
especially when creating much larger images. Another possible
technique would be to use [ruby2c][3], or something like it, to create
a C method instead of using `Proc`s or `eval`.
Let us bask in the beauty of these majestic behemoths, these gentle
giants of the deep:
![Christmas box magic][4]
![spironator][5]
![winter's delight][6]
![nebulogue][7]
![crystal cavern of the paraboloids][8]
![beam and bend][9]
[1]: http://wxruby.rubyforge.org/wiki/wiki.pl
[2a]: http://rubyquiz.strd6.com/quizzes/191/image6a.png
[2b]: http://rubyquiz.strd6.com/quizzes/191/image6b.png
[3]: http://rubyforge.org/projects/ruby2c/
[4]: http://rubyquiz.strd6.com/quizzes/191/1212289356.png
[5]: http://rubyquiz.strd6.com/quizzes/191/1212289475.png
[6]: http://rubyquiz.strd6.com/quizzes/191/1212289587.png
[7]: http://rubyquiz.strd6.com/quizzes/191/1212289672.png
[8]: http://rubyquiz.strd6.com/quizzes/191/1212289788.png
[9]: http://rubyquiz.strd6.com/quizzes/191/1212289848.png
on 2009-02-17 16:20
* Daniel Moore <yahivin@gmail.com> wrote: > > No one got really crazy with performance and created a lookup table > for trigonometric functions, but that may be one way to save cycles, > especially when creating much larger images. After I posted my code here, I did some quick experimentations involving "caching" of sub-expressions not involving x as a factor by calculating those outside the inner loop, storing them in a hash and looking up the value from the hash inside the inner loop. However, in my experience it was faster to actually compute the simple expressions (Math.sin(y), y * y, etc.) than looking them up in a hash. I guess such caching could speed things up a little if one was to cache more complex expressions involving just one of the dimensions, but I deemed it too much effort for too little gain to investigate further. Thank you Daniel. -- Lars Haugseth "If anyone disagrees with anything I say, I am quite prepared not only to retract it, but also to deny under oath that I ever said it." -Tom Lehrer
Please log in before posting. Registration is free and takes only a minute.
Existing account
(Switch to SSL-encrypted connection)
NEW: Do you have a Google/GoogleMail or Yahoo account? No registration required!
Log in with Google account | Log in with Yahoo account
Log in with Google account | Log in with Yahoo account
No account? Register here.