System and method for generating planar maps of three-dimensional surfaces

[0002] 1. Field of the Invention

[0003] The present invention relates generally to computer graphics, and more particularly to the generation of planar maps of three-dimensional surfaces.

[0004] 2. Related Art

[0005] The problem of flattening a three dimensional (3-D) surface into a two-dimensional (2-D) domain is age old and takes several forms.

[0006] For example, one of the central concerns of cartography is the representation of a sphere as a planar map. As is well known, it is impossible to represent such a surface in 2-D without distortion and discontinuity. In a Mercator projection, for example, Greenland appears much larger than it really is in relation to more southern countries. Cartographers mitigate this problem either by cutting the surface of the globe into segments, thus trading off increased discontinuity for decreased distortion, or by using other projections which trade off size distortions for shape distortions.

[0007] Other application areas involve surface flattening, or the inverse problem, the construction of 3-D surfaces from originally flat components. An example of flattening involves taking the hide of an animal and creating flat pieces of leather or fur. An example of the inverse process is the construction of apparel such as shoes and garments out of pieces of leather, fur, or cloth. Going in either direction involves stretching/shrinking (distortion) and the alteration of discontinuity/continuity (e.g., by cutting or sewing).

[0008] The problem of correspondences between flat and curved surfaces arises in computer graphics software. A technique known as texture mapping is used to give 3-D surfaces character and realism. Whenever there exists a mapping from a 3-D surface to a 2-D region, an arbitrary image can be identified with the 2-D region so that rendered attributes of the surface (e.g., color, shininess, displacement) are controlled by the image's values. An image used in this way is called a texture map.

[0009] For 3-D surfaces such as bicubic patches, the mapping from surface to a 2-D region is intrinsic. However, for 3-D surfaces composed of polygons, an a priori mapping does not exist. The construction of such mappings, known as parameterization, has been a problem in computer graphics for several years because without a parameterization a polygonal surface is not amenable to texture mapping. Parameterization is equivalent to flattening.

[0010] Some conventional parameterization methods involve 1) selecting a boundary on a 3-D surface, 2) mapping the boundary to a planar convex polygon, and 3) using relaxation methods to calculate a mapping of interior points of the surface to interior points of the convex polygon. To visualize this process, imagine the 3-D surface to be a rubber sheet whose boundary is stretched around the perimeter of the polygon.

[0011] A drawback with these methods is that the planar convex polygon (e.g., a circle or square) does not necessarily reflect the shape of the surface boundary, thus increasing the possibility that the mapping will introduce shape distortions, particularly in polygons close to the boundary. A need therefore exists for an improved system and method for creating a planar boundary which inherits the geometry of a given surface boundary.

[0012] Briefly stated, the present invention is directed to a system and method for generating planar maps which reflect the distances and angles of a 3-D surface, where the user can manually adjust the balance between discontinuity and distortion.

[0013] A preferred embodiment of the present invention includes receiving a 3-D surface, defining a surface boundary on the 3-D surface, and generating a planar map based on the 3-D surface and the defined surface boundary. An edge-and-angle proportional mapping is preferably used to map the surface boundary to a map boundary. Those surface vertices not forming the surface boundary are then relaxed to create the map vertices not forming the map boundary.

[0014] A feature of the present invention is that a user selectively adjusts the balance between discontinuity and distortion in the planar map.

[0015] Another feature is that the present invention allows for the creation of planar maps such that each point on the 3-D surface corresponds to a unique point on the planar map. As a result, operations may be performed on the simpler 2-D planar map rather than the more complex 3-D map, and the result of the operations may be uniquely mapped to the 3-D surface.

[0016] Another feature of the present invention is that the majority of the vertices on a 3-D surface are mapped automatically, even though the user maintains a high degree of control over the mapping process via altering the 3-D surface boundary.

[0017] Another feature of the present invention is that user-selected map vertices may be pinned to a user-selected location, and held fixed while a conventional relaxation technique is applied. This provides the user with a greater degree of control over the relaxation process.

[0018] Another feature of the present invention is that a map boundary interpolation can be performed to generate alternate planar maps. These alternate planar maps may be superior in some respect to non-interpolated planar maps.

[0019] Further features and advantages of the invention, as well as the structure and operation of various embodiments of the invention, are described in detail below with reference to the accompanying drawings. In the drawings, like reference numbers generally indicate identical, functionally similar, and/or structurally similar elements. The drawing in which an element first appears is indicated by the leftmost digit(s) in the corresponding reference number.

[0020] The present invention will be described with reference to the accompanying drawings, wherein:

[0021] FIG. 1 is a block diagram of a digital computer environment within which the present invention is used;

[0022] FIG. 2 is a flowchart illustrating the functions performed according to the present invention;

[0023] FIG. 3A depicts an example 3-D surface;

[0024] FIG. 3B depicts an example 3-D surface with a defined boundary;

[0025] FIG. 3C depicts an example 3-D surface with a modified (cut) boundary;

[0026] FIG. 4A depicts an example planar map of the example 3-D surface with no cuts;

[0027] FIG. 4B depicts an example distortionless planar map of the example 3-D surface after cuts;

