Re: [Algorithms] CSG operations on textured meshes -- something better than CGAL?

[Jon Watte <jwatte@gm...>]

> You are going to be distorting triangles in different ways depending on
the overall shape of the mesh at any given point though.
> If you just retain existing UV coordinates for the new vertices, the
results will be...  strange.

I do this operation with some frequency in 3ds Max, and it works the way I
expect there.

The 3ds Max boolean (and proboolean) modifier behavior would be good enough
for my purposes, although they do have some edge cases and limitaitons (a k
a "bugs" :-)
But I don't want to buy a copy of 3ds Max per server that will be running
this code, not to mention I want to run the servers on Linux.

So, does anyone know of any textured-triangle-mesh CSG library out there,
free or paid for, that would work?

Sincerely,

jw






Sincerely,

Jon Watte


--
"I find that the harder I work, the more luck I seem to have." -- Thomas
Jefferson


On Tue, May 13, 2014 at 10:07 PM, James Robertson <james@...> wrote:

>  You are going to be distorting triangles in different ways depending on
> the overall shape of the mesh at any given point though.  If you just
> retain existing UV coordinates for the new vertices, the results will
> be...  strange.
>
> Consider the case where a convex region meets a concave one.  One side of
> the triangle will be slightly expanded, while the other side will be
> contracted.  Of course you know your input data better than us, so maybe
> such distortions are acceptable or won't be noticeable, but they will be
> there.
>
>
>
> On 14/05/2014 01:41, Jon Watte wrote:
>
>  I don’t believe you will be able to use your existing uv values with the
>> mesh that results from this csg operation
>
>
>  The operations I want to do are rigid and well conditioned and do not
> stretch or generate new surfaces compared to the input meshes. They may
> invert the winding of triangles, though (so normal maps would have to be
> flipped) in the case of a cut-out.
> I also need to preserve vertex bone weighting, too... something that can
> preserve UV should be able to preserve that, too. Worst case, I put in a
> vertex ID value in the UV channel and loop up the other parameters based on
> that.
>
>  So... no general purpose parameterized trimesh CSG library available?
>
>  Sincerely,
>
>  jw
>
>
>
>
>
> Sincerely,
>
> Jon Watte
>
>
> --
> "I find that the harder I work, the more luck I seem to have." -- Thomas
> Jefferson
>
>
> On Thu, May 8, 2014 at 12:28 PM, Chris Green <cgreen@...>wrote:
>
>>  I don’t believe you will be able to use your existing uv values with
>> the mesh that results from this csg operation – it has a different
>> topology, and there will be changes in the ratios of the areas of different
>> parts of the model, with really bumpy areas of the mesh being smoothed out,
>> etc. You’ll even have brand new areas emerge that don’t have corresponding
>> areas on the original model, as holes are filled in, etc.
>>
>>
>>
>> What might work better is to just do the csg operation and generate a uv
>> atlas for the resultant mesh. You can then generate a new texture map for
>> this uv parametization by sampling from the original one, in a similar
>> manner to the way in which people produce bumpmaps mapping the normals of
>> highly tessellated models onto low-detail models.
>>
>>
>>
>>
>>
>>
>>
>> *From:* Jon Watte [mailto:jwatte@...]
>> *Sent:* Thursday, May 08, 2014 11:08 AM
>> *To:* Game Development Algorithms
>> *Subject:* [Algorithms] CSG operations on textured meshes -- something
>> better than CGAL?
>>
>>
>>
>> I have a triangle mesh composed of many submeshes with different
>> textures/materials. This mesh may not be a 2-manifold -- it may have open
>> edges. Typical game art.
>>
>>
>>
>> I now want to create a 3mm thick shell of this mesh. As an approximation,
>> taking each triangle, and extrude it back along the normal of each vertex,
>> and union all of those generated chopped pyramids would be an approximation
>> of what I want. If I do literally that, and self-union the result, then
>> that should resolve the self-intersection problems I'll run into along
>> narrow sharp creases etc.
>>
>>
>>
>> I can't find any library to do this, though. CGAL has some fairly robust
>> functions on NEF polyhedra, but those polyhedra don't seem to allow
>> parameterization (which is academic speak for texture coordinates that may
>> have discontinuities across edges.)
>>
>>
>>
>> So, what are some robust CSG libraries available that work on such
>> game-style meshes, preserving texture coordinates?
>>
>>
>>
>> (And actually, I don't have one such mesh; I have > 120 million such
>> meshes, so a by-hand or even script-the-Max-shell-modifier solution is
>> unlikely to work. I do have hundreds of Linux servers at my disposal,
>> though.)
>>
>>
>>
>> Sincerely,
>>
>> Jon Watte
>>
>>
>> --
>> "I find that the harder I work, the more luck I seem to have." -- Thomas
>> Jefferson
>>
>>
>> ------------------------------------------------------------------------------
>> Is your legacy SCM system holding you back? Join Perforce May 7 to find
>> out:
>> &#149; 3 signs your SCM is hindering your productivity
>> &#149; Requirements for releasing software faster
>> &#149; Expert tips and advice for migrating your SCM now
>> http://p.sf.net/sfu/perforce
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDAlgorithms-list@...
>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> Archives:
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>
>
>
>
> ------------------------------------------------------------------------------
> "Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE
> Instantly run your Selenium tests across 300+ browser/OS combos.
> Get unparalleled scalability from the best Selenium testing platform available
> Simple to use. Nothing to install. Get started now for free."http://p.sf.net/sfu/SauceLabs
>
>
>
> _______________________________________________
> GDAlgorithms-list mailing listGDAlgorithms-list@...nethttps://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>
>
>
>
> ------------------------------
>    <http://www.avast.com/>;
>
> This email is free from viruses and malware because avast! Antivirus<http://www.avast.com/>protection is active.
>
>
>
> ------------------------------------------------------------------------------
> "Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE
> Instantly run your Selenium tests across 300+ browser/OS combos.
> Get unparalleled scalability from the best Selenium testing platform
> available
> Simple to use. Nothing to install. Get started now for free."
> http://p.sf.net/sfu/SauceLabs
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

Re: [Algorithms] CSG operations on textured meshes -- something better than CGAL?

[James Robertson <james@os...>]

You are going to be distorting triangles in different ways depending on the overall shape of the mesh at any given point though.  If you just retain existing UV coordinates for the new vertices, the results will be...  strange.

Consider the case where a convex region meets a concave one.  One side of the triangle will be slightly expanded, while the other side will be contracted.  Of course you know your input data better than us, so maybe such distortions are acceptable or won't be noticeable, but they will be there.


