8 replies to this topic

[Dom_152]

I have two questions. The first is how exactly does polygon clipping against a plane work? I've looked on the net for some resources but I can't find anything good. There's an implementation in a book I have whereby a point is added at the point an edge intersects the plane but I'm not sure how the triangles are then reconstructed. The second isn't so much a Maths problem but I thought I'd put it in here. If I was to describe a mesh using a Polygon class which holds information of 3 vertices that make up the polygon how would I then be able to get the indices for the entire mesh to work? If the vertices are stored in the Polygon class how do the indices know which vertex to reference? Or should I store the indices in the polygon instead? But then when I clip it what do I do with the new vertices generated and how do I re generate the indices? Any help is much appreciated.

[Vertexmania]

Firstly you should familiarize yourself with the problem of clipping a 2d polygon against a 2d line. Afterwards it should be rather straightforward to port the algorithm to the 3rd dimension. A famous algorithm for 2d polygon clipping is the Hodgman-Sutherland-Algorithm – perhaps this can be a starting point for you.

To your second problem (meshing problem) I can only say that it depends on if you want to have a permanent change on our mesh or just a temporal change. In the second scenario it wouldn’t make much sense to change the mesh data.

[Vertexmania]

i just stumbled over the following website:
http://www.geometric...on/ClipMesh.pdf

[Dom_152]

I'll take your advice and look up 2D Clipping, thanks for the link too. After a set of triangles has been clipped it is permanent. I want to store the new data.

[Reedbeta]

Dom_152 said:

The second isn't so much a Maths problem but I thought I'd put it in here. If I was to describe a mesh using a Polygon class which holds information of 3 vertices that make up the polygon how would I then be able to get the indices for the entire mesh to work? If the vertices are stored in the Polygon class how do the indices know which vertex to reference? Or should I store the indices in the polygon instead?

I would store a mesh simply as a vertex buffer and an index buffer where every group of 3 indices makes a triangle. If you want to have triangles be objects so you can store additional data about each triangle, I would have the triangle contain a pointer to the spot in the index buffer where its indices live. That way it's easy to manipulate triangles but you don't have to do any copying when you want to send the data to the GPU.

Quote

But then when I clip it what do I do with the new vertices generated and how do I re generate the indices? Any help is much appreciated.

What I would do is simply append any new vertices onto the end of the vertex buffer. Removed vertices can be left in the vertex buffer (for now) as they will just be ignored. As for triangles, clipping will generally result in one triangle turning into two, so just re-use the original triangle's spot in the index buffer for one of the two new ones and then append the second new triangle at the end of the index buffer.

If you do a lot of these operations on the same mesh, you'll eventually end up with a lot of unused vertices, and so when they get over some limit (maybe 10% of the total) you may want to compact the vertex buffer, removing the unused vertices, and making a corresponding update to the index buffer.

[Dom_152]

Thanks a lot for the help. I can finally go ahead with my rendering module now that my designs are complete.

[Dom_152]

OK, I'm still having a bit of trouble in creating the new indices. Once I have clipped the polygons in a mesh for instance I will want to add them to a RenderData object which contains vertices, indices, materials etc. for this mesh.
I will call AppendTriangle and pass the array of newly clipped triangles I have. Adding vertices is simple enough but indices isn't. Consider this:



v1 through 4 are the original vertices of the two original triangles. v1 and v3 are shared by both triangles. Now when the plane splits them 3 new vertices are created, v5, 6 and 7. All of which are shared by two triangles. Also v2 and v4 are now shared by two triangles created from the split. So how can I insert v5, v6 and v7 into the existing vertex data while creating index data for the triangles them selves.

EDIT: I've now implemented this but any further ideas are welcome: One way I thought was to see if a vertex has already been added and if so don't add it again and make the index the position of the existing vertex.

[Reedbeta]

A different way to think about this is you do a first pass where you clip *edges* rather than triangles, so each split edge potentially adds one more vertex, but each new vertex can only be added once. Then you do a second pass where you find triangles that were split and reassign their indices / generate new triangles from the new vertices.

[.oisyn]

A good structure for this problem is the doubly connected edge list. Every edge is represented by two half-edges, one half-edge belonging to each polygon shared by the edge. Every half-edge has references to the previous and next half-edge of the same polygon, as well as a reference to the 'opposite' half-edge. Furthermore it has a reference to the face it belongs to, and to the vertex that is the startingpoint of the edge.

Using this structure, you can easily walk the whole topology and split faces and edges where needed.