Algorithm Help - Grid Space Calculations

[Phrogz]

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.]

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]

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

 

[Phrogz]

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]

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

 

[Phrogz]

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]

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