Sign in to follow this  
Wex Viator

CSG Primitives

Recommended Posts

Wex Viator    122
Hi. I can usually find information on and around the net, but this seems to be eluding me completely... I'd like to know how CSG Primitives are built in detail. I already know that they are the construct of a number of planes (minimal of 4), but how do you go about developing the polygons for each face? I'd assume some plane-plane intersection alroithm is used, I have that written down somewhere already. But how is it used? Rather than starting off with an infinate-plane do you limit it and then simply resize it as other planes are introduced to intersect it? What happens when two points of the limited-plane merge to form a triangle? Or what happens if there are many points on the plane? I'm not talking about the subtraction of one object from the other, I'm not bothered about that yet. I need the objects first! :) Cheers for any help, links, or tutorials...

Share this post


Link to post
Share on other sites
superpig    1825
CSG brushes always have to be convex, so you do just do exactly what you described - start with each face as an infinite plane, then clip it against all the other planes.

Share this post


Link to post
Share on other sites
Etnu    880
Here are some basics. I've worked with CSG extensively in my own engine, and this is about hte best I can offer up:

Don't just store planes. Yes, you can store just planes if you want, but if you do that you're going to increase your computational overhead significantly. Sacrafice a little bit of ram and store polygons (vertices, plane equation, and whatever else you might need).

This also makes things a lot easier when doing CSG operations like joins and such.

Here's the two fundamental structures that I use for my classes:



//--------------------------------------
// Poly
// A base polygon class containing
// a set of vertices, plane, etc.
//--------------------------------------
class Poly
{
private:
Vert GetEdgeIntersection(const Vert& Point1, const Vert& Point2);
bool IntervalIntersect(const Vec& vAxis, const Poly& poly);
void CalculateInterval(const Vec& vAxis, const Vert* pVerts,UINT uiNumVerts, float& fMin,float& fMax);

public:

UINT NumVerts; // Number of vertices encompassing the Poly.
Vert* Verts; // Vertices
AABox BoundingBox; // Axis-aligned bounding box
Plane PlaneEquation; // Coplanar to the Poly
UINT MaterialID; // Material used to create the poly
bool IsVisible; // Determines if the plane should be drawn
Poly* SourcePoly; // If the poly has been split, this is the poly it was original split from.

Poly(Vert* pVerts = NULL,UINT uiNumVerts = 0,UINT uiMatID = 0);
~Poly();
void Clone(Poly* poly);
void Clear();
void Rebuild(Vert* pVerts, UINT uiNumVerts = 0);
void Recalculate();
void Simplify();
float GetSurfaceArea();
bool IsConvex();
void Invert();
bool Intersects(const Vec& vOrigin, const Vec& vDirection,Vec& vReturn,bool DoubleSided = true);
bool Intersects(const Poly& poly);
UINT Split(Poly* pSplitter,Poly* NewPolys);

Poly& operator=(Poly& poly);
};

//--------------------------
// Brush
// Contains a set of convex polygons
// and info about their relationship to one another.
//--------------------------
class Brush
{
public:
UINT NumPolys; // Number of Polys
Poly* Polys; // Actual poly data.
AABox BoundingBox; // Bounding box
Vec Origin; // Origin in world space.

Brush(Poly* polys = NULL, UINT uiNumPolys = 0,float fX = 0.0f, float fY = 0.0f,float fZ = 0.0f);
~Brush();
void Clone(Brush* brush);
void Clear();
void AddPoly(Poly* poly);
void Rebuild(Poly* polys, UINT uiNumPolys);
void Recalculate();
void Bisect(Brush* brush);
void Subtract(Brush* brush,bool FlagInsideFaces = false);
void Join(Brush* brush);
void Intersect(Brush* brush);
void Simplify();
void Rotate(float Yaw,float Pitch, float Roll);
void Move(float X,float Y, float Z);
bool ContainsPoly(Poly* poly);
Brush& operator=(Brush& brush);
};

Share this post


Link to post
Share on other sites
Wex Viator    122
Ooo, thanks. That looks great. However...

What I'm looking at doing is reading in a file format I have no control over. It's the new VMF file format that the Half-Life2 editor Hammer4 uses. It stores solids as a number of planes in the format:


side
{
"id" "18"
"plane" "(-64 -256 -128) (448 -256 -128) (448 64 -128)"
"material" "BRICK/BRICKFLOOR001A"
"uaxis" "[1 0 0 0] 0.25"
"vaxis" "[0 -1 0 0] 0.25"
"rotation" "0"
"lightmapscale" "16"
"smoothing_groups" "0"
}



As you can see, it only has the plane information...

Share this post


Link to post
Share on other sites
superpig    1825
The way the original HLCSG worked was to generate a very large polygon on the plane - something 4096 units along each side, or something. I know that VMF allows a bigger world, so you start with a bigger polygon. Then you do just clip it against each plane.

Share this post


Link to post
Share on other sites
LogicalError    293
Keep in mind tough that the bigger your polygon is, the bigger the math errors will be in your csg function..
In fact math errors will accumulate every time you clip the same edge.
Hell, everytime you clip a polygon by the other planes in a different order you'd end up with a slightly different vertex..
It's simpler to have a big polygon and split it, yes.
But you might get problems with small brushes then.
(all algorithms have this problem to a certain degree)

Another method is that you can calculate the intersection of each triplet of planes, calculate the vertex and check if it's on the inside of every other plane in the brush.
It's more complicated tough, since you have to figure out the order of the vertices.
(When i say complicated, i mean complicated as in not intuitive, not necesarry as in complicated code)
I build a csg function which does exactly this using half-edges, which i connect when i find a pair.
I use the knowledge which planes create a vertex to properly connect the half-edges to their opposite and to their neighbours..

However, if you're a beginner with this, i suggest you stick to the polygon clipping method

Share this post


Link to post
Share on other sites
Wex Viator    122
Hmm, cheers guys.

So you generate three half-edges per vertex, which has been generated by three planes?

I assume you do some sort of check for parrallel planes and plane-triplets which don't all meet each other...

Share this post


Link to post
Share on other sites
Extrarius    1412
It seems like a better way to do it would just to do all the plane-plane intersections to form lines (since planes are infinite, whever they intersect is also infinite - a line), then do line-line intersections to form points (or you could just intersect 3 planes at once to get the points, either way), and for each plane make a convex polygon from all the resulting points that lie on that plane. Then you can triangulate that N-sided convex polygon to get your actual face triangles, which is very simple to do for convex polygons.

You should be able to find all the formulas you need at http://astronomy.swin.edu.au/~pbourke/geometry/

Share this post


Link to post
Share on other sites
de_matt    181
I've just finished CSG for a .MAP file (Hammer 3.4 for HL 1) convertor I'm writing in VB. I based my code on the article everyone refers to in thse forums. I can't remember the name of it but it's really good. I'm sure tat somebody else knows the name.

This article used the intersection-of-3-planes method which I thought seemed "better". I know that it doesn't really do anything different to clipping massive planes but it just felt, well, right.

I'm really pleased with my results. It took a while of debugging to fix some of the errors I was having but I got there in the end.

Be warned - the article does have a couple of errors in it but you should be able to notice them. I managed it after all.

Again, this is a fantastic paper that you should really read if your going to try CSG or converting .MAP (or similar) files.

Hope that helps

Matt

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