Constraining user movement in virtual environments

[0001] This application is a continuation-in-part application of pending U.S. patent application Ser. No. 10/021,648 filed on Oct. 30, 2001, which is hereby incorporated by reference in its entirety.

[0002] Computer systems are commonly used to display objects in a virtual environment. The objects may comprise text, still images, video, audio, graphic symbols, icons, any other type of computer-representable items, and/or combinations of any of the foregoing.

[0003] The virtual environment (and the objects therein) may be two-dimensional (e.g., a maze game) or three-dimensional (e.g., a simulation of a city having low-rise homes as well as towering skyscrapers). Depending on the background of the user, three-dimensional applications may be depicted in a series of two-dimensional views. For example, a computer-aided blueprinting application may depict top, side and end views of a three-dimensional building because draftsmen and architects are used to working with those kinds of two-dimensional views. However, for other applications or users, it is inconvenient to use a series of two-dimensional views, and it is preferable to have a three-dimensional view. For example, laymen are generally not accustomed to looking at two-dimensional blueprints, so an architect might prefer to present a design for a home for client approval using a perspective view, while retaining the two-dimensional views for construction purposes.

[0004] Whatever the application, and whether in two or three dimensions, users may have difficulty navigating through the virtual environment. For instance, difficulties may arise due to inexperience with digital navigation tools (e.g., joystick, keyboard, etc.), the user interface, the complexity of the environment, etc. For example, a user may navigate too close to a displayed image to view the entire image, and also thereby lose track of the context and how that particular image fits within the overall environment. Moreover, some or all of a virtual environment may not have been designed to be viewed at near distances (e.g., some parts of the environment may not properly render when viewed too closely).

[0005] In addition, many virtual environments have a number of boundaries that constrain the user's movement. For example, when traversing a maze, the user must navigate between—but cannot cross over—the lines defining the maze. Similarly, a user exploring a virtual house should not be permitted to bump into any of the walls, but should instead move from room to room through virtual doorways.

[0006] Thus, a market exists for a computer-implemented process that provides constraints on the user's movements in virtual environments, whether in two or three dimensions.

[0007] An exemplary method for constraining a user's movement in a virtual environment includes determining a user's current location in the virtual environment, determining a permitted zone based on the current location, dividing an area outside the permitted zone into multiple zones, obtaining an input to move to a new location, calculating a point within the permitted zone proximate to the new location based on one or more of the multiple zones, and moving the user to the proximate point.

[0008] Other embodiments and implementations are also described below.

[0009] FIG. 1 illustrates an exemplary process for constraining a user's movement to a permitted zone in a virtual environment.

[0010] FIG. 2 illustrates an exemplary process for determining a user's new location if the new location is in another permitted zone.

[0011] FIG. 3A illustrates an exemplary partitioned area in a partitioned virtual environment.

[0012] FIG. 3B illustrates an exemplary permitted zone within the partitioned area.

[0013] FIG. 4 illustrates an exemplary division of areas outside of the permitted zone into multiple zones.

[0014] FIG. 5 illustrates an exemplary polygonal permitted zone surrounded by constraint lines.

[0015] FIG. 6 illustrates an exemplary division of zones outside of the polygonal permitted zone.

[0016] FIG. 7 illustrates an exemplary specification of the zones outside of the polygonal permitted zone based on the constraint lines.

[0017] FIG. 8 illustrates an exemplary zone outside of the polygonal permitted zone.

[0018] FIG. 9 illustrates an exemplary rectangular permitted zone surrounded by constraint lines.

[0019] FIG. 10 illustrates an exemplary specification of the zones outside of the rectangular permitted zone based on the constraint lines.

[0020] FIG. 11 illustrates exemplary multiple partitioned areas separated by a passageway.

[0021] FIG. 12 illustrates an exemplary path in an exemplary partitioned area.

[0022] FIG. 13 illustrates an exemplary system and operating environment.

I. Overview

[0023] Section II describes, in a general sense, exemplary processes for constraining a user's movement within a virtual environment.

[0024] Section III describes an exemplary partitioned area in which the user's movement may be constrained, and illustrates more specifically an application of the exemplary process of Section II to determine a permitted zone within the exemplary partitioned area.

[0025] Section IV describes exemplary processes for dividing zones outside of a permitted zone based on constraint lines surrounding the permitted zone.

[0026] Section V describes other exemplary implementations and aspects.

[0027] Section VI describes an exemplary system and operating environment.

II. An Exemplary Process for Constraining a User's Movement within a Virtual Environment

[0028] FIG. 1 illustrates, in a general sense, an exemplary process for constraining a user's movement within a virtual environment that is partitioned into various sub-areas. For example and without limitation, in a simple form of partitioning, the virtual environment might be gridded into rectangular sub-areas having the overall pattern of a checkerboard or tic-tac-toe board. Of course, a virtual environment can be partitioned into sub-areas of any shape, not simply rectangular, and sub-areas may have different shapes. At any given time, the user is located in one of the sub-areas, and the user can move within one of the sub-areas or from one sub-area to another. For continuity with the terminology used in U.S. patent application Ser. No. 10/021,648 from which this patent claims priority, each of the sub-areas into which the domain is partitioned will be referred to hereafter as a “partitioned area.” Some exemplary partitioned areas are illustrated in FIGS. 3A, 3B and 4. These Figures will be referred to in the exemplary process steps described below for clarity purposes. The virtual environment may be a two-dimensional environment or a three-dimensional environment; however, for ease of explanation, the exemplary process will be illustrated in the context of a two-dimensional virtual environment.

[0029] At step 110, a user's current location in a virtual environment is determined. In two dimensions, the user's current location may be indicated by L=(x, y) in the x- and y-coordinate system.

[0030] At step 120, a permitted zone is determined based on the user's current location. In an exemplary implementation, the partitioned area where the user is currently located can be referred to as the “active” area. Within the active area, the permitted zone can be specified by a spacing parameter, p, which is the minimum distance away from one or more walls in the active area. For example, in FIG. 3B, the partitioned area 300 is the active area and the permitted zone 360 within the active area is specified by the parameter p.

[0031] The spacing parameter is not necessarily a constant but can vary as a function of the walls of an active area. For example, a different spacing parameter may be assigned with respect to each wall of an active area. Further, the spacing parameter may also be assigned to zero (which is equivalent to not having a spacing parameter at all). In this implementation, the user may be able to move right up to the edge of a wall or even pass through a wall depending on design choice. The term wall as used herein shall include any types of boundary (visible or transparent) partially or wholly separating one partitioned area from another partitioned area, or restricting the user to a portion of the active area. In general, p can be any predetermined value depending on design choice. In general, the permitted zone is a sub-area within the active area which may be specified by one or more spacing parameters greater than or equal to zero from the wall(s) of the active area.

[0032] At step 130, areas outside of the permitted zone are divided into multiple zones. To give a very simple form of example, if all the partitioned areas are rectangular, then the areas outside the permitted zone could be divided into eight zones surrounding the permitted zone, with each zone corresponding to one of the non-active partitioned areas. The other zones outside the permitted zone extend to infinity (if the virtual environment is unbounded), or to the respective edge(s) of the virtual environment (if it is bounded). For example, in FIG. 4, zone 5 represents the permitted zone and areas outside of zone 5 have been divided into 8 zones surrounding zone 5.

[0033] One skilled in the art will recognize that the partitioned areas can be of other shapes than rectangular. For example, the partitioned areas may be squares, circles, ellipses, ovals, and/or other polygons. In addition, partitioned areas in a virtual environment need not be of the same type of shapes or sizes. In general, the number (and shapes) of zones outside the permitted zone is dependent on the shape of a particular permitted zone. In general, the number of zones outside a permitted zone can be selected based on design choice.

[0034] In an exemplary implementation, the zones outside a polygonal permitted zone can be characterized by constraint lines surrounding the permitted zone. This exemplary implementation will be described in more detail in Section IV below.

[0035] At step 140, a user input to move to a new location in the virtual environment is received. In an exemplary implementation, the input may be a new coordinate value of the new location, relative vector values (e.g., an offset and a direction), and/or other types of input indicative of the new location.

