Forum: Ruby Algorithm Help - Grid Space Calculations

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
Gavin K. (Guest)
on 2007-02-07 20:15
(Received via mailing list)
I have a problem, and I'm hoping someone will find it interesting
enough to understand it and come up with a better/more direct
solution. I'd claim that I need more coffee, but I don't *drink*
coffee. The mental failings are all my own. ;)

If you've worked with a 3D modeler before, imagine an orthographic
editing camera. Behind the model a grid of lines is drawn. The camera
is rendering a particular section of the world to a window on your
screen.

As you zoom the camera in and out, the grid of lines needs to change
placement to continue representing the same spot in the world. As you
resize the window that the camera is rendering to, the placement also
needs to change.

Like Modo and unlike Maya, I want our orthographic grid to
automatically change scale as it crosses certain thresholds. If it
gets too small (the lines are too close together), I want the scale of
the grid to double - get rid of half the lines. If it gets too large
(the lines are too far apart) I want the scale of the grid to half -
draw lines in-between the existing lines. This should occur if the
user is zooming the camera in and out, or if the user is resizing the
window.[1]

Below is some Ruby code that reflects what I want to do. It's non-
ideal because it uses loops to get to the value I want. I feel that
there ought to be a simple one-line formula that calculates what I
want, using rounding or truncation or modding...but I can't quite
grasp what it should be.

The particularly complicating factor is that the answer depends on the
current grid size, since for most camera/window combinations there is
a pair of grid sizes that would satisfy the conditions. In these
cases, I want to use the grid size closest to the current grid size
(which is the same size, when possible). The last set of assertions
covers this case.

Anyone got a bright idea?

  BASE_GRID_SIZE = 40

  def grid_size( world_width, pixel_width )
    pixels_per_unit = pixel_width / world_width
    px_per_grid_line = $grid_spacing * pixels_per_unit
    while px_per_grid_line > BASE_GRID_SIZE * 2
      $grid_spacing /= 2
      px_per_grid_line /= 2
    end
    while px_per_grid_line < BASE_GRID_SIZE / 2
      $grid_spacing *= 2
      px_per_grid_line *= 2
    end
    puts "A %dcm wide camera mapped to %dpx " %
[world_width,pixel_width] +
         "will have a grid every %dcm " % [$grid_spacing] +
         "drawn every %.2f pixels, " % [px_per_grid_line] +
         "resulting in %.2f lines being drawn." % [pixel_width/
px_per_grid_line]
    $grid_spacing
  end

  require 'test/unit/assertions'
  include Test::Unit::Assertions

  begin
    # Use a global to handle overlapping legal ranges
    $grid_spacing = BASE_GRID_SIZE

    # Changing window size
    assert_equal( BASE_GRID_SIZE, grid_size( 400.0, 400 ) )
    assert_equal( BASE_GRID_SIZE*2, grid_size( 400.0, 190 ) )
    assert_equal( BASE_GRID_SIZE/2, grid_size( 400.0, 810 ) )
    assert_equal( BASE_GRID_SIZE/2, grid_size( 400.0, 1200 ) )
    assert_equal( BASE_GRID_SIZE/2, grid_size( 400.0, 1600 ) )
    assert_equal( BASE_GRID_SIZE/4, grid_size( 400.0, 1601 ) )

    # Changing camera zoom
    assert_equal( BASE_GRID_SIZE, grid_size( 420.0, 400 ) )
    assert_equal( BASE_GRID_SIZE, grid_size( 790.0, 400 ) )
    assert_equal( BASE_GRID_SIZE*2, grid_size( 810.0, 400 ) )

    # Overlapping range test
    assert_equal( BASE_GRID_SIZE*2, grid_size( 1595.0, 400 ) )
    assert_equal( BASE_GRID_SIZE*4, grid_size( 1610.0, 400 ) )
    assert_equal( BASE_GRID_SIZE*4, grid_size( 1595.0, 400 ) )
    assert_equal( BASE_GRID_SIZE*4, grid_size( 810.0, 400 ) )
    assert_equal( BASE_GRID_SIZE*2, grid_size( 790.0, 400 ) )
    assert_equal( BASE_GRID_SIZE*2, grid_size( 400.0, 400 ) )
    assert_equal( BASE_GRID_SIZE, grid_size( 399.0, 400 ) )
    assert_equal( BASE_GRID_SIZE, grid_size( 790.0, 400 ) )
  rescue Test::Unit::AssertionFailedError => e
    puts e
  end

[1] I'm not really sure I like having the window resizing change the
grid size, but for the purposes of this discussion and the code, I'm
leaving that requirement in there.
Eric I. (Guest)
on 2007-02-07 20:50
(Received via mailing list)
I haven't fully read your code other than to get a general sense of
what it is you're trying to do.  And since you double or halve the
spacing until it meets certain constraints, it looks to me like you're
ultimately trying to solve a problem like this:

    2 ** x == y

Where you know y but do not know x.  Such a problem can be solved with
logarthims.

    x * log(2) == log(y)

    x == log(y) / log(2)

Once you derive x, you can then do a ceiling, floor, round, etc.
depending on what your preference is.

So the puzzle for you is can you turn the problem you're trying to
solve into the form:

    2 ** x == y ?

For example, maybe y would be some formula involving the base grid and
40, which seems to be a key number to you?

Good luck,

Eric
Martin DeMello (Guest)
on 2007-02-07 21:26
(Received via mailing list)
Here you go:

