Sign in to follow this  
Etnu

Anyone know of any good CSG papers?

Recommended Posts

I've scoured Google, and I pretty much keep coming up with the same basic layout, just explaining the basics. I understand the basic operations, and what they should do...what I'm still a little confused on are some of the mathematics involved. Unfortunately, the last math class I took was linear Algebra when I was 17, and I haven't really kept up with much aside from the usual stuff you encounter in graphics programming. So, say you've got 2 brushes. Brush 1 is just a 6-sided cube, and Brush 2 is a complex shape made up of several dozen polygons. In order to do a subtraction between these two, subtracting the cube from the second brush, you should be left with the second brush, only now any vertices completely contained within the cube will be clipped off, and a new polygon with those dimensions is added to the complex brush at the cut off point. That seems simple enough, I suppose, though I'm still not quite certain about how you should calculate the point at which you split each polygon. Then, when it comes to doing operations on two complex brushes, I'm really sort of dumbfounded. So you need to somehow calculate each new face on the brush being subtracted from (which should theoretically just mirror the outside faces of the brush doing the subtracting?) -- so how do you actually calculate the point of intersection? Do you test each vertex in the first shape vs. the volume of the second (or vice versa) to determine if it's within it, and if so you determine the point of intersection along the edge, clip that off,and form new polygons? That seems like a rather processor-intensive task, and using UnrealEd as a point of reference, it just seems like there's got to be a more efficient method. Again, let me reiterate here: I don't need an 'introduction' to CSG -- I know the basics of how it works. I'm trying to figure out a practical implementation, though, that will actually let you edit in real time.

Share this post


Link to post
Share on other sites
If you are looking for simply a visual CSG operation that simply generates the correct screen pixels, then you'll want to look at the Advanced OpenGL course notes from the SIGGRAPH conference. I believe there are links at opengl.org or you can do a web search. The advanced course is presented most every year at the conference.

If you are looking for computational geometry techniques, then essentially you are looking to convert a CGS tree into a boundary representation, or B-rep. Which is most difficult! For smooth geometry (analytic surfaces, not polygon meshes) you can look for papers on the "BOOLE" software developed at the University of Chapel Hill several years ago. If you can accept just polygon meshes (closed polyhedra), then David Eberly's book "Geometric Tools for Computer Graphics." See the following link:

Magic Software Books Page

That book discusses 3D and higher dimension boolean operations on polyhedra. Its not comprehensive, but it is a decent, modern presentation.

There's also bound to be some document out there that discusses the techniques implement in, say, the Unreal Engine.

Share this post


Link to post
Share on other sites
The flipcode article helped immensely. Thanks.

I've now got my brushes all bisected and ready to go, and am just trying to figure out a good triangulation algorithm.

Since all my polys are going to be convex, I was goign to just use use triangle fans, but of course that isn't very helpful since you wind up having to call draw primitive (using d3d) for every polygon. That would suck.

Obviously an extension of the fan would work well, simply creating triangle lists that all share a common vertex (and every other one shares 2). The only problem with that is insuring the correct winding order. I've been playing around with it a bit but I'm still not quite getting the consistent results.

Share this post


Link to post
Share on other sites
I have done real-time CSG, and for rendering I do the following (it works, but don't know if its the most efficient method).

1. For every vertex assign it a unique ID starting from 0. Allocate and fill in the vertex array.

2. Calculate the TOTAL number of indices required (by going through every face and asking how many indices it needs).

3. Allocate the index array.

4. Then go through every face and get it to fill in the index array at the correct position, by passing in the pointer to the index array and the current array position.

Then you're good to go... However that method requires 3 for loops and two memory allocations. And as the vertex/face counts grow this process will slow down. I have yet to devise a better, more efficient method though.

Share this post


Link to post
Share on other sites
Actually, I already figured out a triangulation implementation that works perfectly for convex polygons. I just do this:

for(int i = 2; i < NumVerts; i++)
{
Indices[NumIndices++] = 0;
Indices[NumIndices++] = i - 1;
Indices[NumIndices++] = i;
}



As you can see, it's just creating triangle strips in a fan pattern (not actually creating fans as they're too difficult to use effectively). This only works for convex polys created with vertices winding in the correct order though, of course.

My big problem now is that my splitting algorithm seems to be doing something wrong. I'm guessing it's probably something similiar, but when I have 2 cubes, 1 with vertices:

0,64, 0 64,64, 0 64, 0, 0 0, 0, 0 (front face)
64,64,64 0,64,64 0, 0,64 0 64,64 (back face)