[0036] At step 150, whether the new location is outside the permitted zone is determined.

[0037] At step 160, if the new location is outside the permitted zone, a point within the permitted zone that is proximate to the new location is calculated. Depending on a design choice, a proximate point may be a nearest point from the current location to a boundary, a nearest point from the new location to a boundary, a nearest point from the current location to a boundary while maintaining the direction indicated by the user, or any other point within a permitted zone between the current location and the new location.

[0038] In an exemplary implementation, a proximate point can be efficiently calculated by determining which zone (e.g., the permitted zone or any of the zones surrounding the permitted zone) the new location is located. Based on the determined zone, a reasonable approximation can be made to quickly calculate the edge of the permitted zone where the user should be sent. For example, if the new location is located in the upper left corner zone of a rectangular gridded virtual environment, then the proximate point can be approximated as the point at the lower right corner of the corner zone.

[0039] Alternatively, if the new location is within a side zone (rather than a corner zone), then a line connecting the current location (x_current, y_current) to the new location (x_new, y_new) can be described by the equation (y−y_current)=(y_new−y_current)/(x_new−x_current)*(x−x_current). If the boundary of the permitted zone is characterized as any function y=f(x), then the intersection of the line and the boundary can straightforwardly be calculated since there are two equations and two unknowns. The intersection point (x_intersection, y_intersection) will lie at the boundary of the permitted zone. In a vertical move, one can simply set x_new=x_current and y_new=y_boundary (and in a horizontal move, set y_new=y_current and x_new=x_boundary) to achieve a faster calculation. If the line between the current and new locations is perpendicular to the boundary, the intersection point will be the point on the boundary of the permitted zone that is actually nearest to the new location (as well as the current location). Otherwise, the actual nearest point can be found by simply moving along the boundary until a line between the instantaneous boundary position and the new point is perpendicular to the new location (or the current location). It is not necessary to compute the intersection point in this case.

[0040] If it is desired to maintain the same direction of movement as that originally expected by the user in specifying the new location, the intersection point on the boundary intersecting a line connecting the current location and the new location can be considered as the proximate point (i.e., to a sufficiently good approximation). If it is more important to minimize the distance to the new location, the boundary moving technique of the previous paragraph can be used to obtain the actual nearest point as the proximate point.

[0041] At step 170, the user is moved to the proximate point. In an exemplary implementation, the user can be moved in a straight line path from the current location to the proximate point. In another exemplary implementation, the user can be moved in a zig-zag path, for example, if an impassable obstacle (e.g., wall) is in the way of a straight-line path. The process returns to step 140 for a next input to move.

[0042] Referring back to step 150, if the new location is within the permitted zone, then at step 180, the user is moved to that location based on the input. The process returns to step 140 for a next input to move.

[0043] From time to time, a user's input at step 140 may indicate a new location located in another permitted zone. FIG. 2 illustrates an exemplary process to resolve this situation.

[0044] If it is determined that the new location is located outside the permitted zone at step 150, then at step 210, it is determined whether the new location is located within another permitted zone.

[0045] If the new location is not located within another permitted zone, at step 220, a point within a permitted zone that is proximate to the new location is calculated. For example, the proximate point may be within the permitted zone where the user is currently located; or the proximate point may be within another permitted zone that is closer to the new location but not necessarily in the permitted zone where the user is currently located.

[0046] At step 230, the user is moved to the proximate point. The process returns to step 140 for a next input to move.

[0047] Referring back to step 210, if the new location is within another permitted zone, then at step 240, areas outside the new permitted zone are divided into multiple zones and, at step 180, the user is moved to that location based on the input. In general, steps 180 and 240 may be performed sequentially in any order or simultaneously. The process returns to step 140 for a next input to move.

[0048] The processes illustrated above are merely exemplary. Those skilled in the art will appreciate that other processes and/or steps may be used in accordance with the requirements of a particular implementation.

III. An Exemplary Partitioned Area within which a User's Movement may be Constrained

