INTERFACE MSImageMap; IMPORT MSImage, PSPlot; TYPE LONG = LONGREAL; NAT = CARDINAL; BOOL = BOOLEAN; SIGN = [-1..+1]; TYPE Point = MSImage.Point; (* Coordinates of the center of an image pixel. *) Size = MSImage.Size; (* Dimensions (X and Y) of an image. *) Node = Point; (* Name of a vertex of the reference mesh. *) CONST NoPoint = Point{LAST(NAT), LAST(NAT)}; TYPE T = ARRAY OF ARRAY OF Point; (* An MSImageMap.T is a partial mapping from vertices of a reference mesh to integer points of the plane. THE REFERENCE MESH The vertices of the reference mesh are also pairs of positive integers. Its topology is that of an infinite regular triangular network. Each node (x,y) is connected to the six nodes 0 1 2 3 4 5 (x+1,y) (x,y+1) (x-1,y+1) (x-1,y) (x,y-1) (x+1,y+1) in positive order, as shown below left. 2-1 2---1 y / |\|\ / \ / \ / 3-*-0 3---*---0 *---- \|\| \ / \ / x 4-5 4---5 The reference mesh is a topological object, without intrinsic geometry. Since its edges are treated uniformly in the algorithms, it may be more natural to think of them as equal in length, as shown above right. Note that in this picture the "y" axis is tilted 30 degrees to the right of the vertical. THE MAPPING An MSImageMap.T "m" represents a mapping from some finite subset of the vertices of the reference mesh to integer points of the plane. Let "p=(x,y)" be a node of the reference grid. If "m[y,x] = NoPoint", then "m(p)" is undefined, by convention. Otherwise, "m[y,x]" is the position of "p", denoted here by "m(p)". Note that the domain of the mapping is contained in the non-negative quadrant. If "m(p)" is defined, we say that "p" is `placed'. If "e={p,q}" is an edge of the reference mesh, and "p" and "q" are both placed, then we consider "m(x)" to be defined also for any point "x" interior to "e", by linear interpolation between "m(p)" and "m(q)". Similarly, if the three corners of a mesh triangle are placed, we extend "m()" to the interior of the triangle, by linear interpolation. *) PROCEDURE Neighbor(p: Point; k: INTEGER): Node; (* The "k"th neighbor of "p" in the reference mesh, counting counterclockwise from "p + (1,0)", modulo 6. *) CONST RefineRatio = 4; (* The area scaling factor of "Refine". *) PROCEDURE Refine(READONLY mOld: T): REF T; (* Given a partial mapping "mOld" from the reference mesh "tOld" to the integer grid "gOld", returns a mapping "mNew" from a refinement "tNew" of "tOld" to a refinement "gNew" of "gOld". In the current implementation, the refined mesh "tNew" is obtained by splitting every edge of "tOld" with a new vertex, so that each triangle of "tOld" becomes four triangles of "tNew". The function "RefinedNode(p)" gives the node of the finer refrence mesh that corresponds to node "p" of the coarser mesh. Similarly, the refined grid "gNew" is such that the point "u" of "gOld" becomes "MSImage.RefinedPoint(u)" in "gNew". If a node "pNew" of "tNew" was inherited from node "p" of "tOld", then "mNew(pNew) = MSImage.RefinedPoint(m(p))". Otherwise, if "pNew" is an edge-splitting node, "mNew(pNew)" is defined by interpolation of the endpoints of that edge. The result of that interpolation had better be an integer point. *) TYPE Sign = [-1..+1]; PROCEDURE Extrapolate(VAR m: T; gridSize: Size; maxDist: LONG; sign: SIGN); (* Tries to extend the mapping "m" by one layer of triangles. The procedure first collects all unplaced mesh nodes which are adjacent to at least one placed node. Then, for every such node "p", it tries to find a position "u" in "[0..NX-1, 0..NY-1]", where "(NX,NY) = gridSize", that satisfies the following contraints: (1) for any placed neighbor "q" of "p", the distance from "u" to "m(q)" is at most "maxDist", (2) for any two placed nodes "q,r" that are consecutive neighbors of "p" in the mesh, the triangle "u,m(q),m(r)" is either zero or has the specified "sign". If the procedure can find such an "u", it sets "m(p) := u". Otherwise it leaves "m(p) = NoPoint" as before. Note that placing one candidate may affect the number of choices available for other candidates. Therefore, the candidates are processed in order of decreasing number of placed neighbors (in the original mapping). Hopefully this order minimizes the chances of getting "painted into a corner". This order should also give to candidates that originally had only one placed neighbor the chance to have two or more placed neighbors by the time they are processed. Since a single placed neighbor does not give any hint about the predominant angle of rotation, candidates in that situation will be placed on top of that single neighbor. *) PROCEDURE AreaX2(READONLY m: T): INTEGER; (* Sum of area of all triangles in the image mesh of "a" (i.e. the images of all reference mesh triangles that are mapped by "a"). The result is scaled by 2 to keep it integer. *) PROCEDURE Clone(READONLY m: T): REF T; (* Makes a copy of "m" in newly allocated storage. *) PROCEDURE Plot(f: PSPlot.File; READONLY m: T); (* Draws the reference mesh as transformed by the map "m". Assumes "f" has already been initialized and is ready for drawing commands. *) PROCEDURE RefinedNode(p: Node): Node; (* Returns the node of the refined mesh (see "Refine") that corresponds to node "p" of the coarser mesh. *) PROCEDURE RefinedSize(p: Size): Size; (* Given the size of the array containing a coarse map, returns the minimum size of the array that will contain the refined mesh, with enough space around it for expansion. *) PROCEDURE FromTriangle(READONLY u, v, w: Point): REF T; (* Returns a map that takes the reference grid nodes "(0,0)","(1,0)","(0,1)" to the points "u", "v", "w", respectively. *) END MSImageMap.