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

[Jon Watte]

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

[Robin Green]

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.

Post by Jon Watte
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
• 3 signs your SCM is hindering your productivity
• Requirements for releasing software faster
• Expert tips and advice for migrating your SCM now
http://p.sf.net/sfu/perforce
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

[Chris Green]

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:***@gmail.com]
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

[Jon Watte]

Post by Chris Green
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

Post by Chris Green
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.
*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
• 3 signs your SCM is hindering your productivity
• Requirements for releasing software faster
• Expert tips and advice for migrating your SCM now
http://p.sf.net/sfu/perforce
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

[James Robertson]

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.

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
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.
*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
------------------------------------------------------------------------------
• 3 signs your SCM is hindering your productivity
• Requirements for releasing software faster
• Expert tips and advice for migrating your SCM now
http://p.sf.net/sfu/perforce
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
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
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
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

[Jon Watte]

Post by James Robertson
You are going to be distorting triangles in different ways depending on

the overall shape of the mesh at any given point though.

Post by James Robertson
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

Post by James Robertson
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.
I don’t believe you will be able to use your existing uv values with the

Post by Chris Green
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

Post by Chris Green
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.
*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
------------------------------------------------------------------------------
• 3 signs your SCM is hindering your productivity
• Requirements for releasing software faster
• Expert tips and advice for migrating your SCM now
http://p.sf.net/sfu/perforce
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
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
_______________________________________________
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
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

[Eric Haines]

[Vilya Harvey]

[Graham Rhodes ARA/SED]

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:***@gmail.com]
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.

Post by James Robertson
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 <***@osodata.com<mailto:***@osodata.com>> 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 <***@valvesoftware.com<mailto:***@valvesoftware.com>> 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:***@gmail.com<mailto:***@gmail.com>]
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

[Jon Watte]

[unknown]

--001a11c36da2ae50af04f9eaca33
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

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.

Post by James Robertson

Post by James Robertson
You are going to be distorting triangles in different ways depending on

the overall shape of the mesh at any given point though.

Post by James Robertson
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

Post by James Robertson
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.
I don’t believe you will be able to use your existing uv values with

Post by Chris Green
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

Post by Chris Green
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.
*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
&#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
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
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
_______________________________________________
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
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
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
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

--001a11c36da2ae50af04f9eaca33
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable <div dir="ltr">I&#39;d certainly like to know, too. MeshLab might have one hiding in its bowels, but I haven&#39;t looked hard enough yet. MeshMixer looks super-cool, but appears to be just an application, not a library.</div> <div class="gmail_extra"><br><br><div class="gmail_quote">On Wed, May 21, 2014 at 11:05 AM, Jon Watte <span dir="ltr">&lt;<a href="mailto:***@gmail.com" target="_blank">***@gmail.com</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> <div dir="ltr"><div class=""><span style="font-family:arial,sans-serif;font-size:16.363636016845703px">&gt; You are going to be distorting triangles in different ways depending on the overall shape of the mesh at any given point though.?</span></div> <div><div class=""> <span style="font-family:arial,sans-serif;font-size:16.363636016845703px">&gt; If you just retain existing UV coordinates for the new vertices, the results will be...� strange.</span><br><div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px"><br> </span></div></div><div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px">I do this operation with some frequency in 3ds Max, and it works the way I expect there.</span></div><div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px"><br> </span></div><div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px">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 &quot;bugs&quot; :-)</span></div> </div><div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px">But I don&#39;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.</span></div> <div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px"><br></span></div><div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px">So, does anyone know of any textured-triangle-mesh CSG library out there, free or paid for, that would work?</span></div> <div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px"><br></span></div><div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px">Sincerely,</span></div><div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px"><br> </span></div><div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px">jw</span></div><div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px"><br></span></div><div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px"><br> </span></div></div><div class="gmail_extra"><div class=""><br clear="all"><div><div dir="ltr"><font face="courier new, monospace"><br><br><br><font>Sincerely,</font><br><br><font>Jon Watte</font><br><br><br>--<br>&quot;<span style="color:rgb(0,0,0)">I find that the harder I work, the more luck I seem to have.&quot; -- Thomas Jefferson</span></font></div> </div> <br><br></div><div><div class="h5"><div class="gmail_quote">On Tue, May 13, 2014 at 10:07 PM, James Robertson <span dir="ltr">&lt;<a href="mailto:***@osodata.com" target="_blank">***@osodata.com</a>&gt;</span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">




