• Advertisement

3D Dynamic Dismemberment and slicing through limbs

Recommended Posts

TL;DR Mesh slicing... Anyone try to venture that way?

So I'm aware of this thread: 

 

 

But since it's from 2004, I wanted to ask.. are there any games since (or ever) that actually have real dynamic mesh slicing?

The only one that I know of that kind of does this is Metal Gear Rising Revenge..?

Anyone know / can guess, how they did this? Is this mesh slicing in real time? It doesn't seem precomputed at least..

I tried myself at programming a mesh slicing algorithm, the other day, but for my routine, at about 200 Vertices it gets too slow for real time.

Using this paper here:

http://www.dainf.ct.utfpr.edu.br/~murilo/public/CAD-slicing.pdf

(Obviously some bugs, face orientation messes up, and I have to say it was completely on the CPU, and didn't spend much effort optimizing anything)

slicing-01.gif

Edited by teutoburger
missing info

Share this post


Link to post
Share on other sites
Advertisement

Look at this: 

 

really a good game as well.

Slicing definitively realtime, remember software rendered games which did this for every polygon intersecting a frustum plane.

Maybe look for polygon clipping.

Here is a routine that i use in a preprocessing tool, but you need to build and triangulate the large poly where the volume intersects the plane alongside:

Edit: Thinking of it, you should use only convex polyhedra, so slicing always results in only convex polygons.

Complex shapes can be made by multiple convex shapes (like we do for physics collision detection).

And if you have poly adjacency information at edges, you can slice in order so the volume poly emits in correct order as well and no searching is necessary to connect unordered split edges. This way you also quickly reject polys that do not intersect the splitting plane.

 

 

	inline int32_t ClipTexmapPolygon (const TexmapPolygon *pin, const vec &plane, TexmapPolygon *pout, const int32_t space)
	{
		if (pout->numAvailableVertices < pin->numVertices + 1)
			pout->Resize (pin->numVertices + 1);

		int32_t i, curin, nextin;
		float curdot, nextdot, scale;
		TexmapPolygon::Vertex *pinvert, *poutvert, *nextvert;

		pinvert = pin->vertices;
		poutvert = pout->vertices;
		curdot = pinvert->puv[space].Dot (plane);
		curin = (curdot >= plane[3]);
	
		int32_t ret = -1; // assume inside

		for (i=0; i<pin->numVertices; i++)
		{
			nextvert = &pin->vertices[(i+1) % pin->numVertices];
			// keep if inside	
			if (curin) 
			{
				*poutvert++ = *pinvert;
			}
		
			nextdot = nextvert->puv[space].Dot (plane);
			nextin = (nextdot >= plane[3]);
			
			if (curin!=nextin) // add clipped vertex if plane splits edge
			{
				assert (fabs(nextdot - curdot) > FP_EPSILON);
				ret = 1; // clipped or outside
				scale = (plane[3] - curdot) / (nextdot - curdot);

				for (int32_t c=0; c<3; c++)
					poutvert->puv[c] = pinvert->puv[c] + (nextvert->puv[c] - pinvert->puv[c]) * scale; // position and 2 uc channels

				poutvert++;
			}

			curdot = nextdot;
			curin = nextin;
			pinvert++;
		}

		pout->numVertices = int32_t(poutvert - pout->vertices);
		if (pout->numVertices < 3) return 0; // outside
	
		return ret;
	}

 

Edited by JoeJ

Share this post


Link to post
Share on other sites
12 hours ago, JoeJ said:

And if you have poly adjacency information at edges

something like a winged edge structure, right?

 

12 hours ago, JoeJ said:

This way you also quickly reject polys that do not intersect the splitting plane.

I think I get the idea of how the triangle adjacency information allows you to disregard the majority of triangles. Correct me if I'm wrong.. 

(1)Make an empty Set L of triangles (edges) T that intersect the plane.

(2) Pick any triangle (or edge) T that intersects the plane. (I have questions about this step actually*..)

(3) Add T to L. 

(4) Regard each adjacent triangle (edge) of T and check if it is intersecting the plane. If it isn't, you can disregard all its adjacent triangles (edges) (herein lies the major part of the optimisation for this algorithm). If one of them does intersect the plane, you take it as your current T and repeat the step.

 

*How do you find the very first T, that intersects, without looking up every triangle in the mesh until you hit one that intersects the plane? So the worst case is you check them all, the average case is somewhere around 1/2'N checks? Or is there a much better way that I'm missing here?

 

 

Edited by teutoburger

Share this post


Link to post
Share on other sites

Regarding 

ClipTexmapPolygon (const TexmapPolygon *pin, const vec &plane, TexmapPolygon *pout, const int32_t space)

This routine constructs the intersection polygon of mesh and plane, right? Its a 2d polygon.

Viewing the parameter list, why is one vec enough to define the plane? Shouldn't there be a distance and a normal? Or a Point-on-plane and a normal?

Share this post


Link to post
Share on other sites
59 minutes ago, teutoburger said:

something like a winged edge structure, right?

Not sure what that is, but i mean for each edge have indices to left / right triangle. Further The whole mesh needs consistent winding order (each triangle has clockwise vertices. The mesh needs to be closed... the typical requirements).

59 minutes ago, teutoburger said:

I think I get the idea of how the triangle adjacency information allows you to disregard the majority of triangles. Correct me if I'm wrong.. 

Find a edge that intersects the plane, split it and go to the left trianlge, find the other edge of that triangle that intersects the plane and continue with the other triangle from that edge until you get back to the starting edge. During that add each split point to the volume / plane intersection polygon. 

No Set required. Processing any edge just once. Works only for convex meshes (otherwise need to find all starting edges, not just any single one).

It's like cutting a mesh made of paper with a scissor, so just in order vs. poking individual cuts into random triangles like traditional frustum clipping would do. 

(I've just implemented tracing a crossfield on mesh surface, which is pretty similar and i used this simple algorithm without issues.)

 

59 minutes ago, teutoburger said:

*How do you find the very first T, that intersects, without looking up every triangle in the mesh until you hit one that intersects the plane? So the worst case is you check them all, the average case is somewhere around 1/2'N checks? Or is there a much better way that I'm missing here?

Yeah you are right - the need to find a single intersecting edge kinda destroys the advantage we do not walk to triangles not touching the plane while cutting.

But you could speed this up when everything else works as well: 

Pick a random vertex and select the edge closest to the plane, continue until you find an intersecting edge.

Again this works only for the convex case (and you may need more adjacency information like vertex knowing all its edges - pretty annoying to maintain ;)

Edited by JoeJ

Share this post


Link to post
Share on other sites
22 minutes ago, teutoburger said:

This routine constructs the intersection polygon of mesh and plane, right? Its a 2d polygon.

Viewing the parameter list, why is one vec enough to define the plane? Shouldn't there be a distance and a normal? Or a Point-on-plane and a normal?

All 3D. The routine processes a polygon with an array of 3 3D vectors, 'puv'. (I store 3D position and uv channels there)

My vec has storage for 4 numbers, so in this case i use plane[3] to store the plane distance to the origin. (confusing, but seems i was too lazy to create a plane class.) 

The original code came along Michael Abrashs Graphics Programming Black Book.

 

 

 

Share this post


Link to post
Share on other sites
11 minutes ago, JoeJ said:

Works only for concave meshes

just to remove any ambiguity here, convex(?), you probably meant to say convex here, right? 

 

Share this post


Link to post
Share on other sites
30 minutes ago, JoeJ said:

Works only for concave meshes

wait.... I think it would work for all convex meshes and also for those concave meshes without inner holes.

 

 

Share this post


Link to post
Share on other sites
17 minutes ago, teutoburger said:
30 minutes ago, JoeJ said:

Works only for concave meshes

just to remove any ambiguity here, convex(?), you probably meant to say convex here, right? 

Ooops, i did it again. Convex is right, yes - fixed.

Share this post


Link to post
Share on other sites
Just now, teutoburger said:

wait.... I think it would work for all convex meshes and also for those concave meshes without inner holes.

Yes, but you need to find multiple starting edges.

But the mentioned optimization to find a start edge would fail: I could get stuck in a sink. (I'm not sure at what complexity this optimization would be a win anyways, due to the need to maintain more adjacency).

 

There is however a algorithm to calculate a cut graph for a mesh that cuts it to a topological disc. (Using spanning tree and it's dual, i'd need to look it up...) Eventually you could precompute that cut graph, and then only check those edges to find intersecting edges. But i need to think about this for some time - not sure if it works yet... (Also unsure if you'd need to recalculate this graph for sliced pieces so you can slice tham again - that would be much worse than just checking all edges.)

Share this post


Link to post
Share on other sites

 

I see.. so you split up a mesh into its convex sub-meshes (with all triangles clockwise), and you have a winged-edge-equivalent structure (that's exactly what you mean by the adjacency information for each vertex, edge and face).

Yes so, the problem remains with finding the first intersecting edge. If you randomize the picking of the first vertex, then you have the best average case performance, but it can still happen that it's the worst case.

The algorithm I used so far, needs a preordered mesh as input mesh.

For each Triangle you note its zMin and zMax. That's simply the smallest (largest) z component of the triangles vertices.
Then you order the triangles by their zMin. (You could also save the mesh to file in that face order)

Then you can intersect the mesh with any plane in distance D parallel to the xy-plane (meaning the plane containing the x and y-axis), pretty optimally, by disregarding all triangles that either have zMax < D or zMin > D.

You only have to check those triangles for which zMin < D < zMax.

Pretty restrictive because it works only for planes that are parallel to the xy plane, right?
 
But you can rotate any arbitrary plane to be parallel to xy and rotate the mesh the same way. Of course, then you have to recalculate the zMin and zMax for each triangle (but should be faster than checking for intersection).
 
This works for concave too.
 
Not sure how this compares to your approach, though, regarding performance.
 
I'd have to implement and compare. That'll take some time.
 
 
 

Share this post


Link to post
Share on other sites
1 hour ago, JoeJ said:

There is however a algorithm to calculate a cut graph for a mesh that cuts it to a topological disc. (Using spanning tree and it's dual, i'd need to look it up...) Eventually you could precompute that cut graph, and then only check those edges to find intersecting edges. But i need to think about this for some time - not sure if it works yet... (Also unsure if you'd need to recalculate this graph for sliced pieces so you can slice tham again - that would be much worse than just checking all edges.)

Thought about it. It would work with minor modifications for something like a torus, but it would fail for a bumpy torus with sinks on the surface, so useless. :( 

55 minutes ago, teutoburger said:

The algorithm I used so far, needs a preordered mesh as input mesh.

Thought about presorting as well, but i end up preferring either a tree or sorting in 3 axis to lift the 1D restriction. And rebuilding / adapting that stuff for both split pieces? Only worth if you have really high resolution meshes. Checking all vertices against the plane has perfect caching so brute force will be hard to beat i guess.

Note that if you restrict yourself to convex meshes the 'walk from random start towards the plane' approach will be best, similar runtime than hopping in a presorted list or walk a tree but no additional data structure required.

 

Edit: Presorting does not require to rebuild or adapt anything after the slice, right? And using 3 axis and selecting the best fit should work as well? You would need to create a bounding box of the plane intersetion with the objects bounding box, and then check all edges within that i guess, (so still a lot in worst case).

Edited by JoeJ

Share this post


Link to post
Share on other sites
1 hour ago, JoeJ said:

but no additional data structure required.

Yup, none but the adjacency structure, which can be built offline, so who cares.

Share this post


Link to post
Share on other sites
1 hour ago, JoeJ said:

Edit: Presorting does not require to rebuild or adapt anything after the slice, right?

Not for the original mesh. But you now have two new split meshes, each one having an open section, where the plane cut through. That will have to be closed up still. This means, clockwise-ordering the segments, that make up the 2d polygon (which is a convex one, if you had a convex mesh to begin with) and then triangulizing the 2d-polygon (splitting it into clockwise triangles). And lastly adding the new triangles to each of the new split meshes to close the open section.

Edit: Actually its a 3d polygon, in terms of data (made up of 3d vertices) but it "lives" in the slicing plane.

Edited by teutoburger

Share this post


Link to post
Share on other sites
2 hours ago, JoeJ said:

And using 3 axis and selecting the best fit should work as well?

That gets my brain into a knot. You'd have to order the triangles by projected-distance on the vector going from origin to plane. So for each triangle, you project each vertex on to the vector going from origin to plane.

This gives you a Vmin, and Vmax for each triangle. Corresponding to the zMin and zMax of the 1D approach outlined above. The preordering here is more costly. There's the projection (actually not sure how that is accomplished exactly, something with dot product maybe?) and the length involves a square root, which maybe you can avoid by using the squared length? 

Edit: or perhaps I'm missing completely out on what you meant by the best fit 3 axis approach... 

Edited by teutoburger

Share this post


Link to post
Share on other sites
59 minutes ago, teutoburger said:

Not for the original mesh. But you now have two new split meshes, each one having an open section, where the plane cut through. That will have to be closed up still. This means, clockwise-ordering the segments, that make up the 2d polygon (which is a convex one, if you had a convex mesh to begin with) and then triangulizing the 2d-polygon (splitting it into clockwise triangles). And lastly adding the new triangles to each of the new split meshes to close the open section.

Ah yeah, i ignored you need to add new stuff no matter if you sort tris / edges or verts. So resorting (at least insert) unavoidable, which means you run over the entire sorted list to copy and resort it. Further, if you use 3 axis, you can't sort primitives but just indirection indices, so jumping around in memory a lot until you find first and last element in range, making a win over brute force again unlikely.

9 minutes ago, teutoburger said:

or perhaps I'm missing completely out on what you meant by the best fit 3 axis approach... 

I meant 3 independent sorted lists of indirect indices to triangles (or edges), and you pick the one best fitting the plane normal. The worse the fit, the larger becomes the volume containing potential intersecting edges.

However, you spend a lot effort maintaining a data structure that you need only one times. Likely this has the same cost as brute force search while throwing other data out of cache. Convex decomposition to avoid all this seems much more attractive, which is necessary anyways if you want to do collision detection for the pieces.

You could order the primitives themselves by morton code in memory, which improves caching in any case.

 

 

Share this post


Link to post
Share on other sites

Looking at the convex decomposition image from that presentation it becomes clear to me that this is not really a option for detailed visual meshes.

I think creating clusters of triangles with a bounding box might be better than sorting: Checking all boxes with brute force is fast, then checking all edges per cluster remembering split edges and eventually intersections. During the scissor walk results could be reused.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now


  • Advertisement
  • Advertisement
  • Popular Tags

  • Advertisement
  • Popular Now

  • Similar Content

    • By mister345
      Hi, I'm on Rastertek series 42, soft shadows, which uses a blur shader and runs extremely slow.
      http://www.rastertek.com/dx11tut42.html
      He obnoxiously states that there are many ways to optimize his blur shader, but gives you no idea how to do it.
      The way he does it is :
      1. Project the objects in the scene to a render target using the depth shader.
      2. Draw black and white shadows on another render target using those depth textures.
      3. Blur the black/white shadow texture produced in step 2 by 
      a) rendering it to a smaller texture
      b) vertical / horizontal blurring that texture
      c) rendering it back to a bigger texture again.
      4. Send the blurred shadow texture into the final shader, which samples its black/white values to determine light intensity.
       
      So this uses a ton of render textures, and I just added more than one light, which multiplies the render textures required.
       
      Is there any easy way I can optimize the super expensive blur shader that wouldnt require a whole new complicated system?
      Like combining any of these render textures into one for example?
       
      If you know of any easy way not requiring too many changes, please let me know, as I already had a really hard time
      understanding the way this works, so a super complicated change would be beyond my capacity. Thanks.
       
      *For reference, here is my repo, in which I have simplified his tutorial and added an additional light.
       
      https://github.com/mister51213/DX11Port_SoftShadows/tree/MultiShadows
       
    • By Matt_Aufderheide
      I have never quite been a master of the d3d9 blend modes.. I know the basic stuff, but have been trying for a while to get a multiply/add blending mode... the best I can figure out is mult2x by setting:
      SetRenderState(D3DRS_DESTBLEND, D3DBLEND_SRCCOLOR);
      SetRenderState(D3DRS_SRCBLEND, D3DBLEND_DESTCOLOR);
      //this isn't quite what I want.. basically I wonder if there is a way to like multiply by any color darker than 0.5 and add by any color lighter than that..? I don't know, maybe this system is too limited...
    • By regnar
      Hi!
      I've been trying to implement simple virtual globe rendering system using "3D Engine Design for Virtual Globes" book as a reference.  What I do is I use 6 planes to form a cube, send it to GPU and use vertex shader to form a sphere and add random noise to simulate surface of the planet. The problem is how do I do CPU work on the vertex data from now on - how do I get world space coordinates of a terrain patch to perform LOD techniques, how do I do camera-terrain collision detection etc. ?
    • By KarimIO
      Hey guys,
      Are lightmaps still the best way to handle static diffuse irradiance, or is SH used for both diffuse and specular irradiance now?
      Also, do any modern games use direct light in lightmaps, or are all direct lighting handled by shadow maps now?
      Finally, how is SH usually baked?
      Thanks!
    • By KarimIO
      Hey guys
      So I was wondering how modern terrain and water geometry works both with and without tesselation. Essentially:
      1) Is Geoclipmapping still the best CPU tesselation technique?
      2) Is Geoclipmapping still used with tesselation?
      3) Is non-tesselated water just flat? Is there any other (reasonable) ways to simulate it? Do people use Geoclipmapping for that too?
      Thanks!
  • Advertisement