cancel
Showing results for 
Search instead for 
Did you mean: 

Archives Discussions

stephan
Adept I

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

0 Likes
1 Solution
stephan
Adept I

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...​.

View solution in original post

0 Likes
5 Replies
jtrudeau
Staff

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

0 Likes
particlepeter
Adept II

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?

0 Likes

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. 

0 Likes
stephan
Adept I

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...​.

0 Likes