🎉 Celebrating 25 Years of GameDev.net! 🎉

Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!

Split quad into triangles

Started by
6 comments, last by JoeJ 1 year, 6 months ago

Some old models have suport for quads, while today quads are not really much suported so the solution is to split every quad into triangles. The problem for a quad [1, 2, 3, 4] there are 2 posibilities [1, 2, 3] and [3, 4, 1] or [2, 3, 4] and [4, 1, 2]. If all vertex of the quad have exactly the same normal this play no role, but if not the resul after rendering could be diferent. So what is the best solution to split the quad and keep the result after rendering the same?

Advertisement

convert said:
So what is the best solution to split the quad and keep the result after rendering the same?

A good and standard solution is to apply the rules from ‘Delaunay Triangulation’, which tries to maximize angles, and mostly picks the shorter new edge.

Example code (vPos is an array of the 4 vertices in clockwise or counterclockwise order):


				float dot0 = vec(vPos[3]-vPos[2]).Unit().Dot(vec(vPos[1]-vPos[2]).Unit());
				float dot1 = vec(vPos[3]-vPos[0]).Unit().Dot(vec(vPos[1]-vPos[0]).Unit());
				float angle0 = acos(max(-1, min(1, dot0))) + acos(max(-1, min(1, dot1)));


				dot0 = vec(vPos[0]-vPos[3]).Unit().Dot(vec(vPos[2]-vPos[3]).Unit());
				dot1 = vec(vPos[0]-vPos[1]).Unit().Dot(vec(vPos[2]-vPos[1]).Unit());
				float angle1 = acos(max(-1, min(1, dot0))) + acos(max(-1, min(1, dot1)));


				bool choice = angle0 < angle1;

				if (choice)
				{
					// triangle 1: vPos[2], vPos[3], vPos[1]
					// triangle 2: vPos[1], vPos[3], vPos[0]
				}
				else
				{
					// triangle 1: vPos[1], vPos[2], vPos[0]
					// triangle 2: vPos[0], vPos[2], vPos[3] 

				}

While this is often considered optimal, there are cases where it is not. The problem is that the method ignores curvature as given from the neighborhood of the quad. So the new edge may be a bad fit to represent the shape of the model, and Delaunay is only optimal on a flat plane (2D).

So i use a second method: Calculate primary curvature directions using the vertex normals (not trivial). Then select the new edge which is closer to this direction.
But this method has the problem that it ignores angles, and so we might again get triangles with a very small angle. Such sliver triangles are always bad for rendering, simulations, geometry processing, and just anything.

To make a decision, i calculate Delaunay first, and if it prevents a case of a small angle threshold, i stick at it. Otherwise i use the curvature method (which i could elaborate in more detail if you want.)

There surely is no single, provably optimal answer to your question. Which feels a bit surprising considering the problem seems simple.

Is your main concern to make it look good, to make it look consistent, or to make it look the same as the original?

If it's to look good, do what JoeJ said.

If it's to look consistent, then just pick an order and stick with it.

If it's to look the same as the original, then do whatever the original hardware or device driver did. Which is probably [1, 2, 3], [3, 4, 1]. Using a more complicated method is a bad idea in realtime, not (just) because of the computational expense, but because it leads to popping when the mesh is animated.

There surely is no single, provably optimal answer to your question. Which feels a bit surprising considering the problem seems simple.

Seems not simple to me. Would not ask if it was simple. Since new hardware seems to not suport quads animore, thought there must be a solution to render old models which used quads.

If it's to look the same as the original, then do whatever the original hardware or device driver did.

In original would just use GL_QUADS, but what it does internaly have no idea.

convert said:
In original would just use GL_QUADS, but what it does internaly have no idea.

There never was HW support of quads, even for perfectly planar quads.
I'm sure the triangulation was just this:

a light breeze said:
If it's to look the same as the original, then do whatever the original hardware or device driver did. Which is probably [1, 2, 3], [3, 4, 1].

Actually you can make a test model with non planar quad to find out which order from two possibilities is used.
But it may have varied across drivers and hardware, in case the order was never specified. (Did not find such specs from a very quick search at least.)

Oh, had still a tab open with some info: https://www.khronos.org/opengl/wiki/Primitive

A quad is a 4 vertex quadrilateral primitive. The four vertices are expected to be coplanar; failure to do so can lead to undefined results.

A quad is typically rasterized as a pair of triangles. This is not defined by the GL spec, but it is allowed by it. This can lead to some artifacts due to how vertex/geometry shader outputs are interpolated over the 2 generated triangles.

  • GL_QUADS: Vertices 0-3 form a quad, vertices 4-7 form another, and so on. The vertex stream must be a number of vertices divisible by 4 to work.
  • GL_QUAD_STRIP: Similar to triangle strips, a quad strip uses adjacent edges to form the next quad. In the case of quads, the third and fourth vertices of one quad are used as the edge of the next quad. So vertices 0-3 are a quad, 2-5 are a quad, and so on. A vertex stream of n length will generate (n - 2) / 2 quads. As with triangle strips, the winding order of quads is changed for every other quad.

So the triangle order was not specified.
And it was assumed to be planar, so order does not matter anyway.

But then i guess the correct behavior also expects the UVs would cause no distortion (practically impossible if charts span multiple quads), or there was quadrilateral texture mapping, as shown here:

https://www.reedbeta.com/blog/quadrilateral-interpolation-part-1/

Though, such things may have been on SGI workstations, surely not on PC GPUs.

This topic is closed to new replies.

Advertisement