On 14/05/2014 01:41, Jon Watte wrote:
>
>     I don't believe you will be able to use your existing uv values with the mesh that results from this csg operation
>
>
> The operations I want to do are rigid and well conditioned and do not stretch or generate new surfaces compared to the input meshes. They may invert the winding of triangles, though (so normal maps would have to be flipped) in the case of a cut-out.
> I also need to preserve vertex bone weighting, too... something that can preserve UV should be able to preserve that, too. Worst case, I put in a vertex ID value in the UV channel and loop up the other parameters based on that.
>
> So... no general purpose parameterized trimesh CSG library available?
>
> Sincerely,
>
> jw
>
>
>
>
>
> Sincerely,
>
> Jon Watte
>
>
> --
> "I find that the harder I work, the more luck I seem to have." -- Thomas Jefferson
>
>
> On Thu, May 8, 2014 at 12:28 PM, Chris Green <cgreen@... <mailto:cgreen@...>> wrote:
>
>     I don't believe you will be able to use your existing uv values with the mesh that results from this csg operation -- it has a different topology, and there will be changes in the ratios of the areas of different parts of the model, with really bumpy areas of the mesh being smoothed out, etc. You'll even have brand new areas emerge that don't have corresponding areas on the original model, as holes are filled in, etc.
>
>     What might work better is to just do the csg operation and generate a uv atlas for the resultant mesh. You can then generate a new texture map for this uv parametization by sampling from the original one, in a similar manner to the way in which people produce bumpmaps mapping the normals of highly tessellated models onto low-detail models.
>
>     *From:*Jon Watte [mailto:jwatte@... <mailto:jwatte@...>]
>     *Sent:* Thursday, May 08, 2014 11:08 AM
>     *To:* Game Development Algorithms
>     *Subject:* [Algorithms] CSG operations on textured meshes -- something better than CGAL?
>
>     I have a triangle mesh composed of many submeshes with different textures/materials. This mesh may not be a 2-manifold -- it may have open edges. Typical game art.
>
>     I now want to create a 3mm thick shell of this mesh. As an approximation, taking each triangle, and extrude it back along the normal of each vertex, and union all of those generated chopped pyramids would be an approximation of what I want. If I do literally that, and self-union the result, then that should resolve the self-intersection problems I'll run into along narrow sharp creases etc.
>
>     I can't find any library to do this, though. CGAL has some fairly robust functions on NEF polyhedra, but those polyhedra don't seem to allow parameterization (which is academic speak for texture coordinates that may have discontinuities across edges.)
>
>     So, what are some robust CSG libraries available that work on such game-style meshes, preserving texture coordinates?
>
>     (And actually, I don't have one such mesh; I have > 120 million such meshes, so a by-hand or even script-the-Max-shell-modifier solution is unlikely to work. I do have hundreds of Linux servers at my disposal, though.)
>
>
>
>     Sincerely,
>
>     Jon Watte
>
>
>     --
>     "I find that the harder I work, the more luck I seem to have." -- Thomas Jefferson
>
>
>     ------------------------------------------------------------------------------
>     Is your legacy SCM system holding you back? Join Perforce May 7 to find out:
>     &#149; 3 signs your SCM is hindering your productivity
>     &#149; Requirements for releasing software faster
>     &#149; Expert tips and advice for migrating your SCM now
>     http://p.sf.net/sfu/perforce
>     _______________________________________________
>     GDAlgorithms-list mailing list
>     GDAlgorithms-list@... <mailto:GDAlgorithms-list@...>
>     https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>     Archives:
>     http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>
>
>
>
> ------------------------------------------------------------------------------
> "Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE
> Instantly run your Selenium tests across 300+ browser/OS combos.
> Get unparalleled scalability from the best Selenium testing platform available
> Simple to use. Nothing to install. Get started now for free."
> http://p.sf.net/sfu/SauceLabs
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list



---
This email is free from viruses and malware because avast! Antivirus protection is active.
http://www.avast.com

Re: [Algorithms] CSG operations on textured meshes -- something better than CGAL?

[Jon Watte <jwatte@gm...>]

>
> I don’t believe you will be able to use your existing uv values with the
> mesh that results from this csg operation


The operations I want to do are rigid and well conditioned and do not
stretch or generate new surfaces compared to the input meshes. They may
invert the winding of triangles, though (so normal maps would have to be
flipped) in the case of a cut-out.
I also need to preserve vertex bone weighting, too... something that can
preserve UV should be able to preserve that, too. Worst case, I put in a
vertex ID value in the UV channel and loop up the other parameters based on
that.

So... no general purpose parameterized trimesh CSG library available?

Sincerely,

jw





Sincerely,

Jon Watte


--
"I find that the harder I work, the more luck I seem to have." -- Thomas
Jefferson


On Thu, May 8, 2014 at 12:28 PM, Chris Green <cgreen@...>wrote:

>  I don’t believe you will be able to use your existing uv values with the
> mesh that results from this csg operation – it has a different topology,
> and there will be changes in the ratios of the areas of different parts of
> the model, with really bumpy areas of the mesh being smoothed out, etc.
> You’ll even have brand new areas emerge that don’t have corresponding areas
> on the original model, as holes are filled in, etc.
>
>
>
> What might work better is to just do the csg operation and generate a uv
> atlas for the resultant mesh. You can then generate a new texture map for
> this uv parametization by sampling from the original one, in a similar
> manner to the way in which people produce bumpmaps mapping the normals of
> highly tessellated models onto low-detail models.
>
>
>
>
>
>
>
> *From:* Jon Watte [mailto:jwatte@...]
> *Sent:* Thursday, May 08, 2014 11:08 AM
> *To:* Game Development Algorithms
> *Subject:* [Algorithms] CSG operations on textured meshes -- something
> better than CGAL?
>
>
>
> I have a triangle mesh composed of many submeshes with different
> textures/materials. This mesh may not be a 2-manifold -- it may have open
> edges. Typical game art.
>
>
>
> I now want to create a 3mm thick shell of this mesh. As an approximation,
> taking each triangle, and extrude it back along the normal of each vertex,
> and union all of those generated chopped pyramids would be an approximation
> of what I want. If I do literally that, and self-union the result, then
> that should resolve the self-intersection problems I'll run into along
> narrow sharp creases etc.
>
>
>
> I can't find any library to do this, though. CGAL has some fairly robust
> functions on NEF polyhedra, but those polyhedra don't seem to allow
> parameterization (which is academic speak for texture coordinates that may
> have discontinuities across edges.)
>
>
>
> So, what are some robust CSG libraries available that work on such
> game-style meshes, preserving texture coordinates?
>
>
>
> (And actually, I don't have one such mesh; I have > 120 million such
> meshes, so a by-hand or even script-the-Max-shell-modifier solution is
> unlikely to work. I do have hundreds of Linux servers at my disposal,
> though.)
>
>
>
> Sincerely,
>
> Jon Watte
>
>
> --
> "I find that the harder I work, the more luck I seem to have." -- Thomas
> Jefferson
>
>
> ------------------------------------------------------------------------------
> Is your legacy SCM system holding you back? Join Perforce May 7 to find
> out:
> &#149; 3 signs your SCM is hindering your productivity
> &#149; Requirements for releasing software faster
> &#149; Expert tips and advice for migrating your SCM now
> http://p.sf.net/sfu/perforce
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

Re: [Algorithms] CSG operations on textured meshes -- something better than CGAL?

[Chris Green <cgreen@va...>]

I don’t believe you will be able to use your existing uv values with the mesh that results from this csg operation – it has a different topology, and there will be changes in the ratios of the areas of different parts of the model, with really bumpy areas of the mesh being smoothed out, etc. You’ll even have brand new areas emerge that don’t have corresponding areas on the original model, as holes are filled in, etc.

What might work better is to just do the csg operation and generate a uv atlas for the resultant mesh. You can then generate a new texture map for this uv parametization by sampling from the original one, in a similar manner to the way in which people produce bumpmaps mapping the normals of highly tessellated models onto low-detail models.



From: Jon Watte [mailto:jwatte@...]
Sent: Thursday, May 08, 2014 11:08 AM
To: Game Development Algorithms
Subject: [Algorithms] CSG operations on textured meshes -- something better than CGAL?

I have a triangle mesh composed of many submeshes with different textures/materials. This mesh may not be a 2-manifold -- it may have open edges. Typical game art.

I now want to create a 3mm thick shell of this mesh. As an approximation, taking each triangle, and extrude it back along the normal of each vertex, and union all of those generated chopped pyramids would be an approximation of what I want. If I do literally that, and self-union the result, then that should resolve the self-intersection problems I'll run into along narrow sharp creases etc.

I can't find any library to do this, though. CGAL has some fairly robust functions on NEF polyhedra, but those polyhedra don't seem to allow parameterization (which is academic speak for texture coordinates that may have discontinuities across edges.)

So, what are some robust CSG libraries available that work on such game-style meshes, preserving texture coordinates?

(And actually, I don't have one such mesh; I have > 120 million such meshes, so a by-hand or even script-the-Max-shell-modifier solution is unlikely to work. I do have hundreds of Linux servers at my disposal, though.)


Sincerely,

Jon Watte


--
"I find that the harder I work, the more luck I seem to have." -- Thomas Jefferson

Re: [Algorithms] CSG operations on textured meshes -- something better than CGAL?

[Robin Green <robin.green@gm...>]

May I suggest another route?

Implicit surfaces provide the kind of distance-field and union operations
you need quite simply, and the results can be polygonalized using extremely
robust, mature libraries.
I know implicit surfaces haven't been a hot topic at Siggraph for years,
but they are still useful for solving specific problem sets.

- Robin Green.


On Thu, May 8, 2014 at 11:08 AM, Jon Watte <jwatte@...> wrote:

> I have a triangle mesh composed of many submeshes with different
> textures/materials. This mesh may not be a 2-manifold -- it may have open
> edges. Typical game art.
>
> I now want to create a 3mm thick shell of this mesh. As an approximation,
> taking each triangle, and extrude it back along the normal of each vertex,
> and union all of those generated chopped pyramids would be an approximation
> of what I want. If I do literally that, and self-union the result, then
> that should resolve the self-intersection problems I'll run into along
> narrow sharp creases etc.
>
> I can't find any library to do this, though. CGAL has some fairly robust
> functions on NEF polyhedra, but those polyhedra don't seem to allow
> parameterization (which is academic speak for texture coordinates that may
> have discontinuities across edges.)
>
> So, what are some robust CSG libraries available that work on such
> game-style meshes, preserving texture coordinates?
>
> (And actually, I don't have one such mesh; I have > 120 million such
> meshes, so a by-hand or even script-the-Max-shell-modifier solution is
> unlikely to work. I do have hundreds of Linux servers at my disposal,
> though.)
>
>
> Sincerely,
>
> Jon Watte
>
>
> --
> "I find that the harder I work, the more luck I seem to have." -- Thomas
> Jefferson
>
>
> ------------------------------------------------------------------------------
> Is your legacy SCM system holding you back? Join Perforce May 7 to find
> out:
> &#149; 3 signs your SCM is hindering your productivity
> &#149; Requirements for releasing software faster
> &#149; Expert tips and advice for migrating your SCM now
> http://p.sf.net/sfu/perforce
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

[Algorithms] CSG operations on textured meshes -- something better than CGAL?

[Jon Watte <jwatte@gm...>]

I have a triangle mesh composed of many submeshes with different
textures/materials. This mesh may not be a 2-manifold -- it may have open
edges. Typical game art.

I now want to create a 3mm thick shell of this mesh. As an approximation,
taking each triangle, and extrude it back along the normal of each vertex,
and union all of those generated chopped pyramids would be an approximation
of what I want. If I do literally that, and self-union the result, then
that should resolve the self-intersection problems I'll run into along
narrow sharp creases etc.

I can't find any library to do this, though. CGAL has some fairly robust
functions on NEF polyhedra, but those polyhedra don't seem to allow
parameterization (which is academic speak for texture coordinates that may
have discontinuities across edges.)

So, what are some robust CSG libraries available that work on such
game-style meshes, preserving texture coordinates?

(And actually, I don't have one such mesh; I have > 120 million such
meshes, so a by-hand or even script-the-Max-shell-modifier solution is
unlikely to work. I do have hundreds of Linux servers at my disposal,
though.)


Sincerely,

Jon Watte


--
"I find that the harder I work, the more luck I seem to have." -- Thomas
Jefferson

Re: [Algorithms] sparse bitset compression

[Richard Fabian <raspo1@gm...>]

AC (and now Finite State Entropy
https://github.com/Cyan4973/FiniteStateEntropy) are really good, but carry
the weight of spending more time than we had to do the task. Goulomb coding
the distance between high bits was a great, simple to implement solution
for us. Another issue was the compression time. It needed to be quick, and
AC is not known to be fast.

In future, I hope to use FSE for almost all my lossless coders.


On 8 March 2014 15:13, Colt McAnlis <mainroach@...> wrote:

> Why not just use industry standard Arithmetic Compression?
>
> If you calculate the estimated entropy for that data set (
> http://planetcalc.com/2476/) you end up with about H=0.06 for 7k set bits
> in a 1024*1024 stream, and H=0.01 for 1k set bits.
> That being entropy (or minimum bits per symbol) should yield 70kb and 10k
> after compression, respectively. Or, with AC, and those sparse values, you
> can get around 94% compression and 99% compression. (if my early morning
> math is right)
>
> AC is a known algorithm, easy examples to find on the web. And as far a
> serialization is concerned, it's pretty straight forward to just encode
> your bits, then decode; no extra special data structures needed.
>
> ~Main
>
>
> On Fri, Jan 31, 2014 at 3:27 PM, Richard Fabian <raspo1@...> wrote:
>
>> there was a lot of similarity, but with no processng at the destination,
>> we decided that the Golomb-rice algorithm was good enough. Dropped our data
>> by 70%. That was enough of a saving for this one area.
>>
>>
>> On 31 January 2014 21:32, Jon Watte <jwatte@...> wrote:
>>
>>> Encode a single starting value at full bandwidth then send a stream of
>>>> differences:
>>>
>>>
>>> Which is equivalent to a wavelet "lift" transform :-)
>>>
>>> Back to the original question: If you have a previous save game, is
>>> there lots of similarity in the next save? If so, can you save a delta
>>> instead?
>>> If not, what solution did you end up choosing?
>>>
>>> Sincerely,
>>>
>>> jw
>>>
>>>
>>>
>>>
>>>
>>>
>>> Sincerely,
>>>
>>> Jon Watte
>>>
>>>
>>> --
>>> "I find that the harder I work, the more luck I seem to have." --
>>> Thomas Jefferson
>>>
>>>
>>> On Tue, Jan 21, 2014 at 12:08 AM, Robin Green <robin.green@...>wrote:
>>>
>>>>
>>>> Here's a modern Run Length version of Golomb-Rice encoding designed for
>>>> compressing general data with a Generalized Gaussian distribution. Works
>>>> best if you can prove there are, in most cases, small differences between
>>>> adjacent data (but handily you get to define what "adjacent" means to your
>>>> stream). Encode a single starting value at full bandwidth then send a
>>>> stream of differences:
>>>>
>>>>     https://research.microsoft.com/pubs/102069/malvar_dcc06.pdf
>>>>
>>>> As a bonus, if you're encoding depth images, you can remap the values
>>>> to leave zero as an out-of-band value:
>>>>
>>>>     http://www.charlesneedham.com/pubs/153971/depthcode-final.pdf
>>>>
>>>> Yes, I know that wasn't the question you asked but at least it's an
>>>> algorithm. :-)
>>>>
>>>> - Robin Green
>>>>
>>>>
>>>>
>>>> On Fri, Jan 17, 2014 at 10:04 AM, Alex Walters <ajw.walters@...>wrote:
>>>>
>>>>> Its on the fringe of being useful, but one thing you could look at to
>>>>> reduce your data size is Exponential Golomb coding (
>>>>> http://en.wikipedia.org/wiki/Exponential-Golomb_coding), its used in
>>>>> H.264 entropy encoding among other things.
>>>>>
>>>>> Instead of writing a full n-bit values for every number you store, it
>>>>> produces a bit stream of codes, using far less bits for small numbers -
>>>>> take a look at the wiki page, its pretty simple to see whats going on when
>>>>> you look at the example. It can reduce the amount of data you have to move,
>>>>> and from what I remember from when I worked with video, it produces much
>>>>> more predictable (and compressible) stream of bits for the next compression
>>>>> scheme along (variable length encoding, or arithmetic encoding in the case
>>>>> of H.264) - I've not looked into the details but could probably improve the
>>>>> compression of the stream you get through gzip.
>>>>>
>>>>> Regards,
>>>>>
>>>>> Alex
>>>>>
>>>>>
>>>>>
>>>>
>>>> ------------------------------------------------------------------------------
>>>> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
>>>> Learn Why More Businesses Are Choosing CenturyLink Cloud For
>>>> Critical Workloads, Development Environments & Everything In Between.
>>>> Get a Quote or Start a Free Trial Today.
>>>>
>>>> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk
>>>> _______________________________________________
>>>> GDAlgorithms-list mailing list
>>>> GDAlgorithms-list@...
>>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>>> Archives:
>>>>
>>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>>>
>>>
>>>
>>>
>>> ------------------------------------------------------------------------------
>>> WatchGuard Dimension instantly turns raw network data into actionable
>>> security intelligence. It gives you real-time visual feedback on key
>>> security issues and trends.  Skip the complicated setup - simply import
>>> a virtual appliance and go from zero to informed in seconds.
>>>
>>> http://pubads.g.doubleclick.net/gampad/clk?id=123612991&iu=/4140/ostg.clktrk
>>>
>>> _______________________________________________
>>> GDAlgorithms-list mailing list
>>> GDAlgorithms-list@...
>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>> Archives:
>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>>
>>
>>
>>
>> --
>> fabs();
>> "The fact that an opinion has been widely held is no evidence whatever
>> that it is not utterly absurd." - Bertrand Russell
>>
>>
>> ------------------------------------------------------------------------------
>> WatchGuard Dimension instantly turns raw network data into actionable
>> security intelligence. It gives you real-time visual feedback on key
>> security issues and trends.  Skip the complicated setup - simply import
>> a virtual appliance and go from zero to informed in seconds.
>>
>> http://pubads.g.doubleclick.net/gampad/clk?id=123612991&iu=/4140/ostg.clktrk
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDAlgorithms-list@...
>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> Archives:
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>
>
>
>
> --
> ==
> Colt "MainRoach" McAnlis
> Graphics Programmer
>
>
> ------------------------------------------------------------------------------
> Subversion Kills Productivity. Get off Subversion & Make the Move to
> Perforce.
> With Perforce, you get hassle-free workflows. Merge that actually works.
> Faster operations. Version large binaries.  Built-in WAN optimization and
> the
> freedom to use Git, Perforce or both. Make the move to Perforce.
>
> http://pubads.g.doubleclick.net/gampad/clk?id=122218951&iu=/4140/ostg.clktrk
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>



-- 
fabs();
"The fact that an opinion has been widely held is no evidence whatever that
it is not utterly absurd." - Bertrand Russell

Re: [Algorithms] sparse bitset compression

[Colt McAnlis <mainroach@gm...>]

Why not just use industry standard Arithmetic Compression?

If you calculate the estimated entropy for that data set (
http://planetcalc.com/2476/) you end up with about H=0.06 for 7k set bits
in a 1024*1024 stream, and H=0.01 for 1k set bits.
That being entropy (or minimum bits per symbol) should yield 70kb and 10k
after compression, respectively. Or, with AC, and those sparse values, you
can get around 94% compression and 99% compression. (if my early morning
math is right)

AC is a known algorithm, easy examples to find on the web. And as far a
serialization is concerned, it's pretty straight forward to just encode
your bits, then decode; no extra special data structures needed.

~Main


On Fri, Jan 31, 2014 at 3:27 PM, Richard Fabian <raspo1@...> wrote:

> there was a lot of similarity, but with no processng at the destination,
> we decided that the Golomb-rice algorithm was good enough. Dropped our data
> by 70%. That was enough of a saving for this one area.
>
>
> On 31 January 2014 21:32, Jon Watte <jwatte@...> wrote:
>
>> Encode a single starting value at full bandwidth then send a stream of
>>> differences:
>>
>>
>> Which is equivalent to a wavelet "lift" transform :-)
>>
>> Back to the original question: If you have a previous save game, is there
>> lots of similarity in the next save? If so, can you save a delta instead?
>> If not, what solution did you end up choosing?
>>
>> Sincerely,
>>
>> jw
>>
>>
>>
>>
>>
>>
>> Sincerely,
>>
>> Jon Watte
>>
>>
>> --
>> "I find that the harder I work, the more luck I seem to have." -- Thomas
>> Jefferson
>>
>>
>> On Tue, Jan 21, 2014 at 12:08 AM, Robin Green <robin.green@...>wrote:
>>
>>>
>>> Here's a modern Run Length version of Golomb-Rice encoding designed for
>>> compressing general data with a Generalized Gaussian distribution. Works
>>> best if you can prove there are, in most cases, small differences between
>>> adjacent data (but handily you get to define what "adjacent" means to your
>>> stream). Encode a single starting value at full bandwidth then send a
>>> stream of differences:
>>>
>>>     https://research.microsoft.com/pubs/102069/malvar_dcc06.pdf
>>>
>>> As a bonus, if you're encoding depth images, you can remap the values to
>>> leave zero as an out-of-band value:
>>>
>>>     http://www.charlesneedham.com/pubs/153971/depthcode-final.pdf
>>>
>>> Yes, I know that wasn't the question you asked but at least it's an
>>> algorithm. :-)
>>>
>>> - Robin Green
>>>
>>>
>>>
>>> On Fri, Jan 17, 2014 at 10:04 AM, Alex Walters <ajw.walters@...>wrote:
>>>
>>>> Its on the fringe of being useful, but one thing you could look at to
>>>> reduce your data size is Exponential Golomb coding (
>>>> http://en.wikipedia.org/wiki/Exponential-Golomb_coding), its used in
>>>> H.264 entropy encoding among other things.
>>>>
>>>> Instead of writing a full n-bit values for every number you store, it
>>>> produces a bit stream of codes, using far less bits for small numbers -
>>>> take a look at the wiki page, its pretty simple to see whats going on when
>>>> you look at the example. It can reduce the amount of data you have to move,
>>>> and from what I remember from when I worked with video, it produces much
>>>> more predictable (and compressible) stream of bits for the next compression
>>>> scheme along (variable length encoding, or arithmetic encoding in the case
>>>> of H.264) - I've not looked into the details but could probably improve the
>>>> compression of the stream you get through gzip.
>>>>
>>>> Regards,
>>>>
>>>> Alex
>>>>
>>>>
>>>>
>>>
>>> ------------------------------------------------------------------------------
>>> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
>>> Learn Why More Businesses Are Choosing CenturyLink Cloud For
>>> Critical Workloads, Development Environments & Everything In Between.
>>> Get a Quote or Start a Free Trial Today.
>>>
>>> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk
>>> _______________________________________________
>>> GDAlgorithms-list mailing list
>>> GDAlgorithms-list@...
>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>> Archives:
>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>>
>>
>>
>>
>> ------------------------------------------------------------------------------
>> WatchGuard Dimension instantly turns raw network data into actionable
>> security intelligence. It gives you real-time visual feedback on key
>> security issues and trends.  Skip the complicated setup - simply import
>> a virtual appliance and go from zero to informed in seconds.
>>
>> http://pubads.g.doubleclick.net/gampad/clk?id=123612991&iu=/4140/ostg.clktrk
>>
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDAlgorithms-list@...
>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> Archives:
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>
>
>
>
> --
> fabs();
> "The fact that an opinion has been widely held is no evidence whatever
> that it is not utterly absurd." - Bertrand Russell
>
>
> ------------------------------------------------------------------------------
> WatchGuard Dimension instantly turns raw network data into actionable
> security intelligence. It gives you real-time visual feedback on key
> security issues and trends.  Skip the complicated setup - simply import
> a virtual appliance and go from zero to informed in seconds.
>
> http://pubads.g.doubleclick.net/gampad/clk?id=123612991&iu=/4140/ostg.clktrk
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>



-- 
==
Colt "MainRoach" McAnlis
Graphics Programmer

Re: [Algorithms] sparse bitset compression

[Richard Fabian <raspo1@gm...>]

there was a lot of similarity, but with no processng at the destination, we
decided that the Golomb-rice algorithm was good enough. Dropped our data by
70%. That was enough of a saving for this one area.


On 31 January 2014 21:32, Jon Watte <jwatte@...> wrote:

> Encode a single starting value at full bandwidth then send a stream of
>> differences:
>
>
> Which is equivalent to a wavelet "lift" transform :-)
>
> Back to the original question: If you have a previous save game, is there
> lots of similarity in the next save? If so, can you save a delta instead?
> If not, what solution did you end up choosing?
>
> Sincerely,
>
> jw
>
>
>
>
>
>
> Sincerely,
>
> Jon Watte
>
>
> --
> "I find that the harder I work, the more luck I seem to have." -- Thomas
> Jefferson
>
>
> On Tue, Jan 21, 2014 at 12:08 AM, Robin Green <robin.green@...>wrote:
>
>>
>> Here's a modern Run Length version of Golomb-Rice encoding designed for
>> compressing general data with a Generalized Gaussian distribution. Works
>> best if you can prove there are, in most cases, small differences between
>> adjacent data (but handily you get to define what "adjacent" means to your
>> stream). Encode a single starting value at full bandwidth then send a
>> stream of differences:
>>
>>     https://research.microsoft.com/pubs/102069/malvar_dcc06.pdf
>>
>> As a bonus, if you're encoding depth images, you can remap the values to
>> leave zero as an out-of-band value:
>>
>>     http://www.charlesneedham.com/pubs/153971/depthcode-final.pdf
>>
>> Yes, I know that wasn't the question you asked but at least it's an
>> algorithm. :-)
>>
>> - Robin Green
>>
>>
>>
>> On Fri, Jan 17, 2014 at 10:04 AM, Alex Walters <ajw.walters@...>wrote:
>>
>>> Its on the fringe of being useful, but one thing you could look at to
>>> reduce your data size is Exponential Golomb coding (
>>> http://en.wikipedia.org/wiki/Exponential-Golomb_coding), its used in
>>> H.264 entropy encoding among other things.
>>>
>>> Instead of writing a full n-bit values for every number you store, it
>>> produces a bit stream of codes, using far less bits for small numbers -
>>> take a look at the wiki page, its pretty simple to see whats going on when
>>> you look at the example. It can reduce the amount of data you have to move,
>>> and from what I remember from when I worked with video, it produces much
>>> more predictable (and compressible) stream of bits for the next compression
>>> scheme along (variable length encoding, or arithmetic encoding in the case
>>> of H.264) - I've not looked into the details but could probably improve the
>>> compression of the stream you get through gzip.
>>>
>>> Regards,
>>>
>>> Alex
>>>
>>>
>>>
>>
>> ------------------------------------------------------------------------------
>> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
>> Learn Why More Businesses Are Choosing CenturyLink Cloud For
>> Critical Workloads, Development Environments & Everything In Between.
>> Get a Quote or Start a Free Trial Today.
>>
>> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDAlgorithms-list@...
>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> Archives:
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>
>
>
>
> ------------------------------------------------------------------------------
> WatchGuard Dimension instantly turns raw network data into actionable
> security intelligence. It gives you real-time visual feedback on key
> security issues and trends.  Skip the complicated setup - simply import
> a virtual appliance and go from zero to informed in seconds.
>
> http://pubads.g.doubleclick.net/gampad/clk?id=123612991&iu=/4140/ostg.clktrk
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>



-- 
fabs();
"The fact that an opinion has been widely held is no evidence whatever that
it is not utterly absurd." - Bertrand Russell

Re: [Algorithms] sparse bitset compression

[Jon Watte <jwatte@gm...>]

>
> Encode a single starting value at full bandwidth then send a stream of
> differences:


Which is equivalent to a wavelet "lift" transform :-)

Back to the original question: If you have a previous save game, is there
lots of similarity in the next save? If so, can you save a delta instead?
If not, what solution did you end up choosing?

Sincerely,

jw






Sincerely,

Jon Watte


--
"I find that the harder I work, the more luck I seem to have." -- Thomas
Jefferson


On Tue, Jan 21, 2014 at 12:08 AM, Robin Green <robin.green@...> wrote:

>
> Here's a modern Run Length version of Golomb-Rice encoding designed for
> compressing general data with a Generalized Gaussian distribution. Works
> best if you can prove there are, in most cases, small differences between
> adjacent data (but handily you get to define what "adjacent" means to your
> stream). Encode a single starting value at full bandwidth then send a
> stream of differences:
>
>     https://research.microsoft.com/pubs/102069/malvar_dcc06.pdf
>
> As a bonus, if you're encoding depth images, you can remap the values to
> leave zero as an out-of-band value:
>
>     http://www.charlesneedham.com/pubs/153971/depthcode-final.pdf
>
> Yes, I know that wasn't the question you asked but at least it's an
> algorithm. :-)
>
> - Robin Green
>
>
>
> On Fri, Jan 17, 2014 at 10:04 AM, Alex Walters <ajw.walters@...>wrote:
>
>> Its on the fringe of being useful, but one thing you could look at to
>> reduce your data size is Exponential Golomb coding (
>> http://en.wikipedia.org/wiki/Exponential-Golomb_coding), its used in
>> H.264 entropy encoding among other things.
>>
>> Instead of writing a full n-bit values for every number you store, it
>> produces a bit stream of codes, using far less bits for small numbers -
>> take a look at the wiki page, its pretty simple to see whats going on when
>> you look at the example. It can reduce the amount of data you have to move,
>> and from what I remember from when I worked with video, it produces much
>> more predictable (and compressible) stream of bits for the next compression
>> scheme along (variable length encoding, or arithmetic encoding in the case
>> of H.264) - I've not looked into the details but could probably improve the
>> compression of the stream you get through gzip.
>>
>> Regards,
>>
>> Alex
>>
>>
>>
>
> ------------------------------------------------------------------------------
> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
> Learn Why More Businesses Are Choosing CenturyLink Cloud For
> Critical Workloads, Development Environments & Everything In Between.
> Get a Quote or Start a Free Trial Today.
>
> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

Re: [Algorithms] sparse bitset compression

[Robin Green <robin.green@gm...>]

Here's a modern Run Length version of Golomb-Rice encoding designed for
compressing general data with a Generalized Gaussian distribution. Works
best if you can prove there are, in most cases, small differences between
adjacent data (but handily you get to define what "adjacent" means to your
stream). Encode a single starting value at full bandwidth then send a
stream of differences:

    https://research.microsoft.com/pubs/102069/malvar_dcc06.pdf

As a bonus, if you're encoding depth images, you can remap the values to
leave zero as an out-of-band value:

    http://www.charlesneedham.com/pubs/153971/depthcode-final.pdf

Yes, I know that wasn't the question you asked but at least it's an
algorithm. :-)

- Robin Green



On Fri, Jan 17, 2014 at 10:04 AM, Alex Walters <ajw.walters@...>wrote:

> Its on the fringe of being useful, but one thing you could look at to
> reduce your data size is Exponential Golomb coding (
> http://en.wikipedia.org/wiki/Exponential-Golomb_coding), its used in
> H.264 entropy encoding among other things.
>
> Instead of writing a full n-bit values for every number you store, it
> produces a bit stream of codes, using far less bits for small numbers -
> take a look at the wiki page, its pretty simple to see whats going on when
> you look at the example. It can reduce the amount of data you have to move,
> and from what I remember from when I worked with video, it produces much
> more predictable (and compressible) stream of bits for the next compression
> scheme along (variable length encoding, or arithmetic encoding in the case
> of H.264) - I've not looked into the details but could probably improve the
> compression of the stream you get through gzip.
>
> Regards,
>
> Alex
>
>
>

Re: [Algorithms] sparse bitset compression

[Richard Fabian <raspo1@gm...>]

hah, that was funny. I looked at the link, then realised that it was the
same as what I'm doing except I pack with ones instead of zeros.
0 -> 0
100 -> 1
101 -> 2
11000 -> 3
etc.
I'm pretty sure i read about this in a jpeg compression book more than 10
years ago.


On 17 January 2014 18:04, Alex Walters <ajw.walters@...> wrote:

> Its on the fringe of being useful, but one thing you could look at to
> reduce your data size is Exponential Golomb coding (
> http://en.wikipedia.org/wiki/Exponential-Golomb_coding), its used in
> H.264 entropy encoding among other things.
>
> Instead of writing a full n-bit values for every number you store, it
> produces a bit stream of codes, using far less bits for small numbers -
> take a look at the wiki page, its pretty simple to see whats going on when
> you look at the example. It can reduce the amount of data you have to move,
> and from what I remember from when I worked with video, it produces much
> more predictable (and compressible) stream of bits for the next compression
> scheme along (variable length encoding, or arithmetic encoding in the case
> of H.264) - I've not looked into the details but could probably improve the
> compression of the stream you get through gzip.
>
> Regards,
>
> Alex
>
>
> On Fri, Jan 17, 2014 at 10:14 AM, Richard Fabian <raspo1@...> wrote:
>
>> I would question this assumption:
>>>
>>> This is too much for sending over the network regularly as part of a
>>>> save.
>>>
>>>
>>>
>>
>> Well, we've got our play-through logs showing how much data was being
>> sent per day per user, and this part of the save was the bit being updated
>> the most. Over a day of play it was adding up to about 5mb I think (can't
>> remember precisely now) and this made it into the top three we needed to
>> compress better to reduce the client bandwidth cost (mobile carrier data
>> limits and all that).
>>
>>
>>
>>> If I had to compress the data you talk about, I might want to look into
>>> some implicit representation, like a quad tree with filled/not nodes.
>>> Something like:
>>> "Does the current sub-area have entities? If not, store 0, and
>>> terminate. Else store 1. If the size of the sub-area is greater than one,
>>> subdivide, and recurse for each sub-quadrant."
>>> Depending on how clustered the entities are, this may compress well or
>>> poorly (but with a max 7% fill rate, it ought to at least compress
>>> somewhat.)
>>>
>>
>> I had thought about a quad tree, but I think I chose to not go that way
>> because my previous experience with them was that they're not quite as
>> efficient in practice as the should be. I can't remember why I think this,
>> but I remember working through some code and thinking something along the
>> lines of "Oh, yeah. Of course" but that might have been because the data
>> involved wasn't quite as clumpy.
>>
>>
>>> Apply gzip on top of any encoding you come up with for possible bonus
>>> gains.
>>>
>>> that's part of the network layer, so no point in doing it explicitly.
>>
>>
>>> Sincerely,
>>>
>>> jw
>>>
>>>
>>> Thanks, I might try the quad tree idea again.
>>
>>
>> ------------------------------------------------------------------------------
>> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
>> Learn Why More Businesses Are Choosing CenturyLink Cloud For
>> Critical Workloads, Development Environments & Everything In Between.
>> Get a Quote or Start a Free Trial Today.
>>
>> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDAlgorithms-list@...
>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> Archives:
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>
>
>
>
> ------------------------------------------------------------------------------
> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
> Learn Why More Businesses Are Choosing CenturyLink Cloud For
> Critical Workloads, Development Environments & Everything In Between.
> Get a Quote or Start a Free Trial Today.
>
> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>



-- 
fabs();
"The fact that an opinion has been widely held is no evidence whatever that
it is not utterly absurd." - Bertrand Russell

Re: [Algorithms] sparse bitset compression

[Samuel Moll <samimoll@go...>]

Another Idea that might be useful is to think of your positions
dataset as a black-and white 1024*1024 bitmap (This gets harder if two
entities are allowed to occupy the same position) and compress it with
some sort of run-length-encoding, i.e. you go through each pixel line
from left to right and instead of saving 0s (for empty space) and 1s
(for occupied pixels), you save how many 0s there are until the next
1.

On 1/17/14, Alex Walters <ajw.walters@...> wrote:
> Its on the fringe of being useful, but one thing you could look at to
> reduce your data size is Exponential Golomb coding (
> http://en.wikipedia.org/wiki/Exponential-Golomb_coding), its used in H.264
> entropy encoding among other things.
>
> Instead of writing a full n-bit values for every number you store, it
> produces a bit stream of codes, using far less bits for small numbers -
> take a look at the wiki page, its pretty simple to see whats going on when
> you look at the example. It can reduce the amount of data you have to move,
> and from what I remember from when I worked with video, it produces much
> more predictable (and compressible) stream of bits for the next compression
> scheme along (variable length encoding, or arithmetic encoding in the case
> of H.264) - I've not looked into the details but could probably improve the
> compression of the stream you get through gzip.
>
> Regards,
>
> Alex
>
>
> On Fri, Jan 17, 2014 at 10:14 AM, Richard Fabian <raspo1@...> wrote:
>
>> I would question this assumption:
>>>
>>> This is too much for sending over the network regularly as part of a
>>> save.
>>>
>>>
>>>
>>
>> Well, we've got our play-through logs showing how much data was being
>> sent
>> per day per user, and this part of the save was the bit being updated the
>> most. Over a day of play it was adding up to about 5mb I think (can't
>> remember precisely now) and this made it into the top three we needed to
>> compress better to reduce the client bandwidth cost (mobile carrier data
>> limits and all that).
>>
>>
>>
>>> If I had to compress the data you talk about, I might want to look into
>>> some implicit representation, like a quad tree with filled/not nodes.
>>> Something like:
>>> "Does the current sub-area have entities? If not, store 0, and
>>> terminate.
>>> Else store 1. If the size of the sub-area is greater than one,
>>> subdivide,
>>> and recurse for each sub-quadrant."
>>> Depending on how clustered the entities are, this may compress well or
>>> poorly (but with a max 7% fill rate, it ought to at least compress
>>> somewhat.)
>>>
>>
>> I had thought about a quad tree, but I think I chose to not go that way
>> because my previous experience with them was that they're not quite as
>> efficient in practice as the should be. I can't remember why I think
>> this,
>> but I remember working through some code and thinking something along the
>> lines of "Oh, yeah. Of course" but that might have been because the data
>> involved wasn't quite as clumpy.
>>
>>
>>> Apply gzip on top of any encoding you come up with for possible bonus
>>> gains.
>>>
>>> that's part of the network layer, so no point in doing it explicitly.
>>
>>
>>> Sincerely,
>>>
>>> jw
>>>
>>>
>>> Thanks, I might try the quad tree idea again.
>>
>>
>> ------------------------------------------------------------------------------
>> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
>> Learn Why More Businesses Are Choosing CenturyLink Cloud For
>> Critical Workloads, Development Environments & Everything In Between.
>> Get a Quote or Start a Free Trial Today.
>>
>> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDAlgorithms-list@...
>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> Archives:
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>
>

Re: [Algorithms] sparse bitset compression

[Alex Walters <ajw.walters@gm...>]

Its on the fringe of being useful, but one thing you could look at to
reduce your data size is Exponential Golomb coding (
http://en.wikipedia.org/wiki/Exponential-Golomb_coding), its used in H.264
entropy encoding among other things.

Instead of writing a full n-bit values for every number you store, it
produces a bit stream of codes, using far less bits for small numbers -
take a look at the wiki page, its pretty simple to see whats going on when
you look at the example. It can reduce the amount of data you have to move,
and from what I remember from when I worked with video, it produces much
more predictable (and compressible) stream of bits for the next compression
scheme along (variable length encoding, or arithmetic encoding in the case
of H.264) - I've not looked into the details but could probably improve the
compression of the stream you get through gzip.

Regards,

Alex


On Fri, Jan 17, 2014 at 10:14 AM, Richard Fabian <raspo1@...> wrote:

> I would question this assumption:
>>
>> This is too much for sending over the network regularly as part of a save.
>>
>>
>>
>
> Well, we've got our play-through logs showing how much data was being sent
> per day per user, and this part of the save was the bit being updated the
> most. Over a day of play it was adding up to about 5mb I think (can't
> remember precisely now) and this made it into the top three we needed to
> compress better to reduce the client bandwidth cost (mobile carrier data
> limits and all that).
>
>
>
>> If I had to compress the data you talk about, I might want to look into
>> some implicit representation, like a quad tree with filled/not nodes.
>> Something like:
>> "Does the current sub-area have entities? If not, store 0, and terminate.
>> Else store 1. If the size of the sub-area is greater than one, subdivide,
>> and recurse for each sub-quadrant."
>> Depending on how clustered the entities are, this may compress well or
>> poorly (but with a max 7% fill rate, it ought to at least compress
>> somewhat.)
>>
>
> I had thought about a quad tree, but I think I chose to not go that way
> because my previous experience with them was that they're not quite as
> efficient in practice as the should be. I can't remember why I think this,
> but I remember working through some code and thinking something along the
> lines of "Oh, yeah. Of course" but that might have been because the data
> involved wasn't quite as clumpy.
>
>
>> Apply gzip on top of any encoding you come up with for possible bonus
>> gains.
>>
>> that's part of the network layer, so no point in doing it explicitly.
>
>
>> Sincerely,
>>
>> jw
>>
>>
>> Thanks, I might try the quad tree idea again.
>
>
> ------------------------------------------------------------------------------
> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
> Learn Why More Businesses Are Choosing CenturyLink Cloud For
> Critical Workloads, Development Environments & Everything In Between.
> Get a Quote or Start a Free Trial Today.
>
> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

Re: [Algorithms] sparse bitset compression

[Richard Fabian <raspo1@gm...>]

>
> I would question this assumption:
>
> This is too much for sending over the network regularly as part of a save.
>
>
>

Well, we've got our play-through logs showing how much data was being sent
per day per user, and this part of the save was the bit being updated the
most. Over a day of play it was adding up to about 5mb I think (can't
remember precisely now) and this made it into the top three we needed to
compress better to reduce the client bandwidth cost (mobile carrier data
limits and all that).



> If I had to compress the data you talk about, I might want to look into
> some implicit representation, like a quad tree with filled/not nodes.
> Something like:
> "Does the current sub-area have entities? If not, store 0, and terminate.
> Else store 1. If the size of the sub-area is greater than one, subdivide,
> and recurse for each sub-quadrant."
> Depending on how clustered the entities are, this may compress well or
> poorly (but with a max 7% fill rate, it ought to at least compress
> somewhat.)
>

I had thought about a quad tree, but I think I chose to not go that way
because my previous experience with them was that they're not quite as
efficient in practice as the should be. I can't remember why I think this,
but I remember working through some code and thinking something along the
lines of "Oh, yeah. Of course" but that might have been because the data
involved wasn't quite as clumpy.


> Apply gzip on top of any encoding you come up with for possible bonus
> gains.
>
> that's part of the network layer, so no point in doing it explicitly.


> Sincerely,
>
> jw
>
>
> Thanks, I might try the quad tree idea again.

Re: [Algorithms] sparse bitset compression

[Jon Watte <jwatte@gm...>]

I would question this assumption:

This is too much for sending over the network regularly as part of a save.


How often do you send the savegame? 7k entities, times 20 bits, equals less
than 18 kB of data.
By comparison, the amount of cookie and image data involved in a single
mouseover-and-click event in a web browser these days is probably about
that same size.
Are you saying that your save data must be more lightweight than a mouse
click? Where does this limitation come from? Are you targeting a modem
where a 5 second background upload is not acceptable?

If I had to compress the data you talk about, I might want to look into
some implicit representation, like a quad tree with filled/not nodes.
Something like:
"Does the current sub-area have entities? If not, store 0, and terminate.
Else store 1. If the size of the sub-area is greater than one, subdivide,
and recurse for each sub-quadrant."
Depending on how clustered the entities are, this may compress well or
poorly (but with a max 7% fill rate, it ought to at least compress
somewhat.)

Apply gzip on top of any encoding you come up with for possible bonus gains.

Sincerely,

jw






Sincerely,

Jon Watte


--
"I pledge allegiance to the flag of the United States of America, and to
the republic for which it stands, one nation indivisible, with liberty and
justice for all."
~ Adopted by U.S. Congress, June 22, 1942


On Tue, Jan 14, 2014 at 4:37 AM, Richard Fabian <raspo1@...> wrote:

> The web is full of different solutions for compressing things, but some of
> you have probably already done this and found a really good ratio
> compression scheme that fits what I'm asking about.
>
> I've got a load of entites, (4-7k) that live on a grid (1024x1024), and I
> need to persist them to a savegame which gets sent across the network to
> keep the save safe. I need to compress it. I'm compressing the entities in
> the world already, ones that have been affected cost a few bytes, but the
> but for the ones that don't have any changes, all I'm left with is the
> coords. There are only a few that need the fatter compression, but at the
> numbers I'm looking at, those "unchanged entity" coords add up to a lot of
> data when storing as 20 bit structs. This is too much for sending over the
> network regularly as part of a save.
>
> I've had some ideas on how to compress the data, but they might be crap. I
> don't know.
>
> I can't easily regenerate the set so thought someone who wanted to
> compress consumables might know the name of a good solution for sparse
> bitset compression. The bits are clumped around different areas of the
> grid, so I feel that something that leverages spatial coherence might do
> well.
>
> Any leads would be highly appreciated.
>
> --
> fabs();
> "The fact that an opinion has been widely held is no evidence whatever
> that it is not utterly absurd." - Bertrand Russell
>
>
> ------------------------------------------------------------------------------
> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
> Learn Why More Businesses Are Choosing CenturyLink Cloud For
> Critical Workloads, Development Environments & Everything In Between.
> Get a Quote or Start a Free Trial Today.
>
> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

Re: [Algorithms] sparse bitset compression

[Richard Fabian <raspo1@gm...>]

I was going to plug in the morten coded version. Code from ryg's blog.

http://fgiesen.wordpress.com/2009/12/13/decoding-morton-codes/


On 14 January 2014 19:11, Chris Birke <cbirke@...> wrote:

> You might also look into morton order encoding, as it is a simple and
> efficient locality preserving way to do lossless n dimensional tree
> structures - this is of course best for applications like map data. Your
> mileage may vary.
>
> -Chria
>
> ἀπὸ μηχανῆς iPhone 5
>
> On Jan 14, 2014, at 9:01 AM, Oscar Forth <oscar@...>
> wrote:
>
> Pretty much.
>
> The space filling curve might not be necessary but you may be able to use
> it to keep smaller gaps between the entries which are local to each other
> spatially.
>
>
> On 14 January 2014 16:52, Richard Fabian <raspo1@...> wrote:
>
>> That sounds good. Something like the JPEG VLC for the actual distance
>> between entries and just store deltas on a space filling curve should be
>> good then.
>>
>>
>> On 14 January 2014 13:11, Oscar Forth <oscar@...>wrote:
>>
>>> Just a random though, so apologies if i'm talking about my arse, but ...
>>> couldn't you just use something like the bit plane compression from Wavelet
>>> Difference Reduction (WDR)?
>>>
>>> A lot depends on your data, I appreciate, so this may not work out as
>>> any significant saving ...
>>>
>>> I wrote about the compression method in my blog a few years back:
>>>
>>> http://trueharmoniccolours.co.uk/Blog/?p=55
>>>
>>> Obviously thats in the context of a full wavelet image compressor so you
>>> will have to just grab the part I explain in the link above.
>>>
>>> Also apologies for the code formatting on my blog ... ill fix it one day
>>> ;)
>>>
>>> Oscar
>>>
>>> On 14 January 2014 12:37, Richard Fabian <raspo1@...> wrote:
>>>
>>>> The web is full of different solutions for compressing things, but some
>>>> of you have probably already done this and found a really good ratio
>>>> compression scheme that fits what I'm asking about.
>>>>
>>>> I've got a load of entites, (4-7k) that live on a grid (1024x1024), and
>>>> I need to persist them to a savegame which gets sent across the network to
>>>> keep the save safe. I need to compress it. I'm compressing the entities in
>>>> the world already, ones that have been affected cost a few bytes, but the
>>>> but for the ones that don't have any changes, all I'm left with is the
>>>> coords. There are only a few that need the fatter compression, but at the
>>>> numbers I'm looking at, those "unchanged entity" coords add up to a lot of
>>>> data when storing as 20 bit structs. This is too much for sending over the
>>>> network regularly as part of a save.
>>>>
>>>> I've had some ideas on how to compress the data, but they might be
>>>> crap. I don't know.
>>>>
>>>> I can't easily regenerate the set so thought someone who wanted to
>>>> compress consumables might know the name of a good solution for sparse
>>>> bitset compression. The bits are clumped around different areas of the
>>>> grid, so I feel that something that leverages spatial coherence might do
>>>> well.
>>>>
>>>> Any leads would be highly appreciated.
>>>>
>>>> --
>>>> fabs();
>>>> "The fact that an opinion has been widely held is no evidence whatever
>>>> that it is not utterly absurd." - Bertrand Russell
>>>>
>>>>
>>>> ------------------------------------------------------------------------------
>>>> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
>>>> Learn Why More Businesses Are Choosing CenturyLink Cloud For
>>>> Critical Workloads, Development Environments & Everything In Between.
>>>> Get a Quote or Start a Free Trial Today.
>>>>
>>>> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk
>>>> _______________________________________________
>>>> GDAlgorithms-list mailing list
>>>> GDAlgorithms-list@...
>>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>>> Archives:
>>>>
>>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>>>
>>>
>>>
>>>
>>> ------------------------------------------------------------------------------
>>> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
>>> Learn Why More Businesses Are Choosing CenturyLink Cloud For
>>> Critical Workloads, Development Environments & Everything In Between.
>>> Get a Quote or Start a Free Trial Today.
>>>
>>> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk
>>> _______________________________________________
>>> GDAlgorithms-list mailing list
>>> GDAlgorithms-list@...
>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>> Archives:
>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>>
>>
>>
>>
>> --
>> fabs();
>> "The fact that an opinion has been widely held is no evidence whatever
>> that it is not utterly absurd." - Bertrand Russell
>>
>>
>> ------------------------------------------------------------------------------
>> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
>> Learn Why More Businesses Are Choosing CenturyLink Cloud For
>> Critical Workloads, Development Environments & Everything In Between.
>> Get a Quote or Start a Free Trial Today.
>>
>> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDAlgorithms-list@...
>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> Archives:
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>
>
>
> ------------------------------------------------------------------------------
> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
> Learn Why More Businesses Are Choosing CenturyLink Cloud For
> Critical Workloads, Development Environments & Everything In Between.
> Get a Quote or Start a Free Trial Today.
>
> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>
>
>
> ------------------------------------------------------------------------------
> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
> Learn Why More Businesses Are Choosing CenturyLink Cloud For
> Critical Workloads, Development Environments & Everything In Between.
> Get a Quote or Start a Free Trial Today.
>
> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>



-- 
fabs();
"The fact that an opinion has been widely held is no evidence whatever that
it is not utterly absurd." - Bertrand Russell

Re: [Algorithms] sparse bitset compression

[Chris Birke <cbirke@gm...>]

You might also look into morton order encoding, as it is a simple and efficient locality preserving way to do lossless n dimensional tree structures - this is of course best for applications like map data. Your mileage may vary.

-Chria

ἀπὸ μηχανῆς iPhone 5

> On Jan 14, 2014, at 9:01 AM, Oscar Forth <oscar@...> wrote:
> 
> Pretty much.  
> 
> The space filling curve might not be necessary but you may be able to use it to keep smaller gaps between the entries which are local to each other spatially.
> 
> 
>> On 14 January 2014 16:52, Richard Fabian <raspo1@...> wrote:
>> That sounds good. Something like the JPEG VLC for the actual distance between entries and just store deltas on a space filling curve should be good then.
>> 
>> 
>>> On 14 January 2014 13:11, Oscar Forth <oscar@...> wrote:
>>> Just a random though, so apologies if i'm talking about my arse, but ... couldn't you just use something like the bit plane compression from Wavelet Difference Reduction (WDR)?
>>> 
>>> A lot depends on your data, I appreciate, so this may not work out as any significant saving ...
>>> 
>>> I wrote about the compression method in my blog a few years back:
>>> 
>>> http://trueharmoniccolours.co.uk/Blog/?p=55
>>> 
>>> Obviously thats in the context of a full wavelet image compressor so you will have to just grab the part I explain in the link above.
>>> 
>>> Also apologies for the code formatting on my blog ... ill fix it one day ;)
>>> 
>>> Oscar
>>> 
>>>> On 14 January 2014 12:37, Richard Fabian <raspo1@...> wrote:
>>>> The web is full of different solutions for compressing things, but some of you have probably already done this and found a really good ratio compression scheme that fits what I'm asking about.
>>>> 
>>>> I've got a load of entites, (4-7k) that live on a grid (1024x1024), and I need to persist them to a savegame which gets sent across the network to keep the save safe. I need to compress it. I'm compressing the entities in the world already, ones that have been affected cost a few bytes, but the but for the ones that don't have any changes, all I'm left with is the coords. There are only a few that need the fatter compression, but at the numbers I'm looking at, those "unchanged entity" coords add up to a lot of data when storing as 20 bit structs. This is too much for sending over the network regularly as part of a save.
>>>> 
>>>> I've had some ideas on how to compress the data, but they might be crap. I don't know.
>>>> 
>>>> I can't easily regenerate the set so thought someone who wanted to compress consumables might know the name of a good solution for sparse bitset compression. The bits are clumped around different areas of the grid, so I feel that something that leverages spatial coherence might do well.
>>>> 
>>>> Any leads would be highly appreciated.
>>>> 
>>>> -- 
>>>> fabs();
>>>> "The fact that an opinion has been widely held is no evidence whatever that it is not utterly absurd." - Bertrand Russell
>>>> 
>>>> ------------------------------------------------------------------------------
>>>> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
>>>> Learn Why More Businesses Are Choosing CenturyLink Cloud For
>>>> Critical Workloads, Development Environments & Everything In Between.
>>>> Get a Quote or Start a Free Trial Today.
>>>> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk
>>>> _______________________________________________
>>>> GDAlgorithms-list mailing list
>>>> GDAlgorithms-list@...
>>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>>> Archives:
>>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>> 
>>> 
>>> ------------------------------------------------------------------------------
>>> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
>>> Learn Why More Businesses Are Choosing CenturyLink Cloud For
>>> Critical Workloads, Development Environments & Everything In Between.
>>> Get a Quote or Start a Free Trial Today.
>>> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk
>>> _______________________________________________
>>> GDAlgorithms-list mailing list
>>> GDAlgorithms-list@...
>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>> Archives:
>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>> 
>> 
>> 
>> -- 
>> fabs();
>> "The fact that an opinion has been widely held is no evidence whatever that it is not utterly absurd." - Bertrand Russell
>> 
>> ------------------------------------------------------------------------------
>> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
>> Learn Why More Businesses Are Choosing CenturyLink Cloud For
>> Critical Workloads, Development Environments & Everything In Between.
>> Get a Quote or Start a Free Trial Today.
>> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDAlgorithms-list@...
>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> Archives:
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
> 
> ------------------------------------------------------------------------------
> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
> Learn Why More Businesses Are Choosing CenturyLink Cloud For
> Critical Workloads, Development Environments & Everything In Between.
> Get a Quote or Start a Free Trial Today. 
> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] sparse bitset compression

[Oscar Forth <oscar@tr...>]

Pretty much.

The space filling curve might not be necessary but you may be able to use
it to keep smaller gaps between the entries which are local to each other
spatially.


On 14 January 2014 16:52, Richard Fabian <raspo1@...> wrote:

> That sounds good. Something like the JPEG VLC for the actual distance
> between entries and just store deltas on a space filling curve should be
> good then.
>
>
> On 14 January 2014 13:11, Oscar Forth <oscar@...>wrote:
>
>> Just a random though, so apologies if i'm talking about my arse, but ...
>> couldn't you just use something like the bit plane compression from Wavelet
>> Difference Reduction (WDR)?
>>
>> A lot depends on your data, I appreciate, so this may not work out as any
>> significant saving ...
>>
>> I wrote about the compression method in my blog a few years back:
>>
>> http://trueharmoniccolours.co.uk/Blog/?p=55
>>
>> Obviously thats in the context of a full wavelet image compressor so you
>> will have to just grab the part I explain in the link above.
>>
>> Also apologies for the code formatting on my blog ... ill fix it one day
>> ;)
>>
>> Oscar
>>
>> On 14 January 2014 12:37, Richard Fabian <raspo1@...> wrote:
>>
>>> The web is full of different solutions for compressing things, but some
>>> of you have probably already done this and found a really good ratio
>>> compression scheme that fits what I'm asking about.
>>>
>>> I've got a load of entites, (4-7k) that live on a grid (1024x1024), and
>>> I need to persist them to a savegame which gets sent across the network to
>>> keep the save safe. I need to compress it. I'm compressing the entities in
>>> the world already, ones that have been affected cost a few bytes, but the
>>> but for the ones that don't have any changes, all I'm left with is the
>>> coords. There are only a few that need the fatter compression, but at the
>>> numbers I'm looking at, those "unchanged entity" coords add up to a lot of
>>> data when storing as 20 bit structs. This is too much for sending over the
>>> network regularly as part of a save.
>>>
>>> I've had some ideas on how to compress the data, but they might be crap.
>>> I don't know.
>>>
>>> I can't easily regenerate the set so thought someone who wanted to
>>> compress consumables might know the name of a good solution for sparse
>>> bitset compression. The bits are clumped around different areas of the
>>> grid, so I feel that something that leverages spatial coherence might do
>>> well.
>>>
>>> Any leads would be highly appreciated.
>>>
>>> --
>>> fabs();
>>> "The fact that an opinion has been widely held is no evidence whatever
>>> that it is not utterly absurd." - Bertrand Russell
>>>
>>>
>>> ------------------------------------------------------------------------------
>>> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
>>> Learn Why More Businesses Are Choosing CenturyLink Cloud For
>>> Critical Workloads, Development Environments & Everything In Between.
>>> Get a Quote or Start a Free Trial Today.
>>>
>>> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk
>>> _______________________________________________
>>> GDAlgorithms-list mailing list
>>> GDAlgorithms-list@...
>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>> Archives:
>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>>
>>
>>
>>
>> ------------------------------------------------------------------------------
>> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
>> Learn Why More Businesses Are Choosing CenturyLink Cloud For
>> Critical Workloads, Development Environments & Everything In Between.
>> Get a Quote or Start a Free Trial Today.
>>
>> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDAlgorithms-list@...
>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> Archives:
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>
>
>
>
> --
> fabs();
> "The fact that an opinion has been widely held is no evidence whatever
> that it is not utterly absurd." - Bertrand Russell
>
>
> ------------------------------------------------------------------------------
> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
> Learn Why More Businesses Are Choosing CenturyLink Cloud For
> Critical Workloads, Development Environments & Everything In Between.
> Get a Quote or Start a Free Trial Today.
>
> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