<div text="#000000" bgcolor="#FFFFFF">
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.<br>
<br>
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&#39;t be noticeable,
but they will be there.<div><div><br>
<br>
<br>
<div>On 14/05/2014 01:41, Jon Watte wrote:<br>
</div>
</div></div><blockquote type="cite"><div><div>
<div dir="ltr">
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><span style="color:rgb(31,73,125);font-family:Calibri,sans-serif;font-size:14.399999618530273px">I
don’t believe you will be able to use your existing uv
values with the mesh that results from this csg operation</span></blockquote>
<div><br>
</div>
<div>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.</div>
<div>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.</div>
<div><br>
</div>
<div>So... no general purpose parameterized trimesh CSG library
available? </div>
<div><br>
</div>
<div>Sincerely,</div>
<div><br>
</div>
<div>jw</div>
<div><br>
</div>
</div>
<div class="gmail_extra"><br clear="all">
<div>
<div dir="ltr"><font face="courier new, monospace"><br>
<br>
<br>
<font>Sincerely,</font><br>
<br>
<font>Jon Watte</font><br>
<br>
<br>
--<br>
&quot;<span style="color:rgb(0,0,0)">I find that the harder I
work, the more luck I seem to have.&quot; -- Thomas Jefferson</span></font></div>
</div>
<br>
<br>
<div class="gmail_quote">On Thu, May 8, 2014 at 12:28 PM, Chris
Green <span dir="ltr">&lt;<a href="mailto:***@valvesoftware.com" target="_blank">***@valvesoftware.com</a>&gt;</span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div link="blue" vlink="purple" lang="EN-US">
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d">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.</span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d"> </span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d">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.
</span></p>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d"> </span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d"> </span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d"> </span></p>
<p class="MsoNormal"><b><span style="font-size:10.0pt;font-family:&quot;Tahoma&quot;,&quot;sans-serif&quot;">From:</span></b><span style="font-size:10.0pt;font-family:&quot;Tahoma&quot;,&quot;sans-serif&quot;">
Jon Watte [mailto:<a href="mailto:***@gmail.com" target="_blank">***@gmail.com</a>]
<br>
<b>Sent:</b> Thursday, May 08, 2014 11:08 AM<br>
<b>To:</b> Game Development Algorithms<br>
<b>Subject:</b> [Algorithms] CSG operations on
textured meshes -- something better than CGAL?</span></p>
<p class="MsoNormal"> </p>
</div>
<div>
<p class="MsoNormal">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.</p>
<div>
<div>
<div>
<p class="MsoNormal"> </p>
</div>
<div>
<p class="MsoNormal">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&#39;ll run into along narrow sharp
creases etc.</p>
</div>
<div>
<p class="MsoNormal"> </p>
</div>
<div>
<p class="MsoNormal">I can&#39;t find any library to
do this, though. CGAL has some fairly robust
functions on NEF polyhedra, but those
polyhedra don&#39;t seem to allow parameterization
(which is academic speak for texture
coordinates that may have discontinuities
across edges.)</p>
</div>
<div>
<p class="MsoNormal"> </p>
</div>
<div>
<p class="MsoNormal">So, what are some robust
CSG libraries available that work on such
game-style meshes, preserving texture
coordinates?</p>
</div>
<div>
<p class="MsoNormal"> </p>
</div>
<div>
<p class="MsoNormal">(And actually, I don&#39;t have
one such mesh; I have &gt; 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.)<br clear="all">
</p>
<div>
<div>
<p class="MsoNormal"><span><br>
<br>
Sincerely,<br>
<br>
Jon Watte<br>
<br>
<br>
--<br>
&quot;<span style="color:black">I find that
the harder I work, the more luck I
seem to have.&quot; -- Thomas Jefferson</span></span></p>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
<br>
------------------------------------------------------------------------------<br>
Is your legacy SCM system holding you back? Join Perforce
May 7 to find out:<br>
&amp;#149; 3 signs your SCM is hindering your productivity<br>
&amp;#149; Requirements for releasing software faster<br>
&amp;#149; Expert tips and advice for migrating your SCM now<br>
<a href="http://p.sf.net/sfu/perforce" target="_blank">http://p.sf.net/sfu/perforce</a><br>
_______________________________________________<br>
GDAlgorithms-list mailing list<br>
<a href="mailto:GDAlgorithms-***@lists.sourceforge.net" target="_blank">GDAlgorithms-***@lists.sourceforge.net</a><br>
<a href="https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list" target="_blank">https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list</a><br>
Archives:<br>
<a href="http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list" target="_blank">http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list</a><br>
</blockquote>
</div>
<br>
</div>
<br>
<fieldset></fieldset>
<br>
</div></div><pre>------------------------------------------------------------------------------
&quot;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.&quot;
<a href="http://p.sf.net/sfu/SauceLabs" target="_blank">http://p.sf.net/sfu/SauceLabs</a></pre><div>
<br>
<fieldset></fieldset>
<br>
<pre>_______________________________________________
GDAlgorithms-list mailing list
<a href="mailto:GDAlgorithms-***@lists.sourceforge.net" target="_blank">GDAlgorithms-***@lists.sourceforge.net</a>
<a href="https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list" target="_blank">https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list</a>
Archives:
<a href="http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list" target="_blank">http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list</a></pre>
</div></blockquote>
<br>

