Misplaced Pages

#607392

50-546: PK3 may refer to: PK3 (file extension) , a file extension in the id Tech 3 game engine PK3 Paris , a clothing brand made by French footballer Presnel Kimpembe "PK3" (song) , an alternative name for the Hindi song Nanga Punga Dost in the 2014 Bollywood film PK See also [ edit ] PK-3 Plus (ISS experiment) , a joint Russian-German laboratory PK-35 (disambiguation) PK (disambiguation) Topics referred to by

100-684: A root-finding method , a method that finds the zero of a function . The algorithm uses Newton's method : if there is an approximation, y n {\displaystyle y_{n}} for y {\displaystyle y} , then a better approximation y n + 1 {\displaystyle y_{n+1}} can be calculated by taking y n − f ( y n ) f ′ ( y n ) {\displaystyle y_{n}-{\frac {f(y_{n})}{f'(y_{n})}}} , where f ′ ( y n ) {\displaystyle f'(y_{n})}

150-451: A union is also undefined behavior in C++. In modern C++, the recommended method for implementing this function's casts is through C++20's std::bit_cast . This also allows the function to work in constexpr context: The algorithm computes 1 x {\textstyle {\frac {1}{\sqrt {x}}}} by performing the following steps: Since this algorithm relies heavily on

200-427: A "snapshot" system to relay information about game "frames" to the client over UDP . The server updates object interaction at a fixed rate independent of the rate clients update the server with their actions and then attempts to send the state of all objects at that moment (the current server frame) to each client. The server attempts to omit as much information as possible about each frame, relaying only differences from

250-464: A 32-bit container. As an example, consider again the number x = 0.15625 = 0.00101 2 {\displaystyle x=0.15625=0.00101_{2}} . Normalizing x {\displaystyle x} yields: and thus, the three unsigned integer fields are: these fields are packed as shown in the figure below: If 1 x {\textstyle {\frac {1}{\sqrt {x}}}} were to be calculated without

300-440: A 32-bit floating-point number as the input and stores a halved value for later use. Then, treating the bits representing the floating-point number as a 32-bit integer, a logical shift right by one bit is performed and the result subtracted from the number 0x 5F3759DF , which is a floating-point representation of an approximation of 2 127 {\textstyle {\sqrt {2^{127}}}} . This results in

350-502: A computer or a calculator, a table of logarithms would be useful, together with the identity log b ⁡ ( 1 x ) = log b ⁡ ( x − 1 2 ) = − 1 2 log b ⁡ ( x ) {\textstyle \log _{b}\left({\frac {1}{\sqrt {x}}}\right)=\log _{b}\left(x^{-{\frac {1}{2}}}\right)=-{\frac {1}{2}}\log _{b}(x)} , which

400-400: A floating point number is used in digital signal processing to normalize a vector, scaling it to length 1 to produce a unit vector . For example, computer graphics programs use inverse square roots to compute angles of incidence and reflection for lighting and shading . 3D graphics programs must perform millions of these calculations every second to simulate lighting. When the code

450-472: A floating-point number, y = y*(threehalfs - x/2*y*y); is equivalent to By repeating this step, using the output of the function ( y n + 1 {\displaystyle y_{n+1}} ) as the input of the next iteration, the algorithm causes y {\displaystyle y} to converge to the inverse square root. For the purposes of the Quake III engine , only one iteration

500-475: A good approximation with only one division step. The length of the vector is determined by calculating its Euclidean norm : the square root of the sum of squares of the vector components . When each component of the vector is divided by that length, the new vector will be a unit vector pointing in the same direction. In a 3D graphics program, all vectors are in three- dimensional space, so v {\displaystyle {\boldsymbol {v}}} would be

550-573: A large amount of the code rewritten. Successor id Tech 4 was derived from id Tech 3, as was Infinity Ward 's IW engine used in Call of Duty 2 onward. At QuakeCon 2005, John Carmack announced that the id Tech 3 source code would be released under the GNU General Public License v2.0 or later, and it was released on August 19, 2005. It was originally distributed via FTP , and moved to GitHub . Unlike most other game engines released at

SECTION 10

#1732876230608

600-426: A range. He first computed the optimal constant for the linear approximation step as 0x5F37642F , close to 0x5F3759DF , but this new constant gave slightly less accuracy after one iteration of Newton's method. Lomont then searched for a constant optimal even after one and two Newton iterations and found 0x5F375A86 , which is more accurate than the original at every iteration stage. He concluded by asking whether

650-558: A variation of the algorithm in Activision 's 1997 Interstate '76 . Quake III Arena , a first-person shooter video game, was released in 1999 by id Software and used the algorithm. Brian Hook may have brought the algorithm from 3dfx to id Software. A discussion of the code appeared on the Chinese developer forum CSDN in 2000, and Usenet and the gamedev.net forum spread the code widely in 2002 and 2003. Speculation arose as to who wrote

700-474: A vector ( v 1 , v 2 , v 3 ) {\displaystyle (v_{1},v_{2},v_{3})} . is the Euclidean norm of the vector. is the normalized (unit) vector. Substituting ‖ v ‖ {\textstyle \|{\boldsymbol {v}}\|} , the equation can also be written as: which relates the unit vector to the inverse square root of

750-442: Is a scaled and shifted piecewise-linear approximation of log 2 ⁡ ( x ) {\displaystyle \log _{2}(x)} , as illustrated in the figure on the right. In other words, log 2 ⁡ ( x ) {\displaystyle \log _{2}(x)} is approximated by The calculation of y = 1 x {\textstyle y={\frac {1}{\sqrt {x}}}}

800-762: Is an integer, and 1. b 1 b 2 b 3 … {\textstyle 1.b_{1}b_{2}b_{3}\ldots } is the binary representation of the significand . Since the single bit before the point in the significand is always 1, it does not need be stored. The equation can be rewritten as: where m x {\textstyle m_{x}} means 0. b 1 b 2 b 3 … {\textstyle 0.b_{1}b_{2}b_{3}\ldots } , so m x ∈ [ 0 , 1 ) {\textstyle m_{x}\in [0,1)} . From this form, three unsigned integers are computed: These fields are then packed, left to right, into

850-639: Is based on the identity Using the approximation of the logarithm above, applied to both x {\displaystyle x} and y {\displaystyle y} , the above equation gives: Thus, an approximation of I y {\displaystyle I_{y}} is: which is written in the code as The first term above is the magic number from which it can be inferred that σ ≈ 0.0450466 {\displaystyle \sigma \approx 0.0450466} . The second term, 1 2 I x {\displaystyle {\frac {1}{2}}I_{x}} ,

900-432: Is calculated by shifting the bits of I x {\displaystyle I_{x}} one position to the right. With y {\displaystyle y} as the inverse square root, f ( y ) = 1 y 2 − x = 0 {\displaystyle f(y)={\frac {1}{y^{2}}}-x=0} . The approximation yielded by the earlier steps can be refined by using

950-536: Is different from Wikidata All article disambiguation pages All disambiguation pages PK3 (file extension) id Tech 3 , popularly known as the Quake III Arena engine , is a game engine developed by id Software for its Quake III Arena . It has been adopted by numerous games. It competed with the Unreal Engine ; both engines were widely licensed. id Tech 3 is based on id Tech 2 , with

1000-497: Is subject to additional integrity checks. Developers must manually deactivate pure server to test maps or mods that are not in data packs using the PK3 file format. Later versions supplemented pure server with PunkBuster support, though all the hooks to it are absent from the source code release because PunkBuster is closed source software and including support for it in the source code release would have caused any redistributors/reusers of

1050-595: Is the derivative of f ( y ) {\displaystyle f(y)} at y n {\displaystyle y_{n}} . For the above f ( y ) {\displaystyle f(y)} , where f ( y ) = 1 y 2 − x {\displaystyle f(y)={\frac {1}{y^{2}}}-x} and f ′ ( y ) = − 2 y 3 {\displaystyle f'(y)=-{\frac {2}{y^{3}}}} . Treating y {\displaystyle y} as

SECTION 20

#1732876230608

1100-502: Is the basis of several game projects based on the id Tech 3 engine, such as OpenArena (mimicking Quake III Arena ), Tremulous , Smokin' Guns , Urban Terror , Turtle Arena and World of Padman and game engine projects such as efport (a Star Trek: Voyager – Elite Force Holomatch clone), ioJedi Outcast, ioJedi Academy, ioDoom3, and OpenMoHAA . The engine and its associated games have been included in several Linux and BSD distributions. The cMod engine derived from

1150-451: Is valid for every base b {\displaystyle b} . The fast inverse square root is based on this identity, and on the fact that aliasing a float32 to an integer gives a rough approximation of its logarithm. Here is how: If x {\displaystyle x} is a positive normal number : then and since m x ∈ [ 0 , 1 ) {\displaystyle m_{x}\in [0,1)} ,

1200-479: The optimal approximation (the best in the sense of the uniform norm of the error). However, this value is not used by the algorithm as it does not take subsequent steps into account. Thus there is the approximation Interpreting the floating-point bit-pattern of x {\displaystyle x} as an integer I x {\displaystyle I_{x}} yields It then appears that I x {\displaystyle I_{x}}

1250-420: The C standard, reinterpreting a floating point value as an integer by casting then dereferencing the pointer to it is not valid ( undefined behavior ). Another way would be to place the floating point value in an anonymous union containing an additional 32-bit unsigned integer member, and accesses to that integer provides a bit level view of the contents of the floating point value. However, type punning through

1300-534: The LLVM project due to his synthesis of the ioquake3 engine, ray-tracing rendering technique, and LLVM. The project has since received forks, such as Quake3e, Spearmint, and vkQuake3. Other derived engines include the Daemon engine used by Unvanquished , as well as competing source ports like XreaL, Kwaak3 for Android and Quake-3-Android-Port-QIII4A. Fast inverse square root The algorithm accepts

1350-492: The algorithm and how the constant was derived; some guessed John Carmack . Quake III ' s full source code was released at QuakeCon 2005 , but provided no answers. The authorship question was resolved in 2006 when Greg Walsh, the original author, contacted Beyond3D after their speculation gained popularity on Slashdot. In 2007 the algorithm was implemented in some dedicated hardware vertex shaders using field-programmable gate arrays (FPGA). The inverse square root of

1400-456: The algorithm are illustrated below: Interpreting as IEEE 32-bit representation: Reinterpreting this last bit pattern as a floating point number gives the approximation y = 2.61486 {\displaystyle y=2.61486} , which has an error of about 3.4%. After one single iteration of Newton's method , the final result is y = 2.52549 {\displaystyle y=2.52549} , an error of only 0.17%. According to

1450-529: The appearance of many surfaces can be defined in text files referred to as "shader scripts." Shaders are described and rendered as several layers, each layer contains a texture, a "blend mode" which determines how to superimpose it over the previous layer and texture orientation modes such as environment mapping, scrolling, and rotation. These features can readily be seen within the game with many bright and active surfaces in each map and even on character models. The shader system goes beyond visual appearance, defining

1500-418: The bit-level representation of single-precision floating-point numbers, a short overview of this representation is provided here. To encode a non-zero real number x {\displaystyle x} as a single precision float, the first step is to write x {\displaystyle x} as a normalized binary number: where the exponent e x {\textstyle e_{x}}

1550-573: The code is finished. The algorithm generates reasonably accurate results using a unique first approximation for Newton's method ; however, it is much slower and less accurate than using the SSE instruction rsqrtss on x86 processors also released in 1999. As an example, the number x = 0.15625 {\displaystyle x=0.15625} can be used to calculate 1 x ≈ 2.52982 {\textstyle {\frac {1}{\sqrt {x}}}\approx 2.52982} . The first steps of

PK3 - Misplaced Pages Continue

1600-504: The code to violate the GPL . Ioquake3 is a game engine project which aims to build upon the id Tech 3 source code release in order to remove bugs, clean up source code and to add more advanced graphical and audio features via SDL and OpenAL . ioquake3 is also intended to act as a clean base package, upon which other projects may be built. The game engine supports Ogg Vorbis format and video capture of demos in .avi format. The project

1650-436: The contents of volumes (e.g. a water volume is defined by applying a water shader to its surfaces), light emission and which sound to play when a volume is trodden upon. In order to assist calculation of these shaders, id Tech 3 implements a specific fast inverse square root function, which attracted a significant amount of attention in the game development community for its clever use of integer operations. id Tech 3 uses

1700-426: The distance components. The inverse square root can be used to compute v ^ {\displaystyle {\boldsymbol {\hat {v}}}} because this equation is equivalent to where the fraction term is the inverse square root of v 1 2 + v 2 2 + v 3 2 {\displaystyle v_{1}^{2}+v_{2}^{2}+v_{3}^{2}} . At

1750-625: The earlier Elite Force port was used to package the 20th anniversary freeware release of the game for Windows and Linux . The source code for the Return to Castle Wolfenstein and Wolfenstein: Enemy Territory engines was released under GNU GPL-3.0-or-later on August 12, 2010. The ioquake3 developers announced the start of other engine projects. The ioquake3 project has been used academic research such as Stanford University's Center for Computer Research in Music and Acoustics (CCRMA), Notre Dame as

1800-434: The fast inverse square root trick came from treating the 32-bit floating-point word as an integer , then subtracting it from a " magic " constant, 0x 5F3759DF . This integer subtraction and bit shift results in a bit pattern which, when re-defined as a floating-point number, is a rough approximation for the inverse square root of the number. One iteration of Newton's method is performed to gain some accuracy, and

1850-583: The first approximation of the inverse square root of the input. Treating the bits again as a floating-point number, it runs one iteration of Newton's method , yielding a more precise approximation. William Kahan and K.C. Ng at Berkeley wrote an unpublished paper in May 1986 describing how to calculate the square root using bit-fiddling techniques followed by Newton iterations. In the late 1980s, Cleve Moler at Ardent Computer learned about this technique and passed it along to his coworker Greg Walsh. Greg Walsh devised

1900-473: The foundation for VR research, and Swinburne University of Technology's Centre for Advanced Internet Architectures. Collaborative efforts from researchers at Carnegie Mellon University and the University of Toronto use ioquake3 as a platform for their published research. Students have used ioquake3 as the basis for advanced graphics work for their theses, such as Stephan Reiter's work which has been noted at

1950-445: The inverse square root was to calculate an approximation for 1 x {\textstyle {\frac {1}{\sqrt {x}}}} , then revise that approximation via another method until it came within an acceptable error range of the actual result. Common software methods in the early 1990s drew approximations from a lookup table . The key of the fast inverse square root was to directly compute an approximation by utilizing

2000-618: The last frame the client confirmed as received ( Delta encoding ). All data packets are compressed by Huffman coding with static pre-calculated frequency data to reduce bandwidth use even further. Quake 3 has an integrated and relatively elaborate cheat-protection system called "pure server". Any client connecting to a pure server automatically has pure mode enabled, and while pure mode is enabled only files within data packs can be accessed. Clients are disconnected if their data packs fail one of several integrity checks. The cgame.qvm file, with its high potential for cheat-related modification,

2050-641: The logarithm on the right-hand side can be approximated by where σ {\displaystyle \sigma } is a free parameter used to tune the approximation. For example, σ = 0 {\displaystyle \sigma =0} yields exact results at both ends of the interval, while σ = 1 2 − 1 + ln ⁡ ( ln ⁡ ( 2 ) ) 2 ln ⁡ ( 2 ) ≈ 0.0430357 {\textstyle \sigma ={\frac {1}{2}}-{\frac {1+\ln(\ln(2))}{2\ln(2)}}\approx 0.0430357} yields

PK3 - Misplaced Pages Continue

2100-423: The now-famous constant and fast inverse square root algorithm. Gary Tarolli was consulting for Kubota, the company funding Ardent at the time, and likely brought the algorithm to 3dfx Interactive circa 1994. Jim Blinn demonstrated a simple approximation of the inverse square root in a 1997 column for IEEE Computer Graphics and Applications . Reverse engineering of other contemporary 3D video games uncovered

2150-429: The relative difference 0.0017478, or 0.175% of the true value, 10. The absolute error only drops from then on, and the relative error stays within the same bounds across all orders of magnitude. It is not known precisely how the exact value for the magic number was determined. Chris Lomont developed a function to minimize approximation error by choosing the magic number R {\displaystyle R} over

2200-403: The same term [REDACTED] This disambiguation page lists articles associated with the title PK3 . If an internal link led you here, you may wish to change the link to point directly to the intended article. Retrieved from " https://en.wikipedia.org/w/index.php?title=PK3&oldid=1251872515 " Category : Disambiguation pages Hidden categories: Short description

2250-530: The structure of floating-point numbers, proving faster than table lookups. The algorithm was approximately four times faster than computing the square root with another method and calculating the reciprocal via floating-point division. The algorithm was designed with the IEEE 754-1985 32-bit floating-point specification in mind, but investigation from Chris Lomont showed that it could be implemented in other floating-point specifications. The advantages in speed offered by

2300-417: The time, floating-point division was generally expensive compared to multiplication; the fast inverse square root algorithm bypassed the division step, giving it its performance advantage. The following code is the fast inverse square root implementation from Quake III Arena , stripped of C preprocessor directives, but including the exact original comment text: At the time, the general method to compute

2350-414: The time—including its primary competitor, the Unreal Engine —id Tech 3 requires an OpenGL -compliant graphics accelerator to run. The engine does not include a software renderer . id Tech 3 introduced spline-based curved surfaces in addition to planar volumes, which are responsible for many of the game's surfaces. The graphical technology of the game is based tightly around a " shader " system where

2400-410: Was developed in the early 1990s, most floating point processing power lagged the speed of integer processing. This was troublesome for 3D graphics programs before the advent of specialized hardware to handle transform and lighting . Computation of square roots usually depends upon many division operations, which for floating point numbers are computationally expensive . The fast inverse square generates

2450-635: Was started shortly after the source code release with the goal of creating a bug -free, enhanced open source Quake III engine source code distribution upon which new games and projects can be based. In addition, the project aims to provide an improved environment in which Quake III: Arena , the Team Arena expansion pack and all the popular mods can be played. The project added features including builtin VoIP support, Anaglyph stereo rendering (for viewing with 3D glasses), and numerous security fixes. Ioquake3

2500-423: Was used. A second iteration remained in the code but was commented out . As noted above, the approximation is very accurate. The single graph on the right plots the error of the function (that is, the error of the approximation after it has been improved by running one iteration of Newton's method), for inputs starting at 0.01, where the standard library gives 10.0 as a result, and InvSqrt() gives 9.982522, making

#607392