[0049] The exemplary processes described above in Section II can be more specifically illustrated in an exemplary two-dimensional virtual environment shown in FIGS. 3A-3B and 4.

[0050] FIG. 3A illustrates an exemplary partitioned area 300 in a virtual environment. The partitioned area 300 includes multiple doorways 310a-350a which may lead to other partitioned areas (not shown).

[0051] FIG. 3B illustrates an exemplary permitted zone 360 within the partitioned area 300. In this example, a spacing parameter p (or distance) from each boundary of the permitted zone to the walls of the partitioned area is the same throughout. In addition, FIG. 3B illustrates (smaller) additional permitted zones 310b-350b to provide users with access to the multiple doorways 310a-350a. In an exemplary implementation, the spacing parameter p is set to zero for the additional permitted zones. In other words, users have access up to the boundaries surrounding the additional permitted zones 310a-350a. In another exemplary implementation, one or more spacing parameters (same or different than the spacing parameter(s) for permitted zone 360) may be implemented in one or more additional permitted zones 310a-350a. In one implementation, the additional permitted zones 310b-350b can be treated as other permitted zones (i.e., treated just like the permitted zone 360). Alternatively, the permitted zone 360 and the additional permitted zones 310b-350b may be considered as a single (polygonal) permitted zone.

[0052] FIG. 4 illustrates the exemplary partitioned area 300 of FIG. 3B being divided into nine zones. The permitted zone 360 of FIG. 3B is the middle zone, or zone 5. Zones 1-4 and 6-9 are indicated by dashed lines and each extends to infinity (or at least to the edge of the virtual environment). Three examples are provided below. In each example, a user is currently located in zone 5.

[0053] In a first example, the user inputs a move to P₁ in zone 3. In this example, P₁ is not located in a permitted zone. A possible proximate point to P₁ is the point nearest to zone 5, P₁′, which is approximated as the upper right hand corner point. The user is moved to P₁′ instead of P₁ in zone 3, which is not located in a permitted zone.

[0054] In a second example, the user's input of a new location P₂ is located in additional permitted zone 350b in zone 4. The additional permitted zone 350b is a permitted zone, so the user is moved to P₂ in the additional permitted zone 350b. In an exemplary implementation, areas outside the additional permitted zone 350b can also be divided into multiple zones to facilitate quicker determination of the proper location for the next move.

[0055] In a third example, the user's input of a new location P₃ is located in zone 6, and not within a permitted zone. In this example, a proximate point can be within zone 5 or zone 6, depending on design choice. For example, in a first scenario, the user is moved to a proximate point (e.g., the nearest point) to P₃ in zone 5 (where the user started). In a second scenario, the user is moved to a proximate point (e.g., the nearest point) to P₃ in the additional permitted zone 330b in zone 6. In this scenario, the additional permitted zone 330b becomes the current permitted zone and all areas outside of the additional permitted zone 330b can be divided into multiple zones to facilitate quicker determination of the proper location for the next move.

[0056] By dividing the areas outside a permitted zone (where the user is currently located), one can efficiently and quickly determine a proximate point between a new location and the (or another) permitted zone and move the user accordingly.

IV. Exemplary Processes for Dividing Zones Based on Constraint Lines Surrounding a Permitted Zone

[0057] In an exemplary implementation, zones can be characterized based on constraint lines surrounding a polygonal permitted zone. This is particularly useful for representing the zones in a manner that can be readily stored and manipulated by a computer.

[0058] FIG. 5 illustrates an exemplary polygonal permitted zone 500 in a two-dimensional virtual environment having a generalized u,v coordinate system. The polygonal permitted zone 500 is characterized by constraint lines I-V. Each constraint line I-V separates two half planes. Each constraint line can be characterized as: a_ku+b_kv+c_k=0 in the generalized u,v coordinate system. The half planes separated by each constraint line can either be characterized as a_ku+b_kv+c_k>0 (positive half plane) or a_ku+b_kv+c_k<0 (negative half plane). As a matter of convenience in this exemplary embodiment, the half plane outside the polygonal permitted zone 500 will be referred to as the “negative” half plane.

