Slicing objects (a CAD question)

Hi,

I’m writing a CAD-like program and I need a way to:

  1. ‘Slice’ a piece off of an object (with a plane, kind-of-like a ‘table saw’ operation).

  2. Discard the piece I cut off, keep the rest of the object.

  3. ‘Patch’ up the hole in the object with triangles, so it is a true solid again.

Any good URLs or coding ideas are appreciated. I need to get this working right away.

SteveH

P.S. - Object-to-Object ‘and’, ‘or’, and ‘xor’ intersection methods are not really needed, but would be appreciated. A ‘jigsaw’ approach using a curved plane or nurbs would also be of use later.

Originally posted by steve_hiemstra:
[b]

  1. ‘Slice’ a piece off of an object (with a plane, kind-of-like a ‘table saw’ operation).
  1. Discard the piece I cut off, keep the rest of the object.
  1. ‘Patch’ up the hole in the object with triangles, so it is a true solid again.

[/b]

1 and 2, well there is always regular sutherland hodgman clipping. Just extend it to 3d.

3, you have the intersection points and the discarded vertices.Make triangles out of that.

Did that help?

Yes… you are pointing me in the right direction, although I am wondering how I might use OpenGL to minimize the calculation of:

  1. New vertices at the point of intersection between my clipping plane (table saw) and the segments/vertices of my polys.

  2. Creating new polys between the new vertices.

<NOTE: assume all polys are/must be triangles, not quads>

Also, if OpenGL doesn’t help much with 1) and 2) do I just ‘march through’ pairs of vertices and check for intersections with my ‘plane’, storing the new vertices (in a ‘new vertice’ array) along the way? Then I have to figure out which ‘new vertices’ are the right ones to form new triangles, or do I just ‘converge’ all of them to a point (forming the new triangles)?

  1. and 2) beg a further question:

Object Data Structures

What is a good way to structure the data of a 3D object so I can easily subtract/add vertices and keep track of polys in the object? I smell a linked-list here, and possibly some structs(or better classes) for polys in the object.

Again - URLs pointing to code examples are better than ‘re-inventing the wheel’…

Thanks for responding so quickly,

SteveH

You should search for “CSG” (Constructive Solid Geometry). That´s exactly what you need.

With csg you can get the result of carving, merging or the intersection of the objects.

First you need to create a bsp tree for all objects you want to work with. Than you perform the csg operation on those trees.

A good link is this: http://www.cfxweb.net/~aggrav8d/tutorials/csg.html

Jan.

As long as you only need the visual effect of slicing through your geometry, use user clipping planes and a stencil algorithm to fill the opened hole.
This is probably what you want for interactive mode before you calculate the new triangles to close the hole with a true clipper and tesselator.

The simplest one which works for closed shapes only goes like this:
Init the stencil buffer to 0.
Enable clipping plane.
Draw backfaces of the cut object. Pixels which pass the z test should set the stencil to 1.
Draw the front faces of the cut object. Pixels which pass the depth test set the stencil to 0.
For a highlight effect of the cut, draw a full window rectangle where all stencil values are 1. For a lit plane draw a big enough 3D quad with the clip plane orientation in the desired material where stencil values are 1.
This should color all faces where you can see a back face, aka. the inside.
To increase the fidelity at the edges, set glDepthFunc(GL_LEQUAL) instead of GL_LESS.
In case your geometry has T-vertices you might get some stitch marks at such edges.

[This message has been edited by Relic (edited 02-04-2003).]

It all comes down to how accurate you want your solution to be, as always in visualization. If you want the visual effect, go with relic’s approach. Other than that you need to do it yourself.Remember that opengl is just a rendering api.

Originally posted by steve_hiemstra:
Also, if OpenGL doesn’t help much with 1) and 2) do I just ‘march through’ pairs of vertices and check for intersections with my ‘plane’, storing the new vertices (in a ‘new vertice’ array) along the way? Then I have to figure out which ‘new vertices’ are the right ones to form new triangles, or do I just ‘converge’ all of them to a point (forming the new triangles)?

Yes that seems about right. But I dont know what you mean by “converging vertices” though. I guess if you have several slicing planes it can get pretty complicated. You might want to search for some triangulation algorithms that could fit your needs.

Depending on how complicated your scene is you would need a scene graph to store objects. You could store them as bounding boxes, and also let each object have there own graph structure. The flipcode link below summarizes some data structures. Remember that clipping is expensive, but not that expensive. With an S-H algorithm with some good trivial rejection tests and a descent fpu, you can clip a lot of polys.

Object Data Structures

http://www.flipcode.com/harmless/
Also, take a look at the Winged-Edge data structure, it is often used in meshing algorithms.

[EDIT] Also, try posting this at comp.graphics.algorithms. You usually get VERY thorough answers though

[This message has been edited by roffe (edited 02-04-2003).]

Thanks for the feedback.

I’d like to respond to a few items you mentioned:

(1) Yes that seems about right. But I don’t know what you mean by “converging vertices” though. I guess if you have several slicing planes it can get pretty complicated. You might want to search for some triangulation algorithms that could fit your needs.

(2) Depending on how complicated your scene is you would need a scene graph to store objects.

For Item (1) I’d just like to clarify… The “coverging vertices” are not vertices-that-converge, just my odd way of expressing that I have a bunch of vertices that need to be joined together by segments (to create triangles) so I proposed a single new vertice be created somewhere in the middle of the ‘hole’ and I draw a segment to it from each vertice (effectively turning the hole into a patch of triangles).

For Item (2) I’d just like to say that my ‘scenes’ aren’t game-caliber stuff. Heck, most all of it is just simple CAD. No motion, no realtime issues, just a bunch of primitive solids with textures and simple lighting.

Just imagine I’m designing a wooden deck outback of the house and I want to write a program to do it with 3D. I need to cut the floor boards: sometimes on an angle, sometimes on a curve - always perpendicular (no angling the blade when I cut) to the ground. So I draw a line (curved or straight) on my board, take out a jigsaw, and cut on the line.

I want to do ‘just-that-and-little-more’ in my 3D program, and save the shortened boards in my model list for re-use later.

I’m inclined to use BSP trees for it, because I need collision detection later when I space the ‘boards’ and it sounds like this is the way to go <although it seems like ‘a little more than is necessary’ just to cut and place ‘some boards’>. The ‘clipping planes’ ideas are just not what I had in mind (I have too many ‘boards’ being cut too many different ways).

[Please Note: I am not building a deck, I am just trying to convey an analogy here]

Thanks again,

SteveH