• Advertisement
Sign in to follow this  

Z-Buffer CSG Alternatives

This topic is 4429 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have a complex triangle mesh that I am trying to split using axis aligned planes. I have a working z-buffer CSG implementation, but I would need to be able to store all the coordinates for the generated object. That is, after I split my object using my splitting plane, I want to update the triangles that were split by the plane, and generate additional triangles to fill the open areas of the object so that it appears solid. Does anyone know any methods for this that works on a triangle-level instead of using z-buffer tricks? Thanks, -D

Share this post


Link to post
Share on other sites
Advertisement
I had originally written a long, detailed description of why this was a hard problem, and gave lists of software packages and docs that would help. But, upon reading your message carefully, there is an easier solution to your specific clipping plane problem.

It is still quite tedious, and subject to floating point oddities that will frustrate you quite a lot, :)! But, if what I write below is clear enough, and if your geometry skills and basic understanding of topology are sufficient (and not even advanced), then you should be able to implement a basic system without much difficulty.

I have one assumption. The assumption is that your object is manifold, e.g., it is a simple, closed 3D polygonal surface----no holes and every edge is touched by exactly two triangles, no more, no less. In this case, you can do the following:

edge_list is the list of edges that are created by splitting triangles. Note that these edges must be oriented, e.g., their endpoints are directed in such a way that they form a counterclockwise loop around the triangles when viewing the object from the outside.

tri_list is the list of triangles in the mesh. This changes over time.

new_tris is the list of new triangles created by splitting

The pseudo-code is written for clarity, not speed! And make sure that you are careful about what the list.erase() methods do! Think about reference counting, for example, to avoid many fine-grained allocations/frees.


for each plane, p,
edge_list.resize(0)
new_tris.resize(0)
for each triangle in tri_list, t
if (t is completely in front of p)
// t is not part of the result
tri_list.erase(t)
else if (t is split by p)
// the following intersection will produce a line
// segment. The segment must be oriented, as
// described above. All the edges must be oriented
// the same way, to create consistent loops in the
// clip plane.
edge_list.add(intersect(t, p))

// the newly added edge splits t into two pieces,
// one piece behind p and the other piece in
// front of p.
q = the bit of t behind p----1 triangle or 1 quad

// break q, which might be a quadrilateral, into
// 1 or 2 triangles. these new triangles are
// part of the result
new_tris.add(tessellate(q))
end if
next triangle

tri_list.add(new_tris);

// at this point, edge_list contains edges that form
// one or more closed polygons within the clip plane.
// These polygons are the polygons that fill the gaps.
// If you tessellate them to triangles, they can be
// added to the result mesh (tri_list) to make your
// object solid again. Your job now is to walk through
// the edges, identifying the polygons, then
// tessellate them to find the new polygons that fill
// in the space on the cutting plane.
//
// the outer while loop walks through cutting plane
// polygons.
while (edge_list.size())
{
polygon_edges.resize(0);
first_edge = edge_list.front();
edge_list.erase(first_edge);
polygon_edges.add(first_edge);
prev_edge = first_edge
closed = false;
edge = edge_list.front();
while (edge != edge_list.end())
{
if (edge is neighbor of prev_edge)
{
prev_edge = edge
polygon_edges.add(edge);
edge_list.erase(edge);
if (edge is neighbor of first_edge)
{
closed = true;
break;
}
// must start over at beginning of
// list, since neighbor of new prev_edge
// might occur earlier in the list
edge = edge_list.front();
}
else
{
edge = edge_list.next();
}
}
if (!closed)
Houston we have a problem!
else // we have a closed polygon
{
tri_list.add(tessellate(polygon_edges));
}
}
// at this point, tri_list has been updated to:
// a) clip the mesh against the single plane, p; and,
// b) add new triangles to fill the gap revealed
// by the clip. The mesh is once again a manifold
// solid that can be fed back into the next plane
// pass.
//
// Before you go to the next plane, you might want to
// consider running a "repair" step that stitches vertices
// that are close together. This can lead you into trouble,
// in some rare cases, since it is possible to break
// the manifold nature of the model along the way. But,
// the main thing for the algorithm to run
// successfully is that the mesh be manifold from a
// topology sense and not necessarily from a geometric
// sense (even though you really want both).
next plane


So, I hope that helps. Conceptually, it is simple, but there's a lot for you to get right. Edges that you create during the clip have to be oriented correctly in order to be able to find closed polygons to make the cut mesh a solid. You need a good generalized (possibly concave, but non self-intersecting) polygon tessellator. You gotta watch out for floating point tolerance issues (which will get you every time---see Jonathan Shewchuk's robust predicates web page for details). Think about using the Winged-Edge-Data-Structure (WEDS), which is amazingly, super-handy for this type of thing once you learn how to use it. And....you might consider an ear-clipping technique to tessellate polygons. David Everly has a nice implementation over at Geometric Tools.

[Edited by - grhodes_at_work on January 4, 2006 4:15:11 PM]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement