Previous | Next --- Slide 61 of 70
Back to Lecture Thumbnails
BryceSummers

Here is a rewriting of the code on this slide in vector form :

// T1 and T2 are two points of the triangle in a well defined orientation 
//(clock-wise / counter-clockwise).
// test is the location of the pixel to be tested.
// = 0 : on edge.
// > 0 : one side of edge.
// < 0 : other side of edge.
float E(Vector T1, Vector T2, Point test)
{
    Vector dP = T2 - T1;// Offset vector from T1 pointing to T2.

    Vector dTest = T1 - test;// Offset vector from test pointing to T1.

    // Computes the 2D perpendicular direction.    
    Vector dP_perp = Vector(dP.y, -dP.x);


    return dTest **dot_product** dP_perp;

}

Note:

To use algorithms such as those on this slide, it is important to be consistent in the orientation of the points, in other words, do not mix your clock-wises with your counter-clockwises, choose one and stick with it.

Line Side Test Interpretation.

The code on this slide is pretty much a line side test:

// -- Internal function to a Line with 2 points: p1 and p2.
// Returns -1 on one side of the line.
// Returns 0 if the point is on the line.
// Returns 1 if the point is on the other side of the line.
float Line::line_side_test(Point c)
{
   return ((p2.x - p1.x)*(c.y - p1.y) - (p2.y - p1.y)*(c.x - p1.x));
}

A point is inside of a triangle if it is on the same side of the line side test for each of the three sides, because naturally it is impossible for a point in space to be on the exterior of all three sides.

jezimmer

Thanks Bryce, that dot product version really helped clarify things.

By clockwise and counterclockwise, are you referring to the possibility of using either

Vector(dP.y, -dP.x)

or

Vector(-dP.y, dP.x)

for dP_perp?

BryceSummers

@jezimmer By clockwise vs. counterclockwise, I am referring to any computational geometry algorithm that needs to make a consistent arbitrary decision.

Vector(dP.y, -dP.x) vs. Vector(-dP.y, dP.x) is indeed one such arbitrary decision. High School Physics teachers run into this problem when tying to explain the cross-product in the definition of physics equations.

A specific example related to this slide explicitly using the notion of clockwise vs. counter-clockwise is whether we use:

{E(a, b), E(b, c), E(c, a)}

or:

{E(c, b), E(b, a), E(a, c)}

for our calculations, which amounts to traversing the corners of the triangle in clockwise order or counter-clockwise order.

The calculation for many algorithms such as these will be equal, but negative. This is only a problem with regards to the internal consistency of all of the procedures in your program. If you are using a standard library such as openGL, you will need to play by the orientation rules set forth therein, but if you are programming a project by itself you can come up with your own internal consistency rules.

A neat trick is that often the specific orientation of an object does not matter. In situations such as calculating the area of triangles, you can just take the absolute value of the resulting calculation to ensure correctness under any orientation. For line side tests, we often do not care that a given point is on a particular side of a line, but rather that it is on the same or different side as another point. This is useful for line segment intersection tests.

Here is a blog post that I wrote detailing many of the algorithms I have mentioned in this post.