cancel
Showing results for
Did you mean:

# Archives Discussions

## OpenGL tessellation: equation for coordinates of new triangles inside original triangle

Dear AMD developers,

are you allowed to share the equation which computes the uvw coordinates of a tessellation-result-triangle of the outer triangle coordinates? I am implementing OpenGL's inner tessellation in C++ on CPU to emulate GPU tessellation because I need to process the result on CPU not as an image on GPU. For that I would like to compare my point finding with the original equation.

Thank you and with best regards,

Stephan

1 Solution

By simplifying the triangle in question it is possible to discard the 3rd dimension and to reduce the system of linear equations to one linear equation:

Point IntersectionFinder::intersectionPoint( const int tesslevel ) const

{

// given equilateral triangle with:

//      A in origin

//      length AB = 1

//      z coordinate == 0

//      AB == 1 --> B = (1;0)

//

// equilateral: C.x = 0.5 * AB and C.y = AB * sin(60deg) --> ( 0.5; sin(60) )

//

// observation: iff triangle is equilateral

//              all intersections for tessellation meet on ray

//              from A through midpoint BC

//              because perpendicular rays which meet in intersection points

//              always have the same length

//

// mid( BC ).x = 0.5 * AB + 0.5 BC

// mid( BC ).y = 0.5 * sin(60) --> ( 0.75; 0.5 * sin60 )

// slope( A, mid( BC ) 😞 due to A being in origin slope m = mid(BC).y / mid(BC).x

// --> 0.5 * sin60 / 0.75 == 1/2 * sin( 60deg ) / 3/4

// --> m = 1/2 * 4/3 * sin( 60deg );

const Scalar m = ( 1.0 / 2.0 ) * ( 4.0 / 3.0 ) * sin( 60.0 * DEG2RAD );

// calculate tessellation intersection point i depending on tessLevel t

// i.x = AB / t with AB = 1 --> i.x(t) = 1 / t

// i.y = i.x * slope --> i.y = m * 1 / t

// i.y(t) = m/t;

double x = 1.0 / static_cast<double>( tesslevel );

double y = m / static_cast<double>( tesslevel );

double z = 0.0;

return Point( x, y, z );

}

The calculated intersection point is only valid in the given equilateral triangle. Now this point needs to be converted from cartesian coordinates to triangle independent barycentric coordinates. Equations for that are here: http://gamedev.stackexchange.com/questions/23743/whats-the-most-efficient-way-to-find-barycentric-co...​.

5 Replies
Staff

I have added you to our white list, welcome to the community. Moved this into the OpenGL Forum.

You could transform feedback. Run a geometry shader after the tesselation shader, record the generated vertices in a separate vbo and read the data back to CPU memory.

ParticlePeter

Thank you for your suggestion. This would return the list of tessellated triangles.

However I am using a halfedge datastructure to do distance computation on the tessellated result. That datastructure cannot be generated out of a list of loose triangles. Therefore I am computing all tessellated points and incrementally fill up the halfedge list.

Because all GPU vendors have to produce the same tessellation output I thought the equation for the first tessellation point as marked on my attached image is not a secret. Can you share it?

I did some research on OpenGL forums and found a useful hint in    https://www.opengl.org/registry/specs/ARB/tessellation_shader.txt

It says:

 [..] Otherwise, for each corner of the outer    triangle, an inner triangle corner is produced at the intersection of two    lines extended perpendicular to the corner's two adjacent edges running    through the vertex of the subdivided outer edge nearest that corner. [..]

How about non-equlateral triangles? Well, I wasn't the first to ask: https://www.opengl.org/discussion_boards/showthread.php/171470-Triangle-tessellation-in-GL_ARB_tesse...

 [..] It really only needs to be done for one triangle, the one with vertices (1, 0, 0), (0, 1, 0), (0, 0, 1). Which is an equilateral triangle where the algorithm works correctly. The resulting vertices can be used as barycentric coordinates for any triangle. So basically, for each tessellation-level parameters, the tessellation only needs to be done once, and the resulting data can be used for any other triangle. [..]

This is not yet the final mathematical equation but a bit of linear algebra will help: build two perpendicular vectors and let them intersect, store uvw coordinates for reuse with any triangle later.

By simplifying the triangle in question it is possible to discard the 3rd dimension and to reduce the system of linear equations to one linear equation:

Point IntersectionFinder::intersectionPoint( const int tesslevel ) const

{

// given equilateral triangle with:

//      A in origin

//      length AB = 1

//      z coordinate == 0

//      AB == 1 --> B = (1;0)

//

// equilateral: C.x = 0.5 * AB and C.y = AB * sin(60deg) --> ( 0.5; sin(60) )

//

// observation: iff triangle is equilateral

//              all intersections for tessellation meet on ray

//              from A through midpoint BC

//              because perpendicular rays which meet in intersection points

//              always have the same length

//

// mid( BC ).x = 0.5 * AB + 0.5 BC

// mid( BC ).y = 0.5 * sin(60) --> ( 0.75; 0.5 * sin60 )

// slope( A, mid( BC ) 😞 due to A being in origin slope m = mid(BC).y / mid(BC).x

// --> 0.5 * sin60 / 0.75 == 1/2 * sin( 60deg ) / 3/4

// --> m = 1/2 * 4/3 * sin( 60deg );

const Scalar m = ( 1.0 / 2.0 ) * ( 4.0 / 3.0 ) * sin( 60.0 * DEG2RAD );

// calculate tessellation intersection point i depending on tessLevel t

// i.x = AB / t with AB = 1 --> i.x(t) = 1 / t

// i.y = i.x * slope --> i.y = m * 1 / t

// i.y(t) = m/t;

double x = 1.0 / static_cast<double>( tesslevel );

double y = m / static_cast<double>( tesslevel );

double z = 0.0;

return Point( x, y, z );

}

The calculated intersection point is only valid in the given equilateral triangle. Now this point needs to be converted from cartesian coordinates to triangle independent barycentric coordinates. Equations for that are here: http://gamedev.stackexchange.com/questions/23743/whats-the-most-efficient-way-to-find-barycentric-co...​.