From: Phrogz <gavin@...>
Date: 2007-02-08T03:15:07+09:00
Subject: Algorithm Help - Grid Space Calculations

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.