[0028] FIG. 5 is a flowchart detailing the generation of planar maps;

[0029] FIG. 6 is a flowchart detailing boundary mapping;

[0030] FIG. 7 is a flowchart detailing a preferred embodiment of an edge-and-angle proportional boundary mapping;

[0031] FIG. 8A illustrates a first step in a preferred embodiment of an edge-and-angle proportional boundary mapping;

[0032] FIG. 8B illustrates a second step in a preferred embodiment of an edge-and-angle proportional boundary mapping;

[0033] FIG. 8C illustrates a third step in a preferred embodiment of an edge-and-angle proportional boundary mapping;

[0034] FIG. 8D depicts a map boundary generated according to a preferred embodiment of an edge-and-angle proportional boundary mapping;

[0035] FIG. 9 is a flowchart detailing relaxation and pinning;

[0036] FIG. 10A depicts an example planar map with a distorted map primitive;

[0037] FIG. 10B depicts an example planar map after a map vertex has been moved and pinned; and

[0038] FIG. 11A depicts an example self-crossing map boundary generated according to a preferred embodiment of an edge-and-angle proportional boundary mapping (source boundary);

[0039] FIG. 11B depicts an example map boundary generated according to an edge-proportional boundary mapping (target boundary);

[0040] FIG. 11C depicts an example map boundary generated according to an interpolation between a source boundary and a target boundary; and

[0041] FIG. 12 is a flowchart detailing the map boundary interpolation method.

[0042] Overview of the Environment

[0043] FIG. 1 is a block diagram of a digital computer environment 100 within which the present invention is used. A user 102 interacts with a computer system 104 according to conventional user interface techniques. The present invention is preferably implemented as computer readable program code 108 stored on a computer usable medium 110, accessed via a communication link 112. Computer system 104 operates under the control of computer readable program code 108.

[0044] Computer system 104 represents any computer system known to those skilled in the art with sufficient capability (i.e., both memory and processing power) to execute computer readable program code 108. Examples of computer system 104 include, but are not limited to, a microcomputer, workstation, or terminal connected to a central processor.

[0045] Computer usable medium 110 is any digital memory capable of storing computer readable program code 108. Examples of computer usable medium 110 include, but are not limited to, hard disks (both fixed and portable), floppy disks, and CD-ROMs.

[0046] Communication link 112 provides the communication pathway between computer system 104 and computer usable medium 110. Communication link 112 includes, but is not limited to, parallel cables, local area networks, wide area networks, the Internet, and any other combination of electrical equipment designed to pass an electrical signal from one point to another.

[0047] User 102 communicates with computer system 104 according to conventional user input/output (I/O) techniques. Computer system 104 (under the control of computer readable program code 108) provides output to user 102 according to the present invention via video displays and audio messages, for example. User 102 provides input to computer system 104 via a keyboard, mouse, joystick, voice recognition, or any other type of input device known to those skilled in the art.

[0048] The present invention is preferably implemented as computer readable program code 108. Computer readable program code 108 provides the instructions necessary for computer system 104 to execute the functionality described below. Those skilled in the art will recognize that computer readable program code 108 might be implemented in any computer language (e.g., C) acceptable to computer system 104.

[0049] The present invention is described below in terms of computer graphics displays and operations performed upon these displays. Example graphical displays are provided, along with flowcharts which describe various operations performed on the displays. Those skilled in the art will readily recognize how to implement the graphical displays and operations on those displays as computer readable program code 108.

[0050] Over View of the Invention

[0051] The purpose of this section is to provide an overview of the functionality encompassed by the present invention. FIG. 2 is a flowchart 200 describing functions performed by computer system 104 under the control of computer readable program code 108 according to the present invention, and the relative order in which these functions preferably occur. Those skilled in the art will recognize that these steps might equivalently be performed in different sequence, and still achieve the results described below.

[0052] In step 202, computer system 104 receives a 3-D surface. FIG. 3A depicts an example 3-D surface 300. The functionality of the present invention is described below as operations on 3-D surface 300—those skilled in the art will recognize how these operations would apply to any arbitrary 3-D surface. Those skilled in the art will also recognize that 3-D surface 300 can be received from any digital memory accessible via communication link 112, not just computer usable medium 110.

[0053] 3-D surface 300 includes one or more surface primitives 302. A surface primitive 302 is a planar region bounded by surface edges 304. A surface vertex 306 is the point at which two or more surface edges 304 meet. Consider 3-D surface 300. Surface vertices 306 are labeled with a single digit number between 1 and 8, and will be referred to, e.g., as surface vertex 1. Surface edges 304 will be referred to herein with reference to the surface vertices 306 each particular edge connects. For example, surface edge 304 connecting surface vertex 2 and 6 will be referred to as surface edge 2-6. Similarly, surface primitives 302 will be referred to with reference to the surface vertices 306 surrounding each particular surface primitive. For example, surface primitive 302 bounded by surface vertices 1, 2, 6, and 5 will be referred to as surface primitive 1-2-6-5 (shown in FIG. 3A as the shaded region). 3-D surface 300 is an “open-topped” box-surface vertices 1 and 3 are not connected, and surface primitives 1-2-3 and 1-3-4 do not exist. 3-D surface 300 therefore includes five surface primitives 302, eight surface vertices 306, and twelve surface edges 304.