Re: [Algorithms] sparse bitset compression

[Richard Fabian <raspo1@gm...>]

That sounds good. Something like the JPEG VLC for the actual distance
between entries and just store deltas on a space filling curve should be
good then.


On 14 January 2014 13:11, Oscar Forth <oscar@...>wrote:

> Just a random though, so apologies if i'm talking about my arse, but ...
> couldn't you just use something like the bit plane compression from Wavelet
> Difference Reduction (WDR)?
>
> A lot depends on your data, I appreciate, so this may not work out as any
> significant saving ...
>
> I wrote about the compression method in my blog a few years back:
>
> http://trueharmoniccolours.co.uk/Blog/?p=55
>
> Obviously thats in the context of a full wavelet image compressor so you
> will have to just grab the part I explain in the link above.
>
> Also apologies for the code formatting on my blog ... ill fix it one day ;)
>
> Oscar
>
> On 14 January 2014 12:37, Richard Fabian <raspo1@...> wrote:
>
>> The web is full of different solutions for compressing things, but some
>> of you have probably already done this and found a really good ratio
>> compression scheme that fits what I'm asking about.
>>
>> I've got a load of entites, (4-7k) that live on a grid (1024x1024), and I
>> need to persist them to a savegame which gets sent across the network to
>> keep the save safe. I need to compress it. I'm compressing the entities in
>> the world already, ones that have been affected cost a few bytes, but the
>> but for the ones that don't have any changes, all I'm left with is the
>> coords. There are only a few that need the fatter compression, but at the
>> numbers I'm looking at, those "unchanged entity" coords add up to a lot of
>> data when storing as 20 bit structs. This is too much for sending over the
>> network regularly as part of a save.
>>
>> I've had some ideas on how to compress the data, but they might be crap.
>> I don't know.
>>
>> I can't easily regenerate the set so thought someone who wanted to
>> compress consumables might know the name of a good solution for sparse
>> bitset compression. The bits are clumped around different areas of the
>> grid, so I feel that something that leverages spatial coherence might do
>> well.
>>
>> Any leads would be highly appreciated.
>>
>> --
>> fabs();
>> "The fact that an opinion has been widely held is no evidence whatever
>> that it is not utterly absurd." - Bertrand Russell
>>
>>
>> ------------------------------------------------------------------------------
>> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
>> Learn Why More Businesses Are Choosing CenturyLink Cloud For
>> Critical Workloads, Development Environments & Everything In Between.
>> Get a Quote or Start a Free Trial Today.
>>
>> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDAlgorithms-list@...
>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> Archives:
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>
>
>
>
> ------------------------------------------------------------------------------
> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
> Learn Why More Businesses Are Choosing CenturyLink Cloud For
> Critical Workloads, Development Environments & Everything In Between.
> Get a Quote or Start a Free Trial Today.
>
> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>



