Carving in a mesh
Blitz3D Forums/Blitz3D Programming/Carving in a mesh
| ||
| Hi all, I would like to understand how can I carve inside a mesh. Say I build up a box (mesh1) using addvertex and addtriangle commands. Later, if I wanted to carve a smaller box (mesh2) inside it, how could I accomplish this task ? In the code archive I've found some code about CSG functions - Boolean Union/Subtraction/Intersection - but I don't really get it, due to the lack of comments and explanations - no offence for the authors though :-) What puzzles me, is how should I arrange the new vertex that comes from the second mesh, and combine it with the vertex from the first mesh, in order to create the new triangles which will form the - now carved - surface. I may get how to realize that using two simple meshes like two boxes; but the problem comes when I want, for example, carve a cone in a box, or other complex meshes. Is there any tutorial about ? Thanks for attention, Sergio. |
| ||
| I think basically you do this: For any boolean operation: Split all the polygons in A with the planes of the polygons in B, and vice versa. Operate on these split versions of the meshes. To subtract B from A: 1. Flip polygons in B. 2. Find all the polygons of B which lie inside A. Add those to final mesh. 3. Find all polygons in A which lie outside B. Add those to the final mesh. 4. Weld vertices of final mesh if desired. To add A and B: 1. Find all polygons of B which lie outside A. Keep them. 2. Find all polygons of A which lie outside B. Keep them. 4. Weld vertices of final mesh if desired. AND and NOT operations aren't all that useful so I won't bother to explain those. |
| ||
| Thanks Swift for the reply. I don't really get what you mean with polygons and planes. I think you mean triangle for polygons, but what about plane ? <<Flip polygons>> = I guess you mean to reverse the mesh here ? So that is not visible from outside, but from inside ? <<Find all the polygons of B which lie inside A>> That's not a trivial task I guess. It's exactly what puzzles me now. How I can determine that a triangle (of mesh B) is inside the mesh A ? Should I check all the vertex coordinates (of that triangle) against all the vertex coords of the mesh A ? And more, how can I determine the vertex sequence to use, in order to add the mesh b surface triangles to ones which belongs to mesh a ? Maybe using TriangleVertex ? The problem here is that is not enough to add just the (flipped) triangles which lie inside the mesh A, because the surface of the mesh A should also change. It does not change automatically when you add new triangles. Suppose a big cube A and a cube B which is one half smaller of cube A. Cube B penetrates for its half height through a face of cube B. In case of carving (subtracting), the two triangles of that face (the one being penetrated) should be deleted, and the whole face structure should be re-arranged with the new triangles added... My brain hurts now.. You know, conceptually I can get your drift; but I find really tricky to actually realize it, having to use only the surface and vertex commands. Anyway, I'll try to realize your concepts. Thank you. :) Sergio. |
| ||
| Because I suck at 3D ;) this is the only way I can think of to tell if a polygon from MeshB is inside MeshA. 1. Find the furthest point from MeshA on MeshB. 2. Create a pivot (PivotB) there. 3. Find the XYZ coordinates of the vertex on MeshB that you're testing. 4. Create a pivot (PivotA) there. 5. Find the vector angle between the two points. 6. Move PivotB towards PivotA along this vector until it collides. 7. Move PivotB back one frame to where it was before it collided. 8. Hide MeshB. 9. Use EntityPick to find the nearest entity to the PivotA. 10. If it returns MeshA, the polygon is inside MeshA. If it returns PivotB, the polygon is outside MeshA. While that process would only take a hundredth of a second to process, it seems a very long and cubersome method of checking what should be a simple process. Anyone got a better method? +BlackD [edit:] Actually, just realised afterward, you could shorten that to: 1. Using vectors, find the furthest polygon from MeshA on MeshB. 2. Create a pivot there. 4. Move the pivot towards the polygon you're checking, testing for collision with MeshA. 5. If it never collides, then the polygon is outside MeshA. If a collision with MeshA does occur, then obviously the polygon is inside MeshB. Though you'll probably want to test individual vertices, not triangles, as part of a triangle may be inside while the center of it is outside. This assumes that there is some point of meshB outside meshA. If there isn't, then the carve won't happen as it won't find any polygons which meet - which they shouldn't.. they're all inside.[/edit] |
| ||
| "I think you mean triangle for polygons, but what about plane?" When I said planes, I mean the planes which the triangles lie in. A triangle is three points, which lie on a plane. A quad is two triangles which lie on a plane. A polygon is a bunch of triangles connected together that lie on a plane. "I guess you mean to reverse the mesh here ? So that is not visible from outside, but from inside?" Basically, yes. But you don't actually have to flip any polygons exept those which you ultimately end up keeping that belong to the object I said to flip. "That's not a trivial task I guess. It's exactly what puzzles me now. How I can determine that a triangle (of mesh B) is inside the mesh A ? Should I check all the vertex coordinates (of that triangle) against all the vertex coords of the mesh A?" I think you're in a bit over your head trying to tackle CSG if you have to ask things like this. :-) (CSG = Constructive Solid Geometry = Boolean opaerations on 3D models) To find out which polygons of B are inside A, assuming you have used the planes defined by the polygons in A to split all the polygons in B, all polygons in B will now either be entirely inside, or entirely outside A. That's why you do the split. To find out if they are inside or outside, all you need to do then is check every vertex in B to see which side of every polygon in A it is on. If it is on the inside side of every plane defined by a polygon in A, then it is inside A. You then check each triangle and if any vertex that it uses is inside A then it too is inside A. If A can be a concave object, which it may very well be if you already did one CSG operation on it, then you'll have to do a slightly different test to determine if each point is inside A. To do that, you need to cast a ray from the vertex in any direction to infinity. Let's say, along the X axis in the positive direction. If your ray crosses an odd number of polygons, then you are inside A, otherwise you are outside A. "And more, how can I determine the vertex sequence to use, in order to add the mesh b surface triangles to ones which belongs to mesh a ? Maybe using TriangleVertex?" Basically, find all the vertcies which you're gonna keep, and add those, and then find all the tirnagles you're going to keep, and then use that command I guess it is to find the original vertex indexes for that triangle and convert them to the new vertex indexes, because the numebrs will be different cause you have fewer vertices. If you need more help type CSG 3D POLYGON into google and it will come up with lots of pages with info. |
| ||
| Thank you very much sswift, I'll try out the above concepts. Sergio. |
| ||
| Semar - where did you find the existing CSG functions? Were they written in B3d 'cos I wouldn't mind a look? |
| ||
| http://www.blitzbasic.com/codearcs/codearcs.php?code=560 :) |
   |