# CSG Primitives

## Recommended Posts

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 on other sites
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 on other sites
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?

##### Share on other sites
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 on other sites
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 on other sites
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 on other sites
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 on other sites
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 on other sites
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 on other sites
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 on other sites
i think de_matt meant:
http://folk.uio.no/stefanha/MAPFiles.pdf

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628394
• Total Posts
2982427

• 10
• 9
• 19
• 24
• 9