[0054] Returning to FIG. 2, in step 204, a surface boundary is defined on 3-D surface 300. The surface boundary is used by the present invention to generate a planar map from 3-D surface 300, as is described in detail below. A surface boundary is a closed path along 3-D surface 300 composed of surface edges 304 and surface vertices 306. In FIG. 3B, four surface edges (4-1, 1-2, 2-3, and 3-4) and four surface vertices (1, 2, 3, and 4) form surface boundary 308, which will be referred to herein as surface boundary 1-2-3-4.

[0055] In step 206, a planar map is generated based on the 3-D surface received in step 202, given the surface boundary defined in step 204. FIG. 4A depicts an example planar map 400. As with 3-D surfaces, planar map 400 includes map primitives 402, map edges 404, map vertices 406, and a map boundary 408 made up of four map edges (1-2, 2-3, 3-4, and 4-1) and four map vertices (1, 2, 3, and 4). However, planar map 400 is defined in two dimensions (i.e., planar map 400 is defined in a single plane) whereas 3-D surface 300 is defined in three dimensions. The same naming conventions described above with respect to 3-D surface 300 will be followed with respect to planar map 400.

[0056] Planar map 400 must satisfy the following restrictions: each point on 3-D surface 300 must map to a unique point on planar map 400, and the connectivity of 3-D surface must be maintained in planar map 400. The uniqueness restriction ensures that each element (i.e., vertex, edge, and primitive) of the 3-D surface corresponds in a one-to-one fashion with one element of the planar map. Map vertices 406 correspond in one-to-one fashion with surface vertices 306, map edges 404 correspond to surface edges 304, and so on. For example, map vertex 2 corresponds to surface vertex 2, map edge 2-1 corresponds to surface edge 2-1, map primitive 1-2-6-5 corresponds to surface primitive 1-2-6-5 (both are represented as shaded regions), and map boundary 1-2-3-4 corresponds to surface boundary 1-2-3-4. In order to satisfy this restriction, none of the map primitives 402 may overlap, otherwise the point of overlap would correspond to multiple locations on 3-D surface 300. However, it is not required that shapes or sizes be maintained, i.e., a map edge may be longer or shorter than the corresponding surface edge and a map primitive may be of a different shape and size than the corresponding surface primitive.

[0057] It is this one-to-one correspondence that makes planar map 400 a useful representation of 3-D surface 300. Consider an embodiment where planar map 400 represents a region of a texture map for a 3-D graphical surface in a computer graphics system. When planar map 400 satisfies the above restriction, the texture region within map primitive 402 will appear only on the corresponding surface primitive 302, though the texture may be distorted due to any differences in shape between the primitives. Those skilled in the art will recognize additional advantages of ensuring this unique one-to-one correspondence between the 3-D surface and the planar map.

[0058] In addition to requiring one-to-one correspondence, planar map 400 must also maintain the connectivity of 3-D surface 300. That is, map edges 404 and map vertices 406 must be interconnected in the same way that the corresponding surface edges 304 and surface vertices 306 are interconnected. For example, in FIG. 3B, surface vertex 4 is connected (via a single surface edge) to surface vertices 1, 3, and 8. Map vertex 4 must therefore be connected (via a single map edge) to map vertices 1, 3, and 8, as shown in FIG. 4A. Again, it is not required that the edges be the same length, nor is it required that the primitives be the same shape.

[0059] Returning to FIG. 2, flowchart 200 indicates that program flow proceeds from step 206 back to step 204. According to the current invention, the surface boundary 308 defined in the first iteration of step 204 can be modified in subsequent iterations. Once surface boundary 308 has been modified, a new planar map is generated in step 206. This iteration may be repeated as many times as necessary to achieve a desired planar mapping of the received 3-D surface.

[0060] The following sections provide detailed descriptions of steps 204 and 206. Defining the surface boundary is described first, followed by the generation of planar maps.

[0061] Defining the Surface Boundary

[0062] In step 204, a surface boundary is defined on the 3-D surface. The 3-D surface received in step 202 may have a pre-defined surface boundary, depending on the particular application. Thus, on a first iteration through the method illustrated in flowchart 200, the surface boundary may need to be defined in its entirety (if the 3-D surface has no pre-defined boundary), or user 102 may wish to modify the pre-defined surface boundary if one is present. On subsequent iterations, in step 204 user 102 may modify the surface boundary defined in the previous iteration. Thus, step 204 encompasses specifying surface boundary 308 in its entirety and/or modifying an existing surface boundary 308.

[0063] Where a surface boundary must be specified in its entirety, user 102 preferably traces the desired surface boundary 308 directly onto the displayed image of 3-D surface 300 using a mouse, trackball, joystick, or any other appropriate user input device. Those skilled in the art will recognize that standard graphical user interface (GUI) techniques might be employed to implement this tracing function. However, those skilled in the art will also recognize that methods other than manual definition could be used for defining surface boundary 308, such as an automated method which defines surface boundary 308 based on some arbitrary criteria.

[0064] Once surface boundary 308 has been defined, user 102 thereafter preferably modifies surface boundary 308 using “cutting” and “sewing” operations. Cutting 3-D surface 300 refers to splitting a surface edge adjacent to surface boundary 308, such that the modified surface boundary 308 now traces through the split edge. For example, FIG. 3C depicts 3-D surface 300 with a surface boundary 308 modified by a cutting operation. Here, user 102 has cut 3-D surface 300 from surface vertex 4 to surface vertex 8. Cutting operations will be described herein with reference to the surface vertices through which the cut passes. For example, the cut depicted in FIG. 3C would be described as a cut 4-8.

[0065] As a result of the cutting operation, an additional surface vertex and surface edge has been created. Surface vertex 4 has been split into surface vertex 4a and 4b, and two surface edges (4a-8 and 4b-8) now exist where there was only one (4-8). The modified boundary on 3-D surface 300 is now indicated by surface boundary 1-2-3-4a-8-4b. FIG. 3C depicts surface vertices 4a and 4b as being spaced apart for illustrative purposes only. Surface vertices generated as the result of a cutting operation actually occupy the same point in 3-D space, as do the split surface edges.

[0066] Sewing refers to an operation which is the opposite of cutting, i.e., user 102 may rejoin surface edges and surface vertices which have been split as the result of a cutting operation. Sewing operations will be also described herein with reference to the affected surface vertices.

[0067] Cutting a 3-D surface allows, in many instances, a less distorted planar map to be generated. Consider FIGS. 3B and 4A. Planar map 400 is a 2-D mapping of 3-D surface 300. As can be seen, the shapes of map primitives 402 are distorted as compared to their corresponding surface primitives 302. This distortion is due to the restrictions placed on planar map 400 (i.e., uniqueness and connectivity). Those skilled in the art will recognize the desirability of producing planar maps where each map primitive accurately reflects the shape of the corresponding surface primitive. For example, map primitive 1-2-6-5 (shown as the shaded map primitive in FIG. 4A) would ideally have the same shape as surface primitive 1-2-6-5 (shown as the shaded primitive in FIG. 3B). However, as can be seen, these shapes are similar but not identical. The measure of this difference in shape will be referred to as distortion.

[0068] Given the restrictions on planar map 400, it is generally not possible to produce a distortionless planar map of a 3-D surface. Consider 3-D surface 300. Clearly, it is not possible to “flatten out” this open-topped box to a distortionless planar map while maintaining connectivity and one-to-one correspondence. However, it would be possible if one were to cut the box along certain of the edges. The box could then be unfolded and laid flat, while maintaining connectivity and one-to-one correspondence.

[0069] FIG. 4B depicts a distortionless planar map 400 generated according to the present invention where user 102 performed the following cuts to 3-D surface 300 in step 204: 4-8, 8-7, 8-5, and 5-6. As shown in FIG. 4B, map boundary 1-4b-8c-5b-6-5a-8b-7-8a-4a-3-2 results from this series of cuts. Now, for example, map primitive 4a-3-7-8a and surface primitive 4-3-7-8 have an identical shape, as do the other four primitives. Those skilled in the art will recognize that further cuts will not further decrease the distortion, as planar map 400 is already distortionless. Connectivity is also maintained, as each cut creates an extra surface vertex and surface edge, which may then be separated and laid flat. Thus, cutting operations in some instances will decrease distortion in planar map 400.

[0070] However, distortion is not the only measure of interest. Those skilled in the art will also recognize that the discontinuities introduced by the cuts are not desirable for some applications. In the present context, a discontinuity refers to the situation where the map primitives corresponding to adjoining surface primitives do not adjoin because of a cut. For example, surface primitive 4-3-7-8 adjoins (i.e., shares an edge with) surface primitive 1-4-5-8; however, their corresponding map primitives 4a-3-7-8a and 6-7-8b-5a do not adjoin because of cut 7-8. Planar map 400 has greater discontinuity in FIG. 4B than in FIG. 4A, but less distortion.

[0071] This illustrates the fundamental tradeoff between discontinuity and distortion. Cutting 3-D surface 300 increases the discontinuity of planar map 400 but decreases the distortion. Those skilled in the art will recognize that the particular application to which the present invention is applied will determine the appropriate balance between distortion and discontinuity. The iterative approach of the present invention allows user 102 to achieve a desired balance by varying the number of cuts made to 3-D surface 300.

[0072] Generation of Planar Maps

[0073] Once 3-D surface 300 has been received, and surface boundary 308 defined, a planar map is then generated in step 206. FIG. 5 depicts a flowchart 500 illustrating step 206 in greater detail. Planar map generation is fundamentally a two step process: boundary mapping and relaxation. In step 502, surface boundary 308 (see FIG. 3B), which is defined in three dimensions, is mapped according to the present invention to 2-D map boundary 408 (see FIG. 4A). In step 506, conventional relaxation techniques are then applied to the remainder of the surface vertices (those surface vertices 306 not forming surface boundary 308) to form map vertices 406. These steps are described in detail in the following two sub-sections.