<br><br>
<hr style="border:none;color:#909090;background-color:#b0b0b0;min-height:1px;width:99%">
<table style="border-collapse:collapse;border:none">
<tbody><tr>
<td style="border:none;padding:0px 15px 0px 8px">
<a href="http://www.avast.com/" target="_blank">
<img border="0">
</a>
</td>
<td>
<p style="color:#3d4d5a;font-family:&quot;Calibri&quot;,&quot;Verdana&quot;,&quot;Arial&quot;,&quot;Helvetica&quot;;font-size:12pt">
This email is free from viruses and malware because <a href="http://www.avast.com/" target="_blank">avast! Antivirus</a> protection is active.
</p>
</td>
</tr>
</tbody></table>
<br>
</div>

<br>------------------------------------------------------------------------------<br>
&quot;Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE<br>
Instantly run your Selenium tests across 300+ browser/OS combos.<br>
Get unparalleled scalability from the best Selenium testing platform available<br>
Simple to use. Nothing to install. Get started now for free.&quot;<br>
<a href="http://p.sf.net/sfu/SauceLabs" target="_blank">http://p.sf.net/sfu/SauceLabs</a><br>_______________________________________________<br>
GDAlgorithms-list mailing list<br>
<a href="mailto:GDAlgorithms-***@lists.sourceforge.net" target="_blank">GDAlgorithms-***@lists.sourceforge.net</a><br>
<a href="https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list" target="_blank">https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list</a><br>
Archives:<br>
<a href="http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list" target="_blank">http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list</a><br></blockquote></div><br></div></div></div>

<br>------------------------------------------------------------------------------<br>
&quot;Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE<br>
Instantly run your Selenium tests across 300+ browser/OS combos.<br>
Get unparalleled scalability from the best Selenium testing platform available<br>
Simple to use. Nothing to install. Get started now for free.&quot;<br>
<a href="http://p.sf.net/sfu/SauceLabs" target="_blank">http://p.sf.net/sfu/SauceLabs</a><br>_______________________________________________<br>
GDAlgorithms-list mailing list<br>
<a href="mailto:GDAlgorithms-***@lists.sourceforge.net">GDAlgorithms-***@lists.sourceforge.net</a><br>
<a href="https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list" target="_blank">https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list</a><br>
Archives:<br>
<a href="http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list" target="_blank">http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list</a><br></blockquote></div><br></div>

--001a11c36da2ae50af04f9eaca33--

[unknown]

--089e01176febefd0dd04f9eb3c6d
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

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.

Post by unknown
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.

Post by James Robertson

Post by James Robertson
You are going to be distorting triangles in different ways depending on

the overall shape of the mesh at any given point though.

Post by James Robertson
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

Post by James Robertson
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.
I don’t believe you will be able to use your existing uv values with

Post by Chris Green
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

Post by Chris Green
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.
*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
&#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
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
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
_______________________________________________
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
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
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
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
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
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

