gdalgorithms-list

Re: [Algorithms] ping

[Super H. <sup...@gm...>]

it does, my guy, it does

On Tue 8. Nov 2022 at 09:50, Marc B. Reynolds <mar...@gm...>
wrote:

> Testing to see if this list still "works".
>
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

[Algorithms] ping

[Marc B. R. <mar...@gm...>]

Testing to see if this list still "works".

Re: [Algorithms] Special cases of Weiler-Atherton

[Andrzej B. <bor...@gm...>]

Yes, I saw this.
And algorithm Greiner-Hormann is similar to this. In base version not
handles special cases, but is extension to special case by Foster and
Overleft. This extension requires computing if point is inside or outside
neighbor polygon. Fortunately is not need computing it for all vertices,
only for first, and vertices which meet intersections points
I don't know which if faster - Greiner-Hormann with special cases or Vatti?

Re: [Algorithms] Special cases of Weiler-Atherton

[<pie...@fr...>]

Hi,

I tried this almost 10 years ago :-)
The algorithm was Ok if I remember well but then I should have worked some float precision issues which I didn't do ;-(

May be this can help
http://pierloic.free.fr/clip/clip.html

-- 
pl


----- Mail original -----
De: "Andrzej Borucki" <bor...@gm...>
À: gda...@li...
Envoyé: Dimanche 23 Novembre 2014 13:30:55
Objet: [Algorithms] Special cases of Weiler-Atherton



I am writing Weiler-Atherton algorithm. I can't find full description of this. 
My source trial is on bitbucket on aborucki/weileratherton, this is unclear of brute_force_intersections() function because I am moving form brute-force to Bentley-Ottmann sweep line intersections. 
I have two main rountines: 
brute_force_intersections(): inserting points of intersections 

unionWalk - walk over lists and make union two polygons. 

In unionWalk are special cases: vertex of one polygon touch vertex second polygon etc 
Where can I find detail description of this algorithm? 


------------------------------------------------------------------------------
Download BIRT iHub F-Type - The Free Enterprise-Grade BIRT Server
from Actuate! Instantly Supercharge Your Business Reports and Dashboards
with Interactivity, Sharing, Native Excel Exports, App Integration & more
Get technology previously reserved for billion-dollar corporations, FREE
http://pubads.g.doubleclick.net/gampad/clk?id=157005751&iu=/4140/ostg.clktrk
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

[Algorithms] Special cases of Weiler-Atherton

[Andrzej B. <bor...@gm...>]

I am writing Weiler-Atherton algorithm. I can't find full description of
this.
My source trial is on bitbucket on aborucki/weileratherton, this is unclear
of brute_force_intersections() function because I am moving form
brute-force to Bentley-Ottmann sweep line intersections.
I have two main rountines:
brute_force_intersections(): inserting points of intersections
unionWalk - walk over lists and make union two polygons.
In unionWalk are special cases: vertex of one polygon touch vertex second
polygon etc
Where can I find detail description of this algorithm?

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

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

That's actually quite helpful! Thanks.





Sincerely,

Jon Watte


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


On Wed, May 21, 2014 at 12:53 PM, Graham Rhodes ARA/SED <gr...@ar...>wrote:

>  Components of the IntegrityWare SOLIDS++ commercial middleware may be
> useful. For example:
>
>
>
> http://www.integrityware.com/meshlib.html
>
>
>
> Not sure how they handle interpolating vertex attributes, though. They
> might support a user-provided function for that.
>
>
>
> Beyond that, we use Spatial’s ACIS library for some quite complex CSG
> work. This adds another level of cost and complexity through, being
> primarily used in the CAD industry. It does support non-manifold topology,
> regularized and non-regularized solids, provides built-in functions to do
> operations such as extruding or offsetting a sheet into a thickened solid,
> geometry healing, etc. ACIS is extremely flexible in the way you can
> attribute intermediate surfaces and edge lists that arise during the
> evaluation of CSG ops. And there are the ACIS competitors…Parasolid,
> Granite, Open Cascade (assuming these others still exist…my knowledge of
> solid modeling kernels is slightly stale now).
>
>
>
> Graham
>
>
>
> *From:* Eric Haines [mailto:eri...@gm...]
> *Sent:* Wednesday, May 21, 2014 11:39 AM
> *To:* Game Development Algorithms
> *Subject:* Re: [Algorithms] CSG operations on textured meshes --
> something better than CGAL?
>
>
>
> I'd certainly like to know, too. MeshLab might have one hiding in its
> bowels, but I haven't looked hard enough yet. MeshMixer looks super-cool,
> but appears to be just an application, not a library.
>
>
>
> On Wed, May 21, 2014 at 11:05 AM, Jon Watte <jw...@gm...> 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.
>
>
>
> 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 <ja...@os...>
> 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 <cg...@va...>
> 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:jw...@gm...]
> *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
>
>
>
>
> ------------------------------------------------------------------------------
> "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
> GDA...@li...
> 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?

[Graham R. ARA/S. <gr...@ar...>]

Components of the IntegrityWare SOLIDS++ commercial middleware may be useful. For example:

http://www.integrityware.com/meshlib.html

Not sure how they handle interpolating vertex attributes, though. They might support a user-provided function for that.

Beyond that, we use Spatial’s ACIS library for some quite complex CSG work. This adds another level of cost and complexity through, being primarily used in the CAD industry. It does support non-manifold topology, regularized and non-regularized solids, provides built-in functions to do operations such as extruding or offsetting a sheet into a thickened solid, geometry healing, etc. ACIS is extremely flexible in the way you can attribute intermediate surfaces and edge lists that arise during the evaluation of CSG ops. And there are the ACIS competitors…Parasolid, Granite, Open Cascade (assuming these others still exist…my knowledge of solid modeling kernels is slightly stale now).

Graham

From: Eric Haines [mailto:eri...@gm...]
Sent: Wednesday, May 21, 2014 11:39 AM
To: Game Development Algorithms
Subject: Re: [Algorithms] CSG operations on textured meshes -- something better than CGAL?

I'd certainly like to know, too. MeshLab might have one hiding in its bowels, but I haven't looked hard enough yet. MeshMixer looks super-cool, but appears to be just an application, not a library.

On Wed, May 21, 2014 at 11:05 AM, Jon Watte <jw...@gm...<mailto:jw...@gm...>> 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.

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 <ja...@os...<mailto:ja...@os...>> 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 <cg...@va...<mailto:cg...@va...>> 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:jw...@gm...<mailto:jw...@gm...>]
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

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

[Vilya H. <vil...@gm...>]

Have you come across Carve CSG? The repository is here:
https://code.google.com/p/carve/

I haven't used the library myself, but the website does mention that it
handles interpolating texture coordinates (and other arbitrary attributes)
correctly across the output mesh.

Hope that's useful,

Vil.




On 21 May 2014 16:38, Eric Haines <eri...@gm...> wrote:

> I'd certainly like to know, too. MeshLab might have one hiding in its
> bowels, but I haven't looked hard enough yet. MeshMixer looks super-cool,
> but appears to be just an application, not a library.
>
>
> On Wed, May 21, 2014 at 11:05 AM, Jon Watte <jw...@gm...> 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.
>>
>> 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 <ja...@os...>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 <cg...@va...>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:jw...@gm...]
>>>> *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
>>>> GDA...@li...
>>>> 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 lis...@li...https://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
>>> GDA...@li...
>>> 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
>> GDA...@li...
>> 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
> GDA...@li...
> 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?

[Eric H. <eri...@gm...>]

I'd certainly like to know, too. MeshLab might have one hiding in its
bowels, but I haven't looked hard enough yet. MeshMixer looks super-cool,
but appears to be just an application, not a library.


On Wed, May 21, 2014 at 11:05 AM, Jon Watte <jw...@gm...> 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.
>
> 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 <ja...@os...>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 <cg...@va...>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:jw...@gm...]
>>> *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
>>> GDA...@li...
>>> 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 lis...@li...https://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
>> GDA...@li...
>> 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
> GDA...@li...
> 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?

[Jon W. <jw...@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 <ja...@os...> 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 <cg...@va...>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:jw...@gm...]
>> *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
>> GDA...@li...
>> 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 lis...@li...https://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
> GDA...@li...
> 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 R. <ja...@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 <cg...@va... <mailto:cg...@va...>> 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:jw...@gm... <mailto:jw...@gm...>]
>     *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
>     GDA...@li... <mailto:GDA...@li...>
>     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
> GDA...@li...
> 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 W. <jw...@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 <cg...@va...>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:jw...@gm...]
> *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
> GDA...@li...
> 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 G. <cg...@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:jw...@gm...]
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 G. <rob...@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 <jw...@gm...> 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
> GDA...@li...
> 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 W. <jw...@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 F. <ra...@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 <mai...@gm...> 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 <ra...@gm...> 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 <jw...@gm...> 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 <rob...@gm...>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...@gm...>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
>>>> GDA...@li...
>>>> 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
>>> GDA...@li...
>>> 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
>> GDA...@li...
>> 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
> GDA...@li...
> 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 M. <mai...@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 <ra...@gm...> 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 <jw...@gm...> 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 <rob...@gm...>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...@gm...>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
>>> GDA...@li...
>>> 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
>> GDA...@li...
>> 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
> GDA...@li...
> 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 F. <ra...@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 <jw...@gm...> 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 <rob...@gm...>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...@gm...>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
>> GDA...@li...
>> 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
> GDA...@li...
> 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 W. <jw...@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 <rob...@gm...> 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...@gm...>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
> GDA...@li...
> 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 G. <rob...@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...@gm...>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 F. <ra...@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...@gm...> 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 <ra...@gm...> 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
>> GDA...@li...
>> 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
> GDA...@li...
> 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 M. <sam...@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...@gm...> 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 <ra...@gm...> 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
>> GDA...@li...
>> 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 W. <ajw...@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 <ra...@gm...> 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
> GDA...@li...
> 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 F. <ra...@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 W. <jw...@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 <ra...@gm...> 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
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>