CODEWITHSUNDEEP
calgorithmgeometrytriangulation
krb
krb

Reputation: 16315

Fastest way of converting a quad to a triangle strip?

What is the fastest way of converting a quadrilateral (made up of four x,y points) to a triangle strip? I'm well aware of the general triangulation algorithms that exist, but I need a short, well optimized algorithm that deals with quadrilaterals only.

My current algorithm does this, which works for most quads but still gets the points mixed up for some:

#define fp(f) bounds.p##f

/* Sort four points in ascending order by their Y values */
point_sort4_y(&fp(1), &fp(2), &fp(3), &fp(4));

/* Bottom two */
if (fminf(-fp(1).x, -fp(2).x) == -fp(2).x)
{
    out_quad.p1 = fp(2);
    out_quad.p2 = fp(1);
}
else
{
    out_quad.p1 = fp(1);
    out_quad.p2 = fp(2);
}

/* Top two */
if (fminf(-fp(3).x, -fp(4).x) == -fp(3).x)
{
    out_quad.p3 = fp(3);
    out_quad.p4 = fp(4);
}
else
{
    out_quad.p3 = fp(4);
    out_quad.p4 = fp(3);
}

Edit: I'm asking about converting a single quad to a single triangle strip that should consist of four points.

Upvotes: 1

Views: 4418

Answers (2)

Paul Michalik
Paul Michalik

Reputation: 4381

  1. Locate an extremum point of the quad w.r.t a coordinate. Let it be p, where p is an iterator on a cyclic container
  2. Check if p + 2 lies inside of the ear formed by {p - 1, p, p + 1}. If yes, seek extremum w.r.t. other coordinate (or switch from min to max or vice versa) and repeat step 1.
  3. Split the quad into two triangles by cutting off the "ear" around the extremum point: t0 = { p - 1, p, p + 1} and t1 = { p + 1, p + 2, p - 1 }

No need to sort, just locate the extremum. If your quads are guaranteed to be convex (real quadrilaterals) then skip the extremum search and choose arbitrary p.

Edit: Modified according to suggestion from the comment. Also the formulation suggested by the commenter is simpler to implement:

  1. Given a quad A, B, C, D form the diagonals AC and BD
  2. If points B and D lie on different sides of AC then AC can be used to split the quad
  3. Apply the same reasoning to BD and points A and C

Upvotes: 3

Dude
Dude

Reputation: 583

Given a quad A B C D we can split it into A B C, A C D or A B D, D B C.

Compare the length of A-C and B-D and use the shorter for the splitting edge. In other words use A B C, A C D if A-C is shorter and A B D, D B C otherwise.

Upvotes: 2

Related Questions