Light Based Tessellation Application Note

by Jeff Andrews


1.0 Introduction

Light Based Tessellation technology is used for adding enhanced lighting effects to three-dimensional objects. Current lighting algorithms (e.g., DX* and OpenGL*) operate only on each vertex of a polygon in order to create lighting effects. By tessellating (breaking up) a polygon, more vertices will be created with which the lighting algorithms can work, thus producing better lighting effects. (Figure 1)

 Light Based Tessellation Sample
Figure 1: Light Based Tessellation Sample

Not all polygons in a scene need to be tessellated. Tessellation only applies to polygons affected by a light source. This is where the bulk of the calculations come in, since the algorithm must determine which of the polygons need to be tessellated based on whether or not they are being illuminated by the light source. Also, the algorithm needs to be performed on each individual polygon in a scene, including the newly-generated polygons from the tessellation.

This is a computationally-demanding technology that requires the power of a high-performance processor operating in the area of 1+ GHz.


2.0 Tessellation Factors

The factors to consider before tessellating a scene are:

  • Type of light affecting the polygons
  • Necessary calculations to perform on each polygon (triangle)
  • Location of the light in relation to the polygons
  • Amount of tessellation required
  • Subdivision of the polygon (actual tessellation)

 


2.1 Lights

Several types of lights are used in rendering a scene, but only two of them are effective with Light Based Tessellation. The other types either affect the entire scene or have more of a flat lighting effect and would not benefit from the additional polygons.

 Point Light Source
Figure 2: Point Light Source

The two types of acceptable lights are point lights and spotlights. Point lights are light sources that radiate equally in all directions, while spotlights emit a cone of light, so only objects within the cone are illuminated.

Spotlights are the main focus of this paper, so the formulas in the following sections deal primarily with this type of light.

However, if you want to use point light tessellation, follow these steps:

  • Use the face distance calculation (see "2.2.1 Face Distance")below to determine if the light is in front of or behind the polygon. (Figure 2)
  • Use the formula of a sphere to determine if the vertices of the triangle fall within the point light's radius. This is the point light calculation equivalent to "2.2.2 Vertex Distance" below. The formula is as follows:

     Sphere
    Equation 1: Sphere

    Where x, y, and z indicate the location of the point light, a, b, and c indicate the location of one of the triangle's vertices, and r indicates the radius of the point light.

 

Note: The point light algorithm above does not take into account a point light intersecting a triangle and not touching any of the vertices of that triangle. Therefore, based on the algorithm above, such a triangle would not be tessellated.


2.2 Distance

Several formulas are used to calculate the distance of a spotlight in relation to the triangle. The first distance is the distance from the light to the face of the triangle.


Figure 3: "Face" Plane Distance

The next distance is from the angle "distance" of the vertices to the cone of the spotlight. Finally, the third distance is that from the spotlight to the edges of the triangle.


2.2.1 Face Distance

The face distance is the distance from the origin of the light to the plane of the triangle. (Figure 3) Calculating this distance tells you whether the light is in front of or behind the polygon and how far away it is from the polygon.

The formula for calculating the distance of the light to the triangle face plane is as follows:

 Plane
Equation 2: Plane

Where A, B, and C are the x, y, and z face normal values of the triangle, x, y, and z is any point on the triangle, lx, ly, and lz is the origin of the light source, and d is the distance from the light to the face plane.

The distance calculated should be greater than or equal to zero and less than or equal to the length of the light source. It is expressed as follows:

 Face Distance Validity
Equation 3: Face Distance Validity

If d is less than zero, the light is behind the polygon. If d is greater than the light's length, the light is too far away from the polygon to require tessellation.


2.2.2 Vertex Distance

The vertex distance determines whether each of the triangle's vertices falls within the cone of the spotlight (see illustration in Figure 4). The cosine of the angle between the light's direction vector and the vector between the light's origin to each of the triangle's points needs to be calculated. This is done by getting the dot product of 1) the spotlight's norm alized direction vector, with 2) the normalized vector of the light's origin to the point. This can then be compared with the cosine of the angle of the spotlight's cone. If the value is greater than or equal to the spotlight's cosine, then the point falls within the spotlight's cone.

 Spotlight Cone
Figure 4: Spotlight Cone

The formula is as follows:

 Angle Cosine of Two Vectors
Equation 4: Angle Cosine of Two Vectors

Where VecLight is the direction vector of the light, VecL2P is the vector from the light to the point, and Ø is the angle of the spotlight's cone.

To calculate the vector between the point and the origin of the light (VecL2P), subtract the x, y, and z of the light's origin from the x, y, and z coordinates of the point. This vector then needs to be normalized before calculating the dot product.


2.2.3 Edge Distance

In the event that the vertices of a polygon do not fall within the cone of the spotlight (Figure 5), further processing can determine whether the light source still affects the polygon via edge distance calculations. The edge distance is the distance of the center of the circle created by the intersection of the spotlight's cone and the triangle's plane in relation to the three edges of the triangle.