[0074] Steps 504 and 508 describe an extension to the basic planar mapping described in steps 502 and 506, whereby the map boundary created in step 502 is interpolated with another map boundary created according to a conventional boundary mapping technique. This extension is discussed in detail below.

[0075] Boundary Mapping

[0076] FIG. 6 depicts a flowchart 600 illustrating step 502 (mapping surface boundary 308 to map boundary 408) in greater detail. In step 602, the surface angle is calculated at each surface vertex 306 on surface boundary 308. For example, referring to FIG. 3B, the surface angle is calculated at surface vertices 1, 2, 3, and 4. The surface angle is calculated at each surface vertex 306 by determining the angle between the two boundary edges which meet at the surface vertex, where the angle is calculated traveling along 3-D surface 300.

[0077] For example, at surface vertex 4, the surface angle is equal to the angle separating surface edges 1-4 and 3-4 traveling along 3-D surface 300. To calculate the angle traveling along 3-D surface 300, the angle between surface edges 4-1 and 4-8 must be added to the angle between surface edges 4-8 and 3-4. Each of these angles is 90 degrees, so the surface angle at surface vertex 4 is 180 degrees. Similarly, at surface vertex 1, the surface angle is the total of the angle between surface edges 1-4 and 1-5 (90 degrees), and the angle between surface edges 1-5 and 1-2 (135 degrees, totaling 225 degrees). The surface angle at surface vertex 2 is 90 degrees, and 225 degrees at surface vertex 3.

[0078] In step 604, the length of each surface edge forming surface boundary 308 is calculated. For example, in FIG. 3B, the length of surface edges 1-4, 1-2, 2-3, and 3-4 are calculated.

[0079] In step 606, map boundary 408 is created, where the planar angle at each map vertex 406 along map boundary 408 is proportional to the surface angle at the corresponding surface vertex 306. Similarly, the length of each map edge along map boundary 408 is proportional to the length of the corresponding surface edge along surface boundary 308. Step 606 is therefore called an “edge-and-angle proportional” mapping.

[0080] The term “proportional” as used herein indicates approximate proportionality by a factor common to all the planar/surface angle relationships, k_a, and a factor common to all the map/surface edge relationships, k_e. For example, the planar angle at map vertex 4 is approximately equal to k_atimes the surface angle at surface vertex 4, the planar angle at map vertex 1 is approximately equal to k_atimes the surface angle at surface vertex 1, and so on for the remainder of the corresponding planar/surface angle relationships along map boundary 408. Similarly, the length of map edge 3-4 is approximately equal to k_etimes the length of surface edge 3-4, the length of map edge 4-1 is approximately equal to k_etimes the length of surface edge 4-1, and so on for the remainder of the corresponding map/surface edge relationships along map boundary 408.

[0081] Those skilled in the art will recognize that various approaches might be followed for calculating planar angles and map edge lengths which are proportional to surface angles and surface edge lengths. FIG. 7 depicts a flowchart 700 which illustrates a preferred edge-and-angle proportional mapping method. Reference will also be made to FIGS. 8A-8D which graphically illustrate these operations on surface boundary 308 as defined in FIG. 3B. Note that these illustrations are meant for explanatory purposes only—in a preferred embodiment, the calculations take place within computer system 104 and only the final result (FIG. 8D) is displayed to user 102.

[0082] In step 702, the planar angles of map boundary 408 are set equal to the corresponding surface angles calculated in step 602, and the map edge lengths of map boundary 408 are set equal to the corresponding edge lengths calculated in step 604. FIG. 8A depicts map boundary 408 at this stage of the edge-and-angle proportional mapping. The planar angle at each map vertex 406 is the angle between the two map edges 404 which meet at the map vertex in the plane in which map boundary 408 is defined. For example, map vertex 3 has a planar angle 802 as shown in FIG. 8A. Planar angle 802 is set equal to the surface angle calculated at surface vertex 3, i.e., 225 degrees. Planar angle 808 indicates the angle between map edges 1-2 and 2-3—the dashed line indicates the angular position of map edge 2-3 relative to map edge 1-2—which is set equal to the surface angle calculated at surface vertex 2, i.e., 90 degrees.

[0083] In step 704, the planar angles of map boundary 408 are adjusted in prorata fashion so that their sum is π(n−2), where n is the number of map edges forming map boundary 408. The appropriate angle proportionality factor, k_a, for achieving this angle sum is computed according to the following equation: $k_a=\frac{\pi \left(n-2\right)}{{\alpha }_{\mathrm{tot}}}$

[0084] where α_tot=sum of planar angles on map boundary The planar angle at each map vertex along map boundary 408 is multiplied by k_a; proportionality, as described above, is therefore maintained. FIG. 8B depicts map boundary 408 after planar angles 802, 804, 806, and 808 have been adjusted. Note that at this step in the mapping, the map edge lengths along map boundary 408 are equal to the corresponding surface edge lengths, and are therefore proportional (i.e., k_e=1).