[0059] FIG. 6 illustrates exemplary zones 1-11 characterizable by the constraint lines I-V (corresponding to k=1 to 5, respectively). In this example, the permitted zone 500 is zone 11. Each zone in FIG. 6 can be characterized by overlapping half planes as shown in the table illustrated in FIG. 7.

[0060] In an exemplary implementation, the table in FIG. 7 may be used to quickly deduce the zone in which a given point (u, v) is located. For example, if one determines that (u, v) is located in the positive half plane of constraint line I, then one can eliminate zones 1 to 3, and so forth. The table in FIG. 7 is merely exemplary. One skilled in the art will recognize that, depending on design choice, other calculations can be implemented to quickly determine a zone at least partially bounded by constraint lines.

[0061] In FIG. 8, constraint lines I and III can be characterized by a₁u+b₁v+c₁=0 and a₃u+b₃v+C₃=0, respectively. In this example, zone 3 is the area of overlap between negative half planes a₁u+b₁v+c₁<0 and a₃u+b₃v+C₃<0. Similarly, zone 1 can be characterized by the negative half planes of constraint lines I and II, and zone 2 can be characterized by the negative half plane of constraint line I, and positive half planes of constraint lines II and III.

[0062] Thus, the zone in which a new location is located can be ascertained based on the constraint lines surrounding a permitted zone (e.g., evaluating the sign of a_ku+b_kv+c_k for each relevant constraint line k and determining the zone from FIG. 7). After determining the zone of a new location, a proximate point to the new location can be quickly determined by applying the techniques described in Section III above.

[0063] The foregoing describes a generalized process for characterizing polygonal zones in a virtual environment. A rectangular permitted zone (having rectangular surrounding zones) can alternatively be calculated by a simpler technique. FIG. 9 illustrates an exemplary rectangular permitted zone (zone 5) surrounded by four constraint lines I-IV that may extend to the boundaries of the virtual environment. In a x,y coordinate system, constraint lines I and II have constant x values of A and B, respectively, and constraint lines III and IV have constant y values of C and D, respectively. Zones 1-9 can be readily characterized based on these constraint lines. Any point within a given zone will have an identifiable relationship with respect to the constant x, y values of the constraint lines for that zone. For example, any point having a value of x greater than A and less than B, and a value of y greater than C and less than D, must be in zone 5. FIG. 10 illustrates an exemplary table characterizing each zone based on its relationship to the constant values (of that zone's constraint lines).

[0064] Referring back to FIG. 9, upon determining a zone where the new location (x₂, y₂) is located and knowing where the current location (x₁, y₁) is located, one can determine a proximate point (e.g., (x,y)) very quickly. For example, a direction maintaining proximate point may be determined by solving the following equation: y−y₁=(y₂−y₁)/(x₂−x₁))*(x−x₁), where either x or y in this case is a known constant value determined by the boundary type (e.g., x=constant for a vertical boundary and y=constant for a horizontal boundary). In this example, the proximate point (x,y) is the intersection point on the boundary of zones 2 and 5 where y=D. A person skilled in the art will recognize that this proximate point is merely exemplary. Other types of proximate points (e.g., the nearest point to the new location, the nearest point to the old location, etc.) may alternatively be implemented in accordance with design choice.

V. Other Exemplary Implementations and Aspects

[0065] 1. Two or More Partitioned Areas Connected by Passageways

[0066] In a typical virtual environment, multiple partitioned areas are interconnected. For example, multiple partitioned areas may be interconnected by openings (e.g., doors) or passageways (e.g., hallways).

[0067] FIG. 11 illustrates two partitioned areas 1110 and 1120 being interconnected by a passageway 1130. In an exemplary implementation, each partitioned area 1110, 1120 includes a primary permitted zone 1140, 1160, respectively. In addition, each partitioned area 1110, 1120 may include one or more additional permitted zones 1170, 1180 to enable users to go through doorways (not shown).

