gdalgorithms-list

Re: [Algorithms] Acceleration Structures For Vertex Snapping

[Mat N. <mat...@bu...>]

On a related note, is there a way to hash two points such that they map to the same value if they are within specified distance d of each other? Obviously you can hash down to their positions quantized to a cell of d, but if the two points happen to be in two different cells but less than d apart they hash to different values.

MSN
From: Jeff Russell [mailto:je...@8m...]
Sent: Friday, November 19, 2010 2:43 PM
To: Game Development Algorithms
Subject: Re: [Algorithms] Acceleration Structures For Vertex Snapping

It's not *really* O(1), since you can have an arbitrary number of vertices in a single hash cell (worst case would be the entire mesh). Only perfect hashing would allow for O(1) worst case behavior. It's really O(n) worst case, but since the n is divided by such a large constant in practice it is still a very fast approach.
On Fri, Nov 19, 2010 at 4:31 PM, Fabian Giesen <ry...@gm...<mailto:ry...@gm...>> wrote:
On 11/19/2010 2:15 PM, Oscar Forth wrote:
> O(1) implies hash lookup is direct array index ... surely best case
> lookup is O(n * log( n ))? Or care to explain where I am going wrong on
> my thinking? Ta
Vertex snapping: Take your snapping distance d
Imagine an infinite uniform grid with cell edge length e >= 2d.
Every vertex within d units of your query vertex must be either in the
same cell or in one of the directly adjacent cells (that's 2^n cells to
check where n is your dimension).
Hash on grid cell coordinates (x,y,z) to turn the theoretical infinite
grid into a very practical hash-table :)

For vertex welding, the weld operation ensures that the number of points
in each infinite grid cell is <= some constant C(n,e/d). Size the hash
table according to the number of vertices and the expected number of
items in a cell is also a small constant. That makes the whole thing
expected O(1).

-Fabian

------------------------------------------------------------------------------
Beautiful is writing same markup. Internet Explorer 9 supports
standards for HTML5, CSS3, SVG 1.1,  ECMAScript5, and DOM L2 & L3.
Spend less time writing and  rewriting code and more time creating great
experiences on the web. Be a part of the beta today
http://p.sf.net/sfu/msIE9-sfdev2dev
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...<mailto:GDA...@li...>
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list



--
Jeff Russell
Engineer, 8monkey Labs
www.8monkeylabs.com<http://www.8monkeylabs.com>

Re: [Algorithms] Acceleration Structures For Vertex Snapping

[Fabian G. <ry...@gm...>]

On 11/19/2010 2:43 PM, Jeff Russell wrote:
> It's not *really* O(1), since you can have an arbitrary number of
> vertices in a single hash cell (worst case would be the entire mesh).
> Only perfect hashing would allow for O(1) worst case behavior.

What do you mean by "not *really* O(1)"? Big O notation just means we're 
talking about asymptotic complexity, it doesn't have to be worst-case 
(hence "expected O(1)").

 > It's
 > really O(n) worst case, but since the n is divided by such a large
 > constant in practice it is still a very fast approach.

No, that's not true. Hash tables are fast in practice because they do a 
small number of reasonably fast operations in the average case, not 
because they do a large number of operations in a magically ultra-fast 
fashion (which would be the O(N) with tiny constant that you decribe). 
Their worst-case is definitely linear and the constant isn't tiny as 
everyone who's ever used a bad hash function knows :). Worst-case and 
average-case analysis are just different things.

-Fabian

Re: [Algorithms] Acceleration Structures For Vertex Snapping

[Sebastian S. <seb...@gm...>]

On Fri, Nov 19, 2010 at 10:43 PM, Jeff Russell <je...@8m...>wrote:

> It's not *really* O(1), since you can have an arbitrary number of vertices
> in a single hash cell (worst case would be the entire mesh). Only perfect
> hashing would allow for O(1) worst case behavior. It's really O(n) worst
> case, but since the n is divided by such a large constant in practice it is
> still a very fast approach.
>
>
If we're talking about welding (which was not the original question, as I
understand it). Then you can probably modify the distance threshold criteria
slightly so that it's okay to weld with any vertex in the 3x3 neighbourhood
of current cell in the appropriately sized grid. Then you'll only ever get
at most one vertex per cell (the second, etc., will be discarded due to
welding).

-- 
Sebastian Sylvan

Re: [Algorithms] Acceleration Structures For Vertex Snapping

[Jeff R. <je...@8m...>]

It's not *really* O(1), since you can have an arbitrary number of vertices
in a single hash cell (worst case would be the entire mesh). Only perfect
hashing would allow for O(1) worst case behavior. It's really O(n) worst
case, but since the n is divided by such a large constant in practice it is
still a very fast approach.

On Fri, Nov 19, 2010 at 4:31 PM, Fabian Giesen <ry...@gm...> wrote:

> On 11/19/2010 2:15 PM, Oscar Forth wrote:
> > O(1) implies hash lookup is direct array index ... surely best case
> > lookup is O(n * log( n ))? Or care to explain where I am going wrong on
> > my thinking? Ta
>
> Vertex snapping: Take your snapping distance d
> Imagine an infinite uniform grid with cell edge length e >= 2d.
> Every vertex within d units of your query vertex must be either in the
> same cell or in one of the directly adjacent cells (that's 2^n cells to
> check where n is your dimension).
> Hash on grid cell coordinates (x,y,z) to turn the theoretical infinite
> grid into a very practical hash-table :)
>
> For vertex welding, the weld operation ensures that the number of points
> in each infinite grid cell is <= some constant C(n,e/d). Size the hash
> table according to the number of vertices and the expected number of
> items in a cell is also a small constant. That makes the whole thing
> expected O(1).
>
> -Fabian
>
>
> ------------------------------------------------------------------------------
> Beautiful is writing same markup. Internet Explorer 9 supports
> standards for HTML5, CSS3, SVG 1.1,  ECMAScript5, and DOM L2 & L3.
> Spend less time writing and  rewriting code and more time creating great
> experiences on the web. Be a part of the beta today
> http://p.sf.net/sfu/msIE9-sfdev2dev
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>



-- 
Jeff Russell
Engineer, 8monkey Labs
www.8monkeylabs.com

Re: [Algorithms] Acceleration Structures For Vertex Snapping

[Fabian G. <ry...@gm...>]

On 11/19/2010 2:15 PM, Oscar Forth wrote:
> O(1) implies hash lookup is direct array index ... surely best case
> lookup is O(n * log( n ))? Or care to explain where I am going wrong on
> my thinking? Ta

Vertex snapping: Take your snapping distance d
Imagine an infinite uniform grid with cell edge length e >= 2d.
Every vertex within d units of your query vertex must be either in the 
same cell or in one of the directly adjacent cells (that's 2^n cells to 
check where n is your dimension).
Hash on grid cell coordinates (x,y,z) to turn the theoretical infinite 
grid into a very practical hash-table :)

For vertex welding, the weld operation ensures that the number of points 
in each infinite grid cell is <= some constant C(n,e/d). Size the hash 
table according to the number of vertices and the expected number of 
items in a cell is also a small constant. That makes the whole thing 
expected O(1).

-Fabian

Re: [Algorithms] Acceleration Structures For Vertex Snapping

[Fabian G. <ry...@gm...>]

On 11/19/2010 1:31 PM, chr...@pl... wrote:
>
> Sebastian Sylvan wrote:
>>> I'm working on the vertex snapping feature for our level editor.
>>>
>>> So, in vertex snapping mode all translates are snapped to the
>>> nearest vertex on screen.
>>> [...]
>>
>> You could try some sort of BVH (e.g. an AABB tree) in world space,
>
> Vertex snapping is the same as vertex welding, for which
> a spatial hash gives you O(1) operations for a single vertex.

To snap based on screen-space coordinates, you either need to use a 2D 
hash that you rebuild every time the camera position/data changes, or 
visit all hash cells along a "fat ray" (intersection of a cone with your 
partitioning grid - messy and not O(1)).

2D hash is pretty damn practical though. You build it the first time 
it's needed after a camera position change (it's a fairly trivial 
addition to the brute-force solution and doesn't make it much more 
expensive), and then you can use it for subsequent frames. As long as 
you're not moving the camera every frame while moving a vertex, you're fine.

-Fabian

Re: [Algorithms] Acceleration Structures For Vertex Snapping

[Oscar F. <os...@tr...>]

O(1) implies hash lookup is direct array index ... surely best case lookup
is O(n * log( n ))? Or care to explain where I am going wrong on my
thinking? Ta
On 19 Nov 2010 22:09, <chr...@pl...> wrote:
>
> Sebastian Sylvan wrote:
>>> I'm working on the vertex snapping feature for our level editor.
>>>
>>> So, in vertex snapping mode all translates are snapped to the
>>> nearest vertex on screen.
>>> [...]
>>
>> You could try some sort of BVH (e.g. an AABB tree) in world space,
>
> Vertex snapping is the same as vertex welding, for which
> a spatial hash gives you O(1) operations for a single vertex.
>
>
> Christer Ericson, Director of Tools and Technology
> Sony Computer Entertainment, Santa Monica
>
>
>
------------------------------------------------------------------------------
> Beautiful is writing same markup. Internet Explorer 9 supports
> standards for HTML5, CSS3, SVG 1.1, ECMAScript5, and DOM L2 & L3.
> Spend less time writing and rewriting code and more time creating great
> experiences on the web. Be a part of the beta today
> http://p.sf.net/sfu/msIE9-sfdev2dev
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] Acceleration Structures For Vertex Snapping

[<chr...@pl...>]

Sebastian Sylvan wrote:
>> I'm working on the vertex snapping feature for our level editor.
>>
>> So, in vertex snapping mode all translates are snapped to the
>> nearest vertex on screen.
>> [...]
>
> You could try some sort of BVH (e.g. an AABB tree) in world space,

Vertex snapping is the same as vertex welding, for which
a spatial hash gives you O(1) operations for a single vertex.


Christer Ericson, Director of Tools and Technology
Sony Computer Entertainment, Santa Monica

Re: [Algorithms] Acceleration Structures For Vertex Snapping

[Sebastian S. <seb...@gm...>]

On Fri, Nov 19, 2010 at 1:46 PM, Alexander Shafranov <sha...@gm...>wrote:

> Hi guys,
>
> I'm working on the vertex snapping feature for our level editor.
>
> So, in vertex snapping mode all translates are snapped to the nearest
> vertex on screen.
>
> Brute force approach would be something like --
>
> - project all vertices to screen-space
> - find closest vertex to object's projected pivot
>
> I know, that nearest point query is an O(log N) problem with kd-tree.
> But, building kd-tree for mesh vertices doesn't help here, because the
> query is 'nearest point in screen-space'.
> Kd-tree can be built for a set of projected (2d) vertices, it doesn't sound
> great though, since tree has to be rebuilt on any camera moves.
>
> What would you recommend ?
>
> Or maybe I'm overengineering here and something more brute force will work
> good enough.
>
>
You could try some sort of BVH (e.g. an AABB tree) in world space, and then
just send a ray through it from the eye to the pivot point, and find the
nearest point to the ray by descending the tree. This means you don't have
to update the acceleration structure when the camera moves. And BVHs are
easy enough to update incrementally as objects themselves move, which is
nice.

As for the actual query, the first approach I can think of right now for an
AABB tree is based on the observation that you know that there's at least
one point on each /face/ of each AABB in the tree (assuming your AABBs were
built correctly), so for each child in a node find the furthest point on the
closest face, w.r.t. the ray. That gives you an upper bound of how far the
nearest point is, which you can then use to cull what children you need to
visit (by discarding any boxes whose closest point is further than this
distance).

I'll also plug my talk on R-trees from last GDC too (slides should be on
their website), which basically is just a very cache friendly way of
organising AABB trees. It's not clear that PCs have severe enough cache
penalties to motivate them, but it turned out (somewhat surprisingly to me)
that the construction logic for high-branching-factor trees ended up being
much simpler/robust than binary ones (esp. if you need to insert new objects
dynamically, which you frequently do), so even if you're not on an in-order
CPU with slow memory, it might still be worthwhile for simplicity reasons.
-- 
Sebastian Sylvan

Re: [Algorithms] Acceleration Structures For Vertex Snapping

[Alexander S. <sha...@gm...>]

Hi guys,

Thanks a lot for your suggestions !

I'm now assured to do a 'brute force' approach.

Cheers,
Alexander.

On Fri, Nov 19, 2010 at 8:08 PM, Nicholas Francis <nic...@un...>wrote:

> As far as I remember, what we did in Unity for our vertex snapping is to
> find the object under the mouse pointer, then snap to nearest vertex in that
> (by just going through the vertices in the model and finding the nearest in
> O(n) time. That drastically reduces the dataset :)
>
> It's cheating, really - but there's a fair chance that if I'm
> vertexsnapping and dragging something on to a table, then it's because I
> want to snap the object to the table, and not to the floor below (or even
> worse: to some vertex that's in another room through 5 walls 3 miles away).
>
> Either way: unless you're very resource constrained, I'd say you should do
> some broadphase culling (do normal cull-for-rendering in 10 pixels around
> the mouse) - then you shouldn't need to be very clever about finding the
> actual vertex.
>
> This approach also has the look-and-feel advantage that you won't snap an
> object to very far away in screen space (which looks jarring and feels
> wrong). It's a bit like docking toolbar windows in photoshop: you want them
> to snap somewhat, but if the snapping is too 'eager', it'll feel pretty bad.
>
> Cheers,
> Nicholas Francis
> main editor dude, Unity.
>
>
> On Nov 19, 2010, at 2:46 PM, Alexander Shafranov wrote:
>
> >
> > I know, that nearest point query is an O(log N) problem with kd-tree.
> > But, building kd-tree for mesh vertices doesn't help here, because the
> query is 'nearest point in screen-space'.
> > Kd-tree can be built for a set of projected (2d) vertices, it doesn't
> sound great though, since tree has to be rebuilt on any camera moves.
> >
> > What would you recommend ?
>
>
>
> ------------------------------------------------------------------------------
> Beautiful is writing same markup. Internet Explorer 9 supports
> standards for HTML5, CSS3, SVG 1.1,  ECMAScript5, and DOM L2 & L3.
> Spend less time writing and  rewriting code and more time creating great
> experiences on the web. Be a part of the beta today
> http://p.sf.net/sfu/msIE9-sfdev2dev
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

Re: [Algorithms] Acceleration Structures For Vertex Snapping

[Nicholas F. <nic...@un...>]

As far as I remember, what we did in Unity for our vertex snapping is to find the object under the mouse pointer, then snap to nearest vertex in that (by just going through the vertices in the model and finding the nearest in O(n) time. That drastically reduces the dataset :)

It's cheating, really - but there's a fair chance that if I'm vertexsnapping and dragging something on to a table, then it's because I want to snap the object to the table, and not to the floor below (or even worse: to some vertex that's in another room through 5 walls 3 miles away).

Either way: unless you're very resource constrained, I'd say you should do some broadphase culling (do normal cull-for-rendering in 10 pixels around the mouse) - then you shouldn't need to be very clever about finding the actual vertex. 

This approach also has the look-and-feel advantage that you won't snap an object to very far away in screen space (which looks jarring and feels wrong). It's a bit like docking toolbar windows in photoshop: you want them to snap somewhat, but if the snapping is too 'eager', it'll feel pretty bad.

Cheers,
Nicholas Francis
main editor dude, Unity.


On Nov 19, 2010, at 2:46 PM, Alexander Shafranov wrote:

> 
> I know, that nearest point query is an O(log N) problem with kd-tree.
> But, building kd-tree for mesh vertices doesn't help here, because the query is 'nearest point in screen-space'.
> Kd-tree can be built for a set of projected (2d) vertices, it doesn't sound great though, since tree has to be rebuilt on any camera moves.
> 
> What would you recommend ?

Re: [Algorithms] Acceleration Structures For Vertex Snapping

[Chris G. <cg...@va...>]

If you are optimizing for development time, and you only do this once in response to a user action (meaning you don't need to be any faster than 18ms or so), don't discount a brute force sequential scan.
If your point data is stored in a memory/simd friendly format, you can perform a ridiculous number of point comparison tests per second on a modern multicore processor. If you have easy threading primitives in your system, it's a trivial operation to thread as well.

If you are going to use an auxiliary data structure to accelerate this operation, you'll have to keep it incrementally updated, since if you built the data structure every time you snapped, you'd have to examine all the points anyway to build it.

If you do have such a large number of points or need to do this operation for many points per mouse-event, you want to optimize it for cache layout and access pattern - it takes much longer to fetch the point position from DRAM than it does to perform the distance^2 calculation, so you don't want to swallow up all your memory bandwidth with pointers. For example, if using a kd-tree, you don't want your leaf nodes to be individual points; you want them to be cache-aligned simd arrays of points.




From: Alexander Shafranov [mailto:sha...@gm...]
Sent: Friday, November 19, 2010 5:46 AM
To: Game Development Algorithms
Subject: [Algorithms] Acceleration Structures For Vertex Snapping

Hi guys,

I'm working on the vertex snapping feature for our level editor.

So, in vertex snapping mode all translates are snapped to the nearest vertex on screen.

Brute force approach would be something like --

- project all vertices to screen-space
- find closest vertex to object's projected pivot

I know, that nearest point query is an O(log N) problem with kd-tree.
But, building kd-tree for mesh vertices doesn't help here, because the query is 'nearest point in screen-space'.
Kd-tree can be built for a set of projected (2d) vertices, it doesn't sound great though, since tree has to be rebuilt on any camera moves.

What would you recommend ?

Or maybe I'm overengineering here and something more brute force will work good enough.

Cheers,
Alex.

[Algorithms] Acceleration Structures For Vertex Snapping

[Alexander S. <sha...@gm...>]

Hi guys,

I'm working on the vertex snapping feature for our level editor.

So, in vertex snapping mode all translates are snapped to the nearest vertex
on screen.

Brute force approach would be something like --

- project all vertices to screen-space
- find closest vertex to object's projected pivot

I know, that nearest point query is an O(log N) problem with kd-tree.
But, building kd-tree for mesh vertices doesn't help here, because the query
is 'nearest point in screen-space'.
Kd-tree can be built for a set of projected (2d) vertices, it doesn't sound
great though, since tree has to be rebuilt on any camera moves.

What would you recommend ?

Or maybe I'm overengineering here and something more brute force will work
good enough.

Cheers,
Alex.

Re: [Algorithms] Directx9 ambient occlusion

[Fabian G. <ry...@gm...>]

On 11/9/2010 9:40 AM, Jeff Gooloolie wrote:
> I am making a dx9 ao shader.
>
> I have the ao greyscale image in a texture, and the rendered scene in
> the backbuffer.
>
> What blendmodes (dx9 fixed function pipeline) would I need to multiply
> the ao texture against the backbuffer.
>
> something like this : backbuffer=backbuffer*aotexture
>
> I currently have the following, but it is not blending with the backbuffer.
>
> gRender->SetRenderState(D3DRS_ALPHABLENDENABLE,TRUE);
> gRender->SetRenderState(D3DRS_SRCBLEND, D3DBLEND_ZERO);
> gRender->SetRenderState(D3DRS_DESTBLEND, D3DBLEND_SRCCOLOR);

This blend setup looks right for what you're trying to do.

> gRender->SetTextureStageState( 0, D3DTSS_COLOROP, D3DTOP_MODULATE );
> gRender->SetTextureStageState( 0, D3DTSS_COLORARG1, D3DTA_TEXTURE );
> gRender->SetTextureStageState( 0, D3DTSS_COLORARG2, D3DTA_DIFFUSE );
> gRender->SetTextureStageState( 0, D3DTSS_ALPHAOP, D3DTOP_SELECTARG2 );
> gRender->SetTextureStageState( 0, D3DTSS_ALPHAARG2, D3DTA_DIFFUSE );

Did you double-check whether the diffuse colors are set up correctly? 
Also, what is the effect you're seeing? If you're only using texture 
stage 0, did you remember to disable stage 1 (which also auto-disables 
all following ones)?

> Is it even possible to blend a texture with the existing backbuffer?

Yes, certainly - way back before even double-texturing texture hardware, 
alpha blending was the *only* way to do this.

This is not really an algorithmic question though - consider asking such 
questions on the directxdev mailing list.

Cheers,
-Fabian

[Algorithms] Directx9 ambient occlusion

[Jeff G. <jef...@ho...>]

I am making a dx9 ao shader.
 
I have the ao greyscale image in a texture, and the rendered scene in the backbuffer.
 
What blendmodes (dx9 fixed function pipeline) would I need to multiply the ao texture against the backbuffer. 
 
something like this : backbuffer=backbuffer*aotexture
 
I currently have the following, but it is not blending with the backbuffer.
 
gRender->SetRenderState(D3DRS_ALPHABLENDENABLE,TRUE);
gRender->SetRenderState(D3DRS_SRCBLEND, D3DBLEND_ZERO);
gRender->SetRenderState(D3DRS_DESTBLEND, D3DBLEND_SRCCOLOR);
gRender->SetTextureStageState( 0, D3DTSS_COLOROP,   D3DTOP_MODULATE );
gRender->SetTextureStageState( 0, D3DTSS_COLORARG1, D3DTA_TEXTURE );
gRender->SetTextureStageState( 0, D3DTSS_COLORARG2, D3DTA_DIFFUSE );
gRender->SetTextureStageState( 0, D3DTSS_ALPHAOP,   D3DTOP_SELECTARG2 );
gRender->SetTextureStageState( 0, D3DTSS_ALPHAARG2, D3DTA_DIFFUSE );

Is it even possible to blend a texture with the existing backbuffer?
 
 
Thanks
  		 	   		  

Re: [Algorithms] MMO Server Side

[Jon W. <jw...@gm...>]

Re: DarkStar
My experience is that DarkStar never reached its potential, for a few
reasons.
One was the "everything's a connected mesh of objects" problem, which means
that locking turns out to be more global than you'd want.
The second is that it never scaled beyond a single node -- adding nodes made
it *slower*.
The third is that the "potential" was always hyped in the marketing, and
always years and years ahead of actual delivery (and still is).

Re: What language/framework to use
Which language you use doesn't matter much. How you use that language is
much more important.

Re: Where you're at in designing your massive system
When you say "I want to access values of the other connections," it makes it
sound as if you don't have your data architecture and consistency model down
yet. You need to first decide what kinds of data is owned where, how out of
data it is allowed to be at what point at any one time, what kind of
connection quality you can require from your clients, how many consistency
classes you'll need (with ranges from "always synchronously ACID backed into
database" all the way to "ephemerally synthesized on the client")

Once you have all that, you can start figuring out how to partition the
simulation and other operations that go server-side. For example, if
locality of space is most important, then you'd probably partition all
services for a certain geographic area into a single physical node. If
locality of processing is more important, then perhaps you'll put all things
about a certain subsystem on a specific node.

Re: What I/we ended up doing
I've spent the last year writing a massively scaled system in Erlang, and
while it was alien as all get out to start out with, it's very clear that
it's a system that has been used in production for large, distributed
systems. It's not a toy, like many other pretenders, and it stands up to the
pressure when you do real things with it. You might want to look at the
following article for starting out:

http://www.metabrew.com/article/a-million-user-comet-application-with-mochiweb-part-1

If you use C++, then I suggest using boost::asio for the threading and async
networking/IO bit.

Sincerely,

jw


--
Americans might object: there is no way we would sacrifice our living
standards for the benefit of people in the rest of the world. Nevertheless,
whether we get there willingly or not, we shall soon have lower consumption
rates, because our present rates are unsustainable.



On Wed, Oct 13, 2010 at 3:33 PM, Hasse Schougaard <
has...@gm...> wrote:

> Project DarkStar/RedDwarf might be a starting point to get ideas;
>
> http://www.reddwarfserver.org/?q=content/open-source-online-gaming-universe
>
> Cheers,
> Hasse
>
>
> ------------------------------------------------------------------------------
> Beautiful is writing same markup. Internet Explorer 9 supports
> standards for HTML5, CSS3, SVG 1.1,  ECMAScript5, and DOM L2 & L3.
> Spend less time writing and  rewriting code and more time creating great
> experiences on the web. Be a part of the beta today.
> http://p.sf.net/sfu/beautyoftheweb
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

Re: [Algorithms] MMO Server Side

[Hasse S. <has...@gm...>]

Project DarkStar/RedDwarf might be a starting point to get ideas;

http://www.reddwarfserver.org/?q=content/open-source-online-gaming-universe

Cheers,
Hasse

Re: [Algorithms] MMO Server Side

[Stefan S. <kef...@gm...>]

  My preference would be lua + zmq.

www.lua.org
www.zeromq.org

On 2010-10-12 16:58, Jonathan Hickman wrote:
> I intend to create a server side application to handle incoming connection
> requests.  I want the server side AI (non-cut scenes) to be a local
> connection on the server.  What programming languages do you recommend
> (preferrably on a Linux based machine, but I am open minded) for handling
> these 'telnet' type connections to receive commands from the client?  Do you
> know of any existing frameworks for this that are capable of handling a
> numerous number of connections?  I would be able to separate the number of
> connections based on region (and therefore separate the servers) within the
> game (which would all access a centralized database), but I want something
> where each zone of the game can handle at least 100 player characters and
> the enemy NPCs would connect locally.  The difficult part is that I would
> need each connection to be able to access many variables of the other
> connections or to somehow share information to report back player locations,
> orientation, customizations, current animations, etc. for the client side.
> I am only accustomed to each connection being entirely separate and unique.
>
> Have any of you seen an implementation of this that can be used as an
> example?
>
> Jonathan Hickman
>
>
>
> ------------------------------------------------------------------------------
> Beautiful is writing same markup. Internet Explorer 9 supports
> standards for HTML5, CSS3, SVG 1.1,  ECMAScript5, and DOM L2&  L3.
> Spend less time writing and  rewriting code and more time creating great
> experiences on the web. Be a part of the beta today.
> http://p.sf.net/sfu/beautyoftheweb
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

[Algorithms] MMO Server Side

[Jonathan H. <web...@cl...>]

I intend to create a server side application to handle incoming connection
requests.  I want the server side AI (non-cut scenes) to be a local
connection on the server.  What programming languages do you recommend
(preferrably on a Linux based machine, but I am open minded) for handling
these 'telnet' type connections to receive commands from the client?  Do you
know of any existing frameworks for this that are capable of handling a
numerous number of connections?  I would be able to separate the number of
connections based on region (and therefore separate the servers) within the
game (which would all access a centralized database), but I want something
where each zone of the game can handle at least 100 player characters and
the enemy NPCs would connect locally.  The difficult part is that I would
need each connection to be able to access many variables of the other
connections or to somehow share information to report back player locations,
orientation, customizations, current animations, etc. for the client side.
I am only accustomed to each connection being entirely separate and unique.

Have any of you seen an implementation of this that can be used as an
example?

Jonathan Hickman

Re: [Algorithms] Filtering

[Adrian B. <ad...@gm...>]

FYI, DirectX 11 claims: "Require 8-bits of subtexel and sub-mip
precision on texture filtering"

It doesn't appear to say anything about precision of the resulting
color.  I would think subtexel precision usefulness would be at least
somewhat coupled to output precision, but maybe not.

Cheers,
Adrian

On Fri, Oct 1, 2010 at 1:42 PM, Tibor Klajnscek
<tib...@gm...> wrote:
>  Just wanted to point something out - now that you know it won't work
> it probably makes sense to switch to a float32 texture and still do the
> filtering manually... you'll at least save the pack/unpack instructions :)
>
> - Tibor
>
> On 10/1/2010 9:51 PM, Andreas Brinck wrote:
>> Hi Ola,
>>
>> unfortunately the floating point textures on the platform I'm working
>> on don't support bilinear filtering (this is the reason why I stored
>> the value in an RGB-texture to begin with).
>>
>> /Andreas
>>
>> P.S. Got your Ph.D yet?
>>
>> On Fri, Oct 1, 2010 at 8:12 PM, Ola Olsson<ola...@gm...>  wrote:
>>> While we're throwing ideas around, why not try using a float texture and see
>>> if it produces the same error?
>>>
>>> .ola
>>>
>>> P.S.
>>>   Hi Andreas :)
>>>
>>> ----- Original Message -----
>>> From: "Nathaniel Hoffman"<na...@io...>
>>> To: "Game Development Algorithms"<gda...@li...>
>>> Sent: Friday, October 01, 2010 7:59 PM
>>> Subject: Re: [Algorithms] Filtering
>>>
>>>
>>>> Didn't the newer NVIDIA GPUs fix this?
>>>>
>>>>> You guessed right. The loss of precision is in the texture units.
>>>>> Unfortunately, 8 bit components are filtered to 8 bit results (even
>>>>> though
>>>>> they show up as floating point values in the shader). This is true for
>>>>> nvidia gpus for sure and probably all other gpus.
>>>>>
>>>>> -mike
>>>>>    ----- Original Message -----
>>>>>    From: Stefan Sandberg
>>>>>    To: Game Development Algorithms
>>>>>    Sent: Friday, October 01, 2010 1:45 AM
>>>>>    Subject: Re: [Algorithms] Filtering
>>>>>
>>>>>
>>>>>    Assuming you're after precision, what's wrong with doing it manually?
>>>>> :)
>>>>>    If performance is what you're after, and you're working on textures as
>>>>> they were intended(ie, game textures or video or something like that,
>>>>> not 'data'), you could separate contrast&  color separately, keeping
>>>>> high contrast resolution, and downsampled color, and
>>>>>    you'd save both bandwidth and instr.
>>>>>    If you simply want to know 'why', I'm guessing loss of precision in the
>>>>> tex units?
>>>>>    You've already ruled out shader precision from your own manual
>>>>> filtering, so doesn't leave much else, imo..
>>>>>    Other than manipulating the data you're working on, which is the only
>>>>> thing you -can- change I guess, I cant really see a solution,
>>>>>    but far greater minds linger here than mine, so hold on for what I
>>>>> assume will be a lengthy description of floating point math as
>>>>>    it is implemented in modern gpu's :)
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>    On Fri, Oct 1, 2010 at 9:57 AM, Andreas Brinck
>>>>> <and...@gm...>  wrote:
>>>>>
>>>>>      Hi,
>>>>>
>>>>>      I have a texture in which I use the R, G and B channel to store a
>>>>>      value in the [0, 1] range with very high precision. The value is
>>>>>      extracted like this in the (Cg) shader:
>>>>>
>>>>>      float
>>>>>      extractValue(float2 pos) {
>>>>>         float4 temp = tex2D(buffer, pos);
>>>>>         return (temp.x * 16711680.0 + temp.y * 65280.0 + temp.z * 255.0) *
>>>>>      (1.0 / 16777215.0);
>>>>>      }
>>>>>
>>>>>      I now want to sample this value with bilinear filtering but when I do
>>>>>      this I don't get a correct result. If I do the filtering manually
>>>>> like
>>>>>      this:
>>>>>
>>>>>      float
>>>>>      sampleValue(float2 pos) {
>>>>>             float2 ipos = floor(pos);
>>>>>             float2 fracs = pos - ipos;
>>>>>             float d0 = extractValue(ipos);
>>>>>             float d1 = extractValue(ipos + float2(1, 0));
>>>>>             float d2 = extractValue(ipos + float2(0, 1));
>>>>>             float d3 = extractValue(ipos + float2(1, 1));
>>>>>             return lerp(lerp(d0, d1, fracs.x), lerp(d2, d3, fracs.x),
>>>>> fracs.y);
>>>>>      }
>>>>>
>>>>>      everything works as expected. The values in the buffer can be seen as
>>>>>      a linear combination of three constants:
>>>>>
>>>>>      value = (C0 * r + C1 * g + C2 * b)
>>>>>
>>>>>      If we use the built in texture filtering we should get the following
>>>>>      if we sample somewhere between two texels: {r0, g0, b0} and {r1, g1,
>>>>>      b1}. For simplicity we just look at filtering along one axis:
>>>>>
>>>>>      filtered value = lerp(r0, r1, t) * C0 + lerp(g0, g1, t) * C1 +
>>>>>      lerp(b0, b1, t) * C2;
>>>>>
>>>>>      Doing the filtering manually:
>>>>>
>>>>>      filtered value = lerp(r0 * C0 + b0 * C1 + g0 * C2, r1 * C0 + g1 * C1
>>>>> +
>>>>>      b1 * C2, t)  =
>>>>>                        = (r0 * C0 + b0 * C1 + g0 * C2) * (1 - t) + (r1 *
>>>>>      C0 + g1 * C1 + b1 * C2) * t =
>>>>>                        = (r0 * C0) * (1 - t) + (r1 * C0) * t + ... =
>>>>>                        = lerp(r0, r1, t) * C0 + ...
>>>>>
>>>>>      So in the world of non floating point numbers these two should be
>>>>>      equivalent right?
>>>>>
>>>>>      My theory is that the error is caused by an unfortunate order of
>>>>>      floating point operations. I've tried variations like:
>>>>>
>>>>>      (temp.x * (16711680.0 / 16777215.0) + temp.y * (65280.0/16777215.0) +
>>>>>      temp.z * (255.0/16777215.0))
>>>>>
>>>>>      and
>>>>>
>>>>>      (((temp.x * 256.0 + temp.y) * 256.0 + temp.z) * 255.0) * (1.0 /
>>>>> 16777215.0)
>>>>>
>>>>>      but all exhibit the same problem. What do you think; is it possible
>>>>> to
>>>>>      solve this problem?
>>>>>
>>>>>      Regards Andreas
>>>>>
>>>>>      ------------------------------------------------------------------------------
>>>>>      Start uncovering the many advantages of virtual appliances
>>>>>      and start using them to simplify application deployment and
>>>>>      accelerate your shift to cloud computing.
>>>>>      http://p.sf.net/sfu/novell-sfdev2dev
>>>>>      _______________________________________________
>>>>>      GDAlgorithms-list mailing list
>>>>>      GDA...@li...
>>>>>      https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>>>>      Archives:
>>>>>
>>>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> ------------------------------------------------------------------------------
>>>>>
>>>>>
>>>>>    ------------------------------------------------------------------------------
>>>>>    Start uncovering the many advantages of virtual appliances
>>>>>    and start using them to simplify application deployment and
>>>>>    accelerate your shift to cloud computing.
>>>>>    http://p.sf.net/sfu/novell-sfdev2dev
>>>>>
>>>>>
>>>>> ------------------------------------------------------------------------------
>>>>>
>>>>>
>>>>>    _______________________________________________
>>>>>    GDAlgorithms-list mailing list
>>>>>    GDA...@li...
>>>>>    https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>>>>    Archives:
>>>>>
>>>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list------------------------------------------------------------------------------
>>>>> Start uncovering the many advantages of virtual appliances
>>>>> and start using them to simplify application deployment and
>>>>> accelerate your shift to cloud computing.
>>>>> http://p.sf.net/sfu/novell-sfdev2dev_______________________________________________
>>>>> GDAlgorithms-list mailing list
>>>>> GDA...@li...
>>>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>>>> Archives:
>>>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>>>
>>>>
>>>> ------------------------------------------------------------------------------
>>>> Start uncovering the many advantages of virtual appliances
>>>> and start using them to simplify application deployment and
>>>> accelerate your shift to cloud computing.
>>>> http://p.sf.net/sfu/novell-sfdev2dev
>>>> _______________________________________________
>>>> GDAlgorithms-list mailing list
>>>> GDA...@li...
>>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>>> Archives:
>>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>>
>>> ------------------------------------------------------------------------------
>>> Start uncovering the many advantages of virtual appliances
>>> and start using them to simplify application deployment and
>>> accelerate your shift to cloud computing.
>>> http://p.sf.net/sfu/novell-sfdev2dev
>>> _______________________________________________
>>> GDAlgorithms-list mailing list
>>> GDA...@li...
>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>> Archives:
>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>>
>> ------------------------------------------------------------------------------
>> Start uncovering the many advantages of virtual appliances
>> and start using them to simplify application deployment and
>> accelerate your shift to cloud computing.
>> http://p.sf.net/sfu/novell-sfdev2dev
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDA...@li...
>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> Archives:
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>
>
> ------------------------------------------------------------------------------
> Start uncovering the many advantages of virtual appliances
> and start using them to simplify application deployment and
> accelerate your shift to cloud computing.
> http://p.sf.net/sfu/novell-sfdev2dev
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

Re: [Algorithms] Filtering

[Tibor K. <tib...@gm...>]

  Just wanted to point something out - now that you know it won't work 
it probably makes sense to switch to a float32 texture and still do the 
filtering manually... you'll at least save the pack/unpack instructions :)

- Tibor

On 10/1/2010 9:51 PM, Andreas Brinck wrote:
> Hi Ola,
>
> unfortunately the floating point textures on the platform I'm working
> on don't support bilinear filtering (this is the reason why I stored
> the value in an RGB-texture to begin with).
>
> /Andreas
>
> P.S. Got your Ph.D yet?
>
> On Fri, Oct 1, 2010 at 8:12 PM, Ola Olsson<ola...@gm...>  wrote:
>> While we're throwing ideas around, why not try using a float texture and see
>> if it produces the same error?
>>
>> .ola
>>
>> P.S.
>>   Hi Andreas :)
>>
>> ----- Original Message -----
>> From: "Nathaniel Hoffman"<na...@io...>
>> To: "Game Development Algorithms"<gda...@li...>
>> Sent: Friday, October 01, 2010 7:59 PM
>> Subject: Re: [Algorithms] Filtering
>>
>>
>>> Didn't the newer NVIDIA GPUs fix this?
>>>
>>>> You guessed right. The loss of precision is in the texture units.
>>>> Unfortunately, 8 bit components are filtered to 8 bit results (even
>>>> though
>>>> they show up as floating point values in the shader). This is true for
>>>> nvidia gpus for sure and probably all other gpus.
>>>>
>>>> -mike
>>>>    ----- Original Message -----
>>>>    From: Stefan Sandberg
>>>>    To: Game Development Algorithms
>>>>    Sent: Friday, October 01, 2010 1:45 AM
>>>>    Subject: Re: [Algorithms] Filtering
>>>>
>>>>
>>>>    Assuming you're after precision, what's wrong with doing it manually?
>>>> :)
>>>>    If performance is what you're after, and you're working on textures as
>>>> they were intended(ie, game textures or video or something like that,
>>>> not 'data'), you could separate contrast&  color separately, keeping
>>>> high contrast resolution, and downsampled color, and
>>>>    you'd save both bandwidth and instr.
>>>>    If you simply want to know 'why', I'm guessing loss of precision in the
>>>> tex units?
>>>>    You've already ruled out shader precision from your own manual
>>>> filtering, so doesn't leave much else, imo..
>>>>    Other than manipulating the data you're working on, which is the only
>>>> thing you -can- change I guess, I cant really see a solution,
>>>>    but far greater minds linger here than mine, so hold on for what I
>>>> assume will be a lengthy description of floating point math as
>>>>    it is implemented in modern gpu's :)
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>    On Fri, Oct 1, 2010 at 9:57 AM, Andreas Brinck
>>>> <and...@gm...>  wrote:
>>>>
>>>>      Hi,
>>>>
>>>>      I have a texture in which I use the R, G and B channel to store a
>>>>      value in the [0, 1] range with very high precision. The value is
>>>>      extracted like this in the (Cg) shader:
>>>>
>>>>      float
>>>>      extractValue(float2 pos) {
>>>>         float4 temp = tex2D(buffer, pos);
>>>>         return (temp.x * 16711680.0 + temp.y * 65280.0 + temp.z * 255.0) *
>>>>      (1.0 / 16777215.0);
>>>>      }
>>>>
>>>>      I now want to sample this value with bilinear filtering but when I do
>>>>      this I don't get a correct result. If I do the filtering manually
>>>> like
>>>>      this:
>>>>
>>>>      float
>>>>      sampleValue(float2 pos) {
>>>>             float2 ipos = floor(pos);
>>>>             float2 fracs = pos - ipos;
>>>>             float d0 = extractValue(ipos);
>>>>             float d1 = extractValue(ipos + float2(1, 0));
>>>>             float d2 = extractValue(ipos + float2(0, 1));
>>>>             float d3 = extractValue(ipos + float2(1, 1));
>>>>             return lerp(lerp(d0, d1, fracs.x), lerp(d2, d3, fracs.x),
>>>> fracs.y);
>>>>      }
>>>>
>>>>      everything works as expected. The values in the buffer can be seen as
>>>>      a linear combination of three constants:
>>>>
>>>>      value = (C0 * r + C1 * g + C2 * b)
>>>>
>>>>      If we use the built in texture filtering we should get the following
>>>>      if we sample somewhere between two texels: {r0, g0, b0} and {r1, g1,
>>>>      b1}. For simplicity we just look at filtering along one axis:
>>>>
>>>>      filtered value = lerp(r0, r1, t) * C0 + lerp(g0, g1, t) * C1 +
>>>>      lerp(b0, b1, t) * C2;
>>>>
>>>>      Doing the filtering manually:
>>>>
>>>>      filtered value = lerp(r0 * C0 + b0 * C1 + g0 * C2, r1 * C0 + g1 * C1
>>>> +
>>>>      b1 * C2, t)  =
>>>>                        = (r0 * C0 + b0 * C1 + g0 * C2) * (1 - t) + (r1 *
>>>>      C0 + g1 * C1 + b1 * C2) * t =
>>>>                        = (r0 * C0) * (1 - t) + (r1 * C0) * t + ... =
>>>>                        = lerp(r0, r1, t) * C0 + ...
>>>>
>>>>      So in the world of non floating point numbers these two should be
>>>>      equivalent right?
>>>>
>>>>      My theory is that the error is caused by an unfortunate order of
>>>>      floating point operations. I've tried variations like:
>>>>
>>>>      (temp.x * (16711680.0 / 16777215.0) + temp.y * (65280.0/16777215.0) +
>>>>      temp.z * (255.0/16777215.0))
>>>>
>>>>      and
>>>>
>>>>      (((temp.x * 256.0 + temp.y) * 256.0 + temp.z) * 255.0) * (1.0 /
>>>> 16777215.0)
>>>>
>>>>      but all exhibit the same problem. What do you think; is it possible
>>>> to
>>>>      solve this problem?
>>>>
>>>>      Regards Andreas
>>>>
>>>>      ------------------------------------------------------------------------------
>>>>      Start uncovering the many advantages of virtual appliances
>>>>      and start using them to simplify application deployment and
>>>>      accelerate your shift to cloud computing.
>>>>      http://p.sf.net/sfu/novell-sfdev2dev
>>>>      _______________________________________________
>>>>      GDAlgorithms-list mailing list
>>>>      GDA...@li...
>>>>      https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>>>      Archives:
>>>>
>>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>>>
>>>>
>>>>
>>>>
>>>>
>>>> ------------------------------------------------------------------------------
>>>>
>>>>
>>>>    ------------------------------------------------------------------------------
>>>>    Start uncovering the many advantages of virtual appliances
>>>>    and start using them to simplify application deployment and
>>>>    accelerate your shift to cloud computing.
>>>>    http://p.sf.net/sfu/novell-sfdev2dev
>>>>
>>>>
>>>> ------------------------------------------------------------------------------
>>>>
>>>>
>>>>    _______________________________________________
>>>>    GDAlgorithms-list mailing list
>>>>    GDA...@li...
>>>>    https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>>>    Archives:
>>>>
>>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list------------------------------------------------------------------------------
>>>> Start uncovering the many advantages of virtual appliances
>>>> and start using them to simplify application deployment and
>>>> accelerate your shift to cloud computing.
>>>> http://p.sf.net/sfu/novell-sfdev2dev_______________________________________________
>>>> GDAlgorithms-list mailing list
>>>> GDA...@li...
>>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>>> Archives:
>>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>>
>>>
>>> ------------------------------------------------------------------------------
>>> Start uncovering the many advantages of virtual appliances
>>> and start using them to simplify application deployment and
>>> accelerate your shift to cloud computing.
>>> http://p.sf.net/sfu/novell-sfdev2dev
>>> _______________________________________________
>>> GDAlgorithms-list mailing list
>>> GDA...@li...
>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>> Archives:
>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>
>> ------------------------------------------------------------------------------
>> Start uncovering the many advantages of virtual appliances
>> and start using them to simplify application deployment and
>> accelerate your shift to cloud computing.
>> http://p.sf.net/sfu/novell-sfdev2dev
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDA...@li...
>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> Archives:
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>
> ------------------------------------------------------------------------------
> Start uncovering the many advantages of virtual appliances
> and start using them to simplify application deployment and
> accelerate your shift to cloud computing.
> http://p.sf.net/sfu/novell-sfdev2dev
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

Re: [Algorithms] Filtering

[Sylvain G. V. <vi...@ii...>]

>   On Fri, Oct 1, 2010 at 9:57 AM, Andreas Brinck
> <and...@gm...> wrote:
>     filtered value = lerp(r0 * C0 + b0 * C1 + g0 * C2, r1 * C0 + g1 * C1
> +
>     b1 * C2, t)  =
>                       = (r0 * C0 + b0 * C1 + g0 * C2) * (1 - t) + (r1 *
>     C0 + g1 * C1 + b1 * C2) * t =
>                       = (r0 * C0) * (1 - t) + (r1 * C0) * t + ... =
>                       = lerp(r0, r1, t) * C0 + ...
>
>     So in the world of non floating point numbers these two should be
>     equivalent right?

No they're not, due to rounding.

Take for example 2 texels:
R=1 G=0 B=0 and R=0 G=255 B=0

Lerping in the texfetch would spawn something like:
R=0 G=128 B=0
Definitely not what you're expecting! You'd want :
R=0 G=255 B=something

Using texfetch interpolation fails because it doesn't treat the 3 channels as one number; it won't always interpolate in the correct direction (interpreting 128 as either 0,5 or 1,5 depending on what's on the next channel) and it won't alter the other channel accordingly either.

Re: [Algorithms] Filtering

[Andreas B. <and...@gm...>]

Hi Ola,

unfortunately the floating point textures on the platform I'm working
on don't support bilinear filtering (this is the reason why I stored
the value in an RGB-texture to begin with).