And the other with the same vertices offset by 32 units along each axis, it's just missing something. Instead of creating 15 faces for each side that needs to be split (the 3 intersecting sides should each be split twice, forming 4 polys, and the 3 outside faces should remain intact, forming a total of 15 polys), it seems to be stopping at 9 total faces (subdividing the inside faces each only once, forming 2 polys each split, and then leaving the outside faces).

I thought "hmm, it must not be re-splitting the previously split faces" -- but it is. I loop infinitely until no splits are found, it's just...doing something wrong.

I'm sure it's a simple logic error on my part, but it's been frustrating that I've worked on it for 4 days now and still don't even have my faces splitting properly. All the source I've found on the web is doing more or less the same algorithm that i came up with, so I don't think my general approach is the problem.

Share this post


Link to post
Share on other sites
Okay, so you have your square face, and its being intersected by the other cube to remove the corner. That WILL result in 9 faces not 15. One face of the intersecting cube will split the square in half... then the other face will split that new half in half - not both halfs. So you end up with 3 faces, not 4.

hope that makes sense.

Share this post


Link to post
Share on other sites
Yeah, you're right, now that I think about it. For some reason I was thinking that both faces should be sub divided. Either way, there's still something fishy going on with the way it's displaying the final polys...but, again, I'd bet on it being a simple math error on my part.

Share this post


Link to post
Share on other sites
Ok, I've got it working mostly right, but I think there's still something going wrong.

(WARNING: LARGE IMAGES)

Here is the cube before any subtraction has been done:



The little purple lines are the surface normals. Pay no mind to the large number of triangles being reported as drawn...there's a lot of other crap being rendered off screen at the moment.



This is the cube I'm subtracting from the first.



And this is the final cube after the cut. Yes, I know the texture coordinates don't look right. This is a byproduct of the way the shader being used renders the surface, though, and not a real issue.

As you can see, it's dividing some faces more than it should. The splits themselves are done in the right locations, it's just that it's overdoing it. Here's what I'm doing to bisect the brushes:


//-----------------------------
// Brush::Bisect()
// Bisects this against brush.
//-----------------------------
void Brush::Bisect(Brush* brush)
{
bool NoSplits = false;

Poly TempPolys1[2], TempPolys2[2],
Brush1Polys[BC_MAXPOLYS],Brush2Polys[BC_MAXPOLYS];

UINT Brush1PolyCount = NumPolys;
for(UINT ui = 0; ui < Brush1PolyCount; ui++)
Polys[ui].Clone(&Brush1Polys[ui]);

UINT Brush2PolyCount = brush->NumPolys;
for(UINT ui = 0; ui < Brush2PolyCount; ui++)
brush->Polys[ui].Clone(&Brush2Polys[ui]);

// Loop through all polys until no more splits can occur.
while(!NoSplits)
{
NoSplits = true;

// Split all polys against each other.
for(UINT B1 = 0; B1 < Brush1PolyCount; B1++)
{
for(UINT B2 = 0; B2 < Brush2PolyCount; B2++)
{
if(Brush1Polys[B1].BoundingBox.Overlaps(Brush2Polys[B2].BoundingBox))
{
if(Brush1Polys[B1].Split(&Brush2Polys[B2],TempPolys1) == PC_INTERSECT &&
Brush2Polys[B2].Split(&Brush1Polys[B1],TempPolys2) == PC_INTERSECT)
{
// Replace polys.
Brush1Polys[B1] = TempPolys1[1];
Brush1Polys[Brush1PolyCount++] = TempPolys1[0];
Brush2Polys[B2] = TempPolys2[1];
Brush2Polys[Brush2PolyCount++] = TempPolys2[0];
NoSplits = false;
}
}
}
}
}

// Delete old brush data and create new brushes.
Rebuild(Brush1Polys,Brush1PolyCount);
brush->Rebuild(Brush2Polys,Brush2PolyCount);
}




The Poly.Split() function is actually dividing the polygons and returning 2 newly split ones.

As you can see, I replace the polygon that was just split with one of the new polys, and add the other into the list.

The function runs until no possible splits can be made, at which point each brush's Rebuild() function is called, passing to it the new polygons. Rebuild() simply copies the list of polygons to the brush.

I thought the likely culprit might be the following:


//--------------------------------
// AABox::Overlaps()
// Returns true if the box overlaps
// the specified AABB.
//---------------------------------
bool AABox::Overlaps(AABox& box)
{
const Vec T = box.Origin - Origin;
return fabs(T.x) <= (Extents.x + box.Extents.x)
&&

fabs(T.y) <= (Extents.y + box.Extents.y)

&&

fabs(T.z) <= (Extents.z + box.Extents.z);
}




but I just don't see what's wrong with this algorithm.

Any thoughts?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this