Part of the Khronos Group
OpenGL.org

The Industry's Foundation for High Performance Graphics

from games to virtual reality, mobile phones to supercomputers

Page 1 of 2 12 LastLast
Results 1 to 10 of 19

Thread: Tesselate triangle

  1. #1
    Junior Member Regular Contributor
    Join Date
    Dec 2010
    Location
    Oakville, ON, CA
    Posts
    165

    Tesselate triangle

    Hi!
    Say, I want to increase detalization of a mesh to make a model smoother.

    I want to do this by a simple iterative approach: if a certain edge with vertices Va and Vb and normals Na and Nb has an angle between those normals higher than X degrees, I break that edge on two by inserting an extra vertex Vm. It is required that normal Nm at this vertex is equal: Nm=normalize(Na+Nb). So how do I determine the coordinates of that extra vertex Vm?

    Should be a trivial task, but I had a hard time searching for a solution...

  2. #2
    Senior Member OpenGL Guru
    Join Date
    Jun 2013
    Posts
    2,526
    Quote Originally Posted by Yandersen View Post
    So how do I determine the coordinates of that extra vertex Vm?
    However you like.

    One option is to take the midpoint of the edge of a PN triangle, which would be

    Vm = (Va+Vb)/2 - (Wa*Na + Wb*Nb)/8

    where

    Wa = (Vb - Va) . Na
    Wb = (Va - Vb) . Nb

  3. #3
    Junior Member Regular Contributor
    Join Date
    Dec 2010
    Location
    Oakville, ON, CA
    Posts
    165
    Oh, thank you, GClements, it works!
    Care to explain why the displacement divided specifically by 8?

  4. #4
    Junior Member Regular Contributor
    Join Date
    Dec 2010
    Location
    Oakville, ON, CA
    Posts
    165
    Whoops, I just realized I have incorrectly specified the problem. We can't say that the normal Nm in the middle point Vm will be the average between normals Na and Nb. Attachment is an example were both normals are pointing the same direction but the Nm shall be perpendicular to them at Vm.
    I am getting lost here... I thought I could just divide edge few times and get a smooth curvature as a result. Any suggestions how to do that correctly?
    Attached Thumbnails Attached Thumbnails Click image for larger version. 