[0068] Depending on the size of a passageway, a spacing parameter p may be set to a non-zero value or to a zero value (i.e., equivalent to not having a spacing parameter). For example, if a passageway is narrow, it may not be practical to limit the user's movement within the passageway. However, if a passageway is being used to display images of objects, a spacing parameter (albeit a small one) may be implemented to prevent the user from getting too close to the images.

[0069] In FIG. 11, if a user's current position is in the passageway 1130, the passageway 1130 is the permitted zone and all areas outside the passageway 1130 can be divided into multiple zones as described in various implementations herein.

[0070] 2. Creating a Path in a Partitioned Area

[0071] Permitted zones may also be linked together to create a path in a partitioned area.

[0072] FIG. 12 illustrates an exemplary partitioned area 1200 having multiple permitted zones 1210-1250 within the area.

[0073] In an exemplary implementation, each permitted zone can be implemented by selecting appropriate spacing parameter(s) for that zone. For example, permitted zone 1210 has the following spacing parameters for each of its four boundaries: upper boundary, p=0; lower boundary, p=8; right boundary, p=6.5; left boundary, p=4.

[0074] This implementation can be used, for example, to constrain a user to a guided tour through a partitioned area.

[0075] 3. Application in a Three-Dimensional Virtual Environment

[0076] The various exemplary implementations described herein are generally described in the context of two-dimensional space. One skilled in the art will readily appreciate that the exemplary implementations can be adapted to be applied to constrain user movements in three-dimensional space in which each permitted zone is a three-dimensional volume.

[0077] For example, in the case of a rectangular permitted zone, instead of dividing the virtual environment into nine zones in two-dimensional space (8 outer zones surrounding a central permitted zone), one could divide the virtual environment into 27 zones in three-dimensional space (26 outer zones surrounding a central permitted zone). In an exemplary implementation, the zones can be characterized by constraint planes (a more generalized form of intersection by constraint lines) in the three-dimensional space. Based on these zones, one can efficiently determine where and how to move the user (e.g., by determining the nearest point to the new location within a permitted zone).

VI. An Exemplary System and Operating Environment

[0078] FIG. 13 illustrates an exemplary system for generating virtual environments in which exemplary implementations described herein may be applied. The exemplary system 1300 including a graphics processing unit 1310, a rendering engine 1320, a user output interface 1330, a user input interface 1340, and memory 1350. The graphics processing unit 1310 functions to receive object data 10A and generate two- and/or three-dimensional imaging data 10B corresponding to the specified type of virtual environment using techniques that are well known in the field of graphics imaging. Rendering engine 1320 receives imaging data 10B and generates rendering data 11A outputted through user output interface 1330. For instance, rendering data 11A might be configured for a monitor (not shown) or other form of output device to display the three-dimensional virtual environment including the representative images. User input interface 1340 might include computer-implemented hardware and/or software that allows a user to interact with the three-dimensional environment. For instance, the user input interface 1340 might allow the user to navigate through and view the three-dimensional environment by moving a displayed cursor using a user input device (e.g., a keyboard, a mouse, a joystick, a pressure sensitive screen, etc.). Graphics processing unit 1310 may function to generate the representative images of the data objects or the representative image data may be stored within the memory 1350 and linked to a data object database.

[0079] The embodiments described herein may be implemented in an operating environment, such as the system 100, comprising software installed on a computer, in hardware, or in a combination of software and hardware.

[0080] The software and/or hardware would typically include some type of computer-readable media which can store data and logic instructions (such as those which, when executed, authenticates a user having a biometric authentication datum using a pass code) that are accessible by the computer or the processing logic within the hardware. Such media might include, without limitation, hard disks, floppy disks, flash memory cards, digital video disks, random access memories (RAMs), read only memories (ROMs), and the like.

VII. Conclusion

[0081] The foregoing examples illustrate certain exemplary embodiments from which other embodiments, variations, and modifications will be apparent to those skilled in the art. The inventions should therefore not be limited to the particular embodiments discussed above, but rather are defined by the claims. Furthermore, some of the claims may include alphanumeric identifiers to distinguish the elements thereof. Such identifiers are merely provided for convenience in reading, and should not necessarily be construed as requiring or implying a particular order of steps, or a particular sequential relationship among the claim elements.