--089e01176febefd0dd04f9eb3c6d
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable <div dir="ltr">Have you come across Carve CSG? The repository is here:?<a href="https://code.google.com/p/carve/">https://code.google.com/p/carve/</a><div><br></div><div>I haven&#39;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.</div> <div><br></div><div>Hope that&#39;s useful,</div><div><br></div><div>Vil.<br><div><div><br></div><div><br></div></div></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On 21 May 2014 16:38, Eric Haines <span dir="ltr">&lt;<a href="mailto:***@gmail.com" target="_blank">***@gmail.com</a>&gt;</span> wrote:<br> <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">I&#39;d certainly like to know, too. MeshLab might have one hiding in its bowels, but I haven&#39;t looked hard enough yet. MeshMixer looks super-cool, but appears to be just an application, not a library.</div> <div class="HOEnZb"><div class="h5"> <div class="gmail_extra"><br><br><div class="gmail_quote">On Wed, May 21, 2014 at 11:05 AM, Jon Watte <span dir="ltr">&lt;<a href="mailto:***@gmail.com" target="_blank">***@gmail.com</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> <div dir="ltr"><div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px">&gt; You are going to be distorting triangles in different ways depending on the overall shape of the mesh at any given point though.?</span></div> <div><div> <span style="font-family:arial,sans-serif;font-size:16.363636016845703px">&gt; If you just retain existing UV coordinates for the new vertices, the results will be...� strange.</span><br><div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px"><br> </span></div></div><div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px">I do this operation with some frequency in 3ds Max, and it works the way I expect there.</span></div><div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px"><br> </span></div><div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px">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 &quot;bugs&quot; :-)</span></div> </div><div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px">But I don&#39;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.</span></div> <div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px"><br></span></div><div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px">So, does anyone know of any textured-triangle-mesh CSG library out there, free or paid for, that would work?</span></div> <div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px"><br></span></div><div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px">Sincerely,</span></div><div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px"><br> </span></div><div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px">jw</span></div><div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px"><br></span></div><div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px"><br> </span></div></div><div class="gmail_extra"><div><br clear="all"><div><div dir="ltr"><font face="courier new, monospace"><br><br><br><font>Sincerely,</font><br><br><font>Jon Watte</font><br><br><br>--<br>&quot;<span style="color:rgb(0,0,0)">I find that the harder I work, the more luck I seem to have.&quot; -- Thomas Jefferson</span></font></div> </div> <br><br></div><div><div><div class="gmail_quote">On Tue, May 13, 2014 at 10:07 PM, James Robertson <span dir="ltr">&lt;<a href="mailto:***@osodata.com" target="_blank">***@osodata.com</a>&gt;</span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">