-- 
fabs();
"The fact that an opinion has been widely held is no evidence whatever that
it is not utterly absurd." - Bertrand Russell

Re: [Algorithms] sparse bitset compression

[Oscar Forth <oscar@tr...>]

Just a random though, so apologies if i'm talking about my arse, but ...
couldn't you just use something like the bit plane compression from Wavelet
Difference Reduction (WDR)?

A lot depends on your data, I appreciate, so this may not work out as any
significant saving ...

I wrote about the compression method in my blog a few years back:

http://trueharmoniccolours.co.uk/Blog/?p=55

Obviously thats in the context of a full wavelet image compressor so you
will have to just grab the part I explain in the link above.

Also apologies for the code formatting on my blog ... ill fix it one day ;)

Oscar

On 14 January 2014 12:37, Richard Fabian <raspo1@...> wrote:

> The web is full of different solutions for compressing things, but some of
> you have probably already done this and found a really good ratio
> compression scheme that fits what I'm asking about.
>
> I've got a load of entites, (4-7k) that live on a grid (1024x1024), and I
> need to persist them to a savegame which gets sent across the network to
> keep the save safe. I need to compress it. I'm compressing the entities in
> the world already, ones that have been affected cost a few bytes, but the
> but for the ones that don't have any changes, all I'm left with is the
> coords. There are only a few that need the fatter compression, but at the
> numbers I'm looking at, those "unchanged entity" coords add up to a lot of
> data when storing as 20 bit structs. This is too much for sending over the
> network regularly as part of a save.
>
> I've had some ideas on how to compress the data, but they might be crap. I
> don't know.
>
> I can't easily regenerate the set so thought someone who wanted to
> compress consumables might know the name of a good solution for sparse
> bitset compression. The bits are clumped around different areas of the
> grid, so I feel that something that leverages spatial coherence might do
> well.
>
> Any leads would be highly appreciated.
>
> --
> fabs();
> "The fact that an opinion has been widely held is no evidence whatever
> that it is not utterly absurd." - Bertrand Russell
>
>
> ------------------------------------------------------------------------------
> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
> Learn Why More Businesses Are Choosing CenturyLink Cloud For
> Critical Workloads, Development Environments & Everything In Between.
> Get a Quote or Start a Free Trial Today.
>
> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

[Algorithms] sparse bitset compression

[Richard Fabian <raspo1@gm...>]

The web is full of different solutions for compressing things, but some of
you have probably already done this and found a really good ratio
compression scheme that fits what I'm asking about.

I've got a load of entites, (4-7k) that live on a grid (1024x1024), and I
need to persist them to a savegame which gets sent across the network to
keep the save safe. I need to compress it. I'm compressing the entities in
the world already, ones that have been affected cost a few bytes, but the
but for the ones that don't have any changes, all I'm left with is the
coords. There are only a few that need the fatter compression, but at the
numbers I'm looking at, those "unchanged entity" coords add up to a lot of
data when storing as 20 bit structs. This is too much for sending over the
network regularly as part of a save.

I've had some ideas on how to compress the data, but they might be crap. I
don't know.

I can't easily regenerate the set so thought someone who wanted to compress
consumables might know the name of a good solution for sparse bitset
compression. The bits are clumped around different areas of the grid, so I
feel that something that leverages spatial coherence might do well.

Any leads would be highly appreciated.

-- 
fabs();
"The fact that an opinion has been widely held is no evidence whatever that
it is not utterly absurd." - Bertrand Russell

Re: [Algorithms] Texture mip streaming prioritization

[Sebastian Sylvan <sebastian.sylvan@gm...>]

On Mon, Jul 22, 2013 at 7:24 PM, Sebastian Sylvan <
sebastian.sylvan@...> wrote:

>
>
> On Mon, Jul 22, 2013 at 5:21 PM, Josh Green <inbilla@...> wrote:
>
>>
>> Unfortunately the above algorithm looks like it'd be very serial, and
>> involve a bunch of sorts... But I think it might acheive good results?
>>
>
> Seems reasonable. You should of course try to keep your texture requests
> in a priority queue instead of re-sorting in each iteration, and use
> "adjust key"/"decrease key" whenever you decide to drop a MIP level for a
> key. There are heap implementation where this operation is O(1) (e.g.
> Fibonacci heap), so it's at least possible to be efficient (in practice,
> depending on the number of textures, a straight binary heap a la STL may be
> faster due to being less complicated).
>
>

Also, it's worth considering your expectation here. If you intend to keep
enough memory for textures that you'll "almost never" have to turn down a
MIP-loading request, you don't really have to over-think this too much.
Simply loading the lowest-resolution MIP always (taking object visibility
into account) will do a decent job - it's sort of like having a global
resolution clamp and just lowering it until stuff fits in memory, which
won't be optimal, but tends to behave consistently and predictably.


> --
> Sebastian Sylvan
>

Re: [Algorithms] Texture mip streaming prioritization