/Andreas

P.S. Got your Ph.D yet?

On Fri, Oct 1, 2010 at 8:12 PM, Ola Olsson <ola...@gm...> wrote:
> While we're throwing ideas around, why not try using a float texture and see
> if it produces the same error?
>
> .ola
>
> P.S.
>  Hi Andreas :)
>
> ----- Original Message -----
> From: "Nathaniel Hoffman" <na...@io...>
> To: "Game Development Algorithms" <gda...@li...>
> Sent: Friday, October 01, 2010 7:59 PM
> Subject: Re: [Algorithms] Filtering
>
>
>> Didn't the newer NVIDIA GPUs fix this?
>>
>>> You guessed right. The loss of precision is in the texture units.
>>> Unfortunately, 8 bit components are filtered to 8 bit results (even
>>> though
>>> they show up as floating point values in the shader). This is true for
>>> nvidia gpus for sure and probably all other gpus.
>>>
>>> -mike
>>>   ----- Original Message -----
>>>   From: Stefan Sandberg
>>>   To: Game Development Algorithms
>>>   Sent: Friday, October 01, 2010 1:45 AM
>>>   Subject: Re: [Algorithms] Filtering
>>>
>>>
>>>   Assuming you're after precision, what's wrong with doing it manually?
>>> :)
>>>   If performance is what you're after, and you're working on textures as
>>> they were intended(ie, game textures or video or something like that,
>>> not 'data'), you could separate contrast & color separately, keeping
>>> high contrast resolution, and downsampled color, and
>>>   you'd save both bandwidth and instr.
>>>   If you simply want to know 'why', I'm guessing loss of precision in the
>>> tex units?
>>>   You've already ruled out shader precision from your own manual
>>> filtering, so doesn't leave much else, imo..
>>>   Other than manipulating the data you're working on, which is the only
>>> thing you -can- change I guess, I cant really see a solution,
>>>   but far greater minds linger here than mine, so hold on for what I
>>> assume will be a lengthy description of floating point math as
>>>   it is implemented in modern gpu's :)
>>>
>>>
>>>
>>>
>>>
>>>
>>>   On Fri, Oct 1, 2010 at 9:57 AM, Andreas Brinck
>>> <and...@gm...> wrote:
>>>
>>>     Hi,
>>>
>>>     I have a texture in which I use the R, G and B channel to store a
>>>     value in the [0, 1] range with very high precision. The value is
>>>     extracted like this in the (Cg) shader:
>>>
>>>     float
>>>     extractValue(float2 pos) {
>>>        float4 temp = tex2D(buffer, pos);
>>>        return (temp.x * 16711680.0 + temp.y * 65280.0 + temp.z * 255.0) *
>>>     (1.0 / 16777215.0);
>>>     }
>>>
>>>     I now want to sample this value with bilinear filtering but when I do
>>>     this I don't get a correct result. If I do the filtering manually
>>> like
>>>     this:
>>>
>>>     float
>>>     sampleValue(float2 pos) {
>>>            float2 ipos = floor(pos);
>>>            float2 fracs = pos - ipos;
>>>            float d0 = extractValue(ipos);
>>>            float d1 = extractValue(ipos + float2(1, 0));
>>>            float d2 = extractValue(ipos + float2(0, 1));
>>>            float d3 = extractValue(ipos + float2(1, 1));
>>>            return lerp(lerp(d0, d1, fracs.x), lerp(d2, d3, fracs.x),
>>> fracs.y);
>>>     }
>>>
>>>     everything works as expected. The values in the buffer can be seen as
>>>     a linear combination of three constants:
>>>
>>>     value = (C0 * r + C1 * g + C2 * b)
>>>
>>>     If we use the built in texture filtering we should get the following
>>>     if we sample somewhere between two texels: {r0, g0, b0} and {r1, g1,
>>>     b1}. For simplicity we just look at filtering along one axis:
>>>
>>>     filtered value = lerp(r0, r1, t) * C0 + lerp(g0, g1, t) * C1 +
>>>     lerp(b0, b1, t) * C2;
>>>
>>>     Doing the filtering manually:
>>>
>>>     filtered value = lerp(r0 * C0 + b0 * C1 + g0 * C2, r1 * C0 + g1 * C1
>>> +
>>>     b1 * C2, t)  =
>>>                       = (r0 * C0 + b0 * C1 + g0 * C2) * (1 - t) + (r1 *
>>>     C0 + g1 * C1 + b1 * C2) * t =
>>>                       = (r0 * C0) * (1 - t) + (r1 * C0) * t + ... =
>>>                       = lerp(r0, r1, t) * C0 + ...
>>>
>>>     So in the world of non floating point numbers these two should be
>>>     equivalent right?
>>>
>>>     My theory is that the error is caused by an unfortunate order of
>>>     floating point operations. I've tried variations like:
>>>
>>>     (temp.x * (16711680.0 / 16777215.0) + temp.y * (65280.0/16777215.0) +
>>>     temp.z * (255.0/16777215.0))
>>>
>>>     and
>>>
>>>     (((temp.x * 256.0 + temp.y) * 256.0 + temp.z) * 255.0) * (1.0 /
>>> 16777215.0)
>>>
>>>     but all exhibit the same problem. What do you think; is it possible
>>> to
>>>     solve this problem?
>>>
>>>     Regards Andreas
>>>
>>>     ------------------------------------------------------------------------------
>>>     Start uncovering the many advantages of virtual appliances
>>>     and start using them to simplify application deployment and
>>>     accelerate your shift to cloud computing.
>>>     http://p.sf.net/sfu/novell-sfdev2dev
>>>     _______________________________________________
>>>     GDAlgorithms-list mailing list
>>>     GDA...@li...
>>>     https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>>     Archives:
>>>
>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>>
>>>
>>>
>>>
>>>
>>> ------------------------------------------------------------------------------
>>>
>>>
>>>   ------------------------------------------------------------------------------
>>>   Start uncovering the many advantages of virtual appliances
>>>   and start using them to simplify application deployment and
>>>   accelerate your shift to cloud computing.
>>>   http://p.sf.net/sfu/novell-sfdev2dev
>>>
>>>
>>> ------------------------------------------------------------------------------
>>>
>>>
>>>   _______________________________________________
>>>   GDAlgorithms-list mailing list
>>>   GDA...@li...
>>>   https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>>   Archives:
>>>
>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list------------------------------------------------------------------------------
>>> Start uncovering the many advantages of virtual appliances
>>> and start using them to simplify application deployment and
>>> accelerate your shift to cloud computing.
>>> http://p.sf.net/sfu/novell-sfdev2dev_______________________________________________
>>> GDAlgorithms-list mailing list
>>> GDA...@li...
>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>> Archives:
>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>
>>
>>
>> ------------------------------------------------------------------------------
>> Start uncovering the many advantages of virtual appliances
>> and start using them to simplify application deployment and
>> accelerate your shift to cloud computing.
>> http://p.sf.net/sfu/novell-sfdev2dev
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDA...@li...
>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> Archives:
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>
>
> ------------------------------------------------------------------------------
> Start uncovering the many advantages of virtual appliances
> and start using them to simplify application deployment and
> accelerate your shift to cloud computing.
> http://p.sf.net/sfu/novell-sfdev2dev
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