The edge distance calculations may or may not be necessary depending upon the implementation chosen. If enough polygons are in an object for a lighting algorithm to create some lighting effects, the vertex distance calculation is all that is necessary. However, if there aren't enough polygons (e.g., a large floor made up of only two polygons), making the likelihood of the light striking a vertex very low, edge distance calculations are necessary.

Edge distance calculation is composed of several combined calculations. The following points must be calculated:

  • Intersection point of the spotlight and the face plane.
  • Distance from the intersection point to the triangle's edge planes.
  • Radius of the circle (or ellipse) made at the intersection point of the spotlight cone and the face plane and the distance to the edge lines.

 

 Situations Requiring Edge Distance Calculation
Figure 5: Situations Requiring Edge Distance Calculation


2.2.3.1 Intersection Point

The formula for calculating the intersection point of the center of the spotlight with the plane of the triangle's face is as follows:

 Intersection of a Vector and a Plane
E quation 5: Intersection of a Vector and a Plane

Where P is the origin of the light, A is any point on the plane, V is the vector of the light, and N is the normal of the plane.


2.2.3.2 Distance to Edge Planes

Now that the intersection point has been calculated, you can calculate the distances to each of the triangle's edge planes. An edge plane is the plane on a triangle's edge that is perpendicular to the triangle's face plane. The formula "Equation 2: Plane" calculates this distance, except A, B, and C of the formula are the x, y, and z values, respectively, of the edge normal. This is calculated for each edge of the triangle.

If the distance d is less than or equal to zero for all edges, the spotlight is inside the triangle and can now be tessellated. The formulas in "2.2.3.3 Radius and Distance to Edge" are no longer necessary for this triangle.


2.2.3.3 Radius and Distance to Edge

 Point to Line Distance
Figure 6: Point to Line Distance

The final calculation determines whether the ellipse created by the intersection of the spotlight and plane intersects any of the edges of the triangle. (Figure 6)

To simplify the calculation, assume that a circle is created by the intersection of the spotlight and the plane. To further enhance the accuracy of the overall algorithm, the equation of an ellipse can be used.

The radius of the circle created at the point of intersection now must be calculated using the following formula:

 Radius of a Cone at a Given Point
Equation 6: Radius of a Cone at a Given Point

Where Pt is the intersection point calculated in Equation 5, P is the origin of the light, and Ø is the angle of the spotlight's cone.

The distance of the point to the triangle's edges can be calculated using the formula for the distance of a point to a line. The formula is as follows:

 Distance of a Point to a Line Segment

Equation 7: Distance of a Point to a Line Segment

Where A and B are two end points of an edge, d1 is the distance of the point to the edge plane, and d2 is the distance of the point to the line.

If the distance to the edge is less than or equal to the radius calculated in Equation 6, the intersection circle intersects the edge.

 


2.3 Size

Aside from calculating the distance, Light Based Tessellation must also determine if the triangle is the appropriate size. The size check calculation can be accomplis hed in two ways:

  • Verify that the perimeter is above a certain threshold, using the following formula to calculate the perimeter:

     Perimeter of a Triangle
    Equation 8: Perimeter of a Triangle

    Where d1, d2 and d3, are the lengths of each of the edges.
  • Verify that the area is above a certain threshold, using the following formula to calculate the area:

     Area of a Triangle
    Equation 9: Area of a Triangle

    Where d1, d2, and d3 are the lengths of each of the edges.

 

Note: This is the actual size of the triangle in coordinate units and not the size as seen on screen. To calculate the triangle's perceived view, the coordinates for each of the triangle's points must first be transformed into the projection matrix of the viewing camera.


2.4 Polygon Tessellation

The final stage in the algorithm is to perform the actual tessellation on the triangle. The quickest way to break up the triangle and still produce visually appealing results is to divide it into four equal parts. (Figure 7)

 Tessellated Triangle
Figure 7: Tessellated Triangle

The method for dividing a triangle is to place new vertices half the distances of each of the edges. The new points are calculated as follows:

 Triangle Tessellation
Equation 10: Triangle Tessellation

The new triangles must then be checked to determine if their size, vertex distances, and edge distances are within the appropriate levels.


3.0 Conclusion

Light Based Tessellation can drastically decrease the number of polygons that need to be transmitted over the Internet. Objects that intentionally have a large number of polygons for spotlight algorithms to create correct lighting effects can now be trimmed. For example, a floor that is lit by a spotlight can now be reduced to two triangles from an initial 1000+ triangles. This translates into smaller file sizes and faster loads.

While Light Based Tessellation is computationally demanding, it can produce dramatic lighting effects with spotlights. If low-end scalability is a concern, this technology can be enabled only upon detecting a high-performance processor.


4.0 Contributors

Hillarie Klempner, Application Engineer, Intel Corporation
Rachana Gupta, Application Engineer, Intel Corporation
Bryant Freitag, Application Engineer, Intel Corporation
Ignacio Ybarra, Application Engineer, Intel Corporation

Intel Corporation
http://www.intel.com


For more complete information about compiler optimizations, see our Optimization Notice.