<div text="#000000" bgcolor="#FFFFFF">
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.<br>
<br>
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&#39;t be noticeable,
but they will be there.<div><div><br>
<br>
<br>
<div>On 14/05/2014 01:41, Jon Watte wrote:<br>
</div>
</div></div><blockquote type="cite"><div><div>
<div dir="ltr">
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><span style="color:rgb(31,73,125);font-family:Calibri,sans-serif;font-size:14.399999618530273px">I
don’t believe you will be able to use your existing uv
values with the mesh that results from this csg operation</span></blockquote>
<div><br>
</div>
<div>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.</div>
<div>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.</div>
<div><br>
</div>
<div>So... no general purpose parameterized trimesh CSG library
available? </div>
<div><br>
</div>
<div>Sincerely,</div>
<div><br>
</div>
<div>jw</div>
<div><br>
</div>
</div>
<div class="gmail_extra"><br clear="all">
<div>
<div dir="ltr"><font face="courier new, monospace"><br>
<br>
<br>
<font>Sincerely,</font><br>
<br>
<font>Jon Watte</font><br>
<br>
<br>
--<br>
&quot;<span style="color:rgb(0,0,0)">I find that the harder I
work, the more luck I seem to have.&quot; -- Thomas Jefferson</span></font></div>
</div>
<br>
<br>
<div class="gmail_quote">On Thu, May 8, 2014 at 12:28 PM, Chris
Green <span dir="ltr">&lt;<a href="mailto:***@valvesoftware.com" target="_blank">***@valvesoftware.com</a>&gt;</span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div link="blue" vlink="purple" lang="EN-US">
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d">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.</span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d"> </span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d">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.
</span></p>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d"> </span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d"> </span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d"> </span></p>
<p class="MsoNormal"><b><span style="font-size:10.0pt;font-family:&quot;Tahoma&quot;,&quot;sans-serif&quot;">From:</span></b><span style="font-size:10.0pt;font-family:&quot;Tahoma&quot;,&quot;sans-serif&quot;">
Jon Watte [mailto:<a href="mailto:***@gmail.com" target="_blank">***@gmail.com</a>]
<br>
<b>Sent:</b> Thursday, May 08, 2014 11:08 AM<br>
<b>To:</b> Game Development Algorithms<br>
<b>Subject:</b> [Algorithms] CSG operations on
textured meshes -- something better than CGAL?</span></p>
<p class="MsoNormal"> </p>
</div>
<div>
<p class="MsoNormal">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.</p>
<div>
<div>
<div>
<p class="MsoNormal"> </p>
</div>
<div>
<p class="MsoNormal">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&#39;ll run into along narrow sharp
creases etc.</p>
</div>
<div>
<p class="MsoNormal"> </p>
</div>
<div>
<p class="MsoNormal">I can&#39;t find any library to
do this, though. CGAL has some fairly robust
functions on NEF polyhedra, but those
polyhedra don&#39;t seem to allow parameterization
(which is academic speak for texture
coordinates that may have discontinuities
across edges.)</p>
</div>
<div>
<p class="MsoNormal"> </p>
</div>
<div>
<p class="MsoNormal">So, what are some robust
CSG libraries available that work on such
game-style meshes, preserving texture
coordinates?</p>
</div>
<div>
<p class="MsoNormal"> </p>
</div>
<div>
<p class="MsoNormal">(And actually, I don&#39;t have
one such mesh; I have &gt; 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.)<br clear="all">
</p>
<div>
<div>
<p class="MsoNormal"><span><br>
<br>
Sincerely,<br>
<br>
Jon Watte<br>
<br>
<br>
--<br>
&quot;<span style="color:black">I find that
the harder I work, the more luck I
seem to have.&quot; -- Thomas Jefferson</span></span></p>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
<br>
------------------------------------------------------------------------------<br>
Is your legacy SCM system holding you back? Join Perforce
May 7 to find out:<br>
&amp;#149; 3 signs your SCM is hindering your productivity<br>
&amp;#149; Requirements for releasing software faster<br>
&amp;#149; Expert tips and advice for migrating your SCM now<br>
<a href="http://p.sf.net/sfu/perforce" target="_blank">http://p.sf.net/sfu/perforce</a><br>
_______________________________________________<br>
GDAlgorithms-list mailing list<br>
<a href="mailto:GDAlgorithms-***@lists.sourceforge.net" target="_blank">GDAlgorithms-***@lists.sourceforge.net</a><br>
<a href="https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list" target="_blank">https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list</a><br>
Archives:<br>
<a href="http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list" target="_blank">http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list</a><br>
</blockquote>
</div>
<br>
</div>
<br>
<fieldset></fieldset>
<br>
</div></div><pre>------------------------------------------------------------------------------
&quot;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.&quot;
<a href="http://p.sf.net/sfu/SauceLabs" target="_blank">http://p.sf.net/sfu/SauceLabs</a></pre><div>
<br>
<fieldset></fieldset>
<br>
<pre>_______________________________________________
GDAlgorithms-list mailing list
<a href="mailto:GDAlgorithms-***@lists.sourceforge.net" target="_blank">GDAlgorithms-***@lists.sourceforge.net</a>
<a href="https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list" target="_blank">https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list</a>
Archives:
<a href="http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list" target="_blank">http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list</a></pre>
</div></blockquote>
<br>

<br><br>
<hr style="border:none;color:#909090;background-color:#b0b0b0;min-height:1px;width:99%">
<table style="border-collapse:collapse;border:none">
<tbody><tr>
<td style="border:none;padding:0px 15px 0px 8px">
<a href="http://www.avast.com/" target="_blank">
<img border="0">
</a>
</td>
<td>
<p style="color:#3d4d5a;font-family:&quot;Calibri&quot;,&quot;Verdana&quot;,&quot;Arial&quot;,&quot;Helvetica&quot;;font-size:12pt">
This email is free from viruses and malware because <a href="http://www.avast.com/" target="_blank">avast! Antivirus</a> protection is active.
</p>
</td>
</tr>
</tbody></table>
<br>
</div>

<br>------------------------------------------------------------------------------<br>
&quot;Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE<br>
Instantly run your Selenium tests across 300+ browser/OS combos.<br>
Get unparalleled scalability from the best Selenium testing platform available<br>
Simple to use. Nothing to install. Get started now for free.&quot;<br>
<a href="http://p.sf.net/sfu/SauceLabs" target="_blank">http://p.sf.net/sfu/SauceLabs</a><br>_______________________________________________<br>
GDAlgorithms-list mailing list<br>
<a href="mailto:GDAlgorithms-***@lists.sourceforge.net" target="_blank">GDAlgorithms-***@lists.sourceforge.net</a><br>
<a href="https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list" target="_blank">https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list</a><br>
Archives:<br>
<a href="http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list" target="_blank">http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list</a><br></blockquote></div><br></div></div></div>


<br>------------------------------------------------------------------------------<br>
&quot;Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE<br>
Instantly run your Selenium tests across 300+ browser/OS combos.<br>
Get unparalleled scalability from the best Selenium testing platform available<br>
Simple to use. Nothing to install. Get started now for free.&quot;<br>
<a href="http://p.sf.net/sfu/SauceLabs" target="_blank">http://p.sf.net/sfu/SauceLabs</a><br>_______________________________________________<br>
GDAlgorithms-list mailing list<br>
<a href="mailto:GDAlgorithms-***@lists.sourceforge.net" target="_blank">GDAlgorithms-***@lists.sourceforge.net</a><br>
<a href="https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list" target="_blank">https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list</a><br>
Archives:<br>
<a href="http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list" target="_blank">http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list</a><br></blockquote></div><br></div>
</div></div><br>------------------------------------------------------------------------------<br>
&quot;Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE<br>
Instantly run your Selenium tests across 300+ browser/OS combos.<br>
Get unparalleled scalability from the best Selenium testing platform available<br>
Simple to use. Nothing to install. Get started now for free.&quot;<br>
<a href="http://p.sf.net/sfu/SauceLabs" target="_blank">http://p.sf.net/sfu/SauceLabs</a><br>_______________________________________________<br>
GDAlgorithms-list mailing list<br>
<a href="mailto:GDAlgorithms-***@lists.sourceforge.net">GDAlgorithms-***@lists.sourceforge.net</a><br>
<a href="https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list" target="_blank">https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list</a><br>
Archives:<br>
<a href="http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list" target="_blank">http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list</a><br></blockquote></div><br></div>

--089e01176febefd0dd04f9eb3c6d--

[unknown]

--001a11c211165a553604fa6413d7
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

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

Post by Graham Rhodes ARA/SED
Components of the IntegrityWare SOLIDS++ commercial middleware may be
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
*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.

Post by James Robertson
You are going to be distorting triangles in different ways depending on

the overall shape of the mesh at any given point though.

Post by James Robertson
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
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.
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
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.
*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
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

--001a11c211165a553604fa6413d7
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable <div dir="ltr">That&#39;s actually quite helpful! Thanks.<div><br></div></div><div class="gmail_extra"><br clear="all"><div><div dir="ltr"><font face="courier new, monospace"><br><br><br><font>Sincerely,</font><br><br><font>Jon Watte</font><br> <br><br>--<br>&quot;<span style="color:rgb(0,0,0)">I find that the harder I work, the more luck I seem to have.&quot; -- Thomas Jefferson</span></font></div></div> <br><br><div class="gmail_quote">On Wed, May 21, 2014 at 12:53 PM, Graham Rhodes ARA/SED <span dir="ltr">&lt;<a href="mailto:***@ara.com" target="_blank">***@ara.com</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">






<div lang="EN-US" link="blue" vlink="purple">
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d">Components of the IntegrityWare SOLIDS++ commercial middleware may be useful. For example:<u></u><u></u></span></p>

<p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d"><a href="http://www.integrityware.com/meshlib.html" target="_blank">http://www.integrityware.com/meshlib.html</a><u></u><u></u></span></p>

<p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d">Not sure how they handle interpolating vertex attributes, though. They might support a user-provided function for that.<u></u><u></u></span></p>

<p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d">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).<u></u><u></u></span></p> <p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d"><u></u>?<u></u></span></p> <p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d">Graham<u></u><u></u></span></p> <p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d"><u></u>?<u></u></span></p> <p class="MsoNormal"><b><span style="font-size:10.0pt;font-family:&quot;Tahoma&quot;,&quot;sans-serif&quot;">From:</span></b><span style="font-size:10.0pt;font-family:&quot;Tahoma&quot;,&quot;sans-serif&quot;"> Eric Haines [mailto:<a href="mailto:***@gmail.com" target="_blank">***@gmail.com</a>] <br> <b>Sent:</b> Wednesday, May 21, 2014 11:39 AM<br> <b>To:</b> Game Development Algorithms<br> <b>Subject:</b> Re: [Algorithms] CSG operations on textured meshes -- something better than CGAL?<u></u><u></u></span></p><div><div class="h5"> <p class="MsoNormal"><u></u>?<u></u></p> <div> <p class="MsoNormal">I&#39;d certainly like to know, too. MeshLab might have one hiding in its bowels, but I haven&#39;t looked hard enough yet. MeshMixer looks super-cool, but appears to be just an application, not a library.<u></u><u></u></p> </div> <div> <p class="MsoNormal" style="margin-bottom:12.0pt"><u></u>?<u></u></p> <div> <p class="MsoNormal">On Wed, May 21, 2014 at 11:05 AM, Jon Watte &lt;<a href="mailto:***@gmail.com" target="_blank">***@gmail.com</a>&gt; wrote:<u></u><u></u></p> <div> <div> <p class="MsoNormal"><span style="font-size:12.5pt;font-family:&quot;Arial&quot;,&quot;sans-serif&quot;">&gt; You are going to be distorting triangles in different ways depending on the overall shape of the mesh at any given point though.�</span><u></u><u></u></p> </div> <div> <div> <p class="MsoNormal"><span style="font-size:12.5pt;font-family:&quot;Arial&quot;,&quot;sans-serif&quot;">&gt; If you just retain existing UV coordinates for the new vertices, the results will be...  strange.</span><u></u><u></u></p>

<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.5pt;font-family:&quot;Arial&quot;,&quot;sans-serif&quot;">I do this operation with some frequency in 3ds Max, and it works the way I expect there.</span><u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.5pt;font-family:&quot;Arial&quot;,&quot;sans-serif&quot;">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 &quot;bugs&quot; :-)</span><u></u><u></u></p>

</div>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.5pt;font-family:&quot;Arial&quot;,&quot;sans-serif&quot;">But I don&#39;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.</span><u></u><u></u></p>

</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.5pt;font-family:&quot;Arial&quot;,&quot;sans-serif&quot;">So, does anyone know of any textured-triangle-mesh CSG library out there, free or paid for, that would work?</span><u></u><u></u></p>

</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.5pt;font-family:&quot;Arial&quot;,&quot;sans-serif&quot;">Sincerely,</span><u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.5pt;font-family:&quot;Arial&quot;,&quot;sans-serif&quot;">jw</span><u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"><br clear="all">
<u></u><u></u></p>
<div>
<div>
<p class="MsoNormal"><span style="font-family:&quot;Courier New&quot;"><br>
<br>
<br>
Sincerely,<br>
<br>
Jon Watte<br>
<br>
<br>
--<br>
&quot;<span style="color:black">I find that the harder I work, the more luck I seem to have.&quot; -- Thomas Jefferson</span></span><u></u><u></u></p> </div> </div> <p class="MsoNormal" style="margin-bottom:12.0pt"><u></u>�<u></u></p> </div> <div> <div> <div> <p class="MsoNormal">On Tue, May 13, 2014 at 10:07 PM, James Robertson &lt;<a href="mailto:***@osodata.com" target="_blank">***@osodata.com</a>&gt; wrote:<u></u><u></u></p>
<div>
<p class="MsoNormal">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.<br>

