DOC PREVIEW
SWARTHMORE CS 97 - Seamless Intersection Between Triangle Meshes

This preview shows page 1-2-3 out of 8 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Seamless Intersection Between Triangle MeshesDavid [email protected] present an algorithm that providesartistic control of the rendering of in-tersections between two triangle meshes.We detect the intersection edges usingan octree, and then seamlessly subdivideboth meshes at and around the intersectionedges to allow local geometry morphingand creation of transition texture bands.1 IntroductionIn computer graphics there has been a lot of progresson rendering techniques that use diffuse, height, andnormal maps to make rendered surfaces look muchmore detailed than their underlying geometry. How-ever, these techniques do nothing to break up thelinear silhouette of each polygon (Figure 1). Thisis a very difficult problem to solve in general, be-cause the silhouette of an object can change signif-icantly every frame, so any algorithm that appropri-ately changes the silhouette would have to be ex-tremely fast for real-time applications. There hasbeen some progress in this area, but nothing that isreally practical yet (Oliveira and Policarpo, 2005).However, this problem can be solved more easilywhere two static objects intersect because the inter-section line is independent of camera position.There are two obvious problems with the naiveintersection. First, there is an immediate discon-tinuity in the lighting and texturing that is unlikewhat you see in such intersections in real-life (Fig-ure 2). Second, this discontinuity occurs along per-fectly straight lines, destroying the illusion of depththat the texture mapping is supposed to create.2 Seamless Intersection AlgorithmTo make intersections more realistic, we must ad-dress both of these problems. First, we need to findFigure 1: Rocks on the beach in Crysis, with shad-ows disabled for clarity. Despite the detailed tex-tures, there is an unrealistically sharp line betweenthe big rocks and the terrain.Figure 2: A photograph of a post intersecting theground.the intersection between the objects and create ver-tices at each point of intersection. We can then findauxiliary intersections which we will discuss auxil-iary intersections in more detail in section 2.2, andexplain more clearly why they are important. Usingour new intersection and auxiliary intersection ver-tices, we can apply geometric deformations aroundthe intersections, and create texture bands to makethem look more natural. None of these steps are triv-ial, so we will explore them one at a time.2.1 Data StructuresFirst, we should look at the data structures we areusing to represent the mesh. The mesh object con-tains an array of vertices and an array of triangles.Each vertex object contains several vectors: a 3-partvector storing its local coordinates, a 3-part vectorstoring its surface normal, and a 2-part vector storingits texture coordinates. Each triangle object containsthree pointers, one to each of its vertices.2.2 Finding Intersection SegmentsTo find the intersection of two meshes, we couldcheck every triangle against every other triangle tosee if there is an intersection. However, this wouldrequire O(n2) comparisons, which is not acceptablewhen working with detailed meshes. Fortunately,we can do much better using what I call an inter-section octree (Figure 3), which indexes pairs of tri-angles that might intersect. Each node in the octreecontains the coordinates of its bounding box and twolists of triangles (one for each mesh). We create theroot of the octree by taking the intersection of thebounding boxes of each mesh, and adding all of thetriangles from each mesh that at least partially liewithin this shared bounding box. We then recur-sively subdivide each node until it reaches a maxi-mum depth or no longer contains at least one trian-gle from each mesh. Finally, we walk through all ofthe child nodes and report each pair of triangles, andcheck each pair for intersection using well-knowntechniques (Moller, 1997), returning the intersectionas a line segment. We have now efficiently found theintersection between two meshes as a set of line seg-ments (Figure 4), which will form a closed loop ifboth meshes are closed.Figure 3: The intersection octree generated by apower transformer and a detailed sidewalk. The oc-tree returned 70 pairs of triangles that might inter-sect, out of 846,000 possible pairs.Figure 4: The intersection segments between apower transformer and a sidewalk.Figure 5: Without an auxiliary intersection (left),the deformation propagates in an uncontrolled way.With the auxiliary intersection (right), we have pre-cise control over the shape of the deformation.Figure 6: Scaling a model by moving vertices alongtheir normals, resulting in discontinuities at sharpedges.2.3 Finding Auxiliary IntersectionsIf we would like to change the geometry aroundthe intersecting object, we will need to find auxil-iary intersections to protect the environment geom-etry from these changes(Figure 5). For example, ifa tree is intersecting the ground on a large, flat fieldrepresented by a single triangle, then altering the in-tersection points will alter the geometry of the en-tire field. If we want to create a small slope in theground around the tree of some controlled size, saytwo inches, then we can find the auxiliary pointsby translating each vertex in the object out by twoinches in the direction of the surface normal. How-ever, for meshes with sharp edges, the surface nor-mals of overlapping vertices can point in differentdirections, and moving each vertex along its surfacenormal could result in a discontinuous mesh (Fig-ure 6). We can solve this by temporarily averagingtogether all normals belonging to overlapping ver-tices (Figure 7).Figure 7: Scaling a model by moving vertices alongtheir corrected normals. This results in some distor-tion, but no discontinuitiesThis can be done in O(n log n) time using a kd-tree (Bentley, 1975). We loop through each vertexin the model, and check if the tree is storing a ver-tex that has the same coordinates. If not, we addthe vertex to the tree. If so, we store a pointer tothe vertex that is already in the tree. Now for eachgroup of overlapping vertices, we have a represen-tative vertex in the tree, and every other overlappingvertex has a pointer to its representative. We findthe average normal for each representative vertex bylooping through the vertices again, adding each ver-tex’s normal to its representative’s normal, and thennormalizing it by dividing it by its length. Finally,we can translate each vertex by


View Full Document

SWARTHMORE CS 97 - Seamless Intersection Between Triangle Meshes

Documents in this Course
Load more
Download Seamless Intersection Between Triangle Meshes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Seamless Intersection Between Triangle Meshes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Seamless Intersection Between Triangle Meshes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?