david@epicb.UUCP (David P. Cook) (10/05/88)
In article <5760@utah-cs.UUCP> banks@utah-cs.UUCP (Michael J. Banks) writes: >I have need of an algorithm to clip 2-D lines to a rectangle. >All of the references I have been able to find give algorithms >for clipping lines in "world coordinates" and rely on floating >point numbers. >Can anyone direct me to an efficient integer algorithm for >clipping lines to rectangles? Mike: Well, there are many efficient clipping algorithms for clipping lines to rectangular surfaces. In paticular, reference the Cohen-Sutherland clipping algorithm as shown in "Fundamentals Of Interactive Computer Graphics" by J. D. Foley and A. Van Dam, pages 146 - 149. This is a very simple clipper for lines on a rectangular surface and can very easily be treated as all integer. NOW, for the rest of your problem.... DAVE'S COMPLETE GUIDE OF FAKING REAL NUMBERS -------------------------------------------- In your 'problem' you said that you can only find algorithms that use floating numbers. This should not be a problem, especially in assembly language. Givens: [1] People based in Math do not ususally make good hackers, unless the math is logic based. (flame off) [2] Real numbers are not suitable for present day computers which tend to use integers. [3] Unless handled by a math coprocessor, all real numbers are actually calculated using many integer steps. Solution: FAKE IT! There are many ways to simulate floating point as follows: [1] When needing to represent numbers to a fixed decimal position (say, two or three digits), simply MULTIPLY the numbers by 100 or 1000 prior to doing the work... for example: Problem: 2 / 3 Solution: (2 * 1000) / 3 The answer is in a magnitude of 1000, but may be 'unscalled' after all work is finished. [2] THE ABOVE EXAMPLE IS SHIT... Yes, even though it works, the multiply times 1000 is paticularly nasty... instead, generalize it to assembly language... ie... Problem: 2 / 3 Solution: (2 * 1024) / 3 Simpler: (2 << 10) / 3 (Read as: Two, shift left 10 bits, divided by Three) See... in most cases (though not all) you can multiply (scale) by ANY number, as long as you unscale by the same number (ie... it does not matter if you multiply by 100, 150, 173.25 or 128, as long as you unscale by the same number to get your final result). By substituting powers of two, a shifter can handle the multiply... NOW THAT'S REALLY EFFICIENT! [3] In times where you REALLY GOTTA SIMULATE FLOATING POINT because you either have: (A) A really nasty calculation to perform which requires non-fixed positions. (B) Been unable to figure out any nifty way to do it. Consider the number 152.3829. This number can be thought of as having two integer portions... 152 and 3829. The decimal point is 'implied'. When adding two real numbers using this method notice what happens: 152.3829 = 152 3829 +45.0020 = +45 +0020 -------- --- ---- 197.3849 197 3849 The only thing you have to watch out for is the decimal point shifting to a new higher or lower magnitude, and that the decimal portion is 'backwards' in terms of magnitude. This requires a little code to handle properly, but is far easier to deal with than true floating point: (1) Make sure that when the decimal portion shifts in magnitude that you move the magnitude portion into the integer side: .3829 + .9000 = .12829 WRONG .3829 + .9000 = 1.2829 RIGHT See... the answer to the addition produced a number which had more digits than the originals... this represents a magnitude change... in this case, everything to the left of the original magnitude needs to be moved (added) to the decimal side (for addition). (2) Make sure that the two decimal portions are the same magnitude before you start: [4] Other Goodies: Lets deal with some other simple TRICKS... Multiplying a number times 10... N * 10 = (N << 3) + (N << 1) Multiplying a number times 5... N * 5 = (N << 2) + N Almost any 'simple' multiply can be handled by shifts and adds where the resulting clock cycles are MUCH LESS than a multiply would have been. Conclusion: The trick to writing good integer math is to do it from the assembly standpoint. Most HIGH LEVEL programmers program assembly language as they would a high level language... this is why they bitch about the 'problems' with assembly language (to long, to hard to read, to hard to document). Assembly language has no problems, only the programmers. If they were to instead program assembly language like assembly language (ie, using EVERY trick in the book INCLUDING self modifying code) they would produce MUCH simplier algorithms (and faster)... NOW, apply this to high level languages and what happens??? You get code that executes 10 times faster... Example: In "C", may people would do this... A = ( B * 4); where they coulda done this: A = ( B << 2); The difference, besides readibility, is the amount of time it took to do the multiply (note... some efficiency compilers will convert the above example into the shift for the programmer). READABILITY: Make sure ALL tricks ARE WELL DOCUMENTED.... NEVER do self modifying code, or integer/real math tricks without SEVERE documentation showing what you did... this is a MUST in ANY language! -------------------------- T H E E N D --------------------------- (Disgruntled mathimaticians who read this should not be offended) just enlightened just enlightened -- | David P. Cook Net: uunet!epicb!david | | Truevision Inc. | "Sometimes I cover my mouth with | | Indianapolis, IN | my hand to tell if I'm breathing" | -----------------------------------------------------------