[0085] In FIG. 8B, note that map boundary 408 remains open. As noted above, one constraint on boundaries, both surface and map, is that they be closed. Therefore, in step 706, map vertices 406 are appropriately displaced so as to close map boundary 408. According to the present invention, map vertices 406 are displaced in a computationally efficient manner while maintaining edge and angle proportionality.

[0086] In a preferred embodiment, each map vertex 406 is displaced in the same direction, by an amount determined by the position of the vertex on map boundary 408. Referring to FIG. 8C, map boundary 408 is shown as being open at map vertex 2 (shown between map edges 3-2 and 1-2, though by definition map vertex 2 only exists at the intersection of these two map edges). Map boundary 408 is closed by displacing the end of map edge 3-2 (at map vertex 2) according to a displacement vector 810. The magnitude and direction of displacement vector 810 are equal to the magnitude and direction of the displacement necessary to close map boundary 408. As shown in FIG. 8D, map vertex 2 is now properly displayed at the juncture of map edges 3-2 and 1-2.

[0087] The remainder of the map vertices on map boundary 408 are also displaced. In a preferred embodiment, each displacement vector is calculated according to the following formula: ${\stackrel{\_}{D}}_i=\left(\frac{L_i}{L_{\mathrm{tot}}}\right)\stackrel{\_}{D}$ $\begin{array}{ccc}\mathrm{where}& {\stackrel{\_}{D}}_i& \mathrm{displacement}\mathrm{vector}\mathrm{at}i\mathrm{th}\mathrm{map}\mathrm{vertex}\\ & \stackrel{\_}{D}& \mathrm{displacement}\mathrm{vector}\mathrm{at}\mathrm{map}\mathrm{boundary}\mathrm{opening}\\ & L_i& \mathrm{length}\mathrm{of}\mathrm{map}\mathrm{boundary}\mathrm{at}i\mathrm{th}\mathrm{map}\mathrm{vertex}\\ & L_{\mathrm{tot}}& \mathrm{total}\mathrm{length}\mathrm{of}\mathrm{map}\mathrm{boundary}\end{array}$

[0088] Referring to FIG. 8C, {overscore (D)} is illustrated as displacement vector 810 (the displacement necessary to close map boundary 408), {overscore (D)}₁is illustrated as displacement vector 816, {overscore (D)}₄is illustrated as displacement vector 814, and {overscore (D)}₃is illustrated as displacement vector 812.

[0089] The remaining map vertices (3, 4, and 1) are displaced according to displacement vectors given by the above formula. L_totis the total length of map boundary 408 (i.e., sum of the length of map edges 1-2, 1-4, 4-3, and 3-2). L_iis the length along map boundary 408 where map vertex i (i.e., the map vertex for which a displacement vector is being calculated) is positioned. For example, at map vertex 3, L₃is equal to the sum of the length of map edges 1-2, 1-4, and 4-3. This sum is divided by the total length of map boundary 408 and multiplied by {overscore (D)} to determine {overscore (D)}₃(displacement vector 812). At map vertex 4, L₄is equal to the sum of the length of map edges 1-2 and 1-4. This sum is divided by the total length of map boundary 408 and multiplied by {overscore (D)} to determine {overscore (D)}₄(displacement vector 814).

[0090] FIG. 8D depicts map boundary 408 after the map vertices have been displaced according to displacement vectors 810, 812, 814, and 816, as shown in FIG. 8C. As required, map boundary 408 is now closed. Those skilled in the art will recognize that many different approaches might be taken to close map boundary 408, and still achieve the same effect of maintaining edge and angle proportionality while minimizing computational costs. This closing of map boundary 408 completes step 706 in FIG. 7, step 606 in FIG. 6, and step 502 in FIG. 5.

[0091] Those skilled in the art will also recognize that alternative approaches exist for creating an edge-and-angle proportional boundary in step 606. One alternative approach is to simulate a system of rods whose lengths are proportional to the surface edge lengths. Each adjacent pair of rods is connected with an angular spring whose rest angle is the surface angle, and which delivers a force proportional to the departure from that angle. The simulated system is allowed to relax while constrained to a plane. The resulting configuration of rods is the map boundary.

[0092] Relaxation & Pinning

