------------------------------------------------- Overview sp.cpp is run as follows: % sp < filename.in > filename.out i.e., it takes its input from stdin and writes to stdout. Here we describe the form of the input file. These files are not intended to be written by hand; rather they would normally be created by some other program. Samples of these other programs are described elsewhere within these pages. The input data is entirely two-dimensional. It specifies a collection of triangles, how they are glued together, and where the source point is. The source point must be a vertex. If the source is to be interior to a face, or on an edge, then the user should first partition the faces so that the source point becomes a vertex. Each triangle is described in in its own coordinate system. Its three vertices are given local labels 0,1,2, counterclockwise. Vertex 0 is necessarily at the origin, vertex 1 is necessarily on the positive x-axis. And vertex 2 should have a positive y-coordinate. Although only three of the six coordinate values need be entered, since three are required to be zero, the input file must include all six in the order indicated. The coordinates are floating point numbers (doubles in the code), and although they could be entered as integers (when they happen to be whole numbers), we follow the convention of representing them with decimal points to visually distinguish them from the vertex labels, which of course are always integers. In addition to the local vertex labels, each vertex has a unique global label. Although it would be possible to generate these labels from the input, we assume they are available ahead of time, and the global index of each triangle vertex must also be specified. How the triangles glue to one another is defined by appropriate integer indices of faces and vertices. Finally, the source face and source vertex are specified at the end of the file. ------------------------------------------------- Detailed Specification Let nV be the number of vertices, and nF the number of faces. Each face must be a triangle. Each face has a unique integer index in [0..nF-1]. Each vertex has a unique integer global index in [0..nV-1]. Each vertex also has a local index in {0,1,2}, representing a ccw boundary traversal around each incident face. Each triangle's shape is specified in 2D, with the 0-th vertex at the origin, and the 1st vertex on the positive x-axis, and the 2nd vertex with positive y-coordinate. The gluing between the triangles is specified with the index of the three adjacent faces, and the local indices of their glued vertices. An input file for sp.cpp consists of five pieces of information: ------------------------------------------------- 1. nF = number of faces (necessarily triangles) 2. nV = number of vertices 3. 2D coordinates and indices of vertices for each face 4. gluing instructions for each face 5. source vertex specified by: index of source face, and local index of vertex on face, {0,1,2} ------------------------------------------------- Between any of the pieces, comments starting with # in the first char position are permitted. Items 1, 2 should be self-explanatory. Items 3, 4 and 5 are detailed below. ------------------------------------------------- 3. 2D coordinates and indices of vertices for each face F nF lines of the form x0 y0 v0 x1 y1 v1 x2 y2 v2 where (x0,y0) = (0.,0.) = vertex 0 of face F (long floats) (x1,y1) = (x1,0.) = vertex 1 of face F (long floats) (x2,y2) = vertex 2 of face F (long floats) v0 = global index of vertex 0 of face F v1 = global index of vertex 1 of face F v2 = global index of vertex 2 of face F The faces may be listed in any order. However, the order is used to assign face indices, which must be consistent with the gluing instructions below. Note that it is important to input the coordinates to as full precision as is available, to ensure correct distance computations. ------------------------------------------------- 4. gluing instructions for each face F nF groups of 3 lines, one per face edge, of the form af0 i0 af1 i1 af2 i2 (or these six numbers could be on one line) where af0 = index of face adjacent to edge 0 of face F i0 = local index of the edge glued to edge 0 of face F af1 = index of face adjacent to edge 1 of face F i1 = local index of the edge glued to edge 1 of face F af2 = index of face adjacent to edge 2 of face F i2 = local index of the edge glued to edge 2 of face F This is (admittedly) confusing. Each of the three vertices of a triangle face have a local index 0,1,2. We define the edge ccw after vertex i to be edge i. So edge 0 runs from vertex 0 to vertex 1, etc. Here is an example. Suppose F is the face whose gluing is being defined. F' below is af0, for it is the face adjacent to edge 0 of face F. In the illustration, the index i0 is 1 (*not* 2), because edge 1 of F' is the edge that glues to edge 0 of F. 2 / \ / \ / F \ /0 1\ +-----------+ (Numbers are vertex local indices) \ 2 1/ \ F' / \ / \ / 0 If an edge of face F is a boundary edge, the two corresponding indices are -1 -1. ------------------------------------------------- 5. source vertex specified by: index of source face, and local index of vertex on face, {0,1,2} This is straightforward, except that the source should not lie on the boundary. So if the data specifies a surface with boundary, and the source is on the boundary, it is necessary to augment the data to surround that boundary with dummy points so that the source is interior to the surface, and surrounded entirely by incicent faces. The shortest paths to these dummy points can be ignored in the output. -------------------------------------------------

Research supported by NSF grant CCR-9731804.

Last Update: