Booleans

[Julio Jerez]

how you handle uv scale?
I beleive it is simpler to just keep then in a UV channel.

[Bird]

yes that will be very useful for debugging. there is OFF public domain code floating around, but it is dreadfull, I just added my own. you can use as a getting start point

Thanks for that! I have a OFF loader running in LW now.

Just to double check can you tell me if this is what the object data you posted should look like? The "after boolean" objects both seem to have some triangles that aren't rendering properly.
http://www.hurleyworks.com/media/flash/OFFloader/OFFloader.html

-Bird

[Julio Jerez]

remember the OFF is not intended to be for any practical engine purpose, I added because the NewtonMesh has lots of mesh conditioning routines,
It removes degenerated faces, make sure that face are convex, remove duplicated vertex, makes optimal triangulation, and a whole lot of other stuff, therefore what you get the same input mesh but not necessarily topologically.
under this conditions it is very hard to debug any algorithm that generates NewtonMeshs as intermediate variables, because the moment I save as a dScene, the output does not math the input.
an example would be a tetrahedral, if I make a tetrahedral a save as a dScene i will still be a tetrahedral, but the vertex and face order will not be the same as the input that was passed in.
I needed a standard file format that soppetred gereanl polygon to allow me to see the data as it is represented inside the NewtonMesh. The simples I found was OFF, there was also PLY but as it turns out is PLY is too complex for what I wanted.

Anyway the two meshes I posted were not intended for you to apply Booleans, they were examples for you to load then in case you have a standard inported in lightwave. I just want to see if they mesh save by NetwonMesh were legal OFF mesh.
Now I am debugging the bug in the boolean. hopefully this is the last bug and the OPFF is a great visual debugging tool, because I can save the sequences of clipped meshes and see when the bug happens.
Standby for the Bug fix.

[Julio Jerez]

ha I found the bug, not tiem to fix now. But is it no in eth cliipper
it was in a special case when combinig teh result cliiped mesh. I fix tonight

[Bird]

ha I found the bug, not tiem to fix now. But is it no in eth cliipper
it was in a special case when combinig teh result cliiped mesh. I fix tonight

Cool! I'm ready to start testing.

One thing I noticed while exporting with NewtonMeshSaveOFF() is that the vertices are saved in object space instead of world space. When I create a NewtonMesh for the boolean operations, I pass in the vertices in world space. I thought I would be able to send you any problem meshes that I encounter by exporting to them to .off files ... but that won't work if both objects vertices are in object space. Or should I use the Newton's serialize api to export meshes that I'm having problems with?

-Bird

[Julio Jerez]

no Polygon formats like the OFF, PLY, and STL do not sopport hiearchy or transform matrices.

The OFF is the mose generec because it male no asumetion of singel close manifold.
the PLY does make asumption of close manifold so I I export a mesh with an opne face then no oeth plugion woudl loaded it because most lieklli will test that.
The STL is the most restricted, because it assumes close manifolds and triangle only meshes. this one is used for digital lithographic.

for us, the OFF is the more flexible but it does not supports anything: matrix, hierrchies, UV, or matreail. just polygons and faces color.
like I said this is for assisting in debuging, if you find a big you can simple save the meshes and post or print the matrix you used
to position the clipping mesh relative to the source mesh, in a different text file.
For all other purposes, the file format is the dMesh Library.

[Bird]

Looks like you've made a lot of progress!

Here's a simple case with a ball intersecting a box that has some problems using Boolean Difference. http://www.hurleyworks.com/media/flash/NewtonBoolDiffProb/NewtonBoolDiffProb.html

Here's the OFF files.http://www.hurleyworks.com/downloads/NewtonBoolDiffProb.zip

The clipper mesh is DifferenceB.off and has a translation of ( 0.0, 0.5, 0.0 );

If I look in LW Modeler it shows that there are 24 unmerged vertices.

I'm using today's svn 2323.

-Bird

[Julio Jerez]

I took a break from working on the algorithm to think about why is falling.
and I realize that the algorithm is correct, but it is numerically unstable.
what this mean is that it will always be bound to fail. I am making a change on how it work.

The theorem is correct, the intersection of two solid volume are be closed polygon on the surface of the two solids.

The problem is that my implementation try to construct the surfaces independently on both solid, and in the end hope the two surface concede. and the only way this can happen is if the calculation are done with exact arithmetic which is not possible in a computer.

My new approach is this. Build the curve on one solid, keeping the other solid unchanged.
Basically this comes down to

-calculate the intersection of all the face of the first solid.
-generate the loop from the integrations.
-do the reverse fix each close loop on the second solid.

this method should also generate fewer slivers (which is the root of the problems in the first method)
and therefore even cleaner Booleans.

what I get form the first pass in a library that I can use to writ the second cleaner version.

[Bird]

what I get form the first pass in a library that I can use to writ the second cleaner version.

Good to hear!

I know GSG is not an easy thing to do... I've been trying to implement my own on and off for a while now but haven't gotten very far. I did find one paper that was helpful http://www.cs.brown.edu/~jfh/papers/Laidlaw-CSG-1986/paper.pdf and there's a Java implementation of the algorithm at http://unbboolean.sourceforge.net/ ... but it sounds like you going to use a different approach.

-Bird

[Julio Jerez]

Oh wow, I did nio knwo abouot that paper.
I will read it because I can see that the already have detremine all of teh diffrent case that can happend when doind the clip,
this cases will be part of any impelementaion, and it is good that they are identified.
I beleieve I covered many of them in our code, the propblem is tha numerical error.

The boolean code should be 100% correct in all case, and until weh do not have that the detruction will no work.
It also must be fast, and produce very high quality meshes.

[Bird]

The boolean code should be 100% correct in all case, and until weh do not have that the detruction will no work.
It also must be fast, and produce very high quality meshes.

Speed and quality are very important for interactive destruction for sure. I did find another paper from Brown that claims to be much faster than the original algorithm.... it only works on a triangulated mesh. ftp://ftp.cs.brown.edu/pub/techreports/90/cs90-07.pdf

I got as far as finding the intersection seam between 2 meshes. I know there's a lot more work than just finding the intersection seam but my CSG tool can find the seam between two 100,000 poly meshes in less than .4 seconds. http://www.hurleyworks.com/media/flash/Intersector/Intersector.html

I hope Newton will be faster than that.

-Bird

[Marc]

What is the status on this? Is there any boolean code in newton atm?

[Julio Jerez]

It is something I plan to do sometime, but I work on what has demand and Booleans operation has not been something people has show any interest in so is low in my loose list of priorities.

[JoeJ]

I thought it's already in, but there is interest from my side.
I'll use it for preprocessing geometry, but can do on my own if it's not ready at the time.

Here's what i need to do after boolean mesh operations:

Mesh segmentation:
Divide the surface to convex patches ignoring high frequency details. Patches as large as possible.
I have most of this but still a lot of work - it's pretty hard.

Mesh parametrization:
Put all geometry to a single texture atlas (automatic UV charts, same requirements as for a game with Megatexture for everything)
Should be easy to do.

Texture baking:
Bake all various textures of hand made models to a single texture in new UV space.
Very easy.


Let me know if you have similar things on your todo list.
(although i don't think so - first point reminds me to convex decomposition, but it's quite different because i need only surface not volume).

Also let me know guys if you are aware of any tools that can do this already - i'm not.
Maybe Simplygon can? Or is it just about LOD levels.