CS3451, Summer 2006, Project 5
Silhouette and Important Edges
Catherine Herrington, Email: catherine@polter.net
Submitted July 20, 2006. Source code: Silhouette, p3d, camera
Built with Processing
Data files: mesh.vts, bunny.vts, horse.vts.

Instructions on Usage

Important Edges
'I' - toggles showing only the important edges
'UP' - increases the percentage of important edges to show
'DOWN' - decreases the percentage of important edges to show

Silhouette Edges
's' - toggles showing the silhouette edges in magenta (all other edges shown black)
'v' - toggles whether to ignore hidden silhouette edges
'f' - toggles showing the filled triangles or only edges (useful for seeing hidden edges)

Camera Keys
'z' - zooms image in and out
'O' - returns view to approximately the original setting

Project Description

The objective of this project is to draw an image using only its most important edges. The importance of an edge is determined on whether it is a visible silhouette edges based on a certain viewpoint. If multiple viewpoints are used and a certain edge is often seen as a visible silhouette edge (more so than other edges), then that edge is more important than the other edges. By randomly placing many cameras around the image and keeping track of the importance of each edge, the image can then be drawn using only its most important edges.

Implementation

The main procedures that were added were computeImportantEdges(), drawAllEdges(), drawImportantEdges(), silhouetteEdge(pt pViewPoint, int corner), rayHitTri(pt pViewPoint, pt pMidEdge, pt A, pt B, pt C), and rayDistToTriPt (pt pViewPoint, pt pMidEdge, pt A, pt B, pt C). An array of integers, Edge[], was also added to store the importance of each edge.

void computeImportantEdges()
The procedure computeImportantEdges() is called when a mesh is loaded. This procedures randomly places 200 cameras (along a sphere) and stores the importance of each edge. The importance or weight of each edge is stored in the Edge[] array. This procedures starts by setting the weight of each edge to 0 and counting the total number of edges in the image. The total number of edges is used to determine the number of edges to show based on the specified percentage of important edges to show.
The 200 cameras are randomly placed using the "bread crust" method:

pt pViewPt = new pt(0,0,0);
float fRadius = 2*Rbox;
for(int iView=0; iView < iNumViews; iView++)
{
//Create random camera location to determine silhouette edges
float fLong = random(-fRadius, fRadius);
float Psi = random(0,2*PI);
pViewPt.x = Cbox.x + fRadius*(cos(fLong)*sin(Psi));
pViewPt.y = Cbox.y + fRadius*(sin(fLong)*sin(Psi));
pViewPt.z = Cbox.z + fRadius*(cos(Psi));

//Determine if silhouette edge
...

}

Once a view point is created, the silhouetteEdge() procedure is called for each edge to determine if that edge is a visible silhouette based on the view point. If the edge is a visible silhouette, then the weight for that edge is increased.

boolean silhouetteEdge(pt pViewPoint, int corner)
The procedure silhouetteEdge is called to determine if the specified edge (determined by the corner and its opposite corner) is a visible silhouette based on the specified view point. An edge is silhouette if its joining triangles have opposite orientations. So, if the triangle containing the specified corner has a clockwise orientation from the view point and the triangle containing the opposite corner has a counter-clockwise orientation from the view point, then the edge is silhouette.

boolean bcCW, boCW;
int o = o(c); //opposite of corner c
bcCW = pViewPoint.cw(G[V[c]], G[V[n(c)]], G[V[p(c)]]);
// Determines if the triangle containing corner c is
// clockwise from the perspective of the ViewPoint
boCW = pViewPoint.cw(G[V[o]], G[V[n(o)]], G[V[p(o)]]);
// Determines if the triangle containing corner o is
// clockwise from the perspective of the ViewPoint
if(bcCW == boCW){return false;} //if the orientations are the same, then it is not a silhouette edge

Once an edge is determined to be a silhouette, it is then necessary to check if the edge is visible. This is accomplished by seeing if a ray from the view point to the middle of the edge hits any triangles using the rayHitTri procedure. If a front facing (counter-clockwise) triangle was hit, then we determine if the point hit on the triangle is closer to the view point than the edge's midpoint using rayDistToTriPt. If the point hit on the triangle is closer than the edge's midpoint, then the edge is behind the triangle and is assumed to be not visable.

int rayHitTri(pt pViewPoint, pt pMidEdge, pt A, pt B, pt C)
A triangle is assumed to be hit if all the triangles forming the tetrahedron (A,B,C,pMidEdge) have the same orientation. This version of rayHitTri differs from previous versions in that it returns 0 if the triangle was not hit, returns 1 if the orientation is clockwise, and -1 if the orientation is counter-clockwise.

float rayDistToTriPt(pt E, pt P, pt A, pt B, pt C)
This procedure determines the distance from the view point E to the location hit H on the triangle (A,B,C) by the ray EP from the view point E to the middle of the edge P.

//Determines distance from P to H
float fDistPH = mixed(AB,AC,EA) / mixed(AB,AC,EP);

//Determines location of point H
H.addScaledVec(fDistPH,EP);

//Determines vector from E to H
EH = E.vecTo(H);

//Determines distance from E to H
return EH.norm();

void drawAllEdges()
This procedure will draw the edges of the triangle mesh. If it is specified to draw only the important edges, then drawImportantEdges() is called; otherwise, each edge is drawn in black (found by going through each corner, but not its opposite). If it is specified to highlight the silhouette edges, then silhouetteEdge is called using the current corner and the view point of camera 2. If the edge is a visible silhouette, then it is shown in magenta instead of black.

void drawImportantEdges()
This procedure draws only the important edges. The total number of edges and the percentage specified by the user determines the number of edges to display. A count is kept of the number of edges shown. If more edges need to be displayed, then each edge is checked to see if the weight is a certain value (edges with the highest weight are drawn first). If more edges need to be drawn, then the needed weight is reduced and the edges are searched again.

Shaded vs. Important Edges

I tried experimenting with a few different number of cameras. For the images below, I used 200 cameras. I tried reducing the number of cameras to 100, but it seemed to cause some variability in the images that was produced. Sometimes, I could make out the bunny at 10% of the edges shown...other times I could not. I tried increasing the number of cameras, but it took too long to determine the weight of each edge. When I was first using the bread-crust strategy, I saved the camera points and drew them. 200 cameras seemed like a good coverage of the sphere. For displaying simple triangle meshes (images with a small number of edges), such as the torus, it is necessary to display a rather large percentage to determine the shape. A box shape is first discovered at 15% and the faint traces of a torus do not appear until 30%. For more complex images (like the bunny and the horse), an intuitive person should be able to recognize an image with only 10% of its important edges showing. It is probably necessary to use at least 20% of the important edges for a person to be able to identify the image from most orientations.

Non-Photorealistic Rendering in Art

Non-Photorealistic Rendering using Watercolor Inspired Textures and Illumination by Eric Lum and Kwan-Lin Ma also uses some silhouette edge detection when creating their watercolor images. The silhouette edges are detected so that the edges of the surface can be given a softer appearance where the edges can fade into the background.

Skeleton Based Toon Shading of 3D Human Characters by Jung Shin uses silhouette edges to remove unnecessary details of images and also it mentions using silhouette edges to determine where to highlight.