[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

Algorithm Help - Grid Space Calculations

Gavin Kistner

2/7/2007 6:13:00 PM

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.
10 Answers

Eric I.

2/7/2007 6:50:00 PM

0

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

----------------
Are you interested in on-site Ruby training that uses well-designed,
real-world, hands-on exercises? http://Lea...

Martin DeMello

2/7/2007 7:25:00 PM

0

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 Kistner

2/7/2007 7:33:00 PM

0

On Feb 7, 12:25 pm, "Martin DeMello" <martindeme...@gmail.com> 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

2/7/2007 8:13:00 PM

0

On 2/8/07, Phrogz <gavin@refinery.com> 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 Kistner

2/7/2007 8:17:00 PM

0

On Feb 7, 1:13 pm, "Martin DeMello" <martindeme...@gmail.com> 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

2/7/2007 8:27:00 PM

0

On 2/8/07, Phrogz <gavin@refinery.com> wrote:
> On Feb 7, 1:13 pm, "Martin DeMello" <martindeme...@gmail.com> 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

Remysun

5/14/2012 4:57:00 AM

0

On May 13, 2:24 pm, "W/Q" <i...@email.com> wrote:

> > FRIDAY
>
> > 8-8:30 p.m. – “Whitney”
> > 8:30-9 p.m. – “Community”
> > 9-10 p.m. – “Grimm”
> > 10-11 p.m. – “Dateline NBC”

> A night that'll go nowhere fast.  We're looking at a 2.5-3.0 household
> rating.

It's a weird mix, not quite sure what it's trying to be, but the
sitcoms on Friday are a decent dare. Community fans can prove their
loyalty to the show, no longer conflicting with the hottest sitcom on
TV, and remember the magic of TGIF?

Remysun

5/14/2012 8:28:00 AM

0

On May 14, 2:48 am, "W/Q" <i...@email.com> wrote:

> It's a weird mix without synergy to maintain an audience flow
> throughout the night.  It's as if each show will have to sink or swim
> on its own without any real help it can draw on from a preceding or
> following show.  My re-do is better with Animal Practice, Community,
> Grimm and Do No Harm.  Animal Practice and Community at least share a
> similarity in their snarky leads and, of course, Grimm paired with Do
> No Harm would create a fantasy duo to round off the night, with all
> more or less appealing to the same demo that I think would likely
> stick with the network throughout the night.  As it is with Whitney
> leading off the night, it's unimaginable that its viewers have
> anything in common with those of Community while Grimm definitely has
> nothing in common with Dateline.

If they're thinking long term with Grimm, they're thinking of
inheriting the sci-fi slot once Fringe ends. Meanwhile, NBC sitcoms
are so battered that they really do need an empty night, so that means
Friday. And Dateline is a place holder, since nobody wants to
challenge that 10pm slot. Far from ideal, but you can't deny that
that's the likely logic behind the decision.

W/Q

5/14/2012 7:10:00 PM

0

On May 14, 4:27 am, Remysun <remysun2...@yahoo.com> wrote:
> On May 14, 2:48 am, "W/Q" <i...@email.com> wrote:
>
> > It's a weird mix without synergy to maintain an audience flow
> > throughout the night.  It's as if each show will have to sink or swim
> > on its own without any real help it can draw on from a preceding or
> > following show.  My re-do is better with Animal Practice, Community,
> > Grimm and Do No Harm.  Animal Practice and Community at least share a
> > similarity in their snarky leads and, of course, Grimm paired with Do
> > No Harm would create a fantasy duo to round off the night, with all
> > more or less appealing to the same demo that I think would likely
> > stick with the network throughout the night.  As it is with Whitney
> > leading off the night, it's unimaginable that its viewers have
> > anything in common with those of Community while Grimm definitely has
> > nothing in common with Dateline.
>
> If they're thinking long term with Grimm, they're thinking of
> inheriting the sci-fi slot once Fringe ends. Meanwhile, NBC sitcoms
> are so battered that they really do need an empty night, so that means
> Friday. And Dateline is a place holder, since nobody wants to
> challenge that 10pm slot.  Far from ideal, but you can't deny that
> that's the likely logic behind the decision.

I don't know if NBC has any logic in much of their decision-making
since their overall programming is so weak, including their new
upcoming shows, as to make whatever "logical" decisions practically
unrealizable in what the network would like to see happen.

As for Dateline, it's been "place-holding" that 10 pm spot since the
spring of 2008, with only Jay Leno briefly and Outlaw even more
briefly each trying, and failing, to claim it as its own. Seems that
Dateline is more of a permanent fixture than a place holder.

But I've always championed the idea of more comedies on Friday, as my
past mock skeds attest to. The problem is to find not only the right
comedies for the night, but also to surround them with the right
action series, since more dramatic ones rarely do well on the night.
And I'm not talking about getting a 2.0 demo (which Grimm struggles
mightily to get but often falls short), I'm talking about getting the
kind of household numbers and total eyeballs that CBS gets with CSI:
NY and Blue Bloods that, with luck, will bring that 2.0 demo or
better. Even Gifted Man, which the network canceled, did almost twice
as well in the non-demo vein as anything else the other networks had
to offer on Friday with its demo being not really that much better or
worse than the other shows on the night.

Used to be networks geared their shows for younger viewers on Fridays,
but now those viewers have virtually abandoned the night. Well, guess
why. Because the networks abandoned gearing their shows for younger
viewers on the night. But, I think there's the possibility that ABC
just might restructure its Friday to produce a slate of 4 sitcoms that
I kind of envision as being led off with Last Man Standing and then
followed by two new ones, The Neighbors and The Family Tools, and
finally topped off by Happy Endings in a new time slot. Standing
could vacate Tuesday, as it should, for Reba McEntire's Malibu Country
and Sarah Chalke's How to Live with Your Parents for the Rest of Your
Life, while Apartment 23 just might retain the Wednesday 9:30 spot
over Happy Endings. This, more than what NBC has laid out, would be a
true test as to whether Friday sitcoms are doable again. It'll be
interesting to see if ABC will actually do it.

Anim8rFSK

5/15/2012 1:20:00 AM

0

In article
<91fd5b5e-61f4-440f-b5d2-fc546ca5e4fe@v10g2000vbe.googlegroups.com>,
Remysun <remysun2000@yahoo.com> wrote:

> On May 13, 2:24?pm, "W/Q" <i...@email.com> wrote:
>
> > > FRIDAY
> >
> > > 8-8:30 p.m. ? ?Whitney?
> > > 8:30-9 p.m. ? ?Community?
> > > 9-10 p.m. ? ?Grimm?
> > > 10-11 p.m. ? ?Dateline NBC?
>
> > A night that'll go nowhere fast. ?We're looking at a 2.5-3.0 household
> > rating.
>
> It's a weird mix, not quite sure what it's trying to be, but the
> sitcoms on Friday are a decent dare. Community fans can prove their
> loyalty to the show, no longer conflicting with the hottest sitcom on
> TV, and remember the magic of TGIF?

It sound like the big 'F.U.' NBC gave to Gene Roddenberry 45 years ago.

--
So we're all agreed that Clod is as stupid as Charlie Sheen?