Method of and system for preventing wall hacking in video games by using ray tracing to filter outgoing data packets
11771997 · 2023-10-03
Assignee
Inventors
Cpc classification
A63F13/75
HUMAN NECESSITIES
A63F13/31
HUMAN NECESSITIES
A63F2300/5586
HUMAN NECESSITIES
A63F2300/5533
HUMAN NECESSITIES
International classification
Abstract
There is provided a method and a system for preventing wall-hacking by using server side ray tracing to filter data packets to be provided to user devices during a multiplayer video gaming session. Map information and player updates indicative of player actions are received, and an acceleration structure is generated. Primary rays from the virtual frustum associated with players are generated and intersections between rays and players geometries on the map are determined based on the acceleration structure. The visibility matrix is generated based on the determined intersections. The visibility matrix includes pair wise visibility information between each player. Data packets provided to each user device are then filtered based on the visibility matrix.
Claims
1. A method for preventing wall hacking by using ray tracing to filter data packets to be provided to a plurality of user devices during a video gaming session, each respective user device being associated with a respective player having a respective player geometry in the gaming session, the method being executed by at least one processing device, the at least one processing device being connected to the plurality of user devices, the method comprising: receiving map information for the gaming session; for a given iteration of a plurality of iterations during the gaming session: receiving player updates indicative of actions of the respective players on the map, the player updates including respective virtual frustum information for each player; generating an acceleration structure using the map information and the player updates; generating, for each player, respective primary rays from the respective virtual frustum associated with the player; determining, for each player, based on the respective primary rays and the acceleration structure, intersections between the respective primary rays and the respective player geometries on the map; generating a visibility matrix based on at least the determined intersections, the visibility matrix comprising pair-wise visibility between the respective players on the map; receiving outgoing data packets representative of player states on the map for the given iteration; filtering the outgoing data packets based on the visibility matrix to obtain respective filtered data packets for each player; and transmitting the respective filtered data packets to each of the plurality of user devices.
2. The method of claim 1, wherein said generating the acceleration structure comprises: generating a plurality of bottom-level acceleration structures based on map geometry instances in the map information and the respective player geometry; and combining the plurality of bottom-level acceleration structures to obtain a top-level acceleration structure to be used for determining intersection between the respective primary rays and the respective player geometries on the map.
3. The method of claim 1, wherein said method further comprises, prior to said generating, the acceleration structure using the map information and the player updates: receiving current vantage point data; receiving future vantage point data; and generating, for each player, using the current vantage point data and future vantage point data, a collated player geometry associated with the respective player; and wherein said generating the acceleration structure comprises further using collated player geometry.
4. The method of claim 1, receiving current vantage point data; receiving future vantage point data; and generate, for each of the respective virtual frustum associated with the player, a respective plurality of virtual frusta using the current vantage point data and future vantage point data from which the respective primary rays are launched.
5. The method of claim 1, receiving a set of force-casters and associated bounding spheres; determining if a given force-caster of the set of force-casters overlaps with a given primary ray; and in response to the given force-caster of the set of force-casters overlapping with the primary ray: launching further primary rays.
6. The method of claim 1, wherein said method further comprises, prior to generating said visibility matrix: determining intersections between the respective rays and players on the map; involving a given light source; storing an indication of players having intersected rays having reached the given light source in association with the respective player having launched the primary rays; and wherein said generating the visibility matrix comprises using the stored indications of players.
7. The method of claim 3, further comprising, prior to said generating the visibility matrix: receiving a respective ping associated with each player; in response to the ping associated with at least one given player being above a predetermined threshold: determining respective origins for each of a plurality of virtual sub-frusta obtained for the respective virtual frustum for each respective player; clipping the respective origins against the map; determining respective threshold distances from a center of a geometry of each respective player, the respective threshold distances being proportional to the geometry of the respective player; generating, based on the respective threshold distances, at least one bottom level acceleration structure for each respective player; and generating, using the generated bottom level acceleration structures, a top level acceleration structure for the at least one given player, the top level acceleration structure to be used for determining intersecting primary rays of the at least one given player originating from at least the respective clipped origins.
8. The method of claim 6, wherein said player geometries comprise player armatures; wherein said generating, for each player, respective primary rays from the respective virtual frustum associated with the player comprises: determining respective difference vectors between each originating player and a centroid of each remaining player armature; determining if lengths of the respective difference vectors are above a predetermined threshold, the predetermined threshold being based on the respective player armature; determining, for the respective difference vector lengths with lengths above the threshold, an angle based on the respective difference vectors and the respective primary rays; and in response to the angle being below a threshold, redirect the primary rays towards the player armatures to be used for determining further intersections for generating the visibility matrix.
9. The method of claim 6, wherein said player geometries comprise bounding boxes; and wherein said generating, for each player, respective primary rays from the respective virtual frustum associated with the player comprises: determining respective difference vectors between each originating player and a centroid of each remaining player bounding box; determining if lengths of the respective difference vectors are above a predetermined threshold, the predetermined threshold being based on respective the bounding box; determining, for respective difference vectors with lengths above the threshold, an angle based on the respective difference vectors and the respective primary rays; and in response to the angle being below a threshold, launch further primary rays to be used for determining further intersections for generating the visibility matrix.
10. A method for determining pair-wise visibility between players during a video game session by using ray-tracing, each player having a respective player geometry, the method being executed by at least one processing device, the method comprising: receiving map information for the gaming session; for a given iteration of a plurality of iterations during the gaming session: receiving player updates indicative of actions of the respective players on the map, the player updates including respective virtual frustum information for each player; generating an acceleration structure using the map information and the player updates; generating, for each player, respective primary rays from the respective virtual frustum associated with the player; determining, for each player, based on the respective primary rays and the acceleration structure, intersections between the respective primary rays and the respective player geometries on the map; and generating a visibility matrix based on at least the determined intersections, the visibility matrix comprising pair-wise visibility between the respective players on the map.
11. A system for preventing wall hacking by using ray tracing to filter data packets to be provided to a plurality of user devices connected to the system during a video gaming session, each respective user device being associated with a respective player having a respective player geometry, the system comprising: a non-transitory storage medium comprising computer-readable instructions; and at least one processing device operatively connected to the non-transitory storage medium; the at least one processing device, upon executing the computer-readable instructions, being configured for: receiving map information for the gaming session; for a given iteration of a plurality of iterations during the gaming session: receiving player updates indicative of actions of the respective players on the map, the player updates including respective virtual frustum information for each player; generating an acceleration structure using the map information and the player updates; generating, for each player, respective primary rays from the respective virtual frustum associated with the player; determining, for each player, based on the respective primary rays and the acceleration structure, intersections between the respective primary rays and the respective player geometries on the map; generating a visibility matrix based on at least the determined intersections, the visibility matrix comprising pair-wise visibility between the respective players on the map; receiving outgoing data packets representative of player states on the map for the given iteration; filtering the outgoing data packets based on the visibility matrix to obtain respective filtered data packets for each player; and transmitting the respective filtered data packets to each of the plurality of user devices.
12. The system of claim 11, wherein said generating the acceleration structure comprises: generating a plurality of bottom-level acceleration structures based on map geometry instances in the map information and the respective player geometry; and combining the plurality of bottom-level acceleration structures to obtain a top-level acceleration structure to be used for determining intersection between the respective primary rays and the respective player geometries on the map.
13. The system of claim 11, wherein said at least one processing device is further configured for, prior to said generating the acceleration structure using the map information and the player updates: receiving current vantage point data; receiving future vantage point data; generating, for each player, using the current vantage point data and future vantage point data, a collated player geometry associated with the respective player; and wherein said generating the acceleration structure comprises further using collated player geometry.
14. The system of claim 11, receiving current vantage point data; receiving future vantage point data; and generate, for each of the respective virtual frustum associated with the player, a respective plurality of virtual frusta using the current vantage point data and future vantage point data from which the respective primary rays are launched.
15. The system of claim 11, receiving a set of force-casters and associated bounding spheres; determining if a given force-caster of the set of force-casters overlaps with a given primary ray in response to the given force-caster of the set of force-casters overlapping with the primary ray: launching further primary rays.
16. The system of claim 11, wherein said at least one processing device is further configured for, prior to generating said visibility matrix: determining intersections between the respective rays and players on the map; involving a given light source; storing an indication of players having intersected rays having reached the given light source in association with the respective player having launched the primary rays; and wherein said generating the visibility matrix comprises using the stored indications of players.
17. The system of claim 12, further comprising, prior to said generating the visibility matrix: receiving a respective ping associated with each player; in response to the ping associated with at least one given player being above a predetermined threshold: determining respective origins for each of a plurality of virtual sub-frusta obtained for the respective virtual frustum for each respective player; clipping the respective origins against the map; determining respective threshold distances from a center of a geometry of each respective player, the respective threshold distances being proportional to the geometry of the respective player; generating, based on the respective threshold distances, at least one bottom level acceleration structure for each respective player; and generating, using the generated bottom level acceleration structures, a top-level acceleration structure for the at least one given player, the top-level acceleration structure to be used for determining intersecting primary rays of the at least one given player originating from at least the respective clipped origins.
18. The system of claim 16, wherein said player geometries comprise player armatures; wherein said generating, for each player, respective primary rays from the respective virtual frustum associated with the player comprises: determining respective difference vectors between each originating player and a centroid of each remaining player armature; determining if lengths of the respective difference vectors are above a predetermined threshold, the predetermined threshold being based on the respective player armature; determining, for the respective difference vector lengths with lengths above the threshold, an angle based on the respective difference vectors and the respective primary rays; and in response to the angle being below a threshold, redirect the primary rays towards the player armatures to be used for determining further intersections for generating the visibility matrix.
19. The system of claim 18, wherein said player geometries comprise bounding boxes; and wherein said generating, for each player, respective primary rays from the respective virtual frustum associated with the player comprises: determining respective difference vectors between each originating player and a centroid of each remaining player bounding box; determining if lengths of the respective difference vectors are above a predetermined threshold, the predetermined threshold being based on respective the bounding box; determining, for respective difference vectors with lengths above the threshold, an angle based on the respective difference vectors and the respective primary rays; and in response to the angle being below a threshold, launch further primary rays to be used for determining further intersections for generating the visibility matrix.
20. The system of claim 11, wherein said at least one processing device comprises a graphics processing unit (GPU).
Description
BRIEF DESCRIPTION OF THE DRAWINGS
(1) For a better understanding of the present technology, as well as other aspects and further features thereof, reference is made to the following description which is to be used in conjunction with the accompanying drawings, where:
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
(13)
(14)
(15)
(16)
(17)
(18)
(19)
(20)
(21)
(22)
(23)
(24)
(25)
(26)
(27)
(28)
DETAILED DESCRIPTION
(29) The examples and conditional language recited herein are principally intended to aid the reader in understanding the principles of the present technology and not to limit its scope to such specifically recited examples and conditions. It will be appreciated that those skilled in the art may devise various arrangements which, although not explicitly described or shown herein, nonetheless embody the principles of the present technology and are included within its spirit and scope.
(30) Furthermore, as an aid to understanding, the following description may describe relatively simplified implementations of the present technology. As persons skilled in the art would understand, various implementations of the present technology may be of a greater complexity.
(31) In some cases, what are believed to be helpful examples of modifications to the present technology may also be set forth. This is done merely as an aid to understanding, and, again, not to define the scope or set forth the bounds of the present technology. These modifications are not an exhaustive list, and a person skilled in the art may make other modifications while nonetheless remaining within the scope of the present technology. Further, where no examples of modifications have been set forth, it should not be interpreted that no modifications are possible and/or that what is described is the sole manner of implementing that element of the present technology.
(32) Moreover, all statements herein reciting principles, aspects, and implementations of the present technology, as well as specific examples thereof, are intended to encompass both structural and functional equivalents thereof, whether they are currently known or developed in the future. Thus, for example, it will be appreciated by those skilled in the art that any block diagrams herein represent conceptual views of illustrative circuitry embodying the principles of the present technology. Similarly, it will be appreciated that any flowcharts, flow diagrams, state transition diagrams, pseudo-code, and the like represent various processes which may be substantially represented in computer-readable media and so executed by a computer or processor, whether or not such computer or processor is explicitly shown.
(33) The functions of the various elements shown in the figures, including any functional block labeled as a “processor” or a “graphics processing unit”, may be provided through the use of dedicated hardware as well as hardware capable of executing software in association with appropriate software. When provided by a processor, the functions may be provided by a single dedicated processor, by a single shared processor, or by a plurality of individual processors, some of which may be shared. In one or more non-limiting embodiments of the present technology, the processor may be a general purpose processor, such as a central processing unit (CPU) or a processor dedicated to a specific purpose, such as a graphics processing unit (GPU). Moreover, explicit use of the term “processor” or “controller” should not be construed to refer exclusively to hardware capable of executing software, and may implicitly include, without limitation, digital signal processor (DSP) hardware, network processor, application specific integrated circuit (ASIC), field programmable gate array (FPGA), read-only memory (ROM) for storing software, random access memory (RAM), and non-volatile storage. Other hardware, conventional and/or custom, may also be included.
(34) Software modules, or simply modules which are implied to be software, may be represented herein as any combination of flowchart elements or other elements indicating performance of process steps and/or textual description. Such modules may be executed by hardware that is expressly or implicitly shown.
(35) With these fundamentals in place, we will now consider some non-limiting examples to illustrate various implementations of aspects of the present technology.
Electronic Device
(36) Referring to
(37) A Graphics Processing Unit or a GPU is an electronic hardware unit designed to provide visuals for computers. It can either be a separate piece of hardware installable on a motherboard, integrated into a motherboard or provided alongside a CPU on the same chip. Modern GPUs are backed by massively parallel processors capable of intensive mathematical computations.
(38) Communication between the various components of the electronic device 100 may be enabled by one or more internal and/or external buses 160 (e.g. a PCI bus, universal serial bus, IEEE 1394 “Firewire” bus, SCSI bus, Serial-ATA bus, etc.), to which the various hardware components are electronically coupled.
(39) The input/output interface 150 may be coupled to a touchscreen 190 and/or to the one or more internal and/or external buses 160. The touchscreen 190 may be part of the display. In one or more embodiments, the touchscreen 190 is the display. The touchscreen 190 may equally be referred to as a screen 190. In the embodiments illustrated in
(40) According to implementations of the present technology, the solid-state drive 120 stores program instructions suitable for being loaded into the random-access memory 130 and executed by the processor 110 and/or the GPU 111 for preventing wall hacking in video games by using server-side ray tracing. For example, the program instructions may be part of a library or an application.
(41) The electronic device 100 may be implemented as a server, a desktop computer, a laptop computer, a tablet, a smartphone, a personal digital assistant or any device that may be configured to implement the present technology, as it may be understood by a person skilled in the art.
System
(42) Referring to
(43) The system 200 comprises inter alia a plurality of client devices 210, a game server 250, and a database 240 communicatively coupled over a communications network 270.
Client Device
(44) The system 200 comprises the plurality of client devices 210 or plurality of user devices 210. The plurality of client devices 210 are associated with a plurality of users 205, respectively.
(45) As depicted in
(46) As such, each of the client devices 212, 214, 216 can sometimes be referred to as a “electronic device”, “user device”, “end user device” or “client electronic device”.
(47) Each of the client devices 210 comprises one or more components of the electronic device 100 such as the processor 110, the graphics processing unit (GPU) 111, the solid-state drive 120, the random access memory 130, the display interface 140, and the input/output interface 150.
(48) It will be appreciated that in some embodiments, each client device 212, 214, 216 may be implemented differently.
(49) Each of the plurality of client devices 210 is configured to execute a game client application 230 (not separately numbered).
(50) Game client application 230 may be specific to a game or may be used to host multiple different games, with video for a game being presented using a display of the client device 212, 214, 216 and interacted with using input/output interfaces of the client device 212, 214, 216. In at least one embodiment, game data may also be stored locally to a database (not shown) or persistent storage device on that client device 212, 214, 216. In at least one embodiment, a processing device of the client device 212, 214, 216 is a central processing unit (CPU). In at least one embodiment, the client device 212, 214, 216 may also utilize one or more graphics processing units (GPUs) for executing game code.
(51) Game client application 230 may be obtained over a network, and/or through any of variety of other mechanisms including, but not limited to a portable computer readable storage medium, such as a portable memory device, a DVD, or the like.
(52) The users 202, 204, 206 use respective client devices 212, 214, 216 to execute game client application 230 and interact in an environment together during a gaming session by transmitting and receiving data from the game server 250 and/or to each other.
(53) Each of the users 202, 204, 206 can provide input to the respective client devices 212, 214, 216. The input can be or include, for example, a tap or swipe on a touch screen, a point and click with a mouse, and/or one or more entries on a keyboard.
(54) Data corresponding to the input is transmitted from the user interface of the client device 212, 214, 216 along a path to the game event procedure executed by the game server 250 which determines and/or manages game events for the game based on the user input. The game events are generally actions or movements taken by a player or a player's character or avatar in the virtual environment for the online game.
(55) During a given gaming session executed by the game client application 230, each user 202, 204, 206 is associated with a respective character in the multiplayer game that interacts in a virtual environment. The virtual environment may for example include a map.
(56) As such, the user 202, 204, 206 controlling its respective associated character via the respective client device 212, 214, 216 may be referred to as respective player 212, 214, 216. Each player 212, 214, 216 is associated with identifier.
(57) It will be appreciated that the nature of the character, attributes and possible actions depend on the game provided by the game client application 230 and the game server 250.
(58) As a non-limiting example, the game client application 230 and the game server 250 may provide a third person shooter and/or a first person shooter game.
(59) Non-limiting examples of multiplayer video games include the Call of Duty franchise, the Counter Strike franchise, the Quake franchise, Halo franchise and the like.
Game Server
(60) The game server 250 is configured to inter alia: (i) host an online gaming environment accessible by the plurality of client devices 210 via the game client application 230; (ii) provide online gaming sessions in virtual environments for interaction by the plurality of client devices 210 by executing a game event procedure; (iii) connect to API 235 executing a visibility determination procedure 310; (iv) receive user inputs in the virtual gaming environment from the plurality of client devices 210; (v) process the user inputs in the virtual gaming environment; (vi) update the online game state based on at least the processed user inputs; (vii) perform a visibility determination procedure 310 using the API 235; (viii) filter outgoing data packets using a data filtering procedure 300 based on the outcome of the visibility determination procedure 310; and (ix) provide filtered data packets including updated game states to the client devices 210.
(61) It will be appreciated that (ii)-(ix) may be executed a plurality of times, sequentially, in parallel or a combination thereof.
(62) The game server 250 is an authoritative source of events in the game—it receives and processes player data, while also transmitting game play data to allow connected plurality of client devices 210 to maintain their own versions of the game world for display in the game client application 230.
(63) In some embodiments, the game server 250 may be hosted or implemented locally, remotely, centrally, distributively, in the cloud, or in any other manner that provides the data communication infrastructure needed for online gaming with the plurality of client devices 210. As such, the game server 250 may also represent a tournament server or an eSport server, which may contain additional modules or components to support competitive gaming broadcast, streaming, and processing.
(64) The game server 250 is configured to perform filtering of data packets to be provided to the plurality of client devices 210 by executing the data filtering procedure 300 so as to prevent wall hacking in the video game. To achieve that purpose, the game server 250 connects to the API 235 to perform a visibility determination procedure 310, and uses the output of the visibility determination procedure 310 to perform filtering of packets by executing the data filtering procedure 300.
(65) The game server 250 has components that are sufficient to execute visibility determination procedure 310 as fast as the time it takes to render one frame of the game state for each client device 212, 214, 216.
(66) As a non-limiting example, a game server 250 with sufficient capabilities to implement one of NVIDIA OptiX™ Ray Tracing Engine, real-time rendering pipelines that voxelize the scene for the purpose of tracing rays crudely, (signed) distance fields (SDFs), and other geometric primitives may be sufficient to perform the visibility determination procedure 310 as will be described herein.
(67) As a non-limiting example, a game server 250 may have as a GPU a RTX 2070 SUPER from NVIDIA to host a single CS:GO gaming session including 10 players at 128 tics.
(68) How the game server 250 is configured to do so will be explained in more detail herein below.
(69) It will be appreciated that the game server 250 can be implemented as a conventional computer server and may comprise at least some of the features of the electronic device 100 shown in
(70) In some embodiments of the present technology, at least one of the components may be provided with encryption using any of a variety of encryption mechanisms. In one or more other embodiments, no components may be provided with encryption.
(71) The implementation of the game server 250 is well known to the person skilled in the art. However, the game server 250 comprises a communication interface (not shown) configured to communicate with various entities (such as the database 240, for example and other devices potentially coupled to the communication network 270) via the communication network 270. The game server 250 further comprises at least one computer processor (e.g., the processor 110 of the electronic device 100) operationally connected with the communication interface and structured and configured to execute various processes to be described herein.
Database
(72) A database 240 is directly coupled to the game server 250. In one or more alternative implementations, the database 240 may be communicatively coupled to the game server 250 over the communication network 270 without departing from the teachings of the present technology. In one or more other embodiments, the database 240 may be optional. Although the database 240 is illustrated schematically herein as a single entity, it will be appreciated that the database 240 may be configured in a distributed manner, for example, the database 240 may have different components, each component being configured for a particular kind of retrieval therefrom or storage therein.
(73) The database 240 may be a structured collection of data, irrespective of its particular structure or the computer hardware on which data is stored, implemented or otherwise rendered available for use. The database 240 may reside on the same hardware as a process that stores or makes use of the information stored in the database 240 or it may reside on separate hardware, such as on the game server 250. The database 240 may receive data from the game server 250 for storage thereof and may provide stored data to the game server 250 for use thereof.
(74) In the context of the present technology, the database 240 is configured to store inter alia game information, player information and/or network information or any other type of information related to the processes described herein. In some embodiments, visibility determination results from data filtering procedure 300 may be stored for future analysis.
Communication Network
(75) In one or more embodiments of the present technology, the communications network 270 is the Internet. In one or more alternative non-limiting embodiments, the communication network 270 may be implemented as any suitable local area network (LAN), wide area network (WAN), a private communication network or a combination thereof. It will be appreciated that implementations for the communication network 270 are for illustration purposes only. How a communication link 275 (not separately numbered) between the client device 210, the game server 250, the database 240, and/or another electronic device (not shown) and the communications network 270 is implemented will depend inter alia on how each electronic device is implemented.
Data Filtering Procedure
(76) The game server 250 is configured to execute the data filtering procedure 300 via the API 235. The purpose of the data filtering procedure 300 is to filter outgoing data packets to be transmitted to each of the plurality of client devices 210 during a multiplayer gaming session so as to prevent wall-hacking.
(77) As such, the data filtering procedure 300 is configured to inter alia: (i) receive outgoing data packets including updated game states; (ii) execute the visibility determination procedure 310 to obtain pair-wise visibility information of the plurality of users 205; and (iii) filter the outgoing data packets using the pair-wise visibility information to obtain filtered packets for each client device 212, 214, 216; and (iv) transmit the filtered data packets to each client device 212, 214, 216.
(78) The data filtering procedure 300 further enables saving bandwidth by limiting data that is transmitted from the game to the client devices to only what is required for the users to play the game
(79) The data filtering procedure 300 starts off by launching an instance of a graphics API. The data filtering procedure 300 executes a headless instance, i.e., an instance without a graphical user interface (GUI). It will be appreciated that the instance may not be headless if the data filtering procedure 300 is launched with a debugging view. For example, if an operator of a game server uses a debugging view for debugging the present API 235, the instance will not be headless.
(80) The API 235 launches the visibility determination procedure 310 in a separate thread which awaits feeding of samplers, material and map geometry instance information. It may be appreciated that procedure 300, the API 235 and visibility determination procedures 310 may not be threaded but embedded within and executed from the same thread as the game server 250.
(81) How the visibility determination procedure 310 is executed will now be explained with reference to
Visibility Determination Procedure
(82) The visibility determination procedure 310 is configured to determine pair-wise visibility information of the plurality of users 205 during one or more frames of a multiplayer gaming session.
(83) In the context of the visibility determination procedure 310, the pair-wise visibility information between players is stored in a data structure which will be referred to as visibility matrix hereinafter. The visibility matrix is a square matrix representing the visibility of each player against every other player during the gaming session, as computed using the procedures described hereinafter. The visibility matrix is populated by using ray tracing techniques on the server side such that each client device 212, 214, 216 participating in the gaming session receives, from the gaming server 250, data packets that have been filtered using the visibility matrix, thus preventing the use of world hacking and wall hacking techniques that enable cheaters to see players that would be otherwise not visible in the environment or map (i.e., as intented by the video game operator or provider) due to objects or other types of opaque obstacles in the map.
(84) Each player is associated with a respective player geometry surrounding its character.
(85) The player geometry may include one of a bounding box and an armature. It will be appreciated that the type of player geometry depends on the type of game. The bounding box is a cuboid surrounding the respective player. The armature is a geometry surrounding the respective player.
(86) In the visibility matrix, all player IDs are labelled on both the rows and the columns. Each cell within the visibility matrix contains a configurable number of Boolean flags that collectively indicate whether the player ID on the column can see the player ID indicated on the row. Each Boolean flag represents the player visibility in a different frame. Any bits within a cell being one represents a transmit decision on the server's part. Only a cell of all zeroes prevents a packet transmit decision.
(87) Reference is now made to
(88) In the non-limiting example illustrated in
(89) The scene 500 comprises four players located at respective positions: a first player 502, a second player 506, a third player 510 and a fourth player 514. The scene 500 depicts a first frame in a first moment in time, which corresponds to the first digit in each cell of the visibility matrix 520. The visibility determination of one player against another player is an evaluation of whether any flags within a cell are equal to one. Given that the Boolean flags are stored in individual bits in memory, this temporal visibility determination simply reduces to vector comparisons aided by SIMD units inside the CPU arithmetic and logic units.
(90) The first player 502 casts rays from the first virtual frustum 504. It can be seen that the third player 510 and the fourth player 514 are within the casted rays of the first virtual frustum 504. The second player 506 is not within the casted rays of the first virtual frustum 504. This is reflected in the first column of the visibility matrix 520 shown in
(91) The second player 506 casts rays from the second virtual frustum 508. It can be seen that a portion of the third player 510 and the fourth player 514 are within the casted rays of the second virtual frustum 508. The first player 504 is not within the casted rays of the second virtual frustum 508. This is reflected in the second column of the visibility matrix 520 shown in
(92) The third player 510 casts rays from the third virtual frustum 512. It can be seen that the first player 504 and the second player 506 are within the casted rays of the second virtual frustum 508. The fourth player 514 is not within the casted rays of the third virtual frustum 512. This is reflected in the third column of the visibility matrix 520 shown in
(93) The fourth player 514 casts rays from the fourth virtual frustum 516. It can be seen that a portion of each of the first player 502, the second player 506 and the third player 510 are within the casted rays of the second virtual frustum 508. This is reflected in the fourth column of the visibility matrix 520 shown in
(94) In some embodiments, each cell holds more than one flag because visibility determination for frames independent of each other may not be taken into account and a limited history of visibility may be taken into account. It will be appreciated that visibility is unidirectional: player 1 seeing player 2 does not guarantee that player 2 is in fact capable of seeing player 1. A frame counter is used and monotonically increases by one with every passing frame. The modulus of the frame counter with the number of Booleans that fit in a single cell determines which flag in every cell will be evaluated at any given frame. Beginning with every frame, flags associated with that frame in each cell are reset to zero indicating a lack of visibility.
(95) The visibility determination procedure 310 casts rays from every player's virtual frustum using the player's aspect ratio. Each player's aspect ratio is received from the game server 250, and matches that of the player's. An under-reported ratio places the player at a disadvantage and an over-reported ratio should be rejected server-side and regarded as misinformation. This mechanism prevents players (i.e. client devices) from abusing the data filtering procedure 300. In scenarios where this information is not available, a reasonable maximum frustum aspect ratio is used for all players equally (e.g., 16:9).
(96) With brief reference to
(97) The client device 212 controls first player 452 in first person view and may interact with the virtual environment or map (collectively represented by map elements 490). The map elements 490 may include walls, doors, objects, etc.
(98) Other players 462, 468 participate in the online gaming session and also interact together and/or with the virtual environment. The first player 452 sees second player 462, which is located in front of him. Fourth player 468 (depicted in dotted lines) is located behind a wall and should not be normally visible to the first player 452. However, if the first player 452 uses wall hacking code on the game client application 230, the first player 452 may gain an unfair advantage over remaining players.
(99) In the illustrated example, the procedures and methods described herein are intended to prevent first player 452 from wall hacking.
(100) In one or more embodiments where only bounding boxes are available, the rays will register player visibility as they intersect player bounding boxes and continue along the ray direction as if these intersections did not occur until encountering a solid wall. This prevents players' bounding boxes from hiding each other in the event that they line up behind each other visually. This scenario, which is referred to as an independent visibility scenario, is depicted in
(101) Independent visibility includes any visibility generated by player geometry resulting from a sequence of rays casted irrespective of any source of light. As a non-limiting example, independent visibility can be a single ray casted directly from a viewer's frustum.
(102) Another scenario arises when a player's body is leaving casted shadows on the surrounding environment due to a source of light. This scenario is referred to as dependent visibility, and is depicted in
(103) Thus, to overcome this problem in the dependent visibility scenario, the visibility determination procedure 310 accumulates player IDs along the path into the ray's payload and only registers visibility for those accumulated players if the shadow ray fails to register a hit with the map. A non-limiting example of this packing strategy is illustrated below:
(104) TABLE-US-00001 Layout (location = 0) rayPayloadInEXT struct { /* 2 bits: rayMask compressed 2 bits: hitType 1 bit: secondary ray flag 3 bits: player hit booleans via secondary ray 6 bits: originating player ID 6 bits: 1.sup.st player hit via secondary 6 bits: 2.sup.nd player hit via secondary 6 bits: 3.sup.rd player hit via secondary */ uint rayMaskHitTypeSecFlagSecHitsPlayerIds; } rayLoad;
(105) In this example, the entire payload is represented using 32 bits and can contain dependent visibility for 3 players back to back. An additional 32 bits will be sufficient to accommodate dependent visibility for 4 more players (accounting for additional hit flags). It will be appreciated that such optimization is game-specific and has to be done on a per-game basis and involves knowing the upper bound on the number of players in a session at any given time. The ray mask is utilized to avoid intersecting friendly players as their information is always transmitted. The hit type indicates one of the following:
(106) 0) No hit was registered. The primary ray escaped to the sky.
(107) 1) Only the environment was hit by the primary ray.
(108) 2) Players were registered as independently visible via the primary ray.
(109) 3) Player hits were packed onto the ray payload via the shadow ray.
(110) It will be appreciated that this information is useful for debugging and to also register dependent visibility at the end of a traversal if and only if a shadow ray missed the map, thus reaching the light source and leaving shadows of players intersected along the way.
(111) Turning back to
(112) In one or more embodiments, the ray casting-procedure 350 comprises one of a super sampling procedure 360 and an importance sampling procedure 370.
(113) Additionally, a force-casting procedure 380 may be launched.
(114) It will be appreciated that the electronic device executing the visibility determination procedure 310 does not require a display output.
(115) In one or more embodiments, for example if the game supports player appearances with greatly varying materials, the visibility determination procedure 310 is configured to cache the range of materials that describe the varieties of player appearances to avoid retransmitting them later. The cached range of materials may be retained until the next map change.
Preparation Procedure
(116) The updated player information is transmitted by each client device 212, 214, 216 to the game server 250. The updated player information comprises, for each client device 212, 214, 216 respectively, actions of the respective player on the map.
(117) In one or more embodiments, the actions include one or more of: player actions related to movement (e.g., strafing, crouching, moving forward or backwards, jumping etc.), player actions resulting in changes in viewing direction (e.g., moving the mouse, gun recoil due to fired weapon etc.), player actions related to gameplay (e.g., firing bullets, opening doors, picking up items, etc.)
(118) In one or more other embodiments, the actions may further include one or more of: entirely new player viewing directions, aspect ratio and vertical or horizontal field of view, entirely new player positions, player health, animation states, updated lighting information indicating dynamic lighting in the map, and changes to a subset of map geometry instances indicating a dynamic map.
(119) The game server 250 updates the game state to obtain a current or updated game state based at least in part on the updated player information received from the plurality of client devices 210.
(120) The game server 250 then transmits at least a portion (i.e., a subset) of the updated player information to the player data preparation procedure 324.
Player Data Preparation Procedure
(121) The player data preparation procedure 324 is executed and receives, from the game server 250, at least a portion of the updated player information or player updates at every frame.
(122) The player data preparation procedure receives, for each player or client device 212, 214, 216, current vantage point data and future vantage point data.
(123) The current vantage point data includes, for each player, eye data, look data, up data, aspect ratio and y-field of view (FOV). It will be appreciated that eye data in this context refers to the current three dimensional location of the player's eye in space, look data refers to the current direction that the player is looking at described by a unit length vector in three dimensional space, up refers to a current direction pointing from the tip of the player's head towards the sky, again provided in unit length in three dimensional space. The up direction is orthogonal to the look direction (forms a 90 degrees celcius angle).
(124) The future vantage point data includes, for each player: future eye, future look, future up, future aspect ratio and future y-FOV.
(125) It will be appreciated that that the current vantage point data and the future vantage point data are determined by the game server 250 and provided to the player data preparation procedure 324.
(126) In one or more embodiments, for example when the client devices 212, 214, 216 are located remotely (i.e., not in LAN), the player data preparation procedure 324 receives lagging indicators for each client device 212, 214, 216. The lagging indicators may include for example a ping associated with each player, or an indication that the ping is above a predetermined threshold known to the player data preparation procedure 324.
(127) The updated player information comprises, for client device 212, 214, 216 respectively, actions of the respective player on the map.
(128) In one or more embodiments where the video game executed by the game client application 230 and the game server 250 support dynamic map changes, the player data preparation procedure 324 receives indication of changes to the map.
(129) In one or more embodiments where the video game executed by the game client application 230 and the game server 250 support dynamic lighting, the player data preparation procedure 324 receives indications of change to lighting information.
(130) The player data preparation procedure 324 is configured to generate, for each player, based on the player geometry, the current vantage point data and the future vantage point data, respective collated player geometry.
(131) In one or more embodiments, the collated player geometry is generated using the current eye and future eye vantage point data.
(132) In one or more other embodiments, the collated player geometry is generated further using a future bounding box. Such a future bounding box causes the dimensions of the bounding box to interpolate as well as its position while future versions of the bounding boxes are being generated and collated.
(133) In one or more other embodiments, when armatures are available instead of bounding boxes, the player data preparation procedure 324 further uses current and future animation states to generate the collated player geometry.
(134) The player data preparation procedure 324 thus obtains, for each player, a respective collated player geometry.
(135) The player data preparation procedure 324 additionally initializes bits within the visibility determination matrix for the current frame to zero.
Map Preparation Procedure
(136) The map data preparation procedure 328 receives map geometry instances.
(137) In one or more embodiments, the map data preparation procedure 328 receives the samplers and materials for map geometry instances.
(138) In one or more embodiments, the map data preparation procedure 328 further receives samplers and materials for players.
(139) In one or more embodiments where the video game executed by the game client application 230 and the game server 250 support dynamic lighting, the map data preparation procedure 328 receives indications of change to lighting information.
(140) The map data preparation procedure 328 is configured to generate an acceleration structure. The acceleration structure to generate comprises a top level acceleration structure (TLAS) comprised of a plurality of bottom-level acceleration structures (BLASes).
(141) The map data preparation procedure 328 is configured to generate BLASes using the map geometry instances.
(142) The BLASes are acceleration structures representing chunks of triangles or shapes arranged together on a top-down structure.
(143) The map data preparation procedure 328 is configured to generate the TLAS by combining the BLASes of map geometry instances together.
(144) The TLAS represents an entire scene. The two-level design of the TLAS allows composing different scenes by mixing and matching different BLASes together.
(145) It will be appreciated that respective player and map geometry instance materials may be used alongside the TLAS.
(146) The map data preparation procedure 328 outputs the TLAS.
Pre-Pass Procedure
(147) The pre-pass procedure 330 is configured to generate look-a-head corners using a look-a-head procedure 334 and bound stretchings using a bound stretching procedure 338.
(148) In one or more embodiments, the pre-pass procedure 330 is configured to generate acceleration structures including BLASes and a TLAS for lagging players only.
Look-a-Head
(149) The look-a-head procedure 334 is configured to: (i) determine respective origins of each of the plurality of virtual sub-frusta; and (ii) clip the respective origins against the map.
(150) In one or more embodiments, the look-a-head procedure 334 is configured to construct a ray segment starting from the player's current eye (i.e., origin) and ending at a quarter of the player's height above the eye, clip the ray segment against the map at a clipped position, and from the clipped position, build four additional ray segments aligned laterally with the four upper corners of the player's current bounding box.
(151) The look-a-head procedure 334 is configured to repeat steps (i)-(ii) with the initial ray segment ending instead at half the player's height below the current eye. This provides another four (4) of the virtual sub-frusta origins.
(152) In one or more embodiments, when armatures are available instead of bounding boxes, the look-a-head procedure 334 is configured to, from the clipped position, build four additional ray segments aligned laterally with the four upper corners of a bounding box surrounding the player armature.
(153)
Bound Stretching Procedure
(154) With insufficient virtual resolutions it is possible for distant players to become invisible as their occupied virtual screen real-estate shrinks. While in some embodiments, the visibility determination procedure 310 employs a jitter similar to temporal super-sampling to capture sub-pixel detail, additional measures may further be used. The pre-pass procedure determines how far player geometries (e.g., bounding boxes or armatures) can be stretched without exceeding twice their initial volume or intersecting the map world at large. The information gathered is used to increase player sizes as the virtual resolution shrinks, which is referred to as bound stretching.
(155) The bound stretching procedure 338 is configured to inter alia: (i) receive the current player geometry (i.e., one of bounding box or current player armature); (ii) construct a ray segment from the center of the player geometry in the positive X direction with A times the size of the X dimension of the player geometry, where A is a configurable threshold, (e.g. A=1.13); (iii) clip the ray segment against the map; and (iv) obtain the stretch bound for the skewing player geometry in the positive X direction based on the clipped segment ray length.
(156) The bound stretching procedure 338 is configured to repeat steps (i)-(iv) for the following directions and dimensions: Negative X direction, X dimension of player geometry (bounding box or armature): retrieving skewing bounds in the negative X direction Positive Y direction, Y dimension of player geometry (bounding box or armature): retrieving skewing bounds in the positive Y direction Negative Y direction, Y dimension of player geometry (bounding box or armature): retrieving skewing bounds in the negative Y direction Positive Z direction, Z dimension of player geometry (bounding box or armature): retrieving skewing bounds in the positive Z direction Negative Z direction, Z dimension of player geometry (bounding box or armature): retrieving skewing bounds in the negative Z direction
(157) The bound stretching procedure 338 thus obtains stretch bounds (i.e., threshold distances) as six (6) skewing amounts, one for each dimension and direction.
(158) In one or more embodiments, the pre-pass procedure 330 is configured to generate a TLAS for lagging players. One or more of the plurality of players 210 may be determined to be lagging based on the lagging indication. In one or more embodiments, the pre-pass procedure 330 determines that players are lagging based on their respective pings being above a threshold.
(159) The pre-pass procedure 330 is configured to use the stretch bounds or threshold distances to generate, for each player, an enlarged player BLAS. The pre-pass procedure 330 then generates an alternate (lagging) TLAS using enlarged player BLASes while reusing map instance geometry BLASes built during map data preparation procedure 328.
(160) In one or more embodiments, the pre-pass procedure 330 uses materials for respective enlarged players and map geometry instances alongside the TLAS.
Ray-Casting Procedure
(161) The ray-casting procedure 350 is configured to inter alia: (i) receive one or more of the TLAS, originating player IDs, current and future vantage point data for all players and in one embodiment ray masks representative of player team associations; (ii) trace rays; (iii) determine intersections between rays, players and other geometry based on one or more of the TLASes (iv) generate and populate a visibility matrix indicative of pair-wise visibility between players.
(162) In one or more embodiments, the ray-casting procedure 350 is configured to divide, for each player, the respective virtual frustum into a plurality of sub-frusta to be placed on the look-a-head corners and the original vantage point (e.g., eye location).
(163) In one or more embodiments, the ray-casting procedure 350 is configured to construct an in-between virtual frustum based on current vantage point data and future vantage point data for each player. Building in-between frusta is also referred to as viewer forward projection, as it produces some rays into the near future using future vantage point information.
(164) In one embodiment, the ray-casting procedure 350 uses in-between sub-frusta starting from look-a-head corners based on current vantage point data and future vantage point data for each player.
(165)
(166) In one or more embodiments, every look-a-head corner also conducts line-of-sight tests to every other enemy player in the game, which may be necessary because look-a-head corners alone will not be able to prevent surprise appearance caused by rapid head swings, as can they only account for popping resulting from lateral movement. Further, the ray casting procedure for a lagging player is configured to perform line-of-sight tests on three locations along player velocity vectors to account for forward projection of enemy positions. Much like force-casters each virtual pixel within a sub-frustum can either take on one or more line-of-sight tests dependent on sub-frusta resolutions.
(167) As a non-limiting example, in a CS:GO implementation with a base resolution of 640×640, each sub-frustum will approximately have a resolution of 213×213. Given that the upper bound on player count is 64, the first 64 virtual pixel rows can naturally be associated with line-of-sight tests. Since each virtual row has also 213 virtual pixels the first three virtual pixels can trace along the combatant's velocity vector. This is our implemented approach for evenly distributing line-of-sight tests across virtual pixels.
(168) In one or more embodiments where there is presence of lagging players, the ray-casting procedure 350 uses the lagging TLAS having been generated for lagging players.
(169) The ray-casting procedure 350 casts rays.
(170) It will be appreciated that a ray includes an origin, direction and parametric interval (TMin, TMax) in which intersections may occur at T locations along the interval. To be concrete, positions along the ray are: origin+T*direction (the direction does not get normalized).
(171) In some embodiments the ray-casting procedure 350 is configured to execute one of a super sampling procedure 360 and an importance sampling procedure 370. In some embodiments both may lead to launching of a force-casting procedure 380.
(172) The super sampling procedure 360 is executed when the respective player geometries are bounding boxes. The importance sampling procedure 370 is executed when the respective player geometries are armatures. The same force-casting procedure 380 may be executed for both bounding boxes and armatures.
Super Sampling Procedure
(173) The visibility determination procedure 310 may use a super sampling procedure 360 to counter lowered resolutions.
(174) The super sampling procedure 360 is configured to inter alia: (i) receive a collection of collated bounding boxes and their bounding spheres for each player; (ii) receive constructed in-between frustum or sub-frustum; (iii) receive primary rays in the constructed frustum or sub-frustum; —and (iv) potentially output further primary rays mimicking the initial primary ray with sub-pixel variations in ray direction.
(175) It will be appreciated that the bounding sphere is determined using the bounding box.
(176) In one or more embodiments, during the super sampling procedure 360, a cone is traced from every pixel starting from the eye with the area of the base being approximately pixel sized. Players with bounding spheres that are enveloped by this cone or overlap this cone are deemed to be sub-pixel. If a cone encounters a sub-pixel player, a number of additional rays—jittered differently—are allotted to attempt intersecting the sub-pixel player. This number scales relative to the distance measured against the furthest encountered player. It will be appreciated that it is a form of selective super-sampling and is done with the sole purpose of increasing the likelihood of visibility for sub-pixel players.
(177) In one or more embodiments, the super sampling procedure 360 does not use exact cones, and verifies if the centroid of the player's collated geometry is sufficiently far enough from the viewer by using a predetermined multiple of its bounding sphere radius shrunk with increasing viewer pixel footprint.
(178) If the player is sufficiently far enough, the super sampling procedure 360 measures an angle difference via a dot product between the originally traced ray and a ray pointing to the player's geometric centroid. If this difference is below a threshold increased with increasing viewer pixel footprint, the player is deemed sub-pixel. This two step process is illustrated in
(179) With one or more players deemed subpixel via the procedure outlined above it is expected that super sampling procedure 360 generates further primary rays mimicking the initial primary ray with sub-pixel variations in ray direction.
(180) In one or more embodiments, the super sampling procedure 360 ignores players on the same team.
Importance Sampling Procedure
(181) The importance sampling procedure 370 is configured to inter alia: (i) receive a collection of collated armatures of all players and their bounding spheres; (ii) constructed in-between frustum; (iii) primary rays in the constructed (sub-)frustum; and (iv) redirect primary rays towards locations on encountered player armatures.
(182) The purpose of importance sampling procedure 370 is to redirect rays to a set of armatures that will potentially yield better results as the rays become more likely to intersect collated player geometry.
(183) In one embodiment, the in-between frustum is determined to be a sub-frustum.
(184) For every collated armature provided in (i), we execute the sub-pixel determination procedure described in the previous section for every primary ray.
(185) If a collated armature is determined to be sub-pixel, a reference to it is added to a list of sub-pixel players for the primary ray that encountered it.
(186) Every primary ray that has a non-empty list of sub-pixel players, selects one entry from that list and re-directs itself towards a location on the armature of the selected entry.
(187) In one or more embodiments, the importance sampling procedure 370 ignores players in the same team.
Force-Casting Procedure
(188) The force-casting procedure 380 is configured to inter alia: (i) receive a collection of force-casters and their bounding spheres; (ii) constructed in-between frustum; (iii) primary rays in the constructed (sub-)frustum; and (iv) casts additional rays uniformly on the surface of a number of chosen force-casters;
(189) The force-casting procedure 380 casts an additional number of primary rays uniformly distributed across the surfaces of force-casters visible in the virtual frustum to cover openings in the map that may be missed during ray generation
(190) In one embodiment, the in-between frustum is determined to be a sub-frustum.
(191) For every force-caster received, their bounding spheres are tested to be at least partially covered in the virtual frustum via the direction vector of the primary ray and a vector extended to the center of their bounding spheres. The threshold that the dot product is tested against factors in the radius of the bounding sphere. Primary must be deemed to be associated with launching force-casters. Otherwise they will not engage in this process.
(192) If the force-caster is overlapping the direction vector of the primary ray, it will launch an additional number of primary rays each covering a unit area over the surface of the force-caster.
(193) The number of additional primary rays depends on whether there are sufficient virtual pixels in the virtual frustum.
(194) These additional primary rays will then attempt to cover openings in the environment that may otherwise be missed.
(195) The intersection determination procedure 390 used by primary rays will now be explained below.
Intersection Determination Procedure
(196) The intersection determination procedure 390 is used to determine intersections between rays (including primary and secondary, when applicable) and one or more of players, maps, light sources and optionally scattering materials so as to populate the visibility determination matrix. It will be appreciated that rays traverse the scene by traversing the TLAS.
(197) In some embodiments, rays are set to use regular ray tracing (i.e. not use modified path-tracing).
(198) In other embodiment, rays may be set to use modified path-tracing as will be explained below.
(199)
Intersections Between Primary Rays and Players
(200) In embodiments where path tracing is not used:
(201) The intersection determination procedure 390 is configured to: (i) extract the originating player ID from the ray payload; (ii) locates the cell on the visibility matrix corresponding to the current originating player ID and the intersected player's ID; and (iii) sets the bit corresponding to the current frame to 1 (register independent visibility of encountered player).
(202) The ray then continues traversal as if this intersection did not happen.
(203) In embodiments where path tracing is used:
(204) The intersection determination procedure 390 is configured to: (i) record the ID of the encountered player onto the ray payload (in preparation for dependent visibility); (ii) causes the ray to launch a secondary ray starting from the location of intersection towards a direction determined by the material properties of the intersected surface.
(205) In one or more embodiments, the ray may launch an additional secondary ray starting from the location of intersection towards a subset of nearby light sources that are determined to have sufficient visual impact to intersect potential players via NEE (use NEE SBT).
Intersections Between Primary Rays and Map
(206) In embodiments where path tracing is not used:
(207) The intersection determination procedure 390 is configured to: (i) cause launching of an additional secondary ray starting from the location of intersection towards a subset of nearby light sources that are determined to have sufficient visual impact to intersect potential players via shadow rays;
(208) In some embodiments, the ray may launch a secondary ray solely for the purpose of capturing global ambient occlusion (use AO SBT).
(209) In some embodiments, if the intersected surface is determined to be mirror-like, the ray may launch a secondary ray starting from the location of intersection with the reflected direction of the primary ray off of the encountered surface for the purpose of capturing visibility in mirrors (use simple reflection SBT).
(210) In embodiments where path tracing is used:
(211) The intersection determination procedure 390 is configured to cause the ray to launch a secondary ray starting from the location of intersection towards a direction determined by the material properties of the intersected surface.
(212) In one or more embodiments, the ray may launch an additional secondary ray starting from the location of intersection towards a subset of nearby light sources that are determined to have sufficient visual impact to intersect potential players via NEE (use NEE SBT).
(213) In some embodiments, where it is determined to be intersecting scattering material: The intersection determination procedure 390 is configured to reduce ray strength based on scattering coefficient of the intersected material, and in response to the ray strength being reduced below a threshold, and terminate the ray.
(214) It is contemplated that in alternative embodiments The intersection determination procedure 390 terminates ray based on the likelihood of termination via the scattering coefficient.
(215) If the potentially encountered scattering material above has not resulted in a termination, continue as if no intersection has occurred.
No Intersections Reported
(216) The intersection determination procedure 390 terminates the ray.
Intersections Between Primary Rays and Light Sources
(217) The intersection determination procedure 390 terminates the ray.
(218) The primary ray procedure has now potentially partially populated the visibility matrix.
Intersections Between Secondary Rays and Players
(219) The ray traverses the scene by traversing the acceleration structure.
(220) In some embodiments, the ray is set to not use modified path-tracing.
(221) In other embodiments, the ray is set to use modified path-tracing.
Intersections Between Secondary Rays and Players (Simple Reflection SBT)
(222) The intersection determination procedure 390 is configured to: (i) extract the originating player ID from the ray payload; (ii) locate the cell on the visibility matrix corresponding to the current originating player ID and the intersected player's ID; and (iii) set the bit corresponding to the current frame inside the cell is set to 1 (register independent visibility of encountered player); and (iv) the ray then continues traversal as if this intersection did not happen.
Intersections Between Secondary Rays and Map (Simple Reflection SBT)
(223) If the intersected surface is mirror-like, the intersection determination procedure 390 is configured to: cause the ray to launch a secondary ray starting from the location of intersection with the reflected direction of the current secondary ray off of the encountered surface for the purpose of capturing visibility in mirrors (use simple reflection SBT).
(224) If the intersected surface is not mirror-like, The intersection determination procedure 390 is configured to: launch a secondary ray starting from the location of intersection towards a subset of nearby light sources that are determined to have sufficient visual impact to intersect potential players via shadow rays.
Intersections Between Secondary Rays and Scattering Material (Simple Reflection SBT)
(225) The intersection determination procedure 390 is configured to: (i) reduce ray strength via scattering coefficient of the intersected material; and (ii) if the ray strength is reduced below a threshold, terminate the ray.
(226) In some embodiments, The intersection determination procedure 390 may terminate the ray based on the likelihood of termination via the scattering coefficient.
(227) If the potentially encountered scattering material above has not resulted in a termination, continue as if no intersection has occurred.
No Intersections Reported (Simple Reflection SBT)
(228) The intersection determination procedure 390 terminates the ray.
Intersections Between Secondary Rays and Players (AO SBT)
(229) The intersection determination procedure 390 is configured to: (i) extract the originating player ID from the ray payload; (ii) locate the cell on the visibility matrix corresponding to the current originating player ID and the intersected player's ID; (iii) set the bit corresponding to the current frame inside the cell to 1 (i.e., register independent visibility of encountered player).
(230) The ray then continues traversal as if this intersection did not happen.
Intersections Between Secondary Rays and all Other Scenarios (AO SBT)
(231) When intersecting anything else or when finished looking for intersections (i.e. all other scenarios), The intersection determination procedure 390 is configured to terminate the ray.
Intersections Between Secondary Rays and Players (NEE SBT)
(232) The intersection determination procedure 390 is configured to: (i) extract the originating player ID from the ray payload; (ii) locate the cell on the visibility matrix corresponding to the current originating player ID and the intersected player's ID; (iii) set the bit corresponding to the current frame inside the cell to 1 (register as if registering independent visibility of encountered player); and (iv) terminate the ray.
Intersections Between Secondary Rays all Other Scenarios (NEE SBT)
(233) When intersecting anything else or when finished looking for intersections (i.e. all other scenarios), The intersection determination procedure 390 is configured to terminate the ray.
(234) Otherwise:
Intersections Between Secondary Rays and Players (Otherwise)
(235) In embodiments where modified path-tracing is not used
(236) The intersection determination procedure 390 is configured to: (i) record the ID of the encountered player onto the ray payload (in preparation for dependent visibility).
(237) The ray then continues traversal as if this intersection did not happen.
(238) In embodiments where path tracing is used:
(239) The intersection determination procedure 390 is configured to: (i) record the ID of the encountered player onto the ray payload (in preparation for dependent visibility); and (ii) causing the ray to launch a secondary ray starting from the location of intersection towards a direction determined by the material properties of the intersected surface.
(240) In one or more embodiments, the ray may launch an additional secondary ray starting from the location of intersection towards a subset of nearby light sources that are determined to have sufficient visual impact to intersect potential players via NEE (use NEE SBT).
Intersections Between Secondary Rays and Map (Otherwise)
(241) In embodiments where modified path-tracing is not used
(242) The intersection determination procedure 390 is configured to terminate the ray.
(243) In embodiments where path tracing is used:
(244) The intersection determination procedure 390 is configured to cause the ray to launch a secondary ray starting from the location of intersection towards a direction determined by the material properties of the intersected surface.
(245) In one or more embodiments, the ray may launch an additional secondary ray starting from the location of intersection towards a subset of nearby light sources that are determined to have sufficient visual impact to intersect potential players via NEE (use NEE SBT).
Intersections Between Secondary Rays and Scattering Materials (Otherwise)
(246) The intersection determination procedure 390 is configured to: (i) reduce ray strength via scattering coefficient of the intersected material; and (ii) if ray strength is reduced below a threshold, terminate the ray.
(247) In some embodiments, the intersection determination procedure 390 is configured to terminate ray based on the likelihood of termination via the scattering coefficient. Otherwise The intersection determination procedure 390 is configured to continue as if no intersection occurred.
Intersections Between Secondary Rays and Light Source (Otherwise)
(248) It will be appreciated that that in some embodiments, there are no intersections. Such an embodiment for example could be the sky which some traditional path-tracing applications consider a light source.
(249) The intersection determination procedure 390 is configured to extract the originating player ID from the ray payload; (ii) for every recorded encountered player ID on the ray payload, locate the cell on the visibility matrix corresponding to the current originating player ID and the recorded encountered player's ID; and (iii) set the bit corresponding to the current frame inside the cell to 1 (register dependent visibility of encountered player).
(250) At this point the visibility matrix for the current frame is deemed to be in a completely determined state.
(251) The visibility determination procedure 310 thus outputs the visibility matrix. The visibility matrix is used by the game server 250 to filter data packets transmitted to each client device 212, 214, 216 to prevent wall hacking.
Method Description
(252) Now turning to
(253) In one or more embodiments, the server 250 comprises a processing device such as the processor 110 and/or the GPU 111 operatively connected to a non-transitory computer readable storage medium such as the solid-state drive 120 and/or the random-access memory 130 storing computer-readable instructions. The processing device is operable to provide real-time ray tracing, for example, via the GPU 111. The processing device, upon executing the computer-readable instructions, is configured to or operable to execute the method 900.
(254) In one or more other embodiments, the output of method 900 may be used for preventing wall hacking from happening by filtering outgoing data packets provided to the client devices.
(255) According to processing step 902, the server 250 receives map information for the gaming session.
(256) According to processing step 904, the server 250 receives player updates indicative of actions of the respective players on the map, the player updates including respective virtual frustum information for each player.
(257) According to processing step 906, the server 250 generates an acceleration structure using the map information and the player updates.
(258) According to processing step 908, the server 250 generates, for each player, respective primary rays from the respective virtual frustum associated with the player.
(259) According to processing step 910, the server 250 determines, for each player, based on the respective primary rays and the acceleration structure, intersections between the respective primary rays and the respective player geometries on the map
(260) According to processing step 912, the server 250 generating a visibility matrix based on at least the determined intersections, the visibility matrix comprising pair-wise visibility between the respective players on the map.
(261) In one or more embodiments, the visibility matrix obtained via method 900 may be used to filter outgoing data packets transmitted to each of the plurality of client devices 210. In one or more other embodiments, the visibility matrix obtained via method 900 may be used to analyze past multiplayer gaming sessions so as to perform statistical analysis.
(262) Reference will now be made to
(263)
Server Loop
(264) According to processing step 1002, the server 250 starts the online gaming session. The online gaming session begins for each of the client devices 212, 214, 216.
(265) According to processing step 1004, the server 250 feeds map information to the consumption loop 1100. The server 250 provides map information. The consumption loop 1100 executes a map preparation method 1200.
(266) According to processing step 1006, the server 250 receives player updates. In one or more embodiments, the server 250 receives player updates from each of the client devices 210 over the communication network 270.
(267) According to processing step 1008, the server 250 runs a game frame.
(268) According to processing step 1010, the server 250 feeds per-frame data to the consumption loop 1100. The consumption loop 1100 executes a frame pre-pass and pass routine 1250.
(269) According to processing step 1012, the server 250 receives a visibility matrix determined by the consumption loop 1100.
(270) According to processing step 1014, the server 250 transmits player packets based on the visibility matrix.
(271) The server 250 executes processing steps 1006 to 1014 repeatedly until a stopping criterion is met, such as the end of the gaming session.
Consumption Loop
(272) According to processing step 1100, the server 250 starts a ray tracing framework instance.
(273) According to processing step 1102, the server 250 receives the map information from the server loop 1000 and executes a map preparation routine or method 1200.
(274) According to processing step 1104, the server 250 receives the per-frame data from the server loop 1000 and executes the frame pre-pass and pass routine 1250 or method 1250.
Map Preparation Routine and Frame Pre-Pass and Pass Routine
(275) Now turning to
(276) According to processing step 1202, the server 250 receives map data.
(277) According to processing step 1204, the server 250 generates bottom level map acceleration structures.
(278) According to processing step 1252, the server 250 receives per-frame data.
(279) According to processing step 1254, the server 250 generates a top level acceleration structure using map and per-frame data.
(280) According to processing step 1256, the server 250 determines if a lagging player is present in the online gaming session. If a lagging player is present, the server 250 proceeds to processing step 1258. If a lagging player is not present, the server 250 proceeds to processing step 1262.
(281) According to processing step 1258, the server 250 runs pre-pass to retrieve stretch-bounds and look-ahead corners for all players.
(282) According to processing step 1260, the server 250 generates a top level acceleration structure for lagging players. The server 250 then proceeds to step 1262.
(283) According to processing step 1262, the server 250 determines if the game uses a regular pipeline. If the game uses a regular pipeline, the server 250 proceeds by executing a regular ray tracing method 1300 with bounding boxes. If the game does not use a regular pipeline, the server 250 proceeds by executing method 1400 to run a path-traced algorithm with armatures.
(284) Reference is now be made to
Regular Ray Tracing with Bounding Boxes
(285)
(286) According to processing step 1302, the server 250 launches primary rays for every virtual pixel. The server 250 launches primary rays for every virtual pixel by executing method 1310.
(287) According to processing step 1338, the server 250 determines if a hit was registered.
(288) If a hit was registered, the server 250 proceeds to method 1340.
(289) If method 1340 determines that the intersection should be ignored, the server 250 proceeds to method 1338. If method 1340 determines that a shadow ray should be launched it proceeds to processing step 1368.
(290) According to step 1368, if shadow rays are supported the server 250 proceeds to method 1370. If not, the server 250 proceeds to processing step 1386.
(291) If method 1370 determines that the shadow ray is already launched, the server 250 proceeds to processing step 1386. Otherwise, the server 250 launches a shadow ray and proceeds to processing step 1338.
(292) If a hit was not registered at processing step 1338, the server 250 proceeds to processing step 1376.
(293) According to processing step 1376, the server 250 determines if shadow rays are supported.
(294) If shadow rays are supported, the server 250 proceeds to method 1380 to handle registration of accumulated player IDS for regular pipelines.
(295) If shadow rays are not supported, the server 250 terminates the current transport path and proceeds to processing step 1386.
(296) According to processing step 1386, the server 250 waits on all the primary launches to finish.
(297) According to processing step 1388, the server 250 provides the visibility matrix including registered hits from step 1388. The method 1300 ends and proceeds to processing step 1012 of the method 1000.
Primary Ray Launch for Regular Ray Tracing
(298)
(299) According to processing step 1312, the server 250 determines if a player is lagging.
(300) If a player is lagging, the server 250 executes processing step 1314.
(301) According to processing step 1314, the server 250 subdivides frustum into sub-frusta placed on look-a-head corners.
(302) According to processing step 1316, the server 250 launches further rays only against the lagging TLAS and proceeds to processing step 1318.
(303) If the player is not lagging, the server 250 executes processing step 1318.
(304) According to processing step 1318, the server 250 picks in-between basis.
(305) According to processing step 1320, the server 250 determines if selective super-sampling is used.
(306) If selective super-sampling is used, the server 250 proceeds to processing step 1322. If selective super-sampling is not used, the server 250 proceeds to processing step 1326.
(307) According to processing step 1322, the server 250 determines if the ray-cone is overlapping sub-pixel players. If the ray-cone is overlapping sub-pixel players the server 250 proceeds to processing step 1324. If the ray-cone is not overlapping sub-pixel players, the server 250 proceeds to processing step 1326.
(308) According to processing step 1324, in response to the ray-cone overlapping sub-pixel players, the server 250 launches multiple jittered primary rays based on distance. It then proceeds to processing step 1328.
(309) According to processing step 1326, in response to the ray-cone not overlapping sub-pixel players, the server 250 launches single jittered primary ray. It then proceeds to processing step 1328.
(310) According to processing step 1328, the server 250 determines if force casters should be used.
(311) If it is determined that force casters should be used, the server 250 proceeds to execute method 1330 for running force-caster logic.
(312) If it is determined that force casters should not be used, the server 250 proceeeds to execute processing step 1338 of method 1300.
Handle Force-Caster Logic
(313)
(314) According to processing step 1332, the server 250 determines if a launch ID is associated with a force-caster.
(315) If a launch ID is associated with a force-caster, the server 250 proceeds to processing step 1334.
(316) If a launch ID is not associated with a force-caster, the server 250 proceeds to execute processing step 1338 of method 1300 if launched from method 1300 or step 1402 of method 1400 if launched from method 1400.
(317) According to processing step 1334, the server 250 determines if a force-caster is in view.
(318) If the server 250 determines that the force-caster is not in view, the server 250 proceeds to execute processing step 1338 of method 1300 if launched from method 1300 or step 1402 of method 1400 if launched from method 1400.
(319) If the server 250 determines that the force-caster is in view, the server 250 proceeds tp execute processing step 1336.
(320) According to processing step 1336, the server 250 launches one or more rays on force-caster surface based on virtual resolution.
(321) The method 1330 ends and the server 250 proceeds to execute processing step 1338 of method 1300 if launched from method 1300 or step 1402 of method 1400 if launched from method 1400.
Handle Ray Hits for Regular Ray Tracing
(322)
(323) According to processing step 1342, the server 250 determines if reflective surfaces are supported.
(324) If reflective surfaces are supported, the server 250 proceeds to execute processing step 1344. If reflective surfaces are not supported, the server 250 proceeds to execute processing step 1350.
(325) According to processing step 1344, the server 250 determines if the intersection is against a reflective map surface. If it is against a reflective map surface, the server 250 executes processing step 1346. If it is not against a reflective map surface, the server 250 proceeds to execute processing step 1350.
(326) According to processing step 1346, the server 250 launches reflected ray and registers all intersected players for originating player frame. It then proceeds to processing step 1348.
(327) According to processing step 1348, the server 250 determines if it intersected another reflective surface. If it did not intersect another reflective surface, the server 250 proceeeds to processing step 1338. If it did intersect another reflective surface the server 250 proceeds to processing step 1346.
(328) According to processing step 1350, the server 250 determines if it intersected against a diffuse a map surface. If it intersected against a diffuse map surface, the server 250 executes processing step 1352. If it did not insersect against a diffuse map surface, the server 250 proceeds to execute step 1360.
(329) According to processing step 1352, the server 250 determines if global AO is supported. If global AO is not supported, the server 250 proceeds to execute processing step 1358.
(330) If global AO is supported, the server 250 proceeds to execute processing step 1354.
(331) According to processing step 1354, the server 250 launches AO ray and registers all intersected players for originating player frame. It then proceeds to processing step 1356.
(332) According to processing step 1356, the server 250 ignores this ray going forward. It then proceeds to processing step 1356.
(333) According to processing step 1358, the server 250 sets hit type to map hit. The server 250 then attemps shadow ray launch at intersection.
(334) According to processing step 1360, if it did not insersect against a diffuse map surface, the server 250 determines if shadow rays are supported. If shadow rays are supported it proceeds to processing step 1362. Otherwise it proceeds to processing step 1366.
(335) According to processing step 1362, the server 250 determines if the ray is a shadow ray. If the ray is a shadow ray the server 250 proceeds to execute processing step 1364. If the ray is not a shadow ray the server 250 proceeds to execute processing step 1366.
(336) According to processing step 1364, if the ray is a shadow ray, the server 250 accumulates player ID on the ray payload.
(337) According to processing step 1366, if the ray is not a shadow ray, the server 250 registers player hit for this originating and frame. and sets type to primary hit.
(338) After processing steps 1364 and/or 1366, the server 250 proceeds to processing step 1338.
Shadow Rays for Regular Ray Tracing
(339)
(340) According to processing step 1372, the server 250 determines if a shadow was already launched. If a shadow ray was already launched, the server 250 proceeds to processing step 1386. If a shadow ray was not already launched, the server 250 proceeds to processing step 1374.
(341) According to processing step 1374, the server 250 sets the shadow flag and launches the ray. The server 250 then proceeds to processing step 1338.
(342) Handle registration of accumulated players for regular ray tracing:
(343)
(344) According to processing step 1382, the server 250 determines if the player IDs are accumulated on the payload. If the player IDs are accumulated on the payload, the server 250 proceeds to execute processing step 1384. If the player IDs are not accumulated on the payload, the server 250 proceeds to processing step 1386 of method 1300.
(345) According to processing step 1384, the server 250 sets the hit type to shadow and registers all players on the ray payload for originating player frame. It then proceeds to processing step 1386 of method 1300.
(346) Reference is now be made to
Path-Tracing with Armatures
(347)
(348) According to processing step 1401, the server 250 launches a primary ray by executing method 1410. It then proceeds to processing step 1402.
(349) According to processing step 1402, the server 250 determines if a ray intersection was detected.
(350) If a ray intersection was detected, the server 250 handles the ray hit by executing method 1430.
(351) If a ray intersection was not detected, the ray hit the sky. The server 250 proceeds to processing step 1404.
(352) If method 1430 exits with outcome A, it has determined that the ray has to be terminated and that it also has accumulated player IDs that require visibility registration. The server 250 proceeds to processing step 1404 to register all dependent visibility.
(353) If method 1430 exits with outcome B, the ray hit has been ignored. The server 250 proceeds to processing processing step 1402 as if the intersection has not happened.
(354) If method 1430 exits with outcome C, the whole ray path is to be terminated. The server 250 proceeds to processing step 1406.
(355) If method 1430 exits with outcome D the server 250 attempts to launch secondary rays. It proceeds to processing step 1450 to handle secondary ray logic.
(356) If method 1450 determines that maximum bounces have been reached the server 250 proceeds to processing step 1406.
(357) Otherwise it has launched a secondary ray and it proceeds to processing this ray via step 1402.
(358) According to processing step 1404, the server 250 registers accumulated players on the ray payload for this originating player and frame. It then proceeds to processing step 1406.
(359) According to processing step 1406, the server 250 waits on all primary launches to finish. It then proceeds to processing step 1408.
(360) According to processing step 1408, the server 250 transmits visibility matrix including registered hits.
Primary Rays for Path-Tracing with Armatures
(361)
(362) According to processing step 1412, the server 250 determines if the player is lagging. If the player is lagging, the server 250 proceeds to execute processing step 1414. If the player is not lagging, the server 250 proceeds to execute processing step 1418.
(363) According to processing step 1414, the server 250 subdivides the frustum into sub-frusta placed on look-a-head corners. It then proceeds to processing step 1416.
(364) According to processing step 1416, the server 250 launches further all rays against the lagging TLAS. It then proceeds to processing step 1418.
(365) According to processing step 1418, the server 250 picks an in-between basis using viewer velocity and a PRNG. It then proceeds to processing step 1420.
(366) According to processing step 1420, the server 250 determines if selective super sampling is used.
(367) If selective super sampling is used, the server 250 proceeds to execute processing step 1422.
(368) If selective super sampling is not used, the server 250 proceeds to execute processing step 1426.
(369) According to processing step 1422, the server 250 determines if the ray-cone overlaps sub-pixel player(s). If the ray-cone overlaps sub-pixel player(s), the server 250 proceeds to execute processing step 1424. If the ray-cone does not overlap sub-pixel player(s), the server 250 proceeds to execute processing step 1426.
(370) According to processing step 1424, the server 250 selects from the sub-pixel armatures overlapping this ray cone, an armature to redirect the ray towards. This corresponds to the importance sampling procedure 370.
(371) According to processing step 1426, the server 250 launches single jittered primary ray.
(372) According to processing step 1428, the server 250 determines if force casters should be used. If force casters should be used, the server 250 proceeds to execute method 1330 to run force-caster logic. If force casters should not be used, the server 250 proceeds to execute step 1402 from of method 1400.
Handling Ray Hits for Path-Tracing with Armatures
(373)
(374) According to processing step 1432, the server 250 determines if the ray intersection is against the map. If the ray has intersected the map, the server 250 proceeds to attempt a secondary ray launch by executing method 1450. If there is no ray hit against the map, the server 250 proceeds to execute processing step 1434.
(375) According to processing step 1434, the server 250 determines if the ray intersection is against a player. If the ray intersection is against a player, the server 250 proceeds to execute processing step 1436. If the ray intersection is not against a player, the server 250 proceeds to execute processing step 1438.
(376) According to processing step 1436, the server 250 accumulates player ID on the ray payload. The server 250 then proceeds to attempt a secondary ray launch by executing method 1450.
(377) According to processing step 1438, the server 250 determines if the ray intersection is against absorbing/scattering material. If the ray intersection is against absorbing/scattering material, the server 250 proceeds to execute processing step 1440.
(378) If the ray hit is not against absorbing/scattering material, a light source was hit and the server 250 terminates the path with registration of accumulated player IDs and proceeds to execute processing step 1404 of method 1400.
(379) According to processing step 1440, the server 250 determines if russian-roulette is used. If russian-roulette is used, the server 250 proceeds to execute processing step 1442. If russian-roulette is not used, the server 250 proceeds to execute processing step 1444.
(380) According to processing step 1442, the server 250 determines if the ray should be terminated based on a dice roll. If the ray should be terminated based on a dice roll, the server 250 terminates the path and proceeds to execute processing step 1406 of method 1400.
(381) If the ray should not be terminated based on a dice roll, the server 250 ignores the current intersection and proceeds to processing step 1402 of method 1400.
(382) According to processing step 1444, the server 250 weakens the ray against vertex info and records the strength on the payload. It then proceeds to process step 1446.
(383) According to processing step 1446, the server 250 determines if the ray is weak. In one or more embodiments, the server 250 determines if the ray is weak by comparing the ray strength to a threshold.
(384) If the ray is determined to be weak, the server 250 terminates the path and proceeds to execute processing step 1406 of method 1400.
(385) If the ray is determined not to be weak, the server 250 ignores the current intersection and keeps proceeds to processing step 1402 of method 1400.
Next Event Estimation Handling for Path-Tracing with Armatures
(386)
(387) According to processing step 1452, the server 250 determines if the ray has reached the maximum number of bounces. If the ray reached the maximum number of bounces, the server 250 terminates the path and proceeds to execute processing step 1406 of method 1400. If the ray has not reached the maximum number of bounces, the server 250 proceeds to execute processing step 1454.
(388) According to processing step 1454, the server 250 launches the secondary ray based on material properties
(389) According to processing step 1456, the server 250 launches a NEE ray if a light source is picked for NEE,
(390) According to processing step 1458, the server 250 determines if a player was hit. If a player was hit, it proceeds to processing step 1460. Otherwise, it proceeds to processing step 1462.
(391) According to processing step 1460, the server 250 registers hit player for originating and frame. It then proceeds to processing step 1462.
(392) According to processing step 1462, the server 250 terminates NEE ray and continues with material-scattered secondary ray. The server 250 proceeds to processing step 1402 of method 1400.
(393) It should be apparent to those skilled in the art that at least some embodiments of the present technology aim to expand a range of technical solutions for addressing a particular technical problem, namely preventing wall hacking from happening in multiplayer video games by using server side ray tracing, which may save bandwidth and computational resources by only transmitting required client update data to client devices.
(394) It should be expressly understood that not all technical effects mentioned herein need to be enjoyed in each and every embodiment of the present technology. For example, embodiments of the present technology may be implemented without the user enjoying some of these technical effects, while other non-limiting embodiments may be implemented with the user enjoying other technical effects or none at all.
(395) Some of these steps and signal sending-receiving are well known in the art and, as such, have been omitted in certain portions of this description for the sake of simplicity. The signals can be sent-received using optical means (such as a fiber-optic connection), electronic means (such as using wired or wireless connection), and mechanical means (such as pressure-based, temperature based or any other suitable physical parameter based).
(396) Modifications and improvements to the above-described implementations of the present technology may become apparent to those skilled in the art. The foregoing description is intended to be exemplary rather than limiting.