Skip to topic
|
Skip to bottom
Jump:
TModeling
TModeling Web
TModeling Web Home
Changes
Notify
Index
Search
Webs
BioGeometry
Main
TModeling
TWiki
Edit
Attach
Printable
TModeling.TripodDataStructure
r1.1 - 16 Aug 2005 - 14:49 - Main.guest
topic end
Start of topic |
Skip to actions
%TOC% ---++ Motivation for Tripod (Data Structure for Embedded Triangulations) ---+++ Edge-based Data Structure Each edge stores * pointers to its vertices: 2 * pointers to the next edges cw and ccw around both vertices: 4 * pointers to faces on either side of edge: 2 <img src="%ATTACHURLPATH%/Capture7-26-2005-11.36.29AM.jpg " alt="8 pointers per edge " /> Therefore, edge-based structures store 8 pointers per edge. ---+++ Face-based Data Structure Each face (or triangle) stores * pointers to adjacent triangles: 3 * pointers to it vertices: 3 <img src="%ATTACHURLPATH%/Capture7-26-2005-11.34.04AM.jpg" alt="6 pointers per face" /> Therefore, face-based structures store 6 pointers per face. ---+++ Euler's Relation We know from Euler's Relation that * e = 3v - 6 and * v - e + f = 2 *e = 3v - 6* Therefore, edge-based structures store 3 x 8 or *24 pointers per vertex*. Additionally, if we count the number of faces in a triangulation and multiply by 3, then every edge will be counted twice. (Every face is bounded by exactly 3 edges, and each edge has a different face on either side of it.) <Hmmmm... this sounds like an infinite triangulation.> Therefore, * 3f = 2e Substitute 2e = 3f into v - e + f = 2<br> 2v - f = 4 *f = 2v - 4* Therefore, face-based structures store 2 x 6 or *12 pointers per vertex*. ---+++ Advantages of Tripod * Tripod stores only *6 pointers per vertex*. * Tripod is vertex based, and vertices are the least ephemeral (compared to edges and faces) and keep location. <Hmmm... I guess vertices never move.> ---++ Features of Tripod * There is a bounding triangle (outer face). * Outer face is a cycle to the left. <img src="%ATTACHURLPATH%/Capture7-26-2005-11.44.12AM.jpg" alt="Bounding Triangle" /> * Every face is a triangle. ---+++ Intricate Features of Tripod * Every vertex (not on the outer face) has exactly 3 outgoing edges labeled 0, 1 and 2 (blue, green, red on the [[http://www.cs.unc.edu/~snoeyink/demos/tripod/home.html Demo]]) ccw. Edge labels are called Schnyder labels. * Incoming edges between _i_ and _i_ + 1 are labeled (_i_ + 2)mod 3. This causes three spanning trees: each including one vertex of the outer face and all vertices inside. (See the [[http://www.cs.unc.edu/~snoeyink/demos/tripod/home.html Demo]]: each color (red, blue and green) represents a different spanning tree.) <img src="%ATTACHURLPATH%/Capture7-26-2005-11.48.20AM.jpg" alt="Edge Schnyder Labels" /> * For an outgoing edge e, e.inc points to the next outgoing edge ccw of e (label is incremented, modulo 3) and e.dec points to the next outgoing edge cw of e (label is decremented, modulo 3). <img src="%ATTACHURLPATH%/Capture7-26-2005-11.52.19AM.jpg" alt="e.inc and e.dec" /> <But this would mean 6 more pointers per vertex, right?> * Each outgoing edge has two pointers : cw, ccw <img src="%ATTACHURLPATH%/Capture7-26-2005-11.56.14AM.jpg" alt="cw and ccw pointers" /> <The abstract incorrectly states that these pointers point to vertices. They instead point to edges as shown below.> ---+++ CW and CCW Pointers To find out the edge pointed by cw/ccw pointers * Go cw/ccw around the vertex from the edge * If the first edge is incoming to the vertex, you've got your edge! STOP! * If the first edge is outgoing from the vertex, find its second vertex. Your edge is the outgoing edge from this vertex with the same label as the original edge. <img src="%ATTACHURLPATH%/Capture7-26-2005-11.59.24AM.jpg" alt="cw and ccw pointers" /> A2.cw --> C0<br> B0.cw --> C0<br> B2.ccw --> A2<br> C0.ccw --> B2<br> C0.cw --> D1<br> D1.cw --> A2 ---+++ Incoming and Outgoing Edges on a Vertex Let e be an outgoing edge from a vertex v, and let f be the next edge ccw from e. When f is incoming to vertex v, e.ccw --> f. Here, f always contributes an edge to a triangle with e. <img src="%ATTACHURLPATH%/Capture7-26-2005-4.19.55PM.jpg" alt="triangle with edges e and f" /> When f is outgoing from vertex v, either e.ccw or f.cw will contribute an edge to a triangle with edge e. Here, e.ccw contributes an edge. <img src="%ATTACHURLPATH%/Capture7-26-2005-4.27.32PM.jpg" alt="triangle with edges e and e.ccw" /> Here, f.cw contributes an edge. <img src="%ATTACHURLPATH%/Capture7-26-2005-4.36.22PM.jpg" alt="triangle with edges e and f.cw" /> <Note: An edge does not point to its own destination; that pointer will be recovered from edges incident on the same triangle. [I have no idea what this means]> ---++ Types of Triangles and Tests for them There are four different types of triangles to the left of an edge e. We can distinguish between these four types with the following tests: ---+++ Cycle Here, edges form a ccw cycle. <img src="%ATTACHURLPATH%/Capture7-26-2005-4.47.43PM.jpg" alt="cycle" /> Test: *e.ccw<sup>3</sup> == e* ---+++ Mouth Here, non-e edges are outgoing from the same vertex. <img src="%ATTACHURLPATH%/Capture7-26-2005-4.51.39PM.jpg" alt="mouth" /> Test: *e.ccw.inc.cw == e* <br> Above, edges e and f have the same Schnyder label since they are both incoming to the same vertex with no outgoing edges from that vertex between them. ---+++ Wedgepar Here, two edges are outgoing from the same vertex, and the third is directed toward e. <img src="%ATTACHURLPATH%/Capture7-26-2005-4.59.47PM.jpg" alt="wedgepar" /> Test: *e.ccw.cw.dec == e* <br> Above, edges e and f have the same Schnyder label. ---+++ Wedgerev Here, two edges are outgoing from the same vertex, and the third is directed away from e. <img src="%ATTACHURLPATH%/Capture7-26-2005-5.10.28PM.jpg" alt="wedgerev" /> Test: *e.inc.cw.ccw == e* <br> Above, edges f and g have the same Schnyder label. It is important to argue that the tests above return true on their triangle type, and return false on any other triangle type. See TriangleTests for details. Note that tests for triangles right of e can be obtained by swapping .ccw with .cw and .inc with .dec ---++ Operations ---+++ Identifying Edges A directed edge can be identified by specifying its vertex, Schnyder label and direction (incoming or outgoing<not sure of this!>).<The demo seems to identify edges by unique numbers 0, 1, 2, 3... Hmmm> ---+++ Accessing Edges Once you know what type of triangle you have, you can access the next edge around a triangle given a first edge. See the tests for types of triangles. ---+++ Swapping Edges When swapping edges (one incoming to a vertex; the other outgoing), Schnyder labels are preserved. Pointers will have to be reassigned, however. <img src="%ATTACHURLPATH%/Capture7-27-2005-5.17.56PM.jpg" alt="Before Diagonal Swap" /><img src="%ATTACHURLPATH%/Capture7-27-2005-5.23.23PM.jpg" alt="After Diagonal Swap" /> Above, edges e and f are swapped. Pointers A1.ccw, A2.cw, B1.ccw, B2.cw, D0.ccw, D1.cw and D2.ccw all have to be reassigned. Swapping becomes tricky when triangles right and left of a "diagonal edge" are of wedge type. <img src="%ATTACHURLPATH%/Capture7-27-2005-5.31.35PM.jpg" alt="Wedge Triangles" /> Above, triangles left and right of edge e are of wedge type, so edges e, f and g are all outgoing from vertex v. There is always a directed cycle of edges through v that does not include edge e. See DirectedCycle for more on finding this directed cycle of edges. By reversing this cycle and relabeling edges, we can make either f or g incoming <the abstract says that we need to find a new outgoing vertex... confused>to vertex v. <img src="%ATTACHURLPATH%/Capture7-27-2005-5.37.31PM.jpg" alt="Reversing Edges" /> Now, we can perform a swap between e and f. Schnyder labels are not preserved in this case. -- Main.SisillaSookdeo - 25 Jul 2005
to top
End of topic
Skip to action links
|
Back to top
Edit
|
Attach image or document
|
Printable version
|
Raw text
|
More topic actions
Revisions: | r1.1
|
Total page history
|
Backlinks
You are here:
TModeling
>
TripodDataStructure
to top
Copyright © 1999-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki?
Send feedback