CSG Primitives
Author
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...
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.
Author
How do you go about clipping though?
What, urm, information would you save while clipping in order to generate the polygon which is on that plane?
What, urm, information would you save while clipping in order to generate the polygon which is on that plane?
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:
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); };
Author
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:
As you can see, it only has the plane information...
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...
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.
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
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
Author
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...
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...
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/
You should be able to find all the formulas you need at http://astronomy.swin.edu.au/~pbourke/geometry/
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
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement