Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!uwm.edu!bionet!apple!vsi1!daver!versatc.versatec.COM!ritter
From: ritter@versatc.versatec.COM (Jack Ritter)
Newsgroups: comp.graphics
Subject: Fracturing self-intersecting polygons into trapezoids
Keywords: polygon,intersection,double precision, accuracy
Message-ID: <20408@versatc.versatec.COM>
Date: 26 Feb 90 21:34:35 GMT
Organization: Versatec, Santa Clara, Ca. 95051
Lines: 33


 I have a problem. I've inplemented the Newell & Sequin
 algorithm for breaking up an arbitrary (2d) polygon into
 a minimum # of trapezoids. I originally wrote the intersection()
 routine in 68020 assembly. I used 68020's "quad word" arithmetic, which
 allows multiplying 2 longs to get a 64 bit (quad word) intermediate
 result, then dividing down to a 32 bit result (computing the
 intersection of 2 arbitrary edges requires this kind of
 accumulation because you must make a product of products before
 dividing). This code worked very well, because I had complete control
 over the arithmetic, I looked for overflow, carry, etc.

 The problem is this: I must now implement the same algorithm
 in C. C has no ability to do quad word arithmetic. I've tried
 breaking up a 32X32 -> 64 muiltiply into factors, but you still
 need to detect carry. The alternative is floating point, but even
 by being careful about F.P. rounding, I get slightly different
 results than the original assembly code. 

 How can I do double precision fixed-point arithmetic in C?
-- 
   Versatec, Inc.
   Jack Ritter, M.S. 1-7
   2710 Walsh Ave.
   P.O. Box 58091
   Santa Clara, CA 95052-8091
   (408)982-4332, or (408)988-2800 X 5743
   UUCP:  {ames,apple,sun,pyramid}!versatc!ritter

   --( / __ - .. ((  /
   / / -- ) . \ \ // . (
	/ ** ) // _*_ // * ..
	) (( . \ / . * ) //