<br>
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&#39;t
be noticeable, but they will be there.<u></u><u></u></p>
<div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><br>
<br>
<u></u><u></u></p>
<div>
<p class="MsoNormal">On 14/05/2014 01:41, Jon Watte wrote:<u></u><u></u></p>
</div>
</div>
</div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<div>
<div>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d">I don’t believe you will be able to use your existing uv values with the mesh that results from this csg operation</span><u></u><u></u></p>

</blockquote>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">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.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">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.<u></u><u></u></p>

</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">So... no general purpose parameterized trimesh CSG library available? <u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">Sincerely,<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">jw<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
</div>
<div>
<p class="MsoNormal"><br clear="all">
<u></u><u></u></p>
<div>
<div>
<p class="MsoNormal"><span style="font-family:&quot;Courier New&quot;"><br>
<br>
<br>
Sincerely,<br>
<br>
Jon Watte<br>
<br>
<br>
--<br>
&quot;<span style="color:black">I find that the harder I work, the more luck I seem to have.&quot; -- Thomas Jefferson</span></span><u></u><u></u></p> </div> </div> <p class="MsoNormal" style="margin-bottom:12.0pt"><u></u>�<u></u></p> <div> <p class="MsoNormal">On Thu, May 8, 2014 at 12:28 PM, Chris Green &lt;<a href="mailto:***@valvesoftware.com" target="_blank">***@valvesoftware.com</a>&gt; wrote:<u></u><u></u></p>
<div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d">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.</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d"> </span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d">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.
</span><u></u><u></u></p>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d"> </span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d"> </span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1f497d"> </span><u></u><u></u></p>
<p class="MsoNormal"><b><span style="font-size:10.0pt;font-family:&quot;Tahoma&quot;,&quot;sans-serif&quot;">From:</span></b><span style="font-size:10.0pt;font-family:&quot;Tahoma&quot;,&quot;sans-serif&quot;"> Jon Watte [mailto:<a href="mailto:***@gmail.com" target="_blank">***@gmail.com</a>]
<br>
<b>Sent:</b> Thursday, May 08, 2014 11:08 AM<br>
<b>To:</b> Game Development Algorithms<br>
<b>Subject:</b> [Algorithms] CSG operations on textured meshes -- something better than CGAL?</span><u></u><u></u></p>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">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.<u></u><u></u></p>
<div>
<div>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">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&#39;ll run into along narrow sharp creases etc.<u></u><u></u></p>

</div>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">I can&#39;t find any library to do this, though. CGAL has some fairly robust functions on NEF polyhedra, but those polyhedra don&#39;t seem to allow parameterization (which is academic
speak for texture coordinates that may have discontinuities across edges.)<u></u><u></u></p> </div> <div> <p class="MsoNormal">�<u></u><u></u></p> </div> <div> <p class="MsoNormal">So, what are some robust CSG libraries available that work on such game-style meshes, preserving texture coordinates?<u></u><u></u></p> </div> <div> <p class="MsoNormal">�<u></u><u></u></p> </div> <div> <p class="MsoNormal">(And actually, I don&#39;t have one such mesh; I have &gt; 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.)<br clear="all">
<u></u><u></u></p>
<div>
<div>
<p class="MsoNormal" style="margin-right:.5in;margin-left:.5in">
<br>
<br>
Sincerely,<br>
<br>
Jon Watte<br>
<br>
<u></u><u></u></p>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</blockquote>
</div>
</div>
</div>
</div>
</div>
</div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
</div></div></div>
</div>

<br>------------------------------------------------------------------------------<br>
&quot;Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE<br>
Instantly run your Selenium tests across 300+ browser/OS combos.<br>
Get unparalleled scalability from the best Selenium testing platform available<br>
Simple to use. Nothing to install. Get started now for free.&quot;<br>
<a href="http://p.sf.net/sfu/SauceLabs" target="_blank">http://p.sf.net/sfu/SauceLabs</a><br>_______________________________________________<br>
GDAlgorithms-list mailing list<br>
<a href="mailto:GDAlgorithms-***@lists.sourceforge.net">GDAlgorithms-***@lists.sourceforge.net</a><br>
<a href="https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list" target="_blank">https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list</a><br>
Archives:<br>
<a href="http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list" target="_blank">http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list</a><br></blockquote></div><br></div>

--001a11c211165a553604fa6413d7--