[0093] Returning to FIG. 5, now that surface boundary 308 has been mapped to map boundary 408, in step 506 a conventional relaxation technique is applied to the remainder of the surface vertices 306, i.e., those surface vertices 306 not on surface boundary 308. Relaxation techniques are well known to those skilled in the art, such as the techniques described in Matthias Eck et al., “Multiresolution Analysis of Arbitrary Meshes,” Computer Graphics (SIGGRAPH '95 Proceedings), 1995, pp. 175-76 (ACM-0-89791-701-4/95/008), which is incorporated herein by reference. Relaxation may be analogized to a configuration of springs with one spring placed along each surface edge 304 not on surface boundary 308. Surface boundary 308 is treated like a rigid framework within which surface vertices 306 are then allowed to relax, forming map vertices 406 in their rest position (i.e., the position of minimum energy).

[0094] Referring to example 3-D surface 300 in FIG. 3B, and example planar map 400 in FIG. 4A, a conventional relaxation technique is applied to surface vertices 5, 6, 7, and 8 to form the corresponding map vertices 5, 6, 7, and 8. FIG. 4A depicts a likely result of applying a conventional relaxation technique to surface vertices 5, 6, 7, and 8.

[0095] FIG. 9 is a flowchart 900 which illustrates step 506 in further detail. Once surface boundary 308 has been mapped to map boundary 408 in step 502, a relaxation technique is applied to those surface vertices not on the surface boundary in step 902 (as described above), forming those map vertices 406 not on map boundary 408.

[0096] According to a preferred embodiment, in step 904 user 102 has the option of performing a “pinning” operation. If user 102 desires to perform a pinning operation, program flow continues to step 906. Otherwise, program flow returns to step 204 in FIG. 2, where user 102 is once again able to define surface boundary 308.

[0097] In step 906, user 102 selects one or more map vertices and pins them to a particular location(s). Pinning refers to modifying the position (in the 2-D plane in which the planar map is defined) of the selected map vertices 406 and fixing the new position so that when the relaxation technique is again applied in step 902, the “pinned” map vertices are held in place. As a result, those map vertices which are pinned, like those which are on map boundary 408, are treated like a rigid framework and the remainder of the map vertices are allowed to relax.

[0098] FIG. 10A depicts an example planar map 1000 which will be used to illustrate the pinning operation. For purposes of this example, assume that a surface boundary (not shown) defined on a 3-D surface (not shown) was mapped to map boundary 408 (as shown in FIG. 10A) in step 502. Assume further that a relaxation technique was applied in step 902 to those surface vertices not on the surface boundary, forming map vertices 5, 6, 7, and 8. Those skilled in the art will recognize that, for many purposes, map primitive 1-5-8-4 might be of little use given its small size. For example, assume that planar map 1000 represents a texture map in a computer graphics system, and that map primitive 1-5-8-4 is too small to be useful and is a distorted representation of the corresponding surface primitive 1-5-8-4 (not shown). User 102 may manually correct for these problems using pinning.

[0099] According to a preferred embodiment, user 102 uses a pointing device (e.g., mouse, joystick, trackball) available with computer system 104 to “drag” map vertex 8 to a new position, such that the redefined map primitive 1-5-8-4 is less distorted and has an increased area. As shown in FIG. 10B, user 102 has dragged map vertex 8 to a new position. Now, map primitive 1-5-8-4 has a larger area and, presumably, is more representative of surface primitive 1-5-8-4 (i.e., less distortion).

[0100] Map vertex 8 has now been pinned to the new location shown in FIG. 10B. When program flow again returns to step 902 (after all pinning is complete), a relaxation technique is applied to map vertices 5, 6, and 7, which will likely relax to a new configuration (depending on the particular configuration and relaxation technique used). Map vertices 1,2,3, and 4 are held rigid because they are on map boundary 408, and map vertex 8 is held rigid because it has been pinned.

[0101] Program flow continues back to step 904, where user 102 again has the option to perform additional pinning. In this manner, user 102 may continue altering planar map 1000 until a desired result is achieved. Those skilled in the art will recognize the advantages of this approach, particularly given extremely complex planar maps with thousands of map vertices. Often, it is desirable to iteratively modify these complex planar maps by pinning key map vertices and relaxing the rest, until each map primitive has an acceptable shape and size.

[0102] Map Boundary Interpolation

[0103] The edge-and-angle proportional mapping method described above can generate planar maps having undesirable qualities. For example, the aforementioned methods can generate a map boundary which crosses itself (“self-crossing” boundary). Self-crossing map boundaries are undesirable because it is no longer true that all points on a 3-D surface map to a unique point on the planar map-the self-crossing map boundary creates an overlap region where a single point on the planar map corresponds to two or more points on the 3-D surface. Another example of an undesirable planar map is one that contains areas which are unacceptably distorted. Those skilled in the art will recognize other instances where the aforementioned methods produce undesirable planar maps.

[0104] Returning to FIG. 5, steps 504 and 508 describe an extension to the mapping methods described above whereby the map boundary generated in step 502 is interpolated with a different map boundary generated according to a conventional boundary mapping technique. This interpolation can alleviate some of the undesirable effects mentioned above.

[0105] Alternatively, the interpolation described in steps 504 and 508 can be used even where the aforementioned methods generated an acceptable planar map to provide an alternate, possibly superior in some respect(s), planar map.

[0106] For purposes of illustration, assume that step 502 has created a self-crossing map boundary, as depicted in FIG. 11A, based on a 3-D surface (not shown) with a defined surface boundary. Map edge 1s-2s crosses map edge 5s-6s and map edge 2s-3s crosses map edge 4s-5s. This map boundary will be referred to as the source map boundary 1102.

[0107] In step 504, program flow continues on to step 508 where interpolation is to be performed, or to step 506 where the interpolation is not to be performed. In a preferred embodiment, user 102 determines whether or not map boundary interpolation will be performed. Those skilled in the art will recognize that this determination could also be made automatically. For example, in an alternate embodiment interpolation is automatically performed whenever a self-crossing boundary is detected (according to conventional numerical techniques).

[0108] In those instances where map boundary interpolation is to be performed, program flow proceeds to step 508. FIG. 12 is a flowchart illustrating step 508 in greater detail. In step 1202, another planar map is generated according to a conventional boundary mapping method.

[0109] Any conventional boundary mapping method may be used in step 1202. For example, an edge proportional boundary mapping method can be used. Edge proportional methods map the surfaces vertices on the surface boundary to the perimeter of a pre-selected geometric shape in proportion to the length of the surface edges forming the surface boundary. Edge proportional methods produce map boundaries which are convex, a property which is particularly useful, for example, when the interpolation is used to correct for a self-crossing map boundary generated in step 502, as will be described below. Convex boundaries, by definition, do not self-cross.

[0110] For purposes of illustration, assume that an edge proportional method is used in step 1202. FIG. 11B depicts an example map boundary generated by applying an edge proportional method to the same 3-D surface used to generate source map boundary 1102. In a preferred embodiment, the pre-selected geometric shape is a rectangle 1112, though other shapes may be used. All of the surface vertices on the surface boundary are mapped onto rectangle 1112. The distance between them, measured along the rectangle perimeter, is proportional to the length of the surface edge connecting the vertices-the resulting map boundary is therefore “edge proportional.”

[0111] These distances are calculated by multiplying the total length of the rectangle perimeter by the length of the surface edge, and dividing that product by the total length of the surface boundary. Once map vertices 1108 are placed, they are connected to form map edges 1110. For example, in FIG. 11B map vertices 1108 are first placed along rectangle 1112, where the distances between map vertices 1108 are calculated as described above. Once map vertices 1108 are placed, map edges 1110 are created in “connect-the-dots” fashion. This map boundary will be referred to as the target map boundary 1104.

[0112] In step 1204, source map boundary 1102 and target map boundary 1104 are interpolated to form a new map boundary. According to a preferred embodiment, the interpolation is computed as follows:

[0113] new_—angle_i=source_—angle_i(1−α)+target_—angle_i*α

[0114] new_—length_i=source_—length_i(1−α)+target_—length_i*α

[0115] The interpolation parameter α controls the relative weight accorded source map boundary 1102 and target map boundary 1104. The source and target map boundaries have the same number of map vertices (and map edges) because they were generated using the 3-D surface and surface boundary. Referring to FIGS. 11A and 11B, source map boundary 1102 has six map vertices 1s to 6s and target map boundary 1104 map vertices 1t to 6t(“s” and “t” designate source and target).

[0116] FIG. 11C depicts an interpolated map boundary 1110, which is interpolation of source map boundary 1102 and target map boundary 1104 according to the formula above. The planar angle at each map vertex on the interpolated map boundary is equal to the weighted average of the planar angles at the corresponding map vertices on the source and target map boundaries, where the relative weighting is determined by interpolation parameter α. For example, the planar angle at map vertex in (new_angle₁) is calculated by multiplying (1−α) times the planar angle at map vertex Is (source_angle₁) and adding a times the planar angle at map vertex It (target_angle₁). Similarly, the length of map edge 1n-2n (new_length₁) is calculated by multiplying (1−α) times the length of map edge 1s-2s (source length₁) and adding a times the length of map edge 1t-2t (target_length₁).

[0117] As shown in FIG. 11C, interpolated map boundary 1106 is no longer a self-crossing boundary. However, this result is not guaranteed in every case, depending on the particular boundaries involved and the value chosen for the interpolation parameter α. If α is chosen such that the source map boundary is too heavily weighted (small α), the resulting interpolated map boundary may still be self-crossing. A non-self-crossing map boundary can eventually be achieved by increasing the value of α, thereby increasing the weight given to the target map boundary.

[0118] The interpolation parameter α is preferably selected by user 102. However, those skilled in the art will recognize that a could be pre-set (ie., 0.5, which accords equal weight to the source and target map boundaries) or chosen automatically based on any one of a variety of criteria.

[0119] This preferred interpolation is easy to implement and requires very little processing time. However, those skilled in the art will recognize that more sophisticated interpolations could be used at the cost of additional complexity and processing time. The fundamental idea remains the same: interpolating a source map boundary generated by an edge-and-angle proportional method with a target map boundary generated by any other conventional method.

[0120] Referring to FIG. 11C, interpolated map boundary 1110 is not closed at map vertex 6n. The preferred interpolation described above does not guarantee that the interpolated map boundary will be closed-in general the interpolated map boundary will not be closed. Therefore, in step 1206 the interpolated map boundary is closed by displacing the map vertices in the same manner as described above with respect to step 706 in FIG. 7.

[0121] Conclusion

[0122] While various embodiments of the present invention have been described above, it should be understood that they have been presented by way of example only, and not limitation. Thus, the breadth and scope of the present invention should not be limited by any of the above-described exemplary embodiments, but should be defined only in accordance with the following claims and their equivalents.

[0123] The previous description of the preferred embodiments is provided to enable any person skilled in the art to make or use the present invention. While the invention has been particularly shown and described with reference to preferred embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the invention.