include Math

BASE_GRID_SIZE = 40

def lg2(a)
  log(a) / log(2)
end

def grid_size( world_width, pixel_width )
  ppu = pixel_width / world_width
  factor = 2 ** lg2(ppu).ceil
  low = BASE_GRID_SIZE / factor
  high = low * 2
  $grid_spacing = ($grid_spacing - high).abs < ($grid_spacing -
low).abs ? high : low

  px_per_grid_line = $grid_spacing * ppu

  puts "A %dcm wide camera mapped to %dpx " % [world_width,pixel_width]
+
        "will have a grid every %dcm " % [$grid_spacing] +
        "drawn every %.2f pixels, " % [px_per_grid_line] +
        "resulting in %.2f lines being drawn." % [pixel_width/
px_per_grid_line]
  $grid_spacing
end

require 'test/unit/assertions'
include Test::Unit::Assertions

begin
  # Use a global to handle overlapping legal ranges
  $grid_spacing = BASE_GRID_SIZE

  # Changing window size
  assert_equal( BASE_GRID_SIZE, grid_size( 400.0, 400 ) )
  assert_equal( BASE_GRID_SIZE*2, grid_size( 400.0, 190 ) )
  assert_equal( BASE_GRID_SIZE/2, grid_size( 400.0, 810 ) )
  assert_equal( BASE_GRID_SIZE/2, grid_size( 400.0, 1200 ) )
  assert_equal( BASE_GRID_SIZE/2, grid_size( 400.0, 1600 ) )
  assert_equal( BASE_GRID_SIZE/4, grid_size( 400.0, 1601 ) )

  # Changing camera zoom
  assert_equal( BASE_GRID_SIZE, grid_size( 420.0, 400 ) )
  assert_equal( BASE_GRID_SIZE, grid_size( 790.0, 400 ) )
  assert_equal( BASE_GRID_SIZE*2, grid_size( 810.0, 400 ) )

  # Overlapping range test
  assert_equal( BASE_GRID_SIZE*2, grid_size( 1595.0, 400 ) )
  assert_equal( BASE_GRID_SIZE*4, grid_size( 1610.0, 400 ) )
  assert_equal( BASE_GRID_SIZE*4, grid_size( 1595.0, 400 ) )
  assert_equal( BASE_GRID_SIZE*4, grid_size( 810.0, 400 ) )
  assert_equal( BASE_GRID_SIZE*2, grid_size( 790.0, 400 ) )
  assert_equal( BASE_GRID_SIZE*2, grid_size( 400.0, 400 ) )
  assert_equal( BASE_GRID_SIZE, grid_size( 399.0, 400 ) )
  assert_equal( BASE_GRID_SIZE, grid_size( 790.0, 400 ) )
rescue Test::Unit::AssertionFailedError => e
  puts e
end

martin
Gavin K. (Guest)
on 2007-02-07 21:35
(Received via mailing list)
On Feb 7, 12:25 pm, "Martin DeMello" <removed_email_address@domain.invalid> 
wrote:
> Here you go:
[snip]
>     ppu = pixel_width / world_width
>     factor = 2 ** lg2(ppu).ceil
>     low = BASE_GRID_SIZE / factor
>     high = low * 2
>     $grid_spacing = ($grid_spacing-high).abs < ($grid_spacing-low).abs ? high : low
[snip]

Excellent, thanks! :)

The logarithm stuff is exactly what was needed (translating it to a
factor in particular). And even though you transcribed into Ruby what
I wrote in English with the "nearest to the current setting"
constraint, for some reason I couldn't come up with it.
Martin DeMello (Guest)
on 2007-02-07 22:13
(Received via mailing list)
On 2/8/07, Phrogz <removed_email_address@domain.invalid> wrote:
> factor in particular). And even though you transcribed into Ruby what
> I wrote in English with the "nearest to the current setting"
> constraint, for some reason I couldn't come up with it.

That was where I really missed the oft-requested min_by:

$grid_spacing = [high, low].min_by {|i| ($grid_spacing - i).abs}

but I felt defining it for that one use would be overkill :)

martin
Gavin K. (Guest)
on 2007-02-07 22:20
(Received via mailing list)
On Feb 7, 1:13 pm, "Martin DeMello" <removed_email_address@domain.invalid> 
wrote:
> That was where I really missed the oft-requested min_by:
>
> $grid_spacing = [high, low].min_by {|i| ($grid_spacing - i).abs}
>
> but I felt defining it for that one use would be overkill :)

Though it would be computationally inefficient compared to what it
could be, you could of course get the same functionality with:
[high,low].sort_by{ |i| ($grid_spacing-i).abs }[0]
Martin DeMello (Guest)
on 2007-02-07 22:27
(Received via mailing list)
On 2/8/07, Phrogz <removed_email_address@domain.invalid> wrote:
> On Feb 7, 1:13 pm, "Martin DeMello" <removed_email_address@domain.invalid> wrote:
> > That was where I really missed the oft-requested min_by:
> >
> > $grid_spacing = [high, low].min_by {|i| ($grid_spacing - i).abs}
> >
> > but I felt defining it for that one use would be overkill :)
>
> Though it would be computationally inefficient compared to what it
> could be, you could of course get the same functionality with:
> [high,low].sort_by{ |i| ($grid_spacing-i).abs }[0]

True, but it would hurt to do that :)

martin
This topic is locked and can not be replied to.