# How to cut a desired shape out of a mesh?

I want the player to be able to cut a hole through a wall, similar to what's shown in this video

I know for the fact that it's really difficult to achieve, so I was wondering how I can cut a shape out of a simple mesh at run time (or even cut a shape out of a 2D sprite).

• good question i look forward to seeing how it's done also. But I would say on this site it will help you to get better answers/help if you show some work/methods you have already tried and where exactly you ran into a problem – Big T Larrity Sep 6 '19 at 12:16
• well unfortunately i don't know much about vertices and creating meshes at run time.so , i was hoping someone with more skills could help... maybe someone could show me a tutorial video or a forum about cutting through mesh or sprite. – h00man13 Sep 6 '19 at 12:35
• i understand where you are coming from trust me. sadly I don't know the answer or id try to help. But this link could be a good startinbg point for mesh editing in c# unity stackoverflow.com/questions/32733293/… – Big T Larrity Sep 6 '19 at 12:43
• This implementation is likely a sprite cutout as thats a 2D (for all intents and purposes) fence. For a 3D format you'll want to use some boolean operations arxiv.org/pdf/1308.4434.pdf – CobaltHex Sep 6 '19 at 16:24
• i could work with some sprite cutting tool, if there is any – h00man13 Sep 6 '19 at 16:43

I have done this for automated medical CAD procedures as well as game engines, and will attempt to provide adequate information in order for you to accomplish this task on your own, but I will not be able to provide the script for you as this is a non-trivial task that requires a good deal of computational geometry and problem-solving. What you're asking is quite complicated and it is for this reason you have not seen this mechanic in most games.

Hurdles and strategies

1. Non-Convex collision detection - Say your user were to cut a hole in the middle of a wall. Not terribly complicated to do by itself, but we'll get to that. They now have presumably two pieces of geometry. The inner piece, assuming your user made a clean triangle, is a convex object meaning a straight line cannot cross through more than two points on the surface. This is the best-case scenario, as modern collision detection algorithms are quite fast because they rely on certain mathematical principals which only apply to convex shapes. As for your second shape, which is a large box with a gaping hole in the middle, it is no longer convex. In fact, it's horribly non-convex. While there are solutions to non-convex collision detection via hand-crafted collider-hierarchies (as sometimes seen with ragdolls) or through automated procedures such as HACD or V-HACD, neither of them are easy to implement. Fortunately, it appears as though someone has attempted to port V-HACD to unity. Having not used it, I can't say whether their implementation works or not. I can say that typically HACD is something you would precompute and package the output with your game. That being said, the problem becomes significantly easier in 2D if that's a viable option for you and may be something to take a look at.

2. If collisions are not a problem for you, you're off to a great start. Next comes graphics. You will need to be familiar with UV coordinates and clipping algorithms. To slice a wall, the resulting geometry will need to retain the UV coordinates. I suggest familiarizing yourself with algorithms such as the Sutherland-Hodgman clipping algorithm, which has been around since 1974 and is still used today for various procedures. The meat and potatoes though, using half-planes or half-spaces to determine the side of a plane in which a point resides, will be the primary functional tool used throughout the procedure. It can not only slice the topology, but you can even slice vertex attributes (like UV coordinates) at the same time in one go.

3. Geodesic Pathfinding and Topological Data Structures - This is where it gets even messier. Unity (to my knowledge) does not natively employ a dynamic mesh data structure which will allow you to easily accomplish this task, which means that every destructible mesh will need to be converted to a traversable graph structure, sliced, and then converted back to the format in which unity expects to pass to the renderer. If your slicing does not occur in one fell swoop, i.e. a slow laser cutting the wall instead of a cookie-cutter stamping out a shape all at once, then you will have to do this every frame. Presumably, your data structure would persist through each frame, and you will have to tell unity to drop the current mesh for the newly-sliced version. I'm not familiar with unity's graphics implementation, but as far as vertex buffer objects and index buffer objects go, there is a fair amount of overhead involved with uploading new meshes to the GPU. The lag-time when transferring data from the CPU to the GPU is one of the worst unavoidable bottlenecks in graphics, something which a lot of smart people spend a lot of time strategizing over. This is why most meshes are uploaded once at the beginning of a level.

So on to the data structure and algorithm;

The Data Structure

A popular data structure used in topological deformation and slicing procedures is called a Half-Edge Mesh, also known as a Doubly Connected Edge List. It's by no means the best graph for all scenarios, but it's a thoroughly tested structure that I've personally employed to accomplish similar tasks and can speak to its versatility. If this was your own engine and not unity, I would suggest moving your collider geometry implementation toward this as it supports non-triangulated surfaces and can be used to optimize certain collision detection algorithms. (image courtesy of wikipedia commons)

As a high-level overview, it's simply a directed graph made up by a doubly-linked list of vertices and edges with the caveat being each physical edge on the geometry is represented by two edges in the graph, known as twin edges. Each of these edges owns 1 vertex (usually represented by an index instead of the physical point), and has a pointer to the next edge, previous edge, and its twin-edge which traverses an adjacent face in the opposite direction. This is the big feature of half-edge graphs, allowing one to iterate an entire polygon face by simply walking the next pointer until you're back where you started. This is essential to the procedure, as it allows us to preserve the winding order of the vertices as they must always be uploaded to the GPU in the same way. Otherwise, you get a big gaping triangular hole wherever the winding order was flipped. I advise looking for existing implementations in Unity for this, as the helper functions you will need to write (such as inserting a vertex) will take a lot of white-board planning and diagramming to get right.