Name:	Tessellation.jpg 
Views:	175 
Size:	21.7 KB 
ID:	2142  

  5. #5
    Member Regular Contributor
    Join Date
    Apr 2012
    Location
    Los Angeles
    Posts
    388
    Your title is "Tesselate triangle". But the figure you included is not a triangle.

  6. #6
    Junior Member Regular Contributor
    Join Date
    Dec 2010
    Location
    Oakville, ON, CA
    Posts
    165
    It is an edge of the triangle. I tessellate the triangle by subdividing it's edge.

  7. #7
    Senior Member OpenGL Guru
    Join Date
    Jun 2013
    Posts
    2,526
    Quote Originally Posted by Yandersen View Post
    Care to explain why the displacement divided specifically by 8?
    A PN (point-normal) triangle is a cubic Bezier triangle whose control points are derived from 3 vertices and their associated normals.

    A more detailed description can be found e.g. here, but a brief summary follows.

    The control points are given by
    Code :
    b300 = P0
    b030 = P1
    b003 = P2
    b210 = (2*P0 + P1 - w01*N0)/3
    b120 = (2*P1 + P0 - w10*N1)/3
    b021 = (2*P1 + P2 - w12*N1)/3
    b012 = (2*P2 + P1 - w21*N2)/3
    b102 = (2*P2 + P0 - w20*N2)/3
    b201 = (2*P0 + P2 - w02*N0)/3
    b111 = (b210 + b120 + b021 + b012 + b102 + b201)/4 - (b300 + b030 + b003)/6
    where P0, P1, P2 are the vertices, N0, N1, N2 are the normals, and wij=dot(Pj-Pi, Ni)

    Each of the 6 edge control points is generated by interpolating the edge in a 2:1 ratio then projecting onto the tangent plane defined by the closest vertex and its associated normal. This ensures that the normals are actually normal to the surface at the vertex. The interior control point b111 is calculated as E+(E-V)/2 where E is the mean of the 6 edge control points and V is the mean of the 3 vertices.

    Given the control points and barycentric coordinates (a,b,c), the corresponding point in the surface is calculated by:
    Code :
    P = b300 * c^3
      + b030 * a^3
      + b003 * b^3
      + b210 * 3 * a * c^2
      + b120 * 3 * c * a^2
      + b201 * 3 * b * c^2
      + b021 * 3 * b * a^2
      + b102 * 3 * c * b^2
      + b012 * 3 * a * b^2
      + b111 * 6 * a * b * c

    So the midpoint of the edge between P1 and P2 is found by evaluating the above with a=1/2, b=1/2, c=0.

    Tangents can be found by substituting c=1-a-b into the above and differentiating with respect to a and b; their cross product gives the surface normal at any point. The expression for each tangent is quadratic, so that for the normal is quartic. But the normal is more commonly approximated by a quadratic Bezier triangle with control points
    Code :
    n200 = N0
    n020 = N1
    n002 = N2
    n110 = N0+N1-v01*(P1-P0)
    n011 = N1+N2-v12*(P2-P1)
    n101 = N2+N0-v20*(P0-P2)
    where vij = 2*dot(Pj-Pi, Ni+Nj)/dot(Pj-Pi, Pj-Pi)

    For given barycentric coordinates, the normal is calculated by:
    Code :
    N = n200 * c^2
      + n020 * a^2
      + n002 * b^2
      + n110 * c * a
      + n011 * a * b
      + n101 * c * b

    Note that cubic Bezier triangles typically don't have C1 continuity across edges. To achieve that, you would need a quintic surface (21 control points), which is significantly more expensive both to determine and evaluate.

    Most of the commonly-used subdivision surfaces which do enforce C1 continuity across edges (e.g. Catmull-Clark, Loop) only approximate the initial vertices (i.e. each subdivision step moves the original vertices as well as creating additional vertices).

  8. #8
    Junior Member Regular Contributor
    Join Date
    Dec 2010
    Location
    Oakville, ON, CA
    Posts
    165
    Wow, wow, GClements, you always shoot so much theoretic material for my simple mind that I start feel myself like a black guy in a science lab...
    I've seen this triangle subdivision with extra 7 points and decided that it is pretty overkill for me. I would like to go with one edge with two corner points subdividing it with 1 extra vertex, and that is it.

    So here is what I came up with. We deal with a curve: it starts at one point and exit through another. At both points we know the normals to that curve. So first let's find a tangent vectors (Ta, Tb) directing the curve at each of those two corner points (Va, Vb). To do this we project the vector VaVb onto planes perpendicular to our normals (Na, Nb):
    Ta = VaVb - Na * dot(VaVb, Na);
    Tb = VbVa - Nb * dot(VbVa, Nb);
    Now let's add a weight coefficients (wa, wb=1-wa) that show how close a certain point on the curve to a corner point: for a point close to Va the wa will be close to 1 and wb is close to 0, and vice-versa. To make the smooth transition we do a "double" blending: if we close to Va, than we want the curve to follow the direction of Ta and the position should be close to Va, and the same with a proximity with Vb. So here is a blending formula I came up with:

    Vm = wa*(Va+(1-wa)*Ta) + wb*(Vb+(1-wb)*Tb);

    If we simplify this for wa=0.5, we get:

    Vm = (Va+Vb)/2 - (dot(Na,(Vb-Va))*Na + dot(Nb,(Va-Vb))*Nb)/4

    Which is the same as the formula at the second post except that the subtracted part is divided by 4, not 8. Shit...

  9. #9
    Junior Member Regular Contributor
    Join Date
    Dec 2010
    Location
    Oakville, ON, CA
    Posts
    165
    I think I found the solution here. As I understood from the video, the "tension line" is tangent to the curve, and the coordinates of the desired point Vm is a center of that line at 50% "completion". Therefore I came up with this GLSL-style C++ algorithm:

    Code :
    #include "GLSL.hpp"  //GLSL vectors, matrices, operators and functions
     
    //Function breaks an edge onto two by inserting an extra point inbetween the
    //specified corner points
    void TessellateEdge(const vec3& Va, const vec3& Na,
                        const vec3& Vb, const vec3& Nb,
                        vec3* Vm, vec3* Nm){
     //Calculate tangents
     vec3 Ta = Vb-Va-Na*dot((Vb-Va),Na),
          Tb = Va-Vb-Nb*dot((Va-Vb),Nb),
          Tm = 0.5*(Vb-Va)+0.25*(Tb-Ta);
     //Calculate coordinates of the middle point
     *Vm = 0.5*(Va+Vb) + 0.375*(Ta+Tb);
     //Calculate normal at the middle point
     vec3 perp = cross((Vb-Va),(Na+Nb));
     *Nm = normalize(cross(perp,Tm));
    }

    I double-checked all the formulas, run this in few setups and concluded that it provides the desired result...
    Attached Files Attached Files
    Last edited by Yandersen; 10-08-2015 at 01:57 AM.

  10. #10
    Senior Member OpenGL Guru
    Join Date
    Jun 2013
    Posts
    2,526
    Quote Originally Posted by Yandersen View Post
    Which is the same as the formula at the second post except that the subtracted part is divided by 4, not 8
    One way to look at it:
    Wa*Na is the vector from Vb to the closest point on the tangent plane passing through Va with normal Na. Halving that (Wa*Na/2) gives the vector from the midpoint of the edge to that tangent plane.

    Similarly, Wb*Nb is the vector from Va to the closest point on the tangent plane passing through Vb with normal Nb. Halving that (Wb*Nb/2) gives the vector from the midpoint of the edge to that tangent plane.

    The average of those two is (Wa*Na+Wb*Nb)/4. If we offset the midpoint of the edge, (Va+Vb)/2, by this vector, we get a third point Vc. The points Va, Vc and Vb form a triangle. One edge is the base, the other edges are approximately tangential to the surface at the corresponding endpoint.

    If these three points were the control points of a quadratic Bezier curve, the curve would be a parabola which would bisect the line between (Va+Vb)/2 and Vc exactly in half.

    To see why this might be the case, consider the curve y=1-x^2. This has roots at x=-1 and x=1 and a maximum of y=1 at x=0. The derivative dy/dx=-2*x which is 2 at x=-1 and -2 at x=1. Thus tangents at the roots intersect at x=0, y=2 to give the interior control point. This gives a control polygon with the vertices (-1,0), (0,2), (1,0) while the curve itself passes through (-1,0), (1,0), (0,0).

    Thus to find the midpoint of the curve, we halve the offset vector, which gives us a denominator of 8.

    So we halve once because we want the offset of the midpoint rather than the endpoint, once when calculating the average of two midpoints, and once due to the fact that the height of the peak of a parabola is half the height at which its tangents intersect.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •