Subtractive Solid Geometry (3d)

M

Misty

Guest
I was wondering how to do subtractive solid geometry (csg) in game maker.

The system must be able to cut away any parts of the object of the other side (normal) of a plane.
Essentially, the plane slices through the object, cutting away all parts of it which are on one side, forming a new set of polygons on the other side.
 
R

rui.rosario

Guest
I'm not sure how feasible this is (since I haven't played around with the physics engine myself) but I think I remember there was a way to define the collision polygon yourself on the GM:S physics engine. Maybe you could use that with some line segment collision algorithms to cut out portions of the solid object. You could then apply blend modes and surfaces to cut them out graphically.
 
T

Tirous

Guest
If you want 3d collisions using csg then i would recommend using a lot of convex hulls comprised of planes.

just a simple plane that can be used to check if points are above or below it, if a convex shape has at least one of its corner verticies under the plane, then its colliding.

this ain't as efficient as some methods(*cough* split-axis-theorem *cough*), but its more then sufficient and allows for the creation of things like bsp maps due to the fact that you can branch the intersection based on if its above or below the plane, going both ways if the hull is in between both sections.

As for the csg portion, then union is fairly easy, just check normal collisions and OR the results, for intersections just do a AND in order to check if the test passes.

As for the subtraction part, thats a tad tricky, but in general just ensure that its colliding with the first convex brush, and is not FULLY colliding with the subtracted brush, partial collisions should be allowed.

Also for subtractive brushes to work, like if you have a rectangle carve a hole through a box, make sure that rectangle is uncapped on the ends that extrude through the base brush, otherwise you can encounter situations in which it not FULLY colliding with the subtracted brush can result in it detecting a collision when it shouldn't.

One trick i have found to avoid this is to auto-remove any faces on the subtracting brush that does not itself intersect with the base geometry, which i find helps solve this problem in most cases.

So ya, i use this method all the time in my c++ stuff, in both 2D and 3D, and its proven itself more then sufficient so long as you.

Hope this helps mate, if you need a more clear explanation then do feel free to ask. As well if you need some help on the nitty gritty of plane-vertex intersections or how to check convex hull intersections/what the difference between a 'partial' and a 'full' collision is, then do again feel free to ask. :D
 
T

Tirous

Guest
sorry for the double-post, but may i ask the exact need of 3D csg your intending? do you need to carve a object into multiple objects? do complex collision checking? fancy rendering? answering this will help greatly in finding a answer, so if you could do so that would be of great use to those trying to help. =)
 
M

Misty

Guest
If you want 3d collisions using csg then i would recommend using a lot of convex hulls comprised of planes.
By plane, do you mean an infinite plane, or a triangular plane?
I think I understand what a convex hull is, it is the shape defined by the outermost points. However I have one question I would like to make clear. It seems to me that Defining the amount of sides of a convex hull is important, and also arbitrarily defined by the user. If I have a box convex hull it is going to be different from a n-sided convex hull. Or are you saying I need to skip the box convex hulls and instead, go for the n-sided, hi-res convex hulls?


Just a simple plane that can be used to check if points are above or below it, if a convex shape has at least one of its corner verticies under the plane, then its colliding.
Okay I think I get this part, but it may be incorrect. For example, two triangles it would return a false positive, it would say they are colliding, when they aren't.


this ain't as efficient as some methods(*cough* split-axis-theorem *cough*),
Don't know what that is, and I'm not sure I want to.

but its more then sufficient and allows for the creation of things like bsp maps due to the fact that you can branch the intersection based on if its above or below the plane, going both ways if the hull is in between both sections.
Tried making BSP in GM and it was unfair and tedious.
As for the csg portion, then union is fairly easy, just check normal collisions and OR the results, for intersections just do a AND in order to check if the test passes.
Collisions the normal way, or collisions of the normals?

As for the subtraction part, thats a tad tricky, but in general just ensure that its colliding with the first convex brush, and is not FULLY colliding with the subtracted brush, partial collisions should be allowed.
Who or what is colliding? There are only two entities here. "ensure that its colliding with the first convex brush, and not fully colliding with the subtracted brush" What is this third entity? Player collisions? (Best left for another topic, let's not overburden ourselves.)

Also for subtractive brushes to work, like if you have a rectangle carve a hole through a box, make sure that rectangle is uncapped on the ends that extrude through the base brush, otherwise you can encounter situations in which it not FULLY colliding with the subtracted brush can result in it detecting a collision when it shouldn't.
I don't see how, please post a picture diagram of the uncapped ends returning a false positive.
Also, I would like to mention, that the type of carving going is slicing cubes, via infinite planes, not shapes as you describe it here. Think of it like an ice sculpture - or a cake being carved by a super sharp plate of metal.

One trick i have found to avoid this is to auto-remove any faces on the subtracting brush that does not itself intersect with the base geometry, which i find helps solve this problem in most cases.
Brushes-Subtractive brushes are outside the scope of what I had in mind. Let's keep it to Brushes-Subtractive planes at the moment.

Hope this helps mate, if you need a more clear explanation then do feel free to ask. As well if you need some help on the nitty gritty of plane-vertex intersections or how to check convex hull intersections/what the difference between a 'partial' and a 'full' collision is, then do again feel free to ask. :D
I would like for you to cook me up an example and post it on the GMC. Less work for me. ;)
 
M

Misty

Guest
sorry for the double-post, but may i ask the exact need of 3D csg your intending? do you need to carve a object into multiple objects? do complex collision checking? fancy rendering? answering this will help greatly in finding a answer, so if you could do so that would be of great use to those trying to help. =)
Exact reason? bsp map specs don't provide vertex data. Instead they provide the data of some subtractive planes....the planes subtract from a 4096x4096x4096 cube and the left over sculpture is the drawn polygons.
 
T

Tirous

Guest
what i mean by a plane is this:

imagine cutting 3D space into 2 halfs, the flat surface you would use to cut with is the plane in question, for intersections we need one defined by 2 things, a direction it defines as 'up', at which it is perpendicular to, and a point upon which it rests, this point being what it pivots around.


the plane in the pic is finite, but in reality it extends perpendicular to its surface normal(its 'up' direction) forever

due to the fact that you can use this to split space into two halves, you can thus use another to split one of those pieces again into two halves, and thus you can use a collection of planes to carve out convex shapes in any dimension(2D, 3D, 4D, ..., ND)
(note the fact that carving 3D space with planes allows you to make things like infinitely extending objects, as thats important for csg to work)

thus with our plane defined, we can do a bit of math to check if a point is below a plane, thus in turn we can check if said point is below ALL of the planes defining a convex shape, thus we can check if said point is colliding with said shape.

as a result of this ability, we can collision test two convex shapes by using a combination of there verticies and faces to determine a collision, as its mathematically impossible for two convex hulls to be intersecting without one having at least one of its corner verticies being fully within the bounds of the other.

thus we can define colliders as convex meshes comprised of corner verticies and planes, this structure is called a 'brush' and is the basis for csg and bsp in most scenarios, you can have more complicated brushes, but this will work for now

with the above in mind, you can check if two brushes are colliding in 3D, with 'partial collisions' being defined as collisions in which no brush is fully within the other, and 'full collisions' being when one brush is fully within the other, with 100% of its verticies being under 100% of the other brushes planes

with this we can do csg operations by defining one brush as the 'base' and another as the 'operand' whom is effecting the base

csg has 3 primary operations, each of which we can perform with brushes and basic logic

-union, in which the operand adds to the base


-intersect, in which the collision is only valid if it takes plane in a space that overlaps both the base and the operand


-difference(subtraction), in which the base is solid, but the operand defines a special area that is exempt from this collision

with this relationship defined, you can take a third brush called the 'client' and use it to check for a collision against this new csg-brush which is just a base/operand plus a relationship type of union, intersect or difference

for union you would check if the client is in a partial or full intersection with ether the base or operand, so long as at least one is intersecting the client brush, then the entire csg-brush is defined as colliding the client

for intersect the client brush must be in a full or partial intersection with the base AND the operand, if its intersecting one but not the other, then there is not intersection with the csg-brush itself

for difference(the tricky one) you must ensure that the client is intersecting the base brush and is not fully intersecting the operand brush, as a partial collision implies its still colliding with the base, but a full one means its not supposed to be touching the base.

the difference operation can be tricky as there are scenarios in which we would consider it a valid collision but the computer doesn't, like this:

blue: base brush
red: operand brush
green: client brush

as you can see in this scenario it would detect a collision despite the fact that the difference brush should prevent it, due to the fact that the intersection between the client and operand is a partial one, not a full one

to solve this you need to uncap the operand brush as to not restrict it in ways that could break it, mainly by removing faces that aren't intersecting the base brush, which can be done automatically

the collision is now ignored as we want, simply by removing disruptive planes from the operand brush

so ya... hopefully this WAY to detailed explanation helps you/who-ever it may help as 3D collisions and csg are a vary oft requested thing on the topic of 3D

your exact implementation of the theory if just explained will vary must depend on what your need is, and what information relating to the collision you wish to detect, so for now ill leave it at this.

as for carving a bsp map... just be aware that in most cases its not just subtracting, rather its CARVING the cube, partitioning into pieces whoms material depends on what side of each subsequent plane that divides it its on, one side of a plane can have ground, the other can be split again into air and the water below it for example, your not just removing stuff, your partitioning and defining what is what.

and while doing such with a bsp file isn't exactly a-tune to what i just explained involving csg, just know the theory i explained here can be used to carve the 4096x#3 cube into what the file describes.

regardless, i have indulged by nerdy side quite enough i do think, so if all can be said and done, i bid you good-day sir =) *put on top-hat and walks out the door*
 
M

Misty

Guest
I think you are both oversimplifying and overcomplicating things.

BSP collision is nice but may I remind you that my only search is for carving a bsp map, of which you sir have only devoted 1 paragraph.

Your collision method causes tunneling issues at high speeds because points may pass through the bsp.
Also, your partial collision method seems to be a bit extraneous, since in most cases it will return true at all times, since brushes are encapsed by 360 angles.
 
T

Tirous

Guest
I think you are both oversimplifying and overcomplicating things.

BSP collision is nice but may I remind you that my only search is for carving a bsp map, of which you sir have only devoted 1 paragraph.

Your collision method causes tunneling issues at high speeds because points may pass through the bsp.
Also, your partial collision method seems to be a bit extraneous, since in most cases it will return true at all times, since brushes are encapsed by 360 angles.
Apologies mate, simply trying to help is all, i do see now what you mean and ill take that into consideration in the future.

Regardless, hope you find the answers you seek, good-day lad =)
 
M

Misty

Guest
Apologies mate, simply trying to help is all, i do see now what you mean and ill take that into consideration in the future.

Regardless, hope you find the answers you seek, good-day lad =)
Well, do you know how to carve geometry (polygons and such?) I have a few ideas but I would prefer an example.
 
Top