   Breakable objects
  I''m working on an algorithm for breakable two dimensional rocks. I''m putting it in here, in math and physics, because I don''t really care about code right now, just the mathematics. Once I have the mathematics, I''ll be able to code it on my own.Now, I have an idea for a simple game, similar to asteroids, but with a slight modification. There is only one asteroid, it is really large, and it has minerals and metals spread throughout it (think like the ol'' plum pudding model of an atom). The player will blast away little chunks of the asteroid in order to get at the valuable stuff.Now, one could piece together the asteroid out of little blocks, and then the game becomes a cross between asteroids and arkanoid (weird...), and that is a consideration, but I would rather not do it quite that way, as it''s not the graphical image I had in mind.What I would rather do is represent the asteroids via vertices, adding new vertices as the asteroid is shot up.In example one, the original asteroid was only a pentagon, 5 vertices. After it was hit, a triangle shape was blown off of it, adding three new vertices, making 8 vertices total.In example two, the ship is firing at a non-normal angle. As a consequence, the "force" of the blast is not as direct, leaving only a smaller whole.Example three is my work so far. Each shot has a "blast triangle". The blast triangle "points" in the direction that the shot is travelling. One vertex of the triangle goes IN the polygon, one connects to the edge of the polygon, and the last is left to outside the polygon (unless the shot came in at a normal angle, in which case there are two vertices on the edge of the polygon).Any suggestions, thoughts, anything? 
  I actually wrote out a model for this a long, long time ago...Basically, with the first few hits, the object would crack, not break. It would crack where it was weakest (with a map of the strength of random points in the asteroid). The force would be subtracted from the point that was hit, and a weaker force would be subtracted from each point it hits (according to the distance form the hit point) as it passes through the asteroid. At 0, the point would turn into a crack, connected to the nearest point (within reasonable distance) with a strength of 0. When a strength drops below 0, more points can be spawned and cracked, OR a small fragment can break off.If two cracks connect, the piece can be broken off and become another asteroid.That's basically the design I had... it might not immitate real physics, but it's a good approximation without getting into nasty math.    EDIT  : The force would be subtracted and projected into the polygon like a triangle.EDIT  : DIAGRAM CLICKY [edited by - Axiom on February 8, 2004 3:44:03 PM];  capn: ah, but what if you hit a corner?just a thought, but couldn''t you represent the asteroid as a texture (in system memory, not graphics)? Then, when you fire a shot, you can do some simple 2d pixels tests to find the first point of intersection, and then delete all of the pixels around the blast point. you could then upload the texture to the graphics card (this wouldn''t be too expensive as it only needs to be done on a successful hit).you could also check to see if all the sounding pixels for the objects inside have been killed. if so, free the objects.no, i don''t have any maths for you. google "2d bitmap intersection" for some very dandy links. ;  that looks fine for a simple triangle edge, but what would happen if you started using this algo with an already pretty fragmented asteroid. I''m not sure this would work. Another solution, tesselate the original asteroid shape, with small perturbation (for each triangle edge, get roughly the midpoint, and interconnect the midpoints, that will split the parent triangle into 4 smaller chunks, and do that recursively). Once you have a decent enough level of detail, stop, and when you fire a shot, do a radius check with the point of collision of the shot and the triangles on the asteroid. detach all triangles included into the blast radius from the main asteroid. You can also use the tesselation properties (basically, it''s a recursive subdivision), to quickly determine the triangular areas inside a radius. Furthermore, if a large chunk is detached, all you have to do is, in the triangle tree, detach a branch of the tree all together. You can further split the detached chunk the same way. ;  using the verlet stuff and stiff constraints, you can do something like Axiom said. When a crack appear, remove a segment constraint, and part of the asteroid will come loose, all by itself. Also, the asteroid will react to shots you fire at it. It will start to spin, and move about after it gets hit. ;  Your concerns about the corners and already-fragmented edges were exactly my concerns.I like the tesselation idea. It is still the "arcanoid" idea, however, it is with a different shape of block.so, each mini-triangle would be a node in a sort of binary tree? hmm, I think I can see it.So, if a bullet hit #9, it would destroy #9 and sever #8's and #15's connections, leaving them to float free.edit1: Hmm, I grew that from the top down, 1 through 16, when I think it would be better to grow it from the center out, creating a hexagon. Then, each triangle would look up its linkages to find out where it is supposed to move, with the #1 node being the root/master.   edit2: I think hexagons would be better than triangles, as then I won't have to worry about which way is "up" or "down" for the triangle.[edited by - capn_midnight on February 8, 2004 4:03:24 PM] [edited by - capn_midnight on February 8, 2004 4:05:27 PM];  actually yeah, you can tesselate each polygon any way you want, use quads instead of triangles, as long as the shape retain a nice aspect ratio (don''t squish them to much, as the subdivision will make it even worse). The advantage is, you can keep the LODs in a tree structure, and remove whole parts of the asteroid by simply removing a branch in the tree. If you use quads, You can remove a quarter of the tree by removing one of the root subdivisions all together, and attach it as a root to another asteroid. For collision detection, it''s also beneficial, as you just have to trasverse the tree from lowest LOD to finest LOD. ;quote:Original post by oliii  actually yeah, you can tesselate each polygon any way you want, use quads instead of triangles, as long as the shape retain a nice aspect ratio (don''t squish them to much, as the subdivision will make it even worse). The advantage is, you can keep the LODs in a tree structure, and remove whole parts of the asteroid by simply removing a branch in the tree. If you use quads, You can remove a quarter of the tree by removing one of the root subdivisions all together, and attach it as a root to another asteroid. For collision detection, it''s also beneficial, as you just have to trasverse the tree from lowest LOD to finest LOD.  ...yeah... I think that''s the ticket... wild stuff, thanks guys. We''ll see how this goes.;  Haven''t read all through, may have been suggested... have blocks but not regular shapes. Have predetermined ''fault-lines'' which allow bits to break off in a seemingly random way. The details are up to you but it seems reasonable, what do you think? ;  Anyone seen any articles on the Red Faction terrain engine? 