pouët.net

How to realize CSG operations in 3D mesh objects? Please, discuss the principles.

Depends.exe on what you are doing.
3D mesh objects as in triangle meshes? I guess there are tons of papers on that topic and a lot of different approaches... google it.
Or just take distance fields instead - in distance fields CSG is trivial ;)

Clip the triangles against each other, check inside/outside rules for each resulting polygon. Simple in theory, but turns into absolute hell in reality due to floating point accuracy. There's a reason why there's very few CSG-packages out there that can eat it's own dog-food.

Maybe an easier place to start: Screen Space CSG?

OpenCSG uses some image-based method.

Indeed, screen-space CSG is much easier to get robust.

This reminds me.. I wonder if anyone ever made a .pov ---> random-polygon-object-format converter, e.g. something that would eat povray's script (even with limited set of primites) and output an approximation as a mesh.

Just a first random pick... http://www.nigels.com/research/ there's really a huge amount of academic research out there...
Or if you wanna just cut out planes, you have it nearly for free in OpenGL, see for instance http://www.cs.duke.edu/courses/fall00/cps124/web/links.html.
Hmm, distance functions are lovely...
must... download... framework... and play!

The easiest one to implement is:

http://www.opengl.org/resources/code/samples/advanced/advanced97/notes/node11.html

Easy peasy. Intersect all edges of mesh A with triangles of mesh B and vice versa. Then just connect the dots :)

Bonus points doing the intersection stuff so that each pair or triangles intersect at either 0 or 2 points, retriangulating without nasty singularities and getting intuitive results on non-perfect input meshes.

bsp trees will help you with csg:

A Tutorial on Binary Space Partitioning Trees
BSP FAQ
flipcode article

also there's example code in Game Programming Gems 5, if you need it, I'll send you the source code

Weeks struggling for a stable connection...
Thanks for the answers.

Ized: Would you mail me it? dang...@gmail.com

with something resembling to an authority, i can confirm that you really don't want to code triangle-mesh CSG yourself. However, if you still insist to do it, I can recommend 216's method above :)

I need it and I want it. D:

I recently want to do this (at work) and I am afraid to go for triangle intersections and stuff. It doesn't seem like an easy problem.
I am considering another approach which seems easier. Do CSG in volume data (which is very easy) and then marching cubes for polygons. Must not be hard.
Then, I'll check how can I get the original mesh and voxelize. That could be a bit harder. But still the overall process sounds easier than traditional CSG atm.
Also, I need to do the voxelization only once in the beginning. And I guess the rest, csg in voxels and marching cubes can be realtime in speed.
All we need to do is some test if we can drill arbitrary holes in an object with a virtual drill machine.

What a beautiful description.

I did the screen-space CSG stuff based on NigelG's work many moons ago, it is indeed rather easy to get robust, and very fast: http://bohemiq.scali.eu.org/forum/viewtopic.php?f=4&t=30

Hehe..

Now I am thinking, what if I specialize the case, cylinder to surface(s), and actually do some crude polygon intersection/reconstruction, since we only need that. Not sure.

@Scali: I'll check this.

My internship was similar: I worked at a company that developed CAD/CAM software specialized for hydraulic manifolds.
We had to develop a solution to accurately estimate the weakest point inside a manifold (where two drill holes are closest together).
The CSG solution was a way to visualize the drill holes (which were modeled as cylinders with cones on top for extra accuracy).
If this visualization worked well enough, we could also estimate the 'area' of a hole with a sort of 2d Finite Element Analysis, by simply drawing the hole in a particular colour and counting pixels.

I should clarify, these were actually two separate problems:
1) By finding the minimum distance between any two drill holes, you could estimate the maximum pressure the manifold could withstand (and possibly modify the design to allow higher pressure).
2) The holes could be drilled at any angle, and holes could also be 'stepped' (a hole starting with a certain diameter, and moving to smaller diameters deeper down). So the meeting point of two holes could be a rather complex and peculiar shape. By estimating the 'area' (it's not really a 2d problem, but it was simplified as such) of this shape, you could also estimate the maximum flow through the hole (and possibly modify the design to allow higher flow).

Voxel test failed. Too minecrafty, too many vertices per object for unity, also this would not be optimal for our haptic device.

콘크 리트 맘 does some realtime csg but i forgot how it works