Re: [Algorithms] Filtering

[Andreas B. <and...@gm...>]

Well that certainly explains it. I guess I'm stuck with doing the
filtering myself then. Thanks anyway guys!

On Fri, Oct 1, 2010 at 4:54 PM, Michael Bunnell <mi...@fa...> wrote:
> You guessed right. The loss of precision is in the texture units.
> Unfortunately, 8 bit components are filtered to 8 bit results (even though
> they show up as floating point values in the shader). This is true
> for nvidia gpus for sure and probably all other gpus.
>
> -mike
>
> ----- Original Message -----
> From: Stefan Sandberg
> To: Game Development Algorithms
> Sent: Friday, October 01, 2010 1:45 AM
> Subject: Re: [Algorithms] Filtering
> Assuming you're after precision, what's wrong with doing it manually? :)
> If performance is what you're after, and you're working on textures as they
> were intended(ie, game textures or video or something like that, not
> 'data'), you could separate contrast & color separately, keeping high
> contrast resolution, and downsampled color, and
> you'd save both bandwidth and instr.
> If you simply want to know 'why', I'm guessing loss of precision in the tex
> units?
> You've already ruled out shader precision from your own manual filtering,
> so doesn't leave much else, imo..
> Other than manipulating the data you're working on, which is the only thing
> you -can- change I guess, I cant really see a solution,
> but far greater minds linger here than mine, so hold on for what I assume
> will be a lengthy description of floating point math as
> it is implemented in modern gpu's :)
>
>
> On Fri, Oct 1, 2010 at 9:57 AM, Andreas Brinck <and...@gm...>
> wrote:
>>
>> Hi,
>>
>> I have a texture in which I use the R, G and B channel to store a
>> value in the [0, 1] range with very high precision. The value is
>> extracted like this in the (Cg) shader:
>>
>> float
>> extractValue(float2 pos) {
>>    float4 temp = tex2D(buffer, pos);
>>    return (temp.x * 16711680.0 + temp.y * 65280.0 + temp.z * 255.0) *
>> (1.0 / 16777215.0);
>> }
>>
>> I now want to sample this value with bilinear filtering but when I do
>> this I don't get a correct result. If I do the filtering manually like
>> this:
>>
>> float
>> sampleValue(float2 pos) {
>>        float2 ipos = floor(pos);
>>        float2 fracs = pos - ipos;
>>        float d0 = extractValue(ipos);
>>        float d1 = extractValue(ipos + float2(1, 0));
>>        float d2 = extractValue(ipos + float2(0, 1));
>>        float d3 = extractValue(ipos + float2(1, 1));
>>        return lerp(lerp(d0, d1, fracs.x), lerp(d2, d3, fracs.x), fracs.y);
>> }
>>
>> everything works as expected. The values in the buffer can be seen as
>> a linear combination of three constants:
>>
>> value = (C0 * r + C1 * g + C2 * b)
>>
>> If we use the built in texture filtering we should get the following
>> if we sample somewhere between two texels: {r0, g0, b0} and {r1, g1,
>> b1}. For simplicity we just look at filtering along one axis:
>>
>> filtered value = lerp(r0, r1, t) * C0 + lerp(g0, g1, t) * C1 +
>> lerp(b0, b1, t) * C2;
>>
>> Doing the filtering manually:
>>
>> filtered value = lerp(r0 * C0 + b0 * C1 + g0 * C2, r1 * C0 + g1 * C1 +
>> b1 * C2, t)  =
>>                   = (r0 * C0 + b0 * C1 + g0 * C2) * (1 - t) + (r1 *
>> C0 + g1 * C1 + b1 * C2) * t =
>>                   = (r0 * C0) * (1 - t) + (r1 * C0) * t + ... =
>>                   = lerp(r0, r1, t) * C0 + ...
>>
>> So in the world of non floating point numbers these two should be
>> equivalent right?
>>
>> My theory is that the error is caused by an unfortunate order of
>> floating point operations. I've tried variations like:
>>
>> (temp.x * (16711680.0 / 16777215.0) + temp.y * (65280.0/16777215.0) +
>> temp.z * (255.0/16777215.0))
>>
>> and
>>
>> (((temp.x * 256.0 + temp.y) * 256.0 + temp.z) * 255.0) * (1.0 /
>> 16777215.0)
>>
>> but all exhibit the same problem. What do you think; is it possible to
>> solve this problem?
>>
>> Regards Andreas
>>
>>
>> ------------------------------------------------------------------------------
>> Start uncovering the many advantages of virtual appliances
>> and start using them to simplify application deployment and
>> accelerate your shift to cloud computing.
>> http://p.sf.net/sfu/novell-sfdev2dev
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDA...@li...
>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> Archives:
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>
> ________________________________
>
> ------------------------------------------------------------------------------
> Start uncovering the many advantages of virtual appliances
> and start using them to simplify application deployment and
> accelerate your shift to cloud computing.
> http://p.sf.net/sfu/novell-sfdev2dev
>
> ________________________________
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>
> ------------------------------------------------------------------------------
> Start uncovering the many advantages of virtual appliances
> and start using them to simplify application deployment and
> accelerate your shift to cloud computing.
> http://p.sf.net/sfu/novell-sfdev2dev
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

Re: [Algorithms] Filtering

[Fabian G. <ry...@gm...>]

On 01.10.2010 11:04, Jeff Russell wrote:
> I'm thinking maybe older gpu's did even courser filtering than this -
> 6-bit or something instead of 8. Maybe this was the recent improvement?

There's the subpixel resolution of texture coordinates going into the 
filtering unit and there's the actual filtering precision.

The former will make blocks appear once you zoom up close enough. For 
most texture this isn't a problem as you try to keep the texel:pixel 
ratio close to 1:1 anyway, but I ran into this a while ago on some 
textures that were mostly gradients. This is extra-annoying on gradient 
textures since you can't make them too large either - if they're too 
large, adjacent pixels have the same color value sometimes, which 
bilinear filtering will expand into a constant stretch in the middle of 
your gradient - a very visible problem, unfortunately.

The actual filtering has been working on at least 8-bit values for quite 
some time (at least as far back as the GeForce3 / original Radeons, not 
sure about earlier cards).

You may get more precision on newer cards, but it's probably not much 
more (half-floats or something like that, most likely). These return 
paths aren't super-wide for a reason - you don't put 128-bit (4x32) 
buses all over your chip when you can avoid it. (Samplers most likely 
support returning full 32-bit results, but it will take more than one 
cycle to transfer results then).