Browse Prior Art Database

Triangle Orientation Determination

IP.com Disclosure Number: IPCOM000114803D
Original Publication Date: 1995-Feb-01
Included in the Prior Art Database: 2005-Mar-29
Document File: 4 page(s) / 79K

Publishing Venue

IBM

Related People

Narayanaswami, C: AUTHOR

Abstract

It is often necessary to determine whether the edges of a triangle are specified in a clockwise or a counter clockwise manner. Examples include cases in graphics where triangles pointing away from the viewer can be discarded from the expensive process of lighting, texturing, and rasterization.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 53% of the total text.

Triangle Orientation Determination

      It is often necessary to determine whether the edges of a
triangle are specified in a clockwise or a counter clockwise manner.
Examples include cases in graphics where triangles pointing away from
the viewer can be discarded from the expensive process of lighting,
texturing, and rasterization.

      Given the three vertices of the triangle V0, V1, and V2 in a
plane (ij) the orientation can be easily determined by computing the
cross product P=V0V1 X V0V2.  In fact examining the z th component Pz
of the cross product is sufficient.  If Pz > 0 the orientation is
counterclockwise and if Pz < 0 the orientation is clockwise.

      The above requires that V0x X V1y - V1x X V0y be computed.
This requires two multiplications.  Often, hardware multipliers are
expensive and it is preferable to utilize the line drawing hardware
already present in the rasterizer.

      METHOD - The new method uses comparators and the line
generating hardware for determining the orientation of a given
triangle.

      The three vertices of the triangle are first sorted by the y
coordinate.  After sorting the vertex with minimum y is labeled Q0,
the one with maximum y is labeled Q1 and the remaining one is labeled
Q2.  The Figure shows an example.  In case of ties for minimum y
coordinates the vertex with the lesser x coordinate is labeled as Q0.
In case of ties for maximum y coordinates the vertex with the greater
x coordinate is labeled as Q1.
  The pseudo code for the algorithm is
    orient_flag = 1;
    if (V0.y > V1.y) {
       swap(V0, V1);  /* swap vertices */
       orient_flag *= -1;
    }
    if (V0.y > V2.y) {
       swap(V0, V2);   /* swap vertices */
       orient_flag *= -1;
    }
    if (V0.y > V2.y) {
       swap(V0, V2);   /* swap vertices */
       orient_flag *= -1;
    }
    Q0 = V0;
    Q1 = V1;
    Q2 = V2;

      The relative orientation of V0V1V2 and Q0Q1Q2 is maintained by
an orientation flag which is reversed each time two...