[Sebastian Sylvan <sebastian.sylvan@gm...>]

On Mon, Jul 22, 2013 at 5:21 PM, Josh Green <inbilla@...> wrote:

>
> Unfortunately the above algorithm looks like it'd be very serial, and
> involve a bunch of sorts... But I think it might acheive good results?
>

Seems reasonable. You should of course try to keep your texture requests in
a priority queue instead of re-sorting in each iteration, and use "adjust
key"/"decrease key" whenever you decide to drop a MIP level for a key.
There are heap implementation where this operation is O(1) (e.g. Fibonacci
heap), so it's at least possible to be efficient (in practice, depending on
the number of textures, a straight binary heap a la STL may be faster due
to being less complicated).


Seb

-- 
Sebastian Sylvan

Re: [Algorithms] Texture mip streaming prioritization

[Jamie Fowlston <jamief@qu...>]

On 23/07/2013 01:21, Josh Green wrote:

<snip>

> Have any of you seen these implementations executed in a product or game
> before? Was it successful? Tricky? worth the time?

We've seen sorting costs for texture prioritization be surprisingly 
high, without doing anything that complex, particularly as you're often 
moving around, priorities change, and you haven't even finished loading 
the mip / texture you wanted to load in the first place (depending on 
hardware, etc.) by the time it's no longer the most important.

Our experience has been that it's not worth over-thinking it. Prioritize 
higher mips close to your points of interest (usually cameras), but 
don't keep too big a queue for low priority things, unless you like 
doing lots of sorting. Once you've started loading something, finish 
loading it; yes, you might bin it soon, but you need some hysteresis in 
the system. Large mips generally are worth seeking and loading on their 
own; small mips may be worth generating from the smallest mip you think 
is worth loading. For our tech, prioritization is configurable via 
plug-ins, so our users can get in and prioritize whatever they think is 
most important, but it's usually just whatever's near the camera (or is 
expected to be near the camera soon). You can do a bit better job if you 
know something about texture density from a pre-process, but it's not 
necessary, particularly if things are built with a reasonably consistent 
texture density.

So I'd build something simple, and see how well it works. Almost never a 
bad way to go about it :)

Jamie

> Thanks for the comments and suggestions so far,
>
> Josh