So now, assuming you've successfully converted your mesh into a half-edge data structure, you can now traverse the surface of the mesh and you're ready to try your hand at geodesic pathfinding. To begin, you would use raycasts or some other method involving your mechanic to somehow pull topological information such as which face of the geometry was hit, in order to find a starting point. If you plan on drawing, I suggest saving these points and converting them into a Catmull-Rom splines because if your user is raycasting each frame, you will need to have a path to follow and splines are a simple way of providing "infinite" precision (because it is an implicit curve), instead of limiting yourself to wherever the user happened to be pointing that frame.

Begin by inserting a point into the geometry at the first spot your user hit. You will need to have some sort of triangulation utility handy, iterative algorithms like Bowyer-Watson or the Earcut Algorithm. This is where the problem-solving actually starts, as you will need to get your hands dirty to implement a rag-tag Constrained Delaunay Triangulation (referred to as CDT) or just a simple constrained triangulation (which there isn't much information on, as almost everyone needs Delaunay triangles, though we do not) which is quite literally a field of study in and of itself. You'll notice in the illustrations provided by Wikipedia on the Bowyer-Watson algorithm that at each iterative insertion, the order in which they are added tend to be preserved via an edge connecting each new vertex at each step. Another hint I can give you from the result of my own experimentation, is that if you look at any convex non-triangulated half-edge diagram, they can be instantly triangulated by connecting from the "head" of an edge, to the tail of the previous edge. i.e.

HalfEdge* edge = face.edges[0];

while(!edge->IsTriangle())
edge = ConnectEdges(edge, edge->prev);



Take that for what you will and roll with it cause it only gets worse from here.

Now you have inserted and triangulated your face, next comes traversing the graph. I suggest precalculating the inward-facing normal of each edge, essentially if you were to rotate each edge's direction 90 degrees to face the center of the triangle, that's the direction you want. Treat that like a half-plane like I mentioned earlier with the sutherland-hodgeman clipping algorithm. You want to continue inserting and triangulating occasionally until the point drawn by your player crosses the edge of a triangle, at which point the sign of the dot product will switch from positive to negative as the dot product with a plane represents the signed-distance of the point from that plane. Split that triangle at the clipped point, inserting it into your graph, and continue on to the next triangle.

Now while all that's going on, if you're in 3D you need your trusty helper functions to be silently creating "internal" edges (literally meant for the inside of the polyhedra, as we are treating it like a solid object which suddenly gains a new internal surface) each time you add your new half-edge pairs to the graph, and make sure they connect with one another, as you will eventually need to triangulate that surface when the procedure is complete.

That about covers it as far as down-and-dirty geodesic pathfinding goes, the rest of the procedure boils down to your mechanics and how you wish to start and stop the process. Ideally, the ends should connect (the spline simplifies this) so that you can easily create your new shapes without thinking much about it. That only leaves conversion back to renderable geometry, which I will leave up to you.

Aside from this, you may want to consider a high-density voxel object approach, which I have no experience with, but have seen it employed for destructible environments using marching cubes or dual contours to smooth the mesh and make it appear like you're not using voxels (as seen in games such as No-Man's Sky).

My point here is that it is possible, but you have to really want it and be willing to put in an enormous amount of time and research. I'll leave you with a few other pertinent white papers and final words of wisdom to mull over.

• Debug drawing will be your BEST FRIEND.
• Consider writing a quick function to export your graph to a wavefront obj at any step, particularly for the triangulation to ensure you aren't accidentally flipping winding order, and again after you split the mesh into two parts. The internal edges are TRICKY to get right.
• Visual Studio can be used to quickly open and view .obj files and can even detect changes to those files so you don't have to open them again
• Use a whiteboard to draw the Half-Edge diagrams with labels, doing it in your head is an easy way to drive yourself insane. I still have occasional triangle-related nightmares.

i dont think there is anyone that can tell you how this exactly works. there should be lots of elements to make this happen but i can give some guessing.

1) if you look for cutting for that is in metal gear rising the sward works like a plane equation with borders. you can make a calculation for vertices Up and Down of that plane. then do a capping algorithm to cover cut. but certainly lots of other things should be handled to make it work properly.

2) it seems in your example, there is a plane with a fence texture over it. maybe on shooting the lazer gun, it raycasts and only removes the nearest polygun and after that a calculation that seperated polygons did make a whole new model, so just adding something like rigidbody and make it fall.

3) in image processing there are region detection algorithms. maybe another binary image is calculated in hidden mode that whole page is white and when lazer is being shot to it, pixels turn to black. so after that close region can be calculated.

remember what is say is based on guessing and there is much distance from implementation.

• If you don't know how this is done, then may I suggest it might be premature to post an answer? Cutting a polygon is certainly tricky to get right, but it's not a mysterious magic trick — there is a concrete algorithm to do this, that an answer could describe. – DMGregory Sep 6 '19 at 15:50
• @DMGregory should i remove my answer? – virtouso Sep 6 '19 at 15:51
• I leave that judgement call to you. – DMGregory Sep 6 '19 at 15:52
• @DMGregory i dont think that answer prevents better answers but all algorithms are based on methods i said. sometimes hints to search and test is better than nothing – virtouso Sep 6 '19 at 15:57
• someone actually has done something similar but it's too clumsy. youtube.com/watch?v=Anjl_y1Rb-8 – h00man13 Sep 6 '19 at 16:40